Name
Abstract | ||
|---|---|---|
Graphs are widely used to model execution dependencies in applications. In particular, the NP-complete problem of partitioning a graph under constraints receives enormous attention by researchers because of its applicability in multiprocessor scheduling. We identified the additional constraint of acyclic dependencies between blocks when mapping streaming applications to a heterogeneous embedded multiprocessor. Existing algorithms and heuristics do not address this requirement and deliver results that are not applicable for our use-case. In this work, we show that this more constrained version of the graph partitioning problem is NP-complete and present heuristics that achieve a close approximation of the optimal solution found by an exhaustive search for small problem instances and much better scalability for larger instances. In addition, we can show a positive impact on the schedule of a real imaging application that improves communication volume and execution time. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.4230/LIPIcs.SEA.2017.30 | symposium on experimental and efficient algorithms |
DocType | Volume | Citations |
Conference | abs/1704.00705 | 1 |
PageRank | References | Authors |
0.34 | 2 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Orlando Moreira | 1 | 1 | 0.34 |
| Merten Popp | 2 | 1 | 0.34 |
| Christian Schulz | 3 | 240 | 24.10 |