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

fYear

2000

fDate

2000

Firstpage

813

Lastpage

816

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(n²) 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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/APCCAS.2000.913645

Filename

913645