Sequential and parallel algorithms and data structures

✍ Scribed by Sanders P

• Publisher: Springer
• Year: 2019
• Tongue: English
• Leaves: 516
• Category: Library

✦ Table of Contents

Preface......Page 6
Contents......Page 9
1 Appetizer: Integer Arithmetic......Page 14
1.1 Addition......Page 15
1.1.1 Parallel Addition......Page 16
1.2 Multiplication: The School Method......Page 19
1.3 Result Checking......Page 23
1.4 A Recursive Version of the School Method......Page 24
1.5 Karatsuba Multiplication......Page 26
1.6 Parallel Multiplication......Page 28
1.7 Algorithm Engineering......Page 30
1.8 The Programs......Page 31
1.9 Proofs of Lemma 1.7 and Theorem 1.9......Page 34
1.11 Historical Notes and Further Findings......Page 36
2 Introduction......Page 38
2.1 Asymptotic Notation......Page 39
2.2 The Sequential Machine Model......Page 42
2.2.1 ExternalMemory......Page 44
2.3.1 Variables and Elementary Data Types......Page 45
2.3.2 Statements......Page 47
2.3.3 Procedures and Functions......Page 48
2.3.4 Object Orientation......Page 50
2.4.1 Shared-Memory Parallel Computing......Page 51
2.4.2 Distributed-Memory Parallel Computing......Page 54
2.4.3 ParallelMemory Hierarchies......Page 55
2.5.1 Single-ProgramMultiple-Data (SPMD)......Page 57
2.5.2 Explicitly Parallel Programs......Page 58
2.6.1 Assertions and Invariants......Page 59
2.6.2 Loop Invariants......Page 60
2.6.4 Certifying Algorithms......Page 61
2.7 An Example – Binary Search......Page 62
2.8 Basic Algorithm Analysis......Page 65
2.8.2 Recurrences......Page 66
2.9.1 Incrementing a Counter......Page 70
2.9.2 Left-to-RightMaxima......Page 71
2.9.3 Linear Search......Page 72
2.10 Parallel-Algorithm Analysis......Page 75
2.11 Randomized Algorithms......Page 76
2.11.1 The Formal Model......Page 78
2.11.2 An Advanced Example......Page 79
2.11.3 Las Vegas and Monte Carlo Algorithms......Page 80
2.12 Graphs......Page 81
2.12.2 Trees......Page 84
2.13 P and NP......Page 86
2.14 Implementation Notes......Page 90
2.14.1 C++......Page 91
2.15 Historical Notes and Further Findings......Page 92
3 Representing Sequences by Arrays and Linked Lists......Page 94
3.1 Processing Arrays in Parallel......Page 95
3.1.1 Reducing Latencies by Tiling......Page 97
3.2.1 Doubly Linked Lists......Page 99
3.2.3 Singly Linked Lists......Page 103
3.3 Processing Linked Lists in Parallel......Page 104
3.3.1 List Ranking by Doubling......Page 105
3.3.2 A Multilevel Algorithm for List Ranking......Page 0
3.3.3 Computing an Independent Set......Page 108
3.4.1 Amortized Analysis of Unbounded Arrays: The Global Argument......Page 110
3.4.2 Amortized Analysis of Unbounded Arrays: The Local Argument......Page 113
3.4.3 Amortized Analysis of Binary Counters......Page 114
3.5 Amortized Analysis......Page 115
3.5.1 The PotentialMethod for Amortized Analysis......Page 116
3.5.2 Universality of the PotentialMethod......Page 118
3.6 Stacks and Queues......Page 119
3.7 Parallel Queue-Like Data Structures......Page 122
3.7.2 Relaxed FIFO Queues and Bulk Operations......Page 123
3.7.4 The Epoch FIFO Queue......Page 125
3.8 Lists versus Arrays......Page 126
3.9.1 C++......Page 127
3.9.2 Java......Page 128
3.10 Historical Notes and Further Findings......Page 129
4 Hash Tables and Associative Arrays......Page 130
4.1 Hashing with Chaining......Page 133
4.2 Universal Hashing......Page 135
4.3 Hashing with Linear Probing......Page 141
4.4 Chaining versus Linear Probing......Page 143
4.5 Perfect Hashing......Page 144
4.6 Parallel Hashing......Page 147
4.6.1 Distributed-Memory Hashing......Page 148
4.6.2 Shared-Memory Hashing......Page 151
4.6.3 Implementation of Shared-Memory Hashing......Page 154
4.6.4 Experiments......Page 158
4.7 Implementation Notes......Page 160
4.7.1 C++......Page 161
4.8 Historical Notes and Further Findings......Page 162
5 Sorting and Selection......Page 165
5.1 Simple Sorters......Page 168
5.2 Simple, Fast, and Inefficient Parallel Sorting......Page 170
5.3 Mergesort – an O(n log n) Sorting Algorithm......Page 172
5.4 Parallel Mergesort......Page 174
5.5 A Lower Bound......Page 177
5.6 Quicksort......Page 180
5.6.1 Analysis......Page 181
5.6.2 Refinements......Page 182
5.7 Parallel Quicksort......Page 185
5.7.1 Distributed-Memory Quicksort......Page 186
5.7.2 In-Place Shared-Memory Quicksort......Page 189
5.8 Selection......Page 190
5.9 Parallel Selection......Page 192
5.9.1 Using Two Pivots......Page 193
5.10 Breaking the Lower Bound......Page 194
5.11 Parallel Bucket Sort and Radix Sort......Page 198
5.12 External Sorting......Page 199
5.12.1 Multiway Mergesort......Page 200
5.12.2 Sample Sort......Page 201
5.13 Parallel Sample Sort with Implementations......Page 203
5.13.1 Shared-Memory Sample Sort Implementation......Page 205
5.13.2 MPI Implementation......Page 210
5.14 Parallel Multiway Mergesort......Page 213
5.14.1 Distributed-Memory Multiway Mergesort......Page 216
5.15 Parallel Sorting with Logarithmic Latency......Page 217
5.16 Implementation Notes......Page 219
5.17 Historical Notes and Further Findings......Page 220
6 Priority Queues......Page 223
6.1 Binary Heaps......Page 225
6.2 Addressable Priority Queues......Page 230
6.2.1 Pairing Heaps......Page 232
6.2.2 Fibonacci Heaps......Page 233
6.3 External Memory......Page 236
6.4 Parallel Priority Queues......Page 238
6.4.1 Refinements......Page 240
6.5.2 Java......Page 241
6.6 Historical Notes and Further Findings......Page 242
7 Sorted Sequences......Page 244
7.1 Binary Search Trees......Page 246
7.2 (a,b)-Trees and Red–Black Trees......Page 249
7.3 More Operations......Page 256
7.3.1 Concatenation......Page 257
7.3.2 Splitting......Page 258
7.4 Amortized Analysis of Update Operations......Page 259
7.5.1 Parent Pointers......Page 261
7.5.2 Subtree Sizes......Page 262
7.6 Parallel Sorted Sequences......Page 263
7.7 Implementation Notes......Page 265
7.7.1 C++......Page 266
7.8 Historical Notes and Further Findings......Page 267
8 Graph Representation......Page 270
8.1 Unordered Edge Sequences......Page 271
8.3 Adjacency Lists – Dynamic Graphs......Page 272
8.4 The Adjacency Matrix Representation......Page 274
8.5 Implicit Representations......Page 275
8.6.2 Distributed Memory......Page 276
8.7.1 C++......Page 278
8.8 Historical Notes and Further Findings......Page 279
9 Graph Traversal......Page 281
9.1 Breadth-First Search......Page 282
9.2.1 Shared-Memory BFS......Page 284
9.2.2 Shared-Memory BFS Implementation......Page 286
9.2.3 Distributed-Memory BFS......Page 290
9.3 Depth-First Search......Page 292
9.3.1 DFS Numbering, Completion Times, and Topological Sorting......Page 294
9.3.2 Strongly Connected Components......Page 296
9.4 Parallel Traversal of DAGs......Page 304
9.4.1 Maximal Independent Sets......Page 306
9.4.2 Graph Coloring......Page 307
9.5.2 Java......Page 308
9.6 Historical Notes and Further Findings......Page 309
10 Shortest Paths......Page 310
10.1 From Basic Concepts to a Generic Algorithm......Page 311
10.2 Directed Acyclic Graphs......Page 315
10.3 Nonnegative Edge Costs (Dijkstra's Algorithm)......Page 316
10.4 Average-Case Analysis of Dijkstra's Algorithm......Page 320
10.5.2 Radix Heaps......Page 322
10.6 Arbitrary Edge Costs (Bellman–Ford Algorithm)......Page 327
10.7 All-Pairs Shortest Paths and Node Potentials......Page 329
10.8 Shortest-Path Queries......Page 331
10.8.1 Goal-Directed Search......Page 332
10.8.2 Hierarchy......Page 334
10.8.3 Transit Node Routing......Page 336
10.9 Parallel Shortest Paths......Page 337
10.10 Implementation Notes......Page 339
10.11 Historical Notes and Further Findings......Page 340
11 Minimum Spanning Trees......Page 342
11.1 Cut and Cycle Properties......Page 343
11.2 The Jarník–Prim Algorithm......Page 346
11.3 Kruskal's Algorithm......Page 347
11.4 The Union–Find Data Structure......Page 349
11.5 External Memory......Page 353
11.5.3 Sibeyn’s Algorithm......Page 354
11.6 Parallel Algorithms......Page 357
11.7.1 The Steiner Tree Problem......Page 360
11.7.2 Traveling Salesman Tours......Page 361
11.8 Implementation Notes......Page 362
11.9 Historical Notes and Further Findings......Page 363
12 Generic Approaches to Optimization......Page 365
12.1.1 Linear Programming......Page 367
12.1.2 Integer Linear Programming......Page 370
12.2 Greedy Algorithms – Never Look Back......Page 373
12.3 Dynamic Programming – Build It Piece by Piece......Page 376
12.4 Systematic Search – When in Doubt, Use Brute Force......Page 381
12.4.2 Parallel Systematic Search......Page 384
12.5.1 Hill Climbing......Page 387
12.5.2 Simulated Annealing – Learning from Nature......Page 390
12.5.2.1 Graph Coloring......Page 392
12.5.3 More on Local Search......Page 395
12.5.4 Parallel Local Search......Page 396
12.6 Evolutionary Algorithms......Page 397
12.7 Implementation Notes......Page 399
12.8 Historical Notes and Further Findings......Page 400
13 Collective Communication and Computation......Page 401
13.1.1 Binomial Trees......Page 404
13.1.2 Pipelining......Page 406
13.1.3 Building Binary Trees......Page 407
13.1.4 *Faster Broadcasting......Page 408
13.2 Reduction......Page 410
13.2.1 All-Reduce and Hypercubes......Page 411
13.3 Prefix Sums......Page 412
13.4.1 Locks......Page 414
13.4.3 Barrier Implementation......Page 416
13.5.1 (All)-Gather......Page 420
13.6 All-to-All Message Exchange......Page 421
13.6.1 Uniform All-to-All with Direct Data Delivery......Page 422
13.6.2 Hypercube All-to-All......Page 423
13.6.3 All-to-All with Nonuniform Message Sizes......Page 424
13.7 Asynchronous Collective Communication......Page 426
14 Load Balancing......Page 427
14.1.1 Independent Tasks......Page 428
14.1.2 A Toy Example – Computing the Mandelbrot Set......Page 429
14.2 Prefix Sums – Independent Tasks with Known Size......Page 430
14.3 The Master–Worker Scheme......Page 432
14.4 (Randomized) Static Load Balancing......Page 434
14.5 Work Stealing......Page 435
14.5.1 Tree-Shaped Computations......Page 436
14.5.2 The RandomizedWork-Stealing Algorithm......Page 437
14.5.3 Termination Detection......Page 439
14.5.4 Further Examples: BFS and Branch-and-Bound......Page 440
14.6 Handling Dependencies......Page 441
A.1 Mathematical Symbols......Page 443
A.2 Mathematical Concepts......Page 444
A.3 Basic Probability Theory......Page 446
A.4Useful Formulae......Page 451
A.4.1 Proofs......Page 452
B.1 Cores and Hardware Threads......Page 455
B.2 The Memory Hierarchy......Page 456
B.3 Cache Coherence Protocols......Page 457
B.6 Memory Management......Page 459
B.7 The Interconnection Network......Page 460
B.8 CPU Performance Analysis......Page 461
B.9 Compiler......Page 462
C.1 Hello World'' C++11 Program with Threads......Page 463<br> C.2 Locks......Page 464<br> C.4 Atomic Operations......Page 465<br> C.6 Memory Management......Page 466<br> C.7 Thread Scheduling......Page 467<br> D.1Hello World'' and What Is an MPI Program?......Page 469
D.2 Point-to-Point Communication......Page 471
D.3 Collective Communication......Page 472
E.1 BSD 3-Clause License......Page 473
References......Page 475
Index......Page 494