基于DAG模型的高效并行任务调度算法研究

在当今的网络并行计算环境中，并行任务调度已经成为并行处理和高性能计算领域中极其重要的关键技术，不恰当的调度甚至会抵消任务并行化所带来的收益。基于此，本文研究了一种以带节点权值和边权值的有向无环图来表示并行任务的DAG调度问题。一般情况下，这种DAG调度是个NP完全问题。 国内外的研究学者在该领域进行了广泛而深入的研究。但是随着网络硬件技术和处理器技术的飞速发展，该领域仍然存在不少亟待解决的关键问题。在这种新形势下，本文主要研究了其中的三个关键技术，它们是：其一，针对非线性聚簇下怎样高效调度独立任务问题，本文提出了一种基于最大并行度的独立任务调度算法MPD；其二，针对某些调度算法虽然性能良好但复杂度高，或者某些调度算法虽然复杂度低但性能不佳的问题，本文提出了一种在性能和复杂度间进行折衷的DAG调度算法EZDCP，从而使得DAG调度算法更加实用；最后本文还提出了一个较为系统性的DAG粒度理论，并且根据fork和join图，本文用数学方法严格证明了细粒度下非线性聚簇要优于线性聚簇。该粒度理论对指导调度算法的选取和进行调度算法的性能评估起着重要的作用。通过对一些基准测试DAG图的实例分析，本文的两个调度算法性能要优于已有的同类DAG调度算法。