Repartition dynamique de donnees regulieres pour des machines MIMD homogenes a memoire distribuee
Abstract
This paper reports a simple strategy for dynamically load balancing of regular data on homogeneous Distributed Memory MIMD computers with static interconnexion network. That is data in which each unit can be processed independently and requires the same time on each processor. This strategy is based upon a global knowledge of the initial distribution of the data' load obtained by a generalized prefix computation on a spanning tree of the graph of the interconnexion network of the processors; this strategy is then usable for any topology. We prove also that the data exchangesinduced by this strategy lead to the balance of the data' load in time O(min P kP kK(P )), where P is a maximum weight path of the spanning tree, kP k its length and K(P ) the maximum weight of its arcs.