Scheduling using genetic algorithms

Considers the scheduling of mixed task- and data-parallel modules comprising computation and communication operations. The program generation starts with a specification of the maximum degree of task- and data-parallelism of the method to be implemented. In several derivation steps, the degree of parallelism is adapted to a specific distributed memory machine. We present a scheduling derivation step based on the genetic algorithm paradigm. The scheduling takes not only decisions on the execution order (independent modules can be executed consecutively by all processors available or concurrently by independent groups of processors) but also on appropriate data distributions and task implementation versions. We demonstrate the efficiency of the algorithm by an example from numerical analysis