A NEW RIP-UP AND REROUTE ALGORITHM FOR VERY LARGE-SCALE GATE ARRAYS

A fast rip-up and reroute algorithm for very large scale gate arrays i s proposed. The automatic routing program for gate arrays usually cons ists of an initial routing process and rip-up and rerouting process. T he rip-up and rerouting process eliminates the unconnects introduced b y the initial routing process. There are two main reasons for leaving some unconnects: routing order dependency and local wire congestion. T he existing rip-up and reroute algorithms can efficiently resolve unco nnects caused by the routing order dependency. However, they cannot do unconnects caused by the local wire congestion. On the other hand, th e proposed algorithm combines a 'global' and 'local' rip-up and rerout e process and efficiently resolve unconnects caused by both of them. T he 'global' process reduces the local wire congestion by ripping up an d rerouting global paths. The 'local' process eliminates the unconnect s, mainly caused by routing order dependency, by ripping up and rerout ing local paths. The effectiveness of our method is demonstrated by ou r experimental results on industrial sea-of-gates (SOG) circuits and a well-known benchmark circuit.