Paper Review: B*-Trees: A New Representation for Non-Slicing Floorplans

Abstract

We present in this paper an efficient, flexibile and effective data structure, B*-trees for non-slicing floorplans. B*-trees are based on ordered binary trees and the admissible placement presented in [1]. Inheriting from the nice properties of ordered binary trees, B*-trees are very easy for implementation and can perform the respective primitive tree operations search, insertion, and deletion in only O(1), O(1), and O(n) times while exisitng representations for non-slicing floorplans need at least O(n) time for each of these operations, where n is the number of modules. The correspondence between an admissible placement and its induced B*-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*-trees and their correspoding placements directly and incrementally. We further show the flexibility of B*-trees by exploring how to handle rotated, pre-placed, soft, and rectilinear modules. Experimental results on MCNC benchmarks show that the B*-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*-tree based simulated annealing scheme for floorplan design; the scheme achieves near optimum area utilization even for rectilinear modules.

Paper Location

ACM Portal

Citation

[1] Y. Chang, Y. Chang, G. Wu, and S. Wu, "B•-Trees: a new representation for non-slicing floorplans," Proceedings of the 37th conference on Design automation, ACM New York, NY, USA, 2000, p. 458–463.

Positive

• Extremely clear on the improvements of the B*-trees over O-trees and other previous implementations for non-slicing.
• Use of standard mathematical notation denoting runtime complexity.
• Makes a direct comparison to current "state-of-the-art" implementation of floorplanning.
• Lovely charts expressing the improvements that the B*-treez are able to achieve.

Negative

• Omits proofs of Lemmas and Theorems stated.