Title :
The multi-BSG: stochastic approach to an optimum packing of convex-rectilinear blocks
Author :
Sakanushi, K. ; Nakatake, S. ; Kajitani, Y.
Author_Institution :
Dept. of Electr. & Electron. Eng., Tokyo Inst. of Technol., Japan
Abstract :
A floorplanner that can handle convex-rectilinear blocks is developed by enhancing the BSG-based packing algorithm. The ideas are in the introduction of (1) multi-rectangle representation of a block as a superpose of element-rectangles, (2) parametric-BSG as a generalization of the BSG, (3) multi-BSG which is an arrangement of plural BSG´s on a multi-layer, and (4) layer sharing condition of element-rectangles so that non-overlapping is discussed on each layer. A solution space of packings is defined as the set of packings generated by changing parametric-BSG and room assignments. It is guaranteed to contain an optimal packing if the BSG is not smaller than a certain size. A floorplan based on a simulated annealing was implemented. In experiments, it output highly compressed packings.
Keywords :
algorithm theory; bin packing; circuit layout CAD; circuit optimisation; integrated circuit layout; simulated annealing; stochastic processes; BSG-based packing algorithm; convex-rectilinear block handling; element rectangles; floorplanner; highly compressed packings; layer sharing condition; multi-BSG; multi-rectangle representation; multilayer; nonoverlapping; optimal packing; parametric-BSG; plural BSGs; room assignments; simulated annealing; solution space; stochastic approach; Brain modeling; Electroencephalography; Electron microscopy; Electronic circuits; Electronic mail; Large-scale systems; Permission; Semiconductor device manufacture; Simulated annealing; Stochastic processes;
Conference_Titel :
Computer-Aided Design, 1998. ICCAD 98. Digest of Technical Papers. 1998 IEEE/ACM International Conference on
Conference_Location :
San Jose, CA, USA
Print_ISBN :
1-58113-008-2
DOI :
10.1109/ICCAD.1998.144277
