Title :
Area optimization of packing represented by sequence-pair
Author :
Ohmura, Tomokazu ; Fujiyoshi, Kunihiro ; Kodama, Chikaaki
Author_Institution :
Dept. of Electr. & Electron. Eng., Tokyo Univ. of Agric. & Technol., Japan
Abstract :
In the rectangle packing, “area optimization problem”, to minimize the whole area by rotating rectangles by 90 degrees, is proved to be NP-hard. But it can be solved in O(n2) time if the packing is restricted to a slicing structure. We propose a method using a local slicing structure to solve the problem efficiently. The packing is represented by a sequence-pair and the necessary and sufficient condition for the maximum local slicing structure is presented and proved. The experimental results show the effectiveness of the proposed method
Keywords :
VLSI; circuit complexity; circuit layout CAD; circuit optimisation; integrated circuit layout; minimisation; NP-hard problem; VLSI layout design; local slicing structure; packing area optimization; rectangle packing; sequence-pair representation; Agricultural engineering; Agriculture; Circuit topology; Cost function; Integrated circuit interconnections; Optimization methods; Performance evaluation; Stochastic processes; Very large scale integration; Wheels;
Conference_Titel :
Circuits and Systems, 2000. IEEE APCCAS 2000. The 2000 IEEE Asia-Pacific Conference on
Conference_Location :
Tianjin
Print_ISBN :
0-7803-6253-5
DOI :
10.1109/APCCAS.2000.913645
