Efficient simulation of cache memories

ABSTRACT

Cache memories are used in computer systems to reduce average memory access times. Existing techniques for predicting cache performance are often unsatisfactory in terms of cost or performance. This paper presents a method for efficiently simulating the effects of a cache on the execution time of a program. We use an execution-driven simulation approach that requires no hardware support and provides a highly accurate dynamic address trace to a cache simulation model. Almost all of the overhead in this approach is in the cache simulation rather than the address trace generation. The cache simulator is used in conjunction with the Rice Parallel Processing Testbed to study the performance of concurrent programs executing on multiprocessor systems with caches. We have also developed an estimative execution-driven simulator that greatly reduces the simulation overhead by using parameters extracted from a detailed simulation of a program's execution on a processor with a cache, along with an analytical model of cache behavior. The predictions and overhead of the estimative technique are compared with those obtained from detailed cache simulations.

REFERENCES

• 1: Agarwal, A., R. L. Sites, and M. Horowitz, ATUM: A New Technique for Capturing Address Traces Using Microcode, in Proceedings of The 13th Annual International Symposium on Computer Architecture, pp. 119--127, June 1986, vol. 14, no. 3.
• 2: Agarwal, A., M. Horowitz, and J. Hennessy, An Analytical Cache Model, ACM Transactions on Computer Systems, 7, pp. 184--215, May 1989.
• 3: Clark, D. W., Cache Performance in the VAX-11/780, ACM Transactions on Computer Systems, 1, pp. 24--37, February 1983.
• 4: Covington, R. G., Validation of Rice Parallel Processing Testbed Applications, Ph.D. thesis, Rice University, Houston TX, December 1988.
• 5: Covington, R. G., S. Madala, V. Mehta, J. R. Jump, and J. B. Sinclair, The Rice Parallel Processing Testbed, in Proceedings of the ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, pp. 4--11, Santa Fe, NM, May 1988.
• 6: Covington, R. G., S. Dwarkadas, J. R. Jump, G. Lauderdale, S. Madala, and J. B. Sinclair, The Efficient Simulation of Parallel Computer Systems, TR 8904, Department of Electrical and Computer Engineering, Rice University, Houston, TX, March 1989.
• 7: Dwarkadas, S., Efficient Methods for Cache Performance Prediction, Master's thesis, Rice University, Houston TX, May 1989.
• 8: Madala, S., Concurrent C User's Manual, Technical Report TR 8701, Dept. of Electrical and Computer Engineering, Rice University, Houston, TX, January 1987.
• 9: Mitchell, C. L. and M. J. Flynn, A workbench for computer architects, IEEE Design and Test of Computers, pp. 19--29, February 1988.
• 10: Smith, A. J., Cache Memories, Computing Surveys, 14, September 1982.
• 11: Smith, A. J., Line (Block) Size Choice for CPU Cache Memories, IEEE Transactions On Computers, C-36, September 1987.
• 12: Thiebaut, D. F. and H. S. Stone, Footprints in the Cache, ACM Transactions on Computer Systems, 5, November 1987.
• 13: Weinberger, J. P., Cheap Dynamic Instruction Counting, AT & T Bell Laboratories Technical Journal, 63,, October 1984.

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**

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

General Terms:
Algorithms, Design, Measurement, Performance