论文部分内容阅读
随着CPU、GPU硬件技术和高速网络技术的发展,通过高速互连网络互连CPU、GPU构成的异构并行高性能计算系统越来越受欢迎。为了充分挖掘异构高性能计算系统的并行计算能力,大量研究工作致力于提出合理高效的任务调度策略。 任务调度算法指的是在满足任务依赖关系的前提下为任务图中的任务安排合适的执行顺序和执行处理器将任务图中的任务调度完毕,其目的在于降低整个应用的执行时间,现有的大部分任务调度算法大多通过优化任务的执行顺序来减少整个应用的调度长度而对任务的输入输出数据在互联网络上的通信代价优化问题关注相对较少。然而随着异构计算系统中处理器数目的急剧增长,互连网络上的通信耗费将逐渐成为整个异构高性能计算系统的性能瓶颈。 针对异构高性能计算系统中的通信耗费优化问题,本文提出了一种新的任务调度算法(Communication-aware Earliest Finish Time,CEFT)。CEFT具有表调度算法和任务复制调度算法相结合的特征,能检测到应用任务图中具有长通信权值的任务,并将具有长通信权值的两个任务调度到同一个处理上来消除任务之间的通信耗费。但是CEFT中存在通信感知因子的不确定性问题,为了解决此问题本文在CEFT算法的基础上提出了另外一个新的表调度和任务复制相结合的任务调度算法DBEFT(Dependency Ratio Binding Earliest Finish Time)。该算法能将具有长通信权值的两个任务捆绑成一个“大”的任务进行调度。DBEFT算法通过赋予具有高任务依赖率的任务更高的优先级来扩大任务间的并行性,通过充分重叠应用任务图中任务的计算权值和通信权值来提高异构调度系统中处理器资源的利用率。实验证明,CEFT算法和DBEFT算法无论是在时间性能指标SLR上还是在加速比等评价算法效率的指标上均优于同类具有相同时间复杂度的高水平任务调度算法。