处理顺序约束的信息物理融合系统静态任务表调度算法

王小乐; 黄宏斌; 邓苏

doi:10.3724/SP.J.1004.2012.01870

处理顺序约束的信息物理融合系统静态任务表调度算法

doi: 10.3724/SP.J.1004.2012.01870

1.
国防科学技术大学信息系统工程重点实验室长沙 410073

详细信息

通讯作者:
王小乐

计量
- 文章访问数: 1843
- HTML全文浏览量: 89
- PDF下载量: 1151
- 被引次数: 0
出版历程
- 收稿日期: 2011-06-27
- 修回日期: 2012-07-09
- 刊出日期: 2012-11-20

List Scheduling Algorithm for Static Task with Precedence Constraints for Cyber-physical Systems

1.
Science and Technology on Information Systems Engineering Laboratory, National University of Defense Technology, Changsha 410073

摘要

摘要: 针对异构环境并行计算的静态任务调度问题,以最小化有向无环图 (Directed acyclic graph, DAG)的执行跨度为目标,改变HEFT (Heterogeneous earliest finish time)算法中任务上行权重的计算方法, 获得更加合理的任务顺序排列,提出了一种最早完成时间优先的表调度算法IHEFT (Improvement heterogeneous earliest finish time).该算法在计算任务的上行权重时, 分别计算该任务分配给不同资源的上行权重,取其最小值,比使用所有资源对该任务的平均处理时间进行计算的HEFT算法更为准确. 确定任务的处理顺序后采用最早完成时间越小越优先的策略将任务分配给最优资源,并使得任务的开始执行时间和结束时间满足DAG中有向边的通讯时间约束.通过使用部分文献中的算例数据以及随机生成满足一定结构要求的DAG进行算法测试,将IHEFT与HEFT, CPOP (Critical-path-on-a-processor)和LDCP (Longest dynamic critical path)进行了比较,结果显示IHEFT算法更有效,而且时间复杂度较低.
- 异构计算环境 /
- 信息物理融合系统 /
- 有向无环图 /
- 任务调度 /
- 表调度 /
- 静态任务
Abstract: In this paper, we study the static task scheduling problems in distribution heterogeneous computing environment such as cyber-physical system (CPS). We present a list scheduling algorithm named improvement heterogeneous earliest finish time (IHEFT) algorithm for minimizing makespan of the precedence constrained applications which can be modelled as a directed acyclic graph (DAG). We acquire a better task list by changing the task's upward rank weight calculation method in heterogeneous earliest finish time (HEFT). In IHEFT, the different computing time not the average computing time in each resource is considered for each task when calculating the upward rank weight. After the priority list is determined, tasks are assigned to the resource based on the earliest finish time first policy and the precedence constraints. Comparison on performance evaluation using both the case data in the recent literature and randomly generated DAGs show that the IHEFT list scheduling algorithm has outperformed the HEFT, CPOP (Critical-path-on-a-processor) and LDCP (Longest dynamic critical path) algorithms both in makespan and scheduling time consumed.
- Heterogeneous computing environment /
- cyber-physical systems (CPS) /
- directed acyclic graph (DAG) /
- task scheduling /
- list scheduling /
- static task

HTML全文

参考文献(1)

[1]

Wen Jing-Rong, Wu Mu-Qing, Su Jing-Fang. Cyber-physical system. Acta Automatica Sinica, 2012, 38(4): 507-517(温景容, 武穆清, 宿景芳. 信息物理融合系统. 自动化学报, 2012, 38(4): 507-517)[2] Lee E A. Cyber physical systems: design challenges. In: Proceedings of the 11th IEEE International Symposium on Object Component Oriented Real-Time Distributed Computing. Orlando, USA: IEEE, 2008. 363-369[3] Tang X Y, Li K L, Li R F, Veeravalli B. Reliability-aware scheduling strategy for heterogeneous distributed computing systems. Journal of Parallel and Distributed Computing, 2010, 70(9): 941-952[4] Ullman J D. NP-complete scheduling problems. Journal of Computer and System Sciences, 1975, 10(3): 384-393[5] Meng Xian-Fu, Liu Wei-Wei. A DAG scheduling algorithm based on selected duplication of precedent tasks. Journal of Computer-Aided Design and Computer Graphics, 2010, 22(6): 1056-1062 (孟宪福, 刘伟伟. 基于选择性复制前驱任务的DAG调度算法. 计算机辅助设计与图形学学报, 2010, 22(6): 1056-1062)[6] Xie Zhi-Qiang, Xin Yu, Yang Jing. Machine-driven integrated scheduling algorithm with rollback-preemptive. Acta Automatica Sinica, 2011, 37(11): 1332-1343(谢志强, 辛宇, 杨静. 可回退抢占的设备驱动综合调度算法. 自动化学报, 2011, 37(11): 1332-1343)[7] Yin Jin-Yong, Gu Guo-Chang, Zhao Jing. Dynamic scheduling algorithm for hybrid real-time tasks with precedence constraints. Computer Integrated Manufacturing Systems, 2010, 16(2): 411-416, 422(殷进勇, 顾国昌, 赵靖. 优先约束的混合实时任务动态调度算法. 计算机集成制造系统, 2010, 16(2): 411-416, 422)[8] Topcuoglu H, Hariri S, Wu M Y. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260-274[9] Daoud M I, Kharma N. A high performance algorithm for static task scheduling in heterogeneous distributed computing systems. Journal of Parallel and Distributed Computing, 2008, 68(4): 399-409[10] Tchiboukdjian M, Trystram D, Roch J L, Bernard J. List Scheduling: the Price of Distribution, Technical Report inria-00458133, Centre de recherche INRIA Grenoble, France, 2010[11] Falzon G, Li M Z. Enhancing list scheduling heuristics for dependent job scheduling in grid computing environments. The Journal of Supercomputing, 2012, 59(1): 104-130[12] Lan Z, Sun S X. Scheduling algorithm based on critical tasks in heterogeneous environments. Journal of Systems Engineering and Electronics, 2008, 19(2): 398-404[13] Gacias B, Artigues C, Lopez P. Parallel machine scheduling with precedence constraints and setup times. Computers and Operations Research, 2010, 37(12): 2141-2151[14] Tang X Y, Li K L, Liao G P, Li R F. List scheduling with duplication for heterogeneous computing systems. Journal of Parallel and Distributed Computing, 2010, 70(4): 323-329[15] Lee Y C, Zomaya A Y. A novel state transition method for metaheuristic-based scheduling in heterogeneous computing systems. IEEE Transactions on Parallel and Distributed Systems, 2008, 19(9): 1215-1223[16] Omara F A, Arafa M M. Genetic algorithms for task scheduling problem. Journal of Parallel and Distributed Computing, 2010, 70(1): 13-22[17] Yang J D, Xu H, Pan L, Jia P F, Long F, Jie M. Task scheduling using Bayesian optimization algorithm for heterogeneous computing environments. Applied Soft Computing, 2011, 11(4): 3297-3310[18] Meng Xian-Fu, Wang Min. Peer to peer task scheduling based on improved immune clonal selection algorithm. Computer Integrated Manufacturing Systems, 2009, 15(9): 1795-1802(孟宪福, 王敏. 基于改进免疫克隆选择的对等网络任务调度机制. 计算机集成制造系统, 2009, 15(9): 1795-1802)[19] Tang X Y, Li K L, Liao G　P, Fang K, Wu F. A stochastic scheduling algorithm for precedence constrained tasks on Grid. Future Generation Computer Systems, 2011, 27(8): 1083-1091[20] Wen Y, Xu H, Yang J D. A heuristic-based hybrid genetic-variable neighborhood search algorithm for task scheduling in heterogeneous multiprocessor system. Information Sciences, 2011, 181(3): 567-581[21] Daoud M I, Kharma N. A hybrid heuristic-genetic algorithm for task scheduling in heterogeneous processor networks. Journal of Parallel and Distributed Computing, 2011, 71(11): 1518-1531[22] Page A J, Keane T M, Naughton T J. Multi-heuristic dynamic task allocation using genetic algorithms in a heterogeneous distributed system. Journal of Parallel and Distributed Computing, 2010, 70(7): 758-766[23] Swiecicka A, Seredynski F, Zomaya A Y. Multiprocessor scheduling and rescheduling with use of cellular automata and artificial immune system support. IEEE Transactions on Parallel and Distributed Systems, 2006, 17(3): 253-262[24] Canon L C, Jeannot E. Evaluation and optimization of the robustness of DAG schedules in heterogeneous environments. IEEE Transactions on Parallel and Distributed Systems, 2010, 21(4): 532-546[25] Chaudhuri P, Elcock J. Scheduling DAG-based applications in multicluster environments with background workload using task duplication. International Journal of Computer Mathematics, 2010, 87(11): 2387-2397[26] Vianna B A, Fonseca A A, Moura N T, Menezes L T, Mendes H A, Silva J A, Boeres C, Rebello V E F. A tool for the design and evaluation of hybrid scheduling algorithms for computational grids. In: Proceedings of the 2nd Workshop on Middleware for Grid Computing. Toronto, Canada: ACM, 2004. 41-46[27] Niu Jian-Jun, Deng Zhi-Dong, Li Chao. Distributed scheduling approaches in wireless sensor network. Acta Automatica Sinica, 2011, 37(5): 517-528(牛建军, 邓志东, 李超. 无线传感器网络分布式调度方法研究. 自动化学报, 2011, 37(5): 517-528)

施引文献

资源附件(0)

访问统计