Exploiting Redundancy in Communication Avoiding Algorithms for Algorithm-based Fault Tolerance

Abstract

Communication-avoiding algorithms allow redundant computations to minimize the number of inter-process communications. In this paper, we propose to exploit this redundancy for fault-tolerance purpose. We illustrate this idea with QR factorization of tall and skinny matrices, and we evaluate the number of failures our algorithm can tolerate under different semantics.

Le site de la conf : http://www.mcs.anl.gov/ieeecluster2015
Deadline le 7 mars
Format : 10 pages IEEE double colonnes

Eventually, get the resulting R on any of the processes
Eventually, get the resulting R on process 0
Eventually, get the resulting R on all the (surviving) processes
Replace the failed process by a new one and continue

svn repository

OpenMPI with user-level failure mitigation (ie, fault-tolerant Open MPI) : Open MPI 1.7ft http://fault-tolerance.org
Compile Open MPI with option –enable-mpi-ext=ftmpi –with-ft=mpi
Run it with option -am ft-enable-mpi

Example: mpiexec -am ft-enable-mpi -n 5 ./ring-ft

Communication-avoiding algorithms :

J. Demmel, L. Grigori, M. F. Hoemmen, and J. Langou, Communication-optimal parallel and sequential QR and LU factorizations : Theory and Practice, UCB-EECS-2008-89 and LAWN 204 http://www.netlib.org/lapack/lawnspdf/lawn204.pdf

ABFT :

George Bosilca, Rémi Delmas, Jack Dongarra, Julien Langou: Algorithm-based fault tolerance applied to high performance computing http://www.sciencedirect.com/science/article/pii/S0743731508002141
Zizhong Chen, Graham E. Fagg, Edgar Gabriel, Julien Langou, Thara Angskun, George Bosilca and Jack Dongarra : Fault tolerant high performance computing by a coding approach http://icl.cs.utk.edu/news_pub/submissions/diskless_ftmpi_ppopp05.pdf

Tools we are using here: