A NEW ALGORITHM FOR STANDARD CELL GLOBAL ROUTING

In this paper, we present a new algorithm for standard cell global routing. The algorithm considers all of the interconnection nets simultaneously; this produces superior results since information about all of the nets is available throughout the global routing process. We formulate the global routing problem as one of finding the optimal spanning forest on a graph that contains all of the interconnection information. The results of an important theorems allow us to prune many non-optimal connections before the global routing process begins. This approach successfully solves the net ordering and congestion prediction problems which other approaches suffer. The new algorithm was implemented as part of the DATools system at Xerox PARC. The benchmarks from the Physical Design Workshop are used as part of the comparison suite. The new algorithm achieves up to 11% area reduction compared to the previous global routing package used in the DATools system and obtains up to 17% reduction in the total channel density compared to the Timberwolf 4.2 package.