Afficher la notice abrégée

Recent Advances in Matrix Partitioning for Parallel Computing on Heterogeneous Platforms

hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorBEAUMONT, Olivier
hal.structure.identifierSchool of Computer Science and Informatics [Dublin]
dc.contributor.authorBECKER, Brett
hal.structure.identifierWellesley College
dc.contributor.authorDEFLUMERE, Ashley
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorEYRAUD-DUBOIS, Lionel
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorLAMBERT, Thomas
hal.structure.identifierSchool of Computer Science and Informatics [Dublin]
dc.contributor.authorLASTOVETSKY, Alexey
dc.date.accessioned2024-04-04T03:06:04Z
dc.date.available2024-04-04T03:06:04Z
dc.date.issued2019-01
dc.identifier.issn1045-9219
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/193307
dc.description.abstractEnThe 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.sponsorshipSolveurs pour architectures hétérogènes utilisant des supports d'exécution - ANR-13-MONU-0007
dc.language.isoen
dc.publisherInstitute of Electrical and Electronics Engineers
dc.title.enRecent Advances in Matrix Partitioning for Parallel Computing on Heterogeneous Platforms
dc.typeArticle de revue
dc.identifier.doi10.1109/TPDS.2018.2853151
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.journalIEEE Transactions on Parallel and Distributed Systems
bordeaux.page11
bordeaux.volume30
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.issue1
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-01670672
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-01670672v1
bordeaux.COinSctx_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

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée