Paper Info
Title
Moving Block Sequence and Organizational Evolutionary Algorithm for General Floorplanning With Arbitrarily Shaped Rectilinear Blocks
Abstract
A new nonslicing floorplan representation, the moving block sequence (MBS), is proposed in this paper. Our idea of the MBS originates from the observation that placing blocks on a chip has some similarities to playing the game, Tetrisreg. Since no extra constraints are exerted on solution spaces, the MBS is not only useful for evolutionary algorithms, but also for dealing with rectangular, convex rectilinear, and concave rectilinear blocks, similarly and simultaneously, without partitioning rectilinear blocks into subblocks. This is owed to a special structure designed for recording the information of both convex and concave rectilinear blocks in a uniform form. Theoretical analyses show that the computational cost of transforming an MBS to a floorplan with rectangular blocks, in terms of the number of blocks, is between linear and quadratic. Furthermore, as a follow-up of our previous works, a new organizational evolutionary algorithm (OEA) based on the MBS (MBS-OEA) is proposed. With the intrinsic properties of the MBS in mind, three new evolutionary operators are designed in the MBS-OEA. To test the performance of the MBS-OEA, benchmarks with hard rectangular, soft rectangular, and hard rectilinear blocks are used. The number of blocks in these benchmarks varies from 9 to 300. Also, the MBS-OEA and several well-designed existing algorithms are compared. The results show that the MBS-OEA can find high quality solutions for various problems. Additionally, the MBS-OEA shows a good performance in solving the problems with 300 hard rectangular blocks, 100 soft rectangular blocks, and 100 hybrid blocks, including both soft rectangular and hard rectilinear blocks. This illustrates that the MBS-OEA is not only suitable for solving a wide range of problems, but also competent for solving large-scale problems. Finally, a set of specific experiments is designed to identify the key component that is mainly responsible for the good performance of the MBS-OEA.
Year
DOI
Venue
2008
10.1109/TEVC.2008.920679
IEEE Trans. Evolutionary Computation
Keywords
Field
DocType
organization,organizational evolutionary algorithm,block sequence,hard rectangular block,evolutionary algorithm,arbitrarily shaped rectilinear blocks,evolutionary computation,general floorplanning,rectilinear block,circuit layout,floorplanning,soft rectangular blocks,convex rectilinear blocks,rectangular block,hard rectilinear blocks,very large scale integration,new nonslicing floorplan representation,concave rectilinear block,soft rectangular block,hard rectilinear block,hard rectangular blocks,evolutionary algorithms,vlsi,integrated circuit design,nonslicing floorplan representation,good performance,moving block sequence,concave rectilinear blocks,new evolutionary operator,indexing terms,circuits,information technology,information processing,benchmark testing,chip
Mathematical optimization,Evolutionary algorithm,Evolutionary computation,Quadratic equation,Algorithm,Regular polygon,Very-large-scale integration,Benchmark (computing),Mathematics,Bin packing problem,Floorplan
Journal
Volume
Issue
ISSN
12
5
1089-778X
Citations 
PageRank 
References 
17
0.75
48
Authors
4
Name
Order
Citations
PageRank
Jing Liu11043115.54
Weicai Zhong238126.14
Licheng Jiao35698475.84
Xue Li42196186.96