B*-trees: a new representation for non-slicing floorplans
B*-trees: a new representation for non-slicing floorplans
复制标题
DOI：
10.1109/dac.2000.855354
复制
发表时间：
2000-06
期刊：
影响因子：
--
通讯作者：
Yun-Chih Chang;Yao-Wen Chang;G. Wu;Shu-Wei Wu
中科院分区：
文献类型：
--
作者：
Yun-Chih Chang;Yao-Wen Chang;G. Wu;Shu-Wei Wu
本文提出了一种高效、灵活、有效的非切片布图规划数据结构--B* 树。B*-树是建立在有序二叉树和文献[1]中提出的容许布局的基础上的。继承了有序二叉树的优良特性，B*-树非常容易实现，并且可以在O（1），O（1）和O（n）时间内执行相应的原始树，操作搜索，插入和删除，而现有的非切片布图表示至少需要O（n）时间来执行这些操作中的每一个，其中n是模块的数量。容许布局与其导出B* 树之间的对应关系是1对1的（即，无冗余）;此外，它们之间的转换仅花费线性时间。与需要构造用于成本评估的约束图的非切片布图规划的其他表示不同，特别地，可以直接地和递增地对B* 树及其对应的放置执行评估。我们进一步展示了B* 树的灵活性，探索如何处理旋转，预置，软，和直线模块。MCNC基准测试的实验结果表明，B* 树表示的运行速度约为O树表示的4.5倍，占用内存约减少60%，并且导致硅面积更小[1]。我们还开发了一个基于B* 树的模拟退火方案的布图设计，该方案实现了接近最佳的面积利用率，即使是直线模块。
We present in this paper an efficient, flexible, 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 existing 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 corresponding 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.