《基于深度强化学习的云工作流调度》.zip

# Cloud Workflow Scheduling base on Deep Reinforcement Learning 北京化工大学本科毕业设计《基于深度强化学习的云工作流调度》 关键词：有向无环图，工作流，深度强化学习，图神经网络； 蒙特卡洛树搜索 ## Installation It requires the following packages: - Python 3.9.7 - torch 1.10 - gym 0.21.0 - networkx 2.6.3 ## Instructions 1. 将 Env/___.py 文件注册在gym的环境中； 2. 运行 DAGs_generator.py 生成 train dataset， test dataset. 3. 修改环境代码适应生成数据集的路径； 4. 运行 PPO/DRLagent.py 训练网络； 5. 运行 PPO/DRLtest.py 测试推理。 5. 运行baseline_tableau.py 得出baseline算法效果 5. 运行MonteCarloTreeSearch.py 得出MCTS算法效果 ## 目前进度 2022.03.11 - 目前状态空间，动作空间下设计的Actor- Critic，PPO方法难以超越baseline [Tetris](https://dl.acm.org/doi/abs/10.1145/2740070.2626334?casa_token=EYl_WpNS79MAAAAA:iNwogrNmlUceBfJ-P0vySitXQzV01kmwGmkRj4qTHPeqBiyd04Zqt6giZpwvOR3TgR1Nv46_8jJYdt0)的效果。 - 尝试经典[GCN](https://arxiv.org/abs/1609.02907)编码DAG，效果不佳。 - 尝试[Decima](https://dl.acm.org/doi/abs/10.1145/3341302.3342080)中的编码结构。 2020.03.23 - 结合[Decima](https://dl.acm.org/doi/abs/10.1145/3341302.3342080)中的[GCN](https://arxiv.org/abs/1609.02907)对DAG进行编码，改变编码数量，效果不佳 - 完成深度强化学习加速蒙特卡洛树搜索算法（魔改[spear](https://ieeexplore.ieee.org/abstract/document/8885307/)），目前在DAG_size=10大小上效果最佳。 - 编写了单个DAG任务资源用量检测脚本。 2020.04.19 - 完成蒙特卡洛树n=10-50的所有实验 - 完成毕业论文初稿 - 下一步优化GCN编码 ## 有向无环图生成设计 ​ 工作流通常由DAG（有向无环图）来定义，其中每个计算任务$T_i$由一个顶点表示。同时，任务之间的每个数据或控制依赖性由一条加权的有向边$E_{ij}$表示。每个有向边$E_{ij}$表示$T_i$是$T_j$的父任务，$T_j$只能在其所有父任务完成后执行。一般在所有任务之前设立一个Start虚拟节点，作为所有没有父任务节点的父节点；同理，在所有任务之后设立一个Exit虚拟节点，作为所有没有子任务节点的子节点，这两个虚拟节点都没有计算资源需求。 ​ 确定表示一个DAG需要三个数据，分别是是节点连接信息，各节点的父节点数，各节点的子节点数。由这三个元素可以确定一个独立的DAG。 ​ 例如一个10个节点的DAG： **Edges:** [(1, 5), (1, 6), (2, 4), (2, 6), (3, 6), (4, 7), (4, 9), (5, 9), (5, 7), (6, 7), ('Start', 1), ('Start', 2), ('Start', 3), ('Start', 8), ('Start', 10), (7, 'Exit'), (8, 'Exit'), (9, 'Exit'), (10, 'Exit')] **In_degree:** [1, 1, 1, 1, 1, 3, 3, 1, 2, 1] **out_degree:** [2, 2, 1, 2, 2, 1, 1, 1, 1, 1] 表示的是下面这一张图。 <img src="README.assets/image-20220228114904174.png" alt="image-20220228114904174" style="zoom:67%;" /> ​ 图 1 一个DAG示例 参数设定为： size = [20,30,40,50,60,70,80,90] #DAG中任务的数量 max_out = [1,2,3,4,5] #DAG节点的最大出度 alpha = [0.5,1.0,1.5] #控制DAG 的形状 beta = [0.0,0.5,1.0,2.0] #控制 DAG 的规则度 具体的实现细节如下： 1. 根据公式$length=\frac{\sqrt{size}}{alpha}$计算出生成DAG的层数，并计算平均每层的数量$\frac{size}{length}$. 2. 在以均值为$\frac{size}{length}$，标准差为$beta$的正态分布中采样每层的任务数并向上取整，这样随机采样得到的总任务数可能有偏差，随机在某几层添加或者删除任务，使DAG总任务数等于$size$。 3. 对于第一层到倒数第二层：每一个任务随机在[0, $max\_out]$，并随机连接$n$个下一层的任务。 4. 最后给所有没有入边的任务添加Start作为父节点，所有没有出边的任务添加Exit任务作为子节点，至此一个随机的DAG就生成好了。 在这里$alpha$控制的是DAG的整体形状，如果$alpha$越小，DAG越长，$alpha$越大，DAG越短。  ​ 图2 不同alpha下DAG的形状（n=30） $beta$则是控制的DAG的规则度，如果$beta$越大，DAG越参差不齐。 ## 添加工作流信息 对DAG中每一个任务随机分配它的持续时间和资源需求（CPU，Memory）。 为了模拟一些时间占用相对较长的任务，定义一个概率prob=80%，每个任务的持续时间有80%的几率在$[t,3t]$的范围内随机取值，20%的概率在$[10t,15t]$的范围内随机取值。 每个任务有50%的概率为CPU密集型任务，剩下的50%是Memory密集型的任务。 CPU密集型的任务CPU的资源占用量在$[0.25r,0.5r]$中随机取值，Memory的资源占用量在$[0.05,0.01]$随机取值。Memory密集型的任务资源需求量相反。 举一个根据以上规则生成的工作流信息的例子，对10个任务的 DAG 随机生成的工作流信息如下表示： (r=100,t=10) 任务占用时间 Ti: [27.174, 23.215,24.209,15.085, 20.691,29.892,20.632, 26.777, 19.402,18.362] 任务资源占用 (res_cpu,res_memory): [(31.432, 1.019), (4.7330, 25.308), (1.208, 42.542), (1.517, 47.633), (39.299, 4.826), (1.654, 46.401), (2.438, 35.593), (3.887, 42.224), (1.594, 30.074), (42.445, 3.225)] ## 马尔可夫决策过程建模 ### 状态空间 1. 当前执行的时间（1维） 2. 当前资源中剩余的 CPU 资源（1维） 3. 当前资源中剩余的 Memory 资源（1维） 4. Ready_task 任务列表（长度为 10）中的任务要求时间（30维）如果不足30空位补-1 5. Ready_task 任务列表中的 CPU 要求资源（30维） 如果不足30空位补-1 6. Ready_task 任务列表中的 Memory 要求资源（30维） 如果不足30空位补-1 7. 当前未完成 DAG 部分的最大路径长度（1维） 8. 当前未完成 DAG 部分的子节点数（1维） 9. 超出 Ready_task 任务列表长度且准备好的任务的时间要求总和（1维） 10. 超出 Ready_task 任务列表长度且准备好的任务的 CPU 要求总和（1维） 11. 超出 Ready_task 任务列表长度且准备好的任务的 Memory 要求总和（1维） 共98维状态。 ### 动作空间 {-1,0,1,2,3,4,5,6,7,8,9,...,29} •选择 $a=-1$表示执行完计算资源里的一个耗时最短的任务。此时执行时间增加该任务的消耗时间，释放占用的CPU和Memory资源。 •选择$a=0\sim29$表示把当前 Ready_task 任务列表的第a个任务提交给计算资源。此时当前执行时间不变，当前CPU/Memory资源减去该任务占用的资源。 ### 回报函数 •选择 $a=-1$: $reward = -\frac{\text{执行时间}}{t}$ •选择$ a=0\sim9$: $reward = 0$ ## 环境说明 实验采用OpenAI 强化学习gym平台，自定义的工作流调度环境主要包括两个函数： ### state, reward, done, infor = env.step(action) step函数用于智能体与环境进行交互，输入动作action返回的是下一步的状态state，该步的reward，是否执行完一整个个DAG任务，和动作是否有效（infor）。 当接受到动作后智能体首先判断该动作是否有效： a) 该动作对应的位置是没有任务（数据是-1），动作无效。 b) 计算资源不能能满足该位置上的任务的CPU/Memory资源需求，动作无效。 c) 如果当前计算资源中没有提交的任务,动作$a=-1$是无效的。 如果动作无效，重新采样动作； 如果动作有效，则更新状态： a) $ a=0\sim29$ ：计算资源中CPU/Memory分别减去该任务占用的资源，更新Ready_task 任务列表中该任务对应位置上的执行时间，CPU/Memory资源全部置为-1，表示该任务已经提交给计算机。 b) $a=-1$ ：表示执行当前计算机�