Skip to Main content Skip to Navigation
Reports

Acyclic partitioning of large directed acyclic graphs

Abstract : We investigate the problem of partitioning the vertices of a directed acyclic graph into a given number of parts. The objective function is to minimize the number or the total weight of the edges having end points in different parts, which is also known as edge cut. The standard load balancing constraint of having an equitable partition of the vertices among the parts should be met. Furthermore, the partition is required to be {\em acyclic}, i.e., the inter-part edges between the vertices from different parts should preserve an acyclic dependency structure among the parts. In this work, we adopt the multilevel approach with coarsening, initial partitioning, and refinement phases for acyclic partitioning of directed acyclic graphs. We focus on two-way partitioning (sometimes called bisection), as this scheme can be used in a recursive way for multi-way partitioning. To ensure the acyclicity of the partition at all times, we propose novel and efficient coarsening and refinement heuristics. The quality of the computed acyclic partitions is assessed by computing the edge cut. We also propose effective ways to use the standard undirected graph partitioning methods in our multilevel scheme. We perform a large set of experiments on a dataset consisting of (i)~graphs coming from an application and (ii)~some others corresponding to matrices from a public collection. We report improvements, on average, around 59\% compared to the current state of the art.
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/hal-01744603
Contributor : Equipe Roma <>
Submitted on : Tuesday, March 27, 2018 - 3:01:14 PM
Last modification on : Wednesday, November 20, 2019 - 3:17:53 AM
Document(s) archivé(s) le : Thursday, September 13, 2018 - 8:11:29 AM

File

RR-9163.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01744603, version 1

Collections

Citation

Julien Herrmann, M Yusuf Özkaya, Bora Uçar, Kamer Kaya, Umit Catalyurek. Acyclic partitioning of large directed acyclic graphs. [Research Report] RR-9163, Inria - Research Centre Grenoble – Rhône-Alpes. 2018. ⟨hal-01744603⟩

Share

Metrics

Record views

284

Files downloads

412