Polynomial-time subgraph enumeration for automated instruction set extension
- Bonzini, Paolo Facoltà di scienze informatiche, Università della Svizzera italiana, Svizzera
- Pozzi, Laura Facoltà di scienze informatiche, Università della Svizzera italiana, Svizzera
-
2006
9 p.
English
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.
- Language
-
- English
- Classification
- Computer science and technology
- License
- License undefined
- Identifiers
-
- RERO DOC 10708
- ARK ark:/12658/srd1318270
- Persistent URL
- https://n2t.net/ark:/12658/srd1318270
Statistics
Document views: 26
File downloads:
- ITR0607.pdf: 58