Data Allocation Strategies for Dense Linear Algebra on two-dimensional Grids with Heterogeneous Communication Links

In this paper, we study the implementation of dense linear algebra kernels, such as matrix multiplication on 2D grids with homogeneous processors when the communication links between the processors are heterogeneous (i.e. the time to transfer a block of the matrix between two processors depends on these processors). We prove that finding the best allocation of the processors into a grid, with respect to the minimization of the communication overhead, is a NP-complete problem.Dans ce rapport, nous nous intéressons à la mise en oeuvre de noyaux d'algèbre linéaire dense, comme le produit de matrices, sur les grilles bidimensionnelles de processeurs identiques reliés par un réseau de communications non homogène (le temps nécessaire au transfert d'un bloc de matrices entre deux processeurs dépend de ces processeurs). Nous montrons que déterminer une organisation des processeurs en grille minimisant les communications est un problème NP-comple