Scheduling Algorithms for new Emerging Applications

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

Communication-Aware Processor Allocation for Supercomputers

SpeakerCindy Phillips

We give processor-allocation algorithms for parallel jobs on grid architectures, where the objective is to select processors from a set of available processors to minimize the average number of communication hops. We present a natural approximation algorithm and show that it is a 7/4-approximation for 2D grids. In d dimensions, the approximation guarantee is 2-(1/2d), which is tight. We will describe experimental results comparing this algorithm to other strategies on a trace of a real job stream. We will describe the impact of this research at Sandia National Laboratories.