Multi-Dimensional Scheduling for Real-Time Tasks on Heterogeneous Clusters |
| |
Authors: | Xiao-Min Zhu Pei-Zhong Lu |
| |
Affiliation: | (1) School of Computer Science, Fudan University, Shanghai, 200433, China |
| |
Abstract: | 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. |
| |
Keywords: | clusters scheduling multi-dimensional heterogeneous real-time makespan |
本文献已被 CNKI 万方数据 SpringerLink 等数据库收录! |
| 点击此处可从《计算机科学技术学报》浏览原始摘要信息 |
|
点击此处可从《计算机科学技术学报》下载全文 |
|