论文部分内容阅读
计算技术和网络技术的飞速发展,极大地促进了基于网络环境的科学应用研究。许多应用领域对计算能力的要求越来越高,单台计算机已很难满足计算需求。由多处理机构建的高性能计算系统已成为计算技术发展的必然,然而在这种系统环境下调度任意结构并行任务并获取最优解的问题仍然是NP完全难题。表调度算法是解决此类问题的一种经典启发式任务调度算法,具有调度性能较好,时间复杂度较低等优点。但经典表调度算法假定目标处理机全互连,以及调度节点时忽略节点之间的通信,显然不符合任意处理机网络计算环境的需求。因为对于任意处理机网络拓朴结构的异构系统,各任务之间的通信竞争不可忽略,这种任务通信对整个并行应用程序的执行有重要影响。因而,考虑通信竞争的调度算法是提高并行分布式计算系统实际性能的重要途径之一。本文研究工作主要方法是在调度算法中考虑通信竞争,即调度任务时同时考虑节点和通信边的调度。为了实现调度目标,提出一个基于最短路径搜索算法的最早通信完成路径查找算法(EFCS),采用插入式链路实现策略,以达到通信边的动态调度;对于任意处理机网络环境下的任务优先级计算问题,受HEFT算法启发提出递归优先权计算公式,并且按非升序排列获得各任务优先级。同时为了降低算法执行时间,采用OpenMP实现算法的并行化,理论分析表明并行算法可达到的加速比为O(PPE)。以随机产生程序任务图和现实中的实际应用程序为数据来源,在两类不同的任意处理机网络目标系统上进行了模拟实验。结果表明本算法明显优于考虑通信竞争的静态表调度算法和不考虑通信竞争的表调度算法,特别是在高通信率应用程序中优势更为明显。