AlphaSort: A Cache-Sensitive Parallel External Sort.

Chris Nyberg, Tom Barclay, Zarka Cvetanovic, Jim Gray, David B. Lomet: AlphaSort: A Cache-Sensitive Parallel External Sort. VLDB J. 4(4): 603-627(1995)

@article{DBLP:journals/vldb/NybergBCGL95,
  author    = {Chris Nyberg and
               Tom Barclay and
               Zarka Cvetanovic and
               Jim Gray and
               David B. Lomet},
  title     = {AlphaSort: A Cache-Sensitive Parallel External Sort},
  journal   = {VLDB J.},
  volume    = {4},
  number    = {4},
  year      = {1995},
  pages     = {603-627},
  ee        = {db/journals/vldb/NybergBCGL95.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A new sort algorithm, called AlphaSort, demonstrates that commodity processors and disks can handle commercial batch workloads. Using commodity processors, memory, and arrays of SCSI disks, AlphaSort runs the industry-standard sort benchmark in seven seconds. This beats the best published record on a 32-CPU 32-disk Hypercube by 8:1. On another benchmark, AlphaSort sorted more than a gigabyte in one minute. AlphaSort is a cache-sensitive, memory-intensive sort algorithm. We argue that modern architectures require algorithm designers to re-examine their use of the memory hierarchy. AlphaSort uses clustered data structures to get good cache locality, file striping to get high disk bandwidth, QuickSort to generate runs, and replacement-selection to merge the runs. It uses shared memory multiprocessors to break the sort into subsort chores. Because startup times are becoming a significant part of the total time, we propose two new benchmarks: (1) MinuteSort: how much can you sort in one minute, and (2) PennySort: how much can you sort for one penny.

Copyright © 1995 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Key Words

Sort, cache, disk, memory, striping, parallel, Alpha, Dec 7000.

Preliminary Version: SIGMOD 1994: 233-242

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An4-1 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD2 or /dvd

References

[Anon et al. 1989]: ...
[Baer & Lin 1989]: Jean-Loup Baer, Yi-Bing Lin: Improving Quicksort Performance with a Codewort Data Structure. IEEE Trans. Software Eng. 15(5): 622-631(1989)
[Baugsto & Greipsland 1989]: Bjørn Arild W. Baugstø, Jarle Fredrik Greipsland: Parallel Sorting Methods for Large Data Volumes on a Hypercube Database Computer. IWDM 1989: 127-141
[Baugsto et al. 1990]: ...
[Beck et al. 1988]: Micah Beck, Dina Bitton, W. Kevin Wilkinson: Sorting Large Files on a Backend Multiprocessor. IEEE Trans. Computers 37(7): 769-778(1988)
[Bitton 1981]: ...
[Connor 1977]: ...
[Cvetanovic & Bhandarkar 1994]: Zarka Cvetanovic, Dileep Bhandarkar: Characterization of Alpha AXP Performance Using TP and SPEC Workloads. ISCA 1994: 60-70
[DeWitt et al. 1992]: David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider: Parallel Sorting on a Shared-Nothing Architecture using Probabilistic Splitting. PDIS 1991: 280-291
[Graefe 1990]: ...
[Graefe & Thakkar 1992]: Goetz Graefe, Shreekant S. Thakkar: Tuning a Parallel Database Algorithm on a Shared-memory Multiprocessor. Softw., Pract. Exper. 22(7): 495-517(1992)
[Gray 1991]: Jim Gray (Ed.): The Benchmark Handbook for Database and Transaction Systems (1st Edition). Morgan Kaufmann 1991
Contents
[Kaivalya 1993]: ...
[Kim 1986]: Michelle Y. Kim: Synchronized Disk Interleaving. IEEE Trans. Computers 35(11): 978-988(1986)
[Kitsuregawa et al. 1989]: Masaru Kitsuregawa, Weikang Yang, Shinya Fushimi: Evaluation of 18-stage Pipeline Hardware Sorter. IWDM 1989: 142-155
[Knuth 1973]: Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
[Lorie & Young 1989]: Raymond A. Lorie, Honesty C. Young: A Low Communication Sort Algorithm for a Parallel Database Machine. VLDB 1989: 125-134
[Lorin 1974]: ...
[Nyberg et al. 1994]: Chris Nyberg, Tom Barclay, Zarka Cvetanovic, Jim Gray, David B. Lomet: AlphaSort: A RISC Machine Sort. SIGMOD Conference 1994: 233-242
[Salzberg et al. 1990]: Betty Salzberg, Alex Tsukerman, Jim Gray, Michael Stewart, Susan Uren, Bonnie Vaughan: FastSort: A Distributed Single-Input Single-Output External Sort. SIGMOD Conference 1990: 94-101
[Tsukerman 1986]: ...
[Weinberger 1986]: ...
[Yamane & Take 1988]: Yasuo Yamane, R. Take: Parallel Partition Sort for Database Machines. IWDM 1987: 117-130