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.