Bonzini, Paolo Pozzi, Laura 2008 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 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 worstcase 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. application/pdf https://localhost:5000/ark:/12658/srd1318261 https://susi.usi.ch/global/documents/318261 https://susi.usi.ch/documents/318261/files/ITR0807.pdf eng info:eu-repo/semantics/altIdentifier/ark/12658/srd1318261 info:eu-repo/semantics/openAccess License undefined info:eu-repo/classification/udc/004 On the complexity of enumeration and scheduling for extensible embedded processors http://purl.org/coar/resource_type/c_816b