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 and technology
- License
- License undefined
- Identifiers
-
- RERO DOC 22105
- ARK ark:/12658/srd1318261
- Persistent URL
- https://n2t.net/ark:/12658/srd1318261
Statistics
Document views: 22
File downloads:
- ITR0807.pdf: 41