Skewed associativity enhances performance predictability

ABSTRACT

Performance tuning becomes harder as computer technology advances. One of the factors is the increasing complexity of memory hierarchies. Most modern machines now use at least one level of cache memory. To reduce execution stalls, cache misses must be very low. Software techniques used to improve locality have been developped for numerical codes, such as loop blocking and copying. Unfortunately, the behavior of direct mapped and set associative caches is still erratic when large numerical data is accessed. Execution time can vary drasticly for the same loop kernel depending on uncontrolled factors such as array leading size. The only software method available to improve execution time stability is the copying of frequently used data, which is costly in execution time. Users are not usually cache organisation experts. They are not aware of such phenomena, and have no control over it.In this paper, we show that the recently proposed four-way skewed associative cache yields very stable execution times and good average miss ratios on blocked algorithms. As a result, execution time is faster and much more predictable than with conventional caches. As a result of its better comportment, it is possible to use larger blocks sizes with blocked algorithms, which will furthermore reduces blocking overhead costs.

REFERENCES

• 1: D. Bernard, F. Bodin, A. Goasguen, C. Fechant, "Implementing a two dimensional pore-scale flow model on different parallel machines", Proceedings of X international Conference on Computational Methods in Water Resources, June 1994.
• 2: F. Bodin, C. Eisenbeis, W. Jalby, D. Windheiser, "A quantitative algorithm for data locality optimization" in Code Generation-Concepts, Tools, Techniques, Springer Verlag, 1992.
• 3: François Bodin , André Seznec, Skewed associativity enhances performance predictability, Proceedings of the 22nd annual international symposium on Computer architecture, p.265-274, June 22-24, 1995, S. Margherita Ligure, Italy
• 4: David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.53-65, June 1990, White Plains, New York, United States
• 5: Christine Eisenbeis , William Jalby , Daniel Windheiser , François Bodin, A strategy for array management in local memory, Mathematical Programming: Series A and B, v.63 n.3, p.331-370, Feb. 25, 1994 [doi>10.1007/BF01582075]
• 6: G.Irlam "Spa" personal communication 1992; the Spa package is available from [e-mail]
• 7: Monica D. Lam , Edward E. Rothberg , Michael E. Wolf, The cache performance and optimizations of blocked algorithms, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.63-74, April 08-11, 1991, Santa Clara, California, United States
• 8: A. Porterfield, "Compiler management of program locality", Technical Report, Rice University, Houston, Texas, January 1988.
• 9: M. Schlansker, R. Shaw, A. Siw~ramakrishnan "Randomization and Associativity in the Design of Placement-Insensitive Caches" HP Laboratories Technical Report 93-41, June. 1993
• 10: André Seznec, A case for two-way skewed-associative caches, Proceedings of the 20th annual international symposium on Computer architecture, p.169-178, May 16-19, 1993, San Diego, California, United States
• 11: André Seznec , François Bodin, Skewed-associative Caches, Proceedings of the 5th International PARLE Conference on Parallel Architectures and Languages Europe, p.304-316, June 14-17, 1993
• 12: O. Temam , E. D. Granston , W. Jalby, To copy or not to copy: a compile-time technique for assessing when data copying should be used to eliminate cache conflicts, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.410-419, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169762]
• 13: M. Wolf, M. Lain, "An algorithm to generate sequential and parallel code with improved data localityD", Technical Report, Stanford University 1990.
• 14: Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.3 Performance Analysis and Design Aids**
          Subjects: Simulation**

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Algorithms, Experimentation, Measurement, Performance