Efficient Net Extraction for Restricted Orientation Designs [Short Paper] - Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Efficient Net Extraction for Restricted Orientation Designs [Short Paper] - Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
复制标题
受限方向设计的高效网络提取[短论文] - 集成电路和系统的计算机辅助设计，IEEE Transactions
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
S. Sahni
中科院分区：
文献类型：
--
作者：
S. Sahni
网络提取对于 VLSI 设计验证至关重要。当前的网络提取算法没有利用以下事实：实际VLSI掩模设计中线段或多边形的不同方向的数量c相对于线段或多边形边缘的数量n来说较小。相反，它们依赖于计算输入中的所有交叉点，因此花费的时间至少与交叉点的数量成正比。在本文中，我们开发并实现了一种实用的网络提取算法，该算法在 O(cn1ogn) 时间和 o(n) 空间中运行，对于固定 c 是最佳的。该算法仅使用整数运算，因此在数值上是稳定的。实验表明，在实际 VLSI 设计中，该算法将优于现有算法。我们预计所提出的技术将在其他使用受限方向几何形状操作的 VLSYCAD 问题中发挥作用。
Net extraction is crucial in VLSI design verification. Current algorithms for net extraction do not exploit the fact that the number, c, of different orientations of the line segments or polygons in a practical VLSI mask design is small relative to the number, n, of segments or polygon edges. Instead they rely on computing all intersections in the input and hence take time that is at least proportional to the number of intersections. In this paper we develop and implement a practical algorithm for net extraction that runs in O(cn1ogn) time and o(n) space, which is optimal for fixed c. The algorithm uses only integer operations and is, as a result, numerically stable. Experiments indicate that the algorithm will outperform existing algorithms on practical VLSI designs, We expect that the techniques presented will he useful in other VLSYCAD problems that operate with restricted orientation geometries.