Generational Cache Management of Code Traces in Dynamic Optimization Systems

ABSTRACT

A dynamic optimizer is a runtime software system thatgroups a program's instruction sequences into traces, optimizesthose traces, stores the optimized traces in a software-basedcode cache, and then executes the optimized code inthe code cache. To maximize performance, the vast majorityof the program's execution should occur in the codecache and not in the different aspects of the dynamic optimizationsystem. In the past, designers of dynamic optimizershave used the SPEC2000 benchmark suite to justifytheir use of simple code cache management schemes.In this paper, we show that the problem and importance ofcode cache management changes dramatically as we movefrom SPEC2000, with its relatively small number of dynamicallygenerated code traces, to large interactive Windowsapplications. We also propose and evaluate a new cachemanagement algorithm based on generational code cachesthat results in an average miss rate reduction of 18% over aunified cache, which translates into 19% fewer instructionsspent in the dynamic optimizer. The algorithm categorizescode traces based on their expected lifetimes and groupstraces with similar lifetimes together in separate storage areas.Using this algorithm, short-lived code traces can easilybe removed from a code cache without introducing fragmentationand without suffering the performance penaltiesassociated with evicting long-lived code traces.

References

1. {1} A. W. Appel. Simple generational garbage collection and fast allocation. Software Practice and Experience, 19(2):171-183, 1989.
2. {2} V. Bala, E. Duesterwald, and S. Banerjia. Transparent dynamic optimization. Technical Report HPL-1999-77, Hewlett Packard, June 1999.
3. {3} V. Bala, E. Duesterwald, and S. Banerjia. Dynamo: A transparent dynamic optimization system. In ACM Conference on Programming Language Design and Implementation, pages 1-12, 2000.
4. {4} L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker. Web caching and zipf-like distributions: Evidence and implications. In INFOCOM, pages 126-134, 1999.
5. {5} D. Bruening, T. Garnett, and S. Amarasinghe. An infrastructure for adaptive dynamic optimization. In First Annual International Symposium on Code Generation and Optimization , pages 265-275, March 2003.
6. {6} P. Cao and S. Irani. Cost-aware WWW proxy caching algorithms. In Usenix Symposium on Internet Technologies and Systems, Monterey, CA, 1997.
7. {7} J. P. Casmira, D. R. Kaeli, and D. P. Hunter. Tracing and characterization of NT-based system workloads. Digital Technical Journal, 10(1):6-21, December 1998.
8. {8} W.-K. Chen, S. Lerner, R. Chaiken, and D. Gillies. Mojo: A dynamic optimization system. In 4th ACM Workshop on Feedback-Directed and Dynamic Optimization, pages 81- 90, 2000.
9. {9} D. Deaver, R. Gorton, and N. Rubin. Wiggins/redstone: An on-line program specializer. In IEEE Hot Chips XI, 1999.
10. {10} G. Desoli, N. Mateev, E. Duesterwald, P. Faraboschi, and J. A. Fisher. Deli: A new run-time control point. In 35th International Symposium on Microarchitecture, pages 257- 268, 2002.
11. {11} E. Duesterwald and V. Bala. Software profiling for hot path prediction: Less is more. In 12th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 202-211, October 2000.
12. {12} K. Hazelwood and M. D. Smith. Code cache management schemes for dynamic optimizers. In 6th Workshop on Interaction between Compilers and Computer Architectures, pages 102-110, February 2002.
13. {13} S. Irani. Page replacement with multi-size pages and applications to web caching. In 29th ACM Symposium on Theory of Computing, pages 701-710, May 1997.
14. {14} D. C. Lee, P. Crowley, J.-L. Baer, T. E. Anderson, and B. N. Bershad. Execution characteristics of desktop applications in windows NT. In 25th International Symposium on Computer Architecture, pages 27-38, 1998.
15. {15} K. London, J. Dongarra, S. Moore, P. Mucci, K. Seymour, and T. Spencer. End-user tools for application performance analysis using hardware counters. In 14th Conference on Parallel and Distributed Computing Systems, August 2001.
16. {16} K. Scott, N. Kumar, S. Velusamy, B. Childers, J. Davidson, and M. L. Soffa. Reconfigurable and retargetable software dynamic translation. In First Annual International Symposium on Code Generation and Optimization, pages 36-47, March 2003.
17. {17} D. Ungar. Generation scavenging: a non-disruptive high performance storage reclamation algorithm. ACM SIGPLAN Notices, 19(5):157-167, May 1984.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Design

    • Measurement

    • Metrics

    • Performance