[Comm/DLT]Taming Unbalanced Trai
论文题目：Taming Unbalanced Training Workloads in Deep Learning with Partial Collective Operations
文章时间：2019.08 arxiv
会议/期刊：PPoPP 2020-02-17
作者背景： 中科院计算所
笔记时间：2021年09月17日周五
论文地址: PPoPP
引用：19+
Abstract
负载不均衡广泛的存在于深度学习训练的过程中，由于任务内存的特性或者系统本身的原因。
传统的同步随机梯度算法在很多领域有着很好的结果，但它依赖于每次全局同步来准确的计算梯度。
本文中，我们提出了一个新的随机梯度下降算法，eager-SDG，放松了对分布式计算的全局同步要求。
为了实现算法，本文提出两种部分集合通讯算法，solo and majority；solo模式只需要最快的节点返回结果，majority模式下只需一半节点返回结果。
我们从理论上证明了方法的收敛性，and详细描述了partial collective
在不均衡的负载环境，我们得到了加速而不损失准确率的结果。
Motivation
深度学习现在是并行和分布式系统中最重要的workload。先前卷积神经网络在计算机视觉上取得了破天荒的进展，图形分类到物体识别。新模型越来越大，训练所需要的时间也越来越长，有些模型直接就要在超算上运行。模型在以指数级别增长，每年能涨10倍。为了支撑规模的增长，对训练过程进行优化是非常有必要的。
DL训练过程是高度并行的，但是受限于通讯。数据并行中，allreduce的规模随着模型的规模变化而变化。而allreduce 本身不是原子化的，也是可以被拆分并隐藏在计算周期中的。
Yet, the optimal scaling of an allreduce of size 𝑆 is at best O (log 𝑃 + 𝑆) in 𝑃 processes [26, 43, 47].
这段理论分析没搞清楚，需要后面再看看。
本文的工作中，我们把负载不均衡当作可扩展性的额外的一个阻碍。负载均衡可能发生在多云湖的云环境中，或者由于网络/系统的噪声，也可能是由于workload内在的问题，比如NLP中不同长度的语句，视频拥有不同的frames。
训练过程其实有着一定的鲁棒性，因为训练过程中会有dropout，cutout这类随机的过程。一些工作利用了这些特性，（1）通讯权重被量化为更有代表性的数字；（2）只有最重要的weighs才会被传输；（3）用gossip算法随机将更新结果传输给附近的邻居
本文探索了一种新的鲁棒算法，partial reduce。
solo算法不能保证收敛（ guarantee bounded error），为majority的方法不是完全wait-free。我们为每种算法都找到了合适的应用场景。
-
深度学习中的负载不均衡
2.1 视频处理
2.2 语言处理
2.3 云上训练 -
分布式深度学习
介绍了分布式深度学习训练的流程
4.部分集合通讯操作
4.1 Schedule Activation
定义schedule 是一系列操作的合集。
定义了原子操作：点对点通信，计算，无操作。
solo collective中，任何一个process 都可以成为initiator；
majority collective中，从P个process 中任选一个作为initiator；
4.2 majority collective
4.3 Asynchronous Execution by Library Offloading
实现了一个库，ffflib2
5 Eager-SGD algorithm
使用partial collective的梯度下降算法
-
理论验证
没有认真看 -
实验证明
很充分，做了很多模拟实验，还有一个video的case study
8.相关工作
8.1 深度学习
PS架构中的SGD算法有多种改进，synchronous [20, 38], asynchronous [11, 13], stale- [22,
62], and approximate-synchronous [29] SGD。
本文是第一个
To the best of our knowledge, this is the first work that implements asynchronous and stale-synchronous decentralized SGD where the messages propagate to all nodes in one step
8.2 集合通讯
allreduce的最优算法取决于网络拓扑，处理器个数，消息大小。
9.结论
文章的idea很好理解，也很自然能够知道这个idea works。但是方法很朴素，缺陷也很明显，每次迭代只要一个或者少量结果，对资源的浪费如何。
随机选initiator，遇到波动或者干扰怎么办。
引用，改进的文章也有几篇了，比如
sigmod21- Heterogeneity-Aware Distributed Machine Learning Training via Partial Reduce
sc20-Herring: rethinking the parameter server at scale for the cloud
可以做一个交叉阅读
