Shared-Memory Parallelism Can Be Simple, Fast, and Scalable

ACM Books......Page 4
Contents......Page 10
Preface......Page 14
Introduction......Page 18
Preliminaries and Notation......Page 40
Part I. PROGRAMMING TECHNIQUES FOR DETERMINISTIC PARALLELISM......Page 50
3. Internally Deterministic Parallelism: Techniques and Algorithms......Page 52
4. Deterministic Parallelism: Sequential Iterative Algorithms......Page 78
5. A Deterministic Phase-Concurrent Parallel Hash Table......Page 138
6. Priority Updates: A Contention-Reducing Primitive for Deterministic Programming......Page 168
Part II. LARGE-SCALE SHARED-MEMORY GRAPH ANALYTICS......Page 194
7. Ligra: A Lightweight Graph Processing Framework for Shared Memory......Page 196
8. Ligra+: Adding Compression to Ligra......Page 228
Part III. PARALLEL GRAPH ALGORITHMS......Page 248
9. Linear-Work Parallel Graph Connectivity......Page 250
10. Parallel and Cache-ObliviousTriangle Computations......Page 276
Part IV. PARALLEL STRING ALGORITHMS......Page 306
11. Parallel Cartesian Tree and Suffix Tree Construction......Page 308
12. Parallel Computation of Longest Common Prefixes......Page 332
13. Parallel Lempel-Ziv Factorization......Page 362
14. Parallel Wavelet Tree Construction......Page 374
15. Conclusion and Future Work......Page 390
References......Page 396
Index......Page 430
Author?s Biography......Page 444