# 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越短。
![image-20220228152039290](README.assets/image-20220228152039290.png)
图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$ :表示执行当前计算机�