Runtime and energy constrained work scheduling for heterogeneous systems

Heterogeneous hardware systems consisting of CPUs and different types of accelerators are wide-spread nowadays for large supercomputers as well as smaller cluster systems in the field of high-performance computing (HPC). A fundamental problem for such systems is the distribution of the workload of data-parallel HPC applications onto heterogeneous compute devices. The distribution of the workload tries to achieve (1) a well-balanced and runtime efficient program execution and (2) energy efficiency. However, typically both goals are contradicting objectives resulting in a challenging bi-criteria optimization problem. In this paper, we present an efficient scheduling algorithm that assigns work bundles to heterogeneous compute devices and determines an optimal solution for minimizing the makespan of a task under a given energy constraint. Work bundles are equal-sized, medium-grained data chunks that are obtained by partitioning the workload of data-parallel applications. Energy consumption and execution time for processing a single work bundle varies depending on the respective compute device and is essential for beneficial scheduling strategies. We formulate our optimization problem as an Integer Linear Program and devise an efficient bisection algorithm, which computes optimal solutions with logarithmic-time complexity. Experiments emphasize the efficiency of our algorithm. Further we investigate the two-dimensional optimization space and sketch an algorithm for Strong Pareto Optimal solutions.