This book is an introduction to the field of parallel algorithms and the underpinning techniques to realize the parallelization. The emphasis is on designing algorithms within the timeless and abstracted context of a high-level programming language. The focus of the presentation is on practical applications of the algorithm design using different models of parallel computation. Each model is illustrated by providing an adequate number of algorithms to solve some problems that quite often arise in many applications in science and engineering.
The book is largely self-contained, presuming no special knowledge of parallel computers or particular mathematics. In addition, the solutions to all exercises are included at the end of each chapter.
The book is intended as a text in the field of the design and analysis of parallel algorithms. It includes adequate material for a course in parallel algorithms at both undergraduate and graduate levels.
Readership: Advanced undergraduate and graduate students studying parallel algorithms.
Author(s): M.H. Alsuwaiyel
Series: Lecture Notes Series on Computing
Edition: 1
Publisher: World Scientific Publishing
Year: 2023
Language: English
Pages: 400
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
