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. Infea-sibility 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 itera-tions 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 in-tegrated with placers and are supposed to provide accurate congestion estimation for each iterative placement optimiza-tion, 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 per-turb global routing problem instances in controlled ways, and analyze the sensitivity of routing outcomes and met-rics. We observe scaling suboptimality and substantial noise in most of our experiments; this suggests a future need for new global router criteria and metrics. 1