An Efficient New Static Scheduling Heuristic for Accelerated Architectures

Heterogeneous architectures that use Graphics Processing Units (GPUs) for general computations, in addition to multicore CPUs, are increasingly common in high-performance computing. However many of the existing methods for scheduling precedence-constrained tasks on such platforms were intended for more diversely heterogeneous clusters, such as the classic Heterogeneous Earliest Finish Time (HEFT) heuristic. We propose a new static scheduling heuristic called Heterogeneous Optimistic Finish Time (HOFT) which exploits the binary heterogeneity of accelerated platforms. Through extensive experimentation with custom software for simulating task scheduling problems on user-defined CPU-GPU platforms, we show that HOFT can obtain schedules at least [Formula: see text] shorter than HEFT’s for medium-to-large numerical linear algebra application task graphs and around [Formula: see text] shorter on average for a large collection of randomly-generated graphs.