并行复习
并行硬件与并行软件
冯诺依曼瓶颈
cpu去主存储器中去指令的过程比cpu执行指令要慢很多
三方面改进：
缓存
CPU Cache是一组相比于 CPU 主存更能快速访问的内存区域
虚拟内存（了解）
主存中放不下，把不常用的放到虚拟内存中
低层次并行
1）指令级并行
不是多核
让多个处理器或者功能单元 同时执行指令
两种实现方式
流水线
7000ns➡️1006ns
多发射
- 复制功能单元来同时执行程序中的不同指令
- 静态多发射：功能单元在编译时调度
- 动态多发射：功能单元在运行时间调度。 超标量
超标量
必须找出能同时执行的指令
猜测
2）硬件多线程
分为3种
- 细粒度 每条指令完成后都切换
- 粗粒度 只切换那些需要等待较长时间而阻塞的线程
- 同步多线程/超线程 真正意义上的同时 一个核上多个线程
Cache相关概念
局部性原理
程序访问完一个存储区域往往会访问接下来的区域
- 空间的局部性
- 时间的局部性
cache命中
cache缺失
cache的问题
- 写直达：当CPU向Cache中写数据时，高速缓存行会立即写入主存中
- 写回：数据不是立即更新到主存中，而是将发生数据更新的高速缓存行标记为脏。当发生高速缓存行替换时，标记为脏的高速缓存行被写入主存中
Cache一致性
z1的值取决于什么时候更新x
解决
- 监听Cache一致性协议
- 基于目录的Cache一致性协议
并行、多线程相关概念
1.1.3
SIMD MIMD（共享内存、分布式内存、网络连接等）
Flynn‘s分类法
SIMD
数据并行
将数据分配给多个处理器实现并行
相同指令来操作数据子集
缺点
- 所有ALU要么执行相同的指令，要么同时处于空闲状态
- ALU同步操作
- ALU没有指令存储器 一次只能执行一条指令
- SIMD并行在大型数据并行问题上有用，但是处理其他并行问题并不优秀
向量处理器
对数组或者数据向量进行操作
向量寄存器 能够存储多个数组成的向量并操作
向量指令 在向量上操作
向量化和流水化的功能单元 对向量中每个元素做同样的操作
优点
- 速度快 容易使用 向量编译器擅长识别向量化的代码
- 编译器能够提供代码为什么不能向量化的原因
- 内存带宽高 每个加载的数据都会使用
缺点
- 不能处理不规则数据结构和其他的并行结构
- 可扩展性受限 可扩展性：处理更大问题的能力
GPU
使用SIMD并行
并不是纯粹的SIMD系统
MIMD
多指令流多数据流
完全独立的处理单元或者核
每个处理单元或者核都有自己的控制单元和ALU
分为：
1）共享内存系统
内存共享
处理器通过访问共享的内存来隐式通信
一个/多个多核处理器 一块芯片上有多个CPU或者核
分为两类
一致内存访问系统
非一致内存访问系统
2）分布式内存系统
集群
大多数混合系统
互连网络
分为两类
- 共享内存互连网络
- 分布式内存互连网络
共享内存互连网络
1）总线互连
随着连接到总线的设备数量增加，竞争增加，性能会下降
2）交换互连网络
交换器
交叉开关矩阵
分布式内存互连网络
分为两种
- 直接互连
- 间接互连
1）直接互连
每个交换器都与一个处理器-内存对直接相连，交换器之间也互相连接
和总线互连不同：P1，P2，P3可以同时信息交换，因为有交换器控制
2）间接互连（了解）
交换器不一定与处理器直接相连
例子
- 交叉开关矩阵 和共享内存网络中的交叉矩阵不同
- Omega网络
评价网络好坏 （掌握）
等分宽度 针对分布式内存网络 中的 直接互连网络
衡量同时通信的链路数目 连接性
计算方法：计数去除最少的链路数从而将节点分为两份
环 等分宽度=2
二维网格结构 p为处理器数目
带宽：传输数据的速度
等分带宽=带宽✖️等分宽度
如果在环中，链路的带宽是10亿位每秒，等分带 宽就是20亿位每秒
全相连网络
超立方体
递归构造
维度 d。
节点数
$$
p=2^d
$$
等分宽度
$$
p/2
$$
总结
| 结构 | 环 | 二维环面 | 超立方体 | 全相连 | |
|---|---|---|---|---|---|
| 等分宽度 | 2 |  | p/2 |  |
并行程序设计的复杂性
- 足够的并发度
- 并发粒度
- 独立的计算任务的大小
- 局部性
- 临近数据
- 负载均衡
- 处理器任务量相近
- 协调和同步
并行算法设计（竞争条件 数据依赖 同步等概念）
额外开销
- 进程间通信 最大开销
- 进程空闲 负载不均、同步操作、不能并行化的部分
- 额外计算
W8L1里面
看书
或者W4L1乱七八糟
飞书共享空间ppt上没有
原子性:一组操作要么全部执行，要么全不执行。
临界区:一个更新共享资源的代码段，一次只能允许一个线程执行该代码段
竞争条件:多个进程/线程尝试更新同一个共享资源时，结果可能是无法预测的，则存在竞争条件。
数据依赖(data dependence):两个内存操作的序，为了保证结果的正确性，必须保持这个序。
同步(synchronization) :在时间上强制使执各行进程/线程在某一点等待，确保各进程/线程的正常顺 序和对共享可写数据的正确访问。
互斥:任何时刻都只有一个线程在执行
互斥量:互斥锁的简称，用来限制每次只有一个线程能进入临界区。保证了一个线程独享临界区。
障碍:阻碍线程继续执行，在此程序点等待，直到所有参与线程都达到障碍点才能继续执行
并行算法性能分析（加速比 效率 可扩展性 阿姆达尔定律）
串行：时间复杂度
加速比。
谁比谁‼️ 串行比并行
选最优（没有最优的话选择普遍使用的）
例子：n个数相加
串行 O（n）
并行 树形结构 深度为logn 包括加法时间 数据传输时间=启动传输时间+传输过程时间 Tp=O（3logn）
例子
串行起泡排序150s 串行快速排序30s 并行起泡排序40
S=30/40=0.75
p为核数
- 一般S<=p
- S=p 称该并行算法有线性加速比
- S>p 超线性加速比 （了解即可
阿姆达尔定律
可并行化比例有限
只和a和p有关系，和时间没关系
例子
S<10
阿姆达尔定律：通过并行化产生的加速比受限
效率
例子
串行排序算法例子🌟
可扩展性
强可扩展。 问题规模不变。 很难达到
弱可扩展 问题规模增大
SIMD
适合应用的特点
- 连续存储的
- 短数据类型 8、16、32位
- 流式数据处理 时间局部性 数据流重用
选择
应用
SSE AVX CUDA GPU 协处理器Xeon Phi 没有占压倒优势 科学计算
向量长度=寄存器宽度/类型大小
C/C++：内置函数、 intrinsics
SIMD编程的问题（打包解包、对其开销、控制流开销）
打包解包开销
打包 拷贝到连续内存区域
解包 拷贝回内存
对齐开销
未对齐的数据可能产生不正确的结果a
控制流 所有语句必须执行
分支语句
存在控制流问题时，SIMD不是一个好的编程模型
SIMD编程 W6L1
X86 32位
X64 64位
SSE 8个128位的向量寄存器
AVX 16个256位的向量寄存器
MMX 8个64位
支持数据类型 128位=16字节
整数 16字节、8short
| 数据类型 | 名字 | 字节 | 能放几个 |
|---|---|---|---|
| dqword | 16 | 1 | |
| short | 2 | 8 | |
| int | 4 | 4 | |
| long | 8 | 2 | |
| float | 单精度浮点数 | 4 | 4 |
| double | 双精度浮点数 | 8 | 2 |
| char | 2 |
SSE指令
- 数据移动指令 将数据移入/出向量寄存器
- 算术指令 多个数据（2doubles，4floats上的算术指令）
- 逻辑指令 多个数据上的逻辑运算
- 比较指令 多个数据上的比较运算
- 洗牌指令 在SIMD寄存器内移动数据
SSE版本向量乘法
Pthread
并行程序设计的复杂性
Pthread一些基础API
同步相关概念
忙等待 互斥量 信号量 障碍
负载均衡 任务划分
MPI
隔离了独立地址空间
不会有数据竞争 但是可能有通信错误
暴露了执行模型，迫使程序员思考局部性，两点对性能都有好处
代码复杂
无共享变量 通信、同步都需要调用函数完成
提供以下类别的函数
通信
点对点通信 消息从特定的发送进程到特定的接受进程
多处理器参与的组通信
同步
障碍
无锁 没有共享变量需要保护
查询
允许接受的量比指定少，接收到更多数据就是错误
强数据类型传输
消息中的数据用三元组（地址、个数、类型）描述
send receive完成了数据传输 同步
编程模型
混合编程
所有MPI实现均支持MPI_THREAD_SINGLE
绪论
推动并行计算的原因
频率已经不是处理器发展的主角
功耗/散热的限制
性能上升放缓
多核、众核成为之后CPU的发展趋势
超算发展
Top 1 Frontier：性能最强，能效最高
我国Top1：神威·太湖之光 自研的 2016
2020年，Summit，获得戈登贝尔奖的是中美合 作的团队 夺冠，“基于机器学习将分子动力学 计算精度极限推广到1亿个原子”
