Graph partitioning with acyclicity constraints

DOI10.4230/LIPICS.SEA.2017.30zbMATH Open1433.68303arXiv1704.00705OpenAlexW2963951790MaRDI QIDQ4580190FDOQ4580190

Authors: Orlando M. Moreira, Merten Popp, Christian Schulz

Publication date: 13 August 2018

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.

Full work available at URL: https://arxiv.org/abs/1704.00705

Recommendations

zbMATH Keywords

graph partitioning computer vision imaging applications

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computing methodologies for image processing (68U10) Machine vision and scene understanding (68T45)

Cited In (2)

This page was built for publication: Graph partitioning with acyclicity constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580190)