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.
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
,
SIGMOD Record 26(2),
June 1997
Contents
[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
![bibliographical record in XML](../../xml.gif)
- [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
![bibliographical record in XML](../../xml.gif)
- [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
![bibliographical record in XML](../../xml.gif)
- [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
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [15]
- David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider:
Parallel Sorting on a Shared-Nothing Architecture using Probabilistic Splitting.
PDIS 1991: 280-291
![bibliographical record in XML](../../xml.gif)
- [16]
- ...
- [17]
- ...
- [18]
- Robert H. Gerber:
Informix Online XPS.
SIGMOD Conference 1995: 463
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [23]
- C. A. R. Hoare:
Quicksort.
Comput. J. 5(1): 10-15(1962)
![bibliographical record in XML](../../xml.gif)
- [24]
- ...
- [25]
- ...
- [26]
- Chris Nyberg, Tom Barclay, Zarka Cvetanovic, Jim Gray, David B. Lomet:
AlphaSort: A RISC Machine Sort.
SIGMOD Conference 1994: 233-242
![bibliographical record in XML](../../xml.gif)
- [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
![bibliographical record in XML](../../xml.gif)
- [28]
- Michael Stonebraker:
Operating System Support for Database Management.
Commun. ACM 24(7): 412-418(1981)
![bibliographical record in XML](../../xml.gif)
- [29]
- Michael Stonebraker:
The Case for Shared Nothing.
IEEE Database Eng. Bull. 9(1): 4-9(1986)
![bibliographical record in XML](../../xml.gif)
- [30]
- ...
- [31]
- The Tandem Performance Group:
A Benchmark of NonStop SQL on the Debit Credit Transaction (Invited Paper).
SIGMOD Conference 1988: 337-341
![bibliographical record in XML](../../xml.gif)
- [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
![bibliographical record in XML](../../xml.gif)
- [34]
- ...
- [35]
- ...
- [36]
- ...
Copyright © Fri Mar 12 17:21:33 2010
by Michael Ley (ley@uni-trier.de)