Recent Advances in Matrix Partitioning for Parallel Computing on Heterogeneous Platforms - Archive ouverte HAL Access content directly
Journal Articles IEEE Transactions on Parallel and Distributed Systems Year : 2019

Recent Advances in Matrix Partitioning for Parallel Computing on Heterogeneous Platforms

(1, 2) , (3) , (4) , (2, 1) , (2, 1) , (3)
1
2
3
4

Abstract

The problem of partitioning a matrix into a set of sub-matrices has received increased attention recently and is crucial when considering dense linear algebra and kernels with similar communication patterns on heterogeneous platforms. The problem of load balancing and minimizing communication is traditionally reducible to an optimization problem that involves partitioning a square into rectangles. This problem has been proven to be NP-Complete for an arbitrary number of partitions. In this paper, we present recent approaches that relax the restriction that all partitions be rectangles. The first approach uses an original mathematical technique to find the exact optimal partitioning. Due to the complexity of the technique, it has been developed for a small number of partitions only. However, even at a small scale, the optimal partitions found by this approach are often non-rectangular and sometimes non-intuitive. The second approach is the study of approximate partitioning methods by recursive partitioning algorithms. In particular we use the work on optimal partitioning to improve pre-existing algorithms. In this paper we discuss the different perspectives it opens and present two algorithms, SNRPP which is a sqrt(3/2) approximation, and NRPP which is a 2/sqrt(3) approximation. While sub-optimal, this approach works for an arbitrary number of partitions. We use the first exact approach to analyse how close to the known optimal solutions the NRRP algorithm is for small numbers of partitions.
Fichier principal
Vignette du fichier
paper-r1.pdf (2.75 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01670672 , version 1 (21-12-2017)
hal-01670672 , version 2 (11-05-2018)

Identifiers

Cite

Olivier Beaumont, Brett A. Becker, Ashley Deflumere, Lionel Eyraud-Dubois, Thomas Lambert, et al.. Recent Advances in Matrix Partitioning for Parallel Computing on Heterogeneous Platforms. IEEE Transactions on Parallel and Distributed Systems, 2019, 30 (1), pp.11. ⟨10.1109/TPDS.2018.2853151⟩. ⟨hal-01670672v2⟩
490 View
520 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More