Completing high-quality global routes

Abstract

To ensure chip manufacturability, all routes must be completed without violations. Furthermore, the chip's power consumption and performance are determined by the length of its routed wires. Therefore, our work focuses on minimizing wirelength. Our key innovations include: (1) a novel branch-free representation (BFR) for routed nets, (2) a trigonometric penalty function (TPF), (3) dynamic adjustment of Lagrange multipliers (DALM), (4) cyclic net locking (CNL), and (5) aggressive lower-bound estimates (ALBE) for A*-search, resulting in faster routing. We complete all routable ISPD 2008 contest benchmarks and re-placed adaptec suite without violation and produce shorter routes.