On the Complexity of Enumeration and Scheduling for Extensible Embedded Processors

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 run-time. Depending on the targeted architecture, different algorithms may be adopted, but toolchains for different architectures often share two common building blocks. The first is a subgraph enumeration algorithm that lists subgraphs that satisfy particular constraints; this paper proves that a well-known branch-and-bound algorithm, previously thought to have worst-case exponential complexity, actually achieves optimal complexity (polynomial in the size of the graph). The second building block is a scheduling algorithm that computes an optimal order for feeding inputs to application-specific functional units, as well as for retrieving outputs; we prove the NP-completeness of this problem by reducing a flowshop scheduling problem to it. 1 1