异构环境下基于强化学习的大数据任务调度算法研究

作     者：陈天祥 

作者单位：浙江大学 

学位级别：硕士

导师姓名：夏莹杰

授予年度：2022年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：大数据任务调度 图卷积神经网络 强化学习 数据本地性 最大完工时间 

摘      要：近年来,随着人类社会积累的数据量不断增加,传统数据处理方法逐渐表现出一些瓶颈和限制。自从Map Reduce论文奠定了大数据处理的思想基础后,开源社区推出了一系列大数据处理框架,比如Spark、Flink等等。这些框架所生成的大数据作业可以抽象成一张有向无环图（Directed Acyclic Graph,DAG）。特别地,大数据作业往往具有较高的复杂性,并且负责执行作业的集群越来越呈现异构化趋势。因此,如何在异构集群中高效地调度大数据作业逐渐成为研究的重点。本文在现有的研究基础上,提出了两种调度算法。两种算法都将大数据作业抽象为DAG结构,并以最小化最大完工时间为优化目标来进行任务调度。两种算法的主要区别在于不同数量的处理阶段。值得注意的是,本文算法并不局限于开源社区中现有的调度框架或数据处理框架,而是一种通用的调度方案。本文的主要研究工作如下:（1）根据大数据作业的结构和数据特点,本文设计了一种基于图结构的任务-资源双向向量表达方法。该方法包含两个处理步骤:自底向上的处理对应着图卷积神经网络对于作业的转化操作,自底向上是指子任务节点的特征信息将在处理过程中传递给父任务节点;自顶向下的处理通过计算特定的矩阵,使调度算法尽可能考虑数据本地性,从而减少数据传输的开销,自顶向下是指父任务节点所使用的任务执行器信息将在处理过程中传递给子任务节点。（2）在异构集群的场景下,针对大数据作业集合的调度问题,本文设计了一种基于任务选择过程强化学习的调度算法。基于上述图结构表达方法,该算法引入强化学习模块和资源匹配模块来实现调度功能。调度算法根据调度过程的特点来对状态、动作、奖励以及智能体进行设计,使得强化学习模块能够确定下一个被调度的任务节点和相应的任务实例数。资源匹配模块用于计算被调度的任务实例与各个任务执行器的匹配值,并选取匹配值最高的任务执行器来运行任务实例。实验结果表明,在调度大批量作业的场景下,该调度算法优于其他调度算法,能够加快作业的完成。（3）考虑到基于任务选择过程强化学习的调度算法中算法结构复杂、资源匹配模块存在不足等问题,本文进一步设计了一种基于全过程强化学习的调度算法。该算法将资源匹配模块所实现的功能集成到强化学习模块中,并对状态、动作、奖励以及智能体进行改进,使强化学习模块既能够确定下一个被调度的任务节点和相应的任务实例数,又能够为任务实例选择最佳任务执行器来运行。实验结果表明,该调度算法的调度效果优于基于任务选择过程强化学习的调度算法。综上所述,本文不仅设计了优于现有解决方案的大数据任务调度算法,而且为任务调度问题提供了一种新的解决思路。