EDGE: Efficient DAG-based Global Routing Engine
Jinwei Liu, Evangeline F. Y. Young
Abstract
Routing is one of the most time-consuming steps in the modern VLSI design flow. A well-designed global routing algorithm can effectively shrink the overall routing time and improve the quality of design after routing. Unlike many global routers that rely heavily on time-consuming path search algorithms like maze routing to resolve overflows, we propose to use directed acyclic graph (DAG) to explore the routing space more efficiently and create detours only when necessary. Experimental results on the ICCAD’19 benchmarks show that our algorithm improves the state-of-the-art quality of result by 1.4% and runs with a single thread faster than the fastest multi-threaded global router.
Topics & Concepts
Computer scienceStatic routingEqual-cost multi-path routingLink-state routing protocolPolicy-based routingMultipath routingDistributed computingRouting tableRouterDynamic Source RoutingComputer networkParallel computingVery-large-scale integrationEnhanced Interior Gateway Routing ProtocolRouting (electronic design automation)Routing protocolEmbedded systemVLSI and FPGA Design TechniquesVLSI and Analog Circuit TestingAdvancements in Photolithography Techniques