Bridging the Gap between Performance and Bounds of Cholesky Factorization on Heterogeneous Platforms

Emmanuel Agullo; Olivier Beaumont; Lionel Eyraud-Dubois; Julien Herrmann; Suraj Kumar; Loris Marchal; Samuel Thibault

doi:10.1109/IPDPSW.2015.35

Bridging the Gap between Performance and Bounds of Cholesky Factorization on Heterogeneous Platforms

Emmanuel Agullo ¹ Olivier Beaumont ^{2, 3} Lionel Eyraud-Dubois ^{2, 3} Julien Herrmann ⁴ Suraj Kumar ^{1, 3, 5, 6} Loris Marchal ^{4, 7} Samuel Thibault ^{6, 2, 5}

1 HiePACS - High-End Parallel Algorithms for Challenging Numerical Simulations

LaBRI - Laboratoire Bordelais de Recherche en Informatique, Inria Bordeaux - Sud-Ouest

2 LaBRI - Laboratoire Bordelais de Recherche en Informatique

3 Realopt - Reformulations based algorithms for Combinatorial Optimization

LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest

4 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement

Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme

5 RUNTIME - Efficient runtime systems for parallel architectures

Inria Bordeaux - Sud-Ouest, UB - Université de Bordeaux, CNRS - Centre National de la Recherche Scientifique : UMR5800

6 STORM - STatic Optimizations, Runtime Methods

LaBRI - Laboratoire Bordelais de Recherche en Informatique, Inria Bordeaux - Sud-Ouest

7 LIP - Laboratoire de l'Informatique du Parallélisme

Abstract : We consider the problem of allocating and scheduling dense linear application on fully heterogeneous platforms made of CPUs and GPUs. More specifically, we focus on the Cholesky factorization since it exhibits the main features of such problems. Indeed, the relative performance of CPU and GPU highly depends on the sub-routine: GPUs are for instance much more efficient to process regular kernels such as matrix-matrix multiplications rather than more irregular kernels such as matrix factorization. In this context, one solution consists in relying on dynamic scheduling and resource allocation mechanisms such as the ones provided by PaRSEC or StarPU. In this paper we analyze the performance of dynamic schedulers based on both actual executions and simulations, and we investigate how adding static rules based on an offline analysis of the problem to their decision process can indeed improve their performance, up to reaching some improved theoretical performance bounds which we introduce.

Keywords : Dense Linear Algebra starpu-simgrid Cholesky Factorization Resource Allocation Scheduling Heterogeneous Resources Dynamic Schedulers Simulation

Document type :

Conference papers

Domain :

Computer Science [cs] / Distributed, Parallel, and Cluster Computing [cs.DC]

Complete list of metadatas

Cited literature [24 references] Display Hide Download

https://hal.inria.fr/hal-01120507
Contributor : Suraj Kumar <>
Submitted on : Wednesday, February 25, 2015 - 6:47:24 PM
Last modification on : Thursday, January 9, 2020 - 9:56:06 AM
Long-term archiving on: Tuesday, May 26, 2015 - 11:25:16 AM

Camera_ready.pdf

Files produced by the author(s)

Bridging the Gap between Performance and Bounds of Cholesky Factorization on Heterogeneous Platforms

File

Identifiers

Collections

Citation

Export

Metrics

1061

829

Contact

Bridging the Gap between Performance and Bounds of Cholesky Factorization on Heterogeneous Platforms

File

Identifiers

Collections

Citation

Export

Share

Metrics

1061

829

Contact