一、基础知识

基本概念

计算机是由硬件、软件和固件（固化的微程序） 组成的复杂系统，按语言划分为多级层次结构

计算机系统层次结构

每一层以一种语言为特征

• 各机器级的实现主要靠翻译或解释或两者结合进行
  • 翻译：把高一级机器上的程序转换为低一级机器上等效的程序，并在低一级机器上运行实现程序的功能。故速度快, 占用存储空间大（L4级以上）。
  • 解释：把高一级机器上程序的每一条语句，转换为低一级机器上的一段等效程序并执行。执行后再去高一级机器取下一条语句解释、 执行， 直到解释执行完整个程序 。故速度慢, 占用的存储空间小（L3级以下）。
• 高级语言以低级语言为基础，由低级语言支撑。
  • 低级语言指令功能较简单，但速度快，高级语言指令功能较强，执行速度慢。高级语言通过低级语言实现。

计算机系统结构定义

计算机系统结构是传统机器语言程序员所看到的计算机的属性， 即概念性结构和功能特性（1964 年 Amdahl）

透明性：在计算机技术中，一种本来存在的事物或属性，但从某种角度看又好像不存在或看不到， 称为透明性。

概念性结构：计算机系统中主要部件及逻辑连接结构：CPU ／存储系统 ／ I/O子系统 ／ 互连系统

概念性结构主要由硬件或固件完成， 物理上具备这些结构， 才能提供（传统机器级上）可操作的指令系统

主要功能及属性：

1. 数据表示（硬件直接识别和处理的数据类型）；
2. 寻址规则（最小寻址单元、寻址方式及表示）；
3. 寄存器定义（各种寄存器的定义、数据及使用方式）；
4. 指令集（指令类型和格式、指令间的排序和控制机构）
5. 中断系统（中断类型、中断响应硬件的功能等）；
6. 机器工作状态的定义和切换；
7. 存储体系（主存容量、程序员可用的最大存储容量等）；
8. 信息保护（信息保护方式、硬件对信息保护的支持）；
9. I/O 结构（I/O 连接方式、处理机、存储器与 I/O 设备间数据传送方式 和格式等）

上述属性、功能由硬件或固件完成，了解它们后才能编出在传统机器级上正确运行的程序

计算机系统结构的实质：确定计算机系统中软硬件的界面，界面之上是软件实现的功能，界面之下是硬件和固件实现的功能。

计算机组成和实现

计算机组成

• 计算机系统结构的逻辑实现
• 包含物理机器级中的数据流和控制流的组成以及逻辑设计等。
• 着眼于：物理机器级内各事件的排序方式与控制方式、各部件的功能以及各部件之间的联系
• 具有相同系统结构的计算机可以采用不同的计算机组成

计算机实现

• 计算机组成的物理实现
• 包括处理机、主存等部件的物理结构，器件的集成度和速度，模块、插件、底板的划分与连接，信号传输，电源、冷却及整机装配技术等。
• 着眼于：器件技术（起主导作用）、微组装技术。
• 同一计算机组成又可以采用多种不同的计算机实现

计算机体系结构、组织、实现的区别举例

计算机系统结构的分类

• 按性能与价格综合指标，分为巨型、大型、中型、小型、微型、单片机等。该标准是随时间变化的。
• 按用途，分为科学计算、事务处理、实时控制、家用计算机等。
• 按处理机个数，分为单处理机，多处理机。
• 按体系结构，可分为标量处理机，超标量处理机，超流水处理机，向量处理机，阵列处理机，大规模并行处理机，机群等。

另外， 从体系结构并行性角度，有以下三种常用的分类方法

Flynn分类法

4类计算机的基本结构

Handler分类法

举例

冯氏分类法

平均并行度

与最大并行度密切相关的一个指标。取决于系统的运用程度，与应用程序有关。

假设每个时钟周期内能同时处理的二进制位数为 P_i，则 T 个时钟周期内的平均并行度：

设计

设计的定量原理

大概率事件优先原理

优先加速使用频率高的部件。对大概率事件，赋予优先处理权和资源使用权

加快处理频繁出现的事件可获得明显的系统性能。该原理是最重要和最广泛采用的计算机设计准则。

程序的局部性原理

程序的局部性原理：程序执行时所访问的存储器地址不是随机分布的，而是相对簇聚。分为时间局部性和空间局部性：

• 时间局部性：程序很可能即将用到目前正使用的信息。
• 空间局部性：程序将用到的信息很可能与正在使用的信息在空间上相邻或临近。

利用程序局部性原理，可以根据程序最近的访问情况来比较准确地预测将要访问的指令和数据。

Amdahl定律

加快某部件执行速度所获得的系统性能（加速比），与该部件在系统中总执行时间的比例有关。

系统加速比

定义如下：

系统性能加速比与该部件在系统中的总执行时间有关。

当系统中的某个部分进行改进后， 所获得的**系统加速比S_n**为（改进前与改进后总执行时间之比）:

举例

举例

CPU性能公式

• 执行一个程序所需的 CPU 时间：CPU_时间 = 执行程序所需的时钟周期数 × 时钟周期时间

  其中：执行程序所需的时钟周期数 = IC × CPI

  IC：执行程序的指令条数

• CPI 是指令的平均时钟周期数（Cycles Per Instruction）

  CPI = 执行程序所需的时钟周期数／ IC

  CPU时间可写成

  CPU_时间 = IC × CPI × t = IC × CPI / f

  f = 1/ t 系统时钟频率 f (MHz)

CPU的性能取决于三个参数：

举例

设计的主要任务

主要包括：指令系统、数据表示、功能的组织、逻辑设计及其物理实现等。

设计一个计算机系统大致要考虑以下 3 个方面：

1. 确定计算机系统的功能、价格和性能的要求

2. 软硬件功能合理分配

   软件和硬件在实现功能上是等价的。

   • 软件实现优点：设计容易、修改简单，硬件成本低。但是实现功能的速度较慢。
   • 硬件实现优点：速度快、性能高，但修改困难，灵活性差。根据经常性事件为重点的原则，在软硬件之间进行折中和取舍。

3. 设计生命周期长的系统结构

   • 考虑计算机应用和计算机技术的发展趋势。
   • 一定前瞻性的系统结构，具有较长的生命周期。

提高并行性的技术途径

• 时间重叠：让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转或速度。
• 资源重复：通过重复设置硬件资源，提高系统的性能。
• 资源共享：多个任务按一定时间顺序轮流使用同一套硬件设备。

性能评测

执行时间与速度性能

执行时间

执行单个程序的时间

假设两台计算机 X 和 Y， X 的执行时间比 Y 的执行时间少。则称 X 的性能（或速度）比 Y 快。 执行时间有多种定义：

• CPU 时间： CPU 执行给定的程序所花费的时间。
• 用户 CPU 时间： 用户程序所耗费的 CPU 时间。
• 系统 CPU 时间： 程序运行期间操作系统耗费的 CPU 时间。

通常，CPU时间指用户CPU时间。即

T_CPU = N_C × t = CPI × I_N × t = (CPI × I_N) / f 或

N_C：程序的 CPU 时钟周期数

I_N（I_C）：程序的指令条数

CPI：指令的平均时钟周期数

速度性能

速度与执行时间通常成反比。即有

• CPI （执行程序所需的时钟周期数／ IC）

• 每秒（百万条）指令数 MIPS（million instructions per second）

MIPS = I_N / (T_E×1000000) = I_N / (I_N × CPI × t × 1000000) = f / (CPI × 1000000）

I_N：程序的指令总数；T_E：执行程序的时间；t：时钟周期；f：频率；CPI：程序中指令的平均时钟周期数。

MIPS 定义的不足：

1. 依赖指令系统。
2. 同一台机器， MIPS 依程序不同而变化。
3. 适于评估标量计算机。

• 每秒（百万次）浮点运算 MFLOPS

由下式定义：

MFLOPS= I_FN / (T_E × 1000000)

I_FN：程序中的浮点运算次数；T_E：执行程序的时间。

• MFLOPS的特点
  1. MFLOPS 基于操作而非指令的，用来比较不同机器。
  2. 衡量机器浮点操作性能， 非整体性能，如编译程序。

例子

性能比较

平均执行时间

各测试程序执行时间的算术平均值

其中，T_i：第i个测试程序的执行时间；n：测试程序组中程序的个数

• 机器执行所有测试程序的总时间：B 机最快
  • B 机执行程序 1 和程序 2 的速度是 A 机的 50.05 倍
  • C 机执行程序 1 和程序 2 的速度是 A 机的 25.025 倍
  • B 机执行程序 1 和程序 2 的速度是 C 机的 2 倍

加权执行时间

各测试程序执行时间的加权平均值

其中，W_i：第 i 个测试程序在测试程序组中所占的比重

T_i：该程序的执行时间

调和平均值法（性能是速度 R）

如果性能是速度 R_i（如 MFLOPS）代替时间 T_i ，则用调和平均值法

加权调和平均值公式：

注意：速度不可简单相加
通常 Ri = 1 / T_i ，R_i 为负荷中执行第 i 个程序的速度。T_i为第 i 个程序的执行时间。

几何平均值法（性能是速度 R）

R_i 表示（由 n 个程序组成的工作负荷中）执行第 i 个程序的速度，R_i = 1 / T_i，∏ 表示连乘符号。

加权几何平均值公式如下：

G_m 表示法的特性：G_m(x_i) / G_m(y_i) = G_m(x_i / y_i)

几何平均值的比与比的几何平均值相等

以任意一台机器性为参考标准，可获得一个一致的相对比值。

按H_m比较

二、流水线技术

流水线技术是体系结构研究的主要内容之一，是实现系统结构平衡和提高系统性能的一种有效技术。

基本概念

流水线技术主要思想是把一个复杂任务分解为若干个子任务。每个子任务由专门功能部件完成，并使多个子任务并行执行。

流水线中每个子过程及其功能部件，称为一个流水（阶）段，各流水段可并行完成不同的子过程（子任务）。流水线的段数称为流水线深（长）度。

流水线技术基础

流水线技术核心：部件功能专用化

1. 一件工作按功能分割为若干相互联系的部分
2. 每一部分指定给专门部件（ 段）完成；即专门部件完成同一类工作
3. 各部件（段）执行过程进行时间重叠（ 各流水段时间尽可能相等）
4. 所有部件依次序分工完成一件工作

实例

流水线的表示

连接图

• 流水线各段依次相连
• 每个流水段完成一条指令的同一部分
• 从流水线左端进入，向右经流水线， 从另一端流出
• 不同阶段并行完成流水线中不同指令的不同部分

时空图

• 从时间和空间两个方面描述流水线工作过程
• 横坐标代表时间， 纵坐标代表流水线各段（空间）

上图是典型四段流水线的时空图

流水线通过时间和排空时间：

通过时间：第一个任务从进入流水线到流出结果所需的时间，又称装入时间。

排空时间：最后一个任务从进入流水线到流出结果所需的时间

注意在装入时间和排空时间，流水线不满载。

技术特点

• 一个处理过程分解为若干个子过程（段），每个子过程由一个专门的功能部件实现。
• 各流水段时间尽可能相等，否则引起流水线堵塞、断流。时间最长的段为流水线瓶颈。
• 每段流水线后面有一个缓冲寄存器，称为流水寄存器。在相邻两段间传送数据，有缓冲、隔离、同步作用

• 在通过时间和排空时间， 流水线不满载。
• 流水线性能与流水线输入端输入速度有关。只有输入端不断且快速地提供任务，才能充分发挥流水线的效率

分类

单功能与多功能

按流水线所完成的功能分类

• 单功能流水线： 只能完成一种固定功能的流水线。
• 多功能流水线： 流水线的各段可以进行不同的连接，以实现不同的功能

例如：多功能加、乘流水线

静态与动态

是对多功能流水线作进一步分类

• 静态流水线：在同一时间内，多功能流水线中的各段只能按同一种功能的连接方式工作。
• 动态流水线：在同一时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。

线性与非线性

按照流水线中是否有反馈回路来进行分类

• 线性流水线：流水线的各段串行连接，没有反馈回路。数据通过流水线中的各段时，每一个段最多只流过一次。
• 非线性流水线：流水线中除有串行连接外，还有反馈回路。

线性流水线举例：

非线性流水线举例：

顺序与乱序

根据任务流入和流出的顺序是否相同来分类

• 顺序流水线： 流水线输出端任务流出的顺序与输入端任务流入的顺序完全相同。每一个任务在流水线的各段中顺序流动。
• 乱序流水线： 流水线输出端任务流出的顺序与输入端任务流入的顺序可以不同。允许后进入流水线的任务先完成（从输出端流出）。也称无序流水线、错序流水线、异步流水线。

性能指标

流水线性能指标主要有吞吐率、 加速比和效率。流水线设计中，流水线最佳段数也是一个重要指标。

吞吐率

单位时间内流水线所完成的任务数量或输出结果的数量

n：任务数

T_k：处理完成 n 个任务所用的时间

各段时间均相等的流水线

对于各段时间均相等的流水线，时空图如下：

理想情况下，一条 k 段线性流水线完成 n 个连续任务的总时间为

T_k = k Δt + (n - 1) Δt = (k + n - 1) Δt

实际吞吐率：

最大吞吐率：

最大吞吐率与实际吞吐率的关系：

• 实际吞吐率总小于最大吞吐率。
• 吞吐率与流水线的段数 k 及输入流水线中的任务数 n 有关。
• 当 n>>k 时，TP ≈ TP_max

各段执行时间不相等的流水线

第二段 S₂ 执行时间是其他各段执行时间的 3 倍。 流水段 S₂ 一直忙碌，成为整个流水线的瓶颈

完成 n 个连续任务的总时间为：

实际吞吐率为：

分母中第一项是流水线完成第 1 个任务所用时间， 第二项是完成其余 n - 1 个任务所用时间。

解决流水线瓶颈

方法一：重复设置瓶颈段

让多个瓶颈流水段并行工作

方法二：瓶颈段再细分

细分为多个子流水段——超流水线

加速比

加速比：完成同样一批任务，不使用流水线所用的时间 T_s 与使用流水线所用的时间 T_k 之比。

T_s：不用流水线所用的时间（顺序执行）
T_k：使用 K 段流水线后所用的时间

流水线各段时间相等：（都是 Δt）

• 一条 k 段流水线完成 n 个连续任务的时间：T_k = (k + n - 1) Δt
• 顺序执行 n 个任务所需要的时间：T_s = n * kΔt

实际加速比为：

n = ∞ 时，最大加速比为：

即流水线段数

流水线各段执行时间不等时，实际加速比为：

效率

流水线效率：流水线中的设备实际使用时间与整个运行时间的比值，又称流水线设备利用率。

各段时间相等，各段的效率 e_i 相同：

整条流水线的效率为：

流水线有通过时间和排空时间，故连续完成 n 个任务的时间内，各段并不是满负荷地工作，效率总小于 1

当 n>>k 时，E ≈ 1

据时空图，流水线效率是完成任务占用的时空区有效面积与完成任务所用的时空区总面积之比。

时空区总面积：总时间与 k 个流水段所围成的矩形

若流水线各段执行时间相等， 且输入的 n 个任务是连续的，则 k 段流水线的效率为

当 n>>k 时，流水线的效率接近最大值 1

流水线效率与吞吐率关系为：

流水线效率与加速比关系为：

例子

性能分析举例

流水线设计中的若干问题

• 瓶颈问题
  • 设计流水线时，尽可能使各段时间相等。
  • 理想情况是各段时间均是一个时钟周期。
  • 时钟周期不能太小：保证一个周期完成 应作的工作。
  • 流水线各段不均时，时钟周期取决于瓶颈段的时间。
• 流水线的额外开销
  • 流水寄存器延迟：流水寄存器需要建立时间和传输延迟。
  • 时钟偏移开销：时钟到达各流水寄存器的最大差值时间，称为时钟偏移开销。
  • 增加流水线段数可提高流水线的性能,但会增加流水线的额外开销。
• 冲突问题：流水线的相关与冲突
  • 流水线设计中要解决的重要问题之一

流水线的相关与冲突

一条经典的5段RISC流水线

经典5段流水线执行可分为取指令（IF）、指令译码（ ID）、执行（EX）等 5 个周期

从第三个周期开始， 不同类指令在各周期含义不同

• 取指令（IF）：从存储器中取出指令放入指令寄存器。 PC 值加 4（每条指令占 4 个字节），顺序指向下一条指令。
• 指令译码 / 读寄存器（ID）：指令译码、分析。译码并访问通用寄存器，读出存放在寄存器中的操作数。
• 执行 / 有效地址计算（EX）：
  • ALU 指令（寄存器－寄存器）：执行运算
  • load 和 store 指令： 计算并形成访存有效地址
  • 分支指令：计算并形成转移目标地址（不确定是否转移）
• 存储器访问／分支完成（MEM）：存储器访问或分支完成
  • store 指令：把指定的数据写入存储器单元
  • load 指令：从存储器中读出相应的数据
  • 分支指令：若分支成功，把转移目标地址送入 PC
  • ALU 类指令在此周期为空操作
• 写回（WB）：把结果数据写入通用寄存器组。
  • ALU 运算指令：结果数据来自 ALU
  • load 指令：结果数据来自存储器
  • 分支指令（或 store 指令）：空操作

分支和 ALU、store 指令需 4 个周期；load 指令需 5 个周期。

注意易发生的冲突：

• 存储器冲突：访存指令在 ME 段访问主存，其它指令 IF 段访问主存
• 寄存器冲突：ID 段读寄存器，ALU 指令在 WB 段写寄存器。避免同时读写同一寄存器。

5段流水线方案实现

• 每个周期为一个流水段， 各段之间加上流水寄存器
• 保证同一周期，同一个功能段不做两件不同工作。如：不能要求 ALU 同时做有效地址计算和算术运算。
• 避免IF段取指与MEM段访存（读/写数据） 发生冲突。
• 采用分离的指令存储器和数据存储器，或指令 Cache 和数据 Cache。又称哈佛结构。
• 如何避免ID段和WB段都访问同一寄存器时产生冲突？
  • WB 段写操作安排在时钟周期的前半拍；
  • ID 段读操作在后半拍完成。

流水线的另一类时空图

相关与流水线冲突

相关是指两条指令之间存在依赖关系。 如果两条指令相关， 有可能引起流水线停顿。

3 种相关类型：

• 数据相关（真数据相关）
• 名相关
• 控制相关

在非流水线中指令顺序执行，不存在相关问题。

数据相关

流水线中多条指令并行执行时，指令读／写操作数顺序可能改变，称为数据相关。如以下两指令：

ADD R1, R2, R3; (R2) ＋ (R3) → R1
SUB R4, R1, R5; (R1) － (R5) → R4

指令在流水线中执行中，改变了指令读／写操作数顺序

后一条指令在时钟 3 读， 前一条指令在时钟 5 完成写

数据相关定义

两条指令 i（前）和 j（后），下述条件之一成立，则称指令 j 与指令 i 数据相关

• 指令 j 使用（读）指令 i 产生（写 ）的结果（后一条指令直接读前一条指令的写结果）
• 指令 j 与指令 k 数据相关，而指令 k 又与指令 i 数据相关（后一条指令间接读前一条指令的写结果）

• 数据流动经过寄存器时，相关的检测比较直观和容易。
• 数据流动经过存储器时，检测比较复杂（ 地址形式多样）
• 数据相关有传递性，对性能有一定负面影响。

例子

名相关

名：指令所访问的寄存器或存储器单元的名称。

如果两条指令使用相同的名， 但它们之间并没有数据流动，则称这两条指令存在名相关

仍假设指令 i（在前）和 j（在后），则存在两种名相关：

• 反相关：如果指令 i 读的寄存器名＝ 指令 j 写的寄存器名
• 输出相关：如果指令 i 写的寄存器名＝ 指令 j 写的寄存器名

名相关的两条指令之间并没有真正意义上的数据传送。

如果一条指令中的名改变了，不影响另外一条指令的执行。

名相关可以通过寄存器换名来消除。

消除名相关

寄存器换名（重命名）：

• 通过改变指令中操作数的寄存器名消除名相关。
• 可用编译器静态实现，也可用硬件动态完成

控制相关

• 分支指令引起的相关。包括（无）条件转移、中断等，又称全局相关。控制相关能改变程序方向，造成流水线断流。
• 为保证程序正确，必须严格按控制相关确定的顺序执行。

典型的程序结构时 “if - then” 结构，如下：

if p1 {
    S1;
}
S;

p1, S1 控制相关（S1 不能移到 if 语句之前）

p1, S 无（控制）相关（可以把 S 移到 if 语句之前）

控制相关特点

• 与分支指令控制相关的指令不能移到分支之前。否则就不受分支控制。
• 如果一条指令与某分支指令不存在控制相关，就不能把该指令移到该分支之后。否则就受该分支控制了。
• 分支指令通常在流水线末端时转移条件才建立，对流水线性能影响大

流水线遇到分支指令时，有两种结果：

1. 发生转移：将程序计数器 PC 内容改成转移目标地址；
2. 不发生转移：PC 指向下一条指令地址。

条件分支（转移）指令：流水线末端时转移条件才建立，流水线性能下降较大。

从相关角度看，条件转移指令或中断指令与后续指令存在着一种控制上的全局相关。

流水线冲突

因流水线中指令相关性存在，导致指令流中下一条指令不能在指定的时钟周期执行，称为流水线冲突。

流水线冲突有 3 种类型：

• 结构冲突：硬件资源不满足指令重叠执行的要求。
• 数据冲突：指令在流水线中重叠执行时， 需要用到前面指令的执行结果而发生的冲突。
• 控制冲突：分支指令和其它会改变 PC 值的指令所引起的冲突。

流水线冲突的影响：

• 导致错误的执行结果。
• 导致流水线停顿，降低流水线性能。
• 约定：当一条指令被暂停时，在该指令之后流出的所有指令都要被暂停，而之前流出的指令仍继续进行

结构冲突

如果指令组合因资源因素而不能正常执行流水，称该处理机有结构冲突

常见的结构冲突原因有：

1. 功能部件不是完全流水：必要时对功能部件进行流水
2. 资源份数不够：必要时可重复设置资源

举例：访存冲突

有些流水线处理机只有一个存储器，将数据和指令放在一起，访存指令会导致访存冲突

解决方法一：插入暂停周期

由引入“流水线气泡”的时空图表示或引入暂停后的时空图表示

数据冲突

当相关的指令靠太近时，它们在流水线中的重叠执行或者重新排序会改变指令读 / 写操作数的顺序，使之不同于它们串行执行时的顺序，则发生数据冲突。

虚线：数据冲突

实线：正常执行（不冲突）

类型

假设两条指令 i 和 j，i 在 j 之前，数据冲突分为 3 种类型。

• 写（后）读冲突（WR，RAW） ：指令 i 先写就不冲突。

  若 j 先去读，j 读出的内容是错误的。对应（真）数据相关，是最常见的一种数据冲突。

• 写（后）写冲突（WAW）：i 先写就不冲突。

  j 先写， i 后写的结果是错误的。

  该冲突对应于输出相关，通常发生在下述情形：

  • 流水线中不只一个段可以进行写操作；
  • 指令被重新排序了。

  前面 5 段流水线一般不发生写后写冲突（在 WB 段写寄存器）

• 读（后）写冲突（RW，WAR）：i 先读就不冲突。

  （i 读之前）j 先写。i 读出的内容是错误的。

  由反相关引起。 前面 5 段流水线一般不发生, WAR 冲突仅发生在这样的情况下：

  • 有些指令的写结果操作提前了
  • 有些指令的读操作滞后了
  • 指令被重新排序了

解决方案

• 定向技术：又称旁路或专用通路技术，思想是通过专用通路使后续指令提前得到前指令的运算结果，以避免或减少流水线停顿。

• 停顿：不是所有的数据冲突都可以用定向技术来解决。增加流水线互锁机制，插入“暂停” 。

  互锁机制：检测发现数据冲突，使流水线停顿，直至冲突消失。

• 编译器解决：编译器重新组织指令顺序来消除冲突，又称为指令调度或流水线调度。

控制冲突

分支指令引起的冲突比数据或结构冲突严重，有分支成功或失败两种结果。

• 如果分支成功：PC 值改变为分支转移的目标地址。（在条件判定和转移地址计算都完成后改 PC 值）。
• 如果分支失败：PC 的值指向顺序的下一条指令

可以通过软件（编译器）减少分支延迟

预测分支失败（不转移）

总预测分支失败，并按失败的分支路径处理。

允许分支指令后的指令继续在流水线中流动，好像什么都没发生。

• 若确定分支失败（预测正确），流水线正常流动，无延迟。
• 若确定分支成功（预测错误），把分支指令后取出的所有指令转化为空操作，并按分支目的地址重新取指令执行。

要保证：分支结果出来之前不能改变处理机的状态，以便猜错时处理机能够回退到原先的状态。有延迟。

预测分支成功（转移）

假设分支转移成功，并从分支目标地址处取指令执行。

在前述 5 段流水线中，除非已知分支目标地址，这种方法没有任何好处。

延迟分支

延迟分支：顺序执行延迟槽中指令

延迟槽：一条或几条与转移指令结果无关而有用的指令

主要思想：由编译器通过重排指令序列，在分支指令后紧跟一条或几条延迟槽指令，不管分支是否成功，都顺序执行延迟槽中的指令。从而逻辑上 “延长” 分支指令的执行时间。

延迟槽指令的调度策略

从前调度：被调度的指令必须与分支无关，适合任何情况。

从目标处调度：分支成功时起作用，分支成功概率高时采用。

从失败处调度：分支失败时起作用，不能从前调度时可用。

转移指令对流水线和性能的影响

图中条件转移指令（BRANCH）通常要在 ME 段末尾才会使 PC 内容发生改变，流水线需停顿 3 个时钟，直到 PC 中生成新地址后，才能取出下一条指令。

在 k 段流水线中，假设最坏情况下，一条条件转移造成 k-1 个时钟周期的停顿

流水线的实现

三、向量处理机

向量处理的主要特点是一条指令可以处理多个（或多对）数据，指令处理效率较高。能够把流水线和并行性能结合起来。

向量处理机是另一类指令级并行的流水线机器。能较好地发挥流水线技术的特性，是并行处理中一种重要的高性能结构，有吞吐量大、效率高、性价比高、适用性广的优点。

向量处理方法

基本概念

• 向量：指一组标量，标量是指单个量。如数组 A＝（a₁，a₂，a₃，…，a_n）是一个 n 元向量，其分量元素 a_i 就是一个标量。
• 标量处理：一条标量指令一次可处理 1 个或 1 对操作数。相应的运算叫做标量处理。
• 向量处理：一条向量指令可以处理 n 个或 n 对操作数。对这组数的运算叫做向量处理，相应指令叫向量指令。

在具有向量数据表示的机器中，向量指令的基本格式为：

参加运算的每个向量都需指明其基地址、 位移量和向量长度。

向量处理

分析向量计算 Y = a X + Y

用向量处理机处理，指令如下：

LD 		F0 a;			标量a 装入F0
LV 		V1 M(X); 		向量X 装入V1
MULV 	V2, F0 ,V1; 	向量乘 V2 = aX
LV 		V3, M(Y); 		向量Y 装入V3
ADDV 	V4, V3, V2; 	向量加
SV 		M(Y), V4; 		向量存 V4

基本思想是对两个向量的对应分量进行计算，产生一个结果向量。基本模式表示为 C = A + B

按向量运算中各计算相继的次序，归结为 3 种方法：

1. 横向处理：计算按行方式从左至右横向进行，逐个求向量中的每个分量。
2. 纵向处理：计算按列方式自上而下纵向地进行。
3. 纵横处理：又称分组处理，上述两种方法的结合，即组内采用纵向处理，组间采用横向处理。

【例】用三种不同处理方法计算表达式 D＝A × (B + C)。其中 A、B、C、D 都是长度为 N 的向量。

横向处理

按行表达式依次计算每个分量：

缺点

• 采用静态流水方式计算，每个向量加、乘运算中都会发生数据相关。
• 计算一个分量要进行 2 次（乘法和加法）转移。
• 共出现 N 次数据相关、2N 次功能转换。
• 横向处理不适合于向量流水处理。

纵向处理

向量计算按列方式自上而下纵向进行

纵向处理共出现 1 次数据相关及功能转换，适合向量流水线处理机。

当向量长度 N 超过向量寄存器限度时，可分组处理。

纵横处理

假设向量长度为 N，分成 S 组，每组长度为n( 寄存器长度)；r 为余数，也作为一组处理，共 S+1 组。有 N = S n + r，其中 n ≤ N，r < n，所有参数均为正整数。

纵横方法适合寄存器-寄存器工作的向量处理机。

向量处理机结构

两种典型的结构

• 存储器-存储器型结构：纵向处理方式采用
• 寄存器-寄存器型结构：分组处理方式采用

存储器-存储器结构

流水线运算部件的输入和输出端都直接（或经缓冲器）与存储器相连。

• 源向量和目的向量都存放在存储器中，运算的中间结果需要送回存储器
• 对应的向量分量能并发访问，计算结果能并行地保存。
• 普通存储器的 3 倍带宽：一个时钟周期内读出两个操作数并写回一个结果。

寄存器-寄存器结构

• 向量处理机的另一种主要结构，包含一个由一级或多级中间存储器形成有层次结构的存储系统。

• CRAY-1 向量处理机，主存与流水结构运算器之间有一级或两级中间存储器。运算速度达亿次／秒以上，可实现向量运算，标量运算。

• 带宽高的存储器安排在离处理器最近的位置。中间级存储器起数据中间存储作用，相当于寄存器。

CRAY-1向量处理机

• 主存（64个模块）
• 向量运算：中间存储器是 8 个向量寄存器（V），与主存成组交换。
• 4 组流水部件：向量、浮点、标量和地址运算部件，共 12 个。
• 标量
  • 8 个 64 位标量寄存器 S 和 64 个快速暂存器 T（两级）
  • 8 个（24 位）A 地址寄存器和（64 个 24 位）B 寄存器（两级）
• 指令缓冲器预取指令，并存放主要程序段。

基本结构

12 条单功能流水线，满足一定条件，可并行工作。

向量运算

• 8 个向量寄存器（V）支持向量运算。

• 主存储器与 V 寄存器之间数据传送以成组传送方式进行。

• 向量指令能对向量寄存器的分量进行连续处理。

• 6个单功能流水部件：进行向量运算

  整数加（3 拍） 逻辑运算（2 拍）

  移位（4 拍） 浮点加（6 拍）

  浮点乘（7 拍） 浮点迭代求倒数（14 拍）

• 向量运算流水线，满足一定条件，可并行工作：

  1. 功能部件不冲突：例如 V0←V1 + V2 和 V6←V4 * V5
  2. 源寄存器不冲突：如 V3←V1 + V2 和 V6←V5 * V4
  3. 结果寄存器不冲突：如 V4←V1 + V2 和 V6 ←V3
  4. 数据不相关：例如 V0←V1 + V2 和 V6←V4 * V5

标量运算

• 两级中间存储器。一级是高速 S 寄存器（8 个 64 位），一级T寄存器（与主存间以成组传送方式交换数据）
• 8 个（24 位）地址寄存器 A 和 64 个（24 位）B 寄存器。B 寄存器与主存间数据传送以成组传送方式（相当于 A 寄存器组的 Cache）。所有操作由程序指令直接控制。
• 指令缓冲器预取指令，并存放主要程序段。如内循环指令，不必到主存反复取指。

提高向量处理机性能的常用技术

• 设置多个功能部件，使它们并行工作
• 采用链接技术，加快一串向量指令的执行
• 采用循环开采技术，加快循环的处理
• 采用多处理机系统，进一步提高性能

多功能部件的并行操作

以 CRAY-1 向量处理机为例

12 个功能部件独立，满足一定约束条件，可并行工作。

约束条件为：

1. 无向量寄存器使用冲突
2. 无功能部件使用冲突

向量寄存器使用冲突

并行工作的向量指令中，源向量或结果向量使用相同的向量寄存器。

例如：

V2 和 V5 源出现了寄存器冲突。

功能部件使用冲突

多条并行工作的向量指令所使用同一功能部件。

例如：

理想情况下，m 个功能部件并行工作，运算速度提高 m 倍。实际中通常小于 m。

链接技术

寄存器-寄存器结构中，一个向量运算所产生的输出，可直接作为下一个向量运算的输入，这种结果寄存器立即成为后继指令操作数寄存器的技术，称为流水线链接技术。

如向量加、向量乘操作：

• 链接技术利用向量指令间存在的先写后读的数据相关性， 加快向量指令序列执行速度。
• 链接技术是流水线定向技术的发展。

并行技术和链接技术结合

• 1、2 条指令可并行执行：无寄存器和功能部件冲突
• 第 3 条指令与前两条指令均能链接。
• 1、2 条指令执行时间和寄存器长度必须相同

• 处理机自动检测每一条向量指令是否与前一条指令形成链接。
• 若满足链接条件，便启动本指令工作而形成链接。
• 数据进（出）每个功能部件，需1个时钟周期

链接条件

• 空间方面：无向量寄存器和功能部件使用冲突

• 时间方面：

  1. 只有前一条指令的第1个结果分量送入结果向量寄存器的那一个时钟周期方可链接。

  2. 向量指令的两个源操作数分别是两条先行指令的结果寄存器时，先行两条指令产生运算结果的时间必须相等。同时，两条向量指令的向量长度也须相等。 例如

     LV V3, M(A); V3←A

     ADDV V2, V0, V1; V2←V0 + V1

     MULV V4, V2. V3; V4←V2 × V3

假定，一个程序段有以下三个向量操作：

链接运算时间

分段开采技术

• 向量长度大于向量寄存器长度时，向量须分段处理，即一次处理一个向量段。
• 处理长向量的程序结构称为向量循环，也称分段开采技术。
• 向量分段由系统硬件和软件控制完成，对程序员透明，即看不到分段过程。
• 进入循环前，系统会根据向量长度计算出循环的次数。
• 分段需一定时间开销，包括流水线启动开销。

多处理机体系结构

• 前三种措施都是在单处理机结构的向量计算机上实现的。
• 新型向量机采用多处理机体系结构。

下图是 CRAY X-MP 的结构框图，由 4 个 CPU 组成。CPU 的结构同 CRAY-1 向量处理机相似。

向量处理机的性能评价

向量处理机性能主要参数：

• 一条向量指令的处理时间
• 每秒浮点运算数目 MFLOP (或一个浮点运算的时间）。
• 一组向量指令的处理时间
• 向量流水线的最大性能 R_∞
• 半性能向量长度 n_1/2
• 向量长度临界值

一条向量指令的处理时间T_vp

执行一条向量长度为 n 的向量指令所需的时间为：T_vp = T_s + T_e + (n - 1)T_c

T_s：流水线的建立时间，流水线开始工作需要准备时间。
T_e：第一个（对）向量元素通过流水线的时间。
T_c：流水线的时钟周期时间。

各流水段执行时间相等时：T_vp = (s + e + n - 1) T_c

s：建立流水线所需时的钟周期数
e：流水功能部件级数

令 T_start = s + e - 1，则 T_vp = (T_start + n) T_c，其中 T_start：向量指令启动时间（周期数）

从向量指令开始执行到还差一个时钟周期就产生第一个结果所需的时钟周期数。即此后每个时钟周期流出一个结果（共 n 个）。

每秒百万次浮点运算MFLOPS

MFLOPS = I_FN / (T_p × 1000000)，其中 I_FN 是程序中浮点运算总次数，T_p 是执行程序时间

• MFLOPS 的倒数：每次浮点运算所需的时间
• MFLOPS 基于操作而非指令，用来比较两种不同机器
• 程序在不同机器上执行的指令数目可能不同，但执行的浮点运算总次数相同。
• MFLOPS 衡量机器浮点操作性能，不体现整体性能。

一组向量指令的处理时间

一组向量指令的执行时间并不是每条指令执行时间的简单相加，具体要考虑多重因素：

1. 向量的长度N
2. 向量指令处理方式
3. 重建一个向量流水线的启动时间。
4. 与向量指令“分段” 或“编队” 执行有关 。

• 编队：能在一个同一时间或时间段并行或链接执行的一条（或多条）向量指令，称为一个编队
  • 并行编队：同一编队中的多条向量指令能并行执行（无功能部件冲突和数据相关）。
  • 链接编队：同一编队中的多条向量指令能链接执行

若 m 个编队组成的向量指令顺序执行，则总执行时间为每个编队的执行时间之“和”，如下图

T(i)_vp：第 i 个编队的执行时间

并行编队中，多条指令的执行时间取该编队中各指令的执行时间的最大值。

一组向量指令、 m个编队的处理时间为

T(i)_start：第 i 编队中各指令的启动时间的最大值

令该组指令总的启动时间（时钟周期个数）如下

表示成时钟周期个数：T_all = T_start + mn（拍）

向量处理机的峰值性能 R_∞

R_∞：向量长度为无穷大时，向量处理机的最高性能，也称为峰值性能。

通常指向量指令的浮点操作次数

半性能向量长度 n_1/2

半性能向量长度 n_1/2：向量处理机性能为其最大性能的一半时所需的向量长度。

评价向量流水线的建立时间对性能影响的重要参数。

反映为建立流水线而导致的性能损失。

• n_1/2 越小，流水线建立的时间越少，性能越好。
• 向量长度 n＝n_1/2，表明这时整个向量流水处理中有一半时间是在做有效操作，一半时间被浪费

向量长度临界值n_v

向量长度临界值 n_v：是指对于某一计算任务而言，向量方式的处理速度优于标量串行方式处理速度时所需的最小向量长度。

四、指令级并行（硬件方法）

指令级并行的概念

指令级并行性（ILP，Instruction-Level Parallelism）：指令之间存在的一种固有的并行性，使计算机可以并行执行两条或两条以上的指令。

• 细粒度并行性：处理机中指令一级或操作一级的并行处理。
• 粗粒度并行性：进程、任务、程序一级的并行处理。

开发指令级并行度能降低指令执行的平均周期数 CPI，是提高计算机性能的重要方法，属细粒度并行性。

开发指令级并行性的主要途径有：

• 资源重复： 重复设置多个处理部件（空间并行）
• 流水线技术： 使指令重叠并行执行（时间并行）

基本程序块：

• 基本程序块：一串连续的代码除了入口和出口以外，没有其他的分支指令和转入点 。
• 程序平均每 4～7 条指令就会有一个分支。
• 基本程序块内并行性低，必须跨越程序块开发 ILP

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

• 每一次循环的内部，没有并行性
• 开发循环的不同叠代之间存在的并行性
• 最常见、最基本：循环展开（loop unrolling）技术
• 采用向量指令和向量数据

相关与指令级并行

相关与流水线冲突

相关：程序中指令之间的一种相互依赖关系——程序固有的属性。

• 三种相关类型：数据相关、名相关、控制相关

流水线冲突：在流水线中，相关存在使得流水线指令流中的后续指令不能在指定的时钟周期执行，称为流水线冲突。

但相关是否会导致实际冲突的发生以及该冲突会带来多长的停顿，是流水线的属性。

• 三种流水线冲突：

  结构冲突：硬件资源冲突引起。
  数据冲突：数据相关和名相关引起。
  控制冲突：控制相关引起。

解决

两个方面可以解决：

1. 保持相关，但避免发生冲突。如指令调度
2. 通过代码变换，消除相关。如寄存器重命名。

程序顺序：由原来程序确定的、完全串行方式下指令的执行顺序。只要保持程序运行结果正确性，程序顺序不必一定保持。只有在导致错误的情况下，才保持程序顺序。

对于正确执行程序来说，必须保持的最关键的两个属性是：数据流和异常行为

保持异常行为

• 改变指令执行顺序，都不改变程序中异常的发生情况.
• 原来程序中异常怎么发生，改变执行顺序后还是怎么发生。

弱化为：指令执行顺序的改变不能导致程序中发生新的异常。

数据流：数据值从其产生者指令到其消费者指令的实际流动。

• 分支指令使得数据流有动态性。
• 分支指令的执行结果决定哪条指令才是所需数据的产生者。

既保持异常行为，也不改变数据流。就可以不遵守控制相关，并进行指令调度。

指令的动态调度

动态调度概念

• 程序执行过程中，依赖专门硬件和算法对代码进行调度。
• 通过配置多个资源（功能部件），允许多条指令同时动态地处于执行阶段（动态调度流水线）
• 允许多条指令同时处于执行阶段。

之前的流水线假设：指令按序流出、按序执行，一旦一条指令受阻，其后的指令都将停顿。

基本流水线中，许多指令受阻来自结构冲突和数据冲突。

• 一般在 ID 阶段检测结构冲突和数据冲突
• 一条指令在 ID 阶段受阻，其他指令不能进入执行阶段。

• 为了使后续指令提前执行，后续指令须能提前流出并执行。这会改变指令的执行顺序，导致乱序执行。
• 乱序执行导致指令的完成是乱序完成。

乱序执行

两个简单方案实现：

1. 把指令在 ID 阶段工作拆分为两步：即
   • 检测结构冲突：只要没有结构冲突，就让指令流出。
   • 等待数据冲突消失：流出指令一旦操作数就绪就立即执行。

2. 是在 ID 阶段和执行阶段中间增设新的指令窗口

   • 译码段和执行段间有指令窗口 (缓冲栈），存放译码信息。
   • 允许窗口中不冲突的后续指令，提前执行。 乱序执行、乱序完成。

   

   • 减少指令 ID 段的工作和停留，使后续指令提前流出

动态调度流水线：在同一时间内能够同时执行多种功能的流水线。

在同一时间仅执行一种功能的流水线，称为静态流水线。

动态调度流水线基本特点

• 调度策略：乱序执行、乱序完成
• 要求有多个功能部件、或者功能部件流水化。这里假设具有多个功能部件。
• 译码阶段划分为流出和读操作数：

记分牌动态调度方法

基本思想

• 把 5 段流水线中 ID 段分解成流出和读操作数两个段

• 执行段采用多功能部件，允许多条指令在执行段并行操作。
• 尽早执行没有结构冲突和数据冲突的指令。
• 实施判断是否有 WR、RW、WW 相关存在。
• 通过互锁机制，阻止数据冲突发生。
• 由一个称为记分牌的硬件实现对指令的动态调度。

记分牌的目标是在没有结构冲突时，尽可能早地执行没有数据冲突的指令，实现每个时钟周期执行一条指令。如果某条指令被暂停，而后面的指令与流水线中正在执行或被暂停的指令都不相关，那么这些指令就可以跨越它们，继续流出和执行下去。记分牌全面负责和管理这些指令的流出和执行，当然也包括检测所有的冲突。

记分牌的硬件表格

• 记分牌硬件表格为 3 张表，分别用于记录指令的执行状态、功能部件状态、寄存器状态以及数据相关关系等。
• （浮点操作）考虑流出、读操作数、执行、写回四个执行状态

指令执行状态表：记录（已取指指令）执行状态。

功能部件状态表：记录各功能部件的状态。

结果（目标）寄存器状态表：指出哪个功能部件将把结果写入该目标寄存器。

有记分牌的MIPS处理器基本结构

指令执行过程——4段

（主要考虑浮点操作）一条指令执行过程为流出、读操作数、执行和写结果、

流出（Issue，IS）

功能部件空闲，目的寄存器可用（无 WW 冲突），就流出指令，并修改记分牌内记录。否则，不流出。检测目的寄存器可用性，解决了 WW 冲突。

读操作数（Read Operands，RO）

源操作数可用（就绪且未读），就读出并执行。否则，等待写完成后读出（锁定）。动态地解决了 WR 冲突。

执行

取到操作数后功能部件开始执行（可能乱序执行），产生出结果后，通知记分牌已完成执行。

• 在浮点流水线中，这一段可能要占用多个时钟周期。
• 其他指令如不与正在执行或被锁定指令相关，可提前执行或完成。

写结果

执行部件完成后，检测目标寄存器，以避免 RW 冲突

• 如检测到 RW 冲突，不许该指令将结果写到目标寄存器。
  这发生在以下情况：

  • 前面的某条指令还没有读取该操作数（即前指令的源操作数寄存器是本指令的目标寄存器）。

  在这种情况下，记分牌必须等待，直到该冲突消失。

• 如果不存在 RW 冲突（或冲突已消失），把结果写入目的寄存器，并释放该指令使用的所有资源（ 指令乱序执行成为可能），避免了 RW 冲突。

通过记分牌控制：避免了 WW、WR、RW 冲突及结构冲突

举例

Tomasulo算法

基本思想

• 又称公共数据总线法，Tomasulo 于 1967 首先提出.
• 通过分散控制处理数据相关和乱序执行，记录和检测指令相关，把发生 WR（RAW）冲突的可能性减少到最小
• 通过寄存器换名来消除 WAR 冲突和 WAW 冲突
• 需要更多地依赖于硬件

Tomasulo 算法中，寄存器换名是通过保留站和流出逻辑来共同完成

指令流出到保留站后，按以下方法完成寄存器换名：

• 如果该数据已经就绪，其操作数寄存器号换成数据本身。
• 如果其操作数还没有计算出来，则将该指令中相应的寄存器号换名为将产生这个操作数的保
  留站的标识，不再与寄存器有关系。

基于Tomasulo算法的MIPS处理器浮点部件基本结构

• 指令队列：存放指令部件送来指令, 先进先出、顺序流出

• 保留站：保存流出到本功能部件执行的指令信息

  包括： 操作码、操作数及用于检测和解决冲突的信息

  浮点加法器有3个保留站：ADD1，ADD2，ADD3

  浮点乘法器有两个保留站：MULT1，MULT2

  每个保留站有一个标识字段，唯一地标识了该保留站

• 访存部件缓冲器：load 缓冲器和 store 缓冲器

  存放读 / 写存储器的数据或地址（类似保留站）

• 公共数据总线 CDB：重要的数据通路

  所有计算结果都送到 CDB，它直接播送到各个需要的地方。

  有多个执行部件且采用多流出的流水线中，采用多条 CDB。

  计算结果先送到 CDB，再传送到功能部件，不经过寄存器。

• 浮点寄存器 FP

  共有16个浮点寄存器： F0，F2，F4，…，F30。

  通过总线连接到各功能部件，通过CDB连接到store缓冲器。

• 运算部件

  浮点加法器：完成加法和减法操作

  浮点乘法器：完成乘法和除法操作

指令执行步骤

流出

流出：从指令队列头部取一条指令。

• 如果该指令对应保留站空闲，就把该指令送到保留站 r。如果保留站不空闲，指令不流出。
• 指令到保留站后，如操作数已就绪，把操作数送到保留站 r。
• 如操作数未就绪，将产生操作数的保留站标识送到保留站 r。
  这步实际上是寄存器换名（换成保留站标识）。消除 RW 冲突。
• 目的寄存器预约：指定将接收哪个保留站的结果。
  这一步可消除 WW 冲突。

执行

执行：通过保留站执行指令规定的操作。

• 如两操作数已就绪，相应的执行部件执行规定的操作。
• 如某操作数没有计算出来，保留站监视 CDB，并等待计算结果。
• 一旦记录的保留站完成计算，直接把数据送给保留站 r。（最大限度通过推迟执行减少 WR 冲突）
• 如多条指令在同一周期操作数均就绪，不同部件可并行执行。（同一部件中，多条指令需逐一执行）
• load 和 store 指令的执行需要分两步
  • 计算有效地址（要等到基地址寄存器就绪）
  • 把有效地址放入 load 或 store 缓冲器

写结果

功能部件计算完毕后，将计算结果放到 CDB，等待寄存器或保留站，包括 store 缓冲器，并从 CDB 上获取。

算法说明

算法特点

冲突检测和指令执行控制是分布的。

每个功能部件的保留站中的信息决定了什么时候指令可以在该功能部件开始执行。

计算结果通过 CDB 直接从产生它的保留站传送到所有需要它的功能部件，不用经过寄存器。

每个保留站有 7 个字段：

• Op：对源操作数进行的操作
• Q_j，Q_k：将产生源操作数的保留站号 ，如 Add1
  0 表示操作数已经就绪且在 V_j 或 V_k 中，或者不需要操作数。
• V_j，V_k：源操作数的值 ，如 Reg[F4]
  对每一个操作数来说，V 或 Q 字段只有一个有效。
• Busy：“yes”表示本保留站或缓冲单元 “忙”
• A：仅 load 和 store 缓冲器有该字段——开始先存放指令中的立即数字段，地址计算后存放有效地址。

例子

符号意义

• r：分配给当前指令的保留站或者缓冲器单元编号；
• rd：目标寄存器编号；
• rs、rt：操作数寄存器编号；
  rs 对应的保留站字段是 V_j，Q_j，rt 对应的保留站字段是 V_k，Q_k
• imm：符号扩展后的立即数；
• RS：保留站
• result：浮点部件或 load 缓冲器返回的结果；
• Q_i：寄存器状态表；0 表示相应寄存器中数据就绪。
  正整数表示相应的寄存器、保留站或缓冲器单元正在等待结果。
• Regs[ ]： 寄存器组

动态分支预测技术

开发的 ILP 越多，控制相关的制约就越大。

对每个时钟周期流出多条或 n 条指令（称为 n 流出）的处理机来说，分支预测的准确度非常重要。要给处理器连续提供指令，就需要准确地预测分支。

动态分支预测：根据分支指令过去的表现来动态地预测其下一次转移的方向，称为动态分支预测技术。

采用分支历史表BHT

概念

• 最简单的动态分支预测方法。
• 用 BHT 记录分支指令最近一次或几次的执行情况（成功还是失败），并进行预测。

BHT 格式

[转移指令，历史表信息，转移目标指令]

• 对转移指令，转移成功或失败的信息记录在 BHT 中的历史位中
• 无论预测的转移方向与实际执行结果方向是否相同，都要修改 BHT
• 常用 2 位计数器来记录最近二次转移是否成功的信息。

逻辑结构及原理

当一条转移指令第一次执行时，可预置转移历史信息。

用二进制数 10、11、01、00 来表示转移预测状态的转换图：

两个步骤：分支预测；状态修改

• 分支预测：当分支指令到达（ID）段时，从 BHT 读出的信息进行分支预测 。若预测正确就继续处理后续的指令，否则，作废已预取和分析的指令，恢复现场，并从另一条分支路径重新取指令。
• 状态修改

采用分支目标缓冲器BTB

分支目标缓冲器BTB（Branch-Target Buffer）

• 将分支成功的分支指令的地址和它的分支目标地址都放到一个缓冲区中保存
• 缓冲区以分支指令的地址作为标识，得到转移目标指令地址信息
• 在 IF 段访问 BTB，将分支的开销降为 0

BTB格式

[成功转移的分支指令地址，转移目标指令地址]

结构和操作

• 看成是用专门的硬件实现的一张表格。
• 执行过的成功分支指令的地址（作为该表的匹配标识）预测的分支目标地址。

采用 BTB 后，在流水线各个阶段进行的相关操作：

基于硬件的前瞻执行

基本思想

• 对分支指令结果进行猜测，并按猜测结果继续取指、流出和执行后续的指令。但执行结果 “不写回” 寄存器或存储器。
• 而是写入一个再定序缓冲器 ROB（ReOrder Buffer）。等指令得到 “确认” 后再写回寄存器或
  存储器。
• 即把写结果分成两个不同的段：写结果和指令确认
• 指令 “确认”后，ROB 结果通过公共数据总线 CDB 在指令之间传送，供需要这些结果的指令使用

结合了以下三种思想：

1. 动态分支预测：选择后续的执行指令。
2. 在控制相关的结果尚未出来前，前瞻地继续取指、流出和执行后续的指令
3. 允许指令乱序执行，但必须顺序确认。确认前，不允许不可恢复的操作。

支持前瞻执行的浮点部件的结构

指令执行步骤

流出

• 从浮点指令队列的头部取一条指令。
• 如果有空闲的保留站（设为 r）且有空闲的 ROB 项（设为 b），就流出该指令，并把相应的信息放入保留站 r 和 ROB 项b。
• 如果保留站或 ROB 全满，便停止流出指令，直到它们都有空闲的项。

执行

• 如果有操作数尚未就绪，就等待，并不断地监测 CDB。（检测 WR 冲突）
• 当两个操作数都已在保留站中就绪后，就可以执行该指令的操作。

写结果

• 结果产生后，将结果连同本指令在流出段所分配到的 ROB 项的编号放到 CDB 上，经 CDB 写到 ROB 以及所有等待该结果的保留站。
• 释放产生该结果的保留站
• store 指令在本阶段完成

确认

• 对分支指令、store 指令以及其它指令的处理不同
• （除分支指令和 store 指令）其它指令当该指令到达 ROB 队列的头部而且其结果已经就绪时，把该结果写入该指令的目的寄存器，并从 ROB 中删除该指令。
• store 指令：处理与上面的类似，只是它把结果写入存储器。
• 分支指令
  • 当预测错误的分支指令到达 ROB 队列的头部时， 清空 ROB，并从分支指令的另一个分支重新开始执行。（错误的前瞻执行）
  • 当预测正确的分支指令到达ROB队列的头部时，该指令执行完毕。

多指令流出技术

基于静态调度的多流出技术

基于动态调度的多流出技术

超长指令字技术

1. 超长指令字的生成由编译器来完成：编译器将串行的操作序列合并为可并行执行的指令序列，以最大限度实现操作并行性。
2. 单一的控制流或控制器：每个时钟周期启动一条超长指令。
3. 超长指令字包含多个控制字段：每个字段独立地控制每个不同的功能部件。
4. 有大量的数据通路和功能部件：编译器在编译时已解决数据相关和资源冲突，控制硬件比较简单。

超流水线处理机

• 将每个流水段进一步细分，这样在一个时钟周期内能够分时流出多条指令。这种处理机称为超流水线处理机。
• 对于一台每个时钟周期能流出 n 条指令的超流水线计算机来说，这 n 条指令不是同时流出，而是每隔1/n 个时钟周期流出一条指令。
  • 实际上该超流水线计算机的流水线周期为 1/n 个时钟周期。
• 有的资料上，把指令流水线级数为 8 或 8 以上的流水线处理机称为超流水线处理机。

每个时钟周期分时流出两条指令的超流水线计算机的时空图：

五、互连网络

概念

互连网络

互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统中结点之间的相互连接。 互连网络已成并行计算机系统中重要的核心部件。对整个计算机系统的性能有着决定性影响。

• SIMD 计算机和 MIMD 计算机的关键组成部分
• 已成为计算机组织和系统结构中独立的研究内容。
• 结点：处理器、存储模块或其它设备。

三要素

• 开关元件：网络中最基本模块，在不同系统和控制中，开关元件所处的物理位置和工作状态不同。
• 互连结构：网络合理布局关键，反映系统结构特征。用有向图或无向图表示，节点对应开关元件或处理机，边对应通信链路。
• 控制方式：网络中各种开关的控制方法。

基本特征

拓扑结构

静态网：各节点间有专用通信线路（链路），运行间不改变或重新组合，又称直接网络（节点通过链路直接连接）

组成：由链路、结构及网络节点组成。

结构：线性、环形、树形、立方体等。

动态网：各节点间有专用通信线路（链路），可通过网络中开关重新组合。节点与节点的连接由程序或控制信号动态地改变，又称间接网络（节点与交换开关连接）。

组成：由链路、结构、开关及节点组成。
结构：总线、环状、开关、（单）多级。

控制策略

集中控制：全局控制器接收所有通信请求，设置互连网络的开关连接。

分散控制：通信请求和开关设置由互连网络分散地进行。

定时方式

同步系统：系统使用一个集中的统一时钟。

异步系统：无统一时钟，节点根据各自情况独立工作。

交换方法

线路交换：源结点和目的结点间的物理通路在整个数据传送期间一直保持连接。

分组交换：信息分割成组（包），各组（包）通过多个不同路径传分别送入互连网络，传送不存在一个实际连接的固定通路。

互连函数

根据输入与输出结点之间的对应关系，有以下表示方法：

• 函数表示法：变量 x 表示输入，函数 f(x) 表示输出，建立输入与输出端的一一对应关系。
  自变量和函数常用二进制、十进制表示。互连函数反映网络输入数组和输出数组之间对应的排列关系，也称排列函数。
• 输入输出对应表示法：

• 图形表示法：用图形表示输入端与输出端之间的一一对应关系

• 循环表示法：如 (0 4)(1 5)(2 6)(3 7)

互连函数

变量 x：输入（设 x = 0，1，…，N - 1）

函数 f(x)：输出

通过数学表达式建立输入端号与输出端号的连接关系。即在互连函数 f 的作用下，输入端 x 连接到输出端 f(x)

• 互连函数反映了网络输入数组和输出数组之间对应的置换关系或排列关系。
  （有时也称为置换函数或排列函数）
• 互连函数 f(x) 有时可以采用循环表示，即：（x₀ x₁ x₂ … x_j-1）
  表示：f(x₀)=x₁，f(x₁)=x₂，…，f(x_j-1)=x₀，j 称为该循环的长度
• 设 n=log₂N，则可以用 n 位二进制来表示 N 个输入端和输出端的二进制地址，互连函数表示为：f(x_n-1x_n-2…x₁x₀)

恒等函数

恒等函数：实现同号输入端和输出端之间的连接

I（x_n-1x_n-2…x₁x₀）= x_n-1x_n-2…x₁x₀

交换函数

交换函数：实现二进制地址编码中第 k 位互反的输入端与输出端之间的连接。

二进制地址编码下，某一位的输入与输出端编号相反。

• 主要用于构造立方体和各种超立方体互连网络。
• 它共有 n = log₂N 种互连函数。（N 为结点个数）
• 当 N = 8 时，n = 3，可得到常用的立方体互连函数：

均匀洗牌函数

均匀洗牌函数：将输入端分成数目相等的两半，前一半和后一半按序一个隔一个，从头依次与输出端相连，类似洗牌方式

• 也称为混洗函数（置换）
• 函数关系如下

即把输入端的二进制编号循环左移一位。

对于有些互连函数（设为 s），还可以定义其第 k 个子函数和第 k 个超函数。它们分别是把 s 作用于输入端的二进制编号的低 k 位和高 k 位。

例如，对于均匀洗牌函数，其第 k 个子函数是

即把输入端的二进制编号中的低 k 位循环左移一位。

均匀洗牌函数的第 k 个超函数是

即把输入端的二进制编号中的高 k 位循环左移一位。

对于任意一种函数 f(x)，如果存在 g(x)，使得 f(x) × g(x) = I(x)，则称 g(x) 是 f(x) 的逆函数，记为 f^-1(x)。

f^-1(x) = g(x)

逆均匀洗牌函数：将输入端的二进制编号循环右移一位而得到所连接的输出端编号。

逆均匀洗牌函数：输入端二进制地址循环右移一位。

蝶式函数

蝶式互连函数：把输入端的二进制编号的最高位与最低位互换位置，便得到了输出端的编号。

• 均匀洗牌，蝶式函数不能单独实现任意结点间互连。它们与交换函数多级组合是构成复杂多级网络的基础

反位序函数

反位序函数：将输入端二进制编号的位序颠倒过来求得相应输出端的编号

当 N=8 时，有：ρ(x₂x₁x₀) = x₀x₁x₂

移数函数

移数函数：将各输入端都错开一定的位置（模 N）后连到输出端。

PM2I函数

• P 和 M 分别表示加和减，2I 表示 2ⁱ。
  • 该函数又称为 “加减2ⁱ ” 函数。
• PM2I 函数：一种移数函数，将各输入端都错开 2ⁱ 个位置（模 N）后连到输出端。

• PM2I 互连网络共有 2n 个互连函数

例子

阵列计算机 ILLIAC Ⅳ

采用 PM2_±0 和 PM2_±n/2 构成其互连网络，实现各处理单元之间的上下左右互连。

互连网络的结构参数与性能指标

结构参数

• 网络规模 N：网络中结点的个数。表示该网络所能连接的部件的数量。
• 结点度 d：与结点相连接的边数（通道数），包括入度和出度。
• 结点距离：对于网络中的任意两个结点，从一个结点出发到另一个结点终止所需要跨越的边数的最小值。
• 网络直径 D：网络中任意两个结点之间距离的最大值。网络直径应当尽可能地小。
• 等分宽度 b：把由 N 个结点构成的网络切成结点数相同（N/2）的两半，在各种切法中，沿切口边数的最小值。
• 线等分宽度：B = b × w
  • 其中：w 为通道宽度（用位表示）
  • 该参数主要反映了网络最大流量。
• 对称性： 从任何结点看到的拓扑结构都是相同的网络称为对称网络。对称网络比较容易实现，编程也比较容易。

性能指标

评估互连网络性能的两个基本指标：时延和带宽

通信时延

指从源结点到目的结点传送一条消息所需的总时间，由以下 4 部分构成：

• 软件开销：在源结点和目的结点用于收发消息的软件所需的执行时间。
  • 主要取决于两端端结点处理消息的软件内核。
• 通道时延：通过通道传送消息所花的时间。
  • 通路时延 = 消息长度 / 通道带宽
  • 通常由瓶颈链路的通道带宽决定。
• 选路时延：消息在传送路径上所需的一系列选路决策所需的时间开销。
  • 与传送路径上的结点数成正比。
• 竞争时延：多个消息同时在网络中传送时，会发生争用网络资源的冲突。为避免或解决争用冲突所需的时间就是竞争时延。
  • 很难预测，它取决于网络的传输状态。

网络时延

通道时延与选路时延的和。

• 由网络硬件特征决定，与程序行为和网络传输状态无关。

端口带宽

对互连网络中的任意一个端口，端口带宽是指单位时间内从该端口传送到其他端口的最大信息量。

• 在对称网络中，端口带宽与端口位置无关。网络的端口带宽与各端口的端口带宽相同。
• 非对称网络的端口带宽则是指所有端口带宽的最小值。

聚集带宽

网络从一半结点到另一半结点，单位时间内能够传送的最大信息量。

等分带宽

与等分宽度对应的切平面中，所有边合起来单位时间所能传送的最大信息量。

静态互连网络

各结点之间有固定的连接通路、且在运行中不能改变的网络。

典型的静态互连网络

线性阵列

一种一维的线性网络，其中 N 个结点用 N-1 个链路连成一行。（N 表示结点的个数）

• 端结点的度：1
• 其余结点的度：2
• 直径：N - 1
• 等分宽度 b = 1

环和带弦环

环：用一条附加链路将线性阵列的两个端点连接起来而构成。可以单向工作，也可以双向工作。

带弦环：增加的链路越多，结点度越高，网络直径就越小

全连接网络：

循环移数网络

通过在环上每个结点到所有与其距离为 2 的整数幂的结点之间都增加一条附加链而构成。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-prxOWbmf-1624538517747)(https://gitee.com/cmz2000/album/raw/master/image/image-20210617211200440.png)]

树形和星形

一棵 5 层 31 个结点的二叉树：

• 一般说来，一棵 k 层完全平衡的二叉树有 N = 2^k - 1 个结点。

星形：

• 结点度较高，为 N - 1。
• 直径较小，是一常数 2。 等分宽度 b=[N/2]
• 可靠性比较差，只要中心结点出故障，整个系统会瘫痪。

胖树形

网格形和环网形

超立方体

带环n-立方体（简称n -CCC）

动态互连网络

由交换开关构成的互连网络，可按运行程序的要求改变网络的连接状态

• 总线网络
• 多级网络
• 交叉开关

STARAN网络

是一种多级立方体网络

• 采用二功能（直送和交换）的 2 × 2 开关。
• 当第 i 级（0 ≤ i ≤ n-1）交换开关处于交换状态时，实现的是 Cube_i 互连函数。
• 一个 N 输入的多级立方体网络有 log₂N 级，每级用 N/2 个 2 × 2开关模块，共需要 log₂N × N/2 个开关。

一个 8 个入端的多级立方体网络如下：

• STARAN 网络采用级控制和部分级控制。

  • 采用级控制时，所实现的是交换功能
  • 采用部分级控制时，则能实现移数功能。

  交换：将有序的一组元素头尾对称地进行交换

3 级 STARAN 网络在各种级控制信号的情况下所实现的入出端连接以及所实现的交换函数和功能。

其中：k₂k₁k₀：控制信号， k_i（i = 0, 1, 2）为第 i 级的级控制信号。

• 当 STARAN 网络用作移数网络时，采用部分级控制，控制信号的分组和控制结果为：

Omega网络

• 一个 8 × 8的 Omega 网络
  • 每级由 4 个 4 功能的 2 × 2 开关构成
  • 级间互连采用均匀洗牌连接方式

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-w9BgPqSP-1624538517752)(C:\Users\10950\AppData\Roaming\Typora\typora-user-images\image-20210618152509739.png)]

• 一个 N 输入的 Omega 网络
  • 有 log₂N 级，每级用 N/2 个 2 × 2 开关模块，共需要 log₂N × N/2 个开关。
  • 每个开关模块均采用单元控制方式。
  • 不同的开关状态组合可实现各种置换、广播或从输入到输出的其它连接。
• N = 8 的多级立方体互连网络的另一种画法

消息传递机制

消息的格式

当源结点和目的结点之间没有直接的连接时，消息需要经过中间的结点进行传递。寻径就是用来实现这种传递的通信方法和算法，有的称之为路由。

四种寻径方式

线路交换、存储转发、虚拟直通、虫孔方式等四种

六、阵列处理机

一种单指令流多数据流处理机（SIMD)，也称为并行处理机。

多处理单元(PE)按一定互连方式并排成阵列，在同一控制部件（CU）控制下，对各自数据完成同一条指令规定的操作。

组成：控制器 CU、多处理单元 PE 、多个存储器模块 M、互连网络 IN 输入输出处理机（主机）

操作模型和特点

五元组表示

阵列处理机 = (N，C，I，M，R)

• N：机器的处理单元（PE）数
• C：控制部件直接执行的指令集，包括标量指令和程序流控制指令。
• I：由 CU 广播至所有 PE 进行并行执行的指令集，包括算术运算、逻辑运算、数据寻径、屏蔽以及其他由每个 PE 对它的数据所执行的局部操作。
• M：屏蔽方案集，将 PE 划分成允许和禁止操作两种工作模式。
• R：数据寻径功能集。说明互连网络中 PE 间通信所需要的各种设置模式，包括置换、广播、选播、多种循环和移数操作。

屏蔽方案

屏蔽方案将 PE 划分为允许和禁止两个子集（并集是全集），决定哪些 PE 是活动的，有地址屏蔽和数据条件屏蔽两种。

地址屏蔽方案

地址由 0，1，X 三字符组成（X 相当于通用符），由地址屏蔽字直接指出活动的 PE

数据条件屏蔽

根据 PE 中执行内容（数据而非地址）或条件进行屏蔽，直接决定 PE 的 “活动” 状态。表达式为：

表示将各 PE 中（寄存器）A 或 B 的较大者加载到 C

• 逻辑上，数据条件屏蔽能 “激活” 任意 PE 子集。
• 数据条件屏蔽语句是程序设计语言的基本部分。
• 可与地址屏蔽方式一起使用。

特点

• 以**单指令流多数据流（SIMD）**方式工作。 通过设置多个相同的处理单元来开发并行性。
• 利用并行性中的同时性，所有处理单元同时对不同的数据进行相同的操作。
• 以某一类算法为背景的专用计算机
• 互连网络设计是阵列机的重点和特点，互连网络实现处理单元间连接。
• 阵列机的研究必须与并行算法的研究密切结合，以便能充分发挥它的处理能力。
• 控制器实质上是一台标量处理机，为完成 I/O 操作以及操作系统的管理，尚需一个前端机。

实际的阵列机系统是由3部分构成的一个异构型多处理机系统。

基本结构

实例

并行算法举例

七、多处理机

多处理机的Cache一致性问题

• 允许共享数据进入 Cache，会出现多个处理器的 Cache 中都有同一存储块的副本的情况
• 当某个处理器对其 Cache 中的数据进行修改后，就会使其 Cache 中的数据与其他 Cache 中的数据不一致

Cache 一致性问题：

• 写作废、写更新
• 监听协议法
• 目录表协议