Title :
Twin binary sequences: a nonredundant representation for general nonslicing floorplan
Author :
Young, Evangeline F Y ; Chu, Chris C N ; Shen, Zion Cien
Author_Institution :
Dept. of Comput. Sci. & Eng., Chinese Univ. of Hong Kong, China
fDate :
4/1/2003 12:00:00 AM
Abstract :
The efficiency and effectiveness of many floorplanning methods depend very much on the representation of the geometrical relationship between the modules. A good representation can shorten the searching process so that more accurate estimations on area and interconnect costs can be performed. Nonslicing floorplan is the most general kind of floorplan that is commonly used. Unfortunately, there is not yet any complete and nonredundant topological representation for nonslicing structure. In this paper, we propose the first representation of this kind. Like some previous work (Zhou et al. 2001), we have also made use of a mosaic floorplan as an intermediate step. However, instead of including a more than sufficient number of extra dummy blocks in the set of modules (that will increase the size of the solution space significantly), our representation allows us to insert an exact number of irreducible empty rooms to a mosaic floorplan such that every nonslicing floorplan can be obtained uniquely from one and only one mosaic floorplan. The size of the solution space is only O(n!23n/n1.5), which is the size without empty room insertion, but every nonslicing floorplan can be generated uniquely and efficiently in linear time without any redundant representation.
Keywords :
VLSI; binary sequences; circuit layout CAD; circuit optimisation; integrated circuit layout; network topology; simulated annealing; CAD; VLSI; computer-aided design; floorplan optimization; irreducible empty rooms insertion; mosaic floorplan; nonredundant topological representation; nonslicing floorplan; simulated annealing; twin binary sequences; very large scale integration; Binary sequences; Circuit optimization; Computer science; Costs; Delay; Design optimization; Integrated circuit interconnections; Minimization; Shape; Very large scale integration;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
DOI :
10.1109/TCAD.2003.809651