Parallel Algorithms

✍ Scribed by M. H. Alsuwaiyel

• Publisher: World Scientific Publishing
• Year: 2022
• Tongue: English
• Leaves: 400
• Series: Lecture Notes Series on Computing, Volume 16
• Category: Library

✦ Table of Contents

Contents
Preface
About the Author
1. Introduction
1.1 Classifications of Parallel Architectures
1.2 Shared-Memory Computers
1.3 Interconnection-Network Computers
1.4 Two Simple Examples
2. Shared-memory Computers (PRAM)
2.1 Introduction
2.2 The Balanced Tree Method
2.3 Brent Theorem
2.4 Sorting in Θ(1) Time on the CRCW PRAM Model
2.4.1 Implementation on the CREW PRAM model
2.4.2 Implementation on the EREW PRAM model
2.5 Parallel Prefix
2.5.1 Array packing
2.5.2 Parallel quicksort
2.6 Parallel Search
2.7 Pointer Jumping
2.8 Euler Tour
2.8.1 Directing a tree
2.8.2 Computing vertex levels in a tree
2.9 Merging by Ranking
2.9.1 Computing ranks
2.9.2 Merging
2.9.3 Parallel bottom-up merge sorting
2.10 The Zero-one Principle
2.11 Odd–Even Merging
2.12 Bitonic Merging and Sorting
2.12.1 Bitonic sorting
2.13 Pipelined Mergesort
2.13.1 The algorithm
2.13.2 Computing and maintaining ranks
2.13.3 Analysis of the algorithm
2.14 Selection
2.15 Multiselection
2.16 Matrix Multiplication
2.17 Transitive Closure
2.18 Shortest Paths
2.19 Minimum Spanning Trees
2.20 Computing the Convex Hull of a Set of Points
2.21 Bibliographic Notes
2.22 Exercises
2.23 Solutions
3. The Hypercube
3.1 Introduction
3.2 The Butterfly
3.3 Embeddings of the Hypercube
3.3.1 Gray codes
3.3.2 Embedding of a linear array into the hypercube
3.3.3 Embedding of a mesh into the hypercube
3.3.4 Embedding of a binary tree into the hypercube
3.4 Broadcasting in the Hypercube
3.5 Semigroup Operations
3.6 Permutation Routing on the Hypercube
3.6.1 The greedy algorithm
3.6.2 The randomized algorithm
3.7 Permutation Routing on the Butterfly
3.8 Computing Parallel Prefix on the Hypercube
3.9 Hyperquicksort
3.10 Sample Sort
3.11 Selection on the Hypercube
3.12 Multiselection on the Hypercube
3.13 Load Balancing on the Hypercube
3.14 Computing Parallel Prefix on the Butterfly
3.15 Odd–Even Merging and Sorting on the Butterfly
3.16 Matrix Multiplication on the Hypercube
3.17 Bibliographic Notes
3.18 Exercises
3.19 Solutions
4. The Linear Array and the Mesh
4.1 Introduction
4.2 Embedding between a Mesh and a Linear Array
4.3 Broadcasting in the Linear Array and the Mesh
4.4 Computing Parallel Prefix on the Mesh
4.5 Odd–Even Transposition Sort
4.6 Shearsort
4.7 A Simple Θ(√n) Time Algorithm for Sorting on the Mesh
4.8 Odd–Even Merging and Sorting on the Mesh
4.9 Routing on the Linear Array and the Mesh
4.9.1 Routing in the linear array
4.9.2 Deterministic routing in the mesh
4.9.3 Randomized routing on the mesh
4.10 Matrix Multiplication on the Mesh
4.10.1 The first algorithm
4.10.2 The second algorithm
4.11 Computing the Transitive Closure on the Mesh
4.12 Connected Components
4.13 Shortest Paths
4.14 Computing the Convex Hull of a Set of Points on the Mesh
4.14.1 The first algorithm
4.14.2 The second algorithm
4.15 Labeling Connected Components
4.15.1 The propagation algorithm
4.15.2 The recursive algorithm
4.16 Columnsort
4.17 3-dimensional Mesh
4.17.1 Sorting on 3-dimensional meshes
4.18 Bibliographic Notes
4.19 Exercises
4.20 Solutions
5. Fast Fourier Transform
5.1 Introduction
5.2 Implementation on the Butterfly
5.3 Iterative FFT on the Butterfly
5.4 The Inverse Fourier Transform
5.5 Product of Polynomials
5.6 Computing the Convolution of Two Vectors
5.7 The Product of a Toeplitz Matrix and a Vectors
5.8 Using Modular Arithmetic
5.9 Bibliographic Notes
5.10 Exercises
5.11 Solutions
6. Tree-based Networks
6.1 The Tree Network
6.1.1 Semigroup operations
6.1.2 Sorting by minimum extraction
6.1.3 Sorting by partitioning
6.1.4 Selection
6.1.5 The one-dimensional pyramid
6.2 The Pyramid
6.2.1 Computing parallel prefix on the pyramid
6.3 Mesh of Trees
6.3.1 Sorting on the mesh of trees
6.3.2 Routing in the mesh of trees
6.4 Computing Parallel Prefix on the Mesh of Trees
6.5 Comparison Between the Mesh of Trees and the Pyramid
6.6 Bibliographic Notes
6.7 Exercises
6.8 Solutions
7. The Star Network
7.1 Introduction
7.2 Ranking of the Processors
7.3 Routing between Substars
7.4 Computing Parallel Prefix on the Star
7.5 Computing the Maximum
7.6 Neighborhood Broadcasting and Recursive Doubling
7.7 Broadcasting in the Star
7.8 The Arrangement Graph
7.9 The (d, k)-Star Graph
7.10 Sorting in the Sd,k Star
7.11 Bibliographic Notes
7.12 Exercises
7.13 Solutions
8. Optical Transpose Interconnection System (OTIS)
8.1 Introduction
8.2 The OTIS-Mesh
8.2.1 Data movements in the OTIS-Mesh
8.2.2 Broadcasting in the OTIS-Mesh
8.2.3 Semigroup operations on the OTIS-Mesh
8.2.4 Parallel prefix in OTIS-Mesh
8.2.5 Shift operations on the OTIS-Mesh
8.2.6 Permutation routing in OTIS-Mesh
8.2.6.1 Deterministic routing in the OTIS-Mesh
8.2.6.2 Randomized routing in the OTIS-Mesh
8.2.7 Sorting on OTIS-Mesh
8.3 The OTIS-Hypercube
8.3.1 Simulation of an n2-processor hypercube
8.3.2 Broadcasting in the OTIS-Hypercube
8.3.3 Semigroup operations on the OTIS-Hypercube
8.3.4 Sorting and routing in the OTIS-Hypercube
8.4 Other OTIS Networks
8.4.1 The OTIS-Star
8.4.2 The OTIS-MOT
8.5 Bibliographic Notes
8.6 Exercises
8.7 Solutions
9. Systolic Computation
9.1 Introduction
9.2 Matrix-vector Multiplication
9.3 Computing the Convolution of Two Sequences
9.3.1 Semisystolic solution
9.3.2 Pure systolic solution
9.4 A Zero-time VLSI Sorter
9.5 An On-chip Bubble Sorter
9.6 Bibliographic Notes
9.7 Exercises
9.8 Solutions
Appendix A Mathematical Preliminaries
A.1 Asymptotic Notations
A.1.1 The O-notation
A.1.2 The Ω-notation
A.1.3 The Θ-notation
A.1.4 The o-notation
A.2 Divide-and-conquer Recurrences
A.3 Summations
A.4 Probability
A.4.1 Random variables and expectation
A.4.2 Bernoulli distribution
A.4.3 Binomial distribution
A.4.4 Chernoff bounds
A.4.4.1 Lower tail
A.4.4.2 Upper tail
Bibliography
Index