Recent Advances in Matrix Partitioning for Parallel Computing on Heterogeneous Platforms
hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
dc.contributor.author | BEAUMONT, Olivier | |
hal.structure.identifier | School of Computer Science and Informatics [Dublin] | |
dc.contributor.author | BECKER, Brett | |
hal.structure.identifier | Wellesley College | |
dc.contributor.author | DEFLUMERE, Ashley | |
hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
dc.contributor.author | EYRAUD-DUBOIS, Lionel | |
hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
dc.contributor.author | LAMBERT, Thomas | |
hal.structure.identifier | School of Computer Science and Informatics [Dublin] | |
dc.contributor.author | LASTOVETSKY, Alexey | |
dc.date.accessioned | 2024-04-04T03:06:04Z | |
dc.date.available | 2024-04-04T03:06:04Z | |
dc.date.issued | 2019-01 | |
dc.identifier.issn | 1045-9219 | |
dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/193307 | |
dc.description.abstractEn | 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. | |
dc.description.sponsorship | Solveurs pour architectures hétérogènes utilisant des supports d'exécution - ANR-13-MONU-0007 | |
dc.language.iso | en | |
dc.publisher | Institute of Electrical and Electronics Engineers | |
dc.title.en | Recent Advances in Matrix Partitioning for Parallel Computing on Heterogeneous Platforms | |
dc.type | Article de revue | |
dc.identifier.doi | 10.1109/TPDS.2018.2853151 | |
dc.subject.hal | Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC] | |
bordeaux.journal | IEEE Transactions on Parallel and Distributed Systems | |
bordeaux.page | 11 | |
bordeaux.volume | 30 | |
bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
bordeaux.issue | 1 | |
bordeaux.institution | Université de Bordeaux | |
bordeaux.institution | Bordeaux INP | |
bordeaux.institution | CNRS | |
bordeaux.peerReviewed | oui | |
hal.identifier | hal-01670672 | |
hal.version | 1 | |
hal.popular | non | |
hal.audience | Internationale | |
hal.origin.link | https://hal.archives-ouvertes.fr//hal-01670672v1 | |
bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=IEEE%20Transactions%20on%20Parallel%20and%20Distributed%20Systems&rft.date=2019-01&rft.volume=30&rft.issue=1&rft.spage=11&rft.epage=11&rft.eissn=1045-9219&rft.issn=1045-9219&rft.au=BEAUMONT,%20Olivier&BECKER,%20Brett&DEFLUMERE,%20Ashley&EYRAUD-DUBOIS,%20Lionel&LAMBERT,%20Thomas&rft.genre=article |
Fichier(s) constituant ce document
Fichiers | Taille | Format | Vue |
---|---|---|---|
Il n'y a pas de fichiers associés à ce document. |