确定区域详细布线算法

提出了一种确定区域的详细布线算法，它能对不同设计模式进行布线。该算法能适用于任意多层布线情况，并且支持不同布线层具有的不同工艺参数，在构造布线树时，考虑芯片当前的走线拥挤度，使布线比较平均，并加快了算法运行速度、改善了布线质量，在连接两点线网时，构造基于二维迷宫布线结果的分层图，提出了一种对分层图的启发式染色算示来进行布线层分配，大大提高算法布线速度，采用拆线重布的方法来处理布线失败的线网。

A DETAILED ROUTING ALGORITHM FOR THE DEFINITE AREA

An algorithm for the definite area detailed routing is presented. The algorithm can handle different design styles. Multiple routing layers and differing design rules of each layer are also supported. The wire congestion during construction of the routing tree is taken into consideration and measures are taken to average the wire congestion of the area, thus both the running time and the routing quality are improved. To avoid routing all nets in three dimensions, a heuristic algorithm for the graph coloring is proposed to solve the layer assignment problem. The rip up and rerouting techniques are used to link the unconnected nets.