Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

Data Redistribution between Distant Clusters using both Local and Wide Area Networks

SpeakerFrédéric Wagner

In recent years, the apparition of high performance networks has enabled the emergence of large scale parallel computing. However, communications times between distant sites are far from being negligible and can represent a problem for high performance applications, in particular applications needing frequent data transfers such as code coupling applications.

We study here the message scheduling problem between distant clusters when it is possible to use, on each cluster, a local network to achieve the redistribution. The use of such a local network helps in balancing the amount of data to be transfered among the participating nodes.

We propose an algorithm that applies to two different cases.

  1. A steady-state redistribution where the communication pattern is repeating. Under this case, our algorithm is asymptotically optimal.
  2. When the redistribution pattern is scheduled only once this algorithm is a 3-approximation algorithm.