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

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.

Post Comment
Name:
E-Mail or Homepage:	URLs (http://...) are displayed, e-mails are hidden and used for Gravatar.
Many common HTML elements are allowed in the text, but no CSS style.