An efficient algorithm for layout compaction problem with symmetry constraints
An efficient algorithm for layout compaction problem with symmetry constraints
复制标题
一种求解对称约束布局压缩问题的高效算法
DOI：
10.1109/iccad.1989.76924
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
K. Tamariu
中科院分区：
文献类型：
--
作者：
R. Okuda;Takashi Sato;H. Onodera;K. Tamariu
针对具有对称性约束的符号布局压缩问题，提出了一种有效的算法。对称约束在布局压缩期间保持电路元件的几何对称。它对于模拟LSI的符号布局是必不可少的，其中元件之间的几何对称性很重要。然而，它使得压缩问题如此复杂，以至于除了耗时的线性规划算法之外，还没有有效的算法。该算法综合运用了基于图的方法和线性规划方法，充分利用了前者的快速性和后者的通用性。作者在布局压缩程序中实现了所提出的算法。实验结果表明，该算法具有较好的实时性. <<ETX>>
An efficient algorithm is presented for the symbolic layout compaction problem with symmetry constraints. The symmetry constraint maintains the geometric symmetry of the circuit components during the layout compaction. It is indispensable to the symbolic layout for analog LSIs where the geometric symmetry between the components is important. However, it makes the compaction problem so complicated that no efficient algorithm has ever been shown except for the time-consuming linear programming algorithm. The proposed algorithm uses both the graph-based technique and the linear programming technique, and takes advantage of the high speed of the former and the generality of the latter. The authors implemented the proposed algorithm in a layout compaction program. The experimental results show that the proposed algorithm is fast enough for practical use.<<ETX>>