首先讨论多处理器的加速比, 现代计算机处理器的架构大多是多个核心, 但为什么需要多个核心, 就是需要讨论的问题
一个直觉上的想法: 多个处理器能够进行加速, 例如, 对于一个给定的计算问题, 我们可以定义多处理器加速比
我们用一个简单的例子来说明这个问题, 对于一个复杂的计算问题,例如把一堆数加起来 让一个学生上来做计算, 需要做一些时间, 接着可以让两个学生上来坐计算, 看起来用的时间减少, 我们可以继续增多计算的学生, 但是会观察到这个计算时间很可能并不会减少了(甚至会增加) 这是因为一个学生算完一部分之后, 需要把结果传递给另一个学生, 这之间也有时间的消耗, 这就是多处理器计算的通信成本 一般地, 在并行任务中, 通信成本有可能也会主导时间消耗
这门课的主题可以归为
设计并写并行程序 经过上面具体的例子之后, 我们来看看并行计算是如何作用在一个具体的任务上的: 一般地为如下过程
- 将任务分解为可以平行处理的部分
- 将分解的任务分配给各个处理器
- 在处理器之间进行通信管理, 以至于其并不限制加速能力
代码就是将上面任务的抽象变为计算机可以运行的程序
并行计算机硬件的配置: 并行计算机是如何工作的 提升效率的机制
和硬件的关系
考虑计算效率
快 != 高效
即使程序在并行计算机上计算得快, 但并不意味着硬件被高效地使用了 需要尽可能利用机器的能力
What is a computer program ?
对处理器而言, 一个计算机程序实际上是一连串处理器执行的指令, 例如对于 C 语言, 通过编译器将其编译为机器码, 从而被计算机执行 而处理器 processor 的作用就是执行指令
一个标准处理器的抽象:
- Fetch/Decode : 用于决定下一个该执行的指令
- ALU (Execution unit) : 执行由指令描述的计算, 从而改变 processor‘s registers 或者计算机 memor 上的值
- Register : 维护程序的状态, 储存变量的值, 作为算子的输入与输出
┌──────────────┐
│ Fetch/Decode │
└──────┬───────┘
│
▼
┌──────────────┐
│ Execution │
│ Unit (ALU) │
└──────┬───────┘
│
▼
┌──────────────────┐
│ Execution Context│
│ │
│ ┌──────┐ ┌──────┐│
│ │ │ │ ││
│ ├──────┤ ├──────┤│
│ ├──────┤ ├──────┤│
│ └──────┘ └──────┘│
└──────────────────┘一个指令的例子: 把两个数加起来 在计算机中, 实际执行的是:
- processor 从内存中获取应该执行的指令: 做一次加法
- 从 register 中获取加法算子的输入值
- 执行加法算子
- 将加法的结果存入 register
对于一个更复杂的计算, 例如计算三个数的平方和
a = x*x + y*y + z*z
我们需要执行以下指令, 完成整个计算
考虑 register R0 = x, R1 = y, R2 = z
mul R0, R0, R0
mul R1, R1, R1
mul R2, R2, R2
add R0, R0, R1
add R3, R0, R2然后将 R3 作为程序的输出值
对于一个 ALU , 我们需要 5 个时间步完成计算, 考虑两个 ALU 我们可以缩短计算时间步
mul R0, R0, R0 | mul R1, R1, R1
mul R2, R2, R2 | add R0, R0, R1
add R3, R0, R2将计算缩短到 3 个时间步, 但是我们能不能做的更快? 引入 3 个 ALU ? 事实上, 我们发现 3 个 ALU 并不能做得更好, 仍然是 3 个时间步 这不是 ALU 的数量决定的, 这实际上来自于程序的 Instruction level parallelism (ILP)
因为总有一些操作需要等待前面的操作完成才能开始执行, 那这两个操作就是不可并行的, 上面的程序的 ILP 层级如下
ILP=3 x·x y·y z·z
│ │ │
× × ×
└────┬───┘ │
ILP=1 + │
└──────┬─────┘
ILP=1 +
│
a可以看到, 这个程序的数据流本身就制约了并行计算的层级
我们上面的计算例子实际上给出了一种并行计算方式 superscalar execution
Superscalar execution: processor automatically finds independent instructions in an instruction sequence and executes them in parallel on multiple execution units
processor 自动寻找指令串中可以并行的指令, 并分配给多个 ALU 并行计算, 一般来说 superscalar processor 的抽象如下
Out-of-order control
────────────────────
│ │
┌───▼───┐ ┌───▼───┐
│ F/D 1 │ │ F/D 2 │
└───┬───┘ └───┬───┘
┌───▼───┐ ┌───▼───┐
│Exec 1 │ │Exec 2 │
└───┬───┘ └───┬───┘
└──────┬───────┘
┌─────▼─────┐
│ Execution │
│ Context │
└───────────┘一般来说, 大部分程序的 ILP 增长并没有 ALU 数量增加的快, 所以单纯增加 ALU 带来的加速的边际收益极小
同样由于处理器功率, processor clock rate 等条件限制, 单纯力大砖飞并没有带来显著的边际收益
既然计算带来的收益已经很小了, 这意味着
Achieving efficient processing almost always comes down to accessing data efficiently
What is memory?
一个程序的 memory 实际上是 一个地址空间 一个 momery 的抽象即为 储存了地址 address 和对应值 value 的列表
Addr Value Addr Value
0x0 16 0x8 32
0x1 255 0x9 48
0x2 14 0xA 255
0x3 0 0xB 255
0x4 0 0xC 255
0x5 0 0xD 0
0x6 6 0xE 0
0x7 0 0xF 0
0x10 128
⋮ ⋮
0x1F 0每行的含义是: 一个 byte 储存在地址 0x8 , 它的值为 32
而 load 实际上就是指令, 让 processor 从内存中获得信息
对于 register R0 : 96 R2: 0x1
ld R0 <- mem[R2]
含义即为: 将内存中地址处于 R2 的值加载进 R0
事实上, 从内存中获取数据是很慢的, 称从 memory 中获取数据并提供给 processor 花费的时间为 latency 例如: 100 clock cycle ~ 100 nsec , 但 latency ~ 2 sec
Stalls : 当一个 processor “stalls” 的时候, 即由于接下来的指令需要之前的指令执行完才能执行, 所以不能执行下一个指令
从内存中获取数据是 stalls 的主要原因, 例如
ld r0 mem[r2]
ld r1 mem[r3]
add r0, r0, r1在获取到 r0 和 r1 之前, 指令 add 不能被执行
一般来说 Memory access times ~ 100’s of cycles
对于这种情形, 优化方法即为让 processor 更快地获取数据, 这就是缓存 caches 的来源
可以在 processor 中加入一个容量较小的存储内存的单元, 称为 cache, 对于频繁访问到的数据, 可以先存储到 cache 中, 缩短访问数据的时间
一般地, 为了高效储存数据, cache 中的数据单元称为 cache line , 实际上就是将内存一段连续的地址的区域分块映射, 等效增大容量
cache 的运作是这样的 当一个指令执行时, 对于需要获取的数据, 先从 cache 中请求, 如果没有, 即第一次访问到, 即称为 cold miss , 然后再从 memory 中将数据加载进 cache (实际上是加载所在块的 cache line) , 当 cache line 的容量到达 cache 上限时, 就更新最久没有访问到的 cache line, 这称为 capacity miss (这是因为 cache 的容量引起的, 和 cache 机制无关)
对于现代 processor 架构, 通常会设置好几个 cache , 例如 L1 caches, L2 caches , L3 caches 按照访问的时间和距离来区分
┌──────────── CPU ────────────┐
│ Core L1 Cache L2 Cache │
└─────────────────────────────┘
↕
┌──────────┐
│ L3 Cache │
└──────────┘
↕
┌──────────┐
│ DRAM │
└──────────┘并且注意: 数据的移动会消耗大量的能量
Summary
- 单指令流性能增长已经显著放缓，继续加速需要并行或专用硬件。
- 更多执行单元不等于更快，实际加速受到指令依赖和可用并行度限制。
- 高效计算很大程度上依赖数据局部性，并应减少高延迟、高能耗的数据移动。
- 编写正确且高效的并行程序并不容易。