Towards developing universal dynamic mapping algorithms

Abstract

We investigate the problem of mapping dynamically generated tasks onto the processors of an MIMD-system. Our main concern is to construct an algorithm which can be integrated in distributed runtime systems like PVM or MPI. Existing methods are often not adjustable to different architecture- and application-demands. Even if they are, the adjustment has to be done manually via time-consuming experiments. A universally applicable strategy has to adjust its parameters automatically according to hardware- and application-characteristics. We concentrate on bidding-algorithms which check the load of K randomly selected processors before placing a task. The analysis of this method is based on a model which allows predicting the behavior of the scheduler. Especially for a large number n of processes it is possible to show that the scheduling behaviour becomes independent of n. As a result we derive optimal K-values for different classes of application/architecture-characteristics. Furthermore, we investigate values of K which guarantee certain execution-times of the application with a given probability.