Efficient trace-driven simulation method for cache performance analysis

ABSTRACT

We propose improvements to current trace-driven cache simulation methods to make them faster and more economical. We attack the large time and space demands of cache simulation in two ways. First, we reduce the program traces to the extent that exact performance can still be obtained from the reduced traces. Second, we devise an algorithm that can produce performance results for a variety of metrics (hit ratio, write-back counts, bus traffic) for a large number of set-associative write-back caches in just a single simulation run. The trace reduction and the efficient simulation techniques are extended to parallel multiprocessor cache simulations. Our simulation results show that our approach substantially reduces the disk space needed to store the program traces and can dramatically speedup cache simulations and still produce the exact results.

REFERENCES

• 1: AGARWAL, ANANT. Analysis of Cache Per}ormance Dissertation, Stanford University, 1987.
• 2: M. D. Hill , A. J. Smith, Evaluating Associativity in CPU Caches, IEEE Transactions on Computers, v.38 n.12, p.1612-1630, December 1989 [doi>10.1109/12.40842]
• 3: Mark Donald Hill , Alan Jay Smith, Aspects of cache memory and instruction buffer performance, 1987
• 4: Mark D. Hill, A Case for Direct-Mapped Caches, Computer, v.21 n.12, p.25-40, December 1988 [doi>10.1109/2.16187]
• 5: N. P. Jouppi , D. W. Wall, Available instruction-level parallelism for superscalar and superpipelined machines, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.272-282, April 03-06, 1989, Boston, Massachusetts, United States
• 6: S. Laha , J. H. Patel , R. K. Iyer, Accurate Low-Cost Methods for Performance Evaluation of Cache Memory Systems, IEEE Transactions on Computers, v.37 n.11, p.1325-1336, November 1988 [doi>10.1109/12.8699]
• 7: LIN YI-BING, J.-L. BAER AND E. D. LAZOWSKA. Tailoring a parallel trace-driven simulation technique to specific multiprocessor cache coherence protocols. Tech. Rep. TR 88-03-02, University of Washirtgton, Mar. 1988.
• 8: ~IATTSON,R., GECSEI,J., SLUTZ,D. AND I.TRAIGER. Evaluation techniques for storage hierarchies. IBM Systems Journal 9, 2 (1970), 78-117.
• 9: PUZAK, THO.~IAS R. Cache-Memory Design. Ph.D. Dissertation, University of Massachusetts, 1985.
• 10: A. D. Samples, Mache: no-loss trace compaction, Proceedings of the 1989 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.89-97, May 23-26, 1989, Oakland, California, United States
• 11: R. L. Sites , A. Agarwal, Multiprocessor cache analysis using ATUM, Proceedings of the 15th Annual International Symposium on Computer architecture, p.186-195, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 12: SMITrl, A. J. Two methods for the efficient analysis of memory address trace data. IEEE Transaction on Software Engineering 3, 1 (Jan. 1977), 94-101.
• 13: P. Sweazey , A. J. Smith, A class of compatible cache consistency protocols and their support by the IEEE futurebus, Proceedings of the 13th annual international symposium on Computer architecture, p.414-423, June 02-05, 1986, Tokyo, Japan
• 14: James G. Thompson , Alan Jay Smith, Efficient (stack) algorithms for analysis of write-back and sector memories, ACM Transactions on Computer Systems (TOCS), v.7 n.1, p.78-117, Feb. 1989 [doi>10.1145/58564.59296]
• 15: James Gordon Thompson , Alan Jay Smith, Efficient analysis of caching systems, 1987
• 16: TP.AIGER, I.L. AND D.R. SLUTZ. One-pass technique for the evaluation of memory hierarchies. Tech. Rep. RJ 892: IBSI Research, July 1971.
• 17: Wen-Hann Wang , Jean-Loup Baer, Multilevel cache hierarchies, 1989

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

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: Performance attributes

  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Tracing

General Terms:
Algorithms, Reliability, Theory