【！！】Routing Congestion in VLSI Circuits: Estimation and Optimization_2007

wodeccbp · 发表于 2009-7-10 22:15:34

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？注册

x

Routing Congestion in VLSI Circuits: Estimation and Optimization——2007

目录
Contents
Part I THE ORIGINS OF CONGESTION
1 AN INTRODUCTION TO ROUTING CONGESTION . . . . 3
1.1 The Nature of Congestion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Basic Routing Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.2 Routing Congestion Terminology . . . . . . . . . . . . . . . . . . . . 9
1.2 The Undesirability of Congestion . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.1 Impact on Circuit Performance . . . . . . . . . . . . . . . . . . . . . . 12
1.2.2 Impact on Design Convergence . . . . . . . . . . . . . . . . . . . . . . 14
1.2.3 Impact on Yield . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3 The Scaling of Congestion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.3.1 Effect of Design Complexity Scaling . . . . . . . . . . . . . . . . . 20
1.3.2 Effect of Process Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.4 The Estimation of Congestion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.5 The Optimization of Congestion . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.6 Final Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Part II THE ESTIMATION OF CONGESTION
2 PLACEMENT-LEVEL METRICS FOR ROUTING
CONGESTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.1 Fast Metrics For Routing Congestion . . . . . . . . . . . . . . . . . . . . . . 34
2.1.1 Total Wirelength . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.1.2 Pin Density . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.1.3 Perimeter Degree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.1.4 Application of Rent’s Rule to Congestion Metrics . . . . . . 38
2.2 Probabilistic Estimation Methods . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.2.1 Intra-bin Nets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.2.2 Flat Nets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
xii Contents
2.2.3 Single and Double Bend Routes for Inter-bin Nets . . . . . 45
2.2.4 Multibend Routes for Inter-bin Nets . . . . . . . . . . . . . . . . . 48
2.2.5 Routing Blockage Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.2.6 Complexity of Probabilistic Methods . . . . . . . . . . . . . . . . . 52
2.2.7 Approximations Inherent in Probabilistic Methods . . . . . 54
2.3 Estimation based on Fast Global Routing. . . . . . . . . . . . . . . . . . . 56
2.3.1 Search Space Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.3.2 Fast Search Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.4 Comparison of Fast Global Routing with Probabilistic Methods 63
2.5 Final Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3 SYNTHESIS-LEVEL METRICS FOR ROUTING
CONGESTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.2 Congestion Metrics for Technology Mapping . . . . . . . . . . . . . . . . 70
3.2.1 Total Netlength . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.2.2 Mutual Contraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.2.3 Predictive Congestion Maps . . . . . . . . . . . . . . . . . . . . . . . . 75
3.2.4 Constructive Congestion Maps . . . . . . . . . . . . . . . . . . . . . . 79
3.2.5 Comparison of Congestion Metrics for Technology
Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.3 Routing Congestion Metrics for Logic Synthesis . . . . . . . . . . . . . 83
3.3.1 Literal Count . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.3.2 Adhesion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.3.3 Fanout and Net Range . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.3.4 Neighborhood Population . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.3.5 Other Structural Metrics for Netlength Prediction . . . . . 89
3.3.6 Comparison of Congestion Metrics for Logic Synthesis . 91
3.4 Final Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
Part III THE OPTIMIZATION OF CONGESTION
4 CONGESTION OPTIMIZATION DURING
INTERCONNECT SYNTHESIS AND ROUTING . . . . . . . . 97
4.1 Congestion Management during Global Routing . . . . . . . . . . . . . 98
4.1.1 Sequential Global Routing . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.1.2 Rip-up and Reroute . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.1.3 Hierarchical and Multilevel Routing . . . . . . . . . . . . . . . . . 105
4.1.4 Multicommodity Flow based Routing . . . . . . . . . . . . . . . . 108
4.1.5 Routing using Simulated Annealing . . . . . . . . . . . . . . . . . . 110
4.1.6 Routing using Iterative Deletion . . . . . . . . . . . . . . . . . . . . . 111
4.2 Congestion Management during Detailed Routing . . . . . . . . . . . 112
Contents xiii
4.3 Congestion-aware Buffering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.3.1 Routability-aware Buffer Block Planning . . . . . . . . . . . . . 116
4.3.2 Holistic Buffered Tree Synthesis within a Physical
Layout Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
4.4 Congestion Implications of Power Grid Design . . . . . . . . . . . . . . 130
4.4.1 Integrated Power Network and Signal Shield Design . . . 130
4.4.2 Signal and Power Network Codesign . . . . . . . . . . . . . . . . . 132
4.5 Congestion-aware Interconnect Noise Management . . . . . . . . . . . 136
4.5.1 Congestion-aware Shield Synthesis for RLC Noise . . . . . 137
4.5.2 Integrated Congestion-aware Shielding and Buffering . . . 138
4.6 Final Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
5 CONGESTION OPTIMIZATION DURING PLACEMENT145
5.1 A Placement Primer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
5.1.1 Analytical Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
5.1.2 Top-down Partitioning-based Placement . . . . . . . . . . . . . . 150
5.1.3 Multilevel Placement Methods . . . . . . . . . . . . . . . . . . . . . . 151
5.1.4 Move-based Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
5.2 Congestion-aware Post-processing of Placement . . . . . . . . . . . . . 152
5.2.1 Find-and-fix Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
5.2.2 Congestion-aware Placement Refinement . . . . . . . . . . . . . 157
5.2.3 White Space Management Techniques . . . . . . . . . . . . . . . . 162
5.3 Interleaved Congestion Management and Placement. . . . . . . . . . 168
5.3.1 Interleaved Placement and Global Routing . . . . . . . . . . . 169
5.3.2 Interleaved Update of Control Parameters in
Congestion-aware Placement . . . . . . . . . . . . . . . . . . . . . . . . 174
5.4 Explicit Congestion Management within Placement . . . . . . . . . . 174
5.4.1 Cell Inflation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
5.4.2 White Space Management Techniques . . . . . . . . . . . . . . . . 180
5.4.3 Congestion-aware Objective Function or Concurrent
Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
5.5 Final Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
6 CONGESTION OPTIMIZATION DURING
TECHNOLOGY MAPPING AND LOGIC SYNTHESIS . . 189
6.1 Overview of Classical Technology Mapping . . . . . . . . . . . . . . . . . 190
6.1.1 Mapping for Area . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
6.1.2 Mapping for Delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
6.1.3 Tree and DAG Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
6.2 Congestion-aware Technology Mapping . . . . . . . . . . . . . . . . . . . . . 197
6.2.1 Technology Mapping using Netlength . . . . . . . . . . . . . . . . 199
6.2.2 Technology Mapping using Mutual Contraction . . . . . . . 203
6.2.3 Technology Mapping using Predictive Congestion Maps 205
xiv Contents
6.2.4 Technology Mapping using Constructive Congestion
Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
6.2.5 Comparison Of Congestion-aware Technology
Mapping Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
6.3 Overview of Classical Logic Synthesis . . . . . . . . . . . . . . . . . . . . . . 214
6.3.1 Technology Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . 215
6.3.2 Multilevel Logic Synthesis Operations . . . . . . . . . . . . . . . . 216
6.4 Congestion-aware Logic Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . 219
6.4.1 Technology Decomposition Targeting Netlength and
Mutual Contraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
6.4.2 Multilevel Synthesis Operations Targeting Congestion . . 221
6.4.3 Comparison of Congestion-aware Logic Synthesis
Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
6.5 Final Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
7 CONGESTION IMPLICATIONS OF HIGH LEVEL
DESIGN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
7.1 An Illustrative Example: Coarse-grained Parallelism . . . . . . . . . 231
7.2 Local Implementation Choices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
7.3 Final Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237

[ 本帖最后由 wodeccbp 于 2009-7-10 23:13 编辑 ]