High-performance Global Routing for Trillion-gate Systems-on-Chips

Due to aggressive transistor scaling, modern-day CMOS circuits have continually increased in both complexity and productivity. Modern semiconductor designs have narrower and more resistive wires, thereby shifting the performance bottleneck to interconnect delay. These trends considerably impact timing closure and call for improvements in high-performance physical design tools to keep pace with the current state of IC innovation. At the heart of physical design lie the placement and routing steps, where, after logic synthesis, all the design's gate-level components are assigned specific locations on the chip layout, and relevant components are connected by metallic wires. These two steps are critical, as they have a direct impact on the design's final performance. Despite impressive improvements within the past decade, further progress is possible, both in terms of solution quality and runtime. As leading-edge designs may incorporate tens of millions of gates, algorithm and software scalability are crucial to achieving reasonable turnaround time. Moreover, with decreasing device sizes, optimizing traditional objectives is no longer sufficient.

Our research focuses on (i) expanding the capabilities of standalone global routing,
(ii) extending global routing for use in different design applications, and (iii) integrating routing within broader physical design optimizations and flows, e.g., congestion-driven global and detailed placement. Our first global router relies on integer-linear programming (ILP), and can solve fairly large problem instances to optimality. Our second iterative global router relies on Lagrangian relaxation, where we relax the routing violation constraint to allowing routing overflow at a penalty. In both approaches, our desire is to give the router the maximum degree of freedom within a specified context. Empirically, both routers produce competitive results within a reasonable amount of runtime. To improve routability, we explore the incorporation of global routing into global placement, where the router produces a congestion map of the layout, and feeds this information to the placer. In turn, the emphasis on runtime is heightened, as the router will be invoked multiple times. Empirically, our placement-and-route framework significantly improves the final solution's routability than performing the steps sequentially. To further enhance routability-driven placement, we (i) generate fast and accurate congestion maps without incurring the high cost of runtime, and (ii) leverage several techniques to relieve netlist- and region-centric congestion. To broaden the scope of routing, we integrate a global router in a chip-design flow that addresses the buffer explosion problem.