Stability and scalability in global routing

As the complexity of physical implementation continues to grow with technology scaling, routability has emerged as a major concern and implementation flow bottleneck. Infeasibility of routing forces a loop back to placement, netlist optimization, or even RTL design and floorplanning. Thus, to maintain convergence and a manageable number of iterations in the physical implementation flow, it is necessary to accurately predict design routability as quickly as possible. Routability estimation during placement typically exploits rough but fast global routers. Fast global routers are integrated with placers and are supposed to provide accurate congestion estimation for each iterative placement optimization, with short turn-around time. Such integrated global routers (as well as congestion estimators without global routers) should give (1) fast, and (2) stably accurate decisions as to whether a given placement is indeed routable. In this paper, we evaluate four academic global routers [14] [1] [9] [4] in terms of stability and scalability. We perturb global routing problem instances in controlled ways, and analyze the sensitivity of routing outcomes and metrics. We observe scaling suboptimality and substantial noise in most of our experiments; this suggests a future need for new global router criteria and metrics.