Abstract FR:

Le parallelisme consiste a faire usage de plusieurs ressources simultanement, afin de diminuer le temps d'execution d'un calcul, ou de resoudre des problemes de plus grande taille. Mais le temps de communication entre les processeurs ainsi que le desequilibre de charge, rendent complexe la parallelisation d'un code. Ainsi, afin de reduire la latence et d'augmenter la localite, on va chercher a regrouper certains calculs, c'est a dire a augmenter la granularite. C'est le principe du pavage, technique d'optimisation que nous abordons dans la premiere partie de cette these, dans differents contextes : soit le nid de boucles ne contient que des dependances internes, et nous cherchons la taille et la forme de tuiles optimales minimisant le chemin critique du graphe des taches ; soit le nid de boucles ne contient que des dependances externes, et nous cherchons la forme de tuiles qui optimise la reutilisation des donnees rapatriees ; nous abordons aussi le probleme de pavage pour des tuiles non atomiques dans lesquelles les taches sont reordonnancees afin de minimiser la latence d'execution. Les problemes lies a la parallelisation se posent de maniere encore plus complexe lorsque les ressources sont heterogenes. Nous abordons ainsi dans une seconde partie le probleme sous une approche plus algorithmique, visant la constitution de librairies de calculs lineaires sur ressources heterogene. Cela pose un certain nombre de problemes d'optimisation geometriques, souvent montres comme etant np-complet, et pour lesquels nous proposons un certain nombre de solutions heuristiques garanties.