Cuboid Partitioning for Parallel Matrix Multiplication on Heterogeneous Platforms

Olivier Beaumont 1 Lionel Eyraud-Dubois 1 Thomas Lambert 2, 1
1 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 : The problem of partitioning a square into zones of prescribed areas arises when partitioning matrices for dense linear algebra kernels onto a set of heterogeneous processors, and several approximation algorithms have been proposed for that problem. In this paper, we address the natural generalization of this problem in dimension 3: partition a cuboid in a set of zones of prescribed volumes (which represent the amount of computations to perform), while minimizing the surface of the boundaries between zones (which represent the data transfers involved). This problem naturally arises in the context of matrix multiplication, and can be seen as a heterogeneous generalization of 2.5D approaches that have been proposed in this context. The contributions of this paper are twofold. We prove the NP-completeness of the general problem, and we propose a 5/6^(2/3) (~1.51) approximation algorithm for cube-partitioning. This is the first known approximation result for this 3D partitioning problem.
Type de document :
Communication dans un congrès
Pierre-François Dutot; Denis Trystram. 22nd International Conference on Parallel and Distributed Computing, Aug 2016, Grenoble, France. Springer International Publishing, Euro-Par 2016, 2016, 〈10.1007/978-3-319-43659-3_13〉
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-01269881
Contributeur : Thomas Lambert <>
Soumis le : vendredi 12 mai 2017 - 17:45:41
Dernière modification le : jeudi 11 janvier 2018 - 01:49:30
Document(s) archivé(s) le : dimanche 13 août 2017 - 12:58:40

Fichier

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

Identifiants

Collections

Citation

Olivier Beaumont, Lionel Eyraud-Dubois, Thomas Lambert. Cuboid Partitioning for Parallel Matrix Multiplication on Heterogeneous Platforms. Pierre-François Dutot; Denis Trystram. 22nd International Conference on Parallel and Distributed Computing, Aug 2016, Grenoble, France. Springer International Publishing, Euro-Par 2016, 2016, 〈10.1007/978-3-319-43659-3_13〉. 〈hal-01269881v2〉

Partager

Métriques

Consultations de la notice

115

Téléchargements de fichiers

35