Performance evaluation of LAN sorting algorithms

ABSTRACT

We adapt several parallel sorting algorithms (block sorting algorithms) and distributed sorting algorithms for implementation on an Ethernet network with diskless Sun workstations. We argue that the performance of sorting algorithms on local area networks (LANs) should be analyzed in a manner that is different from the ways that parallel and distributed sorting algorithms are usually analyzed. Consequently, we propose an empirical approach which will provide more insight into the performance of the algorithms. We obtain data on communication time, local processing time, and response time (i.e. total running time) of each algorithm for various file sizes and different numbers of processors. Comparing the performance data with our theoretical analysis, we attempt to provide rationale for the behaviour of the algorithms and project the future behaviour of the algorithms as file size, number of processors, or interprocessor communication facilities change.

REFERENCES

• 1: Dina Bitton , Haran Boral , David J. DeWitt , W. Kevin Wilkinson, Parallel algorithms for the execution of relational database operations, ACM Transactions on Database Systems (TODS), v.8 n.3, p.324-353, Sept. 1983 [doi>10.1145/319989.319991]
• 2: Dina Bitton , David J. DeWitt , David K. Hsaio , Jaishankar Menon, A taxonomy of parallel sorting, ACM Computing Surveys (CSUR), v.16 n.3, p.287-318, Sept. 1984 [doi>10.1145/2514.2516]
• 3: Cheriton, D.R. The V Kernel: A Software Base for Distributed Systems. IEEE Software. 1(2), April, 1984.
• 4: Robert M. Metcalfe , David R. Boggs, Ethernet: distributed packet switching for local computer networks, Communications of the ACM, v.19 n.7, p.395-404, July 1976 [doi>10.1145/360248.360253]
• 5: Thomas W. Page, Jr. , Gerald J. Popek, Distributed management in local area networks, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.135-142, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325421]
• 6: Rotem, D., Santoro, N. and Sidney, J. Distributed Sorting. IEEE Trans. on Comp. 0-34(4), April, 1985.
• 7: Salehmohamed, M. Experimental Analysis of LAN Sorting Algorithms. Master's thesis, School of Computing Science, Simon Fraser University, 1986.
• 8: Santoro, N. and Sidney, J.B. Communication Bounds for Selection in Distributed Sets. Technical Report SCS-TR-10, School of Computing Science, Carleton University, September, 1982.
• 9: Santoro, N. and Sidney, J.B. A Reduction Technique for Selection in Distributed Files: L Technica# Report SCS-TR-23, School of Computing Science, Carleton University, April, 1983.
• 10: Wegner, L.M. Sorting a Distributed File. Computer Networks (8), August, 1984.

INDEX TERMS

Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Experimentation, Measurement, Performance, Theory