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

被引:5
作者
朱晓敏 [1 ]
陆佩忠 [1 ]
机构
[1] School of Computer Science,Fudan University
基金
中国国家自然科学基金;
关键词
clusters; scheduling; multi-dimensional; heterogeneous; real-time; makespan;
D O I
暂无
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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.
引用
收藏
页码:434 / 446
页数:13
相关论文
共 8 条
[1]   集群软件无线电系统中实时信号处理调度研究 [J].
朱晓敏 ;
陆佩忠 .
软件学报, 2009, 20 (03) :766-778
[2]   A technique for adaptive scheduling of soft real-time tasks [J].
Beccari, G ;
Caselli, S ;
Zanichelli, F .
REAL-TIME SYSTEMS, 2005, 30 (03) :187-215
[3]   A dynamic and reliability-driven scheduling algorithm for parallel real-timejobs executing on heterogeneous clusters [J].
Qin, X ;
Jiang, H .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2005, 65 (08) :885-900
[4]   Non-evolutionary algorithm for scheduling dependent tasks in distributed heterogeneous computing environments [J].
Boyer, WF ;
Hura, GS .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2005, 65 (09) :1035-1046
[5]   Fault-tolerant scheduling for real-time embedded control systems [J].
Yang, CH ;
Deconinck, G ;
Gui, WH .
JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY, 2004, 19 (02) :191-202
[6]   Dynamic mapping of a class of independent tasks onto heterogeneous computing systems [J].
Maheswaran, M ;
Ali, S ;
Siegel, HJ ;
Hensgen, D ;
Freund, RF .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1999, 59 (02) :107-131
[7]  
Dynamic scheduling ofparallel jobs with QoS demands in multiclusters and grids .2 Ligang He,Jarvis S A,Spooner D P,et al. Proceedings Fifth IEEE/ACM International Workshop . 2004
[8]  
Multi-dimensional scheduling scheme for QoSaware aware real-time applications on heterogeneous clusters .2 Zhu X,Lu P. Proc.10th IEEE Int.Conf.High Performance Computing and Communications . 2008