一个简单有效的任务调度算法

摘要

任务调度就是根据一定的调度规则和调度策略,把组成并行程序的一组任务按照一定执行时序分配到并行分布系统的多个计算节点上,以最小化并行应用程序的完成时间.当前,基于任务复制的调度已成为研究热点.任务复制是指在不同处理机上执行相同的任务,从而可以减少任务间的通讯时间.一般来说,基于任务复制的调度绝对优于不是基于任务复制的调度.然而,无论任务是否复制,多处理机相关任务调度问题始终是一个NP完全问题.现已有许多基于任务复制的调度算法在任务满足某些条件时能产生最优调度.任务复制可以通过任务的冗余减少通信时间，现已成为一种新的研究方法。当通信开销较小时，现已有许多基于任务复制的调度算法能产生最优调度。但其最优条件要么比较苛刻，要么比较复杂。因此，本文提出一个简单有效的新调度算法，不仅其最优条件简单、宽松，而且算法具有更小的时间复杂度O（dVIOgd），其中，V和d分别表示任务集中任务的个数和最大入度。