Paper Review

OSDI: Elastic Resource Sharing for Distributed Deep Learning虽然说是elastic，但是在分析的时候是只考虑任务本身资源伸缩的开销，而没有考虑context switch的开销。 active-standby用内存空间换switching overhead。 不同的context之间： Multi-Instance GPU（并行）只有NVIDIA H100, A100, and A30支持； time slicing（并发）则从Pascal架构开始支持，而且提出MPS之后，将多个进程的CUDA Context，合并到一个CUDA Context 中，流处理器就可以被不同的kernel函数共享，可以做到和CPU的多进程并发的效果，但他们需要所有的数据都preload到显存中。 多个stream里面的kernel的并行是一直支持的。 switching overhead由四个部分组成： old task cleaning, new task initialization, GPU memory allocation, and model transmission via PCIe from CPU to GPU. observation: DNN models have a layered structure and a layer-by-layer computation pattern 文章的idea就是模型一层层地传，然后边传变算。 the core idea is pipelining model transmission over the PCIe and model computation in the GPU...

作者提出的是一个RL和Constraint Programming结合的求解组合优化问题的模型，在RL环境和约束规划模型中引入了基于动态规划模型的编码，编码后学习部分用强化学习进行，求解部分用约束规划进行。简单来说是用RL来辅助约束规划在搜索解空间时的分支决策。 为什么可以用动态规划呢？强化学习应用于组合优化问题是model-base的，既知道状态转移的情况，也知道reward函数。但是我觉得不是deterministic transition的情况下也是可以的，因为现在有很多model free的模型（AC）。 论文正文中给的例子是用RL的结果辅助分支界定法，RL的结果作为新的分支，分支界定法是会舍弃掉不可行解的，所以处理了约束问题。附录中还提到RL与另外两种搜索策略的结合。 框架： DQN辅助分支界定法： 对于有时间窗口约束的旅行商问题，这篇文章是用GAT去编码。最后实验结果比单纯的DRL或者CP要好，与DRL做组合优化的其他文章相比也更好，而且与现行的工业组合优化求解器相比也有优势。 有时间窗口约束的旅行商问题的SOTA heuristic是A General VNS heuristic for the traveling salesman problem with time windows，前人已经用可变邻域搜索(VNS)的方法解决得很好了，能不能强化学习+VNS？ 代码写得挺好的，RL和CP的主要结合点在这里，分支定界法取分支的时候，由DQN给出一系列Q值，CP选择最大的那个Q值对应的action，把domain分成采取这个action和采取其他action。 基于这种方法，有人还做了一个叫SeaPearl的CP求解器框架，用强化学习作为value-selection heuristics，用图作为输入。 https://github.com/corail-research/SeaPearl.jl

简单介绍 网络规划传统是用线性规划的解法，但是线性规划没有办法scale，设计几十个节点就很难求解，所以一般会加入一些人为的constraint，就需要在解的最优性和问题的易解性上做权衡。而且这些启发性的求解方法不通用，需要专家进行很多检验和重复的工作。 因为网络规划包括多步骤决策和cost的优化，很适合转化为DRL求解，损失函数优化是基于全局的，而人工的决策很多时候都是局部的。DRL需要很高的样本复杂性，不过很多现实中的网络规划都可以用来训练DRL。网络规划评估很方便，检查在所有网络故障情况下是否还能达到了服务的要求，作者的实现是解一个线性规划问题。 论文用一种domain-specific node-link transformation的方法，使用GNN来编码网络图，先用DRL来代替人工操作对搜索空间进行剪枝，然后再求解线性规划问题。我认为本质上是用强化学习辅助解决大型的线性规划问题。 Network Planning 文中的网络规划主要面向的是内容提供商的广域网网络规划，连接不同的机房和数据中心。 网络规划需要同时考虑网络层和物理层。在网络层，网络规划需要决定ip连接的容量，以及路由器和转发器需要配置的数量；在物理层，网络规划需要考虑启动多少条光缆，以及之后应该铺设和购买的光缆。 网络规划是分阶段的，分为短期规划和长期规划。因为网络建设需要的时间周期很长，不能一次就建成最优的网络拓扑结构。短期规划要能够符合之后的长期规划。虽然分为了长期和短期的规划，但是它们的求解方法是可以合并的，具体后面会讲到。 提出优化问题 目的是优化总的网络开销，包括网络层和物理层，还可以根据应用需要，把数据流的时延等因素也考虑进去。为了简化问题，将网络开销抽象为所有ip连接的开销总和，单个ip连接的开销包括ip连接底层用到的光缆的全部开销和实现指定ip容量的每公里开销。 注：spectrum efficiency是指在给定频段上可以传输的信息速率，通常的单位是bit/s/Hz，但是这里的单位是Hz/bit/s。 以往的痛点是网络拓扑太大，求解器无法求解，需要手工做一些剪枝的工作，例如分成几个子拓扑分别求解，合并一些边和点，限制条件一点一点加等，使得整个优化不是基于全局的。同时这些求解的启发性工作也不是通用的，不同的网络规划又需要不同的启发性工作。 NEUROPLAN 对于长期的网络规划，就算一个action的影响只能在后几个周期才会被评估，但是DRL可以设计延迟奖励，学习中会朝着全局目标去采取action。在RL求得该方法的最优值后，引入α因子去得到一个子搜索空间，对优化效果和易处理性上做权衡。 挑战 1. 动态网络拓扑 在网络规划问题上，环境的结构是动态变化的。DRL的输入是一个图，而不是一些向量，而且这个图会根据agent与环境的交互而发生变化。 解决方案：使用GNN将动态的网络拓扑编码成一个向量，作为agent的输入。 2. 优化效果和易处理性的权衡 RL的结果不一定是最优的。 解决方案：分成两个阶段。第一个阶段用DRL找一个较合理的解，第二个阶段在这个解附近的子搜索空间用线性规划尝试找一个最优解。给了一个α参数去调整想要子搜索空间的大小。 合并长短期规划的求解 短期规划是在已有ip连接的网络拓扑上做决策，而长期规划时事先不存在ip连接。在长期规划时，可以将一些之后可能会有的候选ip连接加进去，把他们的容量设为0，然后像短期规划那样求解。 算法 domain-specific node-link transformation 实际意思是将网络拓扑的边映射为点，对于这些点，如果对应的网络拓扑的边有相同的端点，就将这些点连接起来。就是简单的边和点互换身份。 state表示 用当前的容量作为ip连接的状态特征。并对状态每个维度的特征在全局上进行标准化。 action表示 action是给特定的ip连接加容量，每次容量增加有上限而且增加的值不是连续的，每次只增加一个ip连接的容量。就是说如果每次最多可以增加m个单位的容量，有n条ip连接可以选择，那么action空间就是m*n。 作者建议action只能增加容量不能减少，作者宣称只可增加和可增加可减少这两种方案的搜索空间是一样的，同时只可增加的方案action空间更小，而且只要当前情况通过失败检查，那么之后的step也就不用检查了，因为加容量更加容易通过失败检查。 一味增加容量会导致超出光纤的频谱限制，作者对action增加容量的超出部分应用一个action mask，我的理解是屏蔽掉超出限制的连接更新。 reward表示 如果只有一个final reward，训练会非常难，作者用的是dense reward，每次增加容量都给一个reward，但是把累计的final reward放到[-1, 0)。并且超出了预设的迭代次数后会有一个-1的penalty。 强化学习训练算法 Actor-Critic algorithm 值函数是为了解决信用分配问题，能够在延迟奖励到来之前判断动作的好坏 值函数使用状态值函数，而不是动作值函数，因为动作值函数有高偏差（？） 使用全部奖励来估计策略梯度，尽管无偏但是方差大；Actor-Critic方法使用值函数来估计奖励，能够降低偏差但是方差较大 advantage estimates: action相比于其他选择的优势程度，越大说明这一个action越好 GAE是generalize advantage estimator，几乎所有先进的policy gradient算法实现里面都会用到它 GCN 剪枝 把DRL的结果作为线性规划里面的对每个ip连接容量的最大值约束，并乘以一个≥1的α值，作为权衡优化效果和易处理性的参数。 规划评估 给定故障下的流量会不会超出约束，应该就是算一个线性规划问题有没有解。作者还做了些优化，一个是将相同源点的流约束合成一个；一个是“有状态的故障检测”即只要一个网络可以承受住故障，那么比它容量大的网络更加可以承受住故障。 实验 以纯线性规划求解和加入启发式设置的线性规划求解作为对照组。 结果是在纯线性规划求解的规模中，NEUROPLAN差不多持平；在纯线性规划不能求解的规模下，NEUROPLAN的cost可以低于人工启发式设置的线性规划求解。 GNN的层数不太影响结果，在简单问题上不用GNN层数为0也能收敛。 只有在容量更新集中于某些ip连接的情况下，每个step允许增加的单次最大容量才是越大越好。...

不同的DL训练任务在不同的阶段对资源的利用不一样，如果可以让多个DL训练任务交错地安排可以增加并行度和资源利用率 交错和流水线不一样，流水线是任务内的不同阶段重叠，比如网络IO同步和GPU计算前向后向传播之间的流水线，会受数据依赖的限制，交错是不同的任务之间在不同阶段利用不同的资源 交错的困难是任务之间不一定是对齐的，不一定达到理想加速比，而且怎么选择哪些任务在一组里交错以最小化JCT也是一个复杂的问题，还有就是多机多卡的任务不同的worker要和其他任务一起交错，同时又要和其他worker同步，就会有同步开销 两种资源，两个任务的interleave一般图最大权匹配——Blossom algorithm O(|V|^3)的时间复杂度 k种资源，k个任务：maximum weighted 𝑘-uniform hypergraph matching 多GPU的训练任务交错，一个group的任务间的交错和任务内的worker同步会相互影响，发生蝴蝶效应导致全体变慢，这篇文章的做法是使用相同GPU数量的任务之间才能交错 每个interval六分钟，将暂停所有任务重新组队

前言 现在大部分的边缘计算或者联邦学习的论文，都不免得会提出一个组合优化问题。但是我们现在做的很多组合优化问题都带有复杂的约束。 如果想直接用端到端的深度学习去做，无论是DL还是DRL，和传统的求解器相比，都是既没有办法保证能够得到可行解，也没有办法保证最优解。 提高解的可行性的一个很原始的方法是加惩罚项或者在目标函数上用拉格朗日乘数法。拉格朗日乘数法每有一个约束就要给目标函数加一项，最后一个目标函数有成千上万个项就尴尬了。又或者用更复杂的DRL网络结构（HDRL等），获得更好的性能。但是这和现在的计算机视觉任务或者自然语言处理任务刷分一样，在简单问题上你可能有100%的准确率，但是更复杂的问题又没有办法保证准确率100%，可行性和最优性也一样。 因此现在很多工作都喜欢多次采样取最优值，同时大大提高了可行性，但这也还是原始的做法，没有真正解决约束问题。 Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization (AAAI2021) 作者提出的是一个RL和Constraint Programming结合的求解组合优化问题的模型，在RL环境和约束规划模型中引入了基于动态规划模型的编码，编码后学习部分用强化学习进行，求解部分用约束规划进行。简单来说是用RL来辅助约束规划在搜索解空间时的分支决策。 为什么可以用动态规划，强化学习应用于组合优化问题是model-base的，既知道状态转移的情况，也知道reward函数。但是我觉得不是deterministic transition的情况下也是可以的，因为现在有很多model free的模型（AC）。 论文正文中给的例子是用RL的结果辅助分支界定法，RL的结果作为新的分支，分支界定法是会舍弃掉不可行解的，所以处理了约束问题。附录中还提到RL与另外两种搜索策略的结合。 和整数规划相比，约束规划可能小众一点，但不一定差，整数规划只能解线性问题和部分非线性问题，但约束规划可以解更general的问题。想讲这篇论文用的强化学习提供搜索heuristic的思路，这个思路是无关CP和MIP的，只是因为论文比较新才选的，因为新的论文，介绍和相关工作里面也能学到更多。 框架： state: 点的特征，比如时间窗和坐标的静态特征，还有和DP相关的动态特征；边的特征，距离； action: 对应DP的control； transition: 也是DP的转移； reward: 1+UB是一个严格上界，保证reward是正的，避免出现负reward导致提前结束。 DQN辅助分支界定法： 对于有时间窗口约束的旅行商问题，这篇文章是用GAT去编码。最后实验结果比单纯的DRL或者CP要好，与DRL做组合优化的其他文章相比也更好，而且与现行的工业组合优化求解器相比也有优势。 代码写得挺好的，RL和CP的主要结合点在这里，分支定界法取分支的时候，由DQN给出一系列Q值，CP选择最大的那个Q值对应的action，把domain分成采取这个action和采取其他action。 基于这种方法，有人还做了一个叫SeaPearl的CP求解器框架，用强化学习作为value-selection heuristics，用图作为输入 https://github.com/corail-research/SeaPearl.jl A General VNS heuristic for the traveling salesman problem with time windows 这个应该是SOTA heuristic 前人已经用邻域搜索的方法解决得很好了，能不能强化学习+邻域搜索？ Solving mixed integer programs using neural networks（DeepMind和谷歌Research的团队） 提出了两个组件：Neural Diving和Neural Branching。 Neural Diving是通过深度神经网络生成一个partial assignments，然后交给solver去求解剩下的变量 Neural Branching是通过深度神经网络去模仿学习一个剪枝policy。 最先提出用二部图encode的应该是这篇文章(Exact Combinatorial Optimization with Graph Convolutional Neural Networks)。...