Influence of cross-interferences on blocked loops: a case study with matrix-vector multiply

ABSTRACT

State-of-the art data locality optimizing algorithms are targeted for local memories rather than for cache memories. Recent work on cache interferences seems to indicate that these phenomena can severely affect blocked algorithms cache performance. Because of cache conflicts, it is not possible to know the precise gain brought by blocking. It is even difficult to determine for which problem sizes blocking is useful. Computing the actual optimal block size is difficult because cache conflicts are highly irregular. In this article, we illustrate the issue of precisely evaluating cross-interferences in blocked loops with blocked matrix-vector multiply. Most significant interference phenomena are captured because unusual parameters such as array base addresses are being considered. The techniques used allow us to compute the precise improvement due to blocking and the threshold value of problem parameters for which the blocked loop should be preferred. It is also possible to derive an expression of the optimal block size as a function of problem parameters. Finally, it is shown that a precise rather than an approximate evaluation of cache conflicts is sometimes necessary to obtain near-optimal performance.

REFERENCES

• 1: EISENBEIS, C., JALBY, W., WINDHEISER, D., AND BODIN, F. 1990. A strategy for array management in local memory. In Proceedings of the 3rd Workshop on Programming Languages and Compilers for Parallel Computzng. Irvine, California.
• 2: ESSEGHIR, K. 1993. Improving data locality for caches. M.S. thesis, Univ of Texas, Houston, ~rex.
• 3: Jeanne Ferrante , Vivek Sarkar , W. Thrash, On Estimating and Enhancing Cache Effectiveness, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.328-343, August 07-09, 1991
• 4: FRICKER, C., TEMAM, O., AND JALBY, W. 1993. Accurate evMuation of blocked algorithms cache interferences. Tech. rep., Leiden Univ., Leiden, The Netherlands. Mar.
• 5: Gerry Kane , Joe Heinrich, MIPS RISC architectures, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 6: 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
• 7: Kathryn Stuart McKinley, Automatic and interactive parallelization, Rice University, Houston, TX, 1992
• 8: Allan Kennedy Porterfield , K. W. Kennedy, Software methods for improvement of cache performance on supercomputer applications, 1989
• 9: Richard L. Sites, Alpha architecture reference manual, Digital Press, Newton, MA, 1992
• 10: TEMAM, 0., FRICKER, C., AND JALBY, W. 1993. Impact of cache interferences on usual numer- ical dense loop nests. In Proc. IEEE, special issue on Computer Performance Evaluation.
• 11: O. Temam , C. Fricker , W. Jalby, Cache interference phenomena, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.261-271, May 16-20, 1994, Nashville, Tennessee, United States
• 12: Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, ACM SIGPLAN Notices, v.26 n.6, p.30-44, June 1991

INDEX TERMS

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

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

  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

General Terms:
Measurement, Performance

Keywords:
blocking, cache conflicts (interferences), cache performance, data locality optimization, numerical codes