Blocking: exploiting spatial locality for trace compaction

ABSTRACT

Trace-driven simulation is a popular method of estimating the performance of cache memories, translation lookaside buffers, and paging schemes. Because the cost of trace-driven simulation is directly proportional to trace length, reducing the number of references in the trace significantly impacts simulation time. This paper concentrates on trace driven simulation for cache miss rate analysis. Previous schemes, such as cache filtering, exploited temporal locality for compressing traces and could yield an order of magnitude reduction in trace length. A technique called blocking and a variant called blocking with temporal data are presented that compress traces by exploiting spatial locality. Experimental results show that blocking filtering combined with cache filtering can reduce trace length by nearly two orders of magnitude while introducing about 10% error in cache miss rate estimates.

REFERENCES

• 1: Anant Agarwal , John Hennessy , Mark Horowitz, Cache performance of operating system and multiprogramming workloads, ACM Transactions on Computer Systems (TOCS), v.6 n.4, p.393-431, Nov. 1988 [doi>10.1145/48012.48037]
• 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: R. L. Mattson, J. Gecsei, D. R. Slutz, and I. L. Traiger. Evaluation Techniques for Storage Hierarchies. IBM Systems Journal, 9(2):78-117, 1970.
• 4: 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]
• 5: Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968 [doi>10.1145/363095.363141]
• 6: Alan Jay Smith. Two Methods for the Efficient Analysis of Memory Address Trace Data. IEEE Transactions on Software Engineering, SE-3(1), January 1977.
• 7: Thomas Roberts Puzak, Analysis of cache replacement-algorithms, 1985
• 8: 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
• 9: J. L. Hodges Jr. and E. L. Lehmann. Basic Concepts of Probability and Statistics. Holden-day, Inc., San Francisco, 1964.
• 10: Rupert G. Miller Jr. Beyond Anova- Basics of Applied Statistics. John Wiley ~nd Sons, inc. New York, 1986.
• 11: A. Agarwal , R. L. Sites , M. Horowitz, ATUM: a new technique for capturing address traces using microcode, Proceedings of the 13th annual international symposium on Computer architecture, p.119-127, June 02-05, 1986, Tokyo, Japan
• 12: Arturo Salz. VTRACE. 1984. Computer Systems L~boratory, Stanford University.
• 13: Minor Huffman. A Spatial Locality B~sed Trace Compaction Method. April 1989. Laboratory for Computer Science, Massachusetts Institute of Technology.
• 14: A. Agarwal , M. Cherian, Adaptive backoff synchronization techniques, Proceedings of the 16th annual international symposium on Computer architecture, p.396-406, April 1989, Jerusalem, Israel

INDEX TERMS

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

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

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

General Terms:
Algorithms, Performance, Reliability