By focusing on chip-wide slices of the global routing grid, making a few mild geometric assumptions about layer use, and suitably abstracting pin details, we derive an efficient integer linear programming formulation for track/layer assignment. The key technical insight is to model all constraints - both geometric and crosstalk - as cliques in an appropriate conflict graph; these cliques can be extracted quickly from the interval structure of wires in a slice. We develop a "strong" linear relaxation of this problem that almost always yields the integral optimum; this solution gives us directly the maximum number of wires that can be packed legally without crosstalk risk. Experiments on synthetic netlists that match statistics of wire layouts from industrial 0.25-μm designs demonstrate that we can pack 100-1000 wires optimally or, at worst, a very few overflows in seconds.
|Original language||English (US)|
|Number of pages||8|
|Journal||IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems|
|State||Published - May 2001|
ASJC Scopus subject areas
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering