Hybrid-compiled simulation: An efficient technique for instruction-set architecture simulation

ABSTRACT

Instruction-set simulators are critical tools for the exploration and validation of new processor architectures. Due to the increasing complexity of architectures and time-to-market pressure, performance is the most important feature of an instruction-set simulator. Interpretive simulators are flexible but slow, whereas compiled simulators deliver speed at the cost of flexibility and compilation overhead. This article presents a hybrid instruction-set-compiled simulation (HISCS) technique for generation of fast instruction-set simulators that combines the benefit of both compiled and interpretive simulation. This article makes two important contributions: (i) it improves the interpretive simulation performance by applying compiled simulation at the instruction level using a novel template-customization technique to generate optimized decoded instructions during compile time; and (ii) it reduces the compile-time overhead by combining the benefits of both static and dynamic-compiled simulation. Our experimental results using two contemporary processors (ARM7 and SPARC) demonstrate an order-of-magnitude reduction in compilation time as well as a 70% performance improvement, on average, over the best-known published result in instruction-set simulation.

REFERENCES

• 1: Ronan Amicel , Francois Bodin, Mastering Startup Costs in Assembler-Based Compiled Instruction-Set Simulation, Proceedings of the Sixth Annual Workshop on Interaction between Compilers and Computer Architectures, p.39, February 03-03, 2002
• 2: ARM7, The ARM7 User Manual. http://www.arm.com
• 3: James R. Bell, Threaded code, Communications of the ACM, v.16 n.6, p.370-372, June 1973 [doi>10.1145/362248.362270]
• 4: Gunnar Braun , Andreas Hoffmann , Achim Nohl , Heinrich Meyr, Using static scheduling techniques for the retargeting of high speed, compiled simulators for embedded processors from an abstract machine description, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500014]
• 5: Martin Burtscher , Ilya Ganusov, Automatic Synthesis of High-Speed Processor Simulators, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.55-66, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.7]
• 6: Bob Cmelik , David Keppel, Shade: a fast instruction-set simulator for execution profiling, ACM SIGMETRICS Performance Evaluation Review, v.22 n.1, p.128-137, May 1994
• 7: Frank Engel , Johannes Nührenberg , Gerhard P. Fettweis, A generic tool set for application specific processor architectures, Proceedings of the eighth international workshop on Hardware/software codesign, p.126-130, May 2000, San Diego, California, United States [doi>10.1145/334012.334036]
• 8: Futamura, Y. 1971. Partial evaluation of computation process-an approach to a compiler-compiler. Syst. Comput. Controls 2, 45--50.
• 9: George Hadjiyiannis , Silvina Hanono , Srinivas Devadas, ISDL: an instruction set description language for retargetability, Proceedings of the 34th annual conference on Design automation, p.299-302, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266108]
• 10: Ashok Halambi , Peter Grun , Vijay Ganesh , Asheesh Khare , Nikil Dutt , Alex Nicolau, EXPRESSION: a language for architecture exploration through compiler/simulator retargetability, Proceedings of the conference on Design, automation and test in Europe, p.100-es, January 1999, Munich, Germany [doi>10.1145/307418.307549]
• 11: Mark R. Hartoog , James A. Rowson , Prakash D. Reddy , Soumya Desai , Douglas D. Dunlop , Edwin A. Harcourt , Neeti Khullar, Generation of software tools from processor descriptions for hardware/software codesign, Proceedings of the 34th annual conference on Design automation, p.303-306, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266110]
• 12: Leupers, R., Elste, J., and Landwehr, B. 1999. Generation of Interpretive and Compiled Instruction Set Simulators. In Proceedings of the Asia South Pacific Design Automation Conference (ASP-DAC'99). IEEE, Los Alamitos, CA.
• 13: Peter S. Magnusson , Magnus Christensson , Jesper Eskilson , Daniel Forsgren , Gustav Hållberg , Johan Högberg , Fredrik Larsson , Andreas Moestedt , Bengt Werner, Simics: A Full System Simulation Platform, Computer, v.35 n.2, p.50-58, February 2002 [doi>10.1109/2.982916]
• 14: Achim Nohl , Gunnar Braun , Oliver Schliebusch , Rainer Leupers , Heinrich Meyr , Andreas Hoffmann, A universal technique for fast and flexible instruction-set architecture simulation, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513927]
• 15: Soner Önder , Rajiv Gupta, Automatic Generation of Microarchitecture Simulators, Proceedings of the 1998 International Conference on Computer Languages, p.80, May 14-16, 1998
• 16: Stefan Pees , Andreas Hoffmann , Heinrich Meyr, Retargeting of compiled simulators for digital signal processors using a machine description language, Proceedings of the conference on Design, automation and test in Europe, p.669-673, March 27-30, 2000, Paris, France [doi>10.1145/343647.343888]
• 17: Wei Qin , Sharad Malik, Automated synthesis of efficient binary decoders for retargetable software toolkits, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776027]
• 18: Norman Ramsey , Mary F. Fernández, Specifying representations of machine instructions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.3, p.492-524, May 1997 [doi>10.1145/256167.256225]
• 19: Mehrdad Reshadi , Prabhat Mishra , Nikil Dutt, Instruction set compiled simulation: a technique for fast and flexible instruction set simulation, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776026]
• 20: Mehrdad Reshadi , Nikil Dutt, Reducing Compilation Time Overhead in Compiled Simulators, Proceedings of the 21st International Conference on Computer Design, p.151, October 13-15, 2003
• 21: Mehrdad Reshadi , Nikil Dutt , Prabhat Mishra, A retargetable framework for instruction-set architecture simulation, ACM Transactions on Embedded Computing Systems (TECS), v.5 n.2, p.431-452, May 2006 [doi>10.1145/1151074.1151083]
• 22: Eric Schnarr , James R. Larus, Fast out-of-order processor simulation using memoization, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.283-294, October 02-07, 1998, San Jose, California, United States
• 23: Eric C. Schnarr , Mark D. Hill , James R. Larus, Facile: a language and compiler for high-performance processor simulators, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.321-331, June 2001, Snowbird, Utah, United States
• 24: Simplescalar Home. http://www.simplescalar.com.
• 25: SPARC. Version 7 Instruction set manual: http://www.sun.com
• 26: Emmett Witchel , Mendel Rosenblum, Embra: fast and flexible machine simulation, Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.68-79, May 23-26, 1996, Philadelphia, Pennsylvania, United States
• 27: Jianwen Zhu , Daniel D. Gajski, A retargetable, ultra-fast instruction set simulator, Proceedings of the conference on Design, automation and test in Europe, p.62-es, January 1999, Munich, Germany [doi>10.1145/307418.307509]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.7 Simulation Support Systems

General Terms:
Design, Performance

Keywords:
Compiled simulation, instruction set architecture, interpretive simulation, partial evaluation