This paper presents an approach for the global routing and the placement problem in gate array chip design. The proposed global router gives a topological route for each signal net, based on the graph theory.
The global routing scheme consists of two phases, initial routing and rerouting. In the initial routing phase, all nets are routed by using a constructive method. The rerouting scheme removes the congestion under the initial weight map and then routes all nets again.
A 100% completion of several routing problems has been achieved using this scheme.
The global routing problem was implemented in FORTRAN on VAX-11/780 computer.