An integer linear programming approach for identifying instruction-set extensions

ABSTRACT

This paper presents an Integer Linear Programming (ILP) approach to the instruction-set extension identification problem. An algorithm that iteratively generates and solves a set of ILP problems in order to generate a set of templates is proposed. A selection algorithm that ranks the generated templates based on isomorphism testing and potential evaluation is described. A Trimaran based framework is used to evaluate the quality of the instructions generated by the technique. Speed-up results of up to 7.5 are observed.

REFERENCES

• 1: Cesare Alippi , William Fornaciari , Laura Pozzi , Mariagiovanna Sami, A DAG-based design approach for reconfigurable VLIW processors, Proceedings of the conference on Design, automation and test in Europe, p.57-es, January 1999, Munich, Germany [doi>10.1145/307418.307504]
• 2: Jason Cong , Yiping Fan , Guoling Han , Zhiru Zhang, Application-specific instruction generation for configurable processor architectures, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, February 22-24, 2004, Monterey, California, USA [doi>10.1145/968280.968307]
• 3: Nathan Clark , Hongtao Zhong , Scott Mahlke, Processor Acceleration Through Automated Instruction Set Customization, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.129, December 03-05, 2003
• 4: 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]
• 5: 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]
• 6: R. Niemann, P. Marwedel. An Algorithm for Hardware/Software Partitioning Using Mixed Integer Linear Programming. Design Automation for Embedded Systems, Vol. 2, No. 2, pages 165--193, Mar. 1997
• 7: Nauty Package. http://cs.anu.edu.au/people/bdm/nauty.
• 8: Trimaran: An Infrastructure for Research in Instruction Level Parallelism. http://www.trimaran.org.
• 9: ILOG CPLEX :High-Performance Software for Mathematical Programming and Optimization. http://www.ilog.com/products/cplex/
• 10: R. Zimmermann. Computer Arithmetic: Principles, Architectures, and VLSI Design, Lecture notes, Integrated Systems Laboratory, ETH Zürich, 1997
• 11: Kubilay Atasu , Luca Breveglieri , Marco Macchetti, Efficient AES implementations for ARM based platforms, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.968073]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles

General Terms:
Algorithms, Design, Performance

Keywords:
ASIPs, extensible processors, integer linear, programming