B*-trees: a new representation for non-slicing floorplans

By Yun-Chih Chang, Yao-Wen Chang, G. Wu, Shu-Wei Wu. Proceedings - Design Automation Conference, 2000

580 citations recorded by the source corpus.

We present in this paper an efficient, flexible, and effective data structure, <italic>B<supscrpt>*</supscrpt>-trees</italic> for non-slicing floorplans. B<supscrpt>*</supscrpt>-trees are based on ordered binary trees and the admissible placement presented in [1]. Inheriting from the nice properties of ordered binary trees, B<supscrpt>*</supscrpt>-trees are very easy for implementation and can perform the respective primitive tree, operations search, insertion, and deletion in only <italic>O</italic>(1), <italic>O</italic>(1), and <italic>O</italic>(<italic>n</italic>) times while existing representations for non-slicing floorplans need at least <italic>O</italic>(<italic>n</italic>) time for each of these operations, where <italic>n</italic> is the number of modules. The correspondence between an admissible placement and its induced B<supscrpt>*</supscrpt>-tree is 1-to-1 (i.e., no redundancy); further, the transformation between them takes only linear time. Unlike other representations for non-slicing floorplans that need to construct constraint graphs for cost evaluation, in particular, the evaluation can be performed on B<supscrpt>*</supscrpt>-trees and their corresponding placements <italic>directly</italic> and <italic>incrementally</italic>. We further show the flexibility of B<supscrpt>*</supscrpt>-trees by exploring how to handle rotated, pre-placed, soft, and rectilinear modules. Experimental results on MCNC benchmarks show that the B<supscrpt>*</supscrpt>-tree representation runs about 4.5 times faster, consumes about 60% less memory, and results in smaller silicon area than the O-tree one [1]. We also develop a B<supscrpt>*</supscrpt>-tree based simulated annealing scheme for floorplan design; the scheme achieves near optimum area utilization even for rectilinear modules.

View Paper: https://www.semanticscholar.org/paper/c2b1e2d937214ef2c11c69776d23183d8557ddcf

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Fixed-outline floorplanning: enabling hierarchical design (2003, background): “That is because all wirelength-minimal solutions in this formulation can be captured by compacted representations such as sequence pairs [20], -trees [23], -trees [ 5 ], and corner block lists [11].”
A thermal-driven floorplanning algorithm for 3D ICs (2004, background): “The four side walls and top of the chip are treated as ambient, since the chip is usually packaged in thermally insulated materials.”