Title :
A new rip-up and reroute algorithm for very large scale gate arrays
Author :
Shirota, Hiroshi ; Shibatani, Satoshi ; Terai, Masayuki
Author_Institution :
Syst. LSI Lab., Mitsubishi Electr. Corp., Hyogo, Japan
Abstract :
A fast rip-up and reroute algorithm for large scale gate arrays is reported. The algorithm combines `global´ and `local´ rip-up and reroute processes to efficiently eliminate the unconnects introduced by an initial routing process. The global process reduces the local wire congestion by ripping up and rerouting global paths. The local process eliminates the unconnects, mainly caused by routing order dependency, by ripping up and rerouting local paths. The effectiveness of our method is demonstrated by our experimental results on industrial sea-of-gates (SOG) circuits and a well-known benchmark circuit
Keywords :
logic arrays; network routing; global process; local process; rip-up and reroute algorithm; sea-of-gates circuit; unconnects; very large scale gate array; wire congestion; Application specific integrated circuits; Circuit optimization; Laboratories; Large scale integration; Large-scale systems; Routing; Runtime; Wire; Wiring;
Conference_Titel :
Custom Integrated Circuits Conference, 1996., Proceedings of the IEEE 1996
Conference_Location :
San Diego, CA
Print_ISBN :
0-7803-3117-6
DOI :
10.1109/CICC.1996.510536
