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: A. W. Appel, Simple generational garbage collection and fast allocation, Software—Practice & Experience, v.19 n.2, p.171-183, February 1989 [doi>10.1002/spe.4380190206]
• 2: [2] V. Bala, E. Duesterwald, and S. Banerjia. Transparent dynamic optimization. Technical Report HPL-1999-77, Hewlett Packard, June 1999.
• 3: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.1-12, June 18-21, 2000, Vancouver, British Columbia, Canada
• 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: Derek Bruening , Timothy Garnett , Saman Amarasinghe, An infrastructure for adaptive dynamic optimization, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 6: Pei Cao , Sandy Irani, Cost-aware WWW proxy caching algorithms, Proceedings of the USENIX Symposium on Internet Technologies and Systems on USENIX Symposium on Internet Technologies and Systems, p.18-18, December 08-11, 1997, Monterey, California
• 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: Giuseppe Desoli , Nikolay Mateev , Evelyn Duesterwald , Paolo Faraboschi , Joseph A. Fisher, DELI: a new run-time control point, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 11: Evelyn Duesterwald , Vasanth Bala, Software profiling for hot path prediction: less is more, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.202-211, November 2000, Cambridge, Massachusetts, United States
• 12: Kim Hazelwood , Michael D. Smith, Code Cache Management Schemes for Dynamic Optimizers, Proceedings of the Sixth Annual Workshop on Interaction between Compilers and Computer Architectures, p.102, February 03-03, 2002
• 13: Sandy Irani, Page replacement with multi-size pages and applications to Web caching, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.701-710, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258666]
• 14: Dennis C. Lee , Patrick J. Crowley , Jean-Loup Baer , Thomas E. Anderson , Brian N. Bershad, Execution characteristics of desktop applications on Windows NT, Proceedings of the 25th annual international symposium on Computer architecture, p.27-38, June 27-July 02, 1998, Barcelona, Spain
• 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: K. Scott , N. Kumar , S. Velusamy , B. Childers , J. W. Davidson , M. L. Soffa, Retargetable and reconfigurable software dynamic translation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 17: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, ACM SIGPLAN Notices, v.19 n.5, p.157-167, May 1984

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Design studies

General Terms:
Measurement, Performance