Data Allocation Strategies for Dense Linear Algebra on two-dimensional Grids with Heterogeneous Communication Links

Olivier Beaumont 1 Arnaud Legrand 1 Yves Robert 1
1 REMAP - Regularity and massive parallel computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : In this paper, we study the implementation of dense linear algebra kernels, such as matrix multiplication on 2D grids with homogeneous processors when the communication links between the processors are heterogeneous (i.e. the time to transfer a block of the matrix between two processors depends on these processors). We prove that finding the best allocation of the processors into a grid, with respect to the minimization of the communication overhead, is a NP-complete problem.
Document type :
Reports
Complete list of metadatas

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00072457
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 10:00:51 AM
Last modification on : Friday, May 3, 2019 - 1:33:39 PM

Identifiers

  • HAL Id : inria-00072457, version 1

Collections

Citation

Olivier Beaumont, Arnaud Legrand, Yves Robert. Data Allocation Strategies for Dense Linear Algebra on two-dimensional Grids with Heterogeneous Communication Links. [Research Report] RR-4165, LIP RR-2001-14, INRIA, LIP. 2001. ⟨inria-00072457⟩

Share

Metrics

Record views

153

Files downloads

257