ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

AlphaSort: A RISC Machine Sort.

Chris Nyberg, Tom Barclay, Zarka Cvetanovic, Jim Gray, David B. Lomet: AlphaSort: A RISC Machine Sort. SIGMOD Conference 1994: 233-242
@inproceedings{DBLP:conf/sigmod/NybergBCGL94,
  author    = {Chris Nyberg and
               Tom Barclay and
               Zarka Cvetanovic and
               Jim Gray and
               David B. Lomet},
  editor    = {Richard T. Snodgrass and
               Marianne Winslett},
  title     = {AlphaSort: A RISC Machine Sort},
  booktitle = {Proceedings of the 1994 ACM SIGMOD International Conference on
               Management of Data, Minneapolis, Minnesota, May 24-27, 1994},
  publisher = {ACM Press},
  year      = {1994},
  pages     = {233-242},
  ee        = {http://doi.acm.org/10.1145/191839.191884, db/conf/sigmod/NybergBCGL94.html},
  crossref  = {DBLP:conf/sigmod/94},
  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 Alpha AXP processors, commodity 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 a minute.

AlphaSort is a cache-sensitive memory-intensive sort algorithm. It uses file striping to get high disk bandwidth. It uses QuickSort to generate runs and uses 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 a minute, and (2) DollarSort: how much can you sort for a dollar.

Copyright © 1994 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

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

Printed Edition

Richard T. Snodgrass, Marianne Winslett (Eds.): Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, Minneapolis, Minnesota, May 24-27, 1994. ACM Press 1994 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 23(2), June 1994
Contents

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1143 KB]

References

[1]
...
[2]
Jean-Loup Baer, Yi-Bing Lin: Improving Quicksort Performance with a Codewort Data Structure. IEEE Trans. Software Eng. 15(5): 622-631(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Bjørn Arild W. Baugstø, Jarle Fredrik Greipsland: Parallel Sorting Methods for Large Data Volumes on a Hypercube Database Computer. IWDM 1989: 127-141 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
...
[5]
...
[6]
...
[7]
Micah Beck, Dina Bitton, W. Kevin Wilkinson: Sorting Large Files on a Backend Multiprocessor. IEEE Trans. Computers 37(7): 769-778(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
...
[9]
David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider: Parallel Sorting on a Shared-Nothing Architecture using Probabilistic Splitting. PDIS 1991: 280-291 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
...
[11]
...
[12]
Goetz Graefe, Shreekant S. Thakkar: Tuning a Parallel Database Algorithm on a Shared-memory Multiprocessor. Softw., Pract. Exper. 22(7): 495-517(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Jim Gray (Ed.): The Benchmark Handbook for Database and Transaction Systems (1st Edition). Morgan Kaufmann 1991
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
...
[15]
Masaru Kitsuregawa, Weikang Yang, Shinya Fushimi: Evaluation of 18-stage Pipeline Hardware Sorter. IWDM 1989: 142-155 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
Michelle Y. Kim: Synchronized Disk Interleaving. IEEE Trans. Computers 35(11): 978-988(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
Raymond A. Lorie, Honesty C. Young: A Low Communication Sort Algorithm for a Parallel Database Machine. VLDB 1989: 125-134 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
...
[20]
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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
...
[22]
...
[23]
...

Copyright © Fri Mar 12 17:21:31 2010 by Michael Ley (ley@uni-trier.de)