Evaluating fragment construction policies for SDT systems

ABSTRACT

Software Dynamic Translation (SDT) systems have been used for program instrumentation, dynamic optimization, security policy enforcement, intrusion detection, and many other uses. To be widely applicable, the overhead (runtime, memory usage, and power consumption) should be as low as possible. For instance, if an SDT system is protecting a web server against possible attacks, but causes 30% slowdown, a company may need 30% more machines to handle the web traffic they expect. Consequently, the causes of SDT overhead should be studied rigorously. This work evaluates many alternative policies for the creation of fragments within the Strata SDT framework. In particular, we examine the effects of ending translation at conditional branches; ending translation at unconditional branches; whether to use partial inlining for call instructions; whether to build the target of calls immediately or lazily; whether to align branch targets; and how to place code to transition back to the dynamic translator. We find that effective translation strategies are vital to program performance, improving performance from as much as 28% overhead, to as little as 3% overhead on average for the SPEC CPU2000 benchmark suite. We further demonstrate that these translation strategies are effective across several platforms, including Sun SPARC UltraSparc IIi, AMD Athlon Opteron, and Intel Pentium IV processors.

REFERENCES

• 1: BALA, V., DUESTERWALD, E., AND BANERJIA, S. Dynamo: A transparent dynamic optimization system. In PLDI '00: Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (New York, NY, USA, June 2000), ACM Press, pp. 1--12.
• 2: BROWNE, S., DONGARRA, J., GARNER, N., LONDON, K., AND MUCCI, P. A scalable cross-platform infrastructure for application performance tuning using hardware counters. In Supercomputing '00: Proceedings of the 2000 ACM/IEEE Conference on Supercomputing (CDROM) (Washington, DC, USA, 2000), IEEE Computer Society, p. 42.
• 3: BRUENING, D., DUESTERWALD, E., AND AMARASINGHE, S. Design and implementation of a dynamic optimization framework for windows. In Proceedings of the ACM Workshop on Feedback-Directed and Dynamic Optimization FDDO-4 (December 2001).
• 4: CHEN, W.-K., LERNER, S., CHAIKEN, R., AND GILLIES, D. Mojo: A dynamic optimization system. In Proceedings of the ACM Workshop on Feedback-Directed and Dynamic Optimization FDDO-3 (December 2000).
• 5: CHERNOFF, A., HERDEG, M., HOOKWAY, R., REEVE, C., RUBIN, N., TYE, T., YADAVALLI, S. B., AND YATES, J. FX!32: A profile-directed binary translator. IEEE Micro 18, 2 (Mar. 1998), 56--64. Presented at Hot Chips IX, Stanford University, Stanford, California, August 24-26, 1997.
• 6: CMELIK, B., AND KEPPEL, D. Shade: A fast instruction-set simulator for execution profiling. In SIGMETRICS '94: Proceedings of the 1994 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems (New York, NY, USA, May 1994), ACM Press, pp. 128--137.
• 7: DITZEL, D. R. Transmeta's Crusoe: Cool chips for mobile computing. In Hot Chips 12: Stanford University, Stanford, California, August 13-15, 2000 (1109 Spring Street, Suite 300, Silver Spring, MD 20910, USA, 2000), IEEE, Ed., IEEE Computer Society Press.
• 8: DUESTERWALD, E., AND BALA, V. Software profiling for hot path prediction: less is more. In ASPLOS-IX: Proceedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems (New York, NY, USA, 2000), ACM Press, pp. 202--211.
• 9: EBCIOGLU, K., AND ALTMAN, E. DAISY: Dynamic compilation for 100% architectural compatibility. In ISCA '97: Proceedings of the 24th Annual International Symposium on Computer architecture (New York, NY, USA, 1997), ACM Press, pp. 26--37.
• 10: HINIKER, D., HAZELWOOD, K., AND SMITH, M. D. Improving region selection in dynamic optimization systems. In MICRO 38: Proceedings of the 38th Annual IEEE/ACM International Symposium on Microarchitecture (Washington, DC, USA, 2005), IEEE Computer Society, pp. 141--154.
• 11: KIRIANSKY, V., BRUENING, D., AND AMARASINGHE, S. Secure execution via program shepherding. In 11th USENIX Security Symposium (August 2002).
• 12: KUMAR, N., MISURDA, J., CHILDERS, B. R., AND SOFFA, M. L. Instrumentation in software dynamic translators for self-managed systems. In WOSS '04: Proceedings of the 1st ACM SIGSOFT Workshop on Self-managed systems (New York, NY, USA, 2004), ACM Press, pp. 90--94.
• 13: LUK, C.-K., COHN, R., MUTH, R., PATIL, H., KLAUSER, A., LOWNEY, G., WALLACE, S., REDDI, V. J., AND HAZELWOOD, K. Pin: building customized program analysis tools with dynamic instrumentation. In PLDI '05: Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation (New York, NY, USA, 2005), ACM Press, pp. 190--200.
• 14: SCOTT, K., AND DAVIDSON, J. Strata: A software dynamic translation infrastructure. In IEEE Workshop on Binary Translation (September 2001).
• 15: SCOTT, K., AND DAVIDSON, J. W. Safe virtual execution using software dynamic translation. In Proceedings of the 18th Annual Computer Security Applications Conference (Las Vegas, NV, December 2002), pp. 209--218.
• 16: SCOTT, K., KUMAR, N., CHILDERS, B., DAVIDSON, J. W., AND SOFFA, M. L. Overhead reduction techniques for software dynamic translation. In Proceedings of the 18th International Parallel and Distributed Processing Symposium (2004), IEEE Computer Society, p. 200.
• 17: SCOTT, K., KUMAR, N., VELUSAMY, S., CHILDERS, B., DAVIDSON, J. W., AND SOFFA, M. L. Retargetable and reconfigurable software dynamic translation. In CGO '03: Proceedings of the International Symposium on Code Generation and Optimization (Washington, DC, USA, 2003), IEEE Computer Society, pp. 36--47.
• 18: SMITH, J., AND NAIR, R. Virtual Machines: Versatile Platforms for Systems and Processes. Morgan Kaufmann, 2005.
• 19: SRIDHAR, S., SHAPIRO, J. S., AND BUNGALE, P. P. Hdtrans: A low-overhead dynamic translator. In Proceedings of the 2005 Workshop on Binary Instrumentation and Applications (September 2005), IEEE Computer Society.
• 20: SRIVASTAVA, A., EDWARDS, A., AND VO, H. Vulcan: Binary translation in a distributed environment. Technical Report MSR-TR-2001-50, Microsoft Research, Apr. 2001.
• 21: TAMCHES, A., AND MILLER, B. P. Fine-grained dynamic instrumentation of commodity operating system kernels. In Proceedings of the 3rd Symposium on Operating Systans Design and Implementation (OSDI-99) (Berkeley, CA, Feb. 22-25 1999), Usenix Association, pp. 117--130.
• 22: TAMCHES, A., AND MILLER, B. P. Using dynamic kernel instrumentation for kernel and application tuning. The International Journal of High Performance Computing Applications 13, 3 (Fall 1999), 263--276.
• 23: UNG, D., AND CIFUENTES, C. Machine-adaptable dynamic binary translation. In Proceedings of the ACM Workshop on Dynamic Optimization Dynamo '00 (2000).
• 24: WITCHEL, E., AND ROSENBLUM, M. Embra: Fast and flexible machine simulation. In Proceedings of the ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (May 1996), pp. 68--79.
• 25: ZHOU, S., CHILDERS, B. R., AND SOFFA, M. L. Planning for code buffer management in distributed virtual execution environments. In VEE '05: Proceedings of the 1st ACM/USENIX International Conference on Virtual Execution Environments (New York, NY, USA, 2005), ACM Press, pp. 100--109.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.m MISCELLANEOUS

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

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

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance

Keywords:
dynamic translation performance, low overhead, performance, software dynamic translator