Preface |
|
xiii | |
|
|
1 | (102) |
|
|
3 | (34) |
|
|
4 | (6) |
|
|
4 | (3) |
|
|
7 | (1) |
|
|
8 | (2) |
|
Performance Evaluation of Pram Algorithms |
|
|
10 | (2) |
|
Cost, Work, Speedup, and Efficiency |
|
|
10 | (1) |
|
A Simple Simulation Result |
|
|
10 | (2) |
|
|
12 | (1) |
|
Comparison of Pram Models |
|
|
12 | (3) |
|
|
13 | (1) |
|
|
14 | (1) |
|
|
15 | (9) |
|
|
15 | (3) |
|
|
18 | (2) |
|
Complexity and Correctness |
|
|
20 | (4) |
|
Relevance of the Pram Model |
|
|
24 | (2) |
|
|
26 | (4) |
|
|
26 | (1) |
|
|
26 | (1) |
|
|
26 | (1) |
|
Looking for Roots in a Forest |
|
|
26 | (1) |
|
|
27 | (1) |
|
|
27 | (1) |
|
|
28 | (2) |
|
|
30 | (7) |
|
|
37 | (20) |
|
|
37 | (7) |
|
|
38 | (3) |
|
|
41 | (1) |
|
|
42 | (2) |
|
Sorting on a One-Dimensional Network |
|
|
44 | (5) |
|
Odd-Even Transposition Sort |
|
|
44 | (3) |
|
Odd-Even Sorting on a One-Dimensional Network |
|
|
47 | (2) |
|
|
49 | (3) |
|
|
49 | (1) |
|
|
49 | (1) |
|
Sorting on a Two-Dimensional Grid |
|
|
49 | (3) |
|
|
52 | (5) |
|
|
57 | (46) |
|
|
57 | (5) |
|
|
58 | (1) |
|
|
59 | (2) |
|
|
61 | (1) |
|
|
62 | (10) |
|
A Simple Performance Model |
|
|
63 | (1) |
|
Point-to-Point Communication Protoods |
|
|
63 | (3) |
|
|
66 | (6) |
|
Case Study: The Unidirectional Ring |
|
|
72 | (7) |
|
|
74 | (2) |
|
|
76 | (1) |
|
|
77 | (1) |
|
|
78 | (1) |
|
Case Study: The Hypercube |
|
|
79 | (8) |
|
|
79 | (1) |
|
Paths and Routing in a Hypercube |
|
|
80 | (2) |
|
Embedding Rings and Grids into Hypercubes |
|
|
82 | (1) |
|
Collective Communications in a Hypercube |
|
|
83 | (4) |
|
|
87 | (6) |
|
Distributed Hash Tables and Structured Overlay Networks |
|
|
88 | (2) |
|
|
90 | (1) |
|
Plaxton Routing Algorithm |
|
|
91 | (1) |
|
Multi-Casting in a Distributed Hash Table |
|
|
91 | (2) |
|
|
93 | (4) |
|
Torus, Hypercubes, and Binary Trees |
|
|
93 | (1) |
|
Torus, Hypercubes, and Binary Trees (again!) |
|
|
93 | (1) |
|
|
93 | (1) |
|
|
94 | (1) |
|
Dynamically Switched Networks |
|
|
94 | (1) |
|
|
95 | (1) |
|
|
96 | (1) |
|
|
97 | (6) |
|
|
103 | (104) |
|
Algorithms on a Ring of Processors |
|
|
105 | (42) |
|
Matrix-Vector Multiplication |
|
|
105 | (5) |
|
Matrix-Matrix Multiplication |
|
|
110 | (2) |
|
A First Look at Stencil Applications |
|
|
112 | (8) |
|
A Simple Sequential Stencil Algorithm |
|
|
112 | (1) |
|
Parallelizations of the Stencil Algorithm |
|
|
113 | (7) |
|
|
120 | (9) |
|
|
120 | (6) |
|
|
126 | (2) |
|
|
128 | (1) |
|
A Second Look at Stencil Applications |
|
|
129 | (6) |
|
Parallelization on a Unidirectional Ring |
|
|
130 | (5) |
|
Parallelization on a Bidirectional Ring |
|
|
135 | (1) |
|
Implementing Logical Topologies |
|
|
135 | (1) |
|
Distributed vs. Centralized Implementations |
|
|
136 | (2) |
|
Summary of Algorithmic Principles |
|
|
138 | (1) |
|
|
139 | (3) |
|
Solving a Triangular System |
|
|
139 | (1) |
|
|
139 | (1) |
|
|
140 | (1) |
|
MPI Matrix-Matrix Multiplication |
|
|
140 | (2) |
|
|
142 | (5) |
|
Algorithms on Grids of Processors |
|
|
147 | (28) |
|
Logical Two-Dimensional Grid Topologies |
|
|
147 | (2) |
|
Communication on a Grid of Processors |
|
|
149 | (1) |
|
Matrix Multiplication on a Grid of Processors |
|
|
150 | (17) |
|
The Outer-Product Algorithm |
|
|
151 | (3) |
|
|
154 | (2) |
|
Three Matrix Multiplication Algorithms |
|
|
156 | (5) |
|
Performance Analysis of the Three Algorithms |
|
|
161 | (6) |
|
Two-Dimensional Block Cyclic Data Distribution |
|
|
167 | (2) |
|
|
169 | (2) |
|
|
169 | (1) |
|
|
169 | (1) |
|
|
169 | (1) |
|
Outer-Product Algorithm in MPI |
|
|
169 | (2) |
|
|
171 | (4) |
|
Load Balancing on Heterogenous Platforms |
|
|
175 | (32) |
|
Load Balancing for One-Dimensional Data Distributions |
|
|
176 | (10) |
|
Basic Static Task Allocation Algorithm |
|
|
177 | (2) |
|
|
179 | (2) |
|
Application to a Stencil Application |
|
|
181 | (3) |
|
Application to the LU Factorization |
|
|
184 | (2) |
|
Load Balancing for Two-Dimensional Data Distributions |
|
|
186 | (4) |
|
Matrix Multiplication on a Heterogeneous Grid |
|
|
186 | (3) |
|
On the Hardness of the Two-Dimensional Data Partioning Problem |
|
|
189 | (1) |
|
Free Two-Dimensional Partitioning on a Heterogeneous Grid |
|
|
190 | (11) |
|
|
190 | (4) |
|
|
194 | (7) |
|
|
201 | (2) |
|
Matrix Product on a Heterogenous Ring |
|
|
201 | (1) |
|
LU Factorization on a Heterogeneous Grid |
|
|
201 | (1) |
|
Stencil Application on a Heterogeneous Ring |
|
|
202 | (1) |
|
|
203 | (4) |
|
|
207 | (116) |
|
|
209 | (46) |
|
|
209 | (3) |
|
Where Do Task Graphs Come From? |
|
|
209 | (2) |
|
|
211 | (1) |
|
|
212 | (4) |
|
|
216 | (2) |
|
|
218 | (13) |
|
|
218 | (2) |
|
List Scheduling Heuristics |
|
|
220 | (3) |
|
Implementing a List Schedule |
|
|
223 | (2) |
|
|
225 | (1) |
|
Scheduling Independent Tasks |
|
|
226 | (5) |
|
Taking Communication Costs into Account |
|
|
231 | (1) |
|
Pb(∞) with Communications |
|
|
232 | (8) |
|
|
234 | (2) |
|
A Guaranteed Heuristic for Pb(∞) |
|
|
236 | (4) |
|
List Heuristics for Pb(p) with Communications |
|
|
240 | (4) |
|
|
240 | (1) |
|
|
241 | (1) |
|
|
242 | (2) |
|
Extension to Heterogeneous Platforms |
|
|
244 | (3) |
|
|
247 | (4) |
|
|
247 | (1) |
|
List Scheduling Anomalies |
|
|
248 | (1) |
|
Scheduling a FORK Graph with Communications |
|
|
248 | (1) |
|
|
249 | (2) |
|
|
251 | (4) |
|
|
255 | (68) |
|
Divisible Load Scheduling |
|
|
256 | (15) |
|
|
256 | (1) |
|
|
257 | (4) |
|
|
261 | (3) |
|
Extension to Star Networks |
|
|
264 | (5) |
|
|
269 | (2) |
|
|
271 | (11) |
|
|
271 | (1) |
|
|
272 | (2) |
|
|
274 | (4) |
|
|
278 | (1) |
|
|
279 | (2) |
|
|
281 | (1) |
|
|
282 | (14) |
|
|
283 | (12) |
|
|
295 | (1) |
|
Response Time Minimization |
|
|
295 | (1) |
|
Hyperplane Scheduling (or Scheduling at Compile-Time) |
|
|
296 | (11) |
|
|
296 | (5) |
|
Lamport's Hyperplane Method |
|
|
301 | (6) |
|
|
307 | (5) |
|
Divisible Load Scheduling on Heterogeneous Trees |
|
|
307 | (1) |
|
Steady-State Scheduling of Multiple Applications |
|
|
308 | (1) |
|
|
309 | (1) |
|
Response Time of One-to-One Mappings |
|
|
309 | (1) |
|
Dependence Analysis and Scheduling Vectors |
|
|
310 | (1) |
|
|
310 | (2) |
|
|
312 | (11) |
Bibliography |
|
323 | (10) |
Index |
|
333 | |