并行同构系统中任务调度冗余消除方法研究

摘要

并行分布式计算机系统中的多任务调度是一个NP完全问题.大多数基于复制的启发式调度算法复制当前节点前驱节点时会产生冗余副本.在CPFD/SD算法的基础上提出一种新的消除冗余副本(ERD)的方法,算法在调度的过程中记录下每个节点所使用数据的来源和产生结果的去向,调度完成后利用记录下的信息自底向上地消除冗余的副本节点.算法分析结果表明,这种算法可以有效减少现有的基于复制的任务调度算法的副本数量和处理机的使用数量.