Adaptive statistical scheduling of divisible workloads in heterogeneous systems

This article presents a statistical approach to the scheduling of divisible workloads. Structured as a task farm with different scheduling modes including adaptive single and multi-round scheduling, this novel divisible load theory approach comprises two phases, calibration and execution, which dynamically adapt the installment size and number. It introduces the concept of a generic installment factor based on the statistical dispersion of the calibration times of the participating nodes, which allows automatic determination of the number and size of the workload installments. Initially, the calibration ranks processors according to their fitness and determines an installment factor based on how different their execution times are. Subsequently, the execution iteratively distributes the workload according to the processor fitness, which is continuously re-assessed throughout the program execution. Programmed as an adaptive algorithmic skeleton, our task farm has been successfully evaluated for single-round scheduling and generic multi-round scheduling using a computational biology parameter-sweep in a non-dedicated multi-cluster system.