B*-trees: The first binary-tree based representation of general floorplans for VLSI design

Abstract:

     We present in this talk a data structure, B*-trees, to
represent the topological relations between modules of a general floorplan
for VLSI design. B*-trees are based on ordered binary trees and compacted
placement, and the correspondence between a compacted placement and its
induced B*-tree is 1-to-1. Inheriting from the nice properties of ordered
binary trees, B*-trees are very simple, efficient, flexible, and
effective. It takes only constant time for tree search and insertion, and
linear time for tree deletion and transformation between a B*-tree and a
placement. Further, the cost of a floorplan can be evaluated on B*-trees
directly and incrementally. We show the flexibility of B*-trees by
exploring how to handle hard, soft, preplaced, rectilinear, and
large-scale modules using B*-trees.  Experimental results show the
superiority of B*-trees.