3-D floorplanning using labeled tree and dual sequences

Abstract

3-D packing is an NP-hard problem with wide applications in microelectronic circuit design such as 3-D packaging, 3-D VLSI placement and dynamically reconfigurable FGPA design. We present a complete representation for general non-slicing 3-D floorplan or packing structures, which uses a labeled tree and dual sequences. For each compact placement, there is a corresponding encoding. The number of possible tree-sequence combinations is (n+1)n-1(n!)2, the lowest among complete 3-D representations up to date. The construction of placement from an encoding needs O(n2) in the worst case, but in practical cases we expect O(n4⁄3 log n) time on average for circuit blocks with limited length/width ratios. Experimental results show promising performance using the labeled tree and dual sequences on 3-D floorplan and placement optimizations