Heterogeneous Multiprocessor Scheduling with Differential Evolution

Krzysztof Rzadca (1, 2, 3) , Seredynski Franciszek (3)

1 ID-IMAG - Informatique et Distribution
2 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
3 PJIIT - Polish-Japanese Institute of Information Technology

The problem of scheduling a parallel program given by a Directed Acyclic Graph (DAG) of tasks is a well-studied area. We present a new approach which employs Differential Evolution to numerically optimize the priorities of tasks. Our algorithm starts with a number of acceptable solutions, results of different heuristics, and merges them to achieve better one in a small number of function evaluations. The algorithm outperforms both a number of greedy heuristics and a classical genetic algorithm on the most of the program graphs considered in our experiments.

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Krzysztof Rzadca, Seredynski Franciszek. Heterogeneous Multiprocessor Scheduling with Differential Evolution. 2005. ⟨hal-00005852⟩