Efficient simulated evolution based rerouting and congestion-relaxed layer assignment on 3-D global routing

The increasing complexity of interconnection designs has enhanced the importance of research into global routing when seeking high-routability (low overflow) results or rapid search paths that report wire-length estimations to a placer. This work presents two routing techniques, namely adaptive pseu...

Full description

Saved in:
Bibliographic Details
Main Authors: Ke-Ren Dai, Wen-Hao Liu, Yih-Lang Li
Format: Conference Proceeding
Language:English
Subjects:
Computer science
Cost function
Delay
Electronic mail
Integrated circuit interconnections
Lagrangian functions
Minimization
Routing
Topology
Wire
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The increasing complexity of interconnection designs has enhanced the importance of research into global routing when seeking high-routability (low overflow) results or rapid search paths that report wire-length estimations to a placer. This work presents two routing techniques, namely adaptive pseudorandom net-ordering routing and evolution-based rip-up and reroute using a two-stage cost function in a high-performance congestion-driven 2-D global router. We also propose two efficient via-minimization methods, namely congestion relaxation by layer shifting and rip-up and re-assignment, for a dynamic programming-based layer assignment. Experimental results demonstrate that our router achieves performance similar to the first two winning routers in ISPD 2008 Routing Contest in terms of both routability and wire length at a 1.42X and 25.84X faster routing speed. Besides, our layer assignment yields 3.5% to 5.6% fewer vias, 2.2% to 3.3% shorter wirelength and 13% to 27% less runtime than COLA.
ISSN:2153-6961
2153-697X
DOI:10.1109/ASPDAC.2009.4796541