Polynomial-Time Subgraph Enumeration for Automated Instruction Set Extension
Informazioni aggiuntive
Autori
Bonzini P.,
Pozzi L.
Tipo
Contributo in atti di convegno
Anno
2007
Lingua
Inglese
Sommario
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
Parole chiave
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
Titolo atti di convegno
Design, Automation Test in Europe Conference Exhibition, 2007. DATE ''07
Pagine (o numero dell’articolo)
1-6
