Enhanced code density of embedded CISC processors with echo technology

ABSTRACT

Code density is an important issue in memory constrained systems. Some RISC processor, e.g. the THUMB extension in the ARM processor, supports aggressive code size reduction even at the cost of significant performance loss. In this paper, we develop an algorithm that utilizes a set of novel variable length Echo instructions and evaluate its effectiveness for IA32 binaries. Our experiments show that IA32 processor equipped with Echo instructions is capable of achieving a similar code density as the THUMB extension in the ARM instruction set with significantly lower performance penalty.

REFERENCES

• 1: ARM website, http://www.arm.com/products/CPUs/ archi-thumb2. html, 2004
• 2: P. Brisk and M. Sarrafzadeh, "Framework and Design Methodology of a Compiler that Compresses Code using Echo Instructions," ODES-2, in conjunction with CGO04, March 21, 2004
• 3: Keith D. Cooper , Nathaniel McIntosh, Enhanced code compression for embedded RISC processors, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.139-149, May 01-04, 1999, Atlanta, Georgia, United States
• 4: GCC Code-Size Benchmark Environment (CSiBE), http://sed.inf.u-szeged.hu/csibe/, 2004
• 5: Saumya K. Debray , William Evans , Robert Muth , Bjorn De Sutter, Compiler techniques for code compaction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.378-415, March 2000 [doi>10.1145/349214.349233]
• 6: Christopher W. Fraser , Eugene W. Myers , Alan L. Wendt, Analyzing and compressing assembly code, ACM SIGPLAN Notices, v.19 n.6, p.117-121, June 1984
• 7: C. Fraser. "An instruction for direct interpretation of LZ77-compressed programs," Microsoft Technical Report MSR-TR-2002-90. ftp://ftp.research.microsoft.com/pub/tr/tr-2002-90.pdf.
• 8: Embedded Intel® Architecture at http://www.intel.com/products/embedded/index.htm
• 9: 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
• 10: K. Kunchithapadam and J. Larus. "Using lightweight procedures to improve instruction cache performance," CS-TR-99-1390, University of Wisconsin, 1999.
• 11: N. J. Larsson, Extended application of suffix trees to data compression, Proceedings of the Conference on Data Compression, p.190, March 31-April 03, 1996
• 12: Jeremy Lau , Stefan Schoenmackers , Timothy Sherwood , Brad Calder, Reducing code size with echo instructions, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951724]
• 13: Stan Yi-Huang Liao , Srinivas Devadas, Code generation and optimization for embedded digital signal processors, 1996
• 14: C.G. Nevill-Manning, and I.H. Witten, "Identifying Hierarchical Structure in Sequences: A linear-time algorithm," Journal of Artificial Intelligence Research, 7, 67--82. (1997)
• 15: Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
• 16: M. Nanja and J. D. Munter, "The Effects of Compiler Optimizations and Mixed Mode Code on Application Performance, Memory Footprint, Power, and Energy Consumption for Embedded Systems," Submitted to CTCES04.
• 17: National Geode x86 "appliance-on-chip" SOCs, http: //www.linuxdevices.com/products/PD6094486551.html
• 18: E. Ukkonen, "On-line construction of suffix trees," Algorithmica, Sept 1995.
• 19: Via Embedded Platforms at http://www.viaembedded.com/index.jsp.
• 20: J. Ziv and A Lempel, "A Universal Algorithm for Sequential Data Compression," IEEE Transaction on Information Theory, 23 (3), p337--343, May 1977.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.1 Single Data Stream Architectures
          Subjects: RISC/CISC, VLIW architectures

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
CISC processors, code density, compression, echo technology, embedded systems