考虑通信竞争的任意处理机网络表调度算法

任务调度是高性能计算系统中的基本问题之一。解决此类NP难问题的经典启发式算法都假定目标处理机全互连,调度任务时可忽略节点间通信,这显然与实际计算环境不符。为此,文中提出一种在调度任务时同时考虑通信边调度的表调度算法。在边调度时,提出了一种基于最短路径搜索算法的最早通信完成路径查找算法(EFCS),并采用插入式链路策略实现通信边的动态调度,而对处理机网络异构环境下的任务优先级计算问题,受HEFT算法启发,提出异构系统递归优先权计算方法,按非升序排列获得各任务优先级。为了降低算法的执行时间,文中还提出了理论加速比为O(PPE)的并行算法。以随机产生程序任务图和DSP应用程序实例为数据源,在两类不同任意处理机网络目标系统上进行的模拟实验结果表明:本算法明显优于考虑通信竞争的静态表调度算法和不考虑通信竞争的表调度算法,特别是在高通信率应用程序中优势更明显。