Note: Hal number: tel-01444591.
Keywords: Out-of-core.
| Abstract: | La recherche en parall{\'e}lisme s'est concentr{\'e}e avec succ{\`e}s sur les aspects calcul et communication, on peut aujourd'hui pr{\'e}tendre {\`a} des puissances de calcul de l'ordre du T{\'e}ra-flops (milliard d'op{\'e}ration par seconde). Les applications qui requi{\`e}rent de telle puissance de calcul sont en g{\'e}n{\'e}rales celles qui ont {\`a} traiter des masses de donn{\'e}es qui se mesurent en Giga-octects, voir en T{\'e}ra-octets. Or, dans la pratique les capacit{\'e}s m{\'e}moire fixent la taille maximale du probl{\`e}me que l'utilisateur pourra traiter. L'utilisateur consid{\'e}rera qu'il est inconcevable de recourir au syst{\`e}me de pagination ou aux disques du fait de l'importante chute des performances. Et pourtant, le paradoxe est l{\`a} d'un c{\^o}t{\'e} des capacit{\'e}s m{\'e}moire rapide mais de petite taille et co{\^u}teuses, de l'autre des capacit{\'e}s m{\'e}moire {\`a} bon march{\'e} et de grande taille, plusieurs T{\'e}ra-octets, mais tr{\`e}s lente d'acc{\`e}s. Le concept du calcul out-of-core r{\'e}ponds {\`a} ces attentes en proposant d'utiliser au mieux les ressources des m{\'e}moires externes. Cette th{\`e}se d{\'e}veloppe une {\'e}tude sur le calcul num{\'e}rique hautes performances out-of-core et propose des m{\'e}canismes de traitement des donn{\'e}es de tr{\`e}s grande taille. Pour r{\'e}soudre efficacement le probl{\`e}me de la gestion m{\'e}moire, deux approches diff{\'e}rentes sont trait{\'e}es. Une approche syst{\`e}me dans laquelle nous {\'e}tudions les m{\'e}canismes de pagination. Nous d{\'e}montrons que ces syst{\`e}mes ne sont pas adapt{\'e}s au calcul num{\'e}rique intensif, et qu'il est alors important de r{\'e}ordonnancer les flux d'ex{\'e}cution. Nous pr{\'e}sentons une nouvelle biblioth{\`e}que de gestion de la m{\'e}moire virtuelle au niveau utilisateur. Une optimisation de la factorisation LU de tr{\`e}s grandes matrices illustre l'utilisation de cette biblioth{\`e}que. La seconde approche est bas{\'e}e sur l'algorithmique out-of-core. En pr{\'e}ambule, nous pr{\'e}sentons la biblioth{\`e}que de calcul d'alg{\`e}bre lin{\'e}aire ScaLAPACK, en offrant une description de ses diff{\'e}rentes composantes. Un soin particulier est port{\'e} sur la pr{\'e}sentation du prototype out-of-core et les d{\'e}veloppements que nous avons effectu{\'e} au sein de ce prototype. Nous proposons, ensuite, une {\'e}tude d{\'e}taill{\'e}e de deux algorithmes out-of-core d{\'e}velopp{\'e}s dans cette biblioth{\`e}que : - la factorisation LU : nous pr{\'e}sentons un mod{\`e}le analytique permettant d'{\'e}valuer les performances de la factorisation LU parall{\`e}le out-of-core left-looking. L'objectif de cette mod{\'e}lisation est de d{\'e}celer des optimisations pour l'algorithme en question et de mettre en {\'e}vidence les surco{\^u}ts out-of-core. Le mod{\`e}le de pr{\'e}diction des performances est valid{\'e} de mani{\`e}re exp{\'e}rimentale. Nous prouverons ainsi qu'une distribution de la matrice correctement effectu{\'e}e et la mise en place d'un syst{\`e}me de recouvrement du surco{\^u}t des E/S par le calcul, il est possible d'obtenir des performances proches de l'algorithme en m{\'e}moire. De plus, nous d{\'e}terminons la taille m{\'e}moire minimale n{\'e}cessaire pour permettre ce recouvrement. - l'inversion matricielle : Nous proposons un algorithme d'inversion matricielle out-of-core par extension des travaux r{\'e}alis{\'e}s sur la factorisation LU out-of-core. Par extension du mod{\`e}le de pr{\'e}diction des performances de la factorisation LU, nous avons {\'e}labor{\'e} un mod{\`e}le analytique pour l'inversion. Ce mod{\`e}le permet de mettre en {\'e}vidence les surco{\^u}ts dus au traitement out-of-core. Nous montrons comment r{\'e}duire ces surco{\^u}ts afin d'obtenir une inversion out-of-core pouvant atteindre des performances proches d'une r{\'e}solution en m{\'e}moire. Afin d'exploiter ces r{\'e}sultats nous avons r{\'e}alis{\'e} pour ces deux algorithmes une version effectuant le recouvrement des acc{\`e}s disques par les temps de calcul. La technique utilis{\'e}e pour effectuer les recouvrements est bas{\'e}e sur le clonage de processus, apr{\`e}s avoir {\'e}voqu{\'e} le principe de mise en oeuvre, nous exposons les difficult{\'e}s rencontr{\'e}es pour obtenir un r{\'e}el recouvrement des entr{\'e}es/sorties. Par extension, nous pr{\'e}sentons alors la factorisation LU out-of-core et l'inversion matricielle out-of-core dans lesquelles nous avons mis en place le syst{\`e}me de recouvrement ainsi que les r{\'e}sultats obtenus. Une derni{\`e}re partie pr{\'e}sente l'int{\'e}gration de ces travaux dans Scilab//, un outil de calcul num{\'e}rique. La participation {\`a} ce projet de l'INRIA, permet d'utiliser la biblioth{\`e}que out-of-core de ScaLAPACK avec une interface conviviale, et, d'accro{\^\i}tre ainsi le champ d'application de Scilab//. Nous pr{\'e}sentons Scilab et les techniques permettant d'interfacer des modules externes compil{\'e}s. Nous pr{\'e}sentons ensuite Scilab//, et exposons l'extension que nous avons r{\'e}alis{\'e} afin de proposer une version out-of-core de Scilab. Nous menons ensuite une {\'e}tude afin de proposer des optimisations pour les traitements out-of-core. |
@PhDThesis{ PhDThesisPhD-Caron_00,
abstract = {La recherche en parall{\'e}lisme s'est concentr{\'e}e avec succ{\`e}s sur les aspects calcul et communication, on peut aujourd'hui pr{\'e}tendre {\`a} des puissances de calcul de l'ordre du T{\'e}ra-flops (milliard d'op{\'e}ration par seconde). Les applications qui requi{\`e}rent de telle puissance de calcul sont en g{\'e}n{\'e}rales celles qui ont {\`a} traiter des masses de donn{\'e}es qui se mesurent en Giga-octects, voir en T{\'e}ra-octets. Or, dans la pratique les capacit{\'e}s m{\'e}moire fixent la taille maximale du probl{\`e}me que l'utilisateur pourra traiter. L'utilisateur consid{\'e}rera qu'il est inconcevable de recourir au syst{\`e}me de pagination ou aux disques du fait de l'importante chute des performances. Et pourtant, le paradoxe est l{\`a} d'un c{\^o}t{\'e} des capacit{\'e}s m{\'e}moire rapide mais de petite taille et co{\^u}teuses, de l'autre des capacit{\'e}s m{\'e}moire {\`a} bon march{\'e} et de grande taille, plusieurs T{\'e}ra-octets, mais tr{\`e}s lente d'acc{\`e}s. Le concept du calcul out-of-core r{\'e}ponds {\`a} ces attentes en proposant d'utiliser au mieux les ressources des m{\'e}moires externes. Cette th{\`e}se d{\'e}veloppe une {\'e}tude sur le calcul num{\'e}rique hautes performances out-of-core et propose des m{\'e}canismes de traitement des donn{\'e}es de tr{\`e}s grande taille. Pour r{\'e}soudre efficacement le probl{\`e}me de la gestion m{\'e}moire, deux approches diff{\'e}rentes sont trait{\'e}es. Une approche syst{\`e}me dans laquelle nous {\'e}tudions les m{\'e}canismes de pagination. Nous d{\'e}montrons que ces syst{\`e}mes ne sont pas adapt{\'e}s au calcul num{\'e}rique intensif, et qu'il est alors important de r{\'e}ordonnancer les flux d'ex{\'e}cution. Nous pr{\'e}sentons une nouvelle biblioth{\`e}que de gestion de la m{\'e}moire virtuelle au niveau utilisateur. Une optimisation de la factorisation LU de tr{\`e}s grandes matrices illustre l'utilisation de cette biblioth{\`e}que. La seconde approche est bas{\'e}e sur l'algorithmique out-of-core. En pr{\'e}ambule, nous pr{\'e}sentons la biblioth{\`e}que de calcul d'alg{\`e}bre lin{\'e}aire ScaLAPACK, en offrant une description de ses diff{\'e}rentes composantes. Un soin particulier est port{\'e} sur la pr{\'e}sentation du prototype out-of-core et les d{\'e}veloppements que nous avons effectu{\'e} au sein de ce prototype. Nous proposons, ensuite, une {\'e}tude d{\'e}taill{\'e}e de deux algorithmes out-of-core d{\'e}velopp{\'e}s dans cette biblioth{\`e}que : - la factorisation LU : nous pr{\'e}sentons un mod{\`e}le analytique permettant d'{\'e}valuer les performances de la factorisation LU parall{\`e}le out-of-core left-looking. L'objectif de cette mod{\'e}lisation est de d{\'e}celer des optimisations pour l'algorithme en question et de mettre en {\'e}vidence les surco{\^u}ts out-of-core. Le mod{\`e}le de pr{\'e}diction des performances est valid{\'e} de mani{\`e}re exp{\'e}rimentale. Nous prouverons ainsi qu'une distribution de la matrice correctement effectu{\'e}e et la mise en place d'un syst{\`e}me de recouvrement du surco{\^u}t des E/S par le calcul, il est possible d'obtenir des performances proches de l'algorithme en m{\'e}moire. De plus, nous d{\'e}terminons la taille m{\'e}moire minimale n{\'e}cessaire pour permettre ce recouvrement. - l'inversion matricielle : Nous proposons un algorithme d'inversion matricielle out-of-core par extension des travaux r{\'e}alis{\'e}s sur la factorisation LU out-of-core. Par extension du mod{\`e}le de pr{\'e}diction des performances de la factorisation LU, nous avons {\'e}labor{\'e} un mod{\`e}le analytique pour l'inversion. Ce mod{\`e}le permet de mettre en {\'e}vidence les surco{\^u}ts dus au traitement out-of-core. Nous montrons comment r{\'e}duire ces surco{\^u}ts afin d'obtenir une inversion out-of-core pouvant atteindre des performances proches d'une r{\'e}solution en m{\'e}moire. Afin d'exploiter ces r{\'e}sultats nous avons r{\'e}alis{\'e} pour ces deux algorithmes une version effectuant le recouvrement des acc{\`e}s disques par les temps de calcul. La technique utilis{\'e}e pour effectuer les recouvrements est bas{\'e}e sur le clonage de processus, apr{\`e}s avoir {\'e}voqu{\'e} le principe de mise en oeuvre, nous exposons les difficult{\'e}s rencontr{\'e}es pour obtenir un r{\'e}el recouvrement des entr{\'e}es/sorties. Par extension, nous pr{\'e}sentons alors la factorisation LU out-of-core et l'inversion matricielle out-of-core dans lesquelles nous avons mis en place le syst{\`e}me de recouvrement ainsi que les r{\'e}sultats obtenus. Une derni{\`e}re partie pr{\'e}sente l'int{\'e}gration de ces travaux dans Scilab//, un outil de calcul num{\'e}rique. La participation {\`a} ce projet de l'INRIA, permet d'utiliser la biblioth{\`e}que out-of-core de ScaLAPACK avec une interface conviviale, et, d'accro{\^\i}tre ainsi le champ d'application de Scilab//. Nous pr{\'e}sentons Scilab et les techniques permettant d'interfacer des modules externes compil{\'e}s. Nous pr{\'e}sentons ensuite Scilab//, et exposons l'extension que nous avons r{\'e}alis{\'e} afin de proposer une version out-of-core de Scilab. Nous menons ensuite une {\'e}tude afin de proposer des optimisations pour les traitements out-of-core. },
author = {Caron, Eddy},
keywords = {Out-of-core},
month = {14} # dec,
note = {hal number: tel-01444591},
postscript = {http://www.ens-lyon.fr/~ecaron/biblio/papers/these_caron.ps.gz},
school = {Universit{\'e} de Picardie Jules Verne},
title = {Calcul num{\'e}rique sur donn{\'e}es de grande taille},
type = {Th{\`e}se},
url = {https://tel.archives-ouvertes.fr/tel-01444591},
year = {2000}
}