这一小节没有中文字幕，可以去youtube上看原版视频，开启实时中文字幕功能，youtube视频链接Parallel Computer Architecture and Programming Spring 2018 P2 Lec 2 Modern - YouTube

今天的主题是从硬件角度讨论并行计算,
你会发现硬件设计者在硬件层次结构的多个不同的层次提供了并行计算的潜力，其中一些对程序员不可见，由硬件自己控制。而有一些是需要程序员或者编译器显式生成适当的代码才能利用起来的，因此你必须对硬件有着足够多的理解才能使硬件发挥最大的性能。

我们会介绍4个关键概念，其中两个与并行执行(parallel execution)有关，两个与访问内存的挑战性(challenges of accessing memory)有关。
首先介绍并行执行。

1 parallel execution

1.1 pre multi-core era

在多核时代前，CPU执行技术经过了以下几个阶段的发展(此部分课中没有涉及，但不了解的话在看lecture 2的时候容易迷惑，文字和图都参考自文章什么是Speculative Execution？为什么要有它？ - 知乎)：
386时代：指令是顺序执行的（假设一指令占一个时钟周期）,如下图

image.png

可以看到每个时钟周期只能执行一条指令

在486后，引入了Pipeline(流水线)技术，该技术将指令分为多个阶段，每个时钟周期允许多个指令执行不同的阶段，如下图中将指令的执行分为fetch，decode，execute和write四个阶段。

image.png

此时的指令还是顺序执行(in order execution)的，但图中可以看到有很多wait的阶段，导致这种现象的原因之一是指令间存在数据依赖，例如instr2需要instr1的结果，因此在instr1执行完成前，instr2还是要等待;还有的情况就是代码中有if分支语句，此时也不能提前执行后面的语句。

在奔腾II后，为了缓解该现象，Intel在CPU中引入了乱序执行（out-of-order execution，OOOE）,乱序执行是指指令的执行顺序和指令在内存中的数据不一致，如下图中所示：

image.png

可以看到instr3会在instr2执行之前执行。
但乱序执行还没有解决由于条件分支而等待的问题，这里就引出了分支预测技术和预测执行(speculative execution)技术。
分支预测技术会根据某些信息（如前几次的跳转情况）判断条件分支的跳转情况，然后使用预测执行技术提前执行对应部分的指令。

90年代的奔腾4， 通过超标量实现指令级并行，当时的cpu使用了乱序执行技术。他们在芯片上放大量硬件，并从普通的程序(视频中称为传统程序）中提取各种并行的可能性。如下图的橙红色框中所示，奔腾4有多个指令decoder，可以从指令流中取一堆指令并decode，并将指令映射到一种新的，叫data flow的计算方式，然后CPU会追踪有哪些值生成了，并把这些值填充到即将到来的指令中来解决数据的依赖问题。最后通过许多复杂的硬件和控制将这些指令映射到一堆独立的功能单元上并行执行（这段话看不懂没事，我也没懂，视频中老爷子也只是随口一提，没指望学生能懂 #疑惑）,如橙色框中所示。橙色框中有一个内存接口单元用于存取内存数据，2个整数运算单元，一个浮点数运算单元和一个SIMD（single instruction multi data）单元, SIMD单元可以同时执行多个浮点，整数运算（之后会介绍）。
通过上面的技术，即使一个纯顺序执行的程序，也可以具有一定的并行能力。当然如果你写的代码比较友好或者你的编译器很聪明，CPU也会更容易执行指令级并行。

image.png

上图的黑色框部分是一些控制逻辑，会预测if分支的执行并在预测出错的时候撤销已经执行的，受影响的指令(分支预测技术)，如上方黑色框中的branch target buffer，他保存了控制指令历史的跳转结果信息，并利用该历史信息预测他们将来再次会跳转到哪。下方的黑色框会保存所有通过预测而执行的指令（这些提前执行的指令还不确定是否真的会执行），并在预测成功后把确定执行的指令移除。

然而，前几年的英特尔幽灵漏洞就利用了分支预测技术，原理是分支预测技术在提前执行跳转后的指令时，不会对指令读取的内存的权限进行检查。然后，读取的内存又会在cache中缓存，因此通过判断哪个内存的访问时间快就可以知道之前内存中的数据是多少了，这种方法可以获取任意内存位置上的数据。具体可看本文最后的扩展部分。

需要区分一下流水线和超标量的区别，咋看它们好像都可以在一个时钟周期里运行多条指令，但流水线技术在一个时钟周期内，处于某个阶段的指令只能有一条，因为对应的硬件只有一套。而超标量处理器中，相同功能的硬件有多套，因此一个时钟周期内可运行多个处于同一阶段的指令。

在前多核时代，为了算的更快，使用了许多的晶体管，来增加cache容量、设计更聪明的乱序执行逻辑以及更聪明的分支预测，当然还有更高的时钟频率。然而，就像lecture 1所说，他们不能无限制的通过手段这些增加性能，功耗太大了。

下面介绍多核时代。

1.2 multi-core era

在多核时代，人们的第一个想法是将不断增加的晶体管数量用于在处理器上添加多个核，形成多核处理器，而不是执着于通过加速单一指令流的执行来增加单个核性能（通过乱序技术，以及预测执行（speculative operations）等技术）。

多核的每个核比之前的单核要弱(多个原因，如降低芯片设计复杂程度，减少功耗)，但因为是多个核，协作起来的话计算反而更快。

为什么多核可以降低功耗？这是因为功耗的很大一部分是将信号从一个地方传到另一个地方。在单核情况下，芯片面积大，通信功耗高。在多核情况下，核比较小，传递消耗比较小，这是功耗上的优势。并且，核小的话，信号从一段传递到另一端也更快，这是时间上的优势。

在多核时代，人们的第二个想法是增加多个ALU，这就是产生了SIMD，也就是单指令多数据。SIMD指令会将数据发送到多个ALU，并在多个ALU上同时计算。

如intel发布的avx和avx2指令集(advanced vector extensions，高级向量扩展)，可以同时对256位，即32字节的数据进行操作,如下面代码：

_m256 origx =_mm256_load_ps(&x[i]);//一次从x[i]处读取256位，32字节；ps是pass single，意思是传入的是单精度浮点数float; pd是double
m256 value origx;
m256 numer =_mm256_mul_ps(origx,_mm256_mul_ps(origx,origx));//分别计算8个单精度浮点数的立方
m256 denom =_mm256_broadcast_ss(&three_fact);

生成的汇编如下：

vloadps xmm0, addr[r1] 
vmulps xmm1, xmm0, xmm0 
vmulps xmm1, xmm1, xmm0

具有SIMD指令的CPU核的结构如下图，可以看到有多个ALU。

image.png

有SIMD功能的cpu中有专门的256位寄存器，用于向量指令。也有一些常规指令也会使用该寄存器，但只会使用低位的4或8个字节。
编译器某些特殊情况下也会生成利用AVX的指令，但如果专门为了编译器能够生成这些指令去写相应的代码的话，你需要加许多额外的提示啥的，有点吃力不讨好，还不如自己手动去使用这些指令。

如果遇到if语句，那SIMD是可以同时执行true条件和false条件时的指令，就像它们是顺序代码一样。在条件表达式执行后，通过mask选择最终保留的结果。如下图中，true时会执行黄色指令，fasle会执行蓝色指令，SIMD会将黄色指令和蓝色指令都执行，并且通过一个mask区分哪些指令是true时该执行的，哪些是fasle时该执行的。

image.png

这种同时执行的方法也是gpu的重要方法。

然后课里提到了指令流的一致性执行（instruction stream coherence， coherence execution）和发散执行（divergent execution）。
其中一致性执行有3个特点，分别是：相同的指令序列可以应用到所有元素；一致性执行对于SIMD是重要的；一致性执行对于多核之间的并行执行没啥用，因为每个核可以hold住一个不同类型的指令流。
而发散执行则是指缺乏一致性的指令流。
这是对SIMD的应用场景做了介绍，SIMD在具有一致性的指令流中很有效，而一致性可以理解为多个数据具有相同的处理模式，那么SIMD就可以同时对这些数据进行处理。

现在的CPU上有多种不同的SIMD指令，如128位的SSE，256位的AVX，512位的AVX512.
当发生以下条件时，编译器可以生成SIMD指令：

1. 程序员显式使用了SIMD相关的语句
2. 程序中需要并行的部分使用了并行语言语义（例如forall，这个不是很懂，后面的课中会讲到，到时候回来补 #疑惑）
3. 编译器聪明地分析出了并行性（比较困难）。

这里有个术语为显式SIMD，是指当你不确定编译器是否生成了SIMD代码时，可以查看汇编中有无相关指令，如vstoreps,vmulps等。

与之相对的是隐式SIMD, 如在GPU中，是硬件而不是编译器负责在SIMD ALU上同时执行并行计算。
课中提到了GPU是SPMD（single program multi data),即程序的不同部分可以做不同的事。（这里没完全搞清楚，老爷子没说的很明白。我直接把该页ppt放下面，之后再来瞧瞧 #疑惑）(SPMD在lecture 3中会再次介绍，看本节的时候不理解这个也没影响。)

image.png

1.3 summay

总结一下，在本节parallel execution中，提到了3种现代处理器的并行策略，分别是：

1. 多核：在芯片上放多个核
   1. 提供了线程级的并行
   2. 由软件(程序员)决定何时并行（使用pthreads API）
2. SIMD：在一个核中放多个ALUs，
   1. 高效的数据并行设计
   2. 由编译器显式生成SIMD或者由硬件自动执行
   3. 前提是执行具有一致性（由程序员声明或牛逼的编译器自己发现）
3. 超标量：探索指令级并行(ILP), 来自同一指令流的指令在一个核上并行运行
   1. 由硬件自动挖掘指令并行的可能性（程序员不可见）
   2. 对这个感兴趣可以看课程CMU18447

2 accessing memory

接下来介绍内存访问相关的内容。
虽然CPU的性能提升遇到了瓶颈，但相对于内存存取速度的提升而言，还是进步比较大的。

关于内存存取有两个术语：

1. 内存延迟：指内存系统响应处理器一个内存请求（如load，store）的时间，如100 cycles，100nsec（1nsec=1e-9 sec）
2. 内存带宽：内存系统提供数据给处理器的带宽，如20GB/sec

首先介绍内存延迟

2.1 memory latency

当处理器不能执行下一条指令（因为该指令依赖前面指令的数据并且前面指令没有执行完毕）时，会暂停（stall）。
如下面的汇编：

ld r0 mem[r2]
ld r1 mem[r3]
add r0, r0, r1//依赖前面的指令的结果

而一次内存存取延迟（memory access latency）为100个左右的时钟周期，拖累了CPU的运行速度。

为了减少内存存取的延迟，方法一是在CPU和内存间引入了cache机制以减少延迟(reduce latency)：

image.png

L1 cache的存取延迟为3-4时钟周期，L2为10-12，L3为30-70, 都比内存的存取延迟小很多。

减少内存存取延迟的方法二是预取技术(prefetching)以隐藏延迟(hides latency)。
所有的现代处理器都有将数据预先取到cache的逻辑，他们通过分析程序访问内存的模式来预测哪些数据将会被访问。(看过CSAPP的同学可能对此有印象，在讲到存储器山的时候提到，当存取步长为1时，即使工作集大小超过了L1和L2的大小，读吞吐量也相对保持不变，这是有因为预取技术。具体在CSAPP的p446)
然而，事物都有两面性，当预取技术预测失败时，会降低性能（占用了内存带宽，并可能覆盖了cache中其他有用的数据）

减少内存存取延迟的方法三是多线程以隐藏延迟(文中具体指超线程技术，在后文中也叫硬件多线程)。其中，cache机制是减少延迟的技术，而超线程和预取是隐藏延迟的技术（没有减少延迟）。
超线程技术在一个线程等待内存存取的时候，当前核可以切换到另一个线程继续运行(交错执行线程)。
为了实现这个目的，一个core中必须有多个线程的执行上下文（execution context）：

image.png

上图中的左图只有一套执行上下文（Execution context）(下面的蓝色块)，因此只能保存一个线程的信息。
上图的右图有4套执行上下文，因此可以同时保存4个线程的信息。
一个执行上下文包含了一套寄存器等硬件，因此可以超线程的core中会有多套寄存器。而超线程中ALUs，cache等是多个线程共享的，只是寄存器单独一套。

超线程技术是面向吞吐量的系统，这就意味着它会通过增加单个线程的运行时间来减少整体（多个线程）的运行时间。
例如只有一个线程的运行时间是5s，顺序运行4个线程的时间为20秒。而在超线程时，有4个一起运行的相同线程，每个的运行时间增加到6秒，但4个线程结束时间却变成了15秒，少于20秒。

通过增加单个处理的延迟来增加整体的吞吐量是一个很常用的想法，如网络中的多路复用。
高吞吐量比低延迟更容易实现。
另一种超线程的实现是使用L1 cache作为执行上下文，存储多个线程的状态。
超线程很复杂，具体的要去计算机体系结构课讲。

下图中的cpu有16个core，每个core中有8个ALU，4个执行上下文；因此总共有16个同时运行的指令流（16个core），64个并发的指令流（16个core，每个4个线程），需要512个独立的工作块才能使该CPU饱和（64个线程，每个线程使用全部的8个ALU）。

image.png

总结一下超线程：

1. 优点： 一个core的ALU利用率上升
   1. 隐藏内存延迟
   2. 可以充分填充具有超标量的体系结构中的功能单元（当线程ILP比较少时）
2. 开销：
   1. 要求额外的线程上下文的存储
   2. 增加单个线程的运行时间（不是什么大问题，一般我们关注的是吞吐量）
   3. 这条没懂： Requires additional independent work in a program (more independent work than ALUs!) #疑惑
   4. 严重依赖内存带宽
      1. 更多的线程->更多的工作集->每个线程的cache更少了
      2. 更加频繁地访问内存（线程多了）
         前面说了超线程是一种硬件多线程，而在课件ppt的最后提到硬件多线程分为交叉(interleaved)多线程，同时(simultaneous)多线程，具体可看本博客第3节。

2.2 Bandwidth

下面简单介绍GPU.
GPU是极度面向吞吐量的处理器,NVIDIA GTX 480有16个core，每个core的结构如下：

image.png

每个黄色框是一个SIMD功能单元，
有两组功能单元，每组16个SIMD功能单元。

在每一组功能单元中:

1. 一条指令一次可以操作32个数据（称为“warps”），也就是说该线程发射（issue）了一条32宽的向量指令；
2. 可以交叉执行48个warps，总共48*32=1500个元素
3. 为啥warp是32个数据，而每一组功能单元只有16个SIMD功能单元那？因为ALU的时钟比芯片的其他部分快1倍，每一条指令在16个SIMD ALU上可以运行2个ALU时钟周期，相当于32个SIMD ALU。不过从程序员角度看就是执行了1次32宽度的操作。

GTX480 可以并发处理48 x 32 x 15 = 23000个数据(注意，不是并行)
GTX480 可以并行处理32(ALUs) x 15(cores) =480个数据

下图展示了CPU和GPU的内存层次结构：

image.png

其中CPU cache更大，线程更少，内存存取速度一般（主要靠缓存和预取技术）。
而GPU cache小(给ALU腾空间)，线程多，内存存取速度块（主要依赖于多线程）

理论上，每个时钟周期GTX480可以计算480个数据，每个数据4字节。
假设我们要计算C=AxB，那么有3次内存存取操作，对于GTX 480的1.2GHZ频率来说，每秒需要6.4TB的带宽（480x4x3x1.2G），然而GTX 480的内存带宽只有177GB，3%的效率，但依旧是当时最快cpu的7倍（但该cpu的内存带宽只有25GB/sec，计算效率也只有3%）
因此对于吞吐量系统设计者而言，内存带宽是一个严重的挑战。

不管是CPU还是GPU，内存带宽比计算更加稀缺，因此作为一个程序员你可以采取一些奇妙的技巧来减少内存访问,如：

1. 组织代码使得更少地从内存中获取数据。
   1. 复用该进程之前读取的数据（属于传统的线程内局部性优化。如计算数组累加时，可以使用临时变量）
   2. 在线程间共享数据（线程间合作）
2. 减少请求数据的次数（用计算代替）
   1. 术语:“算术密度”——指令流中算术操作与数据访问操作的比率
   2. 算术密度越高，现代处理器的执行更加高效。

2.3 summary

1. 现代处理器都使用了下面三个思想
   1. 多核
   2. SIMD
   3. 超线程
2. 现在芯片计算能力很强，因此需要并行程序的瓶颈在内存带宽
3. GPU架构使用与cpu相同的吞吐量计算思想:但GPU将这些概念推向了极致

3 Review

老爷子可能知道讲的太多了，还另外搞了一个复习，回顾了一下CPU的发展史。
首先是最简单的单核CPU，超标量单核CPU, 双核CPU:

image.png

不过需要注意超标量的图示。图示中有2个exec分别是exec1和exec2，容易让人认为是核中有2套一模一样的exec 单元，但实际上并不是，具体可以看看本文前面部分的奔腾4的硬件结构。这里的图示只是一种抽象，从程序员的角度看确实是可以理解为有2套一样的exec。

然后是超标量双核，四核，带有SIMD的四核：

image.png

最后是带有超线程、SIMD的四核处理器，以及带有超线程、超标量以及SIMD的四核处理器。

image.png

最后的最后，看一下带有超线程、超标量以及SIMD的四核处理器的简单结构图：

image.png

总结一下本课提出的几种技术：

1. 多核: 通过在CPU上放置多个核来达到多线程并行。
   1. 特征，多个指令流分布在多个核。
2. 超标量: 通过在单个核上放置多个相同类型的硬件来达到指令级并行。
   1. 特点：每个核上一个指令流；在一个核上，每个时钟周期可执行多条指令
3. SIMD：在单个核上放置多个ALUs，可以通过一条指令调用多个ALUs进行并行计算。
   1. 特点：每个核上一个指令流；每个时钟周期执行一条指令；一条指令调用多个ALU；
4. 超线程（硬件多线程）：在单个核上放置多个执行上下文，使得单个核上可以同时存在多个线程。
   1. 同步多线程（Simultaneous multi-threading，SMT）：多个线程是并行的，需要处理器具有超标量结构，可实现在单个core上的多个线程的指令级并行。
      1. 特点：每个核上多个指令流；每个时钟周期可执行多个指令流的指令；
   2. 交叉多线程（Interleaved multi-threading，IMT）：多个线程是并发的，交错执行的，不需要处理器具有超标量结构，
      1. 特点：每个核上多个指令流；每个时钟周期仅执行一个指令流的一条指令；

课程的最后留了一个问题，我也不是很确定答案，大家可以在评论区讨论一下：
你写了一个具有2个线程的程序，它运行在一个带有超线程的（每个核有两个执行上下文）、SIMD的双核处理器上
问题1：谁将你的线程放置到处理器上的？
答：之前写多线程都没关注过哪个线程放到哪个核上，那应该是OS控制的。
问题2：如果你是OS，你现在有4个可用的核，那你将如何分配这两个线程？
答：有两种方案，感觉各有有缺点。
方案一是放在两个不同的核，优点是单个运行时间可能会短，缺点是同一个程序的两个线程应该有很多数据会共用，放到两个核的话，L1和L2就隔离了，cache的miss会变多。
方案二是放在同一个核，因为他是超线程，所以两个线程可以并发执行。优点是L1和L2 可以共用，减少内存延迟，缺点是两个线程的速度可能会变慢。
我也不知道选方案几。。
问题3：如果你的程序有5个线程，该如何分配？
答：还是要确定问题2的答案才行。

4 扩展

4.1 分支预测与幽灵漏洞

前几年的英特尔幽灵漏洞就利用了分支预测技术，原理是，分支预测技术在预测并执行跳转后的指令时，不会对指令读取的内存权限进行检查。然后，读取的内存又会在cache中缓存，因此通过判断哪个内存的访问时间快就可以知道之前内存中的数据是多少了，这种方法可以获取任意内存位置上的数据。
举个例子，现在程序中有个数组a[100]，假设我们想要获取的数据在内存中与数组a的偏移量为2333，则我们在程序中写一条指令if(xxx) int tmp=a[a[2333]];，
假设a[2333]处的权限是我们不可读，那么正常情况下，执行tmp=a[2333]会报错，我们不可能知道其数据。但分支预测的时候，黑客通过精心的构造，可以使得分支预测在预测if的跳转时，认为程序会跳转到该if语句的内部，因此cpu提前执行了tmp=a[a[2333]];,此时不会对是否可读a[2333]的权限进行检查，因此a[a[2333]]被缓存到了cache上。之后，if的条件执行完，CPU发现预测错了，不走if，那么CPU就会撤销已经执行指令，但cache中的数据没被撤销。最后，黑客只需要在主程序内依次遍历a数组的数据，然后发现读取a[30]的时候很快，那他就知道a[2333]的数据是30了。
更加具体的描述可看该链接 15分钟读懂英特尔熔断幽灵漏洞-Emory - 知乎