Techniques for the trace-driven simulation of cache performance

ABSTRACT

In contemporary computers, cache memories are interposed between processors and primary memories in order to decrease access time and bus traffic. Because the design of the cache is critical and the factors affecting its performance are complex, trace-driven simulation is widely used and studied. This paper surveys three interesting techniques for the trace-driven simulation of cache designs: stack analysis methodologies that make it possible to obtain performance measures for a wide variety of cache designs from a single run of the simulator, compression algorithms specifically tailored to memory reference traces, and an approach to parallel trace-driven simulation of multiprocessor caches that dramatically reduces the simulation's synchronization and thus its running time.

References

1. Eggers, SJ. (1989). Simulation Analysis of Data Sharing in Shared Memory Multiprocessors. Technical Report 89/50, Computer Science Division, University of California, Berkeley. (Ph.D. Thesis).]]
2. Goodman, J. R. (1987). Cache Memory Optimization to Reduce Processor/Memory Traffic Journal of VLSI and Computer Systems 2,1, pp. 61--86.]]
3. Hill, M. D. (1987). Aspects of Cache Memory and Instruction Buffer Performance. Technical Report 87/381, Computer Science Division, University of California, Berkeley. (Ph.D. Thesis).]]
4. Hill, M. D., and Smith, A. J. (1989). Evaluating Associativity in CPU Caches. IEEE Transactions on Computers, to appear.]]
5. Katz, R., Eggers, S., Wood, D. A., Perkins, C., and Sheldon, R. G. (1985). Implementing a Cache Consistency Protocol. Proc. 12th Annual International Symposium on Computer Architecture, pp. 276--283.]]
6. Lin, Y.-B., Baer, J.-L., and Lazowska, E. D. (1989). Tailoring a Parallel Trace-Driven Simulation Technique to Specific Multiprocessor Cache Coherence Protocols. Proc. 1989 SCS Multiconference on Distributed Simulation.]]
7. Mattson, R. L., Gecsei, J., Slutz, D. R., and Traiger, I. L. (1970). Evaluation Techniques for Storage Hierarchies. IBM Systems Journal 9,2, pp. 78--117.]]
8. McCreight, E. (1984). The Dragon Computer System: An Early Overview. Technical Report, Xerox Palo Alto Research Center.]]
9. Papamarcos, M., and Patel, J. (1984). A Low-Overhead Coherence Solution for Multiprocessors With Private Cache Memories. Proc. 11th Annual International Symposium on Computer Architecture, pp. 348--354.]]
10. Puzak, T. R. (1985). Analysis of Cache Replacement Algorithms. Ph. D. Thesis, University of Massachusetts.]]
11. Samples, A. D. (1989). Mache: No-Loss Trace Compaction. Proc, ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, pp. 89--97.]]
12. Smith, A. J. (1979). Two Methods for the Efficient Analysis of Memory Address Trace Data. IEEE Transactions on Software Engineering SE-3,1, pp. 94--101.]]
13. Sweazey, P., and Smith, A. J. (1986). A Class of Compatible Cache Consistency Protocols and Their Support by the IEEE. Proc. 13th International Symposium on Computer Architecture, pp. 414--423.]]
14. Thacker, C. P., and Stewart, L. C. (1987). Firefly: A Multiprocessor Workstation. Proc. 2nd International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 164--172.]]
15. Thompson, J. G. (1987). Efficient Analysis of Caching Systems. Technical Report 87/374, Computer Science Division, University of California, Berkeley.]]
16. Traiger, I. L., and Slutz, d. R. (1971). One-Pass Techniques for the Evaluation of Memory Hierarchies. Technical Report RJ892, IBM.]]
17. Ziv, J., and Lempel, A. (1977). A Universal Algorithm for Sequential Data Compression. IEEE Transactions on Information Theory 243, 3, pp. 337--343.]]

Index Terms

• Hardware

  • Integrated circuits

    • Semiconductor memory

      • Dynamic memory

• Theory of computation

  • Models of computation

    • Concurrency

      • Parallel computing models

  • Semantics and reasoning

    • Program constructs

      • Functional constructs