Abstracts

Avec lmergence du calcul haute-performance (HPC) et des applications Big Data, de nouvelles problmatiques cruciales sont apparues. Parmi elles on trouve le problme du transfert de donnes, cest--dire des communications entre machines, qui peut gnerer des dlais lors de gros calculs en plus davoir un impact sur la consommation nergtique. La rplication, que ce soit de tches ou de fichiers, est un facteur qui accrot ces communications, tout en tant un outil quasi-indispensable pour amliorer le paralllisme du calcul et la rsistance aux pannes. Dans cette thse nous nous intressons la rplication de fichiers et son impact sur les communications au travers de deux problmes. Dans le premier, la multiplication de matrices en parallle, le but est de limiter autant que possible ces rplications pour diminuer la quantit de donnes dplaces. Dans le second, lordonnancement de la phase Map de MapReduce, il existe une rplication initiale quil faut utiliser au mieux afin dobtenir lordonnancement le plus rapide ou entranant le moins de cration de nouvelles copies. En plus de la rplication, nous nous intressons aussi la comparaison entre stratgies dordonnancement statiques (allocations faites en amont du calcul) et dynamiques (allocations faites pendant le calcul) sur ces deux problmes avec pour objectif de crer des stratgies hybrides mlangeant les deux aspects. Pour le premier problme, le produit de matrices en parallle, nous nous ramenons un problme de partition de carr o lquilibrage de charge est donn en entre. Cet quilibrage donn, le but est de minimiser la somme des semi-paramtres des rectangles couvrant des zones ainsi crs. Ce problme a dj t tudi par le pass et nous dmontrons de nouveaux rsultats. Nous proposons ainsi deux nouveaux algorithmes dapproximation, lun fond sur une stratgie rcursive et lautre sur lusage dune courbe fractale. Nous prsentons galement une modlisation alternative, fonde sur un problme similaire de partition de cube, dont nous prouvons la NP-compltude tout en fournissant deux algorithmes dapproximation. Pour finir, nous ralisons galement une implmentation pratique du produit de matrices en utilisant nos stratgies dallocation grce la librairie StarPU. Les rsultats exprimentaux montrent une amlioration du temps de calcul ainsi quune diminution significative des transferts de donnes lorsquon utilise une stratgie statique dallocation couple une technique de vol de tches. Pour le second problme, lordonnancement de la phase Map de MapReduce, plusieurs copies des fichiers dentre sont distribues parmi les processeurs disponibles. Le but ici est de faire en sorte que chaque tche soit attribue un processeur possdant son fichier dentre tout en ayant le meilleur temps de calcul total. Une autre option tudie est dautoriser les tches nonlocales (attribus des processeurs ne possdant pas leurs fichiers dentre) mais den limiter le nombre. Dans cette thse nous montrons premirement quunAdvisors/Committee Members: Beaumont, Olivier (thesis director).