用改进激活集合法优化VLSI互连线

Optimizate VLSI Wire by Modified Active Set Method

本文介绍离散线宽的单根互连线时延优化的一种算法:改进激活集合法(MASM)。基于Elmore时延模型,单根互连线的优化问题能被表述为凸二次规划,能在多项式时间里求解,得到最优结果。它是一种非常高效的算法,计算结果证明了此算法的有效性。

In this paper, we introduce a algorithm, approach to the problem of delay minimization for a wire of discrete choices of wire width: Modified Active Set Method(MASM). Based on the Elmore delay model, the problem for wire sizing for a wire can be formulated as a convex quadratic program, which is known to be solvable in polynomial time and derive an optimal solution. It is a very efficient algorithm. The effectiveness of the algorithm is proved by the calculate result.