全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

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

DOI: 10.3724/SP.J.1004.2012.01870, PP. 1870-1879

Keywords: 异构计算环境,信息物理融合系统,有向无环图,任务调度,表调度,静态任务

Full-Text   Cite this paper   Add to My Lib

Abstract:

?针对异构环境并行计算的静态任务调度问题,以最小化有向无环图(Directedacyclicgraph,DAG)的执行跨度为目标,改变HEFT(Heterogeneousearliestfinishtime)算法中任务上行权重的计算方法,获得更加合理的任务顺序排列,提出了一种最早完成时间优先的表调度算法IHEFT(Improvementheterogeneousearliestfinishtime).该算法在计算任务的上行权重时,分别计算该任务分配给不同资源的上行权重,取其最小值,比使用所有资源对该任务的平均处理时间进行计算的HEFT算法更为准确.确定任务的处理顺序后采用最早完成时间越小越优先的策略将任务分配给最优资源,并使得任务的开始执行时间和结束时间满足DAG中有向边的通讯时间约束.通过使用部分文献中的算例数据以及随机生成满足一定结构要求的DAG进行算法测试,将IHEFT与HEFT,CPOP(Critical-path-on-a-processor)和LDCP(Longestdynamiccriticalpath)进行了比较,结果显示IHEFT算法更有效,而且时间复杂度较低.

References

[1]  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
[2]  Ullman J D. NP-complete scheduling problems. Journal of Computer and System Sciences, 1975, 10(3): 384-393
[3]  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)
[4]  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)
[5]  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
[6]  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
[7]  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
[8]  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
[9]  Omara F A, Arafa M M. Genetic algorithms for task scheduling problem. Journal of Parallel and Distributed Computing, 2010, 70(1): 13-22
[10]  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
[11]  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
[12]  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
[13]  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
[14]  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)
[15]  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
[16]  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)
[17]  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
[18]  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
[19]  Gacias B, Artigues C, Lopez P. Parallel machine scheduling with precedence constraints and setup times. Computers and Operations Research, 2010, 37(12): 2141-2151
[20]  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
[21]  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
[22]  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)
[23]  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
[24]  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
[25]  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
[26]  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
[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)

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133