摘要：2017-9-15 苟兄关于SIMD的分享，次日查阅资料并整理成记录。
并行计算是为了解决大批量数据的处理问题，使用时间并行或空间并行的方式实现数据的并行处理。而SIMD是通过采用单控制器控制多处理器从而实现空间并行的技术。流水线化是SIMD的重要思想，但其过程中可能会发生分支跳转问题，分支预测可通过预测分支是否会跳转从而较好地解决这一问题。
一、并行计算parallel computing
- 许多指令同时进行的模式，化整为零以并发方式解决。
分类
- 时间并行：流水线技术；
- 空间并行：使用多处理器执行并发计算；
- 数据并行：化大为小
并行算法
- 算法设计的最常用方法：PCAM（划分-通信-组合-映射）
- 划分：化一为多，让各处理器去同时执行
- 通信：分析执行过程中要交换的数据和任务的协调情况
- 组合：将小问题组合解决以提高性能和减少任务开销
- 映射：将任务分配到每个处理器上
二、SIMD（single instruction multiple media）
- 实现数据级并行的技术
- 单指令多数据流；数据级别的并行；无需多线程配合；可与多线程配合；
- 单指令流多数据流：是一种采用一个控制器来控制多个处理器，同时对一组数据（又称“数据向量”）中的每一个分别执行相同的操作从而实现空间上的并行性的技术。
- 关键：在1条单独的指令中同时执行多个运算操作，以增加处理器的吞吐量。
- 特别适合于多媒体应用等数据密集型运算
pipelining 流水线化
- 延时：单条指令从开始执行到执行结束所花的时钟周期数
- 吞吐量（CPI：cycles per instruction）：平摊到每条指令所花费的时间
- 优化方法：解除依赖，减少代码体积
形象举例：洗衣服的步骤
通：洗第1件-烘干-洗第2件-烘干…
并行高效(流水线化)：洗第1件-洗第2件+烘干第1件-洗第2件+烘干第2件…
以加法指令的处理流程为例说明：
指令单数据流SISD：对加法指令译码——>单处理器访问主存、取得第1个操作数——>再访问主存、取得第2个操作数——>求和运算；
IMD：指令译码——>几个处理器同时访问主存、一次性获取所有操作数——>求和运算
optimization
- 浮点转整型计算；尽量采用单精度浮点；（浮点数的表示方法,浮点数分离，消耗性能）
- 精简指令，减小代码体积（乱序执行-并行执行）
内存对齐
- why：CPU按双字、字、字节访问存储内存，并通过总线进行传输，若未经一定规则的对齐，CPU的访址操作与总线的传输操作将会异常复杂，故编译器中都会对内存进行自动对齐。
- sizeof：判断数据类型或表达式长度的关键字；字节数的计算在程序编译时即进行；
- 类型长度：如C++中使用sizeof得到的结果；
- 数据成员对齐：struct首地址是struct内第一个数据成员的地址；
- 数据成员对齐规则：在第一个成员之后，每个成员距离struct首地址的距离 offset， 都是struct内成员自身长度（sizeof） 与 #pragma pack(n)中的n的最小值的整数倍，如果未经对齐时不满足这个规则，在对齐时就会在这个成员前填充空子节以使其达到数据成员对齐。
- 整体对齐：与数据对齐相似但不是完全相同，如果数据对齐完成时struct的大小不是 struct内成员自身长度最大值（sizeof） 与 #pragma pack(n)中的n的最小值的整数倍。就要在struct的最后添加空字节直到对齐。
AoS or SoA？
- SOA（Structure of arrays）数组的结构与AOS（Array of structures）结构的数组，是面向数据和面向对象设计的区别之一。
- 在需要高频率（如渲染循环中）访问数据的时候，一般情况下SOA的效率高于AOS，因为将需要频繁访问的数据连续存放会大大提高访问速度。虽然AOS的结构可能更适合面向对象设计，但是在高度依赖效率的地方应该使用SOA。
分支预测策略
- why：流水线技术处理分支指令会遇到根据判定条件不同可能产生跳转从而打断流水线指令的处理的问题。分支预测即为解决此问题诞生，预测分支是否会跳转。
- 猜对/猜错
- 静态分支预测：简单：任选一条分支，平均命中率50%；精确：根据原先运行的结果进行统计从而尝试预测分支是否会跳转。
- jxx指令：向上跳/向下跳
内存 缓存
- 都是2的幂次方
- 缓存：内存中的虚映射；缓存读取快；
- 为什么最好填L1/L2缓存的一半：避免数据互相挤兑的问题（内存震荡/摇摆）；
