Parallel Sorting Algorithms (eBook)

Selim G. Akl (Autor)

Werner Rheinboldt (Herausgeber)

eBook Download: PDF

2014 | 1. Auflage
244 Seiten
Elsevier Science (Verlag)
978-1-4832-6808-8 (ISBN)

Infos

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.

Inhalt

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

Produkt-Details

• Erscheint lt. Verlag: 20.6.2014
• Sprache: englisch
• Themenwelt: Sachbuch/Ratgeber ► Freizeit / Hobby ► Spielen / Raten
• Themenwelt: Schulbuch / Wörterbuch ► Lexikon / Chroniken
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Technik
• ISBN-10: 1-4832-6808-X / 148326808X
• ISBN-13: 978-1-4832-6808-8 / 9781483268088