From scalar execution to multi-core
现在从软件工程师的视角来看待计算机的结构
从一个执行的程序说起: 用 的泰勒级数来求值 标准的 C 代码如下
void sinx(int N, int terms,float* x,float* y)
{
for (int i=0; i<N; i++)
{
float value =x[i];
float numer = x[i] * x[i] * x[i];
int denom = 6 ;
int sign = -1;
for (int j=1; j<= terms; j++)
{
value += sign * numer / denom;
numer *= x[i] * x[i];
denom *= (2*j+2) *(2*j+3);
sign *=-1;
}
y[i] = value;
}
}计算一组数组 x 的 sin 的近似值
对于最简单的 processor , 整个逻辑就是将编程语言编译为机器码, 在 processor 上, 按 clock 计时进行执行
对于 superscalar processor , 硬件能够寻找机器码中能够并行的部分, 将可并行的指令同时在多个 ALU 上处理 在多核处理器时代, 处理器的架构就是这样的
在多核处理器时代, 人们可以用更多的更多的处理器核来进行计算, 但是编译的代码一开始并不支持多核同时计算, 否则只是将同一个代码用两个处理器进行计算, 需要在代码中显式适配多核计算:
typedef struct {
int N;
int terms;
float* x;
float* y;
} my_args;
void my_thread_func(my_args* args)
{
sinx(args->N, args->terms, args->x, args->y);
}
void parallel_sinx(int N, int terms, float* x, float* y)
{
std::thread my_thread;
my_args args;
args.N = N/2;
args.terms = terms;
args.x = x;
args.y = y;
my_thread = std::thread(my_thread_func, &args);
sinx(N - args.N, terms, x + args.N, y + args.N);
my_thread.join();
}这里通过 std::thread() 创建了一个新的线程, 将数组 x 分为两半, 给两组进行计算
上面的并行计算是手动实现的, 高级的编程语言通常也有语法来声明某些计算可以并行, 并让机器自动启动多线程进行并行计算
SIMD and vectorization
这个并行的例子中, 所有并行线程执行的操作是一样的, 区别只是输入数组的值不同, 这给了我们启发: 执行多个相同的操作未必需要多个线程, 实际上只需要同时执行多个算子指令
实现的方式就是给同一个处理器增加一组由同一条指令控制的运算单元 如下图的抽象, 这种处理我们叫做 SIMD (Single instruction, multiple data)
+--------------------------+
| Fetch/Decode |
+--------------------------+
|
v
+--------------------------+
| ALU0 ALU1 ALU2 ALU3 |
| ALU4 ALU5 ALU6 ALU7 |
+--------------------------+
|
v
+--------------------------+
| Execution Context |
| [ctx][ctx][ctx][ctx] ... |
+--------------------------+例如前面计算一组数组的正弦值的操作, 实际上可以直接将多个值一起进行操作, 因为执行的指令是相同的, 我们只需要多个执行操作的单元 这就是向量化 vectorize 的思想
#include <immintrin.h>
void sinx(int N, int terms, float* x, float* y)
{
float three_fact = 6; // 3!
for (int i=0; i<N; i+=8)
{
__m256 origx = _mm256_loadu_ps(&x[i]);
__m256 value = origx;
__m256 numer = _mm256_mul_ps(origx, _mm256_mul_ps(origx, origx));
__m256 denom = _mm256_broadcast_ss(&three_fact);
int sign = -1;
for (int j=1; j<=terms; j++)
{
// value += sign * numer / denom
__m256 tmp = _mm256_div_ps(
_mm256_mul_ps(_mm256_set1_ps(sign), numer),
denom
);
value = _mm256_add_ps(value, tmp);
numer = _mm256_mul_ps(
numer,
_mm256_mul_ps(origx, origx)
);
denom = _mm256_mul_ps(
denom,
_mm256_set1_ps((2*j+2) * (2*j+3))
);
sign *= -1;
}
_mm256_storeu_ps(&y[i], value);
}
}具体代码中, 向量化一起处理了 8 个值, 由于每个值是 32 位数, 所以使用了 256 bit 的 vector registers。这里为了突出向量化, 假设 N 是 8 的倍数；实际代码还需要处理不足 8 个元素的尾部
一般来说, 我们用 forall 来表示下面的循环是独立的, 并且同样的循环可以对大量的数组一起做
这种抽象的好处可以自动告诉编译器下面的操作可以做多核并行和 SIMD 操作
void sinx(int N, int terms, float* x, float* result)
{
// declares that loop iterations are independent
forall (int i from 0 to N)
{
float value = x[i];
float numer = x[i] * x[i] * x[i];
int denom = 6; // 3!
int sign = -1;
for (int j = 1; j <= terms; j++)
{
value += sign * numer / denom;
numer *= x[i] * x[i];
denom *= (2*j + 2) * (2*j + 3);
sign *= -1;
}
result[i] = value;
}
}我们把之前的手写的并行程序都抽象为了前面的一句 forall
Divergent execution and instruction stream coherence
但是对于条件性的执行, SIMD 就可能有问题 当同一条 SIMD 指令控制的不同 lanes 需要走不同分支时, 硬件通常用 mask 暂时关闭不属于当前分支的 lanes, 并依次执行不同的分支路径 在纯 SIMD 的情形, 并不是所有 ALU 都在做有用的工作
多个数据元素执行相同的指令序列, 叫 Instruction stream coherence；缺少这种一致性就是 divergent execution 对于 SIMD , coherence execution 对有效利用处理资源是必要的 但是对于不同核心之间的操作, coherence execution 并不是必要的, 因为不同核心有自己线程上的 fetch/decode 单元
对于 CPU 来说, SIMD 的实现和我们上面讲的一样, CPU 有自己的支持 SIMD 的 ALU 单元 但对于 GPU 来说, 实际上是一种 implicit 的 SIMD:
- 编译器生成一系列标量操作
- 在处理器上会一起运行 N 个程序实例
- 硬件本身会负责自动让多个程序实例在不同数据上, 执行同一条命令, 并由 SIMD ALU 完成
所以对于 GPU 来说, 前面的 divergent execution 是需要注意的, 因为编译器本身不会帮我们避免这个问题
Summary
在并行操作上一共有三种形式
- Superscalar: 在一条指令流中利用 ILP. 并行在同一条指令流中并行执行不同指令 (一般对一个核心来说, 且独立指令一般是由处理器硬件自动发现的)
- SIMD: 由同一条指令控制多个 ALUs (在一个核心内). 对于可并行的数据流是高效的, 由编译器或者硬件完成向量化
- Multi-core: 使用多个处理器核心. 提供线程级并行, 可以在每个核心上执行不同的指令流, 通过软件创建线程来暴露给硬件
Accessing memory
前面提到了, cache 降低了 stall 的长度, 即降低了 memory access latency 使得处理器可以更快获得数据, 但是我们总需要面临不在 cache 中的数据, 不巧地是, 这个数据也并不容易被预测到
隐藏这种等待的一种方式是使用多线程: 在一个线程处于 stalls 时, 切换到另一个线程上 对于一个四线程单核处理器, 我们有如下的时间图
Time ↓
Thread 1 Thread 2 Thread 3 Thread 4
│ │ │ │
[execute] │ │ │
│ │ │ │
STALL │ │ │
│ [execute] │ │
│ │ │ │
Done STALL │ │
│ [execute] │
│ │ │
Done STALL │
│ [execute]
│ │
Done STALL
│
Done一般来说, 单个线程的完成时间可能被延长, 因为线程离开 stall 之后, 其他线程的任务也未必执行完, 但是我们可以接受这点延长, 以换取多线程更大的吞吐量
当然, 这不是一个 free lunch , 因为这些线程都需要消耗处理器的 context 要么每个线程分配更少的 context, 要么使用更少的线程
通过在某个线程 stall 时, 启动别的线程, 我们得以提高核心的利用效率
如何通过硬件来实现多线程: 一种实现就是让核心的 ALU 在不同的时间执行在不同的线程上实现, 这时多线程的好处是 hide 例如 memory access 之类的 high-latency 等待, 而不是降低访问本身的 latency
另外一种方式是 simultaneous multi-threading (SMT): 在每个时钟周期从多个线程中选取指令, 并同时发射到不同的执行单元
Putting it together
我们最后留下一个例子: 来给我们处理器的印象
Core 0
+----------------------------------------------------------+
| L2 Cache |
| L1 Cache |
| Instruction Select |
| | |
| +----------+----------+ |
| | | |
| Fetch / Decode Fetch / Decode ... |
| | | |
| +-----------+---------+ +-----+-------------+ |
| | | | | |
| Scalar ALUs Vector ALUs (8-wide SIMD) |
| | | |
| +-------------------------+ |
| | |
| +-------------------------+ |
| | Execution Context 0 | |
| | Execution Context 1 | |
| +-------------------------+ |
+----------------------------------------------------------+这是一个两种操作的多线程核心 (2线程), 处理器可以执行标量操作以及向量操作
对于现代处理器, 现实应用中会更加复杂, 一个应用必须
- 有足够的并行工作来利用全部可利用的执行单元
- 由同一条 SIMD 指令控制的工作组应尽量保持 coherent control flow；不同核心上的线程不必执行相同的指令流
- 暴露比处理器 ALUs 可承担的更多的并行工作来使用多线程来 hide memory stalls
Summary
需要记住的概念
- Instruction stream
- Multi-core processor
- SIMD execution
- Coherent control flow
- Hardware multi-threading: Interleaved/Simultaneous multi-threading