Optimization Online


Global Routing in VLSI Design: Algorithms, Theory, and Computational Practice

Antoine Deza (deza***at***mcmaster.ca)
Chris Dickson (cdickson***at***bedlamgames.com)
Tamas Terlaky (terlaky***at***lehigh.edu)
Anthony Vannelli (vannelli***at***uoguelph.ca)
Hu Zhang (Hu.Zhang***at***rbccm.com)

Abstract: Global routing in VLSI (very large scale integration) design is one of the most challenging discrete optimization problems in computational theory and practice. In this paper, we present a polynomial time algorithm for the global routing problem based on integer programming formulation with a theoretical approximation bound. The algorithm ensures that all routing demands are satisfied concurrently, and the overall cost is approximately minimized. We provide both serial and parallel implementation as well as develop several heuristics used to improve the quality of the solution and reduce running time. We provide computational results on two sets of well-known benchmarks and show that, with a certain set of heuristics, our new algorithms perform extremely well compared with other integer-programming models.

Keywords: Global routing in VLSI design, Approximation algorithms, Integer programming model

Category 1: Applications -- Science and Engineering (VLSI layout )

Category 2: Integer Programming


Download: [PDF]

Entry Submitted: 12/14/2010
Entry Accepted: 12/14/2010
Entry Last Modified: 12/15/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society