Università della Svizzera italiana

On the complexity of enumeration and scheduling for extensible embedded processors

Bonzini, Paolo ; Pozzi, Laura

Compiling for extensible processors includes searching the application’s data-flow graphs for code sequences that can be added (as custom instructions) to the core instruction set, as well as finding optimal ways to use these sequences at runtime. Depending on the targeted architecture, different algorithms may be adopted, but toolchains for different architectures often share two common...

Università della Svizzera italiana

Polynomial-time subgraph enumeration for automated instruction set extension

Bonzini, Paolo ; Pozzi, Laura

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...