Scalable Hierarchical Scheduling for Malleable Parallel Jobs on Multiprocessor-based Systems

Abstract: The proliferation of multi-core and multiprocessor-based computer systems has led to explosive development of parallel applications and hence the need for efficient schedulers. In this paper, we study hierar-chical scheduling for malleable parallel jobs on multiprocessor-based systems, which appears in many distributed and multilayered computing environments. We propose a hierarchical scheduling algorithm, named AC-DS, that consists of a feedback-driven adaptive scheduler, a desire aggregation scheme and an efficient resource allocation policy. From theoretical perspective, we show that AC-DS has scalable performance regardless of the number of hierarchical levels. In particular, we prove that AC-DS achieves O(1)-competitiveness with respect to the overall completion time of the jobs, or the makespan. A detailed malleable job model is developed to experimentally evaluate the effectiveness of the proposed scheduling algorithm. The results verify the scalability of AC-DS and demonstrate that AC-DS outperforms other strategies for a wide range of parallel workloads