A New Approximation Algorithm for Matrix Partitioning in Presence of Strongly Heterogeneous Processors

Olivier Beaumont 1, 2, * Lionel Eyraud-Dubois 1, 2 Thomas Lambert 1, 2
* Auteur correspondant
2 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : In this paper, we consider the problem of partitioning a square into a set of zones of prescribed areas, while minimizing the overall size of their projections onto horizontal and vertical axes. This problem typically arises when considering the amount of communications induced when partitioning matrices for dense linear algebra kernels onto a set of heterogeneous processors. It has been first introduced for matrix multiplication in the 2000's, with a best known approximation ratio was 1.75. Since then, two main new ingredients have been introduced. First, Lastovetsky et al. proposed a special partitioning in the case of 2 or 3 strongly heterogeneous processors, as in the case of a platform made of CPUs and GPUs, relaxing the constraint of a rectangular based partitioning. Second, Nagamochi et al. have introduced clever recursive partitioning techniques and proved, thanks to a careful analysis, that their algorithm achieves a 1.25 approximation ratio. In this paper, we combine both ingredients in order to obtain a non-rectangular recursive partitioning (NRRP), whose approximation ratio is 2 √ 3 1.15. Moreover, we observe on a large set of realistic platforms built from CPUs and GPUs that this proposed NRRP algorithm allows to achieve very efficient partitionings on all considered cases. Index Terms—
Type de document :
Communication dans un congrès
IEEE. 30th IEEE International Parallel & Distributed Processing Symposium , May 2016, Chicago, France. IEEE, 30th IEEE International Parallel & Distributed Processing Symposium 2016, Proceedings of the 30th IEEE International Parallel & Distributed Processing Symposium, IPDPS'16. 〈http://www.ipdps.org〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01216245
Contributeur : Olivier Beaumont <>
Soumis le : jeudi 15 octobre 2015 - 19:26:09
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12
Document(s) archivé(s) le : jeudi 27 avril 2017 - 04:25:05

Fichier

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

Identifiants

  • HAL Id : hal-01216245, version 1

Collections

Citation

Olivier Beaumont, Lionel Eyraud-Dubois, Thomas Lambert. A New Approximation Algorithm for Matrix Partitioning in Presence of Strongly Heterogeneous Processors. IEEE. 30th IEEE International Parallel & Distributed Processing Symposium , May 2016, Chicago, France. IEEE, 30th IEEE International Parallel & Distributed Processing Symposium 2016, Proceedings of the 30th IEEE International Parallel & Distributed Processing Symposium, IPDPS'16. 〈http://www.ipdps.org〉. 〈hal-01216245〉

Partager

Métriques

Consultations de la notice

375

Téléchargements de fichiers

180