An efficient and complete approach for throughput-maximal SDF allocation and scheduling on multi-core platforms
- 1 March 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15301591,p. 897-902
Abstract
Our work focuses on allocating and scheduling a synchronous data-flow (SDF) graph onto a multi-core platform subject to a minimum throughput requirement. This problem has traditionally be tackled by incomplete approaches based on problem decomposition and local search, which could not guarantee optimality. Exact algorithms used to be considered reasonable only for small problem instances. We propose a complete algorithm based on Constraint Programming which solves the allocation and scheduling problem as a whole. We introduce a number of search acceleration techniques that significantly reduce run-time by aggressively pruning the search space without compromising optimality. The solver has been tested on a number of non-trivial instances and demonstrated promising run-times on SDFGs of practical size and one order of magnitude speed-up w.r.t. the fastest known complete approach.Keywords
This publication has 6 references indexed in Scilit:
- Strategic directions towards multicore application specific computing2009
- SDF^3: SDF For Free2006
- Multiprocessor Resource Allocation for Hard-Real-Time Streaming with a Dynamic Job-Mix2005
- Faster maximum and minimum mean cycle algorithms for system-performance analysisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1998
- Determining the Order of Processor Transactions in Statically Scheduled MultiprocessorsJournal of Signal Processing Systems, 1997
- Synchronous data flowProceedings of the IEEE, 1987