Efficient instruction encoding for automatic instruction set design of configurable ASIPs

ABSTRACT

Application-specific instructions can significantly improve the performance, energy, and code size of configurable processors. A common approach used in the design of such instructions is to convert application-specific operation patterns into new complex instructions. However, processors with a fixed instruction bitwidth cannot accommodate all the potentially interesting operation patterns, due to the limited code space afforded by the fixed instruction bitwidth. We present a novel instruction set synthesis technique that employs an efficient instruction encoding method to achieve maximal performance improvement. We build a library of complex instructions with various encoding alternatives and select the best set of complex instructions while satisfying the instruction bitwidth constraint. We formulate the problem using integer linear programming and also present an effective heuristic algorithm. Experimental results using our technique generate instruction sets that show improvements of up to 38% over the native instruction set for several realistic benchmark applications running on a typical embedded RISC processor.

REFERENCES

• 1: Ricardo E. Gonzalez, Xtensa: A Configurable and Extensible Processor, IEEE Micro, v.20 n.2, p.60-70, March 2000 [doi>10.1109/40.848473]
• 2: Tensilica Inc., http://www.tensilica.com/.
• 3: ARC Cores Inc., http://www.arc.com/.
• 4: A. Cataldo, "Compiler that converts C-code to processor gates advances," EE Times, Oct. 23, 2001, http://www.eet.com/story/OEG20011023S0028.
• 5: Y. Zhao et al., "Matching architecture to application via configurable processors," In Proc. ICCD 2001.
• 6: Marnix Arnold , Henk Corporaal, Designing domain-specific processors, Proceedings of the ninth international symposium on Hardware/software codesign, p.61-66, April 2001, Copenhagen, Denmark [doi>10.1145/371636.371677]
• 7: A. Alomary et al., "PEAS-I: A hardware/software co-design system for ASIPs," In Proc. EURO-DAC 1993.
• 8: Johan Van Praet , Gert Goossens , Dirk Lanneer , Hugo De Man, Instruction set definition and instruction selection for ASIPs, Proceedings of the 7th international symposium on High-level synthesis, p.11-16, May 18-20, 1994, Niagra-on-the-Lake, Ontario, Canada
• 9: Hoon Choi , Jong-Sun Kim , Chi-Won Yoon , In-Cheol Park , Seung Ho Hwang , Chong-Min Kyung, Synthesis of Application Specific Instructions for Embedded DSP Software, IEEE Transactions on Computers, v.48 n.6, p.603-614, June 1999 [doi>10.1109/12.773797]
• 10: I.-J. Huang and A. Despain, "Synthesis of application specific instruction sets," IEEE Trans. on CAD, 1995.
• 11: D. Gajski, High-Level Synthesis, Kluwer Academic Publishers, 1992.
• 12: SH-3/SH-3E/SH3-DSP Programming Manual, Hitachi, Ltd., 2000, available at http://www.hitachi-eu.com/hel/ecg/products/micro/pdf/sh7700p.pdf.
• 13: J. Lee et al., "Automatic instruction set design through efficient instruction encoding for application-specific processors," Tech. Report, #02--23, CECS, UC Irvine.
• 14: EXPRESS Retargetable Compiler, Univ. of California, Irvine, Project website http://www.cecs.uci.edu/~aces/.
• 15: lp_solve, Version 3.2, available at ftp://ftp.ics.ele.tue.nl/pub/lp_solve/.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.3 COMPUTERS AND EDUCATION
      K.3.1 Computer Uses in Education
          Subjects: Computer-assisted instruction (CAI)

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

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

General Terms:
Design, Experimentation, Theory