Title: Graph Partitioning with Acyclicity Constraints,
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 computer vision and imaging
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.