Parallel out-of-core matrix inversion
Résumé
This paper presents a parallel out-of-core algorithm to invert huge matrices, that is when size of matrices is larger than the available physical memory by one or more orders of magnitude. Preliminary performance results are shown for a commodity cluster. An accurate prediction performance model of the algorithm is given. Thanks to the prediction model, optimizations which avoid the overhead of the out-of-core algorithm are derived. Performances of the optimized algorithm using a O(N) memory size are similar to the performances of the best known parallel in-core algorithm using a O(N^2) memory size (where N is the matrix order). There is no memory restriction for inversion of huge matrices.
Ce papier présente un algorithme out-of-core pour l'inversion de matrices de taille supérieure à la capacité mémoire physique disponible. Une modélisation de l’algorithme est proposées dans e rapport. Cette modélisation est ensuite validée par des expérimentations menées que une architecture de tue grappe. Outre, le fait que ce modèle nous permet de prédire les temps d'exécution, nous pouvons également extraire les surcoûts out-of-core et proposer des optimisations pour en éviter les effets. L'algorithme ainsi optimisé utilise un taille mémoire en O(N) pour des performances similaires au cas in-core qui utilise une taille mémoire en O(N2) 'où N est l'ordre de la matrice). Il n'y a plus de limite mémoire pour l’inversion matricielle !
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|