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: Contribution to journalArticlepeer-review

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 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 languageEnglish (US)
Pages (from-to)672-679
Number of pages8
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume20
Issue number5
DOIs
StatePublished - May 2001

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

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