| 异构环境中Fork-Join任务图的调度算法 |
| |
| 引用本文： | 张建军,宋业新,黄登斌.异构环境中Fork-Join任务图的调度算法[J].计算机工程与设计,2010,31(3). |
| |
| 作者姓名： | 张建军 宋业新 黄登斌 |
| |
| 作者单位： | 1. 华中科技大学,计算机学院,湖北,武汉,430074;海军工程大学,理学院,湖北,武汉,430033
2. 海军工程大学,理学院,湖北,武汉,430033 |
| |
| 基金项目： | 国家自然科学基金项目，海军工程大学自然科学基金项目 |
| |
| 摘 要： | 目前已有的Fork-Join任务图的调度算法大多假定处理机为同构的,而没有考虑实际应用中处理机的异构性以及节省处理机的问题,导致算法在具体应用中效率较低.因此,对Fork-Join任务图的调度问题进行研究,提出了一个基于异构环境的贪心调度算法,该算法具有高的加速比和总体效率,其时间复杂度为O(v~2),其中,v表示任务集中任务的个数.实验结果表明,相比其它算法,该算法具有较短的调度长度、较短的完成时间,使用的处理机数较少,具有更强的实用性.
|
| 关 键 词： | Fork-Join任务图 异构性 任务复制 贪心算法 调度长度 关键任务 加速比 |
Task scheduling algorithm for Fork-Join task graphs in heterogeneous environment |
| |
| ZHANG Jian-jun,SONG Ye-xin,HUANG Deng-bin.Task scheduling algorithm for Fork-Join task graphs in heterogeneous environment[J].Computer Engineering and Design,2010,31(3). |
| |
| Authors: | ZHANG Jian-jun SONG Ye-xin HUANG Deng-bin |
| |
| Affiliation: | ZHANG Jian-jun 1,2,SONG Ye-xin 2,HUANG Deng-bin 2 (1.College of Computer Science , Technology,Huazhong University of Science , Technology,Wuhan 430074,China,2.College of Science,Naval University of Engineering,Wuhan 430033,China) |
| |
| Abstract: | Many previous scheduling algorithms for Fork-Join task graphs assumed homogeneous processors,while ignoring the heterogeneity of processors and the economization on processors in real applications,which led to low efficiency in real applications.A heterogeneity based greedy algorithm for scheduling Fork-Join task graphs is presented,which can generate a schedule with high speedup and efficiency.The time complexity of the proposed algorithm is 2,where is the number of tasks.Simulation results show that the p... |
| |
| Keywords: | Fork-Join task graph heterogeneity task duplication greedy algorithm scheduling length critical task speedup |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
