Andrea C. Arpaci-Dusseau
Joseph M. Hellerstein
David A. Patterson
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.
- 1.R. C. Agarwal. A Super Scalar Sort Algorithm for RISC Processors. In Proceedings of the 1996 ACM SIGMOD Conference, pages 240-246, June 1996. Google Scholar
Digital Library
- 2.T. E. Anderson, D. E. Culler, and D. A. Patterson. A Case for NOW (Networks of Workstations). IEEE Micro, Feb. 1994. Google ScholarDigital Library
- 3.R. H. Arpaci, A. C. Dusseau, A. M. Vahdat, L. T. Liu, T. E. Anderson, and D. A. Patterson. The Interaction of Parallel and Sequential Workloads on a Network of Workstations. In Proceedings qf SIGMETRICS/Performance "95, pages 267-78, 1995. Google ScholarDigital Library
- 4.C. Baru, G. Fecteau, A. Goyal, H. Hsiao, A. Jhnigran, S. Padmanabhan, and W. Wilson. An Overview of DB2 Parallel Edition. in Proceedings of 1995 SIGMOD International Conference on Management of Data, San Jose, CA, May 1995. Google ScholarDigital Library
- 5.A. Basu, V. Buch, W. Vogels, and T. yon Eicken. U-Net: A User-Level Network Interface for Parallel and Distributed Computing. In Proceedings of the l 5th ACM Symposium on Operating Systen~v Principles, Copper Mountain, Colorado, Dec. 1995. Google ScholarDigital Library
- 6.B. Baugsto, J. Greipsland, and J. Kamerbeek. Sorting Large Data Files on POMA. In Proceedings ofCOMPAR-90 VAPPIV, pages 536-547, Sept. 1990. Springer Vedag Lecture Notes No. 357. Google ScholarDigital Library
- 7.M. Beck, D. Bitton, and W. K. Wilkinson. Sorting Large Files on a Backend Multiprocessor. Technical Report 86-741, Department of Computer Science, Comell University, Mar. 1986. Google ScholarDigital Library
- 8.G. Blelloch, C. Leiserson, and B. Maggs. A Comparison of Sorting Algorithms for the Connection Machine CM-2. In Symposium on Parallel Algorithms and Architectures, July 199 I. Google ScholarDigital Library
- 9.M. A. Blumrich, K. Li, R. Alpert, C. Dubnicki, E. W. Felten, and J. Sandberg. Virtual Memory Mapped Network Interface for the SHRIMP Multicomputer. In Proceedings of the International Symposium on Computer Architecture, pages 142-153, Apr. 1994. Google ScholarDigital Library
- 10.N. Boden, D. Cohen, R. E. Felderman, A. Kulawik, and C. Seitz. Myrinet: A Gigabit-per-second Local Area Network. IEEE Micro, Feb. 1995. Google ScholarDigital Library
- 11.H. Boral, W. Alexander, L. Clay, G. Copeland, et al. Prototyping Bubba, a Highly Parallel Database System. IEEE Transactions on Knowledge and Data Engineering, 2(1):4--24, Mar. 1990. Google ScholarDigital Library
- 12.D. Culler, A. Dusseau, S. Goldstein, A. Krishnamurthy, S. Lumetta, T. von Eicken, and K. Yelick. Parallel Programming in Split-C. In Supercomputing '93, 1993. Google ScholarDigital Library
- 13.D. Culler, L. T. Liu, R. Martin, and C. Yoshikawa. LogP Performance Assessment of Fast Network Interfaces. IEEE Micro, Feb. 1996. Google ScholarDigital Library
- 14.D. DeWitt, S. Ghandeharizadeh, D. Schneider, A. Bdcker, et al. The Gamma Database Machine Project. IEEE Transactions on Knowledge and Data Engineering, 2( l ):44-62, Mar. 1990. Google ScholarDigital Library
- 15.D. Dewitt, J. Naughton, and D. Schneider. Parallel Sorting on a Shared-Nothing Architecture using Probabilistic Splitting. In Proceedings of the International Conference on Parallel and Distributed Information Systmes, 1991. Google ScholarDigital Library
- 16.A.C. Dusseau, D.E. Culler, K. E. Schauser, and R. P. Martin. Fast Parallel Sorting Under LogP: Experience with the CM-5. IEEE Transactions on Parallel and Distributed Systems, 7(8):791-805, Aug. 1996. Google ScholarDigital Library
- 17.A. et. al. A Measure of Transaction Processing Power. Datamation, 31 (7): 112-118, 1985. Also in Readings in Database Systems, M.H. Stonebraker ed., Morgan Kaufmann, San Mateo, 1989. Google ScholarDigital Library
- 18.B. Gerber. Informix Online XPS. In Proceedings of 1995 SIG- MOD International Conference on Management o.f Data, San Jose, CA, May 1995. Google ScholarDigital Library
- 19.D. P. Ghormley, D. Petrou, A. M. Vahdat, and T. E. Anderson. GLUnix: A Global Layer Unix for NOW. http://now.cs.berkeley.edu/Glunix/glunix.html.Google Scholar
- 20.G. Graefe. Volcano: An Extensible and Parallel Dataflow Query Processing System. Technical report, Oregon Graudate Center, June 1989.Google Scholar
- 21.G. Graefe. Parallel External Sorting in Volcano. Technical Report CU-CS-459, Computer Science, University of Colorado at Boulder, June 1990.Google Scholar
- 22.M. D. Hill, J. R. Larus, S. Reinhardt, and D. A. Wood. Cooperative-Shared Memory: Software and Hardware for Scalable Multiprocessors. ACM Transactions on Computer Systems, 11(4):300-318, 1993. Google ScholarDigital Library
- 23.C. A. R. Hoare. Quicksort. Computer Journal, 5( 1): 10-15,1962.Google Scholar
- 24.S. Kleiman, J. Voll, J. Eykholt, A. Shivalingiah, D. Williams, M. Smith, S. Barton, and G. Skinner. Symmetric Multiprocessing in Solaris 2.0. In Proceedings of COMPCON Spring '92, 1992. Google ScholarDigital Library
- 25.X. Li, G. Linoff, S. Smith, C. Stanfill, and K. Thearling. A Practical External Sort for Shared Disk MPPs. In Proceedings of SUPERCOMPUTING "93, pages 666-675, Nov. 1993. Google ScholarDigital Library
- 26.C. Nyberg, T. Barclay, Z. Cvetanovic, J. Gray, and D. Lomet. AlphaSort: A RISC Machine Sort. In Proceedings of 1994 ACM SIGMOD Conference, May 1994. Google ScholarDigital Library
- 27.B. Salzberg, A. Tsukerman, J. Gray, M. Stewart, S. Uren, and B. Vaughna. FastSort; A Distributed Single-Input Single-Output External Sort. SIGMOD Record, 19(2):94-I01,June 1990. Google ScholarDigital Library
- 28.M. Stonebraker. Operating System Support for Database Management. Communications of the ACM, 24(7):412-418, July 1981. Google ScholarDigital Library
- 29.M. Stonebraker. The Case for Shared Nothing. Database Engineering, 9(1 ), 1986.Google Scholar
- 30.A. Sweeney, D. Doucette, W. Hu, C. Anderson, M. Nishimoto, and G. Peck. Scalability in the XFS File System. in Proceedings of the USENIX 1996 Annual Technical Conference, Jan. 1996. Google ScholarDigital Library
- 31.Tandem Performance Group. A Benchmark of NonStop SQL on Debit-Credit Transactions. In Proceedings of SIGMOD International Conference on Managament of Data, Chicago, IL, June 1988. Google ScholarDigital Library
- 32.Teradata Corporation. DBC/IO12 Data Base Computer System Manual, release 2.0 edition, Nov. 1985. Document Number c 10- 0001-02.Google Scholar
- 33.T. yon Eicken, D. E. Culler, S. C. Goldstein, and K. E. Schauser. Active Messages: a Mechanism for Integrated Communication and Computation. In Proceedings of the 19th Annual Symposium on Computer Architecture, Gold Coast, Australia, May 1992. Google ScholarDigital Library
- 34.H. Young and A. Swami. The Parameterized Round-Robin Partitioned Algorithm for Parallel External Sort. In Proceedings 9th international Parallel Processing Symposium, pages 213-219, Santa Barbara, CA, Apr. 1995. Google ScholarDigital Library
- 35.M. Zagha and G. Blelloch. Radix Sort for Vector Multiprocessors. In Supercomputing, 1991. Google ScholarDigital Library
- 36.W. Zhang and P. Larson. A Memory-AdaptiveSort (MASORT) for Database Systems. In Proceedings of CASCON "96, Toronto, Nov. 1996. Google ScholarDigital Library
Index Terms
- High-performance sorting on networks of workstations
Recommendations
High-performance sorting on networks of workstations
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 ...
OpenMP on networks of workstations
SC '98: Proceedings of the 1998 ACM/IEEE conference on SupercomputingWe describe an implementation of a sizable subset of OpenMP on networks of workstations (NOWs). By extending the availability of OpenMP to NOWs, we overcome one of its primary drawbacks compared to MPI, namely lack of portability to environments other ...
A practical performance comparison of parallel sorting algorithms on homogeneous network of workstations
TELE-INFO'06: Proceedings of the 5th WSEAS international conference on Telecommunications and informaticsThree parallel sorting algorithms have been implemented and compared in terms of their overall execution time. The algorithms implemented are the odd-even transposition sort, parallel merge sort and parallel rank sort. A homogeneous cluster of ...
Comments