Preprint

On the complexity of enumeration and scheduling for extensible embedded processors

  • Bonzini, Paolo Facoltà di scienze informatiche, Università della Svizzera italiana, Svizzera
  • Pozzi, Laura Facoltà di scienze informatiche, Università della Svizzera italiana, Svizzera
    2008

8 p.

English 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.
Language
  • English
Classification
Computer science
License
License undefined
Identifiers
  • RERO DOC 22105
Persistent URL
https://susi.usi.ch/usi/documents/318261
Statistics

Document views: 2 File downloads:
  • ITR0807.pdf: 1