On Partitioning Two Dimensional Finite Difference Meshes for Distributed Memory Parallel Computers

Anael Grandjean 1 Bora Uçar 2, 1
Abstract : We investigate the problem of partitioning finite difference meshes in two dimensions among the processors of a parallel computer. The objective is to achieve a perfect load balance while minimizing the communication cost. There are well-known graph, hypergraph, and geometry-based partitioning algorithms for this problem. The known geometric algorithms have linear running time and obtain the best results for very special mesh sizes and processor numbers. We propose another geometric algorithm. The proposed algorithm is linear; is ap-plicable to much more cases than some well-known alternatives; obtains better results than the graph partitioning algorithms; ob-tains better results than the hypergraph partitioning algorithms almost always. Our algorithm also obtains better results than a known asymptotically-optimal algorithm for some small number of processors. We also catalog related theoretical results.
Type de document :
Communication dans un congrès
22nd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP 2014), Feb 2014, Turin, Italy. IEEE, pp.9 - 16, 2014, 〈10.1109/PDP.2014.10〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01111292
Contributeur : Equipe Roma <>
Soumis le : vendredi 30 janvier 2015 - 09:39:04
Dernière modification le : vendredi 20 avril 2018 - 15:44:27
Document(s) archivé(s) le : samedi 12 septembre 2015 - 06:25:46

Fichier

anaelpdp.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Anael Grandjean, Bora Uçar. On Partitioning Two Dimensional Finite Difference Meshes for Distributed Memory Parallel Computers. 22nd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP 2014), Feb 2014, Turin, Italy. IEEE, pp.9 - 16, 2014, 〈10.1109/PDP.2014.10〉. 〈hal-01111292〉

Partager

Métriques

Consultations de la notice

287

Téléchargements de fichiers

172