研一课程笔记-并行计算

一、多核体系结构概述

指令级并行

在多核时代到来之前，倾向于提升晶体管集成度，通过集成，可以将更多的原本片外的部件集成到片内中，从而开发出了诸如流水线、乱序执行、动态分支预测和缓存等，这些“低挂果”虽然硬件实现较为复杂，但生产之后的成本相对较低，开发人员无需考虑数据竞争、同步、通信等问题。

逻辑复杂度：例如超标量处理器中大部分部件都用于确保指令的分隔执行。
功耗问题：功耗和电容 $C$ $C$ 、电压 $V^2$ $V^{2}$ 和时钟频率 $f$ $f$ 相关， $C$ $C$ 和集成度相关， $V$ $V$ 如果降低，将导致 $f$ $f$ 变慢。
- $f_{\max}=c\frac{(V-V_{\mathrm{thd}})^\alpha}V$ 。其中 $V_{thd}$ 为阈值电压
- 如果降低阈值电压，则会导致处理器静态功耗指数级增长

数据级并行

由于之前的问题导致集成度无法再提高，频率无法再提升，产生了多核概念。

并行计算机分类：

SISD，串行体系结构通用模型，但可以实现指令级并行
SIMD，多用于向量处理器结构
MISD，多个计算单元依次对同一个数据进行处理，受限于工作模式、应用场景
MIMD，并行计算机常用结构

MIMD常用体系结构

1、共享高速缓存 2、共享存储器 3、存储器互连 4、分布式集群

受限问题：

并行编程复杂度，对数据结构有要求
多核间通信导致额外开销，边际效应甚至负增长
外围复杂度提升，如“带宽墙”，同样也存在“功耗墙”
Amdahl定律，解释了串行部分 $s$ 成为限制加速比的最大因素，且由于多核的设计，也会额外增加开销到 $s$ 上

二、并行编程概述

并行程序的限制因素 Amdahl’s law

$Speedup_p=\lim_{p\rightarrow+\infty}\frac{1}{s+\frac{1-s}{p}}$

$s$ 为串行部分(不可并行化)， $s$ 为核数，当 $s=0.01$ 时，100个核也只能提升50倍，同时并形程序额外的开销也将计入 $s$ 中，特别的，当把这一部分开销代入上述公式时，加速比逐渐出现边际效应，甚至是负增长。

当 $p\to +\infty,Speedup_{+\infty}=\frac 1 s$ ，也就是说最大加速比是受限于 $s$ 的。

也就是说，我们可以通过将不可并行化的部分通过任务分解实现并行化，但这其中存在两方面问题，一方面是不同并行任务耦合造成的通信与同步的额外损耗，另一部分是为了保证同步造成的某些并行任务必须等待其他并行任务完成，而造成的资源利用率降低。如：

线性加速比与超先行加速比

在理想情况下，如果一个程序可以被完全并行化（即 $s=0$ ），加速比将会是 $Speedu_p=p$ ，它被称为线性加速比（linear speedup）。线性加速比是理论上可获取的最大加速比。然而在实践中，一些程序在某些个数的处理器上会呈现出超线性加速比，即它们的加速比超过了线性加速比。其原因是，随着处理器个数的增加，综合的资源量（如总的Cache和内存容量）也在增长。在多数情形下，程序的工作集合是大于总Cache容量的，然而在某个临界点，通过增加额外的处理器，这一情形可能会被改变，即程序的工作集合可以装入Cache空间，此时，Cache缺失率会显著下降，所有线程的执行速度更快，由此产生超线性加速比。

改进冯诺依曼—流水线

流水线优化

指令冒险

结构冒险
- 由资源竞争引发(如寄存器堆端口, 访存)
- 除非代价太昂贵，可以通过增加资源加以避免
数据冒险
- 由于程序中的依赖性导致(RAW, WAW, WAR)
  - 内存和寄存器操作数的访问都会引发
- 数据依赖和数据冒险是有区别的，如图流水线中
  - 寄存器的RAW 依赖是唯一会导致寄存器数据冒险的依赖关系，因为所有的指令都会按照操作的序流过所有的流水段
  - 内存操作数不存在数据冒险，因为只有一个访存阶段执行内存的读写
- 操作数分别为寄存器和内存的RAW会产生数据冒险
控制冒险
- 分支, 跳转, 异常等

异常

流水线的收益来自于指令执行开销的重叠，当指令流突然’中断’的时候（发生异常）会产生错误
许多的异常必须是精确的，当一个异常是精确的时（同步并且可在断点处恢复)
- 所有在出错指令之前的指令必须完成
- 出错指令和它之后的所有指令必须被销毁（清空）
- 异常处理程序必须开始执行
通常不适宜在异常发生的周期中立即处理异常，因为
- 同一个周期内可能发生多个异常
- 在不同的流水段处理异常会比较复杂
- 异常处理必须按程序处理的序而不是时间序

通常，当异常发生时标记它并记录导致异常的原因，保持“安静”直到指令流水到写回阶段再处理