Competitive two-level adaptive scheduling using resource augmentation

Abstract. As multi-core processors proliferate, it has become more im-portant than ever to ensure efficient execution of parallel jobs on multi-processor systems. In this paper, we study the problem of scheduling par-allel jobs with arbitrary release time on multiprocessors while minimizing the jobs ’ mean response time. We focus on non-clairvoyant scheduling schemes that adaptively reallocate processors based on periodic feed-backs from the individual jobs. Since it is known that no deterministic non-clairvoyant algorithm is competitive for this problem, we focus on resource augmentation analysis, and show that two adaptive algorithms, Agdeq and Abgdeq, achieve competitive performance using O(1) times faster processors than the adversary. These results are obtained through a general framework for analyzing the mean response time of any two-level adaptive scheduler. Our simulation results verify the effectiveness of Agdeq and Abgdeq by evaluating their performances over a wide range of workloads consisting of synthetic parallel jobs with different parallelism characteristics