DeepWeave

一、摘要

coflow：为了提高分布式计算中作业的处理效率，提出了共流的概念。共流是多阶段计算任务中语义相关的工作流的集合。

作业由多个共流组成，通常可以表示为有向无环图（DAG）。在分布式计算中，合理地调度协同流可以显著缩短作业的完成时间。然而，这个调度问题被证明是NP难的。与现有的使用手工制作的启发式算法来解决这个问题的方案不同，本文提出了一个名为 DeepWeave 的深度强化学习（DRL）框架来生成同流调度策略。为了提高作业DAG中的同流调度能力，DeepWeave 采用图形神经网络（GNN）来处理DAG信息。DeepWeave从历史工作负载跟踪中学习，训练DRL代理的神经网络，并在神经网络中编码调度策略，从而在没有专家知识或预先假设的模型的情况下做出同流调度决策。该方案通过一个使用真实跟踪的模拟器进行了评估。模拟结果表明，DeepWeave完成作业的速度至少比最先进的解决方案快1.7倍。

二、介绍

​ 随着数据处理需求的增加，近年来，基于集群计算的计算已被广泛采用，因为它可以在相对较低的资本支出（CAPEX）下实现较高的并行计算性能。许多集群计算应用程序（如Spark和MapReduce）部署在数据中心，并使用作业模型进行抽象，作业模型由几个连续的计算阶段和计算阶段之间的通信阶段组成。每个计算阶段的执行只能在前一阶段的中间数据完全传输时开始。这个工作程序可以被建模为一个作业有向无环图（DAG），其中计算阶段（点集）和通信阶段（边集）分别被建模为节点和边。在作业DAG中，一个通信阶段涉及一组流，这些流从两组机器相互交织，共享一个共同的作业目标。一组这样的流称为共流（coflow）。现有工作指出，在数据中心网络（DCN）中，同流传输（即，中间数据从一个计算元素到另一个计算元素的顺序相关传输）消耗了整个作业至少50%的处理时间。因此，良好的同流调度可以显著减少作业完成时间（JCT）。

​ 然而，设计一个好的同流调度方案并非易事。在DCN中有效地调度同流是一项挑战，因为应考虑各种同流特性，包括同流的特性（例如，流大小和并行流的数量）以及同流之间的特性（例如，作业DAG中不同同流的关系）。已证明最优同流调度是NP难的。现有工作简化了问题，并使用启发式解决方案来最小化共流的传输时间。然而，这些作品有以下两个局限性：

1. 大多数现有工作仅专注于在单个通信阶段尽量缩短共流的传输时间，并未深入探讨具体工作的通信要求。因此，可能不会考虑作业DAG的不同通信阶段中的同流执行顺序，并且这些作业不可知调度方法无法带来最佳JCT。
2. 手工编制的启发式解决方案通过一些放松简化了问题，只确保粗略地近似于NP难问题的最优解。例如，非抢占式调度算法只能确保2-近似最优解（ε-最优理想解），与最优解之间存在很大差距

​ 在本文中，我们提出了DeepWeave，一种基于学习的方法来有效地调度合流。DeepWeave使用深度强化学习（DRL）框架从历史轨迹中学习并训练神经网络。Deep-Weave由两组级联的神经网络和一个策略转换模块组成，它将调度策略编码到神经网络中，可以在不需要专家知识和预先假设的模型的情况下做出同流调度决策。DeepWeave同时适用于同向流内调度和同向流间调度。具体来说，为了更好地处理作业DAG信息，并确保神经网络在不可预测的输入DAG下的泛化能力，我们建议使用图神经网络（GNN）来处理输入数据。DRL代理使用训练好的神经网络中的策略为不同的流生成优先级调度列表。根据该列表，以细粒度的方式进一步调度每个同流中的流。仿真结果表明，DeepWeave完成作业的速度至少比最先进的解决方案快1.7倍。

​ 本文的贡献总结如下：

1. 本文首次提出了一种基于机器学习的同流调度体系结构来加速JCT。
2. 我们使用DRL作为基于学习的框架来训练神经网络，并在没有人类经验的情况下探索同流调度策略。
3. 我们设计了一种基于GNN的神经网络结构来处理输入任务DAG。经过训练，该结构可以很好地推广到不同的DAG尺寸和形状。
4. 我们使用真实的痕迹和生成的痕迹来评估DeepWeave的性能。仿真结果表明，DeepWeave在JCT方面优于最先进的解决方案。（用真实的生产数据进行评估）

三、问题表述

DCNs中的多阶段计算任务通常存在共流。在同流调度中，DCN在逻辑上可以被视为连接不同计算机器的巨大非阻塞交换结构。结构的每个端口都具有相同的容量，并且由于同一端口中的流竞争带宽，拥塞只发生在端口。在现有工作的基础上，我们使用这个DCN模型进行研究。下图是coflow的典型例子[Chowdhury and Stoica，2015]。DCN被建模为非阻塞交换结构，并互连不同的机器组。

​ 在这个图中，结构有三个输入端口，每个输入端口有三个队列。共有三种共流：C1、C2和C3。

• 在时隙0，C1到达端口1，C2到达端口1和2。C1和C2争夺端口1。（只有端口1存在争夺）

• 在时隙1，C3到达端口2。

建模，搞一个DAG $ G = (V,E,T) $ ，其中

• $ V=\left(v_{1}, v_{2}, \cdots, v_{|V|}\right) $ 点集代表工作的计算阶段。
• $ E=\left(e_{1}, e_{2}, \cdots, e_{|E|}\right) $ 边集代表工作的通信阶段。
• $ T $ 指标，代表工作的全局截止时间。

每一个通信阶段都是两个计算阶段之间的共流。作业 DAG按照其不同阶段之间的依赖关系在管道中进行处理，其处理必须在截止时间 $ T $ 内完成。下图展示的是一个带有七个计算结点和六个通信边的例子。作业DAG中有两种类型的Coflow依赖关系：开始后和完成前。在一个开始后关系中， $ e_a $ 在 $ e_b $ 完成之前不能启动（表示为 $ e_a \mapsto e_b $ ）；在完成前关系的情况下， $ e_a $ 在 $ e_b $ 完成之前无法完成（表示为 $ e_a \to e_b $ ）。

​ 在作业DAG中，计算阶段通常是并行执行的，因此，从不同的计算阶段并行生成共流，并在结构的端口上相互竞争。计算阶段的计算时间可以视为常数，共流（也就是通信阶段）的调度是整个JCT 的主要因素。

​ 考虑在一个作业 DAG 中，有 $ N $ 个共流，交换结构有 $ M $ 个入度端口和 $ M $ 个出度端口，共流（边）可以定义为

$$e_i = f_i^{m, n} \ \ \ \ 1\le m \le M,1\le n \le M$$

$ f_i^{m, n} $ 表示一条端口 $ m $ 到端口 $ n $ 的流动。 $ fs_i^{m, n} $ 表示 $ f_i^{m, n} $ 端口的容量。如果在共流 $ e_i $ 中没有没有流动从 $ m $ 端口到 $ n $ 端口，那么 $ fs_i^{m, n} = 0 $ 。由于每个端口具有相同的容量，因此流的传输时间与每个端口的流大小成正比。在不丧失一般性的情况下，我们使用每个流的大小来表示以下传输时间。用 $ C_i $ 表示 $ e_i $ 的传输时间， $ C_i = End(e_i) - Start(e_i) $ ，在以上这些的定义下，同流调度的目标是最小化整个作业的平均传输时间

$$\begin{align} &f(x) = \min{\sum_i^N C_i}\\ s.t.:\ \ &Start(e_i) \ge End(e_x|e_x\mapsto e_i)\\ &End(e_i) \le End(e_x | e_x \to e_i) \end{align}$$

四、DeepWeave算法设计

在本节中，我们将介绍DeepWeave的设计。首先，我们概述DeepWeave的体系结构。其次，我们在训练中介绍plain DeepWeave的DRL框架。第三，我们介绍了神经网络在深编织中的处理机制。最后，我们介绍了策略转换器，它将DRL代理的输出值转换为具体的共流调度策略。

4.1、DeepWeave概述

DeepWeave是基于DRL框架设计的，用于为网络生成同流调度策略。下图显示了一个共流调度代理，它由一组神经网络（详见第4.2节和第4.3节）和一个策略转换器（详见第4.4节）组成。在工作过程中，DeepWeave收集作业DAG信息，并将信息转换为特征图，作为GNN的输入，GNN计算作业DAG的特征，并将计算出的信息传递给策略网络。然后，策略网络生成一个优先级列表作为输出，作为策略转换器的输入。最后，策略转换器将优先级列表转换为同流调度选项，用于调度同流中的同流和流。

4.2、DRL训练框架

DeepWeave通过DRL框架训练其神经网络，并使用包含三个元素 $ 〈S，a，R〉 $ 的元组来描述交互。

• 在元组中， $ S $ 是状态空间，代表环境的状态观察（即DeepWeave中的作业DAG）;
• $ A $ 是动作空间，代表 RL 代理输出动作的空间；
• $ R $ 是奖励空间，用于评估动作的质量。

DeepWeave 的 DRL 代理通过与网络环境的交互逐步得到训练。在每一步中，代理都会收集一个观察结果 $ s \in S $ 从环境中提取并生成动作 $ a \in A $ 通过特定的计算过程安排环境的中共流，可以抽象为策略。某一动作的质量 $ a \in A $ 由带有奖励的评估函数进行评估 $ r \in R $ 来描述质量。基于价值 $ r \in R $ 、 这项策略是为了更好地执行而改进的。具体而言，DeepWeave 中的接口定义如下：

• State：在每个同向流和作业DAG的形状中流动。
• Action：优先级列表，表示作业DAG中边的调度优先级。
• Reward：作业的完成时间。

​ DRL 代理的训练过程分几回合进行，每回合由多个交互步骤组成。在每一回合中，培训的目标是最大化累积的奖励 $ R_{epi} = \sum_{t = 0} ^ T r(t) $ ， $ T $ 表示该回合中的交互步骤次数。我们使用 $ \mu $ 来表示 DRL 代理的策略。 在每个步骤 $ t $ 中，代理从环境中获取一个观察 $ s_t $ ，并基于 $ a_t=\mu(s_t) $ 生成动作 $ a_t $ 。如上所述，在 DRL 中，策略由神经网络生成。因此， $ a_t=\mu(s_t) $ 可以更准确地表示为 $ at=\mu_\theta(s_t) $ ，其中 $ \theta $ 表示神经网络的参数（例如，不同神经元之间的权重和偏差）。当一回合完成时，累积奖励 $ R_{epi} $ 可用于评估该回合中的策略。

​ 在 DeepWeave 中，我们使用策略梯度方法来更新基于 $ R_{epi} $ 的神经网络，以获得更好的策略。在政策梯度法中，计算梯度下降以更新神经网络参数，如下所示[Sutton等人，2000]：

$$\theta^{\prime}=\theta+\alpha \sum_{t=1}^{T} \nabla_{\theta} \log \mu_{\theta}\left(s_{t}, a_{t}\right) Q_{t}$$

其中 $ \alpha $ 表示在每一集中控制 $ \theta $ 更新速度的学习速率， $ Q_t $ 表示当前集中策略的质量评估。具体来说，我们将 $ Q_{t}=\sum_{t^{\prime}=t}^{T} r_{t^{\prime}}-b_{t} $ 是一种有偏形式，其中 $ b_t $ 被用作基准值，以限制政策梯度的变化[Greensmith等人，2004年]。这样，神经网络的参数在每一回合之后都会得到更新，因此该DRL代理在下一回合的预期性能应该更好。由于在几个初始事件中，神经网络参数接近随机值，且策略不好，我们可以使用类似于Decima[Mao等人，2019]中使用的方法，通过缩短事件长度来加速训练。

​ 整个训练过程的逻辑如算法1所示。为了加快训练过程，我们实现了 $ N $ 个并行代理。算法1的训练目标是让神经网络的参数进化，从而生成一个良好的同流调度策略。第 $ 3-4 $ 为DRL代理运行一系列实验，第 $ 5 $ 行在每次迭代中将神经网络的更新值重置为零。第 $ 6-14 $ 行根据累积奖励计算神经网络的更新值，其中第 $ 7-10 $ 行计算基线值bk以减少训练的偏差，第 $ 11-12 $ 行设置每个代理的神经网络参数的变化。第 $ 15 $ 行规定了一回合的长度。在我们的培训中，学习率 $ \alpha $ 设置为 $ 1×10^{−3} $ ，梯度下降用于使用 Adam 优化器更新神经网络参数[Kingma and Ba，2014]。

4.3神经网络的实现

DeepWeave中的神经网络包括两个阶段：GNN处理和策略网络处理，如下图所示。在本小节中，我们将详细介绍这两个阶段。

​ GNN处理作业DAG的信息。与卷积神经网络等其他流行的神经网络相比，GNN更适合处理类似图形的结构化数据[Zhou等人，2018]。此外，GNN被证明具有更好的知识转移能力[Rusek等人，2019]。例如，当输入数据的大小与训练历史略有不同时，GNN仍然可以做出精确的推断。在同流调度中，训练过程很难覆盖所有的作业DAG形状，因此知识转移能力至关重要。

​ 在GNN中，计算出节点属性和作业属性。首先，将 $ V_i $ 的信息（例如计算成本）抽象为图中节点的特征 $ x_i $ 。然后，根据 $ v_i $ 子节点的属性计算节点 $ v_i $ 的属性 $ attr_i $ 。属性信息从 $ v_i $ 的子节点通过一系列信息传递步骤一步步传递到 $ v_i $ 。在这些消息传递步骤中，每个节点通过 $ attr_i=F(x_i,{attr_u|v_u \in des(v_i)}) $ 计算他的属性值。实际上，函数 $ F(·) $ 可以用神经网络实现。我们在DeepWeave中为 $ F(·) $ 实现了两个神经网络，如下所示：

$$\operatorname{attr}_{i}=f\left[\sum_{v_{u} \in \operatorname{des}\left(v_{i}\right)} g\left(\operatorname{attr}_{u}\right)\right]+x_{i}$$

其中 $ f(·) $ 和 $ g(·) $ 是两个小型前馈神经网络，具有两个隐藏层。该函数可以对相应的输入信息进行非线性变换。通过这种方式，消息传递过程可以将复杂信息从节点的子节点传输到节点。此外，[Mao等人，2019]指出，一个神经网络无法计算DAG的关键路径[Kel-ley Jr，1961]。每个节点属性都表示为一个绝对值。属性值被排序，并且在值离开GNN之前，根据它们的值记录每个节点的顺序。在计算节点属性之后，还有一个作业级信息摘要 $ y $ 。在Deep-Weave中，另一组神经网络用于计算 $ y $ ，其中 $ y=f_{job}(\{attr_i，x_i | v_i \in V\}) $ 。

​ 在GNN计算过程之后，作业级别信息和节点属性的序列被发送到策略网络阶段。该策略网络由一个具有一个隐层的前馈神经网络实现。前馈神经网络计算工作级别信息和节点属性，并生成优先级列表 $ P=(p_1,p_2,\cdots,p_{|V|}) $ 作为输出，其中 $ p_i(1 \le i\le |{V}|) $ 对应于作业执行过程中节点 $ v_i $ 的优先级值， $ p_i $ 越高表示优先级越高。请注意，策略网络不能像GNN那样更改其大小。在我们的设计中，输入层的大小等于实验中可能出现的最大顶点数。对于小型DAG，节点属性中的排序值在用作策略网络的输入之前用零填充。

4.4策略转换器

策略转换器将策略网络的输出值转换为具体的同流调度策略。如前所述，策略网络为作业DAG中的每个节点生成优先级列表 $ P=(p_1,p_2,\cdots,p_{|{V}|}) $ 。由于作业DAG只有一条来自某个节点的边，因此我们将边 $ e $ （即同流）的优先级与其源节点的优先级值分配。假设我们得到了优先级列表 $ P=(p_1,p_2,\cdots,p_{|{V}|}) $ 代表每个同流的优先级。调度问题是根据流所属的同流的优先级来调度每个端口的流。调度过程包括入口端口调度和出口端口调度，这两种调度是相似的。为了简单起见，我们只展示入口端口的调度过程。

算法2详细说明了从优先级列表到入口端口的具体调度过程的转换。在算法2中，根据优先级列表 $ P $ 中的优先级对同流进行调度。第2行选择优先级最高的同流进行调度。第3-4行通过首先在选定的同流中安排最大大小的流，来最小化同流的结束时间。第5行获取流的结束时间，并将此流的结束时间用作此同流的结束时间。6-10号线计划 $ n* $ 端口的其他流量. 第11行从优先级列表中删除了已经调度好的同流。

五、实验与评价

略