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 ripup and rerouting techniques are used to link the unconnected nets．