MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Sanders, Peterdblp
Not MPG Author(s):
Winkel, Sebastian
Editor(s):
Albers, Susanne
Radzik, Tomasz		dblp
dblp
BibTeX cite key*:
SandersWinkel2004
Title, Booktitle
Title*:
Super Scalar Sample Sort
Booktitle*:
Algorithms – ESA 2004: 12th Annual European Symposium
Event, URLs
Conference URL::
http://www.ii.uib.no/algo2004/esa2004/
Downloading URL:
http://www.springerlink.com/app/home/contribution.asp?wasp=8000375kwncqqkc11nby&referrer=parent&backto=issue,69,72;journal,165,1919;linkingpublicationresults,1:105633,1
Event Address*:
Bergen, Norway
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
14 September 2004
Event End Date:
17 September 2004
Publisher
Name*:
Springer
URL:
http://www.springer.com/
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
3221
Number:
Month:
September
Pages:
784-796
Year*:
2004
VG Wort Pages:
24
ISBN/ISSN:
3540230254
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
Sample sort, a generalization of quicksort that partitions the input
into many pieces, is known as the best practical comparison based
sorting algorithm for distributed memory
parallel computers. We show that sample sort is also useful on a
single processor. The main algorithmic insight is that
element comparisons can be decoupled from expensive
conditional branching using predicated instructions.
This transformation facilitates optimizations like
loop unrolling and software pipelining.
The final implementation, albeit cache efficient,
is limited by a linear number of memory accesses rather than
the $\Oh{n\log n}$ comparisons.
On an Itanium 2 machine, we obtain a speedup of up to \maxspeedup\
over \texttt{std::sort} from the GCC STL library, which is known as one of
the fastest available quicksort implementations.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{SandersWinkel2004,
AUTHOR = {Sanders, Peter},
 EDITOR = {Albers, Susanne and Radzik, Tomasz},
 TITLE = {Super Scalar Sample Sort},
 BOOKTITLE = {Algorithms – ESA 2004: 12th Annual European Symposium},
 PUBLISHER = {Springer},
 YEAR = {2004},
 VOLUME = {3221},
 PAGES = {784--796},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Bergen, Norway},
 MONTH = {September},
 ISBN = {3540230254},
}

Entry last modified by Christine Kiesel, 04/22/2005
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Peter Sanders		Created
02/15/2005 14:34:47
Revisions
7.
6.
5.
4.
3.		Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
22.04.2005 15:12:12
22.04.2005 15:11:31
22.04.2005 15:06:49
22.04.2005 15:02:47
22.04.2005 14:54:19