CHEVALIER, Cédric; PELLEGRINI, François

doi:10.1007/11823285

Métadonnées

Licence d’utilisation du document

CHEVALIER, Cédric
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithms and high performance computing for grand challenge applications [SCALAPPLIX]

PELLEGRINI, François
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithms and high performance computing for grand challenge applications [SCALAPPLIX]

Langue

Communication dans un congrès

Ce document a été publié dans

Euro-Par 2006 Parallel Processing, Euro-Par 2006 Parallel Processing, Euro-Par, 2006-08-30, Dresden. 2006-11-01, vol. 4128, p. 243-252

Springer

Résumé en anglais

Parallel graph partitioning is a difficult issue, because the best sequential graph partitioning methods known to date are based on iterative local optimization algorithms that do not parallelize nor scale well. On the other hand, evolutionary algorithms are highly parallel and scalable, but converge very slowly as problem size increases. This paper presents methods that can be used to reduce problem space in a dramatic way when using graph partitioning techniques in a multi-level framework, thus enabling the use of evolutionary algorithms as possible candidates, among others, for the realization of efficient scalable parallel graph partitioning tools. Results obtained on the recursive bipartitioning problem with a multi-threaded genetic algorithm are presented, which show that this approach outperforms existing state-of-the-art parallel partitioners.< Réduire