Improving memory performance of sorting algorithms

ABSTRACT

Memory hierarchy considerations during sorting algorithm design and implementation play an important role in significantly improving execution performance. Existing algorithms mainly attempt to reduce capacity misses on direct-mapped caches. To reduce other types of cache misses that occur in the more common set-associative caches and the TLB, we restructure the mergesort and quicksort algorithms further by integrating tiling, padding, and buffering techniques and by repartitioning the data set. Our study shows that substantial performance improvements can be obtained using our new methods.

REFERENCES

• 1: {1} D. Burger and T. M. Austin, <i>The SimpleScalar Tool Set, Version 2.0</i>, TR 1342, Dept. of Computer Sciences, U. of Wisconsin, Madison, June 1997.
• 2: Brian N. Bershad , Dennis Lee , Theodore H. Romer , J. Bradley Chen, Avoiding conflict misses dynamically in large direct-mapped caches, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.158-170, October 05-07, 1994, San Jose, California, United States
• 3: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 4: Anthony LaMarca , Richard E. Ladner, The influence of caches on the performance of sorting, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.370-379, January 05-07, 1997, New Orleans, Louisiana, United States
• 5: {5} L. McVoy and C. Staelin, "lmbench: portable tools for performance analysis," <i>Proc. USENIX Technical Conference</i>, San Diego, California, 1996, 279-295.
• 6: {6} K.-D. Neubert, "The Flashsortl algorithm", Dr. Dobb's Journal, February 1998, 123-125.
• 7: {7} S. Park and L. Leemis, <i>Discrete-Event Simulation: A First Course</i>, Lecture Notes, College of William & Mary, Revised Version, January 1999. Preprint of a Prentice-Hall book, August, 1999.
• 8: Gabriel Rivera , Chau-Wen Tseng, Data transformations for eliminating conflict misses, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.38-49, June 17-19, 1998, Montreal, Quebec, Canada
• 9: Robert Sedgewick, Implementing Quicksort programs, Communications of the ACM, v.21 n.10, p.847-857, Oct. 1978 [doi>10.1145/359619.359631]
• 10: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States
• 11: R. Clint Whaley , Jack J. Dongarra, Automatically tuned linear algebra software, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-27, November 07-13, 1998, San Jose, CA
• 12: Yong Yan , Xiaodong Zhang , Zhao Zhang, Cacheminer: A Runtime Approach to Exploit Cache Locality on SMP, IEEE Transactions on Parallel and Distributed Systems, v.11 n.4, p.357-374, April 2000 [doi>10.1109/71.850833]
• 13: Zhao Zhang , Xiaodong Zhang, Cache-optimal methods for bit-reversals, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.26-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331558]

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Associative memories; Cache memories

General Terms:
Algorithms, Performance

Keywords:
TLB, caches, memory performance, mergesort, quicksort