Parallel Methods for VLSI Layout Design (Google eBook)

Front Cover
Greenwood Publishing Group, 1996 - Computers - 195 pages
1 Review
  

What people are saying - Write a review

We haven't found any reviews in the usual places.

Selected pages

Contents

Introduction
1
13 The Need for Speed
2
14 Towards Parallel Solutions
3
152 Physical Design
5
154 Subproblems in Physical Design
6
16 Organization of This Book
8
Complexity of Physical Design
12
21 Partition
13
822 Concurrent Placement on Array Processors
95
823 Placement on Adaptive Array
97
83 Parallel MinCut Placement
100
84 A DivideandConquer Approach
103
842 DAC algorithm on Orthogonal Array
104
843 DAC on Hypercube Architecture
106
85 rdimensional Placement Using Halls Algorithm
107
851 Implementation on Alliant
110

23 Placement
14
24 Routing
15
241 Lee Routing
16
243 Channel Routing
17
25 Summary
19
Parallel Processing
21
32 A Classification of Parallel Architectures
25
322 MIMD Computers
26
323 MISD Computers
28
324 Interconnection Networks
30
33 Supercomputers
33
34 Theoretical Models for Parallel Computation
34
342 Practical Utility of PRAM Algorithms
36
35 Summary
37
Parallel Processing and NPcompleteness
38
412 Symbolic Computing
39
42 PolynomialTime Solutions to Layout Problems
42
43 How Can Parallel Processing Help?
44
432 Superlinear Speedup
45
433 Searching a Larger Subspace of Solutions
47
44 Summary
58
Matching Algorithms to Architectures
59
51 GeneralPurpose and SpecialPurpose Machines
60
512 GeneralPurpose Parallel Computers
61
521 Treestructured Algorithms
62
522 Iterative Algorithms
63
523 Maze Algorithms
64
Matching Architectures to Algorithms
65
612 Network Optimization
66
613 Force Directed Placement
68
62 SIMD Systems
69
621 CAD Applications
70
64 Summary
71
Parallel Circuit Partition
72
72 Parallel KernighanLin on an EREW PRAM
74
722 Selecting Modules for Interchange
75
723 Updating the D Values
76
724 Executing Step P5 in Parallel
77
73 KernighanLin on an Orthogonal Array
78
733 Data Movement during EXCHANGE Operation
82
74 KernighanLin algorithm on the Alliant FX80
84
75 Parallel FiducciaMatheyses
85
76 Summary
88
Parallel Circuit Placement
90
81 A Taxonomy of Parallel Placement Systems
91
82 Parallel Iterative Improvement
92
821 Placement by Parallel Iterative Improvement
94
861 Parallelism in Simulated Annealing
111
862 Pipelined Execution of Simulated Annealing
112
87 Summary
113
Parallel Routing
115
91 Parallel Global Routing
116
912 Hierarchical Routing on an Orthogonal Array
118
913 Parallel CutandPaste Routing
119
914 Parallel Routing on Hypercube
124
915 LocusRoute
125
92 Parallel Channel Routing
126
922 Routing a Single Channel in Parallel
129
923 Channel Routing on a Hypercube
132
93 Lee Routing Engines
133
931 Parallel Lee Algorithm
134
932 Wave Front Machine
135
933 Alternate Hardware Solutions for Lee Routing
136
94 Summary
137
Perfect Graphs and Their Applications to Layout
138
1012 Permutation Graphs
139
102 Interval Graphs
140
1022 Interval Representation
141
1023 Serial Algorithm
142
1024 Parallel Algorithm
143
1025 A Coloring Algorithm
144
1026 Interval Graph Coloring on iPSC2
148
103 Coloring Permutation Graphs
151
1033 Algorithm for Coloring Permutation Graphs
152
1034 Maximum Independent Set
153
104 Summary
154
Further Research
155
1113 Abstract Parallel Algorithms
156
1114 Computing Platform
157
1116 Performance Evaluation
158
1121 Graph Theory
159
1122 Integer Linear Programming
160
1123 Artificial Intelligence
161
References
165
Notation
172
A13 BigTheta Notation
173
A21 NPcomplete Problems and Reduction
174
A3 Graph Theory
175
Parallel Computers Examples
177
B2 The Alliant FX80
179
B3 The Intel iPSC2
183
Author Index
187
Subject Index
190
Copyright

Common terms and phrases

Bibliographic information