第二讲 并行硬件和并行软件
冯诺依曼结构
缺点：cpu和存储器离得太远，取指令时间很长
冯诺依曼模型改进
利用cache
多级缓存
cpu向cache写数据时，cache和主存中的值不一致的问题
- 写直达：当CPU 向Cache写数据时，高速缓存行会立即写入 主存中。
- 写回：Cache中，数据不是立即 更新到主存中，而是将发生数据更新的高速 缓存行标记称脏(dirty)。当发生高速缓存行 替换时，标记为脏的高速缓存行被写入主存 中。
虚拟内存
内存不够用时，再磁盘中开辟一块区域作为虚拟内存
但是常用的指令还是要放到内存中
指令级并行ILP
通过让多个处理器或者功能单元同时执 行指令来提高处理器的性能。
流水线：将功能单元分阶段安排
多发射：让多条指令同时启动
- 静态多发射：功能单元在编译时调度
- 动态多发射：功能单元再运行时间调度
- 支持动态多发射的处理器叫做超标量
- 这两种发射方式都是硬件级别的，不是程序员控制的
超标量
为了能够利用多发射，系统必须找出能够同时执行的指令
在预测技术中，编译器或者处理器对一条指令进行猜测，然后在猜测的基础上执行代码。（可能会猜错
例1
如果*a_p指向的是z，那么这两条指令不能同时执行
例2
z可能为正数也可能为负数
如果系统猜错了，必须返回并重新计算w=y
进程和线程
进程：是运行着的程序的一个实例
多任务操作系统
给人一种单一处理器系统同时运行多个程序的错觉
实际上每个进程轮流运行
执行了一个时间片的时间后，他会等待一段时间直到再次运行
线程
线程包含在进程中
每个线程相互独立
当某个任务阻塞时能执行其他任务
线程间的切换比进程间的切换要快
硬件多线程
硬件多线程为系统提供一种机制，使得当前执行的任务被阻塞时，系统能够继续其他有用的工作
硬件多线程分为一下三种类型：
图示？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
细粒度（程序员不可见
- 处理器在每条指令完成后切换线程，从而跳过被阻塞的线程
- 优点：能够避免因为阻塞而导致机器时间的浪费
- 缺点：执行很长一段指令的线程在执行每条指令的时候都要等待
粗粒度（程序员不可见
- 只切换那些需要等待较长时间才能完成操作而被阻塞的线程
- 优点：不需要线程间的立即切换
- 缺点：处理器还是可能在短阻塞时空闲，线程间的切换会导致延迟
同步多线程（程序员可见，可以通过写程序来控制
- 类似于多核（真正的同时
- 允许多个线程同时使用多个功能单元来利用超标量处理器的性能
- 局限性：一个核上面不会有太多的线程，常见的是2个线程
并行硬件
Flynn’s 分类法
SIMD（单指令多数据流）
概述
通过将数据分配给多个处理器实现并行化
使用相同的指令来操纵数据子集
这种并行称为数据并行
例子
SIMD缺点：
- 所有ALU（算术处理单元）要么执行相同的指令，要么同时处于空闲状态
- ALU没有指令存储器
- 在经典的SIMD系统中，ALU必须同步操作
- SIMD并行性在大型数据并行问题上非常有用，处理其他并行问题时并不优秀
SIMD典型应用
向量处理器
向量处理器是对数组或者数据向量进行操作，而传统的cpu是对单独数据元素或者标量进行操作
原理
向量寄存器
能够存储由多个操作数组成的向量，并且能够同时对其内容进行操作的寄存器
向量化和流水化的功能单元
对向量中每个元素做同样的操作，这些操作需要应用到2个或以上对应元素上
向量指令
在向量上操作而不是在标量上操作
交叉存储器（不太重要
内存系统由多个内存“体”组成，每个内存体能够独立访问
如果向量中各个元素分布在不同的内存体中，那么在装入/存储连续数据时几乎能够无延迟访问
步长式存储器访问和硬件的散射/聚集（不太重要
程序能够访问向量中固定间隔的元素
向量处理器优点（理解即可
速度快
容易使用
向量编译器擅长于识别向量化的代码
编译器也能提供代码为什么不能向量化的原因
帮助程序员重新评估代码
很高的内存带宽
每个加载的数据都会使用
向量处理器缺点
- 不能处理不规则的数据结构和其他并行结构
- 不规则：例如加一个判断语句y>0之类的就不适用
- 他的可扩展性是个限制，可扩展性是指能够处理更大问题的能力
- 想要提高性能就只能增加向量处理器的数量，而不是提高向量处理器的能力
- 不能处理不规则的数据结构和其他并行结构
GPU（图形处理单元）
- GPU使用图形处理流水线将物体表面的内部表示转化成一个像素的数组
- 流水线的许多阶段（通过着色函数实现）是可编程的
- GPU常使用SIMD来优化性能
- 现在所有的GPU都使用SIMD并行
- 尽管GPU不是纯粹的SIMD系统（GUP里有很多很多核
- 1个控制单元对应多个处理单元？？？
MIMD（多指令多数据流）
支持同时多个指令流在多个数据流上操作
通常包括完全独立的处理单元或者核，每个处理单元或者核都有自己的控制单元和ALU
对比SIMD：
SIMD系统那些指令单元必须同步执行相同指令
MIMD分为两大类
共享内存系统
一组自治的处理器通过互联网络与内存系统相互连接
- 意思是这些处理器共享所有内存，每个处理器能够访问每个内存区域
- 处理器通过访问共享的数据结构来隐式的通信
最广泛使用的共享内存系统使用一个或者多个多核处理器
- 在一块芯片上有多个cpu或者核
图示
共享内存系统可以分为两类：
UMA一致内存访问系统
NUMA非一致内存访问系统
这是共享内存系统，而不是分布式内存系统！！
分布式内存系统
- 集群（最广泛使用
- 这些系统中的节点是通过通信网络互相连接的独立计算单元
互联网络
在分布式内存系统和共享内存系统都扮演了一个决定性的角色
分为两类
共享内存互联网络
分布式内存互联网络
=======================草，从这往后好像都没讲草草草草
共享内存互联网络
总线互连
- 需要排队，但成本低
- 随着连接到总线的设备数量的增加，对总线 的使用的竞争会增加，性能会下降。
交换互连网络
灵活但造价高
允许不同设备之间同时进行通信
cache一致性问题
Y1，z1为1号核的私有变量
y0为0号核的私有变量
监听cache一致性协议
- core0更新x时，会在总线上广播更新信息，core1可以监听到（⚠️不是直接传递x的信息，而是广播共享）
基于目录的cache一致性协议
- 使用一个叫做目录的结构，存储每个内存行的状态
- 当一个变量需要更新时，就会查询目录，并将所有包含该变量的高速缓存行设置为非法
分布式内存互联网络
分为两种：直接互连（要求全部掌握）、间接互连
直接互连
每个交换器与一个处理器-内存对直接相连，交换器之间也互相连接
一个环
可以同时进行通信
二维环面网络
可以同时进行信息交换的节点更多
造价更高
间接互连
交换器不一定与处理器直接相连
间接网络中相对简单的例子：
交叉开关矩阵
区分共享互联网络中的交叉开关矩阵
Omega网络
一些定义（直接互连中）
等分宽度（需要会计算
衡量“同时通信的链路数目”或者“连接性”的一个标准
想象并行系统被分成两部分，每部分都 有一半的处理器或者节点。在这两部份 之间能同时发生多少通信呢？
例1：一个环的两种等分
等分宽度求的是最少的情况下的同时通信链路数目
这个环的等分宽度是2而不是4
例2：一个二维环面网格的等分
把红线全部删掉才能把网格结构等分成两份，把两部分完全分开，由图一变成图二，要剪断8根线
总结：
二维环面网格的等分宽度为2*p^(0.5)
p表示处理器的数目
延迟
- 指从发送源开始传送数据到目的地开始接受数据之间的时间
带宽
- 传输数据的速度
- 通常用兆位每秒或者兆字节每秒来表示
等分带宽
- 等分带宽=等分宽度×带宽
- 用来衡量网络的质量
- 不是计算连接两个等分之间的链路数，而是计算链路的带宽
几个直接互连的例子
全相连网络
- 等分宽度太大，造价高，不切实际
超立方体
- 假如维度为d，则有2^d（p=2^d）个节点，等分宽度为p➗2
| 结构 | 图片 | 等分宽度（p为交换器数目） |
|---|---|---|
| 环 |  |
2 |
| 二维环面网状结构 |  |
 |
| 超立方体 |  |
 |
当p>4时，性能：超立方体结构>二维环面网状结构、环
下面这块是从w4l2开始的，中间部分老师跳过了
并行算法分析
基本指标(🌟必考)
串行算法评价：
- 算法时间复杂度表示为输入规模的函数
并行算法评价
除了输入规模之外，还需要考虑处理器的树木、处理器相对运算速度、通信速度
运行时间
加速比：选择串行算法最优的时间和并行算法时间做除法
- 默认串行算法和并行算法所用的处理器相同
加速比
例
初始：每个进程保存一个数，最终由一个进程保存累加和
树形结构：logn个步骤
每个步骤进行一次加法：
和一个机器字的传输
没懂？？？
例。加速比的计算（‼️考试容易考）
p为核数
搜索分解导致超线性的例子
阿姆达尔定律
定义
- 除非一个串行程序的执行几乎全部都并行化，否则不论多少可以利用的核，通过并行化所产生的加速比都会是受限的
例子
理想化：0.9的可完全并行，拥有线性加速比
从公式可以看出来，s和串行程序运行时间是无关的
效率
效率：度量有效计算时间
例1
- n个核对n个数求和
例2
可扩展性
我们希望，保持问题规模不变时，效率不随着线程数的增加而降低，则称程序是可扩展的
- 强扩展的
问题规模增大时，效率不随着线程数的增加而降低，则称程序是可扩展的
- 弱扩展的
例子
例子：快速傅立叶变换
并行程序设计的复杂性
- 足够的并发度
- 并发粒度
- 独立的计算任务的大小
- 局部性
- 对临近数据进行计算
- 尽量减少数据的计算，对离得比较近的数据进行计算
- 负载均衡
- 每个处理器工作量相近
- 协调和同步
并行算法额外开销
- 进程间通信
- 也可能是线程通信
- 最大开销，大部分并行算法都需要
- 进程空闲
- 负载不均，同步操作，不能并行化的部分
- 额外计算
- 最优串行算法难以并行化，将很差的串行算法并行化，并行算法计算量>最优串行算法
- 最优串行算法并行化也会产生额外计算
- 并行快速傅立叶变换
- 旋转因子的重复计算
