A corner stitching compliant B∗-tree representation and its applications to analog placement
A corner stitching compliant B∗-tree representation and its applications to analog placement
复制标题
符合角缝合的 B* 树表示及其在模拟布局中的应用
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Dick Liu
中科院分区：
文献类型：
--
作者：
Hui;Pang;Shih;Yao;Mark Po;Duan;Dick Liu
现代电路布局，尤其是模拟布局，通常需要考虑各种约束，如对称性、邻近性、预置、可变、固定边界、最小间隔、边界和固定轮廓约束，以获得更好的电气效果和更高的性能。为了处理这些不同的约束，拓扑逻辑平面表示被广泛使用，因为它们具有更高的灵活性和更小的解空间。然而，由于它们在直接从表示本身获得模块邻接信息方面的固有局限性，它们在处理相关约束时可能会遇到困难。在本文中，我们研究了已被证明是解决布局规划问题最有效和最有效的B∗树，并提出了一种角缝顺应B∗树(简称CB树)，以弥补其模块邻接处理方面的显著不足。CB树是一种B∗树，集成了改进的角缝合，以提供更高的灵活性/效率，特别是对于相邻模块识别/封装。与前人的工作相比，CB-树可以在满足上述约束的情况下实现最低的模块布局时间复杂度。实验结果表明，对于各种约束条件下的工业设计，CB-树具有最好的解质量和最小的运行时间。特别是，我们的工作为使用拓扑表示处理全面的放置约束提供了关键的见解。
Modern circuit placement, especially analog placement, often needs to consider various constraints, such as symmetry, proximity, preplaced, variant, fixed-boundary, minimum separation, boundary, and fixed-outline constraints, for better electrical effects and higher performance. To handle these diverse constraints, topo-logical floorplan representations are pervasively used because of their higher flexibility and smaller solution space. Due to their intrinsic limitation in deriving module adjacency information directly from the representations themselves, however, they might incur difficulties in handling related constraints. In this paper, we work on B∗-trees, which have been shown to be most effective and efficient for floor-plan/placement problems, and present a corner stitching compliant B∗-tree (CB-tree, for short) to remedy the significant deficiency in its module adjacency handling. A CB-tree is a B∗-tree integrated with modified corner stitching to offer much higher flexibility/efficiency, especially for adjacent module identification/packing. Compared with the previous works, CB-trees can achieve the lowest time complexity for module packing with the aforementioned constraints. Experimental results show that the CB-trees achieve the best solution quality and consume the least running time for industrial designs with various constraints. In particular, our work provides key insights into the handling of comprehensive placement constraints with a topological representation.