并行计算与机器学习（2月13日）

Parallel Computing for Machine Learning

Why Paralle Computing for ML？为什么做机器学习需要懂并行计算？

深度神经网络：神经网络都特别大，参数特别多，计算量大，必须要有足够多的数据

大数据训练大模型计算量是非常可怕的

例如用ImageNet训练ResNet神经网络，需要迭代90 epochs才能收敛，将数据扫一遍叫一个epoch，如果只用一个GPU做训练需要14天才能收敛

实际上，神经网络里面有很多超参数，必须要调这些超参数，才能获得更好的结果，

因为调了一个超参数，就需要将神经网络重新训练一遍，因此时间会很长

并行计算可以减少计算时间

这里的时间指的是wall-clock time，和平常所说的GPU、CPU时间是不同的

CPU时间指的是所有参与计算的CPU的总时间

比如说有20个CPU，全部都运行一天，那么CPU time就是20天

做并行计算可以减少钟表时间，比如说，从14天降到1天

但是并行计算并不会减少CPU和GPU时间，因为总计算量并没有减少

TensorFlow已经提供了线程级的并行计算，所以可能不需要写并行计算的程序，但是一定要知道并行计算的原理，当程序不work的时候，都不知道问题出哪儿了

线性回归和最小二乘

线性回归的输入是一个x，比如说x是一个房子的特征，房子有100个特征，那么x就会100维的向量，用一个线性模型去预测房价，w参数，向量的内积可以写成标量的连加，用特征的加权平均作为房子的估价

用过去的数据训练出参数W

还需要一个损失函数L(w)

找到一个w，使得损失函数最小

最小二乘回归

并行梯度下降来解最小二乘

L(w)是n个差的平方的连加，为了最小化损失函数，我们需要求梯度，梯度是L关于变量W的一阶导数

这个是标量对向量的求导，所以得到梯度也是一个向量，梯度和W的维度肯定是一样的

梯度物理意义，在一个点W上沿着梯度方向g(w)走很小一步，这个函数L(w)肯定是上升的，如果沿着梯度相反的方向g(w)走很小一步，这个函数L(w)肯定是下降的

目标是找到一个w使得L(w)越小越好，希望L(w)的值是越来越下降的，所以可以沿着梯度相反的方向走一小步

整个算法需要迭代成百上千轮，每一轮都需要算一个梯度，计算梯度的代价是比较大的，需要对每个样本算一个g(w)，然后全都加起来，所以样本越多，计算量越大

计算量和w和x的维度也有关系，维度越高，计算量越大

求神经网络也是同样的道理，参数越多，样本越多，计算越慢

梯度就是算法的瓶颈

如果将计算梯度并行化，那么计算就会越快

复杂在于怎么通信，

处理器之间的通信，1、共享内存，一个处理器可以看到其它处理器的内容，但是没法做到大规模并行，无法支持几十个CPU或GPU的计算，规模上不去

2、message passing，消息传递，有多个节点，每个节点都有多个处理器，节点的处理器是可以共享内存的，但是节点之间是无法看到内存的

client-server架构，将一个节点作为server来协调其它节点，其它节点都作为worker，来做计算，

Peer-to-Peer架构，这种架构没有server，所有节点都用于做计算，每个节点都有几个邻居，邻居之间可以通信

并行梯度下降集中不同的实现方法：

1、MapReduce

google开发，大规模数据分析和机器学习

架构是Client-server，通信是message passing

并行是同步的，bulk synchronous

每一轮必须等待所有的worker都完成工作才能进行下一轮

mapreduce不开源，所以外部就有了很多mapreduce的开源实现，最成功的是Apache Hadoop，java所写，但是还达不到google mapreduce的性能

几年之后，伯克利开发Apache Spark系统，也是mapreduce的编程模型，区别在于spark将所有都放在内存里，而不是写入磁盘，spark有很好的容错机制，spark会比hadoop快很多很多

mapreduce用于做机器学习效率并不是很好

Map Reduce基本操作：server与worker之间可以通信，server可以将信息广播broadcast到所有的worker节点上，比如傲并行梯度下降的时候，server需要将模型参数广播出去，每个worker节点都可以做计算，如果我们要实现算法，我们需要自己定义一个函数，然后所有的worker都会运行这个函数，这一步叫做map，map操作是由所有的worker并行做的，做并行梯度下降的时候，每个worker都用自己的数据去算一部分梯度，这一部分的计算量比较大，这就是map操作，reduce操作也需要通信，worker会将它们的计算结果传回server，然后server将这些结果整合起来，如果用一个叫sum的reduce函数，server就会将所有的这些结果全部加和，结果也是一个小矩阵

用map reduce做并行梯度下降，我们有很多个数据样本，每个样本是一对x和y，x叫做input，或者feature，y叫做target，或者label，数据并发，data Parallelism，意思是数据划分到worker节点上，每个worker都有一部分数据样本

用map reduce实现并行梯度下降，需要重复以下几个步骤：

1、sever要将最新的参数wt广播到所有的worker节点上，这样worker就知道wt了，这一步需要server和worker之间的通信

2、然后worker会做map操作，这一步不需要通信，map操作会将x、y，w这三个变量映射到g上面，n个数据样本映射到了n个向量

3、reduce操作，每个worker会将自己的存的gi全部加起来，得到一个向量，这样一来，每个worker就只有一个向量，然后worker会将这个向量传到server上去，server将每个worker的向量全部都加起来，reduce操作之后，server就得到了g，g就叫梯度，server有了梯度g，sever就可以做一次梯度下降，得到新的模型参数

重复以上步骤，直到结果收敛

如果由m个节点，那么每个worker只存储1/m的数据，每个worker只做1/m的计算，算法计算时间是否减少到原来的1/m了呢？理想情况下是的，但是实际上并没有这么大的加速，虽然计算量减少到了1/m，然而并行计算会有通信和同步的代价，通信和同步都是需要花时间的，如果算上，加速则没有m倍，

加速比：speedup radio = wall clock time using one node/wall clock time using m nodes

实际上，随着节点数量的增加，加速比增长越慢

通信代价：

如果算法设计或编程实现不够好，通信的时间可能会比计算的时间还长，造成加速比非常低

通信代价主要有两方面：1、Communication complexity，通信复杂度，server和worker之间需要传输多少word或者多少个bit，通信复杂度正比于模型的参数，模型越大，通信复杂度越高，也会随节点数量的增长而增长，节点越多，通信复杂度越高；2、latency，网络延迟，通信的时候，向量和矩阵都是压缩成多个packet的，通过网络传输，worker发送一个packet，server不会立刻马上接收到，哪怕这个包只有一个bit，也需要时间传输，这个代价叫做网络延迟，由计算机网络和软件系统决定的

Communication time = complexity/bandwith + latency

通信的矩阵向量越大，通信的复杂度就越高，时间就越慢

网络延迟和传多少参数没有关系，每次通信都有延迟，通信次数越多，延迟越大

还有一部分开销是由同步synchronous造成的，server将参数广播出去，发到每个worker上，worker同时开始做计算，理想的情况是所有的worker同时完成计算，但是实际情况worker会有快有慢，假设碰巧有个worker挂掉了然后重启，那么这个worker就会比其它的慢很多很多，这个现象又叫straggler，等所有的worker都完成计算了，系统才能开始做reduce，这就意味着所有的worker必须等最慢的worker

mapreduce本身就是同步的，同步当然会有代价

节点越多，出现节点挂掉的概率就越大，straggler就会越严重，如果用map reduce这样同步的系统，节点数量越多，同步造成的时间开销就会越大