On partitioning problems with complex objectives

Résumé : Les outils de partitionnement de graphes et d'hypergraphes interviennent pour paralléliser efficacement de nombreux algorithmes liés aux matrices creuses. La plupart du temps, la fonction objectif minimisée par ces outils est liée au besoin de réduire les coûts de communication, tandis que les contraintes d'équilibre à satisfaire sont elles liées à l'équilibrage de la charge ou de la consommation mémoire. Parfois, l'objectif d'équilibre est une fonction complexe du partitionnement. Nous décrivons plusieurs applications majeures de calcul parallèle sur des matrices creuses où de telles contraintes d'équilibre apparaissent. Pour ces exemples, même les outils de partitionnement les plus pointus sont loin d'être adéquats. Pour autant que nous sachions, il n'existe dans la littérature qu'un seul cadre algorithmique qui traite ces problèmes. Nous proposons ici une nouvelle approche algorithmique et fournissons des résultats d'expériences la mettant en œuvre.
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00567129
Contributeur : Bora Uçar <>
Soumis le : vendredi 18 février 2011 - 13:13:29
Dernière modification le : mercredi 12 septembre 2018 - 17:46:02
Document(s) archivé(s) le : mardi 6 novembre 2012 - 14:16:19

Fichier

RR-7546.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00567129, version 1

Citation

Kamer Kaya, François-Henry Rouet, Bora Uçar. On partitioning problems with complex objectives. [Research Report] RR-7546, INRIA. 2011. 〈inria-00567129〉

Partager

Métriques

Consultations de la notice

343

Téléchargements de fichiers

189