Packing-based VLSI module placement using genetic algorithm with sequence-pair representation
Packing-based VLSI module placement using genetic algorithm with sequence-pair representation
- Author(s): A. Drakidis ; R.J. Mack ; R.E. Massara
- DOI: 10.1049/ip-cds:20050134
For access to this article, please select a purchase option:
Buy article PDF
Buy Knowledge Pack
IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.
Thank you
Your recommendation has been sent to your librarian.
- Author(s): A. Drakidis 1 ; R.J. Mack 1 ; R.E. Massara 1
-
-
View affiliations
-
Affiliations:
1: Electronic Systems Engineering Department, University of Essex, Colchester, UK
-
Affiliations:
1: Electronic Systems Engineering Department, University of Essex, Colchester, UK
- Source:
Volume 153, Issue 6,
December 2006,
p.
545 – 551
DOI: 10.1049/ip-cds:20050134 , Print ISSN 1350-2409, Online ISSN 1359-7000
The sequence-pair, a data structure with applications in packing-based VLSI module placement, has received significant amounts of research effort as the core of simulated annealing optimisers. Nevertheless, its application within genetic algorithm frameworks has not been adequately investigated. This paper presents a genetic algorithm approach to rectangle packing using the sequence-pair. The method is extended to handle symmetry constraints, a requirement often arising in the placement of analogue circuits. Genetic operators are developed taking into account the specific properties of the sequence-pair, and the algorithm is tested on several MCNC benchmarks.
Inspec keywords: genetic algorithms; circuit optimisation; VLSI; simulated annealing; integrated circuit layout
Other keywords:
Subjects: Semiconductor integrated circuit design, layout, modelling and testing; Optimisation techniques
References
-
-
1)
- F. Balasa , S.C. Maruvada , K. Krishnamoorthy . On the exploration of the solution space in analog placement with symmetry constraints. IEEE Trans. Comput. Aided. Des. Int. Circuits Syst. , 2 , 177 - 191
-
2)
- Takahashi, T.: `A new encoding scheme for rectangle packing problem', Proc. ASP-DAC, 2000, p. 175–178.
-
3)
- Krishnamoorthy, K., Maruvada, S., Balasa, F.: `Fast evaluation of symmetric-feasible sequence-pairs for analog topological placement', IEEE 5th Int. Conf. on ASIC, 2003, 1, p. 71–74.
-
4)
- F. Balasa , S.C. Maruvada . Using non-slicing topological representations for analog placement. IEICE Trans. Fundam. , 11 , 2785 - 2792
-
5)
- Pang, Y., Cheng, C.K., Yoshimura, T.: `An enhanced algorithm for floorplan design using the O-tree representation', Proc. ACM Int. Symp. Physical Design, 2000, p. 168–173.
-
6)
- Lin, J.M., Chang, Y.W.: `TCG-S: orthogonal coupling of P*-admissible representations for general floorplans', Design Automation Conf, 2002, p. 842–847.
-
7)
- Murata, H., Fujiyoshi, K., Nakatake, S., Kajtani, Y.: `Rectangle-packing-based module placement', IEEE Int. Conf. Computer-Aided Design, 1995, p. 472–479.
-
8)
- S. Nakatake , K. Fujiyoshi , H. Murata , Y. Kajitani . Module packing based on the BSG-structure and IC layout applications. IEEE Trans. Comput.- Aided Des. Integr. Circuits Syst. , 6 , 519 - 530
-
9)
- Guo, P.N., Cheng, C.K., Yoshimura, T.: `An O-tree representation of non-slicing floorplan and its applications', Proc 36th ACM/IEEE Design Automation Conf., 1999, p. 268–273.
-
10)
- Hatta, K., Wakabayashi, S., Koide, T.: `Solving the rectangular packing problem by an adaptive GA based on sequence-pair', Proc. ASP-DAC, 1999, 1, p. 181–184.
-
11)
- A. Lodi , S. Martello , M. Monaci . Two-dimensional packing problems: a survey. Eur. J. Oper. Res. , 241 - 252
-
12)
- Balasa, F.: `Modeling non-slicing floorplans with binary trees', Proc. IEEE Conf. CAD, 2000, p. 13–16.
-
13)
- Crawford, K.D., Wainwright, R.: `Research question: how does one go about developing a new crossover operator with an a priori expectation of its merit? (a survey of crossover operators for genetic algorithms)', UTULSA-MCS-96-2, Technical Report, , The University of Tulsa.
-
14)
- C. Lin , A.H.M. Van Roermund , M.W. Leenaerts . (2003) Mixed-signal layout generation concepts.
-
15)
- Kodama, C., Fujiyoshi, K.: `Selected sequence-pair: an efficient decodable packing representation in linear time using sequence-pair', IEEE ASP-DAC, 2003, p. 331–337.
-
16)
- Lin, J.M., Chang, Y.W.: `TCG: a transitive closure graph-based representation for nonslicing floorplans', 2001, Proc. Design Automation Conf., 2001, p. 764–769.
-
17)
- J. Cohn , D. Garrod , R. Rutenbar , L. Carley . (1994) Analog device-level layout automation.
-
18)
- Chang, Y.C., Chang, Y.W., Wu, G.M., Wu, S.W.: `B*-trees: a new representation for non-slicing floorplans', Design Automation Conf., 2000, p. 458–463.
-
19)
- X. Tang , R. Tian , D.F. Wong . Fast evaluation of sequence pair in block placement by longest common subsequence computation. IEEE Trans. Comput.-Aided Des. Int. Circuits Syst. , 12 , 1406 - 1413
-
20)
- Nakaya, S., Koide, T., Wakabayashi, S.: `An adaptive genetic algorithm for VLSI floorplanning based on sequence-pair', IEEE Int. Symp. on Circuits and Systems, 2000, p. III65–III68.
-
21)
- J.M. Lin , Y.W. Chang . TCG: a transitive closure graph-based representation for general floorplans. IEEE Trans. VLSI Syst. , 2 , 288 - 292
-
22)
- A.E. Eiben , J.E. Smith . (2003) Introduction to evolutionary computing.
-
23)
- Onodera, H., Taniguchi, Y., Tamaru, K.: `Branch-and-bound placement for building block layout', IEEE/ACM Design Automation Conf., 1991, p. 433–439.
-
24)
- F. Balasa , K. Lampaert . Symmetry within the sequence-pair representation in the context of placement for analog design. IEEE Trans. Comput.-Aided Des. Int. Circuits Syst. , 7 , 721 - 731
-
1)
Related content
