文章基本信息

标题：Graph Partitioning with Acyclicity Constraints
本地全文：下载
作者：Orlando Moreira ; Merten Popp ; Christian Schulz 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：75
页码：30:1-30:15
DOI：10.4230/LIPIcs.SEA.2017.30
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Graph Partitioning; Computer Vision and Imaging Applications