Code transformation strategies for extensible embedded processors

ABSTRACT

Embedded application requirements, including high performance, low power consumption and fast time to market, are uncommon in the broader domain of general purpose applications. In order to satisfy these demands, chip manufacturers often provide developers with the possibility to define application-specific Instruction Set Extensions (ISEs). Many techniques have been proposed that automatically identify the most beneficial ISEs from source code, so that compilers can identify the 'best' instruction set for the underlying machine. However, can we simply retrofit these techniques into a traditional compiler, or does ISE identification demand different tuning of the heuristics utilized throughout the optimization pipeline? In this paper, we show why compilers should sometimes make different decisions when targeting customized processors, and we show how traditional ISE identification techniques can improve significantly if the code is properly transformed in order to expose more beneficial extensions. The proposed approach was validated using the SimpleScalar simulator for the ARM processor, augmented with the possibility to define additional instructions.Using benchmarks taken from the MiBench suite,we show that the proposed transformations improve state of the art ISE identi cation techniques by 55% on average and 4x maximum.

REFERENCES

• 1: T. R. Halfhill, "EEMBC releases rst benchmarks," Microprocessor Report 1 May 2000.
• 2: L. Pozzi, K. Atasu, and P. Ienne, "Optimal and approximate algorithms for the extension of embedded processor instruction sets," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems vol. CAD-25, no. 7, pp. 1209--29, July 2006.
• 3: Kubilay Atasu , Laura Pozzi , Paolo Ienne, Automatic application-specific instruction-set extensions under microarchitectural constraints, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775897]
• 4: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 5: Partha Biswas , Nikil Dutt , Paolo Ienne , Laura Pozzi, Automatic identification of application-specific functional units with architecturally visible storage, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 6: David Goodwin , Darin Petkov, Automatic generation of application specific processors, 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.951730]
• 7: 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]
• 8: Monica S. Lam , Robert P. Wilson, Limits of control flow on parallelism, Proceedings of the 19th annual international symposium on Computer architecture, p.46-57, May 19-21, 1992, Queensland, Australia
• 9: Scott A. Mahlke , David C. Lin , William Y. Chen , Richard E. Hank , Roger A. Bringmann, Effective compiler support for predicated execution using the hyperblock, Proceedings of the 25th annual international symposium on Microarchitecture, p.45-54, December 01-04, 1992, Portland, Oregon, United States
• 10: R. Kastner , A. Kaplan , S. Ogrenci Memik , E. Bozorgzadeh, Instruction generation for hybrid reconfigurable systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.4, p.605-627, October 2002 [doi>10.1145/605440.605446]
• 11: Pan Yu , Tulika Mitra, Scalable custom instructions identification for instruction-set extensible processors, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA [doi>10.1145/1023833.1023844]
• 12: Nathan T. Clark , Hongtao Zhong , Scott A. Mahlke, Automated Custom Instruction Generation for Domain-Specific Processor Acceleration, IEEE Transactions on Computers, v.54 n.10, p.1258-1270, October 2005 [doi>10.1109/TC.2005.156]
• 13: Timothy J. Callahan , John Wawrzynek, Instruction-Level Parallelism for Reconfigurable Computing, Proceedings of the 8th International Workshop on Field-Programmable Logic and Applications, From FPGAs to Computing Paradigm, p.248-257, August 31-September 03, 1998
• 14: Nathan Clark , Jason Blome , Michael Chu , Scott Mahlke , Stuart Biles , Krisztian Flautner, An Architecture Framework for Transparent Instruction Set Customization in Embedded Processors, Proceedings of the 32nd Annual International Symposium on Computer Architecture, p.272-283, June 04-08, 2005
• 15: T. R. Halfhill, "Tensilica's software makes hardware," Microprocessor Report 23 June 2003.
• 16: ___, "ARC Cores encourages "plug-ins"," Microprocessor Report 19 June 2000.
• 17: Keith D. Cooper , Alexander Grosul , Timothy J. Harvey , Steven Reeves , Devika Subramanian , Linda Torczon , Todd Waterman, ACME: adaptive compilation made efficient, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 18: Prasad A. Kulkarni , David B. Whalley , Gary S. Tyson , Jack W. Davidson, In search of near-optimal optimization phase orderings, Proceedings of the 2006 ACM SIGPLAN/SIGBED conference on Language, compilers and tool support for embedded systems, June 14-16, 2006, Ottawa, Ontario, Canada

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Algorithms, Design, Performance

Keywords:
ASIPs, compilers, customizable processors, instruction-set extensions