摘要
目前已有的Fork-Join任务图的调度算法大多假定处理机为同构的,而没有考虑实际应用中处理机的异构性以及节省处理机的问题,导致算法在具体应用中效率较低。因此,对Fork-Join任务图的调度问题进行研究,提出了一个基于异构环境的贪心调度算法,该算法具有高的加速比和总体效率,其时间复杂度为2,其中,表示任务集中任务的个数。实验结果表明,相比其它算法,该算法具有较短的调度长度、较短的完成时间,使用的处理机数较少,具有更强的实用性。
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 proposed algorithm has better scheduling length,less completion time and less number of processors than other compared algorithms and so more practicable.
出处
《计算机工程与设计》
CSCD
北大核心
2010年第3期486-490,共5页
Computer Engineering and Design
基金
国家自然科学基金项目(60273075)
海军工程大学自然科学基金项目(HGDJJ05005)
