The multi-BSG: stochastic approach to an optimum packing of convex-rectilinear blocks

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.