Multi-Dimensional Scheduling for Real-Time Tasks on Heterogeneous Clusters

Multiple performance requirements need to be guaranteed in some real-time applications such as multimedia data processing and real-time signal processing in addition to timing constraints. Unfortunately, most conventional scheduling algorithms only take one or two dimensions of them into account. Motivated by this fact, this paper investigates the problem of providing multiple performance guarantees including timeliness, QoS, throughput, QoS fairness and load balancing for a set of independent tasks by dynamic scheduling. We build a scheduler model that can be used for multi-dimensional scheduling. Based on the scheduler model, we propose a heuristic multi-dimensional scheduling strategy, MDSS, consisting of three steps. The first step can be of any existing real-time scheduling algorithm that determines to accept or reject a task. In step 2, we put forward a novel algorithm MQFQ to enhance the QoS levels of accepted tasks, and to make these tasks have fair QoS levels at the same time. Another new algorithm ITLB is proposed and used in step 3. The ITLB algorithm is capable of balancing load and improving throughput of the system. To evaluate the performance of MDSS, we perform extensive simulation experiments to compare MDSS strategy with MDSR strategy, DASAP and DALAP algorithms. Experimental results show that MDSS significantly outperforms MDSR, DASAP and DALAP. Electronic supplementary material The online version of this article (doi: ) contains supplementary material, which is available to authorized users. This work is supported by the National Natural Science Foundation of China under Grant No. 60673082, and the Special Funds of Authors of Excellent Doctoral Dissertation in China under Grant No. 200084. The previous version appeared in Proceedings of the 10th IEEE International Conference on High Performance Computing and Communications (HPCC 2008), pp.205–212.