计算机体系结构——计算机并行性的实现

1 概述

计算机性能指标

处理器性能 = 主频* IPC

处理器时间 = （程序指令数*CPI）/主频

• 性能提升的主要手段

1. 提升工作主频：Khz增长到GHz
   1）生产工艺提升
2. 发掘并行处理能力
   1）指令流/数据流/线程级并行性
   2）软硬件协同

• 循环级并行
  使一个循环中的不同循环体并行执行

提高并行性的技术途径

（1）时间重叠。多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度。

（2）资源重复。通过重复设置资源，尤其是硬件资源，大幅度提高计算机系统的性能。

（3）资源共享。这是一种软件方法，它使多个任务按一定时间顺序轮流使用同一套硬件设备。

计算机不同层次的并行性

从执行程序的角度看，并行性等级从低到高可分为：
（1）指令内部并行：单条指令中各微操作之间的并行。
（2）指令级并行（Instruction Level Parallelism，ILP）：并行执行两条或两条以上的指令。
（3）线程级并行（Thread Level Parallelism，TLP）：并行执行两个或两个以上的线程，通常是以一个进程内派生的多个线程为调度单位。
（4）任务级或过程级并行：并行执行两个或两个以上的过程或任务（程序段），以子程序或进程为调度单元。
（5）作业或程序级并行：并行执行两个或两个以上的作业或程序。

计算机体系结构分类法

冯氏分类法

用系统的最大并行度对计算机进行分类。

Flynn分类

按照指令流和数据流的多倍性进行分类。根据Flynn分类法，可以将计算机中指令和数据的执行可以分成以下的关系：

1. SISD
2. MIMD
3. MISD：没有实现的案例
4. SIMD

现代延伸：

1. SPMD：
2. MPMD

2 指令级并行（ILP）

当指令之间不存在相关时，它们可以在流水线中重叠起来并行执行。这种指令序列中存在的潜在并行性称为指令级并行。

实现指令级的并行必须要有基于硬件前瞻执行的思想。前瞻技术实现的关键是允许指令的乱序执行，但必须循序确认，它不仅能够得到更高的并行性，还能在处理器未判断指令是否可以执行前就提前执行，以克服控制相关。基于硬件的前瞻和动态调度相结合，可以做到同一种体系结构，实现不同机器能够使用相同的编译器。

实现指令级并行的方法如下所述：

2.1 单发射技术

超流水线技术

将流水线进一步细分，增加硬件资源换取处理器性能，流水线级数超过8级即为超流水线处理器

属于时间并行性范畴

2.2 多发射技术

也称多流出技术，即每个周期流出多条指令。增加发射通路，让每级流水线都可以同时处理更多的指令，即降低CPI（每条指令执行的周期数）。

该技术要解决多条指令相关冲突，还要core中的各种资源翻倍，实际效率是要大打折扣的

（1）实现的方法

1. 静态多发射
   在执行前，由编译器复杂封装多条指令并处理冒险
2. 动态多发射
   超标量处理器

图片来源于国防科技大学高级计算机体系结构课程

超长指令字

以一条指令来实现多个操作的并行执行，减少存储器访问，即单指令多操作（多指令）。例如单指令可以包括浮点、整数、load/store等等，为避免数据相关性，该技术对软件编译的要求较高。

基本只有CISC可以实现该并行性，RISC由于指令位数有限，难以实现

超标量处理器

并行执行的流水线条数称为超标量，在每个时钟周期流出的指令条数不固定，依代码的具体情况而定，不过有个上限。设这个上限为n，就称该处理机为n流出。

按序发射=》乱序执行=》按序提交

2.3 指令动态调度技术

指令顺序进入流水栈，根据指令数据相关性、指令写回完成、占用资源情况等要素动态地调度指令流水栈，此时就存在多条指令在队列中等待完成，弹道指令级并行的效果。

即把相关的解决尽量往后拖延，同时前面指令的等待不影响后面指令继续前进。通过指令调度实现的处理器即为乱序处理器。

例如：DIV    $3, $2, $1
           ADD  $5, $4, $3
           SUB  $8, $7, $6
SUB指令的操作数与前面的指令没有关系，可以在前面指令间的相关引起阻塞而空闲的时候“见缝插针”地提前执行。

1. 要完成上述操作，需要对原流水线作一些改动：
   首先，将原译码阶段拆分成“发射”和“读操作数阶段”。发射阶段进行指令译码并检查结构相关，随后在读操作数阶段则一直等待直到操作数可以读取。
   
   处于等待状态的指令将会被存放在保留站中，也称为发射队列，这也是动态调度中的核心部件。保留站的作用是记录下描绘指令间相关关系的信息，控制存放的指令执行时间，同时监测每条指令的执行状态。保留站会在每个时钟周期选择一条没有被阻塞的指令，送往执行逻辑，并退出保留站，该动作称为发射。
   
2. 消除WAR和WAW在动态调度时产生的冲突：
   
   1）记分板办法
   2）Tomasulo算法
3. 精确异常问题
   异常的来源包括：外部事件、指令执行中的错误，数据完整性问题、地址转换异常、系统调用等。精确异常要求处理器处理完异常后，回到产生异常的地方，还能处理正确。
   
   1）在动态调度中，原先指令执行的先后被打乱，当异常来临时，指令该如何先后执行？发生异常后面的指令都不能修改机器状态，万一这些指令越过发生异常的指令提前执行了，该如何避免？
   解决办法是在流水线中添加一个重排序缓冲（ROB），用来维护指令的有序结束，同时在流水线中增加一个“提交”阶段，用来对已经完成的指令做最后处理，更新某些寄存器状态。如上图所示。
   ROB是一个先进先出的有序队列，所有指令在译码后按程序顺序进入队列尾部，所有执行完毕的指令从队列头部按序提交；提交时一旦发现有指令发生异常，则在ROB中将该指令及其后面的指令全部清空，也无法提交，也就不会修改机器状态；发生异常的指令出现在ROB头部时，这条指令前面的指令已经从ROB头部提交并退出了，这些指令对机器状态的修改都生效了；
4. 总结完整的调度流程
   取指：不变
   
   译码：先译码后发射
   正常译码后，把操作队列的指令根据操作类型送至保留站，前提是保留站和ROB都有空，并在ROB中指定一项作为临时保存该指令的结果；发射时读寄存器的值和结果状态域，如果结果状态域指出结果寄存器已被命名到ROB，则读ROB
   
   执行：准备好操作数则执行，否则根据结果ROB号侦听结果并接收结果总线值
   
   写回：把结果送至结果总线，释放保留站；ROB根据结果总线修改相应项
   
   提交：如果队列中第一条指令的结果已经写回且没有发生异常，把该指令的结果从ROB中写回到寄存器或存储器，释放ROB相应项；若队列头的指令发生异常，队列和ROB清空。

记分牌算法

记分牌1964被Cray用于CDC 6600机器。

每条指令均经过记分牌，记分牌记录各指令间数据相关的信息，如果记分牌判断出一条指令不能立即执行，他就检测硬件的变化从而决定何时执行

1）指令乱序执行的前提

1. 充足的资源，无数据相关
2. 记分牌动态解决了RAW相关
3. 指令可以乱序执行

2）实现方案

ID段分为两级

1. 流出：解析指令，检查结构相关
2. 读操作数：直到不存在数据相关时，才读取操作数

如果存在WAR或WAW相关，记分牌暂停这条指令的执行，直到相关消除后才继续执行

执行过程：

当指令满足如下条件时流出，否则将会阻塞在指令队列中：

1. 本指令所需的功能部件有空闲
2. 正在执行指令使用的目的寄存器与本指令的目的寄存器不同（保证WAW相关）

当指令流出进入读操作数阶段，当满足以下两个条件之一读取操作数，否则阻塞在功能部件中，动态解决RAW相关，任何一条指令的源操作数产生之前，这条指令都不能被执行

1. 前面已流出的还在运行的指令不对本指令的源操作数寄存器进行写操作（RAW）
2. 一个正在工作的功能部件已经完成了对这个寄存器的写操作

进入执行阶段：

1. 开始于取到操作数以后
2. 当结果产生后，修改记分牌状态
3. FP流水部件会占用多个周期（一拍出不来结果）

写回阶段：检查WAR相关，出现以下情况时，不允许指令写结果：

1. 前面的某条指令还没有读取操作数
2. 其中某个源操作数寄存器与本指令的目的寄存器相同

Tomasulo算法

 在运算部件的入口设置保留站，当保留站有空时，指令流出。
首先判断操作数是否就绪；如果是，就把操作数读到保留站，否则就把寄存器状态表中的标识送给保留站。并把保留站置为忙，把操作码送保留站，把保留站号r送到与该指令的结果寄存器对应的寄存器状态表项。

1）核心思想

Tomasulo算法思想是只要操作数有效，就将其取到保留站，避免指令流出时才到寄存器中取数据，这就使得即将执行的指令从相应的保留站中取得操作数，而不是从寄存器中。指令的执行结果也是直接送到等待数据的其他保留站中去。因而，对于连续的寄存器写，只有最后一个才真正更新寄存器中的内容。

一条指令流出时，存放操作数的寄存器名被换成为对应于该寄存器保留站的名称（编号）。指令流出逻辑和保留站相结合实现寄存器换名，从而完全消除了数据WAW和WAR的这类名相关。

① 记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减少到最少；
② 通过寄存器换名来消除WAR冲突和WAW冲突。

2）保留站

设置在运算部件的入口，每个保留站中保存一条已经流出并等待到本功能部件执行的指令（相关信息），包括操作码、操作数以及用于检测和解决冲突的信息。

分布式的保留站：
（1）冲突检测和指令执行控制是分布的。每个功能部件的保留站中的信息决定了什么时候指令可以在该功能部件开始执行。
（2）计算结果通过CDB直接从产生它的保留站传送到所有需要它的功能部件，而不用经过寄存器。

3）CDB

公共数据总线。它是一条重要的数据通路，所有功能部件的计算结果都要送到CDB上，由它把这些结果直接送到（播送到）各个需要该结果的地方。

4）ROB

再定序缓冲器。在指令操作完成后到指令被确认的这一时间段内，为指令保存数据。

包含的数据包括：
（1）指令类型：指出该指令是分支指令、store指令或寄存器操作指令。
（2）目标地址：给出指令执行结果应写入的目标寄存器号（如果是load和ALU指令）或存储器单元的地址（如果是store指令）。
（3）数据值字段：用来保存指令前瞻执行的结果，直到指令得到确认。
（4）就绪字段：指出指令是否已经完成执行并且数据已就绪。

• 指令的静态调度

2.4 静态调度技术

依靠编译器对代码进行静态调度，以减少相关和冲突。它不是在程序执行的过程中、而是在编译期间进行代码调度和优化。静态调度通过把相关的指令拉开距离来减少可能产生的停顿。

2.5 分支预测技术

现代处理器普遍采用分支预测机制来解决转移指令引起的控制相关阻塞。

其基本思路是在转移指令的取指或译码阶段预测出转移指令的方向和目标地址，并从该地址继续取指令执行，这样在猜对的情况下无需阻塞流水线
实现分为两步：预测和确认
预测：在取指或译码阶段预测转移指令是否跳转以及转移的目标地址，并根据预测结果进行后续指令的取指
确认：在转移指令执行完成后，比较最终确定的转移条件或转移目标与之前预测的结果是否相同，如果不同则需要取消预测后的指令执行，并从正确的目标重新取指执行。

静态分支预测通过编译技术设置延迟槽、在branch指令后加nop指令，以下着重介绍动态分支预测

动态分支预测

在程序运行时，根据分支指令过去的表现来预测其将来的行为。如果分支行为发生了变化，预测结果也跟着改变。动态分支预测技术的目的有两个：预测分支是否成功和尽快找到分支目标地址（或指令），从而避免因控制相关而造成流水线停顿。

1）分支历史表BHT

记录分支指令最近一次或几次的执行情况（成功或不成功），并据此进行预测。

2）分支目标缓冲器BTB

分支目标缓冲器。用专门的硬件实现的一张表格。表格中的每一项至少有两个字段：① 执行过的成功分支指令的地址；② 预测的分支目标地址。

3）前瞻执行

对分支指令的结果进行猜测，并假设这个猜测总是对的，然后按这个猜测结果继续取、流出和执行后续的指令。只是执行指令的结果不是写回到寄存器或存储器，而是放到一个称为ROB的缓冲器中。等到相应的指令得到“确认”（即确实是应该执行的）后，才将结果写入寄存器或存储器。

2.6 循环展开技术

在开发循环级并行的一种基本技术。它将循环体展开若干次，将循环级并行转化为指令级并行。这个过程既可以通过编译器静态完成，也可以通过硬件动态进行。

2.7 超长指令字技术（VLIW）

VLIW将多个操作包装在一个非常长的指令中，通过多个独立的功能单元并行的执行指令。

缺点：
1）执行代码中不许有足够的操作，增大了代码大小
2）若指令违背填满，没有用到的功能单元造成资源浪费
3）机器的迭代很有可能造成代码的不兼容

3 线程级并行（TLP）

每个线程都有自己的寄存器堆、PC、页表，更关注的是流量

进程：正在运行中的程序

线程：进程运行的实体，一个进程可以分成几个线程。线程是直接对CPU资源进行分配。

例如一个进程需要运行浮点指令和定点数指令，即可以产生两个线程分别由浮点运算部件和定点数运算部件同时执行。

切换时间：

超线程技术（Hyper-Threading）

Intel的线程级并行技术，允许单个处理器采用共享执行资源的方法并行执行两个或多个分离代码流（线程）的技术。即单处理器可以被虚拟化成多个逻辑处理器。

每个被虚拟化的逻辑处理器都要拥有自己的通用处理器、段寄存器、控制寄存器等。

减少CPU的闲置时间，提高系统的资源利用率

多处理机技术

SMT

SMP

参考链接：计算机体系结构——计算机并行性的实现-CSDN博客

4 数据级并行

目前，最多使用的是SIMD和MIMD。SISD是现在传统的单核处理器常用的指令数据执行关系。

单指令多数据流（SIMD）

SIMD使用专用的功能单元进行单指令多数据的计算，常用于科学计算、机器学习、多媒体信号处理等。

SIMD可以将单个指令运用于多个数据的计算，例如将寄存器Source1和Source2中的某段数进行OP，后保存到Destination寄存器中。该过程仅需一条指令就可以完成多组数据的处理。

向量处理器

1）向量处理方式

(1) 水平处理方式：不适合对向量进行流水处理。

(2) 垂直处理方式：适合对向量进行流水处理，向量运算指令的源/目向量都放在存储器内，使得流水线运算部件的输入、输出端直接与存储器相联，构成MM型的运算流水线。

(3) 分组处理方式：适合流水处理。可设长度为n的向量寄存器，使每组向量运算的源/目向量都在向量寄存器中，流水线的运算部件输入、输出端与向量寄存器相联，构成RR型运算流水线。

2）向量链接技术

当两条向量指令出现RAW相关时，若它们不存在功能部件冲突和向量寄存器(源或目的)冲突，就有可能把它们所用的功能部件头尾相接，形成一个链接流水线，进行流水处理。        

3）向量处理机性能的主要参数

1. 向量指令的处理时间。
2. 峰值性能：向量长度为无穷大时，向量处理机的最高性能。
3. 半性能向量长度：向量处理机的性能为其峰值性能一半时所需的向量长度。
4. 向量长度临界值：对同一段程序代码而言，向量方式的处理速度优于标量串行方式处理速度时所需的最小向量长度。