panthema / tags / massive-sorting

Weblog Articles Tagged with '#massive-sorting'

Weblog Articles

Algorithm schema of Recurse Last Parallel Multiway Mergesort

Practical Massively Parallel Sorting -- Basic Algorithmic Ideas

Posted on 2014-10-24 22:30 by Timo Bingmann at Permlink with 0 Comments. Tags: #research #massive-sorting

Last Friday we were able to finish a technical report on "Practical Massively Parallel Sorting -- Basic Algorithmic Ideas", which is now available on arXiv as 1410.6754 or locally: 1410.6754v1.pdf 1410.6754v1.pdf with source 1410.6754v1.tar.gz 1410.6754v1.tar.gz (130 KiB). A big thanks goes to all the other authors, Michael Axtmann, Peter Sanders, and Christian Schulz.

The report proposes two new hierarchical algorithms "Recurse Last Mergesort" (RLM-Sort) and "Adaptive Multipass Sample Sort" (AMS-Sort), together with randomized data exchange schemes to avoid worst case behavior on large instances.

Download 1410.6754v1.pdf

We now plan to implement some of the new algorithms.

Abstract

To obtain sorting algorithms that scale to the largest available machines, conventional parallel sorting algorithms cannot be used since they either have prohibitive communication volume or prohibitive critical path length for computation. We outline ideas how to combine a number of basic algorithmic techniques which overcome these bottlenecks.