Akl / Rheinboldt Parallel Sorting Algorithms

1. Auflage 2014
ISBN: 978-1-4832-6808-8
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 244 Seiten, Web PDF

Parallel Sorting Algorithms explains how to use parallel algorithms to sort a sequence of items on a variety of parallel computers. The book reviews the sorting problem, the parallel models of computation, parallel algorithms, and the lower bounds on the parallel sorting problems. The text also presents twenty different algorithms, such as linear arrays, mesh-connected computers, cube-connected computers. Another example where algorithm can be applied is on the shared-memory SIMD (single instruction stream multiple data stream) computers in which the whole sequence to be sorted can fit in the respective primary memories of the computers (random access memory), or in a single shared memory. SIMD processors communicate through an interconnection network or the processors communicate through a common and shared memory. The text also investigates the case of external sorting in which the sequence to be sorted is bigger than the available primary memory. In this case, the algorithms used in external sorting is very similar to those used to describe internal sorting, that is, when the sequence can fit in the primary memory, The book explains that an algorithm can reach its optimum possible operating time for sorting when it is running on a particular set of architecture, depending on a constant multiplicative factor. The text is suitable for computer engineers and scientists interested in parallel algorithms.

Autoren/Hrsg.

Akl, Selim G.

Rheinboldt, Werner

Inhaltsverzeichnis

1;Front Cover;1
2;Parallel Sorting Algorithms;4
3;Copyright Page;5
4;Table of Contents;8
5;Dedication;6
6;Preface;12
7;Chapter 1. Introduction;16
7.1;1.1 Motivation;16
7.2;1.2 The Sorting Problem;17
7.3;1.3 Parallel Models of Computation;19
7.4;1.4 Parallel Algorithms;22
7.5;1.5 Lower Bounds on the Parallel Sorting Problem;26
7.6;1.6 Organization of the Book;27
7.7;1.7 Bibliographical Remarks;27
7.8;References;29
8;Chapter 2. Networks for Sorting;32
8.1;2.1 Introduction;32
8.2;2.2 Enumeration Sort;32
8.3;2.3 Sorting by Odd–Even Merging;38
8.4;2.4 Sorting Based on Bitonic Merging;44
8.5;2.5 Bibliographical Remarks;52
8.6;References;52
9;Chapter 3. Linear Arrays;56
9.1;3.1 Introduction;56
9.2;3.2 Odd–Even Transposition Sort;56
9.3;3.3 Merge–Splitting Sort;59
9.4;3.4 Mergesort on a Pipeline;63
9.5;3.5 Enumeration Sort;66
9.6;3.6 Bibliographical Remarks;73
9.7;References;74
10;Chapter 4. The Perfect Shuffle;76
10.1;4.1 Introduction;76
10.2;4.2 Bitonic Sorting Using the Perfect Shuffle;80
10.3;4.3 An Optimal Merge–Splitting Algorithm;91
10.4;4.4 Bibliographical Remarks;92
10.5;References;93
11;Chapter 5. Mesh-Connected Computers;96
11.1;5.1 Introduction;96
11.2;5.2 Model of Computation;96
11.3;5.3 The Sorting Problem;98
11.4;5.4 A Lower Bound;100
11.5;5.5 Sorting on the Mesh;101
11.6;5.6 An Optimal Algorithm;121
11.7;5.7 Bibliographical Remarks;123
11.8;References;124
12;Chapter 6. Tree Machines;126
12.1;6.1 Introduction;126
12.2;6.2 Minimum Extraction;127
12.3;6.3 Bucket Sorting and Merging;132
12.4;6.4 Median Finding and Splitting;136
12.5;6.5 Bibliographical Remarks;139
12.6;References;144
13;Chapter 7. Cube-Connected Computers;148
13.1;7.1 Introduction;148
13.2;7.2 Model of Computation;148
13.3;7.3 The Sorting Problem;149
13.4;7.4 The Sorting Machine;150
13.5;7.5 Sorting on the Cube;154
13.6;7.6 Bibliographical Remarks;170
13.7;References;172
14;Chapter 8. Shared-Memory SIMD Computers;174
14.1;8.1 Introduction;174
14.2;8.2 Model of Computation;176
14.3;8.3 A Parallel Algorithm for Selection;178
14.4;8.4 Sorting on a Shared-Memory SIMD Computer;182
14.5;8.5 Bibliographical Remarks;186
14.6;References;188
15;Chapter 9. Asynchronous Sorting on Multiprocessors;190
15.1;9.1 Introduction;190
15.2;9.2 Running Asynchronous Algorithms;192
15.3;9.3 Asynchronous Sorting by Enumeration;193
15.4;9.4 Asynchronous Quicksort;196
15.5;9.5 Bibliographical Remarks;204
15.6;References;205
16;Chapter 10. Parallel External Sorting;208
16.1;10.1 Introduction;208
16.2;10.2 External Sorting on a Tree;209
16.3;10.3 External Sorting on a Pipeline;215
16.4;10.4 Bibliographical Remarks;224
16.5;References;225
17;Chapter 11. Lower Bounds;226
17.1;11.1 Introduction;226
17.2;11.2 A Review of Lower Bounds;227
17.3;11.3 Counting Comparisons;228
17.4;11.4 Broadcasting;229
17.5;11.5 A Lower Bound on Tree Sorting;232
17.6;11.6 Bibliographical Remarks;233
17.7;References;235
18;Author Index;238
19;Subject Index;242