10.2.3. B*-tree for compacted floorplans
B*-trees are based on ordered binary trees to model compacted floorplans. In a compacted floorplan, no modules can be moved toward left or bottom in the floorplan [Chang 2000]. Consequently, an area-optimal floorplan always corresponds to some B*-tree. Inheriting from the nice properties of ordered binary trees, B*-trees are very easy for implementation and can perform the three primitive tree operations search, insertion, and deletion in constant, constant, and linear time, respectively.
Unlike the slicing floorplan and its corresponding slicing tree(s), there exists a unique correspondence between a compacted floorplan and its induced B*-tree. In other words, given a compacted floorplan F, we can ...
Get Electronic Design Automation now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
