Execution Trace Graph Based Multi-criteria Partitioning of Stream Programs

One of the problems proven to be NP-hard in the field of many-core architectures is the partitioning of stream programs. In order to maximize the execution parallelism and obtain the maximal data throughput for a streaming application it is essential to find an appropriate actors assignment. The paper proposes a novel approach for finding a close-to-optimal partitioning configuration which is based on the execution trace graph of a dataflow network and its analysis. We present some aspects of dataflow programming that make the partitioning problem different in this paradigm and build the heuristic methodology on them. Our optimization criteria include: balancing the total processing workload with regards to data dependencies, actors idle time minimization and reduction of data exchanges between processing units. Finally, we validate our approach with experimental results for a video decoder design case and compare them with some state-of-the-art solutions.

Published in:
Procedia Computer Science, 51, 1443-1452
Presented at:
International Conference on Computational Science (ICCS), Reykjavik, Iceland, June 1-3, 2015

 Record created 2015-07-02, last modified 2018-03-17

Publisher's version:
Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)