Yuxiong He, Hongyang Sun, and Wen-Jing Hsu
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 Pmax 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/Pmax)- 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.