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

本文提出的连通孔最小化的三层通道布线算法,根据线网的接点位置建立线网分层图,并对此图进行三着色,确定出初始布线集和分拆线网集,通过引进线网次序图、压缩空段长度、填充原则和逐步排障法等,将初始布线集和拆网集的线网分配到相应的走线道上.实现线网的互连.本算法已用PASCAL语言编程,并在XT/286机上实现.结果表明,该算法不仅使通孔数大大减少,而且有些例子的走线道数也较一般布线法少.

AN ALGORITHM FOR THREE-LAYER CHANNEL ROUTING WITH VIA MINIMIZATION

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.