Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Recent Advances in Matrix Partitioning for Parallel Computing on Heterogeneous Platforms

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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Lionel Eyraud-Dubois Connect in order to contact the contributor
Submitted on : Thursday, December 21, 2017 - 3:28:19 PM
Last modification on : Friday, December 3, 2021 - 3:38:08 PM


Files produced by the author(s)


  • HAL Id : hal-01670672, version 1



Olivier Beaumont, Brett Becker, Ashley Deflumere, Lionel Eyraud-Dubois, Thomas Lambert, et al.. Recent Advances in Matrix Partitioning for Parallel Computing on Heterogeneous Platforms. 2017. ⟨hal-01670672v1⟩



Record views


Files downloads