SINGLE-LAYER GLOBAL ROUTING

We introduce the single-layer global routing problem (SLGRP), also cal led homotopic routing or rubber-band- equivalent routing, and propose a technique for solving it. Given a set of nets, the proposed techniqu e first determines the routing sequence based on the estimated congest ion, the bounding-box length and priority. Then, it finds a routing pa th, being a sequence of tiles, for each net (one net at a time), avoid ing ''congested'' areas. The overall goal of the algorithm is to maxim ize the number of routed nets. The proposed global router is the first true singlelayer global router ever reported in the literature. The s ize of tiles, omega x omega, is an input parameter in our algorithm. F or omega = 1, the proposed global router serves as an effective detail ed router. An optimal postprocessing algorithm, minimizing wire length and number of bends, under homotopic transformation, is presented. Th e technique has been implemented and tried out for randomly generated data. The algorithm is very efficient and produces good results.