Single-Layer Global Routing

Abstract

We introduce the single-layer global routing problem (SLGRP), also called homotopic routing or rubber-band-equivalent routing, and propose a technique for solving it. Given a set of nets, the proposed technique first determines the routing sequence based on the estimated congestion, the bounding-box length and priority. Then, it finds a routing path, being a sequence of tiles, for each net (one net at a time), avoiding “congested” areas. The overall goal of the algorithm is to maximize the number of routed nets. The proposed global router is the first true single-layer global router ever reported in the literature. The size of tiles, w × w, is an input parameter in our algorithm. For w = 1, the proposed global router serves as an effective detailed router. An optimal postprocessing algorithm, minimizing wire length and number of bends, under homotopic transformation, is presented. The technique has been implemented and tried out for randomly generated data. The algorithm is very efficient and produces good results. © 1994 IEEE