QB-trees: Towards an optimal topological representation and its applications to analog layout designs
QB-trees: Towards an optimal topological representation and its applications to analog layout designs
复制标题
QB 树：实现最佳拓扑表示及其在模拟布局设计中的应用
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Yao
中科院分区：
文献类型：
--
作者：
I;H. Ou;Yao
现代模拟砂矿机通常需要考虑各种几何约束来生成所需的布局。为了同时处理一般约束，目前最先进的作品采用基于拓扑表示的模拟退火，因为它们的解空间更小，效率更高。然而，对于一般的几何约束处理和模块打包，没有发表的工作达到最优的时间复杂度。此外，每项工作只考虑和处理有限的约束条件。为了弥补这些不足，我们提出了一种新的四叉树和B*树（简称qb树）的混合表示，以处理一般的几何约束，同时实现线性，模块包装和约束处理的下界时间复杂度。基于各种约束条件的实际工业设计的实验结果表明，我们的砂矿机在运行时间和解决方案质量方面都优于已发表的领先作品。
A modern analog placer often needs to consider various geometrical constraints to generate desired layouts. To handle general constraints simultaneously, current state-of-the-art works adopt simulated annealing based on topological representations, due to their smaller solution spaces and higher efficiency. However, no published work achieves the optimal time complexity for general geometrical constraint handling and module packing. Besides, only limited constraints are considered and handled in each work. To remedy these insufficiencies, we present a new hybrid representation of a quadtree and B*-trees (QB-tree, for short) to handle general geometrical constraints while achieving linear, lower-bound time complexity of module packing and constraint handling. Experimental results based on real industrial designs with various constraints show that our placer outperforms the leading published works in both runtime and solution quality.