一种通孔最小化的三层通道布线算法  

AN ALGORITHM FOR THREE-LAYER CHANNEL ROUTING WITH VIA MINIMIZATION

作　　者：宋学军[1] 刘美轮 

机构地区：[1]天津大学电力及自动化工程系,天津300072

出　　处：《计算机学报》1992年第6期417-425,共9页Chinese Journal of Computers

基　　金：国家自然科学基金

摘　　要：本文提出的连通孔最小化的三层通道布线算法,根据线网的接点位置建立线网分层图,并对此图进行三着色,确定出初始布线集和分拆线网集,通过引进线网次序图、压缩空段长度、填充原则和逐步排障法等,将初始布线集和拆网集的线网分配到相应的走线道上.实现线网的互连.本算法已用PASCAL语言编程,并在XT/286机上实现.结果表明,该算法不仅使通孔数大大减少,而且有些例子的走线道数也较一般布线法少.An algorithm for three-layer channel routing with via minimization ispresented in this paper. The algorithm is based on the definition of net-layering graph and 3-vertex colouring of this graph. All nets are divided into three initial routing sets and a layer-changing set. With the introduction of the net-order graph, the empty length utilizing, the principle of filling up space, the method of getting round obstacles and so on, the algorithm assigns each net of both kinds of sets to certain tracks and completes all connections with as fewer tracks and vias as possible. This algorithm has been coded in PASCAL and implemented on an XT/286 computer. Experimental results show that the numbers of vias can be reduced greatly and, for some examples, the numbers of tracks are also less than those of known results.

关 键 词：通道 布线 集成电路 算法 

分 类 号：TN402[电子电信—微电子学与固体电子学]