Algorithms for VLSI Physical Design Automation: Algorithms for VLSI Physical Design Automation.part1.rar

Contents
Foreword xvii
Preface xix
Acknowledgements xxvii
1 VLSI Physical Design Automation 1
3
7
9
1.1
1.2
1.3
1.4
1.5
VLSI Design Cycle
New Trends in VLSI Design Cycle
Physical Design Cycle
New Trends in Physical Design Cycle
Design Styles
1.5.1
1.5.2
1.5.3
1.5.4
1.5.5
1.5.6
Full-Custom
Standard Cell
Gate Arrays
Field Programmable Gate Arrays
Sea of Gates
Comparison of Different Design Styles
1.6 System Packaging Styles
1.6.1 Die Packaging and Attachment Styles
1.6.1.1
1.6.1.2
Die Package Styles
Package and Die Attachment Styles
1.6.2
1.6.3
1.6.4
1.6.5
Printed Circuit Boards
Multichip Modules
Wafer Scale Integration
Comparison of Different Packaging Styles
1.7
1.8
1.9
Historical Perspectives
Existing Design Tools
Summary
13
15
17
18
20
22
25
25
26
26
26
27
27
29
31
31
32
33
35
39
40
43
43
45
2 Design and Fabrication of VLSI Devices
2.1
2.2
Fabrication Materials
Transistor Fundamentals
2.2.1
2.2.2
Basic Semiconductor Junction
TTL Transistors
viii Contents
2.2.3 MOS Transistors
2.3 Fabrication of VLSI Circuits
2.3.1
2.3.2
2.3.3
nMOS Fabrication Process
CMOS Fabrication Process
Details of Fabrication Processes
2.4
2.5
Design Rules
Layout of Basic Devices
2.5.1
2.5.2
2.5.3
Inverters
NAND and NOR Gates
Memory Cells
2.5.3.1
2.5.3.2
Static Random Access Memory (SRAM)
Dynamic Random Access Memory (DRAM)
2.6
2.7
Summary
Exercises
3 Fabrication Process and its Impact on Physical Design
3.1
3.2
Scaling Methods
Status of Fabrication Process
3.2.1 Comparison of Fabrication Processes
3.3 Issues related to the Fabrication Process
3.3.1
3.3.2
3.3.3
3.3.4
3.3.5
3.3.6
3.3.7
Parasitic Effects
Interconnect Delay
Noise and Crosstalk
Interconnect Size and Complexity
Other Issues in Interconnect
Power Dissipation
Yield and Fabrication Costs
3.4 Future of Fabrication Process
3.4.1
3.4.2
3.4.3
SIA Roadmap
Advances in Lithography
Innovations in Interconnect
3.4.3.1
3.4.3.2
3.4.3.3
3.4.3.4
More Layers of Metal
Local Interconnect
Copper Interconnect
Unlanded Vias
3.4.4
3.4.5
3.4.6
Innovations/Issues in Devices
Aggressive Projections for the Process
Other Process Innovations
3.4.6.1
3.4.6.2
Silicon On Insulator
Silicon Germaniun
3.5
3.6
3.7
3.8
Solutions for Interconnect Issues
Tools for Process Development
Summary
Exercises
46
48
51
53
53
58
62
62
64
66
67
69
71
71
75
76
77
77
79
79
80
81
82
82
82
83
85
85
86
87
87
87
87
88
88
89
90
90
90
91
93
94
94
Contents ix
4 Data Structures and Basic Algorithms 97
4.1
4.2
Basic Terminology 99
Complexity Issues and NP-hardness
4.2.1 Algorithms for NP-hard Problems
4.2.1.1
4.2.1.2
4.2.1.3
4.2.1.4
Exponential Algorithms
Special Case Algorithms
Approximation Algorithms
Heuristic Algorithms
4.3 Basic Algorithms
4.3.1 Graph Algorithms
4.3.1.1
4.3.1.2
4.3.1.3
4.3.1.4
4.3.1.5
4.3.1.6
Graph Search Algorithms
Spanning Tree Algorithms
Shortest Path Algorithms
Matching Algorithms
Min-Cut and Max-Cut Algorithms
Steiner Tree Algorithms
4.3.2 Computational Geometry Algorithms
4.3.2.1
4.3.2.2
Line Sweep Method
Extended Line Sweep Method
4.4 Basic Data Structures
4.4.1
4.4.2
4.4.3
4.4.4
4.4.5
4.4.6
4.4.7
4.4.8
Atomic Operations for Layout Editors
Linked List of Blocks
Bin-Based Method
Neighbor Pointers
Corner Stitching
Multi-layer Operations
Limitations of Existing Data Structures
Layout Specification Languages
4.5 Graph Algorithms for Physical design
4.5.1 Classes of Graphs in Physical Design
4.5.1.1
4.5.1.2
Graphs Related to a Set of Lines
Graphs Related to Set of Rectangles
4.5.2
4.5.3
4.5.4
Relationship Between Graph Classes
Graph Problems in Physical Design
Algorithms for Interval Graphs
4.5.4.1
4.5.4.2
Maximum Independent Set
Maximum Clique and Minimum Coloring
4.5.5 Algorithms for Permutation Graphs
4.5.5.1
4.5.5.2
Maximum Independent Set
Maximum -Independent Set
4.5.6 Algorithms for Circle Graphs
4.5.6.1
4.5.6.2
4.5.6.3
Maximum Independent Set
Maximum -Independent Set
Maximum Clique
4.6
4.7
Summary
Exercises
100
101
102
102
102
103
104
104
104
106
108
110
110
111
115
115
115
117
117
119
120
122
123
130
131
131
135
135
136
138
138
140
142
142
143
144
144
146
148
148
149
151
151
152
x Contents
5 Partitioning 157
5.1 Problem Formulation
5.1.1 Design Style Specific Partitioning Problems
5.2
5.3
Classification of Partitioning Algorithms
Group Migration Algorithms
5.3.1
5.3.2
Kernighan-Lin Algorithm
Extensions of Kernighan-Lin Algorithm
5.3.2.1
5.3.2.2
5.3.2.3
5.3.2.4
Fiduccia-Mattheyses Algorithm
Goldberg and Burstein Algorithm
Component Replication
Ratio Cut
5.4 Simulated Annealing and Evolution
5.4.1
5.4.2
Simulated Annealing
Simulated Evolution
5.5 Other Partitioning Algorithms
5.5.1 Metric Allocation Method
5.6
5.7
5.8
Performance Driven Partitioning
Summary
Exercises
163
166
168
169
170
171
173
174
174
176
177
177
179
183
183
185
187
187
6 Floorplanning and Pin Assignment 191
6.1 Floorplanning
6.1.1 Problem Formulation
6.1.1.1 Design Style Specific Floorplanning Problems
6.1.2
6.1.3
6.1.4
6.1.5
6.1.6
6.1.7
Classification of Floorplanning Algorithms
Constraint Based Floorplanning
Integer Programming Based Floorplanning
Rectangular Dualization
Hierarchical Tree Based Methods
Floorplanning Algorithms for Mixed Block and Cell Designs
6.1.8
6.1.9
6.1.10
6.1.11
Simulated Evolution Algorithms
Timing Driven Floorplanning
Theoretical advancements in Floorplanning
Recent Trends
6.2 Chip planning
6.2.1 Problem Formulation
6.3 Pin Assignment
6.3.1 Problem Formulation
6.3.1.1 Design Style Specific Pin Assignment Problems
6.3.2
6.3.3
6.3.4
Classification of Pin Assignment Algorithms
General Pin Assignment
Channel Pin Assignment
6.4
6.5
6.6
Integrated Approach
Summary
Exercises
193
193
194
194
196
198
200
201
203
203
204
205
206
207
207
207
208
208
209
210
211
214
217
217
Contents xi
7 Placement 219
7.1 Problem Formulation
7.1.1 Design Style Specific Placement Problems
7.2
7.3
Classification of Placement Algorithms
Simulation Based Placement Algorithms
7.3.1
7.3.2
7.3.3
7.3.4
Simulated Annealing
Simulated Evolution
Force Directed Placement
Sequence-Pair Technique
7.3.5 Comparison of Simulation Based Algorithms
7.4 Partitioning Based Placement Algorithms
7.4.1
7.4.2
Breuer’s Algorithm
Terminal Propagation Algorithm
7.5 Other Placement Algorithms
7.5.1
7.5.2
7.5.3
7.5.4
Cluster Growth
Quadratic Assignment
Resistive Network Optimization
Branch-and-Bound Technique
7.6
7.7
7.8
7.9
Performance Driven Placement
Recent Trends
Summary
Exercises
220
223
225
225
226
229
232
233
233
236
236
236
239
240
240
241
241
242
242
243
244
244
8 Global Routing 247
8.1 Problem Formulation
8.1.1 Design Style Specific Global Routing Problems
253
257
8.2 Classification of Global Routing
Algorithms
8.3 Maze Routing Algorithms
8.3.1
8.3.2
8.3.3
8.3.4
Lee’s Algorithm
Soukup’s Algorithm
Hadlock’s Algorithm
Comparison of Maze Routing Algorithms
8.4
8.5
8.6
Line-Probe Algorithms
Shortest Path Based Algorithms
Steiner Tree based Algorithms
8.6.1
8.6.2
8.6.3
8.6.4
Separability Based Algorithm
Non-Rectilinear Steiner Tree Based Algorithm
Steiner Min-Max Tree based Algorithm
Weighted Steiner Tree based Algorithm
8.7 Integer Programming Based Approach
8.7.1 Hierarchical Approach
8.8
8.9
8.10
Performance Driven Routing
Summary
Exercises
260
261
261
263
264
267
269
272
273
274
277
279
281
282
282
286
287
288
xii Contents
9 Detailed Routing
9.1 Problem Formulation
291
293
293
295
297
302
302
303
304
306
306
311
312
316
316
318
320
320
321
321
323
325
329
330
334
338
340
345
345
346
346
348
349
352
353
354
355
358
358
362
362
363
9.1.1
9.1.2
9.1.3
9.1.4
9.1.5
Routing Considerations
Routing Models
Channel Routing Problems
Switchbox Routing Problems
Design Style Specific Detailed Routing Problems
9.2
9.3
Classification of Routing Algorithms
Single-Layer Routing Algorithms
9.3.1 General River Routing Problem
9.3.1.1 General River Routing Algorithm
9.3.2 Single Row Routing Problem
9.3.2.1
9.3.2.2
9.3.2.3
9.3.2.4
Origin of Single Row Routing
A Graph Theoretic Approach
Algorithm for Street Congestion Minimization
Algorithm for Minimizing Doglegs
9.4 Two-Layer Channel Routing Algorithms
9.4.1
9.4.2
Classification of Two-Layer Algorithms
LEA based Algorithms
9.4.2.1
9.4.2.2
9.4.2.3
Basic Left-Edge Algorithm
Dogleg Router
Symbolic Channel Router: YACR2
9.4.3 Constraint Graph based Routing Algorithms
9.4.3.1
9.4.3.2
Net Merge Channel Router
Glitter: A Gridless Channel Router
9.4.4
9.4.5
9.4.6
Greedy Channel Router
Hierarchical Channel Router
Comparison of Two-Layer Channel Routers
9.5 Three-Layer Channel Routing Algorithms
9.5.1
9.5.2
9.5.3
9.5.4
Classification of Three-Layer Algorithms
Extended Net Merge Channel Router
HVH Routing from HV Solution
Hybrid HVH-VHV Router
9.6
9.7
Multi-Layer Channel Routing Algorithms
Switchbox Routing Algorithms
9.7.1
9.7.2
9.7.3
9.7.4
9.7.5
Classification of switchbox routing algorithms
Greedy Router
Rip-up and Re-route Based Router
Computational Geometry Based Router
Comparison of Switchbox Routers
9.8
9.9
Summary
Exercises
Contents xiii
10 Over-the-Cell Routing and Via Minimization 369
370
371
373
373
377
389
396
398
398
400
401
403
407
408
409
410
410
411
417
418
419
422
423
426
427
427
428
429
430
432
433
436
439
439
440
444
444
10.1 Over-the-cell Routing
10.1.1
10.1.2
Cell Models
Two-Layer Over-the-Cell Routers
10.1.2.1
10.1.2.2
10.1.2.3
Basic OTC Routing Algorithm
Planar Over-the-Cell Routing
Over-the-Cell Routing Using Vacant Terminals
10.1.3
10.1.4
10.1.5
Three-Layer Over-the-cell Routing
Multilayer OTC Routing
Performance Driven Over-the-cell Routing
10.2 Via Minimization
10.2.1 Constrained Via Minimization Problem
10.2.1.1 Graph Representation of Two-Layer CVM Problem
10.2.2 Unconstrained Via Minimization
10.2.2.1
10.2.2.2
10.2.2.3
Optimal Algorithm for Crossing-Channel TVM
Problem
Approximation Result for General k-TVM Problem
Routing Based on Topological Solution
10.3
10.4
Summary
Exercises
11 Clock and Power Routing
11.1 Clock Routing
11.1.1
11.1.2
Clocking Schemes
Design Considerations for the Clocking System
11.1.2.1 Delay Calculation for Clock Trees
11.1.3 Problem Formulation
11.1.3.1 Design Style Specific Problems
11.1.4 Clock Routing Algorithms
11.1.4.1
11.1.4.2
11.1.4.3
11.1.4.4
11.1.4.5
11.1.4.6
H-tree Based Algorithm
The MMM Algorithm
Geometric Matching based Algorithm
Weighted Center Algorithm
Exact Zero Skew Algorithm
DME Algorithm
11.1.5
11.1.6
Skew and Delay Reduction by Pin Assignment
Multiple Clock Routing
11.2
11.3
11.4
Power and Ground Routing
Summary
Exercises
xiv Contents
12 Compaction
12.1 Problem Formulation
449
450
450
451
452
453
454
460
463
463
463
464
464
467
468
470
473
473
473
474
474
475
476
476
479
480
485
485
489
490
492
493
494
496
497
501
502
505
507
510
512
512
513
514
12.1.1 Design Style Specific Compaction Problem
12.2
12.3
Classification of Compaction Algorithms
One-Dimensional Compaction
12.3.1 Constraint-Graph Based Compaction
12.3.1.1
12.3.1.2
12.3.1.3
12.3.1.4
Constraint Graph Generation
Critical Path Analysis
Wire Jogging
Wire Length Minimization
12.3.2 Virtual Grid Based Compaction
12.3.2.1
12.3.2.2
12.3.2.3
Basic Virtual Grid Algorithm
Split Grid Compaction
Most Recent Layer Algorithm
12.4
12.5
Compaction
Two-Dimensional Compaction
12.5.1 Simulated Annealing based Algorithm
12.6 Hierarchical Compaction
12.6.1 Constraint-Graph Based Hierarchical Compaction
12.7 Recent trends in compaction
12.7.1
12.7.2
Performance-driven compaction
Compaction techniques for yield enhancement
12.8
12.9
Summary
Exercises
13 Physical Design Automation of FPGAs
13.1
13.2
13.3
13.4
FPGA Technologies
Physical Design Cycle for FPGAs
Partitioning
Routing
13.4.1
13.4.2
Routing Algorithm for the Non-Segmented Model
Routing Algorithms for the Segmented Model
13.4.2.1
13.4.2.2
Basic Algorithm
Routing Algorithm for Staggered Model
13.5
13.6
Summary
Exercises
14 Physical Design Automation of MCMs
14.1
14.2
14.3
14.4
MCM Technologies
MCM Physical Design Cycle
Partitioning
Placement
14.4.1
14.4.2
Chip Array Based Approach
Full Custom Approach
14.5 Routing
14.5.1 Classification of MCM Routing Algorithms
Contents xv
14.5.2
14.5.3
Maze Routing 514
515
515
517
517
517
519
519
521
521
Multiple Stage Routing
14.5.3.1
14.5.3.2
14.5.3.3
Pin Redistribution Problem
Layer Assignment
Detailed Routing
14.5.4
14.5.5
14.5.6
Topological Routing
Integrated Pin Distribution and Routing
Routing in Programmable Multichip Modules
14.6
14.7
Summary
Exercises
Bibliography 525
Author Index 563
Subject Index 567

感谢楼主分享