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

High-Performance Sorting on Networks of Workstations.

Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau, David E. Culler, Joseph M. Hellerstein, David A. Patterson: High-Performance Sorting on Networks of Workstations. SIGMOD Conference 1997: 243-254
@inproceedings{DBLP:conf/sigmod/Arpaci-DusseauACHP97,
  author    = {Andrea C. Arpaci-Dusseau and
               Remzi H. Arpaci-Dusseau and
               David E. Culler and
               Joseph M. Hellerstein and
               David A. Patterson},
  editor    = {Joan Peckham},
  title     = {High-Performance Sorting on Networks of Workstations},
  booktitle = {SIGMOD 1997, Proceedings ACM SIGMOD International Conference
               on Management of Data, May 13-15, 1997, Tucson, Arizona, USA},
  publisher = {ACM Press},
  year      = {1997},
  pages     = {243-254},
  ee        = {http://doi.acm.org/10.1145/253260.253322, db/conf/sigmod/Arpaci-DusseauACHP97.html},
  crossref  = {DBLP:conf/sigmod/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We report the performance of NOW-Sort, a collection of sorting implementations on a Network of Workstations (NOW). We find that parallel sorting on a NOW is competitive to sorting on the large-scale SMPs that have traditionally held the performance records. On a 64-node cluster, we sort 6.0 GB in just under one minute, while a 32-node cluster finishes the Datamation benchmark in 2.41 seconds.

Our implementations can be applied to a variety of disk, memory, and processor configurations; we highlight salient issues for tuning each component of the system. We evaluate the use of commodity operating systems and hardware for parallel sorting. We find existing OS primitives for memory management and file access adequate. Due to aggregate communication and disk bandwidth requirements, the bottleneck of our system is the workstation I/O bus.

Copyright © 1997 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

Joan Peckham (Ed.): SIGMOD 1997, Proceedings ACM SIGMOD International Conference on Management of Data, May 13-15, 1997, Tucson, Arizona, USA. ACM Press 1997 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 26(2), June 1997
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1495 KB]

References

[1]
Ramesh C. Agarwal: A Super Scalar Sort Algorithm for RISC Processors. SIGMOD Conference 1996: 240-246 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
...
[3]
Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau, Amin Vahdat, Lok T. Liu, Thomas E. Anderson, David A. Patterson: The Interaction of Parallel and Sequential Workloads on a Network of Workstations. SIGMETRICS 1995: 267-278 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
Chaitanya K. Baru, Gilles Fecteau, Ambuj Goyal, Hui-I Hsiao, Anant Jhingran, Sriram Padmanabhan, Walter G. Wilson: An Overview of DB2 Parallel Edition. SIGMOD Conference 1995: 460-462 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Thorsten von Eicken, Anindya Basu, Vineet Buch, Werner Vogels: U-Net: A User-Level Network Interface for Parallel and Distributed Computing. SOSP 1995: 40-53 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
...
[7]
...
[8]
...
[9]
...
[10]
...
[11]
Haran Boral, William Alexander, Larry Clay, George P. Copeland, Scott Danforth, Michael J. Franklin, Brian E. Hart, Marc G. Smith, Patrick Valduriez: Prototyping Bubba, A Highly Parallel Database System. IEEE Trans. Knowl. Data Eng. 2(1): 4-24(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
...
[13]
...
[14]
David J. DeWitt, Shahram Ghandeharizadeh, Donovan A. Schneider, Allan Bricker, Hui-I Hsiao, Rick Rasmussen: The Gamma Database Machine Project. IEEE Trans. Knowl. Data Eng. 2(1): 44-62(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
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
[16]
...
[17]
...
[18]
Robert H. Gerber: Informix Online XPS. SIGMOD Conference 1995: 463 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
...
[20]
...
[21]
...
[22]
Mark D. Hill, James R. Larus, Steven K. Reinhardt, David A. Wood: Cooperative Shared Memory: Software and Hardware Support for Scalable Multiprocesors. ACM Trans. Comput. Syst. 11(4): 300-318(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[23]
C. A. R. Hoare: Quicksort. Comput. J. 5(1): 10-15(1962) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
...
[25]
...
[26]
Chris Nyberg, Tom Barclay, Zarka Cvetanovic, Jim Gray, David B. Lomet: AlphaSort: A RISC Machine Sort. SIGMOD Conference 1994: 233-242 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[27]
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
[28]
Michael Stonebraker: Operating System Support for Database Management. Commun. ACM 24(7): 412-418(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[29]
Michael Stonebraker: The Case for Shared Nothing. IEEE Database Eng. Bull. 9(1): 4-9(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[30]
...
[31]
The Tandem Performance Group: A Benchmark of NonStop SQL on the Debit Credit Transaction (Invited Paper). SIGMOD Conference 1988: 337-341 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[32]
...
[33]
Thorsten von Eicken, David E. Culler, Seth Copen Goldstein, Klaus E. Schauser: Active Messages: A Mechanism for Integrated Communication and Computation. ISCA 1992: 256-266 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[34]
...
[35]
...
[36]
...

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