License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2017.30
URN: urn:nbn:de:0030-drops-76042
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7604/
Go to the corresponding LIPIcs Volume Portal

Moreira, Orlando ; Popp, Merten ; Schulz, Christian

Graph Partitioning with Acyclicity Constraints

pdf-format:
LIPIcs-SEA-2017-30.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{moreira_et_al:LIPIcs:2017:7604,
  author =	{Orlando Moreira and Merten Popp and Christian Schulz},
  title =	{{Graph Partitioning with Acyclicity Constraints}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{30:1--30:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Costas S. Iliopoulos and Solon P. Pissis and Simon J. Puglisi and Rajeev Raman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7604},
  URN =		{urn:nbn:de:0030-drops-76042},
  doi =		{10.4230/LIPIcs.SEA.2017.30},
  annote =	{Keywords: Graph Partitioning, Computer Vision and Imaging Applications}
}

Keywords: Graph Partitioning, Computer Vision and Imaging Applications
Collection: 16th International Symposium on Experimental Algorithms (SEA 2017)
Issue Date: 2017
Date of publication: 07.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI