VLSI和PCB双层布线中的通孔最少化算法  

Via Minimization Algorithm for Double-Layer in VLSI and PCB

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

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

出　　处：《Journal of Semiconductors》1996年第7期533-539,共7页半导体学报（英文版）

基　　金：国家自然科学基金

摘　　要：本文提出了一个新的通孔最少化层分配的图模型．该模型克服了传统层分配算法对通孔度数和位置的限制，允许通孔自由地以任意度数和任何需要的位置出现．模型中还提出了通孔秩的概念，它比较能更精确地反映通孔的本质．在此基础上，本文将通孔最少化问题转化为图的最大割问题，并提出了一种启发式算法去求解图的最大割．算法已用Ｃ语言在ＳＵＮ工作站上实现．实验结果表明，算法十分有效且稳定．Abstract A new graphic model of layer assignment for via minimization is proposed.The model has overcome strict limitations of traditional layer assignment methods in via degree and location, and allows that the via appears with freedom in any degrees and anywhere.The conception of via rank is proposed in this model.It can represent the essence of via more precisely than degree of via.Then the via minimization problem is formulated as a maximum cut of weighted graph and a heuristic algorithm is used to solve it. The algorithm is implemented in C language under UNIX operating system on SUN workstation.Experiment results show that the algorithm is efficient and stable.

关 键 词：VLSI PCB 双层布线 通孔最少化算法 

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