TY - GEN
T1 - Efficient simulated evolution based rerouting and congestion-relaxed layer assignment on 3-D global routing
AU - Dai, Ke Ren
AU - Liu, Wen Hao
AU - Li, Yih-Lang
PY - 2009/4/20
Y1 - 2009/4/20
N2 - 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 wire-length and 13% to 27% less runtime than COLA.
AB - 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 wire-length and 13% to 27% less runtime than COLA.
UR - http://www.scopus.com/inward/record.url?scp=64549099361&partnerID=8YFLogxK
U2 - 10.1109/ASPDAC.2009.4796541
DO - 10.1109/ASPDAC.2009.4796541
M3 - Conference contribution
AN - SCOPUS:64549099361
SN - 9781424427482
T3 - Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC
SP - 570
EP - 575
BT - Proceedings of the ASP-DAC 2009
T2 - Asia and South Pacific Design Automation Conference 2009, ASP-DAC 2009
Y2 - 19 January 2009 through 22 January 2009
ER -