Acyclic partitioning of large directed acyclic graphs

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 refinementphases 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 andrefinement 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.; Nous étudions le problème du partitionnement des sommets d’un graphe acyclique dirigé en un nombre donné de parties. La fonction objectiveest de minimiser le poids total des arêtes ayant des extrémités dans différentes parties, qui sont également nommées arêtes coupées. La contrainted’équilibrage de charge standard d’avoir une partition équitable des sommets entre les parties doit être respectée. En outre, la partition doit être acyclique, c’est-à-dire, les arêtes coupées doivent préserver une structure de dépendance acyclique entre les parties. Dans ce travail, nous adoptons une approche multiniveaux avec des étapes de contraction, partitionnement initial et raffinement pour le partitionnement acyclique des graphes acycliques dirigés. Nous nous concentrons sur la bissection, car ce schéma peut être utilisé d’une manière récursive pour le partitionnement multi-voies. Pour assurer l’acyclicité du partitionnement à tout moment, nous proposons des méthodes de contraction etde raffinement. La qualité des partitions acycliques calculées est évaluée en calculant la somme des poids des arêtes coupées. Nous proposons également des moyens efficaces afin d’utiliser des méthodes standard de partitionnement de graphes non orientés dans notre schéma multi-niveaux. Nous effectuons un grand nombre d’expériences sur un ensemble de données constitué de (i) graphes provenant d’une application, et (ii) d’autres graphes correspondant à des matrices d’une collection publique. Nous rapportons des améliorations par rapport aux méthodes existantes d’environ 59 % en moyenne.