Polynomial-Time Subgraph Enumeration for Automated Instruction Set Extension
Additional information
Authors
Bonzini P.,
Pozzi L.
Type
Article in conference proceedings
Year
2007
Language
English
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, this is the first paper to prove this and to present a practical algorithm for this problem with polynomial complexity. The algorithm is based on properties of convex subgraphs that link them to the concept of multiple-vertex dominators. The paper discussed several pruning techniques that, without sacrificing the optimality of the algorithm, make it practical for data-flow graphs of a thousands nodes or more
Keywords
Application specific integrated circuits, automated instruction set extension, computational complexity, convex subgraphs, customizable processors, data flow graphs, data-flow graph, Delay, Embedded system, Informatics, input-output constraint, instruction sets, Integer linear programming, microprocessor chips, multiple-vertex dominators, polynomial complexity, polynomial-time subgraph enumeration, polynomials, Process design, Space exploration, System-on-a-chip, Time factors
Conference proceedings
Design, Automation Test in Europe Conference Exhibition, 2007. DATE ''07
Pages (or article number)
1-6
