Parallel sorting algorithms run faster across multiple computing models

Sorting in PRAM, Parallel Comparison Model and Parallel External Memory Model

Data Structures and Algorithms

Summary

Sorting large amounts of data quickly is important for many computer programs. This paper shows new ways to sort data faster using many processors working in parallel. The authors provide improved methods for three different computer models, each suited for different hardware setups. Their new algorithms reduce the time it takes to sort by cleverly coordinating many processors without conflicts. These improvements could speed up data processing in systems with multiple processors or external memory.

What this means in practice

  • For distributed systems engineers: Design sorting processes that leverage multiple processors to reduce sorting time on large datasets distributed over parallel machines.
  • For database system developers: Improve sorting efficiency on external memory systems where data does not fit in main memory but can be processed in parallel using many I/O operations.

Authors

Gopalan Sajith, Manas Kumar Panda, Ranajit Senko

Abstract

We study the problem of sorting on the Parallel Random Access Machine (PRAM), Parallel Comparison Model (PCM) and Parallel External Memory Model (PEM). On PRAM, we present a Concurrent Read Exclusive Write algorithm that runs in $O(\log n)$ time with $n$ processors; our algorithm is very different from Cole's Merge Sort. On PCM, we present the first optimal algorithm for sorting after AKS; our algorithm runs in $O(\log n/\logα)$ comparison rounds with $nα$ processors, for $1\leqα\leq n$. On PEM, we present a Concurrent Read Exclusive Write algorithm that sorts $N$ elements in $O\left(\log\frac{N}{B}\right)$ I/O rounds with $p\geq \frac{N}{B}$ processors.