一种用于VLSI的统一通孔最少化和线长最小化层分配算法  

A LAYER ASSIGNMENT ALGORITHM FOR UNIFIED VIA MINIMIZATION AND WIRE LENGTH MINIMIZATION ON THE SPECIFIED LAYER IN VLSI

作　　者：洪先龙[1] 潘立 王尔乾[1] 

机构地区：[1]清华大学计算机科学与技术系

出　　处：《计算机学报》1997年第4期335-341,共7页Chinese Journal of Computers

基　　金：国家自然科学基金

摘　　要：本文提出了统一通孔最少化和线长最小化层分配的图论模型．它考虑到不同层电性能不等对线长分布的特殊要求，给出了指定层上线长最小化的形式化描述．在此基础上，本文给出了通孔最少化和线长最小化的统一组合目标，并用一种启发式算法去求解层分配算法．文中还讨论了工程中的许多实际问题的处理方法．算法已用Ｃ语言在ＳＵＮ工作站上实现．实验结果表明，算法十分有效且稳定．A unified graphic model of layer assignment for via minimization and wire length minimization on the specified layer is proposed in this paper. The model considers the special request for wire length assignment on double layers with different electrical performance and gives a formulation of wire length minimization on the specified layer. Based on the model, a unified combined objective for via minimization and wire length minimization is proposed and a heuristic algorithm is used to solve the layer assignment problem. Some solving techniques for practical problems in engineering applications are also discussed in this paper. Experimental results show that the algorithm is efficient and stable.

关 键 词：通孔最小化 线长最小化 层分配 布线 VLSI 

分 类 号：TN470.2[电子电信—微电子学与固体电子学]