Vector Models for Data-Parallel Computing describes a model of parallelism that extends and formalizes the Data-Parallel model on which the Connection Machine and other supercomputers are based. It presents many algorithms based on the model, ranging from graph algorithms to numerical algorithms, and argues that data-parallel models are not only practical and can be applied to a surprisingly wide variety of problems, they are also well suited for very-high-level languages and lead to a concise and clear description of algorithms and their complexity. Many of the author's ideas have been incorporated into the instruction set and into algorithms currently running on the Connection Machine. The book includes the definition of a parallel vector machine; an extensive description of the uses of the scan (also called parallel-prefix) operations; the introduction of segmented vector operations; parallel data structures for trees, graphs, and grids; many parallel computational-geometry, graph, numerical and sorting algorithms; techniques for compiling nested parallelism; a compiler for Paralation Lisp; and details on the implementation of the scan operations. Guy E. Blelloch is an Assistant Professor of Computer Science and a Principal Investigator with the Super Compiler and Advanced Language project at Carnegie Mellon University. Contents: Introduction. Parallel Vector Models. The Scan Primitives. Computational-Geometry Algorithms. Graph Algorithms. Numerical Algorithms. Languages and Compilers. Correction-Oriented Languages. Flattening Nested Parallelism. A Compiler for Paralation Lisp. Paralation-Lisp Code. The Scan Vector Model. Data Structures. Implementing Parallel Vector Models. Implementing the Scan Operations. Conclusions. Glossary.
Author(s): Guy E. Blelloch
Series: Artificial Intelligence
Publisher: MIT
Year: 1990
Language: English
Pages: 268
Preface......Page 9
Acknowledgments......Page 11
1 Introduction......Page 13
1.1 Parallel Vector Models......Page 15
1.2 Vector Instructions......Page 17
1.3 Implementation......Page 21
1.4 Summary and Roadmap......Page 22
I Models......Page 27
2.1 The Vector Random Access Machine......Page 31
2.2 Comparison to P-RAM Models......Page 34
2.3 Comparison to Circuit and Network Models......Page 39
2.4 Comparison to Bit-Vector Models......Page 42
2.6.1 Serially Optimal Algorithms......Page 43
2.6.4 Do We Need the Scalar Memory?......Page 44
2.7 Conclusion......Page 45
3 The Scan Primitives......Page 47
3.1 Why Scan Primitives?......Page 49
3.2 Notation......Page 51
3.3 Example: Line-of-Sight......Page 52
3.4 Simple Operations......Page 54
3.4.1 Example: Split Radix Sort......Page 55
3.5 Segments and Segmented Scans......Page 57
3.5.1 Example: Quicksort......Page 58
3.5.2 Notes on Segments......Page 59
3.6 Allocating Elements......Page 60
3.6.1 Example: Line Drawing......Page 62
3.7 Long Vectors and Load Balancing......Page 63
3.7.1 Load Balancing......Page 65
3.7.2 Example: Halving Merge......Page 66
3.7.3 Notes on Simulating Long Vectors......Page 68
4.1 The Scan Vector Instruction Set......Page 71
4.1.2 Elementwise Instructions......Page 73
4.1.3 Permute Instructions......Page 74
4.1.5 Vector-Scalar Instructions......Page 75
4.2 Simple Operations......Page 76
4.3 Segments and Segmented Instructions......Page 79
4.4 Segmented Operations......Page 80
4.5.1 Merge Instruction......Page 82
4.5.2 Combine Instructions......Page 83
4.5.3 Multi-Extract Instruction......Page 84
4.5.4 Keyed-Scan Instructions......Page 85
II Algorithms......Page 87
5.1 Graphs......Page 91
5.1.1 Vector Graph Representations......Page 92
5.1.3 Distributing an Excess Across Edges......Page 95
5.2.1 Vector Tree Representation......Page 96
5.2.2 Leaffix and Rootfix Operations......Page 98
5.2.3 Tree Manipulations......Page 99
5.3 Multidimensional Arrays......Page 103
6 Computational-Geometry Algorithms......Page 105
6.1 Generalized Binary Search......Page 106
6.2 Building a k-DTree......Page 108
6.3 Closest Pair......Page 111
6.4 Quickhull......Page 113
6.5 √n Merge Hull......Page 115
6.6 Line of Sight......Page 117
7 Graph Algorithms......Page 121
7.1 Minimum Spanning Tree and Connectivity......Page 122
7.3 Maximal Independent Set and Biconnectivity......Page 126
8.1 Matrix-Vector Multiplication......Page 129
8.2 Linear-Systems Solver......Page 130
8.3 Simplex......Page 134
8.5 Sparse-Matrix Multiplication......Page 135
III Languages and Compilers......Page 139
9 Collection-Oriented Languages......Page 143
9.1 Collections......Page 144
9.2 Collection Operations......Page 147
9.3 Mapping Collections onto Vectors......Page 150
10 Flattening Nested Parallelism......Page 155
10.1 Nested Parallelism and Replicating......Page 156
10.2 The Replicating Theorem......Page 159
10.3 Access-Restricted Code......Page 161
10.4 Access-Fixed Replicating Theorem......Page 162
10.5 Indirect Addressing......Page 164
10.6.1 Branch-Packing......Page 166
10.6.2 Contained Programs......Page 169
10.6.3 Containment of Functions in Book......Page 172
10.6.4 Round-Robin Simulation......Page 173
11 A Compiler for Paralation Lisp......Page 175
11.1 Source Code: Paralation Lisp......Page 177
11.1.1 Data Structures......Page 178
11.1.2 Operators......Page 179
11.2 Target Code: Scan-Vector Lisp......Page 181
11.2.2 Operations......Page 182
11.3.1 Data Structures......Page 183
11.3.2 Operations......Page 187
IV Architecture......Page 197
12.1 Implementation on the Connection Machine......Page 201
12.1.1 The Vector Memory......Page 202
12.1.2 The Instructions......Page 204
12.1.3 Optimizations......Page 205
12.2 Simulating on P-RAM......Page 207
13.1 Unsigned +-Scan and Max-Scan......Page 209
13.1.1 Tree Scan......Page 210
13.1.2 Hardware Implementation of Tree Scan......Page 211
13.2 Directly Implementing Other Scans......Page 214
13.2.1 Backward and Segmented Scans......Page 215
13.3 Floating-Point +-Scan......Page 217
14 Conclusion......Page 221
14.1 Contributions......Page 222
14.2 Directions for Future Research......Page 223
14.3 Implementation Goals......Page 224
14.4 Development of Book Ideas......Page 225
A Glossary......Page 229
B Code......Page 235
B.1 Simple Operations......Page 236
B.2.1 Useful Utilities......Page 238
B.2.2 Segment Descriptor Translations......Page 239
B.2.3 Segmented Primitives......Page 240
B.3 Other Routines......Page 241
C.1 Utilities......Page 243
C.3 Quad-Tree......Page 245
C.4 Convex Hull: Quickhull......Page 246
C.5 Quicksort......Page 247
C.6 Entropy......Page 248
C.7 ID3: Quinlan’s Learning Algorithm......Page 249
Bibliography......Page 255
Index......Page 263
