  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 hierarchical 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.

Distributed, Parallel, and Cluster Computing