面向多核异构并行系统的随机调度策略与算法研究

并行分布计算是当前计算机科学与技术的研究热点之一,是天气预报、核爆炸模拟以及金融服务等的重要解决手段.调度策略是保证系统性能的关键因素.针对多核异构系统的随机任务调度目前仍面临挑战.本课题拟采用多元线性回归方法,从理论和实验方面分析典型任务计算量的随机分布，确定其概率分布模型，借鉴利用基于同构系统独立任务随机调度的最新理论成果,建立非独立任务随机调度数学模型,使用凸二次线性规划或随机多维背包优化方法对其求解,以获得随机调度的理论近似结果；据此研究基于随机性的独立和非独立任务的调度策略与机制,提出基于任务执行时间的期望、方差与关键路径的随机调度算法,针对典型并行应用,构建多核异构系统随机调度实验平台对算法性能进行实验验证.本研究将不仅为随机调度算法的设计提供新的尝试,从而为并行系统应用效率的提高奠定基础，还将推进并行处理的研究深度，推动计算机科学与其它学科的交叉研究与发展.

项目执行三年来，紧跟高性能计算最新发展趋势，在随机调度理论和应用上做了系统深入的研究工作，对基于随机性的超级计算机调度器的构建进行了探索..（1） 在调度理论与方法研究方面：.系统深入地分析了大规模并行系统任务执行时间不确定性的原因，并用数学方法对其进行建模，从理论上研究了任务执行时间服从几种典型概率分布的任务，并对其在并行系统的可调度性进行了分析，证明基于DAG模型随机任务调度长度的下限是以任务期望构成的确定型任务调度长度。提出了一种基于博弈论的多项式时间近似调度算法，是目前近似程度最高的理论结果..根据并行系统任务的可靠性和任务计算量随机性，提出了考虑可信性的任务调度理论与方法，克服以任务执行平均值、中间值、最好值或最坏值等方法给任务调度带来的不足，提出异构并行计算系统计算能力异构因子a，并依此实现任务优先级计算和处理机选择。在此基础上，提出基于任务复制的表调度算法(HEFD) 以及考虑任务执行行为安全开销的调度模型和调度算法SDS。实验结果表明所提出的算法一定程度上解决了系统可靠性条件下的随机调度问题..针对基于复制的调度算法造成的资源浪费和能耗开销大的缺点，提出了一种冗余副j本删除调度算法。传统的基于复制的调度算法普遍具有贪婪性，通过复制任务使当前任务最早完成，但某些任务的提前完成并不能减少整体的makepan，反而造成资源和能耗开销。提出的冗余副j本删除调度算法可对所有基于复制的算法进行优化，减少其复制个数，从而达到节能的目的。.（2）在调度与理论的高性能计算应用方面.根据BEKELY大学并行计算中心的研究结果，对并行计算的13个典型计算模块中的FFT,矩阵稀疏线性代数、蒙特卡罗方法、分子动力学等4个数值计算模块和图遍历以及回溯和分支限界等2个非数值计算模块在CPU-GPU异构并行系统的并行计算性能及相应的调度分配方法以及高效并行实现进行了深入研究，取得了较高的加速比和可扩展性..在上述模块的异构并行运算和调度理论成果基础上，设计和实现了一系列典型高性能应用可扩展并行算法,顺利完成了项目申请书的预期研究目标.