1 Search Results for "Popp, Merten"

Document

DOI: 10.4230/LIPIcs.SEA.2017.30

Graph Partitioning with Acyclicity Constraints

Authors: Orlando Moreira, Merten Popp, and Christian Schulz

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

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.

Cite as

Orlando Moreira, Merten Popp, and Christian Schulz. Graph Partitioning with Acyclicity Constraints. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{moreira_et_al:LIPIcs.SEA.2017.30,
  author =	{Moreira, Orlando and Popp, Merten and Schulz, Christian},
  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 =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.30},
  URN =		{urn:nbn:de:0030-drops-76042},
  doi =		{10.4230/LIPIcs.SEA.2017.30},
  annote =	{Keywords: Graph Partitioning, Computer Vision and Imaging Applications}
}

Refine by Author
1 Moreira, Orlando
1 Popp, Merten
1 Schulz, Christian

Refine by Classification

Refine by Keyword
1 Computer Vision and Imaging Applications
1 Graph Partitioning

Refine by Type
1 document

Refine by Publication Year
1 2017

1 Search Results for "Popp, Merten"

Graph Partitioning with Acyclicity Constraints

Abstract

Cite as

Thanks for your feedback!

Could not send message