STRONGROUTER = A Strong General Multi-Layer Area Router for Layout Design Automation of VLSI and PCB

다국어 초록 (Multilingual Abstract)

A strong general multi-layer area router for layout design automation of VLSI and PCB, called STRONGROUTER, is presented in this paper. STRONGROUTER can route various types of routing areas, such as L-shaped channel, switchbox with/without obstacles, and rectilinear area with/without internal modules/terminals. Also, STRONGROUTER can deal with 45° routing.
The STRONGROUTER algorithm consists of five major stages : layerless maze routing, layering, rip-up and reroute, post-processing, and 45° routing. In the layerless maze routing stage, the route of each net is determined by modified maze algorithm without taking the conflicts(short circuits) into account. In layering stage, the layer of each net is determined by a heuristic coloring algorithm. When the conflicts are not removed, rip-up and reroute process is invoked. In rip-up and reroute stager the conflicts are removed iteratively. In post-processing stage, routing result is refined by simple via minimization and wire length minimization process. The 45° routing stage is used for non-Manhattan result output. Inserted wire segment is used to separate terminals which are too close to allow the generation of 45° wires.
Many test cases have been run, and on all the benchmark data known in the literature STRONGROUTER has performed either better than or comparable to the other routers.