Online Scheduling of Heterogeneous Distributed Machine Learning Jobs

总结

  • 主题：分布式机器学习任务中的在线调度问题

  • 问题: 考虑到需求弹性，在资源有限的情况下，如何确定分配给每个作业的worker和ps的数量、类型以及运行时间，从而最大限度地利用资源，最小化平均加权完成时间?

  • 方法（解决步骤）：

    1、先将平均加权完成时间最小化问题表述为一个时间索引的数学程序（3.3系统建模）

    建模中遇到的问题（非传统约束）：非传统约束包括类型约束和非传统约束（集合类型和自然语言描述）约束。以下变量不适合线性约束，又无法被现有方法处理。

    • 类型约束：每个作业使用一种类型的处理器，即每个作业只能使用一种处理器来保证资源效率。

    • 非传统约束：描述了作业、处理器之间的关系，如约束条件(2d)中描述了$q_j、y_{jhm}和s_{jhp}$之间的关系，这种关系难以用线性约束描述。

    • 其他约束：还包括至少为每个机器学习作业分配一个处理器来维护其全局参数的约束，以及为每个作业分配足够数量的工人和时间段来完成数据集的训练的约束。

      如何优化：

    • 由于问题涉及到整数变量、非线性约束等挑战性因素，需要应用紧凑指数技术（第五章）等方法来重新构建问题，以便于求解

    2、需要决策的变量: 包括worker和ps的数量/类型，以及每个作业的执行窗口

    3、设计算法

    • 提出了一个在线框架$A_{online}$，通过将整体时间跨度划分为几何长度递增的区间（通过$A_{dual}$计算𝛼），将在线优化问题转换为一系列批量调度问题。

    • 在指定时间段内调度权重最大的作业，等价于平均加权完成时间最小（不知道说的对不对），所以解决最大加权调度问题：在一个 ML 集群中，给定一个截止时间𝜏𝑖，一组任务集合𝐽𝑖和每个任务的权重，构造一个可行的调度，使在时间𝜏𝑖内完成的任务的总权重最大化

    • $A_{dual}$用来对偶近似算法找到一个超过最优的不可行解，其中算法的性能是由允许的不可行程度来衡量的。由于作业执行可以跨越多个区间，因此不可行解最终将变得可行。超优目标值有 助于约束平均加权完成时间，$A_{maxweight}$用来选择权重最大作业来运行

    • 在某一时间点之前调度尽可能多的未调度作业？

    • 最大加权调度问题包含了几个非传统的约束，涉及整型变量、非线性约束(2b) (2c)和关于变量乘法(2f)(2h)(7b)的约束，还有集合类型的约束，用于表示worker和ps的配置/放置，因此还需要转换（紧凑指数技术优化）。解决方法：将每个有效调度编码为一个变量，并将原始程序重新构建为整数线性规划（ILP），其中只包括传统的打包约束，但代价是引入指数数量的变量。

    • 如何决策：将对偶变量解释为单位资源价格，并根据资源消耗成本和其机器学习框架计算每个作业的最佳调度。如果作业的权重高于其估计的服务成本，则算法会安排该作业。原因：给定有限的资源，希望调度具有更大效用的作业。

4.算法细节：

  • 截止时间如何划分

    截止时间是通过将潜在完成时间的时间跨度划分为几何递增点来划分的。具体来说，设置 $τ_0 = 1$，$τ_i = 2^i-1$。在第 i 轮中，等待直到时间达到$ τ_i$，然后将到达时间在$ τ_i$ 之前的作业划分为集合$ J_i$。

  • 对偶近似算法：原始问题和对偶问题之间存在一种对应关系，通过对偶问题的求解可以获得原始问题的信息

    1. 对偶：算法通过找到一个超优的不可行解来衡量算法的性能，即生成一个长度不超过 ατi 且总权重至少等于最优权重的调度。这种不可行解最终会在作业执行跨越多个时间段后变得可行，从而体现了对偶性质。

    2. 近似：算法利用 γ -近似算法来解决最大权重调度问题，即在给定截止时间和作业集合的情况下，尽可能多地安排作业以最大化总权重。通过近似算法，可以在保证性能的前提下生成有效的调度方案，从而体现了近似性质。

    因此，对偶近似算法在处理最大权重调度问题时同时具有对偶性和近似性，通过这两个方面的特性来保证算法的性能和有效性。

  • 超优的不可行解：

    超优的不可行解指的是一个在不可行的情况下具有优越性能的解。

    通过对偶近似算法，算法会生成一个长度不超过$ ατi$ 且总权重至少等于最优权重的调度方案。这个调度方案在生成时是不可行的，但通过作业执行跨越多个时间段后会变得可行（原始的不可行解可能在某个时间段无法满足所有作业的要求，但随着时间的推移和作业的执行，可能会出现新的资源或条件使得原本不可行的解变得可行）。因此，通过对偶近似算法生成的超优的不可行解来评估算法的性能和有效性。

  • 竞争比率（competitive ratio）指的是在线算法的性能与最优离线算法的性能之间的比率。
    $4α-competitive $表示在线算法的性能是最优离线算法性能的4倍。$A_{maxweight}$在算法3中的近似比率是$ 2log λ$。这里的近似比率表示 $A_{maxweight}$算法的性能相对于最优解的性能的近似比率。在这种情况下，近似比率为$ 2 log λ$，表明 $A_{maxweight}$ 算法的性能接近最优解的两倍对数级别

  • $A_{dual}$算法流程，如何衡量不可行程度

    1. $A_{dual}$算法调用γ-近似算法$A_{maxweight}$进行α轮。在每一轮中，选择尚未在之前轮次中服务过的作业进行调度。
    2. 在第$ι（ι ∈ [α]）$轮中，从时间$(ι-1)τ_i + 1$到时间$ιτ_i$内调度Ji中未在之前轮次中服务过的作业。
    3. 在每轮中，γ-近似算法的输入是当前轮次尚未服务的作业集合。在第一轮中，根据公式$w(J_{i1}^{s}) \geq \frac{1}{\gamma} w(J^*_{i1})$ 选择作业进行调度。
    4. 对于后续轮次$（ι ≥ 2）$，考虑可以被最优解调度但在前几轮未被$A_{dual}$服务的作业，选择这些作业进行调度。
    5. 通过γ-近似算法的多轮调度，尽可能多地调度作业，以实现最大化总权重的目标。

  • α 的值用来计算在线算法 $A_{online}$的竞争比率/衡量不可行程度
    $ \alpha = \left\lfloor \log \frac{w(J) - \log w_{\text{min}}}{\log \gamma - \log(\gamma - 1)} \right\rfloor + 1 $
    其中，$ w(J) = \sum_{j \in J} w_j $表示作业的总权重，$ w_{\text{min}} = \min_{j \in [J]} w_j $ 表示作业的最小权重，$\gamma$ 是算法 3 中$A_{maxweight}$ 的近似比率。

    通过计算得到的 α 值，可以用来衡量在线算法 $A_{online}$ 的竞争比率，进而评估算法的性能优劣。

  • $A_{maxweight}$如何选择权重最大作业？（第五节）

第四节

介绍在线调度框架$A_{online}$，它将时间跨度划分为ML作业组。使用对偶近似算法$ A_{dual} $来进行作业调度。

$ A_{dual} $原理如下：

  • $ A_{dual} $算法基于一个 γ-近似算法，用于解决最大权重调度问题，即在截止时间之前尽可能安排尚未安排的作业。

    • 在算法中，通过调用 γ-近似算法 $ A_{maxweight} $来执行 α 轮。在第$ ι$ 轮（其中$ ι （iota）∈ [α]$）中，从时间$ (ι-1)τ_i + 1 $到时间$ ιτ_i $安排作业集合$ Ji$ \ $J^s_i$, 即第$ ι $轮中在$ Ji $中但在之前的轮次中尚未服务的作业。每一轮运行长度不超过$ ατ_i$的作业，从而满足各种作业长度的需要；

  • $ A_{dual} $构建出一个所需的调度方案，其长度最多为$ ατ_i$，总权重至少等于相应最大权重调度问题的最优目标值。

$ A_{dual} $用来确定运行多少轮$ A_{maxweight} $.

近似比引出；先引出，证明存在近似比，后计算：

第五节

竞争比率（competitive ratio）指的是在线算法的性能与最优离线算法的性能之间的比率。4α-competitive 表示在线算法的性能是最优离线算法性能的4倍。

$A_{maxweight}$在算法3中的近似比率是 2log λ(某一轮完成的：最优的比例）。近似比率表示 $A_{maxweight}$算法的性能相对于最优解的性能的近似比率。近似比率为 2 log λ 表明 $A_{maxweight}$ 算法的性能接近最优解的两倍对数级别

PPT学习

线性规划方法

介绍了线性规划方法，包括以下几种：

  1. 单纯形法（Simplex method）：沿着多面体边界的顶点序列进行步行，每一步都会改进目标值。
  2. 内点法（Interior-point method）：在多面体内部行走，每一步朝着多面体中的新可行解前进，新解在多面体内部而不是靠近边界。
  3. 椭球法（Ellipsoid method）：通过解决可行性问题来解决优化问题，通过二分搜索将可行性多面体包围在一个椭球内，利用分离神经元验证可行性或将椭球分成两半并用较小的椭球包围可行半部分，当椭球足够小时声称不可行。
对偶

在二元线性规划中，对偶（dual）是指与原始线性规划问题相关的另一个线性规划问题。对偶问题的目标是通过最大化（或最小化）原始问题的对偶函数来解决原始问题。对偶问题的解可以提供原始问题的下界（对于最小化问题）或上界（对于最大化问题），并且在某些情况下，对偶问题的解与原始问题的解是等价的，即它们的最优值相等。

线性规划对偶性质是指在线性规划问题中，原始问题（primal）和对偶问题（dual）之间存在一种特殊的关系。具体性质包括：

  1. 如果原始问题是可行的并且具有最优解，那么对偶问题也是可行的，并且它们的最优目标函数值必须相同。
  2. 原始问题的每个可行解都为对偶问题提供一个上界，反之亦然。

如何使用线性规划对偶性质：

  1. 确定原始问题的约束条件和目标函数。
  2. 根据原始问题的形式，应用线性规划对偶性质，将原始问题转换为对偶问题。 （如何转换？
  3. 解决对偶问题，找到最优解。
  4. 验证对偶问题的最优解是否与原始问题的最优解相关联，并且它们的目标函数值相等。
二元线性规划

在线性规划中，二元性通常指的是线性规划问题中的决策变量是二元变量，即只能取0或1的取值。这种特殊的线性规划问题称为二元线性规划（binary linear programming）。在二元线性规划中，决策变量的取值限定为二元值，通常用于描述一些具有离散选择性质的问题。例如，在作业调度中，某些决策可能是“选择”或“不选择”某个资源，这种情况下可以使用二元变量来建模。

二元线性规划在实际问题中有着广泛的应用，例如在资源分配、作业调度、网络优化等领域。通过将问题转化为二元线性规划模型，可以更好地描述问题的离散性质，并利用线性规划的优化方法来求解问题的最优解。二元性的引入使得问题的建模更加灵活，能够应对更多实际场景中的离散性要求。

参数服务器（parameter server，ps）

将模型参数集中存储在参数服务器上。每次计算节点需要更新参数时，只需要向参数服务器发送请求，参数服务器更新后再将新的参数返回给计算节点，避免了每个节点都需要复制参数的问题。

P24 同步训练（synchronous training）

同步训练（synchronous training）的过程可能涉及以下步骤和特点：

  1. 部署大量并行工作器（workers）：为了训练一个大型模型，可能需要部署数百个并发工作器，以实现并行计算。
  2. 数据并行模型和模型并行模型：可能使用数据并行模型和模型并行模型来实现训练任务的并行化，从而提高训练效率。
  3. 每个工作器训练一个数据块：在同步训练过程中，每个工作器可能负责训练一个数据块，以确保任务的分配和处理的有效性。
  4. 确保作业 j 有足够的工作器和时间槽：为了保证同步训练的顺利进行，可能需要确保作业 j 能够获得足够数量的工作器和时间槽。

通过这些步骤和特点，同步训练过程可以实现大规模模型的训练，并利用并行计算的优势提高训练效率。

mini-batch

在机器学习中，mini-batch（小批量）是指将训练数据集划分为一小批一小批的数据样本进行训练的方法。具体来说，mini-batch是介于全批量（full-batch）和随机批量（stochastic batch）之间的一种训练方式。在mini-batch训练中，每次迭代时模型不会处理整个数据集，而是从数据集中随机选择一小部分数据进行训练。

DPS:边缘云网络中分布式机器学习作业的动态定价和调度

  • 问题：ML用户使用简单的线性定价方法来估计所需资源的数量是不经济的，很有可能做出错误的估计。对需求的低估会降低训练进度，而过高的估计会导致资源利用效率低下。

  • 方法：研究了在边缘-云网络中针对分布式机器学习作业的动态定价和调度问题。提出了在线框架DPS（Dynamic Pricing and Scheduling）。DPS包括作业接纳控制、价格函数设计和调度协调器。通过理论分析证明了DPS具有多项式时间复杂度，并分析了其竞争比。此外，通过测试实验和大规模模拟验证了算法的实际性能。

  • 结论：作者证明了DPS能够生成一个可行的社会福利最大化问题的解，并且具有较高的竞争比。实验结果表明，相对于当今云系统中的基准算法，DPS可以有效地避免资源饥渴，在相同的资源下完成更多的作业。因此，DPS框架在边缘-云网络中的资源分配问题上表现出较好的效果，有望提高作业执行效率和社会效益。

云计算的拍卖过程通常涉及两种实体的互动：拍卖者（auctioneer）和出价者（bidder）。以下是一般云计算拍卖过程的概述：

  1. 用户提交出价：用户在拍卖开始时提交自己的出价，即对所需资源的价格或条件的申请。

  2. 拍卖者确定资源分配和价格：拍卖者根据用户的出价和需求，制定资源分配和价格策略。在云计算中，拍卖者可以是云服务提供商或资源管理系统。

  3. 计算支付金额：拍卖者根据资源分配和价格策略，计算每位用户需要支付的金额。这个过程通常考虑到用户的需求、市场供需情况和公平性等因素。

  4. 资源分配：拍卖者根据用户的出价和支付金额，分配相应的资源，确保资源的有效利用和满足用户需求。

  5. 交易完成：一旦资源分配和价格确定，交易即完成，用户可以开始使用所获得的资源进行计算、存储或其他云服务。

第二节

社会福利最大化问题（social welfare maximization problem）：资源有限的前提下，如何使各方需求得到最大满足。将社会福利最大化问题转化为混合整数非线性规划（MINLP）。这个问题涉及传统约束（资源容量约束）和非传统约束。

  • 传统约束：传统约束指的是资源容量约束，即系统中可用资源的限制，例如工作者和参数服务器的数量、带宽等。
  • 非传统约束：非传统约束包括作业开始时间、作业完成时间和数据传输延迟等。这些约束反映了作业在边缘-云网络中执行时的实际情况和限制。

社会福利最大化的公式如下：

$\operatorname{maximize} \sum_{j \in[J]} x_j f_j\left(\hat{t}_j-r_j\right)$

在该公式中，涉及以下几个要素的解释：

  • ∑$j \in[J]$：表示对所有作业j的求和，即考虑所有作业的社会福利总和。

  • $x_j$ ：表示作业j的决策变量，指示作业j是否被接受。

  • $f_j\left(\hat{t}_j-r_j\right)$：表示作业j的效用函数，其中$\hat{t}_j$表示作业j的完成时间，$r_j$表示作业j的到达时间。作业的效用函数考虑了作业的完成时间与到达时间之间的差异，以体现作业的效率和质量

第三节

对动态定价和在线调度的问题建模，具体内容如下：

  1. 系统设置介绍：第3.1节介绍了系统的设置，包括边缘-云网络中的边缘服务器、远程云、操作员、参数服务器和工作者等组成部分。这些组件共同构成了一个边缘-云系统，用于执行机器学习作业的动态定价和调度。

  2. 拍卖设置和代理互动：第3.1节介绍了拍卖设置和代理之间的互动过程，包括接受或拒绝作业、调度已接受的作业、模拟和计算、提交作业竞标、更新参数等步骤。

  3. 约束条件：第3.2节提出了基本的约束条件，包括作业的资源需求、作业的开始和结束时间、资源的供应和需求等

  • $[X]$: 整数集合 ${1, 2, \ldots, X}$

  • $J, S, T$: 作业数量、物理服务器数量和时间槽数量

  • $j, s, t$: 作业、物理服务器和时间槽的索引

  • $W, P$: 工作者和参数服务器类型的数量

  • $r_j$: 作业 $j$ 的到达时间

  • $f_j(\cdot)$: 作业 $j$ 的效用函数

  • $C_{sw}, C_{sp}$: 服务器 $s$ 上类型-$w$工作者和类型-$p$参数服务器的数量

  • $E_j, D_j, M_j$: 作业 $j$ 中训练轮数、数据块数量和每个数据块中的小批次数量

  • $\Delta^\uparrow_{js}$: 将作业 $j$ 的一个数据块传输到服务器 $s$ 的延迟时间

  • $b_w, b_p$: 类型-$w$工作者和类型-$p$参数服务器的带宽

  • $x_j$: 接受作业 $j$ 的决策变量

  • $o_{jw}, o_{jp}$: 作业 $j$ 是否使用类型-$w$工作者和类型-$p$参数服务器

  • $y_{jsw}(t)$: 服务器 $s$ 在时间 $t$ 分配给作业 $j$ 的类型-$w$工作者数量

  • $z_{jsp}(t)$: 服务器 $s$ 在时间 $t$ 分配给作业 $j$ 的类型-$p$参数服务器数量

  • $p_j$: 作业 $j$ 被接受时应支付的费用

  • $a_j, \hat{t}_j$: 作业 $j$ 的开始和完成时间

  • $\psi_j$: 作业 $j$ 的工作者和参数服务器是否放置在一起

  • $k_{wpj}$: 作业 $j$ 使用类型-$w$工作者和类型-$p$参数服务器训练一个小批次的时间

第四节

DPS（Dynamic Pricing and Scheduling）算法的设计主要包括以下几个步骤：

  1. 决策变量封装：首先，DPS将所有决策变量封装成一个新的变量，然后等价地将原始问题重新表述为一个打包问题。这个步骤有助于简化问题的复杂性，使得算法更易于实现和理解。

  2. 对偶问题制定：DPS进一步制定了对原问题的对偶问题，并设计了拍卖接纳机制。通过对原问题和对偶问题的设计，DPS能够更好地实现社会福利的最大化。

  3. 算法设计：DPS通过模拟每个作业的最佳调度来实现社会福利的最大化，采用了一些贪心的算法来计算最优的工作者和参数服务器的部署。主要包括以下几个关键组件：

    • 作业接纳控制（Admission Control）：DPS算法首先通过作业接纳控制来决定是否接受一个新的作业。在接受作业时，需要考虑系统当前的资源状态、作业的资源需求以及系统的负载情况等因素。作业接纳控制的目标是最大化社会福利，并确保系统资源的有效利用。

    • 价格函数设计（Price Function Design）：DPS算法设计了合适的价格函数，用于确定工作者和参数服务器的价格。价格函数的设计需要考虑作业的特性、资源的供需关系以及系统的整体收益等因素。通过合理设计价格函数，DPS能够实现资源的动态定价，以最大化社会福利。

    • 调度协调器（Scheduling Policy Orchestrator）：DPS算法的调度协调器负责协调和调度已接受的作业，以实现社会福利的最大化。调度协调器需要考虑作业的执行顺序、资源分配方案以及作业的完成时间等因素，以确保系统资源的有效利用和作业的高效执行。

第五节、第六节

第五节和第六节中主要进行了实现和评估的工作，包括以下内容：

  1. 实现测试平台：基于MXNet框架构建了一个测试平台，用于实现DPS作为调度器。该测试平台还包括了Hadoop分布式文件系统（HDFS）等组件，用于支持作业的动态部署和参数的存储。

  2. 实验评估：进行了大规模的模拟实验，通过与基准算法（如FIFO和DRF）的比较，评估了DPS算法的性能表现。实验结果表明，DPS在处理作业数量方面表现最优，能够避免资源匮乏现象，并且相较于基准算法，DPS能够实现更多的作业完成，提高社会福利。

  3. 结果分析：通过实验结果分析，验证了DPS算法相对于基准算法的优势，证明了DPS在边缘-云网络中资源分配和作业调度方面的有效性和性能优势。实验结果进一步支持了DPS算法在实际应用中的可行性和有效性。