Parallel Sorting Algorithms - 1st Edition - ISBN: 9780120476800, 9781483268088

Parallel Sorting Algorithms

1st Edition

Authors: Selim G. Akl
Editors: Werner Rheinboldt
eBook ISBN: 9781483268088
Imprint: Academic Press
Published Date: 10th September 1985
Page Count: 244
Tax/VAT will be calculated at check-out Price includes VAT (GST)
30% off
30% off
30% off
30% off
30% off
20% off
20% off
30% off
30% off
30% off
30% off
30% off
20% off
20% off
30% off
30% off
30% off
30% off
30% off
20% off
20% off
54.95
38.47
38.47
38.47
38.47
38.47
43.96
43.96
72.95
51.06
51.06
51.06
51.06
51.06
58.36
58.36
43.99
30.79
30.79
30.79
30.79
30.79
35.19
35.19
Unavailable
Price includes VAT (GST)
× DRM-Free

Easy - Download and start reading immediately. There’s no activation process to access eBooks; all eBooks are fully searchable, and enabled for copying, pasting, and printing.

Flexible - Read on multiple operating systems and devices. Easily read eBooks on smart phones, computers, or any eBook readers, including Kindle.

Open - Buy once, receive and download all available eBook formats, including PDF, EPUB, and Mobi (for Kindle).

Institutional Access

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.

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.

Table of Contents


Preface ix

1. 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

References

2. 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

References

3. 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

References

4. 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

References

5. 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

References

6. 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

References

7. 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

References

8. 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

References

9. 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

References

10. Parallel External Sorting

10.1 Introduction

10.2 External Sorting on a Tree

10.3 External Sorting on a Pipeline

10.4 Bibliographical Remarks

References

11. 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

References

Author Index

Subject Index

Details

No. of pages:
244
Language:
English
Copyright:
© Academic Press 1985
Published:
Imprint:
Academic Press
eBook ISBN:
9781483268088

About the Author

Selim G. Akl

About the Editor

Werner Rheinboldt