计算机体系结构

发表于 更新于 分类于 阅读数： 评论数： 本文字数： 37k 阅读时长 ≈ 1:02
北邮计算机体系结构的笔记

计算机系统结构的基础知识

计算机系统结构的定义

传统机器程序员所看到的计算机属性，即概念性结构与功能特性

广义的系统结构定义：指令系统结构、组成、硬件

Flynn分类法：按照指令流和数据流的多倍性特征对计算机系统进行分类

Handler分类法：按照并行度和流水线进行分类

Amdahl定律

加快某部件执行速度所能获得的系统性能加速比，受限于该部件的执行时间占系统中总执行时间的百分比

系统性能加速比系统性能改进后系统性能改进前总执行时间改进后总执行时间改进前

加速比依赖于两个因素

  • 可改进比例：在改进前的系统中，可改进部分的执行时间在总的执行时间中所占的比例

    • eg：一个需运行60秒的程序中有20秒的运算可以加速，那么这个比例就是20/60。

  • 部件加速比：可改进部分改进以后性能提高的倍数。它是改进前所需的执行时间与改进后执行时间的比。

    • eg：若系统改进后，可改进部分的执行时间是2秒，而改进前其执行时间为5秒，则部件加速比为5/2。

改进后程序的总执行时间

  • :改进前整个程序的执行时间

  • :不可改进比例

系统加速比为改进前与改进后总执行时间之比

例1.1

将计算机系统中某一功能的处理速度加快15倍，但该功能的处理时间仅占整个系统运行时间的40%，则采用此增强功能方法后，能使整个系统的性能提高多少？

例1.2

某计算机系统采用浮点运算部件后，使浮点运算速度提高到原来的25倍，而系统运行某一程序的整体性能提高到原来的4倍，试计算该程序中浮点操作所占的比例。

重要推论：如果只针对整个任务的一部分进行改进和优化，那么所获得的加速比不超过：

－可改进比例

CPU性能公式

执行一个程序所需的CPU时间

时间执行程序所需的时钟周期数时钟周期时间

  • 时钟周期时间是系统时钟频率的倒数。

每条指令执行的平均时钟周期数CPI

执行程序所需的时钟周期数

  • IC：所执行的指令条数

程序执行的CPU时间可以写成

时间时钟周期时间

CPU的性能取决于三个参数

  • 时钟周期时间：取决于硬件实现技术和计算机组成；

  • CPI：取决于计算机组成和指令系统的结构；

  • IC：取决于指令系统的结构和编译技术。

细化CPU性能公式

假设：计算机系统有n种指令：

：第i种指令的处理时间；

：在程序中第i种指令出现的次数；

时钟周期数

时间时钟周期时间

时钟周期数

其中：反映了第i种指令在程序中所占的比例。

例1.3

考虑条件分支指令的两种不同设计方法：

  • CPU1：通过比较指令设置条件码，然后测试条件码进行分支。

  • CPU2：在分支指令中包括比较过程。

在这两种CPU中，条件分支指令都占用2个时钟周期，而所有其它指令占用1个时钟周期。对于CPU1，执行的指令中分支指令占30%；由于每条分支指令之前都需要有比较指令，因此比较指令也占30%。由于CPU1在分支时不需要比较，因此CPU2的时钟周期时间是CPU1的1.35倍。问：哪一个CPU更快？如果CPU2的时钟周期时间只是CPU1的1.15倍，哪一个CPU更快呢？

程序的局部性原理

程序执行时所访问的存储器地址分布不是随机的，而是相对地簇聚。程序执行时间的90%都是在执行程序中10%的代码。

程序的时间局部性

程序即将用到的信息很可能就是目前正在使用的信息

程序的空间局部性

程序即将用到的信息很可能与目前正在使用的信息在空间上相邻或者临近。

计算机系统设计的主要方法

“top-down” 设计

从层次结构中的最上面一级开始，逐层往下设计各层的机器。

适合于专用机的设计，而不适合通用机的设计。

“bottom-up” 设计

从层次结构的最下面一级开始，逐层往上设计各层的机器。

采用这种方法时，软件技术完全处于被动状态，这会造成软件和硬件的脱节，使整个系统的效率降低。

“middle-out” 设计

“由上往下”和“由下往上”设计方法的主要缺点：软、硬件设计分离和脱节

解决方法：综合考虑软、硬件的分工，从中间开始设计。

“中间”：层次结构中的软硬件的交界面，目前一般是在传统机器语言机器级与操作系统机器级之间。

从中间开始设计

  • 首先要进行软、硬件功能分配，确定好这个界面。

  • 然后从这个界面开始，软件设计者开始往上设计操作系统、汇编、编译系统等，硬件设计者开始往下设计传统机器级、微程序机器级等。

计算机系统结构的发展

冯·诺依曼结构及其改进

存储程序原理的基本点：指令驱动

程序预先存放在计算机存储器中，机器一旦启动，就能按照程序指定的逻辑顺序执行这些程序，自动完成由程序所描述的处理工作。

冯·诺依曼结构的主要特点

  • 计算机以运算器为中心。

  • 在存储器中，指令和数据同等对待。

    • 指令和数据一样可以进行运算，即由指令组成的程序是可以修改的。

  • 存储器是按地址访问、按顺序线性编址的一维结构，每个单元的位数是固定的。

  • 指令的执行是顺序的。

    • 一般是按照指令在存储器中存放的顺序执行。

    • 程序的分支由转移指令实现。

    • 由指令计数器PC指明当前正在执行的指令在存储器中的地址。

  • 指令由操作码和地址码组成。

  • 指令和数据均以二进制编码表示，采用二进制运算。

软件对系统结构的影响

软件的可移植性：一个软件可以不经修改或者只需少量修改就可以由一台机器移植到另一台机器上正确地运行。差别只是执行时间的不同。我们称这两台机器是软件兼容的。

向上（下）兼容：按某档机器编制的程序，不加修改就能运行于比它高（低）档的机器。

向前（后）兼容：按某个时期投入市场的某种型号机器编制的程序，不加修改地就能运行于在它之前（后）投入市场的机器。

计算机系统结构中并行性的发展

并行性：计算机系统在同一时刻或者同一时间间隔内进行多种运算或操作。

  • 同时性：两个或两个以上的事件在同一时刻发生。

  • 并发性：两个或两个以上的事件在同一时间间隔内发生。

从处理数据的角度来看，并行性等级从低到高可分为：

  • 字串位串：每次只对一个字的一位进行处理。

  • 字串位并：同时对一个字的全部位进行处理，不同字之间是串行的。

  • 字并位串：同时对许多字的同一位（称为位片）进行处理。

  • 全并行：同时对许多字的全部位或部分位进行处理

从执行程序的角度来看，并行性等级从低到高可分为：

-指令内部并行：单条指令中各微操作之间的并行。

  • 指令级并行：并行执行两条或两条以上的指令。

  • 线程级并行：并行执行两个或两个以上的线程。通常是以一个进程内派生的多个线程为调度单位。

  • 任务级或过程级并行：并行执行两个或两个以上的过程或任务（程序段）以子程序或进程为调度单元。

  • 作业或程序级并行：并行执行两个或两个以上的作业或程序。

提高并行性的技术途径

  • 时间重叠

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

  • 资源重复

    • 引入空间因素，以数量取胜。通过重复设置硬件资源，大幅度地提高计算机系统的性能。

  • 资源共享

    • 这是一种软件方法，它使多个任务按一定时间顺序轮流使用同一套硬件设备。

指令结构的设计

指令系统结构的分类

通用寄存器型结构进一步细分为3种类型

  • 寄存器－寄存器型（RR型）

  • 寄存器－存储器型（RM型）

  • 存储器－存储器型（MM型）

寻址方式

一些操作数寻址方式

<-：赋值操作

Mem：存储器

Regs：寄存器组

方括号：表示内容

Mem[ ]：存储器的内容

Regs[ ]：寄存器的内容

Mem[Regs[R1]]：以寄存器R1中的内容作为地址的存储器单元中的内容

寻址方式实例

寻址方式指令实例含义
寄存器寻址ADD R1,R2Regs[R1]←Regs[R1]＋Regs[R2]
立即值寻址ADD R3,#6Regs[R3]←Regs[R3]＋6
偏移寻址ADD R3,120(R2)Regs[R3]←Regs[R3]＋Mem[120+Regs[R2]]
寄存器间接寻址ADD R4,(R2)Regs[R4]←Regs[R4]＋Mem[Regs[R2]]
索引寻址ADD R4,(R2+R3)Regs[R4]←Regs[R4]＋Mem[Regs[R2]+Regs[R3]]
直接寻址或绝对寻址ADD R4,(1010)Regs[R4]←Regs[R4]＋Mem[1010]
存储器间接寻址ADD R2,@(R4)Regs[R2]←Regs[R2]＋Mem[Mem[Regs[R4]]]
自增寻址ADD R1,(R2)+Regs[R1]←Regs[R1]＋Mem[Regs[R2]]
Regs[R2]←Regs[R2]＋d
自减寻址ADD R1,-(R2)Regs[R2]←Regs[R2]－d
Regs[R1]←Regs[R1]+Mem[Regs[R2]]
缩放寻址ADD R1,80(R2)[R3]Regs[R1]←Regs[R1]＋Mem[80＋Regs[R2]＋Regs[R3]*d]

两种表示寻址方式的方法

将寻址方式编码于操作码中，由操作码描述相应操作的寻址方式。

  • 适合：处理机采用load-store结构，寻址方式只有很少几种。

在指令字中设置专门的寻址字段，用以直接指出寻址方式。

  • 适合：处理机具有多种寻址方式，且指令有多个操作数。

指令系统的设计与优化

对指令系统的基本要求

完整性：在一个有限可用的存储空间内，对于任何可解的问题，编制计算程序时，指令系统所提供的指令足够使用。

规整性：主要包括对称性和均匀性。

  • 对称性：所有与指令系统有关的存储单元的使用、操作码的设置等都是对称的。

    • 在存储单元的使用上，所有通用寄存器都要同等对待。在操作码的设置上，如果设置了A－B的指令，就应该也设置B－A的指令。

  • 均匀性：指对于各种不同的操作数类型、字长、操作种类和数据存储单元，指令的设置都要同等对待。

    • 如果某机器有5种数据表示，4种字长，两种存储单元，则要设置5×4×2=40种同一操作的指令。

正交性：在指令中各个不同含义的字段，如操作类型、数据类型、寻址方式字段等，在编码时应互不相关、相互独立。

高效率：指指令的执行速度快、使用频度高。

兼容性：主要是要实现向后兼容，指令系统可以增加新指令，但不能删除指令或更改指令的功能。

分支条件的方法及其优缺点

名称检测分支条件的方法优点缺点
条件码检测由ALU操作设置的一些特殊的位（即CC）可以自由设置分支条件条件码是增设的状态。而且它限制了指令的执行顺序，因为要保证条件码能顺利地传送给分支指令。
条件寄存器比较指令把比较结果放入任何一个寄存器，检测时就检测该寄存器。简单占用了一个寄存器
比较与分支比较操作是分支指令的一部分，通常这种比较是受到一定限制的。用一条指令（而不是两条）就能实现分支当采用流水方式时，该指令的操作可能太多，在一拍内做不完。

指令操作码的优化

哈夫曼编码

基本思想

当各种事件发生的概率不均等时，可以对发生概率最高的事件用最短的位数（时间）来表示（处理），而对于出现概率较低的事件，则可以用较长的位数（时间）来表示（处理），从而使总的平均位数（时间）缩短。

构造哈夫曼树

将各事件按其使用频度从小到大依次排列;

每次从中选择两个频度值最小的结点，将其合并成一个新的结点，并把新结点画在所选结点的上面，然后用两条边把新结点分别与那两个结点相连。

  • 新结点的频度值是所选两个结点的频度值的和。

把新结点与其他剩余未结合的结点一起，再以上面的步骤进行处理，反复进行，直到全部结点都结合完毕、形成根结点为止。

操作码优化的程度可以用信息熵来衡量。

表示用二进制编码表示n个码点时，理论上的最短平均编码长度。

优缺点：可以减少操作码的平均位数，但所获得的编码是变长度的，不规整，不利于硬件处理。

等长扩展码

为了便于分级译码，一般都采用等长扩展码

定长操作码

固定长度的操作码：所有指令的操作码都是同一的长度（如8位）。

保证操作码的译码速度、减少译码的复杂度。

以程序的存储空间为代价来换取硬件实现上的好处。

指令字格式的优化

如果指令字的宽度固定，地址码的长度和个数固定，则操作码的缩短并不能带来好处，只是使指令字中出现空白浪费。

采用地址个数可变和/或地址码长度可变的方案

利用操作码缩短所带来的好处

最常用的操作码最短，其地址字段个数最多。

指令系统的3种编码格式

可变长度编码格式

当指令系统的寻址方式和操作种类很多时，这种编码格式是最好的。

用最少的二进制位来表示目标代码。

可能会使各条指令的字长和执行时间相差很大。

固定长度编码格式

将操作类型和寻址方式一起编码到操作码中。

当寻址方式和操作类型非常少时，这种编码格式非常好。

可以有效地降低译码的复杂度，提高译码的速度。

大部分RISC的指令系统均采用这种编码格式。

混合型编码格式

提供若干种固定的指令字长。

以期达到既能够减少目标代码长度又能降低译码复杂度的目标。

MIPS指令系统结构

MIPS的指令格式

寻址方式编码到操作码中

所有的指令都是32位的

操作码占6位

I类指令

包括所有的load和store指令，立即数指令，分支指令，寄存器跳转指令，寄存器链接跳转指令。

立即数字段为16位，用于提供立即数或偏移量。

load指令

   访存有效地址：Regs[rs]＋immediate

   从存储器取来的数据放入寄存器rt

store指令

   访存有效地址：Regs[rs]＋immediate

   要存入存储器的数据放在寄存器rt中

立即数指令

   Regs[rt] ← Regs[rs] op immediate

分支指令

   转移目标地址：Regs[rs]＋immediate，rt无用

寄存器跳转、寄存器跳转并链接

   转移目标地址为Regs[rs]

R类指令

包括ALU指令，专用寄存器读/写指令，move指令等。

ALU指令

  Regs[rd]← Regs[rs] funct Regs[rt]
  funct为具体的运算操作编码

J类指令

包括跳转指令，跳转并链接指令，自陷指令，异常返回指令。

在这类指令中，指令字的低26位是偏移量，它与PC值相加形成跳转的地址。

MIPS操作

:从y传送n位到x

: 把z传送到x和y

下标：表示字段中具体的位；

Mem：表示主存；

上标：用于表示对字段进行复制的次数。

符号##：用于两个字段的拼接，并且可以出现在数据传送的任何一边。

例如：

表示：以R6的内容作为地址访问内存，得到的字节按符号位扩展为32位后存入R8的低32位，R8的高32位（即Regs[R8]0-31）不变。

流水线技术

流水线的基本概念

把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。

把多个处理过程在时间上错开，依次通过各功能段，这样，每个子过程就可以与其它的子过程并行进行。

流水线中的每个子过程及其功能部件称为流水线的级或段，段与段相互连接形成流水线。流水线的段数称为流水线的深度。

把指令的解释过程分解为分析和执行两个子过程，并让这两个子过程分别用独立的分析部件和执行部件来实现。在理想情况下速度提高一倍

把流水线技术应用于运算的执行过程，就形成了运算操作流水线，也称为部件级流水线。

把浮点加法的全过程分解为求阶差、对阶、尾数加、规格化四个子过程。理想情况下速度提高3倍

时－空图从时间和空间两个方面描述了流水线的工作过程。时－空图中，横坐标代表时间，纵坐标代表流水线的各个段。

流水技术的特点

流水线把一个处理过程分解为若干个子过程（段），每个子过程由一个专门的功能部件来实现。

流水线中各段的时间应尽可能相等，否则将引起流水线堵塞、断流。

流水线每一个段的后面都要有一个缓冲寄存器（锁存器），称为流水寄存器。

  • 作用：在相邻的两段之间传送数据，以保证提供后面要用到的信息，并把各段的处理工作相互隔离。

流水技术适合于大量重复的时序过程，只有在输入端不断地提供任务，才能充分发挥流水线的效率。

流水线需要有通过时间和排空时间。

  • 通过时间：第一个任务从进入流水线到流出结果所需的时间

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

流水线的分类

部件级、处理机级及处理机间流水线

部件级流水线（运算操作流水线）：把处理机中的部件分段，再把这些分段相互连接起来，使得各种类型的运算操作能够按流水方式进行。

处理机级流水线（指令流水线）：把指令的执行过程按照流水方式处理。把一条指令的执行过程分解为若干个子过程，每个子过程在独立的功能部件中执行。

系统级流水线（宏流水线）：把多台处理机串行连接起来，对同一数据流进行处理，每个处理机完成整个任务中的一部分。

单功能流水线与多功能流水线

单功能流水线：只能完成一种固定功能的流水线。

多功能流水线：流水线的各段可以进行不同的连接，以实现不同的功能。

静态流水线与动态流水线

静态流水线：在同一时间内，多功能流水线中的各段只能按同一种功能的连接方式工作。

  • 对于静态流水线来说，只有当输入的是一串相同的运算任务时，流水的效率才能得到充分的发挥。

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

线性流水线与非线性流水线

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

非线性流水线：流水线中除了有串行的连接外，还有反馈回路。

顺序流水线与乱序流水线

顺序流水线：流水线输出端任务流出的顺序与输入端任务流入的顺序完全相同。每一个任务在流水线的各段中是一个跟着一个顺序流动的。

乱序流水线：流水线输出端任务流出的顺序与输入端任务流入的顺序可以不同，允许后进入流水线的任务先完成（从输出端流出）。

标量处理机与向量流水处理机

标量处理机：处理机不具有向量数据表示和向量指令，仅对标量数据进行流水处理。

向量流水处理机：具有向量数据表示和向量指令的处理机。

流水线的性能指标

吞吐率：在单位时间内流水线所完成的任务数量或输出结果的数量。

n：任务数

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

各段时间均相等的k段流水线

流水线的实际吞吐率小于最大吞吐率，它除了与每个段的时间有关外，还与流水线的段数k以及输入到流水线中的任务数n等有关。

各段时间不完全相等的流水线

(为第i段的时间，共有k个段)

解决流水线瓶颈问题的常用方法

细分瓶颈段

重复设置瓶颈段

流水线的加速比

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

流水线各段时间相等

一条k段流水线完成n个连续任务所需要的时间为：

顺序执行n个任务所需要的时间为：

流水线的实际加速比为：

最大加速比:

流水线的各段时间不完全相等时

流水线的效率

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

各段时间相等

整条流水线的效率为

从时空图上看个任务实际占用的时空区段总时空区

流水线的性能分析举例

设在下图所示的静态流水线上计算：

流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中，试计算其吞吐率、加速比和效率。

时空图

在求解此问题时，该流水线的效率不高,因为

  • 多功能流水线在做某一种运算时，总有一些段是空闲的；

  • 静态流水线在进行功能切换时，要等前一种运算全部流出流水线后才能进行后面的运算；

  • 运算之间存在关联，后面有些运算要用到前面运算的结果；

  • 流水线的工作过程有建立与排空部分。

流水线的相关与冲突

对于一段经典的5段RISC流水线，一条指令的执行过程分为以下五个周期

  • 取指令周期(IF)

    • 以程序计数器PC中的内容作为地址，从存储器中取出指令并放入指令寄存器IR；

    • 同时PC值加4（假设每条指令占4个字节），指向顺序的下一条指令。

  • 指令译码/读寄存器周期(ID)

    • 对指令进行译码，并用IR中的寄存器地址去访问通用寄存器组，读出所需的操作数。

  • 执行/有效地址计算周期(EX)

    • load和store指令：ALU把指令中所指定的寄存器的内容与偏移量相加，形成访存有效地址。

    • 寄存器－寄存器ALU指令：ALU按照操作码指定的操作对从通用寄存器组中读出的数据进行运算。

    • 寄存器－立即数ALU指令：ALU按照操作码指定的操作对从通用寄存器组中读出的操作数和指令中给出的立即数进行运算。

    • 分支指令：ALU把指令中给出的偏移量与PC值相加，形成转移目标的地址。同时，对在前一个周期读出的操作数进行判断，确定分支是否成功。

  • 存储器访问／分支完成周期(MEM)

    • load指令：用上一个周期计算出的有效地址从存储器中读出相应的数据；

    • store指令：把指定的数据写入这个有效地址所指出的存储器单元。

    • 分支指令：分支“成功”，就把转移目标地址送入PC。分支指令执行完成。

  • 写回周期(WB)

    • ALU运算指令和load指令在这个周期把结果数据写入通用寄存器组。

流水线方式需要解决的问题

要保证不会在同一时钟周期要求同一个功能段做两件不同的工作。

  • eg:不能要求ALU同时做有效地址计算和算术运算。

避免IF段的访存（取指令）与MEM段的访存（读/写数据）发生冲突。

  • 可以采用分离的指令存储器和数据存储器；

  • 一般采用分离的指令Cache和数据Cache。

ID段和WB段都要访问同一寄存器文件。

  • 把写操作安排在时钟周期的前半拍完成，把读操作安排在后半拍完成。

考虑PC的问题

  • 流水线为了能够每个时钟周期启动一条新的指令，就必须在每个时钟周期进行PC值的加4操作，并保留新的PC值。这种操作必须在IF段完成，以便为取下一条指令做好准备。（需设置一个专门的加法器）

相关

相关：两条指令之间存在某种依赖关系。

如果两条指令相关，则它们就有可能不能在流水线中重叠执行或者只能部分重叠执行。

数据相关

对于两条指令i（在前，下同）和j（在后，下同），如果下述条件之一成立，则称指令j与指令i数据相关。

  • 指令j使用指令i产生的结果；

  • 指令j与指令k数据相关，而指令k又与指令i数据相关。

数据相关具有传递性。

名相关

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

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

指令j与指令i之间的名相关有两种：

  • 反相关：如果指令j写的名与指令i读的名相同，则称指令i和j发生了反相关。

    • 指令j写的名＝指令i读的名

  • 输出相关：如果指令j和指令i写相同的名，则称指令i和j发生了输出相关。

    • 指令j写的名＝指令i写的名

换名技术：通过改变指令中操作数的名来消除名相关。

1
2
3
DIV.D F2，F8，F4
ADD.D F8，F0，F12
SUB.D F10，F8，F14

进行寄存器换名（F8换成S）后，变成：

1
2
3
DIV.D F2，F8，F4
ADD.D S，F0，F12
SUB.D F10，S，F14

流水线冲突

流水线冲突是指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。

结构冲突

因硬件资源满足不了指令重叠执行的要求而发生的冲突。

常见的导致结构冲突的原因

  • 功能部件不是完全流水

  • 资源份数不够

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

解决办法Ⅰ：插入暂停周期

解决方法Ⅱ：设置相互独立的指令存储器和数据存储器或设置相互独立的指令Cache和数据Cache。

数据冲突

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

考虑两条指令i和j ，且i在j之前进入流水线，可能发生的数据冲突有

  • 写后读冲突（RAW）：在 i 写入之前，j 先去读。j 读出的内容是错误的。

  • 写后写冲突（WAW）：在 i 写入之前，j 先写。最后写入的结果是 i 的。错误！这种冲突对应于输出相关。

  • 读后写冲突（WAR）：在 i 读之前，j 先写。i 读出的内容是错误的！由反相关引起。

对于寄存器堆的操作，采用前半周期写入，后半周期读取

通过定向技术减少数据冲突引起的停顿

关键思想：在计算结果尚未出来之前，后面等待使用该结果的指令并不真正立即需要该计算结果，如果能够将该计算结果从其产生的地方直接送到其它指令需要它的地方，那么就可以避免停顿。

定向的实现

  • EX段和MEM段之间的流水寄存器中保存的ALU运算结果总是回送到ALU的入口。

  • 当定向硬件检测到前一个ALU运算结果写入的寄存器就是当前ALU操作的源寄存器时，那么控制逻辑就选择定向的数据作为ALU的输入，而不采用从通用寄存器组读出的数据。

依靠编译器解决数据冲突

让编译器重新组织指令顺序来消除冲突，这种技术称为指令调度或流水线调度

控制冲突

执行分支指令的结果有两种

  • 分支成功：PC值改变为分支转移的目标地址。在条件判定和转移地址计算都完成后，才改变PC值。

  • 不成功或者失败：PC的值保持正常递增，指向顺序的下一条指令。

处理分支指令最简单的方法：“冻结”或者“排空”流水线

前述5段流水线中，改变PC值是在MEM段进行的。给流水线带来了3个时钟周期的延迟

时钟周期IFIDEXMEMWB
分支指令IFIDEXMEMWB
分支目标指令IFstallstallIFIDEXMEMWB
分支目标指令+1IFIDEXMEM
分支目标指令+2IFIDEX
分支目标指令+3IFID

可采取两种措施来减少分支延迟。

在流水线中尽早判断出分支转移是否成功；

尽早计算出分支目标地址。

下面的讨论中，我们假设：这两步工作被提前到ID段完成，即分支指令是在ID段的末尾执行完成，所带来的分支延迟为一个时钟周期。

预测分支失败

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

若确定分支失败，将分支指令看作是一条普通指令，流水线正常流动；

若确定分支成功，流水线就把在分支指令之后取出的所有指令转化为空操作，并按分支目地重新取指令执行。

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

预测分支成功

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

起作用的前题：先知道分支目标地址，后知道分支是否成功。前述5段流水线中，这种方法没有任何好处。

延迟分支

从逻辑上“延长”分支指令的执行时间。把延迟分支看成是由原来的分支指令和若干个延迟槽构成，不管分支是否成功，都要按顺序执行延迟槽中的指令。

分支延迟指令的调度

任务：在延迟槽中放入有用的指令

由编译器完成。能否带来好处取决于编译器能否把有用的指令调度到延迟槽中。

调度策略要求什么情况下起作用？
从前调度被调度的指令必须与分支无关任何情况
从目标处调度必须保证在分支失败时执行被调度的指令不会导致错误。有可能需要复制指令。分支成功时(但由于复制指令，有可能会增大程序空间)
从失败处调度必须保证在分支成功时执行被调度的指令不会导致错误。分支失败时

进一步改进：分支取消机制（取消分支）

当分支的实际执行方向和事先所预测的一样时，执行分支延迟槽中的指令，否则就将分支延迟槽中的指令转化成一个空操作。

向量处理机

向量的处理方式

以计算表达式D=A*(B-C)为例，A、B、C、D 是长度为 N 的向量

横向(水平)处理方式

向量计算是按行的方式从左到右横向地进行，组成循环程序进行处理


存在N次数据相关，功能切换2N次

纵向(垂直)处理方式

向量计算是按列的方式从上到下纵向地进行

先计算

再计算

存在1次数据相关，功能切换1次

纵横(分组)处理方式

又称为分组处理方式,把向量分成若干组，组内按纵向方式处理，依次处理各组。

对于上述的例子，设：N=S*n+r

其中N为向量长度，S为组数，n为每组的长度，r为余数。

若余下的r个数也作为一组处理，则共有S+1组。

运算过程为：

  • 先算第1组：

  • 再算第二组

  • 依次进行下去，直到最后一组：第S+1组。

  • 每组内各用两条向量指令。

数据相关：1次，功能切换：2次

向量处理机的结构

有两种典型的结构：存储器-存储器型结构和寄存器-寄存器型结构

“存储器-存储器”结构

采用纵向处理方式，向量指令的源向量和目的向量都是存放在存储器中，运算的中间结果需要送回存储器。流水线运算部件的输入和输出端都直接（或经过缓冲器）与存储器相联，从而构成存储器-存储器型操作的运算流水线。

要充分发挥这种结构的流水线效率，存储器要不断地提供源操作数，并不断地从运算部件接收结果。

（每拍从存储器读取两个数据，并向存储器写回一个结果）

对存储器的带宽以及存储器与处理部件的通信带宽提出了非常高的要求。解决方法：一般是通过采用多体交叉并行存储器和缓冲器技术。

“寄存器-寄存器”结构

在向量的分组处理方式中，对向量长度N没有限制，但组的长度n却是固定不变的。

对处理机结构的要求：寄存器－寄存器结构

设置能快速访问的向量寄存器，用于存放源向量、目的向量及中间结果。让运算部件的输入、输出端都与向量寄存器相联，就构成了“寄存器－寄存器”型操作的运算流水线。

CRAY-1的基本结构

共有12条可并行工作的单功能流水线，可分别流水地进行地址、向量、标量的各种运算。

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

  • 整数加（3拍）

  • 逻辑运算（2拍）

  • 移位（4拍）

  • 浮点加（6拍）

  • 浮点乘（7拍）

  • 浮点迭代求倒数（14拍）

括号中的数字为其流水经过的时间，每拍为一个时钟周期，即12.5ns。

向量寄存组V

  • 由512个64位的寄存器组成，分成8块。

  • 编号：V0～V7

  • 每一个块称为一个向量寄存器，可存放一个长度（即元素个数）不超过64的向量。

  • 每个向量寄存器可以每拍向功能部件提供一个数据元素，或者每拍接收一个从功能部件来的结果元素。

  • 标量寄存器S和快速暂存器T

  • 标量寄存器有8个：S0～S7 64位

  • 快速暂存器T用于在标量寄存器和存储器之间提供缓冲。

向量屏蔽寄存器VM

  • 64位，每一位对应于向量寄存器的一个单元。

  • 作用：用于向量的归并、压缩、还原和测试操作、对向量某些元素的单独运算等。

CRAY-1向量处理的一个显著特点

每个向量寄存器都有连到6个向量功能部件的单独总线。

每个向量功能部件也都有把运算结果送回向量寄存器组的总线。

只要不出现冲突和功能部件冲突，各之间和各功能部件之间都能并行工作，大大加快了向量指令的处理。

冲突：并行工作的各向量指令的源向量或结果向量使用了相同的。

例如：源向量相同


功能部件冲突：并行工作的各向量指令要使用同一个功能部件。

例如：都需使用乘法功能部件


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

设置多个功能部件，使它们并行工作

设置多个独立的功能部件。这些部件能并行工作，并各自按流水方式工作，从而形成了多条并行工作的运算操作流水线。

例如：CRAY-1向量处理机有4组12个单功能流水部件：

  • 向量部件：向量加，移位，逻辑运算

  • 浮点部件：浮点加，浮点乘，浮点求倒数

  • 标量部件：标量加，移位，逻辑运算，数“1”/计数

  • 地址运算部件：整数加，整数乘

采用链接技术，加快一串向量指令的执行

占用功能流水线和向量寄存器的4种情况

  • 指令不相关


这两条指令分别使用各自所需的流水线和向量寄存器，可以并行执行。

  • 功能部件冲突


这两条指令都要使用加法流水线，发生了功能部件冲突（但向量寄存器不冲突）。当第一条指令流出时，占用加法流水线。第二条指令要等加法流水线变成空闲后，才能流出。

  • 源寄存器冲突


这两条向量指令的源向量之一都取自V1。由于两者的首元素下标可能不同，向量长度也可能不同，所以难以由V1同时提供两条指令所需要的源向量。这两条向量指令不能同时执行。只有等第一条向量指令执行完、释放V1之后，第二条向量指令才能开始执行。

  • 结果寄存器冲突


这两条指令都要访问目的寄存器V4。由于第一条指令在先，所以它先占用V4直到运算完成，然后再流出后一条指令。

当前一条指令的结果寄存器是后一条指令的源寄存器、且不存在任何其他冲突时，就可以用链接技术来提高性能。


向量流水线链接：具有先写后读相关的两条指令，在不出现功能部件冲突和源向量冲突的情况下，可以把功能部件链接起来进行流水处理，以达到加快执行的目的。

链接时，Cray-1中把向量数据元素送往向量功能部件以及把结果存入向量寄存器都需要一拍时间，从存储器中把数据送入访存功能部件也需要一拍时间。

进行向量链接的要求:

保证：无向量寄存器使用冲突和无功能部件使用冲突

只有在前一条指令的第一个结果元素送入结果向量寄存器的那一个时钟周期才可以进行链接。

当一条向量指令的两个源操作数分别是两条先行指令的结果寄存器时，要求先行的两条指令产生运算结果的时间必须相等，即要求有关功能部件的通过时间相等。

要进行链接执行的向量指令的向量长度必须相等，否则无法进行链接。

采用循环开采技术，加快循环的处理；

当向量的长度大于向量寄存器的长度时，必须把长向量分成长度固定的段，然后循环分段处理，每一次循环只处理一个向量段。

采用多处理机系统，进一步提高性能。

许多新型向量处理机系统采用了多处理机系统结构。例如：

  • CRAY-2

    • 包含了4个向量处理机

    • 浮点运算速度最高可达1800MFLOPS

  • CRAY Y-MP、C90:最多可包含16个向量处理机

向量处理机的性能评价

执行一条向量长度为n的向量指令所需的时间为:

:向量处理部件流水线的建立时间,为了使处理部件流水线能开始工作（即开始流入数据）所需要的准备时间。

:向量流水线的通过时间,第一对向量元素通过流水线并产生第一个结果所花的时间

:流水线的时钟周期时间

对于一组向量指令而言，其执行时间主要取决于三个因素：

  • 向量的长度

  • 向量操作之间是否存在流水功能部件的使用冲突

  • 数据的相关性

把能在同一个时钟周期内一起开始执行的几条向量指令称为一个编队。

分段开采时一组向量指令的总执行时间

当向量长度n大于向量寄存器长度MVL时，需要分段开采。

引入一些额外的处理操作

（假设：这些操作所引入的额外时间为个时钟周期）

对于最后一次循环来说，所需要的时间为：

其他的每一次循环所要花费的时间为:

总的执行时间为：

指令级并行及其开发——硬件方法

指令级并行的概念

开发ILP的方法可以分为两大类

  • 主要基于硬件的动态开发方法

  • 基于软件的静态开发方法

流水线处理机的实际CPI

理想流水线的CPI加上各类停顿的时钟周期数：

流水线理想停顿结构冲突停顿数据冲突停顿控制冲突

理想CPI是衡量流水线最高性能的一个指标。

基本程序块

  • 基本程序块：一串连续的代码除了入口和出口以外，没有其他的分支指令和转入点 。

  • 程序平均每4～7条指令就会有一个分支。

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

开发循环的不同叠代之间存在的并行性，是指令级并行研究的重点之一

最基本的开发循环级并行的技术

  • 循环展开（loop unrolling）技术

  • 采用向量指令和向量数据表示

指令的动态调度

静态调度

  • 依靠编译器对代码进行静态调度，以减少相关和冲突。

  • 它不是在程序执行的过程中、而是在编译期间进行代码调度和优化。

  • 通过把相关的指令拉开距离来减少可能产生的停顿。

动态调度

  • 在程序的执行过程中，依靠专门硬件对代码进行调度，减少数据相关导致的停顿。

  • 优点：

    • 能够处理一些在编译时情况不明的相关（比如涉及到存储器访问的相关），并简化了编译器；

    • 能够使本来是面向某一流水线优化编译的代码在其它的流水线（动态调度）上也能高效地执行。

以硬件复杂性的显著增加为代价

动态调度的基本思想

到目前为止我们所使用流水线的最大的局限性:

指令是按序流出和按序执行的

考虑下面一段代码：

1
2
3
DIV.D F4， F0，F2
ADD.D F10，F4，F6
SUB.D F12，F6，F14

ADD.D指令与DIV.D指令关于F4相关，导致流水线停顿。

SUB.D指令与流水线中的任何指令都没有关系，但也因此受阻。

在前面的基本流水线中：检测结构冲突,检测数据冲突,一旦一条指令受阻，其后的指令都将停顿。

为了使上述指令序列中的SUB.D指令能继续执行下去，必须把指令流出的工作拆分为两步：

  • 检测结构冲突

  • 等待数据冲突消失

只要检测到没有结构冲突，就可以让指令流出。并且流出后的指令一旦其操作数就绪就可以立即执行。

乱序执行

  • 指令的执行顺序与程序顺序不相同

  • 指令的完成也是乱序完成的：即指令的完成顺序与程序顺序不相同。

为了支持乱序执行，我们将5段流水线的译码阶段再分为两个阶段：

  • 流出：指令译码，检查是否存在

  • 读操作数：等待数据冲突消失，然后读操作数。

在前述5段流水线中，是不会发生WAR冲突和WAW冲突的。但乱序执行就使得它们可能发生了。

动态调度的流水线支持多条指令同时处于执行当中。

要求：具有多个功能部件、或者功能部件流水化、或者兼而有之。

指令乱序完成带来的最大问题：异常处理比较复杂

记分牌动态调度算法

基本思想

  • CDC 6600计算机最早采用此功能

    • 该机器用一个称为记分牌的硬件实现了对指令的动态调度。该硬件中维护着3张表，分别用于记录指令的执行状态、功能部件状态、寄存器状态以及数据相关关系等。它把前述5段流水线中的译码段ID分解成了两个段：流出和读操作数，以避免当某条指令在ID段被停顿时挡住后面无关指令的流动。

  • 记分牌的目标：在没有结构冲突时，尽可能早地执行没有数据冲突的指令，实现每个时钟周期执行一条指令。

  • 要发挥指令乱序执行的好处，必须有多条指令同时处于执行阶段。

基本结构

采用了记分牌的MIPS处理器的基本结构，每条指令都要经过记分牌。记分牌负责相关检测并控制指令的流出和执行。

每条指令的执行过程分为4段

  1. 流出：如果当前流出指令所需的功能部件空闲，并且所有其他正在执行的指令的目的寄存器与该指令的不同，记分牌就向功能部件流出该指令，并修改记分牌内部的记录表。解决了WAW冲突

  2. 读操作数：记分牌监测源操作数的可用性，如果数据可用，它就通知功能部件从寄存器中读出源操作数并开始执行。动态地解决了RAW冲突，并导致指令可能乱序开始执行。

  3. 执行：取到操作数后，功能部件开始执行。当产生出结果后，就通知记分牌它已经完成执行。在浮点流水线中，这一段可能要占用多个时钟周期。

  4. 写结果：记分牌一旦知道执行部件完成了执行，就检测是否存在WAR冲突。如果不存在，或者原有的WAR冲突已消失，记分牌就通知功能部件把结果写入目的寄存器，并释放该指令使用的所有资源

记分牌中记录的信息由3部分构成

  • 指令状态表：记录正在执行的各条指令已经进入到了哪一段。

  • 功能部件状态表：记录各个功能部件的状态。每个功能部件有一项，每一项由以下9个字段组成：

    • Busy：忙标志，指出功能部件是否忙。初值为“no”；

    • Op：该功能部件正在执行或将要执行的操作；

    • Fi：目的寄存器编号；

    • Fj，Fk：源寄存器编号；

    • Qj，Qk：指出向源寄存器Fj、Fk写数据的功能部件 ；

    • Rj，Rk：标志位，为“yes”表示Fj，Fk中的操作数就绪且还未被取走。否则就被置为“no”。

  • 结果寄存器状态表Result：每个寄存器在该表中有一项，用于指出哪个功能部件（编号）将把结果写入该寄存器。

    • 如果当前正在运行的指令都不以它为目的寄存器，则其相应项置为“no”。

    • Result各项的初值为“no”（全0）。

示例

对于以下这段代码

1
2
3
4
5
6
L.D      F6, 34(R2)
L.D      F2, 45(R3)
MULT.D   F0, F2, F4
SUB.D    F8, F6, F2
DIV.D    F10, F0, F6
ADD.D    F6, F8, F2

假设浮点流水线中各部件的延迟如下：

  • 加法需2个时钟周期

  • 乘法需10个时钟周期

  • 除法需40个时钟周期

代码段和记分牌信息的起始点状态如上图。分别给出MULT.D和DIV.D准备写结果之前的记分牌状态。

Solution:

第二个周期，L.D F2, 45(R3)执行到写结果状态，需要将功能状态部件表更新如下

由于已经写完，操作数来源已经不是Integer，所以需要更新Qj和Qk，

第三个周期，由于F2终于占用结束，MULT.D F0, F2, F4和SUB.D F8, F6, F2进入读操作数阶段，需要将功能状态部件表更新如下

由于加法器占用2个时钟周期，第四个周期和第五个周期用于SUB.D F8, F6, F2的执行阶段，需要将功能状态部件表更新如下

第六个周期，用于SUB.D F8, F6, F2的写结果阶段，同时由于加法器被释放，所以ADD.D F6, F8, F2可以被流入，需要将功能状态部件表更新如下

第7个周期，用于ADD.D F6, F8, F2的读操作数阶段，需要将功能状态部件表更新如下

由于加法器占用2个时钟周期，第八个周期和第九个周期用于ADD.D F6, F8, F2的执行阶段，需要将功能状态部件表更新如下

第十个周期本应用于ADD.D F6, F8, F2的写结果阶段，但是ADD.D F6, F8, F2和DIV.D F10, F0, F6存在WAR相关，所以被卡在写结果阶段。从第十个周期到第十三个周期均用于执行MULT.D F0, F2, F4，由于DIV.D F10, F0, F6需要更新后的F0，所以一直处于流出阶段，需要将功能状态部件表更新如下

指令状态表如下

结果状态寄存器表如下

第十四个周期用于MULT.D F0, F2, F4的写结果阶段，同时DIV.D F10, F0, F6可以进入读操作数阶段,读完操作数后ADD.D F6, F8, F2可以执行写结果阶段,需要将功能状态部件表更新如下

从第十五个周期到第五十五个周期均是除法器的执行阶段，因此三个表状态如下

具体算法

FU：表示当前指令所要用的功能部件；

D：目的寄存器的名称；

S1、S2：源操作数寄存器的名称；

Op：要进行的操作；

Fj[FU]：功能部件FU的Fj字段（其他字段依此类推）；

Result[D]：结果寄存器状态表中与寄存器D相对应的内容。其中存放的是将把结果写入寄存器D的功能部件的名称。

指令流出阶段

功能部件空闲且没有写后写（WAW）冲突

  • 把当前指令的相关信息填入功能部件状态表，

  • 记录操作码

  • 记录目的寄存器编号

  • 记录第一个源寄存器编号

  • 记录第二个源寄存器编号

  • 记录将产生第一个源操作数的部件

  • 记录将产生第二个源操作数的部件

  • 置第一个源操作数是否可用的标志(如果Qj[FU]为“no”，就表示没有操作部件要写S1，数据可用。置Rj[FU]为“yes”。否则置Rj[FU]为“no”)

  • 置第二个源操作数是否可用的标志

  • D是当前指令的目的寄存器。功能部件FU将把结果写入D

读操作数阶段

两个源操作数都已就绪

  • 已经读走了就绪的第一个源操作数()。

  • 已经读走了就绪的第二个源操作数()。

  • 不再等待其他FU的计算结果(；；)。

执行阶段

功能部件操作结束

写结果阶段

不存在WAR冲突

  • 如果有指令在等待该结果（作为第一源操作数），则将其Rj置为“yes”，表示数据可用

  • 如果有指令在等待该结果（作为第二源操作数），则将其Rk置为“yes”，表示数据可用。

  • 释放目的寄存器Fi[FU]

  • 释放功能部件FU

Tomasulo动态调度算法

核心思想

记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减少到最小；

通过寄存器换名来消除WAR冲突和WAW冲突。

基本结构

保留站

每个保留站中保存一条已经流出并等待到本功能部件执行的指令（相关信息）。

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

  • 在一条指令流出到保留站的时候，如果该指令的源操作数已经在寄存器中就绪，则将之取到该保留站中。

  • 如果操作数还没有计算出来，则在该保留站中记录将产生这个操作数的保留站的标识。

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

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

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

公共数据总线CDB

（一条重要的数据通路）

  • 所有功能部件的计算结果都是送到CDB上，由它把这些结果直接送到（播送到）各个需要该结果的地方。

  • 在具有多个执行部件且采用多流出（即每个时钟周期流出多条指令）的流水线中，需要采用多条CDB。

load缓冲器和store缓冲器

  • 存放读/写存储器的数据或地址

  • load缓冲器的作用有3个

    • 存放用于计算有效地址的分量；

    • 记录正在进行的load访存，等待存储器的响应；

    • 保存已经完成了的load的结果（即从存储器取来的数据），等待CDB传输。

  • store缓冲器的作用有3个

    • 存放用于计算有效地址的分量；

    • 保存正在进行的store访存的目标地址，该store正在等待存储数据的到达；

    • 保存该store的地址和数据，直到存储部件接收。

浮点寄存器FP

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

  • 它们通过一对总线连接到功能部件，并通过CDB连接到store缓冲器。

指令队列

  • 指令部件送来的指令放入指令队列

  • 指令队列中的指令按先进先出的顺序流出

运算部件

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

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

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

  • 当指令流出时，如果其操作数还没有计算出来，则将该指令中相应的寄存器号换名为将产生这个操作数的保留站的标识。

  • 指令流出到保留站后，其操作数寄存器号或者换成了数据本身（如果该数据已经就绪），或者换成了保留站的标识，不再与寄存器有关系。

每个保留站有以下7个字段：

  • Op：要对源操作数进行的操作

  • Qj，Qk：将产生源操作数的保留站号

    • 等于0表示操作数已经就绪且在Vj或Vk中，或者不需要操作数。

  • Vj，Vk：源操作数的值

    • 对于每一个操作数来说，V或Q字段只有一个有效。

    • 对于load来说，Vk字段用于保存偏移量。

  • Busy：为“yes”表示本保留站或缓冲单元“忙”

  • A：仅load和store缓冲器有该字段。开始是存放指令中的立即数字段，地址计算后存放有效地址。

示例1

对于下述指令序列，在给定时刻时，给出Tomasulo算法所用的各信息表中的内容。

1
2
3
4
5
6
L.D      F6,34（R2）
L.D      F2,45（R3）
MUL.D    F0,F2,F4
SUB.D    F8,F2,F6
DIV.D    F10,F0,F6
ADD.D    F6,F8,F2

Solution:

示例2

假设各种操作的延迟为：

  • load：1个时钟周期

  • 加法：2个时钟周期

  • 乘法：10个时钟周期

  • 除法：40个时钟周期

给出MUL.D指令准备写结果时各状态表的内容。

Solution:

指令需要执行到第十二个周期，每个周期操作均已列出

然后忽略之前所填的保留站表，按照新的指令状态表重新填写

动态分支预测技术

在程序运行时，根据分支指令过去的表现来预测其将来的行为。

在预测错误时，要作废已经预取和分析的指令，恢复现场，并从另一条分支路径重新取指令。

分支历史表(BHT)

最简单的动态分支预测方法。

用BHT来记录分支指令最近一次或几次的执行情况（成功还是失败 ），并据此进行预测

采用两位二进制位来记录历史，状态转换如下

两位分支预测中的操作有两个步骤：

  • 分支预测；

    • 当分支指令到达译码段（ID）时，根据从BHT读出的信息进行分支预测 。

    • 若预测正确，就继续处理后续的指令，流水线没有断流。否则，就要作废已经预取和分析的指令，恢复现场，并从另一条分支路径重新取指令。

  • 状态修改。

BHT方法只在判定分支是否成功所需的时间大于确定分支目标地址所需的时间

分支目标缓冲器(BTB)

将分支成功的分支指令的地址和它的分支目标地址都放到一个缓冲区中保存起来，缓冲区以分支指令的地址作为标识。

看成是用专门的硬件实现的一张表格,表格中的每一项至少有两个字段：

  • 执行过的成功分支指令的地址；（作为该表的匹配标识 ）

  • 预测的分支目标地址。

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

基于硬件的前瞻执行

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

实现前瞻的关键思想：

  • 允许指令乱序执行，但必须顺序确认。

  • 在指令被确认之前，不允许它进行不可恢复的操作

ROB中的每一项由以下4个字段组成：

  • 指令类型

    指出该指令是分支指令、store指令或寄存器操作指令。

  • 目标地址

    给出指令执行结果应写入的目标寄存器号（如果是load和ALU指令）或存储器单元的地址（如果是store指令）。

  • 数据值字段

    用来保存指令前瞻执行的结果，直到指令得到确认。

  • 就绪字段

    指出指令是否已经完成执行并且数据已就绪。

指令的执行步骤

流出

  • 从浮点指令队列的头部取一条指令。

  • 如果有空闲的保留站（设为r）且有空闲的ROB项（设为b），就流出该指令，并把相应的信息放入保留站r和ROB项b。

  • 如果保留站或ROB全满，便停止流出指令，直到它们都有空闲的项。

执行

  • 如果有操作数尚未就绪，就等待，并不断地监测CDB。(检测RAW冲突)

  • 当两个操作数都已在保留站中就绪后，就可以执行该指令的操作。

写结果

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

  • 释放产生该结果的保留站。

  • store指令在本阶段完成，其操作为:

    • 如果要写入存储器的数据已经就绪，就把该数据写入分配给该store指令的ROB项。

    • 否则，就监测CDB，直到那个数据在CDB上播送出来，才将之写入分配给该store指令的ROB项。

确认

  • 其它指令（除分支指令和store指令）

    当该指令到达ROB队列的头部而且其结果已经就绪时，就把该结果写入该指令的目的寄存器，并从ROB中删除该指令。

  • store指令

    处理与上面的类似，只是它把结果写入存储器。

  • 分支指令

    • 当预测错误的分支指令到达ROB队列的头部时，清空ROB，并从分支指令的另一个分支重新开始执行。

    • 当预测正确的分支指令到达ROB队列的头部时，该指令执行完毕。

示例

假设浮点功能部件的延迟时间为：加法2个时钟周期，乘法10个时钟周期，除法40个时钟周期。对于下面的代码段，给出当指令MUL.D即将确认时的状态表内容。

1
2
3
4
5
6
L.D F6,34（R2）
L.D F2,45（R3）
MUL.D F0,F2,F4
SUB.D F8,F6,F2
DIV.D F10,F0,F6
ADD.D F6,F8,F2

Solution

由于ROB的特性是乱序执行，顺序确认。题目要求给出当指令MUL.D即将确认时的状态表内容。可以先忽略确认那一步，写出指令MUL.D写结果后的指令状态表

然后按照此写出ROB表

之后修改保留站

多指令流出技术

在每个时钟周期内流出多条指令， CPI＜1

多流出处理机有两种基本风格：

  • 超标量（Superscalar）

    • 在每个时钟周期流出的指令条数不固定，依代码的具体情况而定。（有个上限）

    • 设这个上限为n，就称该处理机为n-流出。

    • 可以通过编译器进行静态调度，也可以基于Tomasulo算法进行动态调度。

  • 超长指令字VLIW（Very Long Instruction Word）

    • 在每个时钟周期流出的指令条数是固定的，这些指令构成一条长指令或者一个指令包。

    • 指令包中，指令之间的并行性是通过指令显式地表示出来的。

    • 指令调度是由编译器静态完成的。

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

指令按序流出，在流出时进行冲突检测。如果有冲突，只流出该指令之前的指令

假设：每个时钟周期流出两条指令：1条整数型指令＋1条浮点操作指令

其中整数执行一个时钟周期，浮点数执行两个时钟周期

需要增加以下硬件：

  • 浮点load或浮点store指令将使用整数部件，会增加对浮点寄存器的访问冲突

    • 增设一个浮点寄存器的读/写端口

  • 由于流水线中的指令多了一倍，定向路径也要增加

限制超标量流水线的性能发挥的障碍

  • load指令

    • load后续3条指令都不能使用其结果，否则就会引起停顿。(因为LOAD指令最快在MEM阶段才会产生结果)

  • 分支延迟

    • 如果分支指令是流出包中的第一条指令，则其延迟是3个时钟周期.(同理，分支指令也会在MEM阶段才会产生结果)

    • 否则就是流出包中的第二条指令，其延迟就是两个时钟周期。

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

扩展Tomasulo算法：支持双流出超标量流水线

  • 每个时钟周期流出两条指令；

  • 一条是整数指令，另一条是浮点指令。

采用一种比较简单的方法：

  • 指令按顺序流向保留站，否则会破坏程序语义。

  • 将整数所用的表结构与浮点用的表结构分离开，分别进行处理，这样就可以同时地流出一条浮点指令和一条整数指令到各自的保留站

有两种不同的方法可以实现多流出

  • 在半个时钟周期里完成流出步骤，这样一个时钟周期就能处理两条指令

  • 设置一次能同时处理两条指令的逻辑电路

示例

对于采用了Tomasulo算法和多流出技术的MIPS流水线，考虑以下简单循环的执行。该程序把F2中的标量加到一个向量的每个元素上。

1
2
3
4
5
Loop:   L.D F0, 0（R1）     // 取一个数组元素放入F0
        ADD.D F4, F0, F2    // 加上在F2中的标量
        S.D F4, 0（R1）     // 存结果
        DADDIU R1,R1，#-8   // 将指针减少8（每个数据占8个字节）
        BNE R1,R2,Loop      // 若R1不等于R2，表示尚未结束，转移到Loop继续。

现做以下假设：

  • 每个时钟周期能流出一条整数指令和一条浮点指令，即使它们相关也是如此。

  • 有一个整数部件，用于整数ALU运算和地址计算；并且对于每一种浮点操作类型都有一个独立的流水化了的浮点功能部件。

  • 指令流出和写结果各占用一个时钟周期。

  • 具有动态分支预测部件和一个独立的计算分支条件的功能部件。

  • 跟大多数动态调度处理器一样，写回段的存在意味着实际的指令延迟会比按序流动的简单流水线多一个时钟周期。

所以，从产生结果数据的源指令到使用该结果数据的指令之间的延迟为：整数运算一个周期，load两个周期，浮点加法运算3个周期。

Question

  • 请列出该程序前面3遍循环中各条指令的流出、开始执行和将结果写到CDB上的时间。

  • 如果分支指令单流出，没有采用延迟分支，但分支预测是完美的。请列出整数部件、浮点部件、数据Cache以及CDB的资源使用情况。

Solution

上述双流出动态调度流水线的性能受限于以下3个因素：

  • 整数部件和浮点部件的工作负载不平衡，没有充分发挥出浮点部件的作用。

    • 应该设法减少循环中整数型指令的数量。

  • 每个循环叠代中的控制开销太大。

    • 5条指令中有两条指令是辅助指令；

    • 应该设法减少或消除这些指令。

  • 控制相关使得处理机必须等到分支指令的结果出来后才能开始下一条L.D指令的执行

超长指令字技术

  • 把能并行执行的多条指令组装成一条很长的指令；

  • 设置多个功能部件；

  • 指令字被分割成一些字段，每个字段称为一个操作槽，直接独立地控制一个功能部件；

  • 在VLIW处理机中，在指令流出时不需要进行复杂的冲突检测，而是依靠编译器全部安排好了。

VLIW存在的一些问题

  • 程序代码长度增加了

  • 提高并行性而进行的大量的循环展开；

  • 指令字中的操作槽并非总能填满。

    • 解决：采用指令共享立即数字段的方法，或者采用指令压缩存储、调入Cache或译码时展开的方法。

  • 采用了锁步机制

    • 任何一个操作部件出现停顿时，整个处理机都要停顿。

  • 机器代码的不兼容性

多流出处理器受到的限制

程序所固有的指令级并行性；

硬件实现上的困难；

超标量和超长指令字处理器固有的技术限制。

超流水线处理机

将每个流水段进一步细分，这样在一个时钟周期内能够分时流出多条指令。这种处理机称为超流水线处理机。

对于一台每个时钟周期能流出n条指令的超流水线计算机来说，这n条指令不是同时流出的，而是每隔1/n个时钟周期流出一条指令。

  • 实际上该超流水线计算机的流水线周期为1/n个时钟周期

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

超标量采用空间并行性。通过重复设置多份硬件提高性能

超流水线采用时间并行性。只需要增加少量硬件，通过各部分硬件的充分重叠工作来提高性能

互联网络

互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统中结点之间的相互连接。

3大要素：互连结构，开关元件，控制方式

互联函数

采用循环表示

即：（x0 x1 x2 … xj-1）

表示： f(x0)=x1，f(x1)=x2，…，f(xj-1)=x0，j称为该循环的长度。

常见互联函数

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

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

主要用于构造立方体互连网络和各种超立方体互连网络。

当N＝8时，n＝3，可得到常用的立方体互连函数：



均匀洗牌函数：将输入端分成数目相等的两半，前一半和后一半按类似均匀混洗扑克牌的方式交叉地连接到输出端（输出端相当于混洗的结果）

互连函数（设为s）的第k个子函数：把s作用于输入端的二进制编号的低k位。

互连函数（设为s）的第k个超函数：把s作用于输入端的二进制编号的高k位。

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

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

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

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

PM2I函数

P和M分别表示加和减，2I表示

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

示例

现有16个处理器，编号分别为0，1，…，15，用一个N=16的互连网络互连。处理器i的输出通道连接互连网络的输入端i，处理器i的输入通道连接互连网络的输出端i。当该互连网络实现的互连函数分别为：

（1）
（2）
（3）
（4）
（5）

时，分别给出与第13号处理器所连接的处理器号。

Solution

(1)

所以处理器13与处理器5双向互连。

(2)

所以处理器13与处理器5双向互连。

(3)

(4)

所以处理器13连至处理器11，而处理器14连至处理器13。

(5)

所以处理器13与处理器7双向互连。

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

互连网络的结构参数

网络规模N：网络中结点的个数

结点度d：与结点相连接的边数（通道数），包括入度和出度

结点距离：对于网络中的任意两个结点，从一个结点出发到另一个结点终止所需要跨越的边数的最小值。

网络直径D：网络中任意两个结点之间距离的最大值。

等分宽度b：把由N个结点构成的网络切成结点数相同（N/2）的两半，在各种切法中，沿切口边数的最小值。

对称性：从任何结点看到的拓扑结构都是相同的网络称为对称网络。

互连网络的性能指标

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

  • 软件开销:在源结点和目的结点用于收发消息的软件所需的执行时间。

  • 通道时延：通过通道传送消息所花的时间

  • 选路时延：消息在传送路径上所需的一系列选路决策所需的时间开销。

  • 竞争时延：多个消息同时在网络中传送时，会发生争用网络资源的冲突。为避免或解决争用冲突所需的时间就是竞争时延

网络时延是通道时延与选路时延的和

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

  • 非对称网络的端口带宽则是指所有端口带宽的最小值。

  • 在对称网络中，端口带宽与端口位置无关。网络的端口带宽与各端口的端口带宽相同。

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

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

静态互连网络

线性阵列：一种一维的线性网络，其中N个结点用N-1个链路连成一行。

端结点的度：1

其余结点的度：2

直径：N－1

等分宽度：b=1

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

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

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

结点度：2n－1

直径：n/2

网络规模:

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

一般说来，一棵k层完全平衡的二叉树有个结点。

最大结点度：3

直径：2(k-1)

等分宽度:b=1

星形

结点度较高，为N－1。

直径较小，是一常数2。等分宽度

可靠性比较差，只要中心结点出故障，整个系统就会瘫痪。

网格形

一个3×3的网格形网络

一个规模为N=n×n的2维网格形网络

  • 内部结点的度d=4

  • 边结点的度d=3

  • 角结点的度d=2

  • 网络直径D=2（n-1）

  • 等分宽度b=n

一个由个结点构成的k维网格形网络（每维n个结点）的内部结点度d=2k，网络直径D=k(n-1) 。

Illiac网络

把2维网格形网络的每一列的两个端结点连接起来，再把每一行的尾结点与下一行的头结点连接起来，并把最后一行的尾结点与第一行的头结点连接起来。

一个规模为n×n的Illiac网络

  • 所有结点的度d=4

  • 网络直径D=n-1

  • Illiac网络的直径只有纯网格形网络直径的一半。

  • 等分宽度：2n

环网形

可看作是直径更短的另一种网格。

把2维网格形网络的每一行的两个端结点连接起来，把每一列的两个端结点也连接起来。

将环形和网格形组合在一起，并能向高维扩展。

一个n×n的环网形网

  • 结点度：4

  • 网络直径：

  • 等分宽度b=2n

超立方体

一种二元n-立方体结构

一般来说，一个二元n-立方体由个结点组成，它们分布在n维上，每维有两个结点

为实现一个n-立方体，只要把两个（n－1）立方体中相对应的结点用链路连接起来即可。共需要条链路

n-立方体中结点的度都是n，直径也是n，等分宽度为b=N/2 。

带环立方体

把3-立方体的每个结点换成一个由3个结点构成的环而形成的

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

  • k-立方体的变形，它是通过用k个结点构成的环取代k-立方体中的每个结点而形成的。

  • 网络规模为

  • 网络直径为

    • 比k-立方体的直径大一倍

  • 等分宽度为b=N/（2k）

k元n-立方体网络

在k元n-立方体网络中，参数n是立方体的维数，k是基数，即每一维上的结点个数

(这表看看就完了，我猜没人背得下来:D)

示例

已知有16台个处理器用Illiac网络互连，写出Illiac网络的互连函数，给出表示任何一个处理器（0≤i≤15）与其他处理器直接互连的一般表达式。

Solution

首先要了解Illiac网络互连。其每一列是自循环且双向互联，可得以下互联函数

1
2
3
4
（0 4 8 12） （12 8 4 0）
（1 5 9 13） （13 9 5 1）
（2 6 10 14） （14 10 6 2）
（3 7 11 15） （15 11 7 3）

概括一下，相当于和

水平螺线互连为一个双向环

1
2
（0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15）
（15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0）

概括一下，相当于和

动态互连网络

总线网络

由一组导线和插座构成，经常被用来实现计算机系统中处理机模块、存储模块和外围设备等之间的互连。

  • 每一次总线只能用于一个源（主部件）到一个或多个目的（从部件）之间的数据传送。

  • 多个功能模块之间的争用总线或时分总线

特点

  • 结构简单、实现成本低、带宽较窄

解决总线带宽较窄问题：采用多总线或多层次的总线

交叉开关网络

单级开关网络

交叉点开关能在对偶（源、目的）之间形成动态连接，同时实现多个对偶之间的无阻塞连接。

带宽和互连特性最好。

一个n×n的交叉开关网络，可以无阻塞地实现n!种置换。

  • 对一个n×n的交叉开关网络来说，需要套交叉点开关以及大量的连线。

当n很大时，交叉开关网络所需要的硬件数量非常巨大。

C.mmp多处理机的互连结构

用16×16的交叉开关网络把16台PDP-11处理机与16个存储模块连在一起

最多可同时实现16台处理机对16个不同存储模块的并行访问

  • 每个存储模块一次只能满足一台处理机的请求

  • 当多个请求要同时访问同一存储模块时，交叉开关就必须分解所发生的冲突，每一列只能接通一个交叉点开关。

  • 为了支持并行（或交叉）存储器访问，可以在同一行中接通几个交叉点开关。

多级互连网络

由a×b开关模块和级间连接构成的通用多级互连网络结构

每一级都用了多个a×b开关:a个输入和b个输出

在理论上，a和b不一定相等，然而实际上a和b经常选为2的整数幂，即＝＝，k≥1。

相邻各级开关之间都有固定的级间连接

各种多级互连网络的区别在于所用开关模块、控制方式和级间互连模式的不同。

控制方式：对各个开关模块进行控制的方式

  • 级控制：每一级的所有开关只用一个控制信号控制，只能同时处于同一种状态。

  • 单元控制：每一个开关都有一个独立的控制信号，可各自处于不同的状态。

  • 第i级的所有开关分别用i＋1个信号控制，0≤i≤n－1，n为级数。

多级立方体网络

这个图是比较重要的，级0和级1之间采用蝶式互连函数的第二个子函数，级1和级2之间采用蝶式互连函数，级2与输出之间采用反均匀洗牌函数

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

  • 采用级控制时，所实现的是交换功能；

以下图为例，展示级0采用交换功能，级1和级2采用直通功能时是如何交换的

  • 采用部分级控制时，则能实现移数功能。

分析方式相似，请自行分析，上表仅仅列出一部分，应有种移数方式

Omega网络

一个8×8的Omega网络

每级由4个4功能的2×2开关构成

级间互连采用均匀洗牌连接方式

$

一个 ( N ) 输入的 ( \Omega ) 网络：

  • 有 ( \log_2 N ) 级，每级用 ( \frac{N}{2} ) 个 ( 2 \times 2 ) 开关模块，共需要 ( \frac{N \log_2 N}{2} ) 个开关。
  • 每个开关模块均采用单元控制方式。
  • 不同的开关状态组合可实现各种置换、广播或从输入到输出的其它连接。

$

动态互连网络的比较

消息传递机制

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

消息寻径方案

消息：结点之间进行通信的逻辑单位

  • 由若干个“包”组成

  • 包的长度是固定的，一条消息中所包含的包的个数是可变的，消息的长度是不定长的。

包：包含寻径所需目的地址的基本单位。

  • 一条消息中的各个包都依次被分配一个序号以便这些包到达目的结点后能重新组装出消息。

  • 包可以进一步分成一些更小的固定长度的单位，称为“片”。

  • 寻径信息和包序列号形成头片，其余的是数据片。

  • 包的长度主要是由寻径方案和网络的具体实现所决定的

  • 典型的长度是64～512位不等

  • 片的长度经常是受网络大小的影响

四种寻径方式

线路交换：在线路交换方式下，在传递一个信息之前，需要先建立一条从源结点到目的结点的物理通路，然后再传递信息。

传输时延

其中：

  • L：信息包的长度（位数）

  • ：建立路径所需的小信息包的长度

  • D：经过的中间结点个数

  • B：带宽

优点：传输带宽较大，平均传输时延较小，而且使用的缓冲区小。

缺点：需要频繁地建立源结点到目的结点的物理通路，时间开销会很大。

存储转发：最简单的分组交换方式。

包是信息传递的基本单位。包从源结点经过一系列中间结点到达目的结点。

要求：所经过的每个中间结点都要设置一个包缓冲器，用于保存所传递的包。当一个包到达某个中间结点时，该结点先把这个包全部存储起来，然后在出口链路可用、而且下一个结点的包缓冲器也可用的情况下，传递给下一个结点。

网络的时延与源和目的地之间的距离（跳数）成正比

通信时延

缺点

  • 包缓冲区大，不利于VLSI实现；

  • 网络时延大，与结点距离成正比。

虚拟直通：对存储转发方式的一种改进，减少了网络时延。

基本思想 ：没有必要等到信息包全部放入缓冲器后再作路由选择，只要接收到用作寻径的包头，就可作出判断。

如果结点的输出链路空闲，信息包可以不必存储在该结点的缓冲器中，而是立即传送到下一个结点。

如果整条链路都空闲，包就可以立即直达目的结点。

在输出链路不空闲时，要用缓冲器进行存储

传输时延

信息包寻径头部的长度一般来说所以

当出现寻径阻塞时，虚拟直通方式需要将整个信息包全部存储在寻径结点中，要求每个结点都有足够大的缓冲区。（不利于VLSI的实现 ）

虫蚀方式：把信息包“切割”成更小的单位——“片”，而且使信息包中各片的传送按流水方式进行。

可以减少结点中缓冲器的容量，缩短传送延迟时间。

  • 在新型的多计算机系统中得到了广泛的应用。

  • 处理的最小信息单位是“片”。当一个结点把头片送到下一个结点后，那么接下来就可以把后面的各个片也依次送出。

一个结点一旦开始传送一个包中的头片后，这个结点就必须等待这个包的所有片都送出去后，才能传送其他包。不同包的片不能混合在一起传送。

与虚拟直通的不同之处

  • 当输出通路忙时，结点是把一个片存储到缓冲器中。

  • 由于片的大小比包小很多，所以能有效地减少缓冲器的容量，使得它易于用VLSI实现。

通信时延

优点

  • 每个节点的缓冲器较小，易于VLSI实现；

  • 有较小的网络传输延迟；

  • 通道共享性好，利用率高；

  • 易于实现选播和广播通信模式。

缺点

  • 当消息的一片被阻塞时，整个消息的所有片都将被阻塞在所在结点，占用了结点资源。

死锁与虚拟直通

虚拟通道：两个结点间的逻辑链接，它由源结点的片缓冲区、结点间的物理通道以及接收结点的片缓冲区组成。

4条虚拟通道共享一条物理通道

  • 源结点和接收结点各有4个片缓冲区。

  • 当物理通道分配给某对缓冲区时，这一对的源缓冲区和接收缓冲区就形成了一条虚拟通道。

  • 物理通道是由所有的虚拟通道分时地共享。

虚拟通道也可以用双向通道实现。把两条单向通道组合在一起可以构成一条双向通道。

  • 增加了利用率，使通道的带宽加倍。

4条虚拟通道以片传递为基础分时地共享一条物理通道

避免死锁

流控制策略

当两个包到达同一个结点时，它们可能都在请求同一个接收缓冲器或者同一个输出通道，这时必须对两个问题进行仲裁。

二维网格网络的X-Y寻径

任意一个源结点：s=（x1，y1）

任意一个目的结点：d=（x2，y2）

从s出发，先沿X轴方向前进，直到找到d 所在的列x2；

然后再沿Y轴方向前进，直到找到目标结点（x2，y2）。

示例

对于图所示的二维网格，确定以下4组“源结点-目的结点”所需要的路经。

1
2
3
4
（2，1）到（7，6）
（0，7）到（4，5）
（6，4）到（2，0）
（5，3）到（1，5）

Solution

所需要的路径如图所示。其中：

1
2
3
4
（2，1）到（7，6）需要用到的是一条东-北路径；
（0，7）到（4，5）需要用到的是一条东-南路径；
（6，4）到（2，0）需要用到的是一条西-南路径；
（5，3）到（1，5）需要用到的是一条西-北路径。

n方体寻路

考虑一个由＝个结点构成的n方体，每个结点的编号是形为＝的二进制编码。设：

源结点＝,

目的结点＝.

现在要确定一条从s到d的步数最少的路径。将这个n方体的各维表示成i＝1，2，…，n，其中第i维对应于结点地址中的第i－1位。

设＝是路径中的任一结点。路径可以根据以下算法唯一地确定：

计算方向位，其中.
令,，反复执行以下步骤：

  1. 如果，则从当前结点寻径到下一结点；否则，跳过此步骤。
  2. . 如果，则返回步骤 1，否则退出。

示例

假设有一个N=16个结点的4方体，每个结点的二进制编码如图所示。请寻找一条从结点0110到1101的距离最短的路径。

Solution

s=0110, d=1101

计算方向位（r4,r3,r2,r1）=

r1＝1,所以从v=0110寻径到

r2＝1,所以从v＝0111寻径到

r3＝0，所以跳过一步

r4＝1,所以从v＝0101寻径到

选播和广播寻径算法

多计算机网络中会出现以下4种通信模式：

  • 单播：对应于一对一的通信情况，即一个源结点发送消息到一个目的结点。

  • 选播：对应于一到多的通信情况，即一个源结点发送同一消息到多个目的结点。

  • 广播：对应于一到全体的通信情况，即一个源结点发送同一消息到全部结点。

  • 会议：对应于多到多的通信情况。

在3×4网格上实现的选播寻径

源结点：S

传送一个包到标号为Di 的5个目的结点（＝，，，）

在虫蚀网络中，用图（c）的选播寻径模式比较好。

在存储转发网络中，则用图（b）的寻径模式比较好，时延较短。

图（d ）：使用一棵4层的生成树可以把一个包从结点S广播到所有的网络结点

  • 产生的时延和流量最小

多处理机

存储器系统结构和通信机制

系统结构

共享地址空间

  • 物理上分离的所有存储器作为一个统一的共享逻辑空间进行编址。

  • 任何一个处理器可以访问该共享空间中的任何一个单元（如果它具有访问权），而且不同处理器上的同一个物理地址指向的是同一个存储单元。

  • 这类计算机被称为分布式共享存储器系统

把每个结点中的存储器编址为一个独立的地址空间，不同结点中的地址空间之间是相互独立的。

  • 整个系统的地址空间由多个独立的地址空间构成

  • 每个结点中的存储器只能由本地的处理器进行访问，远程的处理器不能直接对其进行访问。

  • 每一个处理器-存储器模块实际上是一台单独的计算机

  • 现在的这种机器多以集群的形式存在

通信机制

共享存储器通信机制

  • 共享地址空间的计算机系统采用

  • 处理器之间是通过用load和store指令对相同存储器地址进行读/写操作来实现的。

消息传递通信机制

  • 多个独立地址空间的计算机采用

  • 通过处理器间显式地传递消息来完成

  • 消息传递多处理机中，处理器之间是通过发送消息来进行通信的，这些消息请求进行某些操作或者传送数据。

  • 同步消息传递

    • 请求处理器发送一个消息后一直要等到应答结果才继续运行。

  • 异步消息传递

    • 数据发送方知道别的处理器需要数据，通信也可以从数据发送方来开始，数据可以不经请求就直接送往数据接受方。

不同通信机制的优点

共享存储器通信的主要优点

  • 与常用的对称式多处理机使用的通信机制兼容。

  • 易于编程，同时在简化编译器设计方面也占有优势。

  • 采用大家所熟悉的共享存储器模型开发应用程序，而把重点放到解决对性能影响较大的数据访问上。

  • 当通信数据量较小时，通信开销较低，带宽利用较好。

  • 可以通过采用Cache技术来减少远程通信的频度，减少了通信延迟以及对共享数据的访问冲突。

消息传递通信机制的主要优点

硬件较简单。

  • 通信是显式的，因此更容易搞清楚何时发生通信以及通信开销是多少。

  • 显式通信可以让编程者重点注意并行计算的主要通信开销，使之有可能开发出结构更好、性能更高的并行程序。

  • 同步很自然地与发送消息相关联，能减少不当的同步带来错误的可能性。

并行处理面临的挑战

并行处理面临着两个重要的挑战

  • 程序中的并行性有限

  • 相对较大的通信开销

问题的解决

  • 并行性不足： 采用并行性更好的算法

  • 远程访问延迟的降低：靠系统结构支持和编程技术

对称式共享存储器系统结构

多处理机Cache一致性

写共享数据引起的不一致性

  • 允许共享数据进入Cache，就可能出现多个处理器的Cache中都有同一存储块的副本，

  • 当其中某个处理器对其Cache中的数据进行修改后，就会使得其Cache中的数据与其他Cache中的数据不一致

进程迁移引起的数据不一致

P1和P2中都有X的拷贝，P2修改X(写通过)。进程迁移到P1上，这时P1的Cache中仍然是X

P1中有X的拷贝，P2中没有，P1修改X(写回)。进程迁移到P2上，P2运行时从内存中读到是X

存储器的一致性

如果对某个数据项的任何读操作均可得到其最新写入的值，则认为这个存储系统是一致的。

需要满足以下条件

  • 处理器P对单元X进行一次写之后又对单元X进行读，读和写之间没有其它处理器对单元X进行写，则P读到的值总是前面写进去的值。

  • 处理器P对单元X进行写之后，另一处理器Q对单元X进行读，读和写之间无其它写，则Q读到的值应为P写进去的值。

  • 对同一单元的写是串行化的，即任意两个处理器对同一单元的两次写，从各个处理器的角度看来顺序都是相同的。

实现一致性的基本方案

共享数据的迁移：减少了对远程共享数据的访问延迟，也减少了对共享存储器带宽的要求。

共享数据的复制：不仅减少了访问共享数据的延迟，也减少了访问共享数据所产生的冲突。

Cache一致性协议

目录式协议（directory）：物理存储器中数据块的共享状态被保存在一个称为目录的地方。

监听式协议（snooping）：

  • 每个Cache除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状态信息。

  • Cache通常连在共享存储器的总线上，当某个Cache需要访问存储器时，它会把请求放到总线上广播出去，其他各个Cache控制器通过监听总线（它们一直在监听）来判断它们是否有总线上请求的数据块。如果有，就进行相应的操作。

采用两种方法来解决Cache一致性问题。

写作废协议

在本地Cache的数据块修改时使远程数据块都无效\作废

写更新协议

在本地Cache数据块修改时通过总线把新的数据块广播给含有该数据块的所有其他Cache

写更新和写作废协议性能上的差别

  • 在对同一个数据进行多次写操作而中间无读操作的情况下，写更新协议需进行多次写广播操作，而写作废协议只需一次作废操作。

  • 在对同一Cache块的多个字进行写操作的情况下，写更新协议对于每一个写操作都要进行一次广播，而写作废协议仅在对该块的第一次写时进行作废操作即可。

    • 写作废是针对Cache块进行操作，而写更新则是针对字（或字节）进行。

  • 考虑从一个处理器A进行写操作后到另一个处理器B能读到该写入数据之间的延迟时间。

    • 写更新协议的延迟时间较小。

监听协议的实现

处理器之间通过一个可以实现广播的互连机制相连，通常采用的是总线。

当一个处理器的Cache响应本地CPU的访问时，如果它涉及到全局操作，其Cache控制器就要在获得总线的控制权后，在总线上发出相应的消息。

所有处理器都一直在监听总线，它们检测总线上的地址在它们的Cache中是否有副本。若有，则响应该消息，并进行相应的操作。

写操作的串行化：由总线实现（获取总线控制权的顺序性）

Cache发送到总线上的消息主要有以下两种：

  • RdMiss——读不命中

  • WtMiss——写不命中

需要通过总线找到相应数据块的最新副本，然后调入本地Cache中。

  • 写直达Cache：因为所有写入的数据都同时被写回主存，所以从主存中总可以取到其最新值。

  • 对于写回Cache，得到数据的最新值会困难一些，因为最新值可能在某个Cache中，也可能在主存中。

有的监听协议还增设了一条Invalidate消息，用来通知其他各处理器作废其Cache中相应的副本。

- 与WtMiss的区别：Invalidate不引起调块

Cache的标识（tag）可直接用来实现监听。

作废一个块只需将其有效位置为无效。

给每个Cache块增设一个共享位

  • 为“1”：该块是被多个处理器所共享

  • 为“0”：仅被某个处理器所独占

监听协议举例

在每个结点内嵌入一个有限状态控制器。

  • 该控制器根据来自处理器或总线的请求以及Cache块的状态，做出相应的响应。

每个数据块的状态取以下3种状态中的一种

  • 无效（简称I）：Cache中该块的内容为无效。

  • 共享（简称S）：该块可能处于共享状态。

    • 在多个处理器中都有副本。这些副本都相同，且与存储器中相应的块相同。

  • 已修改（简称M）：该块已经被修改过，并且还没写入存储器。（块中的内容是最新的，系统中唯一的最新副本）

下面来讨论在各种情况下监听协议所进行的操作。

分布式共享存储器系统结构

目录协议的基本思想

目录：一种集中的数据结构。对于存储器中的每一个可以调入Cache的数据块，在目录中设置一条目录项，用于记录该块的状态以及哪些Cache中有副本等相关信息。

  • 特点：对于任何一个数据块，都可以快速地在唯一的一个位置中找到相关的信息。这使一致性协议避免了广播操作。

位向量：记录哪些Cache中有副本。

  • 每一位对应于一个处理器。

  • 长度与处理器的个数成正比。

  • 由位向量指定的处理机的集合称为共享集S。

分布式目录

  • 目录与存储器一起分布到各结点中，从而对于不同目录内容的访问可以在不同的结点进行。

  • 对每个结点增加目录后的分布式存储器多处理机

目录法最简单的实现方案：对于存储器中每一块都在目录中设置一项。目录中的信息量与M×N成正比。

其中：

  • M：存储器中存储块的总数量

  • N：处理器的个数

  • 由于M=K*N， K是每个处理机中存储块的数量，所以如果K保持不变，则目录中的信息量就与N2成正比。

在目录协议中，存储块的状态有3种：

  • 未缓冲：该块尚未被调入Cache。所有处理器的Cache中都没有这个块的副本。

  • 共享：该块在一个或多个处理机上有这个块的副本，且这些副本与存储器中的该块相同。

  • 独占：仅有一个处理机有这个块的副本，且该处理机已经对其进行了写操作，所以其内容是最新的，而存储器中该块的数据已过时。

本地结点、宿主结点以及远程结点的关系：

  • 本地结点：发出访问请求的结点

  • 宿主结点：包含所访问的存储单元及其目录项的结点

  • 远程结点可以和宿主结点是同一个结点，也可以不是同一个结点。

在结点之间发送的消息

P：发出请求的处理机编号

K：所要访问的地址

  • 本地结点发给宿主结点（目录）的消息

    • RdMiss（P，K）处理机P读取地址为A的数据时不命中，请求宿主结点提供数据（块），并要求把P加入共享集。

    • WtMiss（P，K）处理机P对地址A进行写入时不命中，请求宿主结点提供数据，并使P成为所访问数据块的独占者。

    • Invalidate（K）请求向所有拥有相应数据块副本（包含地址K）的远程Cache发Invalidate消息，作废这些副本。

  • 宿主结点（目录）发送给远程结点的消息

    • Invalidate（K）作废远程Cache中包含地址K的数据块。

    • Fetch（K）从远程Cache中取出包含地址K的数据块，并将之送到宿主结点。把远程Cache中那个块的状态改为“共享”。

    • Fetch&Inv（K）从远程Cache中取出包含地址K的数据块，并将之送到宿主结点。然后作废远程Cache中的那个块。

  • 宿主结点发送给本地结点的消息

    • DReply（D）：D表示数据内容。把从宿主存储器获得的数据返回给本地Cache。

  • 远程结点发送给宿主结点的消息

    • WtBack（K，D）把远程Cache中包含地址K的数据块写回到宿主结点中， 该消息是远程结点对宿主结点发来的“取数据”或“取/作废”消息的响应

  • 本地结点发送给被替换块的宿主结点的消息

  • MdSharer（P，K）用于当本地Cache中需要替换一个包含地址K的块、且该块未被修改过的情况。这个消息发给该块的宿主结点，请求它将P从共享集中删除。如果删除后共享集变为空集，则宿主结点还要将该块的状态改变为“未缓存”（U）。

  • WtBack2（P，K，D）用于当本地Cache中需要替换一个包含地址K的块、且该块已被修改过的情况。这个消息发给该块的宿主结点，完成两步操作：①把该块写回；②进行与MdSharer相同的操作。

目录协议实例

在基于目录的协议中，目录承担了一致性协议操作的主要功能

  • 本地结点把请求发给宿主结点中的目录，再由目录控制器有选择地向远程结点发出相应的消息。

  • 发出的消息会产生两种不同类型的动作：

    • 更新目录状态

    • 使远程结点完成相应的操作

在基于目录协议的系统中， Cache块的状态转换图

目录的状态转换及相应的操作

位向量记录拥有其副本的处理器的集合。这个集合称为共享集合。

对于从本地结点发来的请求，目录所进行的操作包括：

  • 向远程结点发送消息以完成相应的操作。这些远程结点由共享集合指出；

  • 修改目录中该块的状态；

  • 更新共享集合

目录可能接收到3种不同的请求

  • 读不命中

  • 写不命中

  • 数据写回

当一个块处于未缓存状态时，对该块发出的请求及处理操作为：

  • RdMiss（读不命中）将所要访问的存储器数据送往请求方处理机，且该处理机成为该块的唯一共享结点，本块的状态变成共享。

  • WtMiss（写不命中）将所要访问的存储器数据送往请求方处理机，该块的状态变成独占，表示该块仅存在唯一的副本。其共享集合仅包含该处理机，指出该处理机是其拥有者。

当一个块处于共享状态时，其在存储器中的数据是当前最新的，对该块发出的请求及其处理操作为：

  • RdMiss：将存储器数据送往请求方处理机，并将其加入共享集合。

  • WtMiss：将数据送往请求方处理机，对共享集合中所有的处理机发送作废消息，且将共享集合改为仅含有该处理机，该块的状态变为独占。

当某块处于独占状态时，该块的最新值保存在共享集合所指出的唯一处理机（拥有者）中。有三种可能的请求：

  • RdMiss：将“取数据”的消息发往拥有者处理机，将它所返回给宿主结点的数据写入存储器，并进而把该数据送回请求方处理机，将请求方处理机加入共享集合。此时共享集合中仍保留原拥有者处理机（因为它仍有一个可读的副本）。将该块的状态变为共享。

  • WtMiss：该块将有一个新的拥有者。给旧的拥有者处理机发送消息，要求它将数据块送回宿主结点写入存储器，然后再从该结点送给请求方处理机。同时还要把旧拥有者处理机中的该块作废。把请求处理机加入共享者集合，使之成为新的拥有者。 该块的状态仍旧是独占。

  • WtBack（写回）：当一个块的拥有者处理机要从其Cache中把该块替换出去时，必须将该块写回其宿主结点的存储器中，从而使存储器中相应的块中存放的数据是最新的（宿主结点实际上成为拥有者）；该块的状态变成未缓冲，其共享集合为空。