Cuboid Partitioning for Parallel Matrix Multiplication on Heterogeneous Platforms
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | BEAUMONT, Olivier | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | EYRAUD-DUBOIS, Lionel | |
| hal.structure.identifier | Université de Bordeaux [UB] | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | LAMBERT, Thomas | |
| dc.contributor.editor | Pierre-François Dutot | |
| dc.contributor.editor | Denis Trystram | |
| dc.date.accessioned | 2024-04-04T03:10:11Z | |
| dc.date.available | 2024-04-04T03:10:11Z | |
| dc.date.issued | 2016-08 | |
| dc.date.conference | 2016-08-24 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/193669 | |
| dc.description.abstractEn | The problem of partitioning a square into zones of prescribed areas arises when partitioning matrices for dense linear algebra kernels onto a set of heterogeneous processors, and several approximation algorithms have been proposed for that problem. In this paper, we address the natural generalization of this problem in dimension 3: partition a cuboid in a set of zones of prescribed volumes (which represent the amount of computations to perform), while minimizing the surface of the boundaries between zones (which represent the data transfers involved). This problem naturally arises in the context of matrix multiplication, and can be seen as a heterogeneous generalization of 2.5D approaches that have been proposed in this context. The contributions of this paper are twofold. We prove the NP-completeness of the general problem, and we propose a 5/6^(2/3) (~1.51) approximation algorithm for cube-partitioning. This is the first known approximation result for this 3D partitioning problem. | |
| 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 | Springer International Publishing | |
| dc.source.title | Euro-Par 2016 | |
| dc.title.en | Cuboid Partitioning for Parallel Matrix Multiplication on Heterogeneous Platforms | |
| dc.type | Communication dans un congrès | |
| dc.identifier.doi | 10.1007/978-3-319-43659-3_13 | |
| dc.subject.hal | Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC] | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | 22nd International Conference on Parallel and Distributed Computing | |
| bordeaux.country | FR | |
| bordeaux.title.proceeding | Euro-Par 2016 | |
| bordeaux.conference.city | Grenoble | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-01269881 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.conference.end | 2016-08-26 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-01269881v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=Euro-Par%202016&rft.date=2016-08&rft.au=BEAUMONT,%20Olivier&EYRAUD-DUBOIS,%20Lionel&LAMBERT,%20Thomas&rft.genre=unknown |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||