Scalable custom instructions identification for instruction-set extensible processors

ABSTRACT

Extensible processors allow addition of application-specific custom instructions to the core instruction set architecture. However, it is computationally expensive to automatically select the optimal set of custom instructions. Therefore, heuristic techniques are often employed to quickly search the design space. In this paper, we present an efficient algorithm for exact enumeration of all possible candidate instructions given the dataflow graph (DFG) corresponding to a code fragment. Even though this is similar to the "subgraph enumeration" problem (which is exponential), we find that most subgraphs are not feasible candidates for various reasons. In fact, the number of candidates is quite small compared to the size of the DFG. Compared to previous approaches, our technique achieves orders of magnitude speedup in enumerating these candidate custom instructions for very large DFGs.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 2: Altera. Nios embedded processor system development. http://www.altera.com/products/ip/processors/nios/nio-index.html.
• 3: 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]
• 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: David Avis , Komei Fukuda, Reverse search for enumeration, Discrete Applied Mathematics, v.65 n.1-3, p.21-46, March 7, 1996 [doi>10.1016/0166-218X(95)00026-N]
• 6: Massimo Baleani , Frank Gennari , Yunjian Jiang , Yatish Patel , Robert K. Brayton , Alberto Sangiovanni-Vincentelli, HW/SW partitioning and code generation of embedded control applications on a reconfigurable architecture platform, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado [doi>10.1145/774789.774820]
• 7: Philip Brisk , Adam Kaplan , Ryan Kastner , Majid Sarrafzadeh, Instruction generation and regularity extraction for reconfigurable processors, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08-11, 2002, Grenoble, France [doi>10.1145/581630.581672]
• 8: D. Burger, T. Austin, and S. Bennett. Evaluating Future Microprocessors: The SimpleScalar Toolset. Technical Report CS-TR96-1308, Univ. of Wisconsin - Madison, 1996. Available from http://www.simplescalar.com.
• 9: 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
• 10: 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]
• 11: Paolo Faraboschi , Geoffrey Brown , Joseph A. Fisher , Giuseppe Desoli , Fred Homewood, Lx: a technology platform for customizable VLIW embedded processing, ACM SIGARCH Computer Architecture News, v.28 n.2, p.203-213, May 2000
• 12: 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]
• 13: M. R. Guthausch et al. Mibench: A free, commercially representative embedded benchmark suite. In IEEE 4th Annual Workshop on Workload Characterization, 2001. Benchmark available from http://www.eecs.umich.edu/mibench/.
• 14: Jong-eun Lee , Kiyoung Choi , Nikil Dutt, Efficient instruction encoding for automatic instruction set design of configurable ASIPs, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.649-654, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774668]
• 15: Surendranath Talla , Krishna V. Palem, Adaptive explicitly parallel instruction computing, 2001
• 16: L. Pozzi, M. Vuletic, and P. Ienne. Automatic topology-based identification of instruction-set extensions for embedded processor. Technical Report 01/377, NSwiss Federal Institute of Technology Lausanne (EPFL), 2001.
• 17: Pan Yu , Tulika Mitra, Characterizing embedded applications for instruction-set extensible processors, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996764]
• 18: Zhi Alex Ye , Andreas Moshovos , Scott Hauck , Prithviraj Banerjee, CHIMAERA: a high-performance architecture with a tightly-coupled reconfigurable functional unit, Proceedings of the 27th annual international symposium on Computer architecture, p.225-235, June 2000, Vancouver, British Columbia, Canada

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, customizable processors, instruction-set extensions, subgraph enumeration algorithm