Soft Block Packing Based on Bounded Slicing Grid Structure

摘要

Soft block packing has become an increasingly important issue in early floorplanning stage where the shapes of many blocks are still open to design. This paper presents a soft block packign method for a set of blocks with fixed areas but flexible shapes, based on a packing topology representation named bounded slicing grid (BSG). The method in this paper is based on an extension and enhancement of the techniques proposed in (1). Given a packing topology, this method gradually adjusts the block shapes to reduce the overall height and overall width alternatively and monotonously. A greedy approach is applied to perform each step of overall height reduction or overall width reduction. Such shape optimization procedure is embedded into the stochastic search of a topology such that its corresponding compacted packing of the blocks with optimized shapes meets the total area constraint and has an minimized total wire length. Experiment results show that the algorithm is very efficient in terms of solution quality and running time.