Software caching vs. prefetching

ABSTRACT

The performance gap between memory subsystem and high-performance processors is ever-increasing. Prefetching is one method to bridge this performance gap. Prefetching has been proposed for array-based and pointer applications, typically using software-based techniques with the help of the compiler. Prefetching suffers from certain disadvantages such as an increase in memory traffic, an increase in the number of executed instructions, and an increase in memory requirement for some cases.In this paper, we investigate the technique of software caching for applications that perform searches or sorted insertions. For data structures larger than the processor data cache, such a search or sorted insert may result in multiple cache misses before the correct value is found. In a software caching approach, a small software buffer is maintained that records the most recently added values (these values are the ones that are later searched) along with their addresses and is consulted during a search or an insert. In this paper, we present results of our initial experiments. We found that for applications involving a search, software caching performs as high as 30% better than the original application. Also, this technique executes upto 14% less instructions and the number of cache accesses decrease by around upto 18%. We also compared this technique against software prefetching and found that in some cases, the performance improvement was as high as 40%. This technique also has an added advantage of using less memory space than prefetching (all the improvements were obtained for very small software caches). These initial results encourage a more in-depth study of this technique.

REFERENCES

• 1: Abdel-Hameed A. Badawy , Aneesh Aggarwal , Donald Yeung , Chau-Wen Tseng, Evaluating the impact of memory system performance on software prefetching and locality optimizations, Proceedings of the 15th international conference on Supercomputing, p.486-500, June 2001, Sorrento, Italy [doi>10.1145/377792.377906]
• 2: D. Burger and T. Austin, "The simplescalar tool set," Technical report, Computer Sciences Department, University of Wisconsin, June, 1997.
• 3: Brad Calder , Chandra Krintz , Simmi John , Todd Austin, Cache-conscious data placement, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.139-149, October 02-07, 1998, San Jose, California, United States
• 4: David Callahan , Ken Kennedy , Allan Porterfield, Software prefetching, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.40-52, April 08-11, 1991, Santa Clara, California, United States
• 5: Trishul M. Chilimbi , Mark D. Hill , James R. Larus, Cache-conscious structure layout, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.1-12, May 01-04, 1999, Atlanta, Georgia, United States
• 6: Chen Ding , Ken Kennedy, Improving cache performance in dynamic applications through data and computation reorganization at run time, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.229-241, May 01-04, 1999, Atlanta, Georgia, United States
• 7: Hwansoo Han , Chau-Wen Tseng, Improving Locality for Adaptive Irregular Scientific Codes, Proceedings of the 13th International Workshop on Languages and Compilers for Parallel Computing-Revised Papers, p.173-188, August 10-12, 2000
• 8: M. Karlsson, F. Dahlgren and P. Stenstrom, "A Prefetching Technique for Irregular Accesses to Linked Data Structures", Proc. of HPCA, Jan. 2000.
• 9: Chi-Keung Luk , Todd C. Mowry, Compiler-based prefetching for recursive data structures, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.222-233, October 01-04, 1996, Cambridge, Massachusetts, United States
• 10: Luddy Harrison, Examination of a memory access classification scheme for pointer-intensive and numeric programs, Proceedings of the 10th international conference on Supercomputing, p.133-140, May 25-28, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237578.237595]
• 11: William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
• 12: 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
• 13: Amir Roth , Andreas Moshovos , Gurindar S. Sohi, Dependence based prefetching for linked data structures, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.115-126, October 02-07, 1998, San Jose, California, United States
• 14: Amir Roth , Gurindar S. Sohi, Effective jump-pointer prefetching for linked data structures, Proceedings of the 26th annual international symposium on Computer architecture, p.111-121, May 01-04, 1999, Atlanta, Georgia, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Memory management (garbage collection)

General Terms:
Performance

Keywords:
memory optimization, software caching, software prefetching