Technical report detail

On the Complexity of Enumeration and Scheduling for Extensible Embedded Processors

by Paolo Bonzini and Laura Pozzi


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.


Technical report 2008/07, December 2008

BibTex entry

@techreport{08on, author = {Paolo Bonzini and Laura Pozzi}, title = {On the Complexity of Enumeration and Scheduling for Extensible Embedded Processors }, institution = {University of Lugano}, number = {2008/07}, year = 2008, month = dec }
Attachments