skip to main content
10.5555/1266366.1266657acmconferencesArticle/Chapter ViewAbstractPublication PagesdateConference Proceedingsconference-collections
Article

Polynomial-time subgraph enumeration for automated instruction set extension

Published: 16 April 2007 Publication History

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]
A. V. Aho and J. D. Ullman. Theory of Parsing, Translation and Compiling. Prentice Hall, 1973.
[2]
K. Atasu, G. Dündar, and C. Özturan. An integer linear programming approach for identifying instruction-set extensions. In Proc. of CODES+ISSS, 2005.
[3]
K. Atasu, L. Pozzi, and P. Ienne. Automatic application-specific instruction-set extensions under microarchitectural constraints. In Proc. of DAC, 2003.
[4]
P. Biswas, S. Banerjee, N. Dutt, L. Pozzi, and P. Ienne. ISEGEN: Generation of high-quality instruction set extensions by iterative improvement. In Proc. of DATE, 2005.
[5]
P. Bonzini and L. Pozzi. Code transformation strategies for extensible embedded processors. In Proc. of CASES, 2006.
[6]
H. Choi, J.-S. Kim, C.-W. Yoon, I.-C. Park, S. H. Hwang, and C.-M. Kyung. Synthesis of application specific instructions for embedded DSP software. In IEEE TC, June 1999.
[7]
N. Clark, A. Hormati, and S. Mahlke. Scalable subgraph mapping for acyclic computation accelerators. In Proc. of CASES, 2006.
[8]
N. Clark, H. Zhong, and S. Mahlke. Processor acceleration through automated instruction set customisation. In Proc. of MICRO, 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]
R. Gupta. Generalized dominators and post-dominators. In Proc. of POPL, 1992.
[11]
T. Lengauer and R. E. Tarjan. A fast algorithm for finding dominators in a flowgraph. In ACM TOPLAS, 1979.
[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]
P. Yu and T. Mitra. Scalable custom instructions identification for instruction set extensible processors. In Proc. of CASES, 2004.
[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

Cited By

View all
  • (2015)OPLEACM Transactions on Embedded Computing Systems10.1145/276445814:4(1-23)Online publication date: 9-Sep-2015
  • (2014)IP-enabled C/C++ based high level synthesisInternational Journal of Reconfigurable Computing10.1155/2014/4187502014(1-1)Online publication date: 1-Jan-2014
  • (2014)A Multiple Equivalent Execution Trace Approach to Secure Cryptographic Embedded SoftwareProceedings of the 51st Annual Design Automation Conference10.1145/2593069.2593073(1-6)Online publication date: 1-Jun-2014
  • Show More Cited By
  1. Polynomial-time subgraph enumeration for automated instruction set extension

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    DATE '07: Proceedings of the conference on Design, automation and test in Europe
    April 2007
    1741 pages
    ISBN:9783981080124

    Sponsors

    Publisher

    EDA Consortium

    San Jose, CA, United States

    Publication History

    Published: 16 April 2007

    Check for updates

    Qualifiers

    • Article

    Conference

    DATE07
    Sponsor:
    • EDAA
    • SIGDA
    • The Russian Academy of Sciences
    DATE07: Design, Automation and Test in Europe
    April 16 - 20, 2007
    Nice, France

    Acceptance Rates

    Overall Acceptance Rate 518 of 1,794 submissions, 29%

    Upcoming Conference

    DATE '25
    Design, Automation and Test in Europe
    March 31 - April 2, 2025
    Lyon , France

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)5
    • Downloads (Last 6 weeks)4
    Reflects downloads up to 15 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2015)OPLEACM Transactions on Embedded Computing Systems10.1145/276445814:4(1-23)Online publication date: 9-Sep-2015
    • (2014)IP-enabled C/C++ based high level synthesisInternational Journal of Reconfigurable Computing10.1155/2014/4187502014(1-1)Online publication date: 1-Jan-2014
    • (2014)A Multiple Equivalent Execution Trace Approach to Secure Cryptographic Embedded SoftwareProceedings of the 51st Annual Design Automation Conference10.1145/2593069.2593073(1-6)Online publication date: 1-Jun-2014
    • (2014)Automatic custom instruction identification for application-specific instruction set processorsMicroprocessors & Microsystems10.1016/j.micpro.2014.09.00138:8(1012-1024)Online publication date: 1-Nov-2014
    • (2012)On the feasibility and limitations of just-in-time Instruction set extension for FPGA-based reconfigurable processorsInternational Journal of Reconfigurable Computing10.1155/2012/4183152012(1-1)Online publication date: 1-Jan-2012
    • (2012)An algorithm for finding input-output constrained convex sets in an acyclic digraphJournal of Discrete Algorithms10.1016/j.jda.2012.02.00213(47-58)Online publication date: 1-May-2012
    • (2011)Practical and effective domain-specific function unit design for CGRAProceedings of the 2011 international conference on Computational science and Its applications - Volume Part V10.5555/2029427.2029481(577-592)Online publication date: 20-Jun-2011
    • (2011)An efficient algorithm for custom instruction enumerationProceedings of the 21st edition of the great lakes symposium on Great lakes symposium on VLSI10.1145/1973009.1973047(187-192)Online publication date: 2-May-2011
    • (2011)The Instruction-Set Extension ProblemACM Transactions on Reconfigurable Technology and Systems10.1145/1968502.19685094:2(1-28)Online publication date: 1-May-2011
    • (2010)A generalized control-flow-aware pattern recognition algorithm for behavioral synthesisProceedings of the Conference on Design, Automation and Test in Europe10.5555/1870926.1871228(1255-1260)Online publication date: 8-Mar-2010
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media