分布式异构计算系统中的DAG任务智能调度方法研究

DAG (Directed Acyclic Graph) tasks scheduling in distributed heterogeneous systems is one of the hot topics in system research field. Due to new DAG tasks applied in big data and AI applications have many computation types and complex data dependencies, traditional heuristic based task scheduling algorithms cannot easily adapt to both software and hardware environment changes, which results in the decreased system efficiency. Using machine learning method to solve the challenges faced by the heuristic-based method is the future trend in system research field. To solve the adaptive scheduling problem of DAG tasks in heterogeneous systems, this project proposes to design and implement self-learning smart scheduling algorithm using deep learning and reinforcement learning methods in various application scenarios. The main research contents include: (1) build a new heterogeneous hardware topology aware policy network model, to improve the accuracy and effectiveness of scheduling policy; (2) design a reinforcement learning based scheduling method, combining with deep neural network and the MCTS method, to improve search efficiency of scheduling policies; (3) design and implement runtime cache based fast parallel training method, to decrease scheduling algorithm’s training time. Based on above work, this project aims to lay the theoretical and technical foundations of smart DAG tasks scheduling research.

分布式异构计算系统中的DAG（有向无环图）任务调度是计算机体系结构研究领域中的热点问题之一。面向新型大数据、人工智能等应用的DAG任务具有计算任务种类多、并行依赖关系复杂等特点，传统启发式调度算法难以自适应软硬件系统的发展变化，通常导致系统运行效率的下降。利用机器学习的方法解决传统启发式方法遇到的难题是系统研究领域的发展方向。为解决异构系统中的DAG任务自适应调度问题，本项目拟结合深度学习和强化学习的方法，设计实现满足多种应用场景的自学习智能调度算法。主要研究内容包括：（1）建立基于异构硬件拓扑感知的调度策略网络模型，以提高调度策略的准确性和通用性；（2）设计结合深度神经网络和蒙特卡洛树搜索方法的强化学习算法，以提高调度策略的搜索效率；（3）设计实现基于运行时间缓存机制的快速并行训练方法，以降低调度算法的训练时间。通过以上研究，本项目为DAG任务智能调度方法奠定理论和技术基础。

分布式异构计算系统中的资源管理与任务调度问题日益成为系统研究的重难点问题之一。本项目面向新型大数据、人工智能等应用的DAG任务调度场景，解决具有计算任务种类多、并行依赖关系复杂等特点的异构计算系统自适应调度问题。主要研究内容包括：（1）建立基于异构硬件拓扑感知的调度策略网路模型，通过强化学习方法，实现DAG任务的智能调度决策，实验结果表明，采用REINFORCE算法的强化学习自适应调度方法相比经典HEFT等算法makespan关键指标平均提升10%。（2）设计结合深度神经网络和蒙特卡洛树搜索方法的强化学习算法，提高了调度策略的搜索效率，同时保证策略网络参数更新的鲁棒性，基于MCTS搜索方法可以在小于1000次模拟搜索中获得相比PEFT更好的DAG调度决策质量。（3）设计实现基于运行时间缓存机制的快速并行训练方法，在此基础上设计了一种网络结构自适应进化的强化学习调度框架，实现了最小化网络节点参数的DAG任务调度决策优化，与现有传统MLP网络结构模型参数相比，模型参数量减少到原来的十分之一。.本项目研究工作为DAG任务智能调度方法奠定理论和技术基础，基于学习+搜索的强化学习方法，可以有效地解决复杂系统中的资源管理与任务调度问题。基于学习的方式可以自适应系统中的复杂变量变化，基于搜索的方式可以精确控制决策并作为学习策略的提升目标。因此，基于学习+搜索的强化学习方法，将是解决未来大规模复杂系统资源管理与任务调度问题的有效技术手段。学习+搜索形成有效的迭代强化闭环。通过学习获得决策概率分布以及状态期望估计，进而提高搜索效率（基于决策概率分布剪枝搜索树的宽度，基于状态期望估计剪枝搜索树的深度）；通过搜索获得改进的决策概率分布和状态期望估计，进而为学习提供新的目标值，达到强化学习的目的。为了进一步提高调度决策效率，未来研究将基于采样和离线学习的方式，提高强化学习的数据利用效率。