Parallel Sorting Algorithms
Published on 20. June 2014
244 pages
978-1-4832-6808-8 (ISBN)
Description
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.
More details
Other editions
Additional editions
S. G. Akl
Parallel Sorting Algorithms
Book
01/1985
Academic Press
€66.24
Article exhausted; check different version
Content
Preface ix1. Introduction 1.1 Motivation 1.2 The Sorting Problem 1.3 Parallel Models of Computation 1.4 Parallel Algorithms 1.5 Lower Bounds on the Parallel Sorting Problem 1.6 Organization of the Book 1.7 Bibliographical Remarks References2. Networks for Sorting 2.1 Introduction 2.2 Enumeration Sort 2.3 Sorting by Odd-Even Merging 2.4 Sorting Based on Bitonic Merging 2.5 Bibliographical Remarks References3. Linear Arrays 3.1 Introduction 3.2 Odd-Even Transposition Sort 3.3 Merge-Splitting Sort 3.4 Mergesort on a Pipeline 3.5 Enumeration Sort 3.6 Bibliographical Remarks References4. The Perfect Shuffle 4.1 Introduction 4.2 Bitonic Sorting Using the Perfect Shuffle 4.3 An Optimal Merge-Splitting Algorithm 4.4 Bibliographical Remarks References5. Mesh-Connected Computers 5.1 Introduction 5.2 Model of Computation 5.3 The Sorting Problem 5.4 A Lower Bound 5.5 Sorting on the Mesh 5.6 An Optimal Algorithm 5.7 Bibliographical Remarks References6. Tree Machines 6.1 Introduction 6.2 Minimum Extraction 6.3 Bucket Sorting and Merging 6.4 Median Finding and Splitting 6.5 Bibliographical Remarks References7. Cube-Connected Computers 7.1 Introduction 7.2 Model of Computation 7.3 The Sorting Problem 7.4 The Sorting Machine 7.5 Sorting on the Cube 7.6 Bibliographical Remarks References8. Shared-Memory SIMD Computers 8.1 Introduction 8.2 Model of Computation 8.3 A Parallel Algorithm for Selection 8.4 Sorting on a Shared-Memory SIMD Computer 8.5 Bibliographical Remarks References9. Asynchronous Sorting on Multiprocessors 9.1 Introduction 9.2 Running Asynchronous Algorithms 9.3 Asynchronous Sorting by Enumeration 9.4 Asynchronous Quicksort 9.5 Bibliographical Remarks References10. Parallel External Sorting 10.1 Introduction 10.2 External Sorting on a Tree 10.3 External Sorting on a Pipeline 10.4 Bibliographical Remarks References11. Lower Bounds 11.1 Introduction 11.2 A Review of Lower Bounds 11.3 Counting Comparisons 11.4 Broadcasting 11.5 A Lower Bound on Tree Sorting 11.6 Bibliographical Remarks ReferencesAuthor IndexSubject Index
