Placement and routing of electronic modules

Cover......Page 1
Half Title......Page 2
Series Page......Page 4
Title Page......Page 8
Copyright Page......Page 9
Dedication......Page 10
Preface......Page 12
Table of Contents......Page 14
Contributors......Page 20
About the CALCE EPRC......Page 22
  1.1.1 Notation......Page 26
  1.1.2 Set definitions......Page 27
  1.1.3 Set algebra......Page 28
  1.2.1 Permutations......Page 31
  1.2.3 Rectilinear edges with a specific number of bends......Page 33
  1.2.4 The traveling salesman problem......Page 38
  1.2.5 The NP theory......Page 41
  1.3.1 Graphs......Page 44
  1.3.3 Line graphs......Page 47
  1.3.4 Paths, cycles and trees......Page 48
  1.3.5 The adjacency matrix......Page 51
 1.4 References......Page 52
 2.1 Tree Types......Page 54
  2.1.1 Routing length......Page 55
  2.1.3 Spanning trees......Page 56
  2.1.5 Source-sink trees......Page 59
  2.1.6 Row-based trees......Page 60
  2.1.7 Trees with special edges......Page 61
  2.2.1 Generating a minimum spanning tree......Page 63
  2.2.2 Generating a minimum chain tree......Page 69
 2.3 Minimum Steiner Tree Approximations......Page 73
  2.3.1 An approximation based on MRSTs for three nodes......Page 74
  2.3.2 Staircase layouts......Page 76
  2.3.3 Nodes lying on a rectangle perimeter......Page 79
 2.4 References......Page 82
Chapter 3: Signal Layer Estimation......Page 84
 3.1 Factors Affecting Layer Estimation......Page 86
  3.2.1 General estimation process......Page 88
  3.2.2 Equivalent integrated circuit count method......Page 89
  3.2.3 Comments on the density approach......Page 92
 3.3 Connectivity Approach......Page 93
  3.3.1 Permitted connectivity......Page 96
  3.3.2 Demanded connectivity......Page 100
  3.3.3 Generic model for layer estimation......Page 116
 3.4 References......Page 121
Chapter 4: Placement for Routability......Page 122
 4.1 Cost Functions......Page 123
  4.1.1 Routing length computations......Page 124
  4.1.2 Correction functions......Page 125
  4.1.3 Partitioning pertaining to placement objectives......Page 126
 4.2 Constructive Techniques......Page 128
  4.2.2 Cluster-development......Page 130
  4.2.3 Quadratic assignment......Page 131
 4.3 Iterative Techniques......Page 133
  4.3.1 Force-directed placement......Page 134
  4.3.2 Simulated annealing......Page 137
  4.3.3 Min-cut......Page 138
 4.4 Approximating Minimum Steiner Trees —......Page 141
  4.4.1 The iso-distance error graph......Page 142
  4.4.2 The connection errors......Page 145
  4.4.3 The error index......Page 147
  4.4.4 Characteristic IDEGs......Page 150
  4.4.5 Approximations with row-based trees......Page 152
  4.4.6 Testing and discussion......Page 155
 4.5 References......Page 159
Chapter 5: Placement for Reliability and Producibility......Page 164
 5.1 Placement for Temperature-Dependent Reliability......Page 165
  5.1.1 Convection-cooling placement......Page 166
  5.1.2 Conduction cooling placement......Page 170
  5.1.3 Placement on substrates......Page 178
 5.2 Placement for Fatigue-dependent Reliability......Page 179
  5.3.1 Deformation, stress and vibration......Page 184
  5.3.2 Modeling for automatic rearrangement......Page 186
  5.3.3 Placement algorithm......Page 190
 5.4 Placement for Producibility......Page 193
  5.5.2 Simulated annealing......Page 198
  5.5.3 Force-directed placement......Page 199
 5.6 References......Page 202
Chapter 6: Detailed Routing......Page 206
 6.1 Maze Searching......Page 208
  6.1.1 Lee\'s router......Page 209
  6.1.2 Modified Lee\'s routers......Page 210
  6.1.3 Minimum detour-length searching......Page 217
  6.2.1 Mikami-Tabuchi\'s router......Page 222
  6.2.2 Hightower\'s router......Page 224
  6.2.3 The line-expansion router......Page 225
  6.3.1 Rectangle expansion router......Page 227
  6.3.2 Ohtsuki\'s gridless router......Page 229
  6.3.3 Multilayer gridless router......Page 232
 6.4 Advanced Search Techniques......Page 234
  6.4.1 Maze searching in a costing workspace......Page 235
  6.4.2 The gridless minimum detour length router......Page 236
  6.4.3 Searching for paths with special requirements......Page 238
 6.5 References......Page 241
Chapter 7: Via Minimization......Page 246
 7.1 Introduction......Page 247
  7.2.1 The general 2-CVM problem......Page 248
  7.2.2 Restricted 2-CVM problem......Page 252
  7.2.3 The n-CVM problem......Page 258
  7.3.1 Basic definitions......Page 262
  7.3.2 The NP-completeness of the two-layer UVM problem......Page 263
  7.4.1 Crossing graph and via minimization algorithms......Page 270
  7.4.2 A 2-CVM algorithm for topological layouts......Page 276
 7.5 References......Page 282
Chapter 8: A Solution for Steiner\'s Problem......Page 286
 8.1 Basic Definitions......Page 287
 8.2 Properties of Steiner Points......Page 297
 8.3 Cliques......Page 302
 8.4 Exchangeable Edge-Sets and Trees......Page 310
 8.5 General Solution......Page 319
 8.6 Procedures......Page 321
 8.7 Example......Page 323
Appendix A: Symbols......Page 330
Appendix B: Acronyms......Page 334
Appendix C: Glossary......Page 336
Index......Page 346