Muutke küpsiste eelistusi

Parallel Algorithms [Kõva köide]

(King Fahd Univ Of Petroleum & Minerals (Kfupm), Saudi Arabia)
  • Formaat: Hardback, 400 pages
  • Sari: Lecture Notes Series on Computing 16
  • Ilmumisaeg: 22-Jun-2022
  • Kirjastus: World Scientific Publishing Co Pte Ltd
  • ISBN-10: 9811252971
  • ISBN-13: 9789811252976
Teised raamatud teemal:
Parallel AlgorithmsSuurem pilt
  • Formaat: Hardback, 400 pages
  • Sari: Lecture Notes Series on Computing 16
  • Ilmumisaeg: 22-Jun-2022
  • Kirjastus: World Scientific Publishing Co Pte Ltd
  • ISBN-10: 9811252971
  • ISBN-13: 9789811252976
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9789811252976.html
Märksõnad:
"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. Thefocus 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"--

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.

Preface vii
About the Author ix
1 Introduction
1(6)
1.1 Classifications of Parallel Architectures
1(1)
1.2 Shared-Memory Computers
2(1)
1.3 Interconnection-Network Computers
3(2)
1.4 Two Simple Examples
5(2)
2 Shared-memory Computers (PRAM)
7(88)
2.1 Introduction
7(1)
2.2 The Balanced Tree Method
8(2)
2.3 Brent Theorem
10(1)
2.4 Sorting in 9(1) Time on the CRCW PRAM Model
11(3)
2.4.1 Implementation on the CREW PRAM model
12(1)
2.4.2 Implementation on the EREW PRAM model
13(1)
2.5 Parallel Prefix
14(4)
2.5.1 Array packing
16(2)
2.5.2 Parallel quicksort
18(1)
2.6 Parallel Search
18(3)
2.7 Pointer Jumping
21(1)
2.8 Euler Tour
22(5)
2.8.1 Directing a tree
25(1)
2.8.2 Computing vertex levels in a tree
26(1)
2.9 Merging by Ranking
27(5)
2.9.1 Computing ranks
27(3)
2.9.2 Merging
30(1)
2.9.3 Parallel bottom-up merge sorting
31(1)
2.10 The Zero-one Principle
32(1)
2.11 Odd-Even Merging
33(2)
2.12 Bitonic Merging and Sorting
35(8)
2.12.1 Bitonic sorting
40(3)
2.13 Pipelined Mergesort
43(7)
2.13.1 The algorithm
44(2)
2.13.2 Computing and maintaining ranks
46(3)
2.13.3 Analysis of the algorithm
49(1)
2.14 Selection
50(2)
2.15 Multiselection
52(4)
2.16 Matrix Multiplication
56(2)
2.17 Transitive Closure
58(1)
2.18 Shortest Paths
58(1)
2.19 Minimum Spanning Trees
59(4)
2.20 Computing the Convex Hull of a Set of Points
63(5)
2.21 Bibliographic Notes
68(1)
2.22 Exercises
69(8)
2.23 Solutions
77(18)
3 The Hypercube
95(64)
3.1 Introduction
95(1)
3.2 The Butterfly
96(3)
3.3 Embeddings of the Hypercube
99(5)
3.3.1 Gray codes
100(1)
3.3.2 Embedding of a linear array into the hypercube
101(1)
3.3.3 Embedding of a mesh into the hypercube
102(1)
3.3.4 Embedding of a binary tree into the hypercube
103(1)
3.4 Broadcasting in the Hypercube
104(1)
3.5 Semigroup Operations
105(1)
3.6 Permutation Routing on the Hypercube
105(5)
3.6.1 The greedy algorithm
106(1)
3.6.2 The randomized algorithm
107(3)
3.7 Permutation Routing on the Butterfly
110(2)
3.8 Computing Parallel Prefix on the Hypercube
112(1)
3.9 Hyperquicksort
113(2)
3.10 Sample Sort
115(3)
3.11 Selection on the Hypercube
118(1)
3.12 Multiselection on the Hypercube
119(3)
3.13 Load Balancing on the Hypercube
122(4)
3.14 Computing Parallel Prefix on the Butterfly
126(1)
3.15 Odd-Even Merging and Sorting on the Butterfly
127(5)
3.16 Matrix Multiplication on the Hypercube
132(6)
3.17 Bibliographic Notes
138(1)
3.18 Exercises
138(6)
3.19 Solutions
144(15)
4 The Linear Array and the Mesh
159(68)
4.1 Introduction
159(2)
4.2 Embedding between a Mesh and a Linear Array
161(1)
4.3 Broadcasting in the Linear Array and the Mesh
162(1)
4.4 Computing Parallel Prefix on the Mesh
163(1)
4.5 Odd-Even Transposition Sort
164(1)
4.6 Shearsort
165(2)
4.7 A Simple O(√n) Time Algorithm for Sorting on the Mesh
167(2)
4.8 Odd-Even Merging and Sorting on the Mesh
169(3)
4.9 Routing on the Linear Array and the Mesh
172(5)
4.9.1 Routing in the linear array
172(1)
4.9.2 Deterministic routing in the mesh
173(1)
4.9.3 Randomized routing on the mesh
174(3)
4.10 Matrix Multiplication on the Mesh
177(3)
4.10.1 The first algorithm
177(1)
4.10.2 The second algorithm
178(2)
4.11 Computing the Transitive Closure on the Mesh
180(4)
4.12 Connected Components
184(1)
4.13 Shortest Paths
185(1)
4.14 Computing the Convex Hull of a Set of Points on the Mesh
185(6)
4.14.1 The first algorithm
186(1)
4.14.2 The second algorithm
187(4)
4.15 Labeling Connected Components
191(5)
4.15.1 The propagation algorithm
191(1)
4.15.2 The recursive algorithm
192(4)
4.16 Columnsort
196(6)
4.17 3-dimensional Mesh
202(4)
4.17.1 Sorting on 3-dimensional meshes
202(4)
4.18 Bibliographic Notes
206(1)
4.19 Exercises
207(5)
4.20 Solutions
212(15)
5 Fast Fourier Transform
227(26)
5.1 Introduction
227(4)
5.2 Implementation on the Butterfly
231(1)
5.3 Iterative FFT on the Butterfly
231(3)
5.4 The Inverse Fourier Transform
234(1)
5.5 Product of Polynomials
235(3)
5.6 Computing the Convolution of Two Vectors
238(1)
5.7 The Product of a Toeplitz Matrix and a Vectors
239(2)
5.8 Using Modular Arithmetic
241(3)
5.9 Bibliographic Notes
244(1)
5.10 Exercises
244(2)
5.11 Solutions
246(7)
6 Tree-based Networks
253(28)
6.1 The Tree Network
253(7)
6.1.1 Semigroup operations
254(1)
6.1.2 Sorting by minimum extraction
254(1)
6.1.3 Sorting by partitioning
255(1)
6.1.4 Selection
256(3)
6.1.5 The one-dimensional pyramid
259(1)
6.2 The Pyramid
260(4)
6.2.1 Computing parallel prefix on the pyramid
262(2)
6.3 Mesh of Trees
264(6)
6.3.1 Sorting on the mesh of trees
266(3)
6.3.2 Routing in the mesh of trees
269(1)
6.4 Computing Parallel Prefix on the Mesh of Trees
270(2)
6.5 Comparison Between the Mesh of Trees and the Pyramid
272(1)
6.6 Bibliographic Notes
273(1)
6.7 Exercises
273(2)
6.8 Solutions
275(6)
7 The Star Network
281(32)
7.1 Introduction
281(2)
7.2 Ranking of the Processors
283(2)
7.3 Routing between Substars
285(2)
7.4 Computing Parallel Prefix on the Star
287(3)
7.5 Computing the Maximum
290(2)
7.6 Neighborhood Broadcasting and Recursive Doubling
292(2)
7.7 Broadcasting in the Star
294(2)
7.8 The Arrangement Graph
296(1)
7.9 The (d, k)-Star Graph
297(3)
7.10 Sorting in the Sd,k Star
300(3)
7.11 Bibliographic Notes
303(1)
7.12 Exercises
303(2)
7.13 Solutions
305(8)
8 Optical Transpose Interconnection System (OTIS)
313(28)
8.1 Introduction
313(1)
8.2 The OTIS-Mesh
314(10)
8.2.1 Data movements in the OTIS-Mesh
315(1)
8.2.2 Broadcasting in the OTIS-Mesh
316(1)
8.2.3 Semigroup operations on the OTIS-Mesh
316(2)
8.2.4 Parallel prefix in OTIS-Mesh
318(2)
8.2.5 Shift operations on the OTIS-Mesh
320(2)
8.2.6 Permutation routing in OTIS-Mesh
322(2)
8.2.7 Sorting on OTIS-Mesh
324(1)
8.3 The OTIS-Hypercube
324(4)
8.3.1 Simulation of an n2-processor hypercube
324(2)
8.3.2 Broadcasting in the OTIS-Hypercube
326(1)
8.3.3 Semigroup operations on the OTIS-Hypercube
326(1)
8.3.4 Sorting and routing in the OTIS-Hypercube
327(1)
8.4 Other OTIS Networks
328(2)
8.4.1 TheOTIS-Star
328(1)
8.4.2 The OTIS-MOT
328(2)
8.5 Bibliographic Notes
330(1)
8.6 Exercises
331(3)
8.7 Solutions
334(7)
9 Systolic Computation
341(16)
9.1 Introduction
341(1)
9.2 Matrix-vector Multiplication
342(1)
9.3 Computing the Convolution of Two Sequences
342(3)
9.3.1 Semisystolic solution
343(1)
9.3.2 Pure systolic solution
344(1)
9.4 A Zero-time VLSI Sorter
345(2)
9.5 An On-chip Bubble Sorter
347(4)
9.6 Bibliographic Notes
351(1)
9.7 Exercises
352(1)
9.8 Solutions
353(4)
Appendix A Mathematical Preliminaries
357(10)
A.1 Asymptotic Notations
357(2)
A.1.1 The O-notation
357(1)
A.1.2 The O-notation
358(1)
A.1.3 The G-notation
358(1)
A.1.4 The o-notation
359(1)
A.2 Divide-and-conquer Recurrences
359(2)
A.3 Summations
361(1)
A.4 Probability
362(5)
A.4.1 Random variables and expectation
362(1)
A.4.2 Bernoulli distribution
363(1)
A.4.3 Binomial distribution
364(1)
A.4.4 Chernoff bounds
364(3)
Bibliography 367(8)
Index 375