Archer: A history-driven global routing algorithm

Muhammet Mustafa Ozdal, Martin D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

62 Citations (Scopus)


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 stateof-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 trade-off 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 show that Archer obtains congestion-free solutions for all circuits in the standard ISP.D98 benchmarks, which is the best result published so far. Furthermore, it produces better results than the best results reported in the ISPD-07 Global Routing Contest in terms of routability. Compared to FastRoute [18, 19], which is the stateof-the-art RNR-based global routing algorithm, Archer improves routability by 30%, and reduces the wirelengths by 32% on the average on. ISPD07 benchmarks.

Original languageEnglish
Title of host publicationProceedings of The 2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2007
Number of pages8
ISBN (Print)9781424413812
Publication statusPublished - 4 Nov 2007
Event2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2007 - DoubleTree Hotel, San Jose, United States
Duration: 4 Nov 20078 Nov 2007 (Conference proceedings)

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
ISSN (Print)1092-3152
ISSN (Electronic)1558-2434


Conference2007 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2007
Country/TerritoryUnited States
CitySan Jose
Internet address

Scopus Subject Areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design


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

Cite this