panthema / 2015 / 0922-Engineering-Parallel-String-Sorting-Journal-Article
Thumbnail of a small ternary search tree used for classification, and LCP-aware tournament tree.

Publication: Engineering Parallel String Sorting in Algorithmica Journal

Posted on 2015-09-22 15:46 by Timo Bingmann at Permlink with 0 Comments. Tags: research sorting university

Our paper "Engineering Parallel String Sorting" was accepted for publication in Springer's Algorithmica Journal, and is available online at http://dx.doi.org/10.1007/s00453-015-0071-1.

Compare to our older technical report, the journal edition contains many (minor and major) corrections, additional references and better explanations.

A pre-print version is available here: Engineering-Parallel-String-Sorting.pdf Engineering-Parallel-String-Sorting.pdf.

Download Engineering-Parallel-String-Sorting.pdf

Please refer to the main parallel-string-sorting page for details and source code.

Abstract

We discuss how string sorting algorithms can be parallelized on modern multi-core shared memory machines. As a synthesis of the best sequential string sorting algorithms and successful parallel sorting algorithms for atomic objects, we first propose string sample sort. The algorithm makes effective use of the memory hierarchy, uses additional word level parallelism, and largely avoids branch mispredictions. Then we focus on NUMA architectures, and develop parallel multiway LCP-merge and -mergesort to reduce the number of random memory accesses to remote nodes. Additionally, we parallelize variants of multikey quicksort and radix sort that are also useful in certain situations. As base-case sorter for LCP-aware string sorting we describe sequential LCP-insertion sort which calculates the LCP array and accelerates its insertions using it. Comprehensive experiments on five current multi-core platforms are then reported and discussed. The experiments show that our parallel string sorting implementations scale very well on real-world inputs and modern machines.

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.
RSS 2.0 Weblog Feed Atom 1.0 Weblog Feed Valid XHTML 1.1 Valid CSS (2.1)
Copyright 2005-2017 Timo Bingmann - Impressum