CSE_lecture24:distributed computing

The distributed (and parallel) programming: it’s all about scalability

训练模型的计算分为两步：前向传播和反向传播

对于前向传播，每层计算 $Y = W \circ X$，假设：

$W: m \times k \ X: k \times B$

则近似的计算量为 $(2k - 1) \times m \times B \sim = 2 \times Size(W) * B$，对于前向传播的所有层求和即可：$2 * B * parameters$

对于反向传播，每层计算 $dX = W \circ dY (k \times m \circ m \times B)$ 和 $dW = dY \circ XT(m \times B \circ B \times k)$，则dX计算量为：$(2m - 1) \times k \times B \sim = 2 \times Size(W) * B$，dW的计算量为：$(2B - 1) \times m \times k \sim = 2 \times Size(W) * B$，对所有层求和即可：$4 * B * parameters$

综上，一次训练的计算量为：$6 * parameters * Batch_size$

并行计算可以提高计算的规模

single chip device

对于CPU而言，每秒能做多少次浮点计算(FLOPS)，取决于每秒能给ALU提供多少指令，即clock rate；也取决于流水线，从而充分把clock rate利用起来。理想状况下没有bubble，此时FLOPS约为clock rate

对于单核CPU，为了提升并行度，需要提高pipeline的并行度，更深的pipeline的bubble更少；超标量（即指令级并行，ILP）每次发射多条指令，尽可能让它们并行计算，但超标量不能太大，否则复杂度会指数上升，受限于芯片的物理面积

approach #1: 使用多核来规避dependency tracking的问题，使用多个CPU，彼此互相独立，减少软件层对dependency的判断，但代码为了利用多核，需要显式分配pthread

多核相互独立的代价就是CPU之间无法共享，因此需要引入cache coherence协议，使用全局的directory来存放每个数据的最新值位于哪个CPU上，代价是directory会成为性能的瓶颈，需要限制核数来保证更强的consistency model，而GPU则是在超多核的情况下完全不使用cache coherence

approach #2: 每个CPU有多个组件，但多核没有充分利用这些组件。因此另一个方法为给每个CPU增加ALU数量，限制在于ALU需要执行相同的操作。SIMD即可实现计算的加速，但问题在于将8个计算并行处理时，性能只提升到了2倍，这是因为计算脱离了缓存

accessing memory & roofline model

一次内存读取的时间足够做几百个ALU操作，拖累了算力的提升。为了优化引入了prefetch，即将下一个可能的内存读取上来，这并不总是有效

内存操作受限于内存延迟(memory latency)和内存带宽(memory bandwidth)，对于prefetch而言更重要的是后者，公式为 $load_time = latency + payload / bandwidth$

roofline model可以判别计算受限于算力还是访存。模型的y轴为算力(Gflops/second)，其中peek flops为算力的上限，当达到peek flops时说明受限于算力。x轴则是每读一个byte能做多少次计算(flops/byte)，越大说明访存次数越少，因此斜率为带宽(bytes/second)