一个调度Fork-Join任务图的最优算法

• 作者: 刘干 李庆华 杨世达 蒋盛益 阮幼林
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 任务调度 任务复制 Fork-Join任务图 加速比
• 年，卷（期）: 2005,（5）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 684-690
• 页数: 7页
• 分类号: TP301
• 语种: 中文

摘要

Fork-Join任务图是一种并行处理的基本结构.虽然许多算法在任务满足某些条件时能产生最优调度,但往往没有考虑节省处理器个数和减少任务集的总完成时间,从而降低算法的加速比和效率.因此,提出一种基于任务复制的平衡调度算法,其时间复杂度为O(vq+vlogv),v和q分别表示任务集中任务的个数和使用的处理器个数.通过分析已用处理器的负载和空闲时间段,把任务尽量分配到已用的处理器上以均衡负载,从而提高其利用率.实验结果表明,该算法的加速比和总体效率优于其他算法.因此,该算法对于高性能应用程序的调度是一个较好的选择.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李庆华	华中科技大学计算机科学与技术学院	113	1366	21.0	30.0
2	蒋盛益	华中科技大学计算机科学与技术学院	16	326	10.0	16.0
3	刘干	华中科技大学电子与信息工程系	13	100	6.0	10.0
4	杨世达	华中科技大学计算机科学与技术学院	6	77	5.0	6.0
5	阮幼林	华中科技大学计算机科学与技术学院	12	115	6.0	10.0