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
* Corresponding author
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—
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-01216245
Contributor : Olivier Beaumont <>
Submitted on : Thursday, October 15, 2015 - 7:26:09 PM
Last modification on : Tuesday, May 7, 2019 - 11:42:10 AM
Long-term archiving on : Thursday, April 27, 2017 - 4:25:05 AM

File

paper.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01216245, version 1

Citation

Olivier Beaumont, Lionel Eyraud-Dubois, Thomas Lambert. A New Approximation Algorithm for Matrix Partitioning in Presence of Strongly Heterogeneous Processors. 30th IEEE International Parallel & Distributed Processing Symposium , May 2016, Chicago, France. ⟨hal-01216245⟩

Share

Metrics

Record views

442

Files downloads

458