Scalable hierarchical scheduling for multiprocessor systems using adaptive feedback-driven policies

Abstract—This work addresses the problem of allocating resource-intensive parallel jobs on multicore- and multiprocessor-based systems, where the performance gains largely depend on effectively exploiting application parallelization across the avail-able parallel computing resources. The objective is to find efficient allocation approaches that minimize the parallel jobs ’ completion time, i.e. makespan. Integrating feedback-driven adaptive strate-gies, we present a general hierarchical scheduling framework and show that two hierarchical scheduling algorithms: ABG-DS and AG-DS achieve scalable performance in term of makespan regardless of the number of hierarchical levels. Specifically, we prove that both ABG-DS and AG-DS have O(1)-competitive ratio for batched parallel jobs. Extending an existing tool, called Malleable-Lab, we evaluate the performance and scalability of our proposed algorithms and compare with that of well-known EQUI-based strategies. The simulation results demonstrate that both ABG-DS and AG-DS generally outperforms EQUI-EQUI for a wide range of parallel workloads. Moreover, feedback-driven adaptive scheduling algorithms show better scalability when the number of levels increases in the scheduling hierarchy. I