A Fast Rescheduling Heuristic of SDF Graphs for HW/SW Partitioning Algorithms
B. Knerr, Martin Hölzer, Markus Rupp · 2006
HW/SW partitioning of modern heterogeneous systems, which combine signal processing as well as multimedia applications, is usually performed on a task or process graph representation. As this optimisation problem is known to be NP-hard, existing partitioning techniques rely on heuristic methods to traverse the vast search space. Moreover the process scheduling of a synchronous data flow (SDF) graph on distributed resources, which constitutes the evaluation of every single partitioning solution, is also an NP-hard problem. This paper proposes a fast rescheduling technique of SDF graphs suitable for HW/SW partitioning algorithms that move incrementally through the search space. Its performance is demonstrated by a comparison to classical list scheduling algorithms for distributed resources.