How to optimize residual communications ?

Minimizing communications when mapping affine loop nests onto distributed memory parallel computers has already drawn a lot of attention. This paper focuses on the next step : as it is generally impossible to obtain a communication-free (or local) mapping, how to optimize the residual communications? We explain how to take advantage of macro-communications such as broadcasts, scatters, gathers or reductions or how to decompose general affine communications into simpler ones that can be performed more efficiently. We finally give a two-step heuristic that summarizes our approach : first minimize the number of nonlocal communications, then optimize residual affine communications using macro-communications or decompositions.Minimiser les communications lors du placement d'un nid de boucles affine sur une machine parallèle à mémoire distribuée a déjà été l'objet de beaucoup d'attention. Dans ce rapport, nous nous intéressons à l'étape suivante : puisqu'il est en général impossible d'obtenir un placement sans communication, comment optimiser les communications résiduelles ? Nous expliquons comment tirer avantage de macro-communications (diffusions, distributions, rassemblements ou réductions) ou comment décomposer des communications affines en communications plus simples et plus efficaces. Nous donnons finalement une heuristique en 2 étapes qui résume notre approche : d'abord minimiser le nombre de communications non locales , puis optimiser les communications résiduelles en utilisant des macro-communications ou des décompositions