Adaptive Scheduling of Parallel Jobs on Functionally Heterogeneous Resources

A parallel program usually incurs operations on multiple processing resources, interleaving computations, I/Os, and communications, where each task can only be executed on a processor of a matching category. Many parallel systems also embed special-purpose processors like vector units, floating-point co-processors, and various I/O processors. Presently, there is no provably good scheduling algorithm that ensures efficient use of multiple resources with functional heterogeneity.

This paper presents K-RAD, an algorithm that adaptively schedules parallel jobs on multiple processing resources without requiring prior information about the jobs, such as their release times and parallelism profiles. Let K denote the number of categories of heterogenous resources and P_max denote the maximum number of processors among all categories. We show that, for any set of jobs with arbitrary release times, K-RAD is (K +1-1/P_max)- competitive with respect to the makespan. This competitive ratio is provably the best possible for any non-clairvoyant deterministic algorithms for K-resource scheduling. We also show that K-RAD is (4K + 1 – 4K/(|J | + 1))- competitive with respect to the mean response time for any batched job set J . For the special case of K = 1, i.e., scheduling on homogeneous resources, the best existing mean response time bound for online non-clairvoyant algorithm is 2 + √ 3 ≅ 3.73 proved by Edmonds et al. in STOC’97. We show that K-RAD is 3-competitive with respect to the mean response time when K = 1, which offers the best competitive ratio to date.