Reducing pressure in bounded DBT code caches

ABSTRACT

Dynamic binary translators (DBT) have recently attracted much attention for embedded systems. The effective implementation of DBT in these systems is challenging due to tight constraints on memory and performance. A DBT uses a software-managed code cache to hold blocks of translated code. To minimize overhead, the code cache is usually large so blocks are translated once and never discarded. However, an embedded system may lack the resources for a large code cache. This constraint leads to significant slowdowns due to the retranslation of blocks prematurely discarded from a small code cache. This paper addresses the problem and shows how to impose a tight size bound on the code cache without performance loss. We show that about 70% of the code cache is consumed by instructions that the DBT introduces for its own purposes. Based on this observation, we propose novel techniques that reduce the amount of space required by DBT-injected code, leaving more room for actual application code and improving the miss ratio. We experimentally demonstrate that a bounded code cache can have performance on-par with an unbounded one.

REFERENCES

• 1: Todd Austin , Eric Larson , Dan Ernst, SimpleScalar: An Infrastructure for Computer System Modeling, Computer, v.35 n.2, p.59-67, February 2002 [doi>10.1109/2.982917]
• 2: Jose Baiocchi , Bruce R. Childers , Jack W. Davidson , Jason D. Hiser , Jonathan Misurda, Fragment cache management for dynamic binary translators in embedded systems with scratchpad, Proceedings of the 2007 international conference on Compilers, architecture, and synthesis for embedded systems, September 30-October 03, 2007, Salzburg, Austria [doi>10.1145/1289881.1289898]
• 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: Derek Bruening , Saman Amarasinghe, Maintaining Consistency and Bounding Capacity of Software Code Caches, Proceedings of the international symposium on Code generation and optimization, p.74-85, March 20-23, 2005 [doi>10.1109/CGO.2005.19]
• 5: 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
• 6: A. Guha, K. Hazelwood, and M. L. Soffa. Reducing exit stub memory consumption in code caches. In Int'l. Conf. on High Performance Embedded Architectures and Compilers (HiPEAC), 2007.
• 7: A. Guha, K. Hazelwood, and M. L. Soffa. Code lifetime-based memory reduction for virtual execution environments. In Workshop on Optimizations for DSP and Embedded Systems, 2008.
• 8: M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , R. B. Brown, MiBench: A free, commercially representative embedded benchmark suite, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
• 9: 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
• 10: Kim Hazelwood , Michael D. Smith, Managing bounded code caches in dynamic binary optimization systems, ACM Transactions on Architecture and Code Optimization (TACO), v.3 n.3, p.263-294, September 2006 [doi>10.1145/1162690.1162692]
• 11: Jason D. Hiser , Daniel Williams , Adrian Filipi , Jack W. Davidson , Bruce R. Childers, Evaluating fragment construction policies for SDT systems, Proceedings of the 2nd international conference on Virtual execution environments, June 14-16, 2006, Ottawa, Ontario, Canada [doi>10.1145/1134760.1134778]
• 12: Jason D. Hiser , Daniel Williams , Wei Hu , Jack W. Davidson , Jason Mars , Bruce R. Childers, Evaluating Indirect Branch Handling Mechanisms in Software Dynamic Translation Systems, Proceedings of the International Symposium on Code Generation and Optimization, p.61-73, March 11-14, 2007 [doi>10.1109/CGO.2007.10]
• 13: Intel Corporation. Intel PXA27x Processor Family Developer's Manual, 2006.
• 14: Vladimir Kiriansky , Derek Bruening , Saman P. Amarasinghe, Secure Execution via Program Shepherding, Proceedings of the 11th USENIX Security Symposium, p.191-206, August 05-09, 2002
• 15: Jason E. Miller , Anant Agarwal, Software-based instruction caching for embedded processors, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 16: Kevin Scott , Jack Davidson, Safe Virtual Execution Using Software Dynamic Translation, Proceedings of the 18th Annual Computer Security Applications Conference, p.209, December 09-13, 2002
• 17: 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
• 18: Qiang Wu , Margaret Martonosi , Douglas W. Clark , V. J. Reddi , Dan Connors , Youfeng Wu , Jin Lee , David Brooks, A Dynamic Compilation Framework for Controlling Microprocessor Energy and Performance, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.271-282, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.7]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation; Compilers; Run-time environments; Interpreters; Optimization; Incremental compilers

General Terms:
Design, Experimentation, Measurement, Performance

Keywords:
code generation, dynamic binary translation, footprint reduction, system-on-chip