A VLSI artwork legalization technique based on a new criterion of minimum layout perturbation
A VLSI artwork legalization technique based on a new criterion of minimum layout perturbation
复制标题
基于最小布局扰动新标准的VLSI图稿合法化技术
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
G. Téllez
中科院分区：
文献类型：
--
作者：
Fook;Zhan Chen;G. Téllez
在本文中，我们提出了一种新的VLSI图形修改技术的基础上的最小布局扰动的概念。布局设计必须满足最低设计规则。通常，布局过程（如自定义布局方法和设计规则迁移活动）会在布局中引入设计规则违规。最小布局扰动定义了对布局的最小成本改变，使得所得到的布局满足所有设计规则。我们制定的最小扰动成本的目标是尽可能多地保留原始布局的几何和拓扑特征。提出的最小扰动问题公式转化为一个具有特殊结构的线性规划问题。我们利用问题的结构来提出解决问题的有效算法。我们还提出并实现了一个实用的基于图的单纯形算法，我们比较商业上可用的线性规划包，在某些情况下，导致超过40倍的性能改进。最后，所提出的方法已被实施，并用于真实的生活问题，例如，在技术迁移的数据路径宏和300单元门阵列库。
In this paper we propose a novel VLSI artwork modification technique based on the concept of a minimum layoutperturbation. Layouts are designed so that minimum design rules must be satisfied. Often layout processes such as custom layout methodologies and design rule migration activities introduce design rule violations in layouts. A minimum layout perturbation defines a minimum cost change to a layout, such that the resulting layout satisfies all design rules. We formulate the minimum perturbation cost with the objective of preserving as much as possible the geometric and topological features of the original layout. The proposed minimum perturbation problem formulation is transformed into a linear programming problem with special structure. We exploit the structure of the problem to propose efficient algorithms that solve the problem. We also propose and implement a practical graph-based simplex algorithm, which we compare to a commercially available linear programming package, resulting in more than 40X performance improvements in some cases. Finally, the proposed methods have been implemented and used in real life problems, for example in the technology migration of data path macros and a 30O-cell gate array library.