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