Optimal Workload Scheduling Algorithm for Data-Parallel Applications on Heterogeneous Platforms based on Dynamic Programming
Algorithme d’ordonnancement optimal basé sur la programmation dynamique pour les applications aux données parallèles sur des plates-formes hétérogènes
Abstract
This report discusses a new algorithm for makespan minimization on situations where the workload can be partitioned among heterogeneous resources. Without making any assumptions regarding the behavior or shape of the functions giving the execution time on a resource, we are able to provide optimal solutions with a dynamic programming algorithm in O(T 2 n) for a workload of T tasks and n heterogeneous resources. This report includes a short state of the art, the problem's model, the algorithm, and its optimality proof.
Origin : Files produced by the author(s)