Archer: A history-based global routing algorithm

Muhammet Mustafa Ozdal, Martin D. F. Wong

Research output: Contribution to journalJournal articlepeer-review

28 Citations (Scopus)

Abstract

Global routing is an important step in the physical design process. In this paper, we propose a new global routing algorithm Archer, which resolves some of the most common problems with the state-of-the-art global routers. It is known that concurrent global routing algorithms are typically too expensive to be applied on today's large designs, which may contain up to a million nets. On the other hand, iterative rip-up and reroute (RNR)-based algorithms are susceptible to getting stuck in local optimal solutions. In this paper, we propose an RNR-based global routing algorithm that guides the routing iterations out of local optima through effective usage of congestion histories. We also focus on the problem of how to enable a smooth tradeoff between seemingly conflicting objectives of overflow and wirelength minimization. Furthermore, we propose a Lagrangian relaxation-based bounded-length min-cost topology improvement algorithm that enables Steiner trees to change dynamically for the purpose of congestion optimization. Our experiments on public benchmarks show the effectiveness of Archer compared to other state-of-the-art global routers.

Original languageEnglish
Article number4802223
Pages (from-to)528-540
Number of pages13
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume28
Issue number4
Early online date16 Mar 2009
DOIs
Publication statusPublished - Apr 2009

Scopus Subject Areas

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

User-Defined Keywords

  • Congestion optimization
  • Global routing
  • Lagrangian relaxation
  • Steiner tree optimization

Fingerprint

Dive into the research topics of 'Archer: A history-based global routing algorithm'. Together they form a unique fingerprint.

Cite this