Congestion is one of the main optimization objectives in global routing; however, the optimization performance is constrained because the cells are already fixed at this stage. Therefore, a designer can save substantial time and resources by detecting and reducing congested regions during the planning stages. An efficient yet accurate congestion estimation model is crucial to be included in the inner loop of floorplanning and placement design. In this dissertation, we mainly focus on routing congestion modeling and reduction during floorplanning and placement.

This volume provides a complete understanding of the fundamental causes of routing congestion in present-day and next-generation VLSI circuits, offers techniques for estimating and relieving congestion, and provides a critical analysis of the accuracy and effectiveness of these techniques. The book includes metrics and optimization techniques for routing congestion at various stages of the VLSI design flow. The subjects covered include an explanation of why the problem of congestion is important and how it will trend, plus definitions of metrics that are appropriate for measuring congestion, and descriptions of techniques for estimating and optimizing routing congestion issues in cell-/library-based VLSI circuits.

RETHINKING GLOBAL ROUTING FOR MODERN VLSI DESIGN: CONGESTION REDUCTION AND MULTI-OBJECTIVE OPTIMIZATION Hamid Shojaei Under the supervision of Professor Azadeh Davoodi At the University of Wisconsin-Madison The high volume and complexity of cells and interconnect structures are causing serious challenges to routability in modern VLSI design. Several new factors contribute to routing congestion including significantly-different wire size and spacing among the metal layers, sizes of inter-layer vias, various forms of routing blockages, local congestion due to pin density and wiring inside a global-cell, and virtual pins located at the higher metal layers. In addition, interconnects now play a significant role in impacting the performance metrics of a design including power, speed and area. Global routing, as the first stage in which the interconnects are planned, is now of significant importance in determining the performance metrics and the routability of the design. However, the standard model of global routing considers minimization of wirelength with a simplified model of routing resources which ignores these objectives and complicating factors. To address the above challenges, this dissertation has three contributions in rethinking global routing for modern VLSI design. First, we present a framework for congestion analysis for quick prediction of the locations of highly-utilized routing regions. The fast framework is suitable for integration in the design flow, for example as an integration within a routability-driven placement procedure. Second, we offer two contributions in order to estimate and manage the congestion caused by local nets which are ignored in a standard model of global routing. It allows optimizing congestion directly within global routing by treating global and detailed routing in a more holistic manner. In addition, many of the above-mentioned factors contributing to congestion are accounted for in our congestion analysis and optimization framework. Finally, we present a procedure for multi-objective global routing which is able to optimize multiple performance metrics beyond wirelength. The framework is a collaborative one which receives as input multiple global routing solutions created by single-objective procedures.

As fabrication technology keeps advancing, many deep submicron (DSM) effects have become increasingly evident and can no longer be ignored in Very Large Scale Integration(VLSI) design. In this dissertation, we study several deep submicron problems (eg. coupling capacitance, antenna effect and delay variation) and propose optimization techniques to mitigate these DSM effects in the place-and-route stage of VLSI physical design. The place-and-route stage of physical design can be further divided into several steps:(1) Placement, (2) Global routing, (3) Layer assignment, (4) Track assignment, and (5) Detailed routing. Among them, layer/track assignment assigns major trunks of wire segments to specific layers/tracks in order to guide the underlying detailed router. In this dissertation, we have proposed techniques to handle coupling capacitance at the layer/track assignment stage, antenna effect at the layer assignment, and delay variation at the ECO (Engineering Change Order) placement stage, respectively. More specifically, at layer assignment, we have proposed an improved probabilistic model to quickly estimate the amount of coupling capacitance for timing optimization. Antenna effects are also handled at layer assignment through a linear-time tree partitioning algorithm. At the track assignment stage, timing is further optimized using a graph based technique. In addition, we have proposed a novel gate splitting methodology to reduce delay variation in the ECO placement considering spatial correlations. Experimental results on benchmark circuits showed the effectiveness of our approaches.