Polynomial-time subgraph enumeration for automated instruction set extension

ABSTRACT

This paper proposes a novel algorithm that, given a data-flow graph and an input/output constraint, enumerates all convex subgraphs under the given constraint in polynomial time with respect to the size of the graph. These subgraphs have been shown to represent efficient Instruction Set Extensions for customizable processors. The search space for this problem is inherently polynomial but, to our knowledge, this is the first paper to prove this and to present a practical algorithm for this problem with polynomial complexity. Our algorithm is based on properties of convex subgraphs that link them to the concept of multiple-vertex dominators. We discuss several pruning techniques that, without sacrificing the optimality of the algorithm, make it practical for data-flow graphs of a thousands nodes or more.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, The theory of parsing, translation, and compiling, Prentice-Hall, Inc., Upper Saddle River, NJ, 1972
• 2: Kubilay Atasu , Günhan Dündar , Can Özturan, An integer linear programming approach for identifying instruction-set extensions, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 19-21, 2005, Jersey City, NJ, USA [doi>10.1145/1084834.1084880]
• 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: Partha Biswas , Sudarshan Banerjee , Nikil Dutt , Laura Pozzi , Paolo Ienne, ISEGEN: Generation of High-Quality Instruction Set Extensions by Iterative Improvement, Proceedings of the conference on Design, Automation and Test in Europe, p.1246-1251, March 07-11, 2005 [doi>10.1109/DATE.2005.191]
• 5: Paolo Bonzini , Laura Pozzi, Code transformation strategies for extensible embedded processors, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176760.1176791]
• 6: 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]
• 7: Nathan Clark , Amir Hormati , Scott Mahlke , Sami Yehia, Scalable subgraph mapping for acyclic computation accelerators, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176760.1176779]
• 8: 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
• 9: E. Dubrova, M. Teslenko, and A. Martinelli. On relation between non-disjoint decomposition and multiple-vertex dominators. In Proc. of ISCAS, 2004.
• 10: Rajiv Gupta, Generalized dominators and post-dominators, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.246-257, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143216]
• 11: Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979 [doi>10.1145/357062.357071]
• 12: L. Pozzi, K. Atasu, and P. Ienne. Optimal and approximate algorithms for the extension of embedded processor instruction sets. In IEEE TCAD, July 2006.
• 13: 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]
• 14: P. Bonzini and L. Pozzi Polynomial-time subgraph enumeration for automated instruction set extension. TR 2006/07, University of Lugano, 2006. http://www.inf.unisi.ch/file/pub/15/bonzini-pozzi-2006-07.pdf