Wire packing: A strong formulation of crosstalk-aware chip-level track/layer assignment with an efficient integer programming solution

Rony Kay, Rob A. Rutenbar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 extremely efficient integer linear programming (ILP) formulation for track/layer assignment. They 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 pack 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 with at worst a very few overflows, in seconds.

Original languageEnglish (US)
Title of host publicationProceedings of the International Symposium on Physical Design
PublisherACM
Pages61-68
Number of pages8
StatePublished - 2000
Externally publishedYes
EventISPD-2000: International Symposium on Physical Design - San Diego, CA, USA
Duration: Apr 9 2000Apr 12 2000

Other

OtherISPD-2000: International Symposium on Physical Design
CitySan Diego, CA, USA
Period4/9/004/12/00

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint

Dive into the research topics of 'Wire packing: A strong formulation of crosstalk-aware chip-level track/layer assignment with an efficient integer programming solution'. Together they form a unique fingerprint.

Cite this