适应多核处理器的任务调度研究

多核并行系统中的任务调度是根据一定的调度规则和策略,将复杂程序的所有任务按照一定执行时序分配到并行分布的多个内核上,并行处理任务。这个问题是强NP完全的,是最难的组合优化问题之一。各国学者对多核处理器上的任务调度技术开展了一些研究,提出了多种调度模型和算法,可是这些算法存在着调度效率低和不能适应处理器内核资源变化等问题,可见适应多核并行系统的任务调度问题仍然是一个不成熟的领域。本文研究的是多核处理器并行系统下的任务调度问题,既考虑了任务调度的执行效率,又考虑了调度结果能够按照处理器内核的具体数量调整的情况,具有重要的理论和实际意义。 针对目前任务调度算法调度时间长或复杂度高的问题,提出一种基于任务复制的调度算法。算法首先通过复制任务的方式将任务图转换成结构简单的join结构图;对join结构图采取一种调度策略:选择使join节点任务能够最早开始的方案,将join节点任务与其前驱节点任务形成调度组合,实现join节点任务开始时间的提前和各前驱节点任务到不同内核上并行执行,达到提高算法调度效率的目的。 针对目前算法在处理资源紧缺的情况下算法不能根据内核的具体数量调整的问题,本文提出了一种适应具体内核数的调度算法。该算法先将任务图分解为无关的执行序列,消除任务间的联系;然后为每个执行序列分配一个核。当内核数少于执行序列数时,采取策略合并执行序列以减少执行序列数。实现根据处理器内核的具体数量调度任务。 针对目前算法在处理资源充足的情况下核间通信开销大的问题,提出了一种消除核间通信的算法。算法先简化任务图为join结构图再逐个合并节点任务的方法,实现在保持较低时间复杂度和完成时间的同时,消除了核间通信开销。