异构环境中Fork-Join任务图的调度算法

摘要：

目前已有的Fork-Join任务图的调度算法大多假定处理机为同构的,而没有考虑实际应用中处理机的异构性以及节省处理机的问题,导致算法在具体应用中效率较低.因此,对Fork-Join任务图的调度问题进行研究,提出了一个基于异构环境的贪心调度算法,该算法具有高的加速比和总体效率,其时间复杂度为O(v~2),其中,v表示任务集中任务的个数.实验结果表明,相比其它算法,该算法具有较短的调度长度、较短的完成时间,使用的处理机数较少,具有更强的实用性.

关键词：Fork-Join任务图、异构性、任务复制、贪心算法、调度长度、关键任务、加速比

所属期刊栏目：31

分类号：TP316(计算技术、计算机技术)

资助基金：国家自然科学基金项目60273075;海军工程大学自然科学基金项目HGDJJ05005

在线出版日期：2010-04-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：486-490