Selective code transformation for dual instruction set processors

ABSTRACT

Embedded systems are often constrained in terms of both code size and execution time, because of a limited amount of available memory and real-time nature of applications. A dual instruction set processor, which supports a reduced instruction set (16 bits/instruction), in addition to a full instruction set (32 bits/instruction), allows an opportunity for a tradeoff between these two design criteria. Specifically, while the reduced instruction set can be used to reduce code size by providing smaller instructions, a program compiled into the reduced instruction set typically runs slower than the same program compiled into the full instruction set. Motivated by this observation, we propose a code generation technique that exploits this tradeoff relationship by selectively using the two instruction sets for different sections in the program. The proposed technique, called selective code transformation, not only provides a mechanism to enable a flexible tradeoff between a program's code size and its execution time, but also facilitates program optimization toward enhancing its worst case performance. The results from our experiments show that our proposed technique can be effectively used to fine-tune an application program on a spectrum of code size and execution performance, which, in turn, enables a system-wide optimization on memory space and execution speed involving multiple applications.

REFERENCES

• 1: Advanced RISC Machines Ltd. 1995. ARM7TDMI Data Sheet. Advanced RISC Machines Ltd.
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: ARC Cores (http://www.arc.com). The ARCtangent-A5 Processor.
• 4: ARM Limited. ARM Developer Suite Developer Guide.
• 5: ARM Linux Project. http://www.arm.linux.org.uk.
• 6: Thomas Ball , James R. Larus, Efficient path profiling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.46-57, December 02-04, 1996, Paris, France
• 7: Manuel E. Benitez , Jack W. Davidson, Target-specific Global Code Improvement: Principles and Applications, University of Virginia, Charlottesville, VA, 1994
• 8: Jack W. Davidson , Christopher W. Fraser, Code selection through object code optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.4, p.505-526, Oct. 1984 [doi>10.1145/1780.1783]
• 9: Davidson, J. W. and Whalley, D. B. 1991. A design environment for addressing architecture and compiler interactions. Microprocessors and Microsystems 15, 9 (Nov.), 459--472.
• 10: Steve B. Furber, ARM System Architecture, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 11: Liam Goudge , Simon Segars, Thumb: Reducing the Cost of 32-bit RISC Performance in Portable and Consumer Applications, Proceedings of the 41st IEEE International Computer Conference, p.176, February 25-28, 1996
• 12: 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 on, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
• 13: A. Halambi , A. Shrivastava , P. Biswas , N. Dutt , A. Nicolau, An Efficient Compiler Technique for Code Size Reduction Using Reduced Bit-Width ISAs, Proceedings of the conference on Design, automation and test in Europe, p.402, March 04-08, 2002
• 14: Kirner, R. 2003. Extending optimising compilation to support worst-case execution time analysis. Ph.D. thesis, Vienna University of Technology.
• 15: Kissel, K. 1997. MIPS16: High-density MIPS for the embedded market. Tech. rep., Silicon Graphics MIPS Group.
• 16: Arvind Krishnaswamy , Rajiv Gupta, Profile guided selection of ARM and thumb instructions, Proceedings of the joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systems, June 19-21, 2002, Berlin, Germany
• 17: Arvind Krishnaswamy , Rajiv Gupta, Enhancing the performance of 16-bit code using augmenting instructions, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 18: Arvind Krishnaswamy , Rajiv Gupta, Mixed-width instruction sets, Communications of the ACM, v.46 n.8, August 2003 [doi>10.1145/859670.859697]
• 19: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 20: Lee, S., Lee, J., Min, S. L., Hiser, J., and Davidson, J. W. 2003. Code generation for a dual instruction set processor based on selective code transformation. In Proceedings of the 7th International Workshop on Software and Compilers for Embedded Systems (SCOPES). Vienna. 33--48.
• 21: Lee, S., Lee, J., Park, C. Y., and Min, S. L. 2004. A flexible tradeoff between code size and WCET using a dual instruction set processor. In Proceedings of the 8th International Workshop on Software and Compilers for Embedded Systems (SCOPES). Amsterdam. 244--258.
• 22: Sung-Soo Lim , Young Hyun Bae , Gyu Tae Jang , Byung-Do Rhee , Sang Lyul Min , Chang Yun Park , Heonshik Shin , Kunsoo Park , Soo-Mook Moon , Chong Sang Kim, An Accurate Worst Case Timing Analysis for RISC Processors, IEEE Transactions on Software Engineering, v.21 n.7, p.593-604, July 1995 [doi>10.1109/32.392980]
• 23: Sung-Soo Lim , Jihong Kim , Sang Lyul Min, A Worst Case Timing Analysis Technique for Optimized Programs, Proceedings of the 5th International Conference on Real-Time Computing Systems and Applications, p.151, October 27-29, 1998
• 24: Park, C. Y. and Shaw, A. C. 1990. Experiments with a program timing tool based on source-level timing schema. In Proceedings of the 11th Real-Time Systems Symposium (RTSS). 72--81.
• 25: Insik Shin , Insup Lee , Sang Lyul Min, Embedded System Design Framework for Minimizing Code Size and Guaranteeing Real-Time Requirements, Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02), p.201, December 03-05, 2002
• 26: Aviral Shrivastava , Nikil Dutt, Energy efficient code generation exploiting reduced bit-width instruction set architectures (rISA), Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, January 27-30, 2004, Yokohama, Japan
• 27: SNU Real-Time Benchmark Suite. http://archi.snu.ac.kr/realtime/benchmark.
• 28: Tamches, A. and Miller, B. P. 2001. Dynamic kernel code optimization. In Proceedings of the 3rd Workshop on Binary Translation. Barcelona.
• 29: Tuning the WCET of Embedded Applications, Proceedings of the 10th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'04), p.472, May 25-28, 2004

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.0 General

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Code generation

General Terms:
Design, Performance

Keywords:
Dual instruction set processors, mixed-width instruction set architecture, reduced bid-width instruction set architecture