Posts

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...

前言 Ray主要是想做一个集成分布式训练、推理和环境模拟于一身，但是彼此又不耦合的分布式框架。经过合理的模块化，每个环节还可以接入不同的系统，例如为训练接入Horovod/torch.distributed，为推理服务在Kubernetes上运行Ray等，让用户可以在一个分布式应用上组合多个库。 Ray更关注的是horizontal scalability和low overhead，当然scalability一般还会要求reliability。Ray的存储是个分布式的内存共享机制，通信基于gRPC。 一个简单的Ray使用示例： Application concepts Task - A remote function invocation. This is a single function invocation that executes on a process different from the caller, and potentially on a different machine. A task can be stateless (a @ray.remote function) or stateful (a method of a @ray.remote class - see Actor below). A task is executed asynchronously with the caller: the .remote() call immediately returns one or more ObjectRefs (futures) that can be used to retrieve the return value(s)....

Horovod 在18年其他框架的分布式训练不成熟的时候，率先用NCCL和MPI实现了ring allreduce。 Horovod Timeline Tensor Fusion Ring-allreduce utilizes the network in an optimal way if the tensors are large enough, but does not work as efficiently or quickly if they are very small. One of the unique things about Horovod is its ability to interleave communication and computation coupled with the ability to batch small allreduce operations, which results in improved performance. We call this batching feature Tensor Fusion....

作者提出的是一个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允许增加的单次最大容量才是越大越好。...

前言 10月份没有更新过博客，一个原因是自己太懒，没有养成写博客的习惯，但主要的原因还是自己太摸，没有什么工作值得记录的。这个月断断续续花了两周时间，把6.824的Lab2给实现了，稍微总结一下水过这个月吧。第一篇博客发完之后我意识到贴代码可能不太合适，因为这是别人学校的作业，但是转念一想不会有什么人会看到我的博客吧（哈哈哈）。无论怎样，之后的Lab还是不要把我的菜鸡代码贴上来了。 6.824的Lab2主要是实现Raft论文里除了configuration change之外的所有内容，包括Leader Election、Log Replication和Snapshot，其中Log Replication包括了减少AppendEntries RPC匹配错误的优化。这篇博客的侧重点更多是在实现方案上的讨论，Raft的核心主要就在这两张精简图里面了，关于Raft的算法本身，请直接看作者的论文：https://www.usenix.org/system/files/conference/atc14/atc14-paper-ongaro.pdf Leader Election 首先，我们需要一个计时器去控制Election Timeout的计时，在Election Timeout被触发时server成为候选人，进入选举流程。如果server接收到leader的请求或者投票给一个候选人时，需要重置计时器，所以计时器还需要随时检查自己是否已经被重置。这种情况下使用channel和信号量都不是很方便，因为阻塞的时候想要重置的话实现起来很麻烦，所以我用的是一个保存在server元数据结构体中的状态变量，在一个循环中“锁-检查状态-释放锁-sleep”的笨办法。 server成为候选人后，需要给其他server发送投票请求，但是如果使用并发发送请求的策略，有时候我们不知道其他server有没有回复，如何统计大多数人的回复呢？这里我在每个发送投票请求的函数中带了一个计数变量的指针，在投票请求回复同意后对这个计数变量进行原子性的自增操作，如果检查到计数变量超过大多数，就进入leader初始化的阶段。在我的实现里，其他server是有“一票否决权”的，被一票否决后server会从候选人变回follower并重置计时器，所以在投票请求回复后还需要检查自己还是不是当前term的候选人。 其他server在决定要不要投票的时候，需要确定对方是不是"at least up-to-date"，也就是对方的term必须至少跟自己一样，如果对方的term跟自己一样则最后一个log entry的索引要至少和自己一样，否则就直接一票否决。 server在成为leader之后，需要进行一个no-op，即马上增加一个当前term的空日志并发给其他server，否则会导致存在一致性的隐患。实验中会因为实现了no-op而导致测试不通过，因为部分测试对log的索引顺序有要求，需要魔改一下测试。 我选择的Heartbeat Timeout是50ms，Election Timeout是150ms到300ms，使用助教的并行测试脚本，进程数等于逻辑核数量时测试可以稳定通过。 Log Replication AppendEntries leader发送AppendEntries RPC请求主要是根据对应follower的next index来决定是发送log entry还是仅发送heartbeat，当接收到超过半数follower的确认后，leader就认为这个log entry是可以commit的，便会提交apply并在下一次AppendEntries RPC请求通知其他follower也提交。有时候leader可能因为经历了网络隔离后是落后的，这时follower对leader的AppendEntries RPC请求会回复自己的term，leader收到后会回到follower状态。如果是leader本身接收到了来自更高term的leader的AppendEntries RPC请求，那么他应该直接成为新leader的follower，因为这里隐藏的含义是有超过半数的server在一个更高的term里投出了一个leader。 对于follower，AppendEntries有很多需要注意的地方。如果请求的term比自己大，需要把自己的last log index回复给leader；如果请求的term比自己小，需要把自己的term回复给leader；如果不是自己投出来的leader，忽略请求；如果匹配错误(last log index < prev log index或者prev log index对应的term不对)，也返回不成功。写入log时要注意，如果发生了重写，last log index不一定是log slice的最后一个元素，需要进行一些处理来分成rewrite和append两类操作。 在我的实现中，无论是leader还是follower，在commit index发生改变时都会马上提交apply，并且等所有apply都推到apply channel后才继续执行之后的代码。相比于计时器定时apply，状态变化的复杂性会少一点。 在我的实现中，last log term和last log index都是有额外的变量保存的，并且和log保持一致，因为有时候AppendEntries RPC匹配错误之后，如果不作额外标识，很难直接定位到最后一个有效的log entry。不过如果只保存last log index也是可以的。 Persistence 需要持久化的变量如下，每次变量发生变化的时候都要进行持久化。其中offset会在后文Snapshot中使用到。 Log []*LogEntry Offset int Term int VoteFor int LastLogIndex int LastLogTerm int LastApplied int Snapshot snapshot在实验框架中的实现是这样的：由上层服务向raft发起snapshot的请求，raft会收到一个snapshot的数据，raft只需要将它持久化即可。在follower需要得到一个snapshot时，leader将自己持久化的这个snapshot的数据取出来发给follower，follower如果确定这个snapshot是最新的，就将它发送到apply channel，并在上层的applier中再次调用follower的接口实现snapshot的安装。...