并行计算与机器学习

1. 机器学习所需的计算成本很大（提出问题）

数据集的规模和模型的维度都是巨量的，epochs很大（将本地数据全部扫一遍是一个epoch），完成一次训练需要跑很多轮模型，且每调一次超参数就要重新训练一次。所以需要借助并行计算来提高计算效率；其次，如果不懂并行计算的话，当程序运行的时候，根本不知道哪里出错。

2. 怎么提高计算效率（解决计算成本问题）

主要通过提高计算梯度的效率，使模型尽快收敛，具体通过多个GPU（分摊计算样本的任务量）并行计算来加快计算梯度的速度；

3. 提高效率的难点——处理器之间的通信

并行梯度下降，要对数据作划分，还要把参数w和梯度g传来传去。
（1） 通过共享内存(sharing memory)进行通信，没有办法做到大规模的并行；
（2） 通过消息传递(message passing)进行通信，适合很多个节点的通信，每个节点都有几个处理器，节点内的处理器可以共享内存，但不同节点间无法共享内存，节点之间要进行消息传递，可以把向量打包通过网线或TCP/IP协议发送。

4. 消息传递的难点——怎样让节点协同工作

（1） client server架构，把一个节点作为server来协调其他的节点，把其他的节点全都作为work用来计算；
（2） peer to peer架构（点对点），所有的节点都拿来做计算，每一个节点都有几个邻居，邻居之间可以通信。

5. 并行梯度下降的实现（同步）

使用MapReduce（hadoop,spark），是client server架构。

（1） broadcast：server把最新模型参数w广播到所有worker(m个)；
（2） map：设置函数，每个worker都通过本地数据和模型参数Wt并行进行，各自计算一部分梯度得到m个向量；

（3） reduce：将每个worker的向量传回server，server将m个向量根据设置的函数合成一个梯度向量g；
（4） 有了梯度g，server可以做一次梯度下降得到新的模型参数Wt+1 ；

（5） 系统不断重复上述MapReduce过程直到算法收敛，理想状态下运行时间减少到1/m，但是并行计算有通信和同步的额外代价。

6. 并行计算额外的时间成本

并行计算的加速比=m个节点运行时间/1个节点运行时间（理想状况下为m）

（1） 通信代价（通信时间=通信复杂度/网络带宽+网络延迟）
通信复杂度：与模型参数，节点个数正相关（尽量减少通信内容的大小）；
网络延迟：与系统和网络有关，与传多少信息无关（尽量减少通信的次数）。
（2） 同步的代价
所有worker算完了才能进行reduce。并行计算同步的时间由跑的最慢的那个worker决定，如果一个节点挂掉了重启就会比其他节点慢很多，这个挂掉的叫struggler（节点越多，同步代价越大）。

哔哩哔哩：
https://www.bilibili.com/video/BV18z411h7Ub/?p=2