前言 我是一个记忆力不怎么好的人，很多大大小小的经历，过去了之后只会留下一个大概的印象，细节则会随着时间的流逝逐渐淡去。于是从今天开始，我会将一些学习和生活上的心得发在这个博客上，既为了分享也为了记录。虽然我不是一个爱码字的人，我的博客也不会有多少人看——所以非常感激正在看这篇文章的你——但是我也会尽量写得认真一点。
由于读研选择了边缘智能这个方向，而边缘计算又是从云原生的概念中延伸出来的，所以我觉得有必要在第一年对一些分布式系统相关的知识进行补全，MIT6.824是我的第一个计划。MIT6.824这个分布式系统课程有四个广受好评的实验，这里先挖个坑，希望能在一个学期内完成它们并记录下来。当然我的代码写得并不好，大家看看图一乐就好，有什么改进的建议也非常希望能够联系我。
什么是MapReduce MIT6.824第一个实验是实现一个MapReduce，这是谷歌最早的用于处理大规模数据的分布式计算模型，为复杂的计算任务提供了可扩展性和容错性。
对于一个工作，可能是统计单词数量或者统计单词出现位置，MapReduce将它分为Map和Reduce两个任务，Map过程是Map Worker将初始内容按要求处理成一些键值对，并且根据键的不同，将这些键值对分类保存起来，以提供给不同的Reduce Worker，这个分类保存的过程也就是Shuffle；Reduce过程则是将这些键值对进行进一步归并，按照键将所有的值聚集在一起，得到最后的结果。下面的伪代码是MapReduce的一般形式。
map (k1,v1) → list(k2,v2) reduce (k2,list(v2)) → list(v2) 在原论文中，除了阐述了MapReduce的工作过程，还提出了很多实际实现上的优化，如Combiner Function，Backup Task等。这是它的论文链接：https://research.google/pubs/pub62/，在这里就不再细说了。
RPC部分 实验使用Golang作为编程语言，并通过开启不同的进程来模拟不同的节点。而对于模拟节点之间的通信，则使用Unix domain socket的跨进程通信，Golang的RPC库的具体细节就不再本文中赘述了。
接下来分析模拟节点的通信。首先Worker之间并不需要通信，而对于Coordinator和Worker之间的通信，只需要以Coordinator作为RPC服务器，并实现Worker的RPC调用，用于Worker申领工作和Worker完成工作后汇报。接口定义如下，GetTask用于Worker向Coordinator申领工作，MapTaskDone和ReduceTaskDone则是Worker完成工作后向Coordinator汇报。
type GetTaskArgs struct { } type TaskType int var ( TaskTypeOff TaskType = 0 TaskTypeMap TaskType = 1 TaskTypeReduce TaskType = 2 TaskTypeWait TaskType = 3 ) type GetTaskReply struct { JobId string TaskType TaskType TaskId string Content []string NReduce int64 ReduceTaskIndex int64 } type MapTaskDoneArgs struct { MapTaskId string IntermediateFileNames []string } type MapTaskDoneReply struct { } type ReduceTaskDoneArgs struct { ReduceTaskId string OutputFileName string } type ReduceTaskDoneReply struct { } Coordinator 首先关注Coordinator的结构体定义，MapReduce对于每一个新的工作都需要指定Coordinator，所以需要有一个唯一的JobId来标识该工作；同时需要一个状态变量来指示工作现在进行到什么阶段，并保存每个MapTask和ReduceTask的状态；显然这个结构体需要被来自不同的节点修改，所以需要在每次修改时加锁，防止出现Data Race，因此Mutex变量也作为结构体成员保存。...
不同的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)。...