Multi-level direct K-way hypergraph partitioning with multiple constraints and fixed vertices - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Journal of Parallel and Distributed Computing Année : 2008

Multi-level direct K-way hypergraph partitioning with multiple constraints and fixed vertices

Résumé

K-way hypergraph partitioning has an ever-growing use in parallelization of scientific computing applications. We claim that hypergraph partitioning with multiple constraints and fixed vertices should be implemented using direct K-way refinement , instead of the widely adopted recursive bisection paradigm. Our arguments are based on the fact that recursive-bisection-based partitioning algorithms perform considerably worse when used in the multiple constraint and fixed vertex formulations. We discuss possible reasons for this performance degradation. We describe a careful implementation of a multi-level direct K-way hypergraph partitioning algorithm, which performs better than a well-known recursive-bisection-based partitioning algorithm in hypergraph partitioning with multiple constraints and fixed vertices. We also experimentally show that the proposed algorithm is effective in standard hypergraph partitioning.
no abstract
Fichier principal
Vignette du fichier
YJPDC2489.pdf (275.62 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00803479 , version 1 (19-12-2019)

Identifiants

  • HAL Id : hal-00803479 , version 1

Citer

Cevdet Aykanat, Berkant B. Cambazoglu, Bora Uçar. Multi-level direct K-way hypergraph partitioning with multiple constraints and fixed vertices. Journal of Parallel and Distributed Computing, 2008, 68, pp.609--625. ⟨hal-00803479⟩
45 Consultations
134 Téléchargements

Partager

Gmail Facebook X LinkedIn More