Routing Congestion in VLSI Circuits: Estimation and Optimization »

With the dramatic increases in on-chip packing densities, routing congestion has become a major problem in chip design. The problem is especially acute as interconnects are also the performance bottleneck in integrated circuits. The solution lies in judicious resource management. This involves intelligent allocation of the available interconnect resources, up-front planning of the wire routes for even wire distributions, and transformations that make the physical synthesis flow congestion-aware.

Routing Congestion in VLSI Circuits: Estimation and Optimization provides the reader with a complete understanding of the root causes of routing congestion in present-day and future VLSI circuits, available techniques for estimating and optimizing this congestion, and a critical analysis of the accuracy and effectiveness of these techniques, so that the reader may prudently choose an approach that is appropriate to their design goals. The scope of the work includes metrics and optimization techniques for routing congestion at various stages of the VLSI design flow, including the architectural level, the logic synthesis/technology mapping level, the placement phase, and the routing step. A particular focus of this work is on the congestion issues that deal primarily with standard cell based design.

Routing Congestion in VLSI Circuits: Estimation and Optimization is a valuable reference for CAD developers and researchers, design methodology engineers, VLSI design and CAD students, and VLSI design engineers.

The Origins of Congestion
An Introduction to Routing Congestion     3
The Nature of Congestion     4
Basic Routing Model     4
Routing Congestion Terminology     9
The Undesirability of Congestion     12
Impact on Circuit Performance     12
Impact on Design Convergence     14
Impact on Yield     17
The Scaling of Congestion     20
Effect of Design Complexity Scaling     20
Effect of Process Scaling     22
The Estimation of Congestion     26
The Optimization of Congestion     27
Final Remarks     28
References     29
The Estimation of Congestion
Placement-Level Metrics for Routing Congestion     33
Fast Metrics For Routing Congestion     34
Total Wirelength     35
Pin Density     37
Perimeter Degree     38
Application of Rent's Rule to Congestion Metrics     38
Probabilistic Estimation Methods     41
Intra-bin Nets     43
Flat Nets     43
Single and Double Bend Routes for Inter-bin Nets     45
Multibend Routes for Inter-bin Nets     48
Routing Blockage Models     50
Complexity of Probabilistic Methods     52
Approximations Inherent in Probabilistic Methods     54
Estimation based on Fast Global Routing     56
Search Space Reduction     57
Fast Search Algorithms     58
Comparison of Fast Global Routing with Probabilistic Methods     63
Final Remarks     64
References     65
Synthesis-Level Metrics for Routing Congestion     67
Motivation     68
Congestion Metrics for Technology Mapping     70
Total Netlength     72
Mutual Contraction     73
Predictive Congestion Maps     75
Constructive Congestion Maps     79
Comparison of Congestion Metrics for Technology Mapping     81
Routing Congestion Metrics for Logic Synthesis     83
Literal Count     85
Adhesion     85
Fanout and Net Range     87
Neighborhood Population     88
Other Structural Metrics for Netlength Prediction     89
Comparison of Congestion Metrics for Logic Synthesis     91
Final Remarks     91
References     92
The Optimization of Congestion
Congestion Optimization During Interconnect Synthesis and Routing     97
Congestion Management during Global Routing     98
Sequential Global Routing     100
Rip-up and Reroute     101
Hierarchical and Multilevel Routing     105
Multicommodity Flow based Routing     108
Routing using Simulated Annealing     110
Routing using Iterative Deletion     111
Congestion Management during Detailed Routing     112
Congestion-aware Buffering     115
Routability-aware Buffer Block Planning     116
Holistic Buffered Tree Synthesis within a Physical Layout Environment     122
Congestion Implications of Power Grid Design     130
Integrated Power Network and Signal Shield Design     130
Signal and Power Network Codesign     132
Congestion-aware Interconnect Noise Management     136
Congestion-aware Shield Synthesis for RLC Noise     137
Integrated Congestion-aware Shielding and Buffering     138
Final Remarks     139
References     140
Congestion Optimization During Placement     145
A Placement Primer     147
Analytical Placement     148
Top-down Partitioning-based Placement      150
Multilevel Placement Methods     151
Move-based Methods     152
Congestion-aware Post-processing of Placement     152
Find-and-fix Techniques     153
Congestion-aware Placement Refinement     157
White Space Management Techniques     162
Interleaved Congestion Management and Placement     168
Interleaved Placement and Global Routing     169
Interleaved Update of Control Parameters in Congestion-aware Placement     174
Explicit Congestion Management within Placement     174
Cell Inflation     175
White Space Management Techniques     180
Congestion-aware Objective Function or Concurrent Constraints     182
Final Remarks     185
References     186
Congestion Optimization During Technology Mapping and Logic Synthesis     159
Overview of Classical Technology Mapping     190
Mapping for Area     191
Mapping for Delay     192
Tree and DAG Mapping     195
Congestion-aware Technology Mapping     197
Technology Mapping using Netlength     199
Technology Mapping using Mutual Contraction     203
Technology Mapping using Predictive Congestion Maps      205
Technology Mapping using Constructive Congestion Maps     208
Comparison Of Congestion-aware Technology Mapping Techniques     213
Overview of Classical Logic Synthesis     214
Technology Decomposition     215
Multilevel Logic Synthesis Operations     216
Congestion-aware Logic Synthesis     219
Technology Decomposition Targeting Netlength and Mutual Contraction     219
Multilevel Synthesis Operations Targeting Congestion     221
Comparison of Congestion-aware Logic Synthesis Techniques     225
Final Remarks     226
References     227
Congestion Implications of High Level Design     231
An Illustrative Example: Coarse-grained Parallelism     231
Local Implementation Choices     234
Final Remarks     235