TCG: A transitive closure graph-based representation for general floorplans
TCG: A transitive closure graph-based representation for general floorplans
复制标题
DOI：
10.1109/tvlsi.2004.840760
复制
发表时间：
2005-02
影响因子：
2.8
通讯作者：
Jai-Ming Lin;Yao-Wen Chang
中科院分区：
文献类型：
--
作者：
Jai-Ming Lin;Yao-Wen Chang
在本文中，我们引入了P*-容许表示的概念，并提出了一种基于P*-容许的传递闭包图的一般布图表示，称为传递闭包图（TCG），并显示其优越的上级性质。TCG结合了流行的表示方法，如序列对、BSG和B* 树的优点。与序列偶和BSG相似，但与O-树、B*-树和CBL不同，TCG是P*-可容许的。类似于B*-树，但不同于序列对、BSG、O-树和CBL，TCG不需要在打包期间构造用于成本评估的额外约束图，这意味着更快的运行时间。此外，TCG支持在操作过程中的增量更新，并保持边界模块的信息，以及形状和相对位置的模块表示。更重要的是，模块之间的几何关系不仅对TCG表示是透明的，而且对其操作也是透明的，从而有助于收敛到期望的解。所有这些属性使TCG处理一般布图/布局设计问题的各种约束的有效和灵活的表示。实验结果表明，承诺的TCG。
In this brief, we introduce the concept of the P*-admissible representation and propose a P*-admissible, transitive closure graph-based representation for general floorplans, called transitive closure graph (TCG), and show its superior properties. TCG combines the advantages of popular representations such as sequence pair, BSG, and B*-tree. Like sequence pair and BSG, but unlike O-tree, B*-tree, and CBL, TCG is P*-admissible. Like B*-tree, but unlike sequence pair, BSG, O-tree, and CBL, TCG does not need to construct additional constraint graphs for the cost evaluation during packing, implying a faster runtime. Further, TCG supports incremental update during operations and keeps the information of boundary modules as well as the shapes and the relative positions of modules in the representation. More importantly, the geometric relation among modules is transparent not only to the TCG representation but also to its operation, facilitating the convergence to a desired solution. All of these properties make TCG an effective and flexible representation for handling the general floorplan/placement design problems with various constraints. Experimental results show the promise of TCG.