系统结构笔记四、五章
第四章 向量处理机
重点
向量处理方法：横向处理、纵向处理、纵横处理
向量流水处理机结构：
1. 存储器-存储器结构：纵向处理
2. 寄存器-寄存器结构：纵横处理
提高向量处理机性能的方法：
- 多功能部件的并行操作
- 链接技术 WD 相关
- 分段开采
- 多处理机系统结构
向量处理机性能的主要参数：
- 一条向量指令的处理时间
- 一组向量指令的处理时间
- 向量处理机的性能评估（MFLOPS 或一个浮点运算的时间）
第四章，重点是链接技术，一般出大题，pin
向量基本概念和处理方法
向量处理机：设置了向量数据表示和向量指令的流水线处理机。
向量处理机方式：
- 横向处理方式：向量按 column 的方式从左到右横向进行。适用于一般处理机，不适用于向量处理机的并行处理。
- 以 $D=A \times (B+C)$为例
- 每个向量的处理产生N次数据相关，2N次功能转移（向量长度特别长）
- 纵向处理方式：向量按 row 的方式从上到下纵向进行。将整个向量按相同运算处理完之后，再进行别的运算。不产生数据相关，对向量长度 N 没有限制。
- 纵横处理方式：把向量分成若干组，组内按纵向方式处理，依次处理各组。对向量长度 N 没有限制，但以每 n 个元素分一组处理，n 的值固定。
向量处理机结构
存储器-存储器结构
适合纵向处理方式。
- 源向量和目的向量都存放在存储器中，运算的中间结果需要送回存储器。
- 对应的向量分量能并发访问，计算结果能并行地保存。
- 普通存储器的 3 倍带宽：3 条独立数据通路，一个时钟周期读出两个操作数并写回一个结果。
为了满足运算器带宽要求，存储器采用多个存储器模块组成的结构方式，运算器与主存间有三条相互独立的数据通路，三条路之间可以并行工作，但每个模块同一时间只服务于一个《？？》
寄存器-寄存器结构
适合纵横处理方式。
- 若干级中间存储器形成有层次结构的存储系统，相当于寄存器。
- 访问中间存储器速度更快(比直接访问存储器)。
- 通过中间存储器形成新的数据结构，高效。
- 中间存储器高带宽、多种寻址方式、支持流水线链接技术。
CRAY-1向量处理机
- 上课讲了，but没怎么听懂（草）。
向量流水线并行条件：
- 功能部件不冲突
- 源寄存器不冲突
- 结果寄存器不冲突
- 数据不相关
提高向量流水处理机性能
- 设置多个功能部件，使它们并行工作
- 采用链接技术，加快一串向量指令的执行
- 采用（分段）循环开采技术，加快循环的处理
- 采用多处理机系统，进一步提高性能
多功能部件的并行操作
约束条件为：
- 无向量寄存器使用冲突
- 无功能部件使用冲突
链接
必须是“寄存器——寄存器”系统
向量运算输出可直接作为输入使用，结果寄存器立即成为后继指令操作数寄存器。是定向技术的发展，利用 RAW 数据相关性。数据进（出）每个功能部件需 1 个时钟周期。
链接条件：
- 空间
- 无向量寄存器(源和结果都不冲突)、功能部件冲突
- 时间
- 仅上一指令的第 1 个结果分量送入结果向量寄存器的时钟周期可链接。
- 若后一指令源操作数分别是前两指令的结果寄存器，前两指令产生结果时间必须相等。
- 向量长度必须相等。
由于同步的要求,链接时,Cray-1中把向量数据元素送往向量功能部件以及把结果存入向量寄存器都需要一拍时间,从存储器中把数据送入访存功能部件也需要一拍时间。
例题（课本4.1 4.2）
分段（循环）开采
向量长度大于向量寄存器长度时，对向量进行分段处理，系统完成，对程序员透明。
处理长向量的程序结构称为向量循环。也称分段开采技术。。
向量分段由系统硬件和软件控制完成，对程序员透明。即看不到分段过程。
进入循环前，系统会根据向量长度计算出循环的次数。
分段需一定时间开销，包括流水线启动开销
多处理机体系结构
略
向量处理机的性能评价
向量处理指令特点：
- 一条指令得到若干运算结果。
- 执行时间与向量长度有关。
- 向量处理中包含标量指令。
- CPI、MIPS 不能反映向量处理性能。
向量处理机性能主要参数
1.一条向量指令的处理时间$T_{vp}$
$T_{vp} = T_s + T_e + (n-1)T_c$
$T_{vp}$ :执行一条向量长度为n的向量指令所需的时间
$T_s$ :向量处理部件流水线的建立时间
$T_e$ :向量流水线的通过时间
$T_c$ :流水线的时钟周期时间
不考虑 $T_s$，令$T_{start} = e-1$
$T_{vp} = T_{start} + (n-1)T_c$
其中, $T_{start}$ 为从一条向量指令开始执行到还差一个时钟周期就产生第一个结果所需的时钟周期数,可称为该向量指令的启动时间。此后,便是每个时钟周期流出一个结果,共有n个结果。
2.一组向量指令的处理时间
下面考虑一组向量指令的执行时间。
这个执行时间主要取决于三个因素:
- 向量的长度
- 向量操作之间是否存在流水功能部件的使用冲突
- 数据的相关性
我们把能在同一个时钟周期内一起开始执行的几条向量指令称为一个编队。
同一个编队中的向量指令之间一定不存在流水功能部件的冲突﹑ $V_i$ 冲突或数据的相关性。如果存在这种冲突或相关,那么就必须将它们编入不同的编队。
$T_{all} = \sum_{i=1}^{m} T_{vp}^{(i)}$
m是编队的数目， $T_{vp}^{(i)}$ 表示第i个编队的执行时间。
当一个编队是由若干条指令组成时,其执行时间就应该由该编队中各指令的执行时间的最大值来确定。由于都是处理n个元素,所以主要的区别在于各条指令的 $T_{start}$ 值。令 $T_{start}^{(i)}$ 表示第i编队中各指令的启动时间的最大值,则
$T_{all} = [T_{start} +mn] T_{c}$
其中， $T_{start}$ 是该组指令总的启动时间(时钟周期个数)。
如果表示成时钟周期个数,则
$T_{all} = T_{start} +mn$ 拍。
后面主要用这个公式来计算向量指令序列的执行时间。
2.每秒浮点运算数目MFLOP（或 一个浮点运算的时间）
4.向量流水线的最大性能$R \infty$
5.半性能向量长度 $n_1/2$
6.向量长度临界值 $n_v$
小结
- 向量处理机方式
- 横向纵向纵横
- 典型结构
第五章 指令级并行及其开发——硬件方法
指令级并行的概念
相关与指令级并行
指令的动态调度
动态分支预测技术
多指令流出技术
指令级并行基础概念
分为两类（实际应用中，两者往往会相结合）
- 基于硬件的动态开发方法(程序运行过程中)
- 基于软件的静态开发方法
之前第三章已经介绍了编译器解决的方法（软件层面，静态的），本章来讨论动态调度代码的硬件方法。
指令级并行（ILP）是指令间存在的一种并行性，使计算机可以并行执行两条及以上的指令。
流水线处理机的实际 CPI:$CPI_{流水线} = CPI_{理想} +停顿_{结构冲突}+停顿_{数据冲突}+停顿_{控制冲突}$
基本程序块：如果一串连续的代码除了入口和出口以外,没有其他的分支指令和转入点,则称之为一个基本程序块(Basic Block)。
由于程序中往往每隔4~7条指令就会有一个分支,而且指令之间还可能存在相关,因此在基本程序块中能开发出的并行性是很有限的,很可能比基本块的平均大小要小得多。为了明显地提高性能﹐必须跨越多个基本块开发ILP。
相关有三种类型
- 数据相关
- 名相关
- 控制相关
流水线冲突(hazard) 是指对于具体的流水线来说,由于相关的存在,使得指令流中的下一条指令不能在指定的时钟周期执行。
流水线冲突有三种类型
- 结构冲突:因硬件资源冲突造成的
- 数据冲突:由数据相关和名相关造成的
- 控制冲突:由控制相关造成的
数据相关限制了所能开发的ILP，可以从两方面来克服这些限制
- 保持相关，但避免发生冲突（指令调度）
- 进行代码变换，消除相关
程序顺序(Program Order)是指:由原来程序确定的在完全串行方式下指令的执行顺序。但是,并不需要在所有存在相关的地方都保持程序顺序。
控制相关并不是一个必须严格保持的关键属性。为了保证程序执行的正确的，必须保持的最关键的两个属性是：数据流和异常行为
- 保持异常行为(Exception Behavoir)
无论怎么改变指令的执行顺序,都不能改变程序中异常的发生情况。即原来程序中是怎么发生的,改变执行顺序后应该还是那样发生。这个条件经常被弱化为:指令执行顺序的改变不能导致程序中发生新的异常。 - 数据流(Data Flow)
是指数据值从其产生者指令到其消费者指令的实际流动。分支指令使得数据流具有动态性,因为一条指令有可能数据相关于多条先前的指令。分支指令的执行结果决定了哪条指令真正是所需数据的产生者。
有时,不遵守控制相关既不影响异常行为,也不改变数据流。这时就可以大胆地进行指
动态调度的基本思想
5段流水：指令按序流出、按序执行
第三章的流水线中，结构冲突和数据冲突都是在ID译码段进行检测的，流出条件为：既没有结构冲突也没有数据冲突
现把指令流出的工作拆成两步
- 检测结构冲突
- 等待数据冲突消失
只要检测到没有结构冲突，就可以让指令流出，且操作数一旦就绪就可以立刻执行
也就是说，把前面的5段露水ID段细分成两个阶段:
- 流出（issue），指令译码，并检查是否存在结构冲突
- 读操作数：等待数据冲突消失，然后读操作数
在读操作数段可能停顿和互相跨越
动态调度的流水线支持多条指令同时处于执行当中，这里我们假设具有多个功能部件。
动态调度的处理机：对于一条会产生异常的指令来说，只有当处理机确切地知道该指令将被执行时，才允许它产生异常行为。
不精确异常(Imprecise Exception)是指:当执行指令i导致发生异常时,处理机的现场(状态)与严格按程序顺序执行时指令i的现场不同。
反之,如果发生异常时,处理机的现场跟严格按程序顺序执行时指令i的现场相同,就称为精确异常(Precise Exception)。
不精确异常使得在异常处理后难以接着继续执行程序。
发生不精确异常的原因:
- 流水线可能已经执行完按程序顺序是位于指令i之后的指令
- 流水线可能还没完成按程序顺序是指令i之前的指令
典型的动态调度算法
- 记分牌算法
- Tomasulo算法（比前者改进了很多）
基本上每次都考这两算法，其中第二个算法考的概率大很多（90%）
记分牌scoreboard
维护三张表：分别记录指令的执行状态、功能部件状态、寄存器状态以及数据相关关系等。所考虑指令有流出、读操作数、执行、写回四个执行状态。
- 记录指令的执行状态 这个表是最重要的，一定不能出错
记录（已取指指令）执行状态。 - 功能部件状态
记录各功能部件的状态 - 结果（目标）寄存器状态表
指出哪个功能部件将把结果写入该目标寄存器
它把前述5段流水线中的译码段ID分解成了两个段:流出和读操作数﹐以避免当某条指令在ID段被停顿时挡住后面无关指令的流动。
- 已经执行完成的指令可以不用画在指令状态表中
- 有的时候，乘法部件和除法部件是合在一起的
- 加法部件既可以做加法也可以做减法
一般第一列都是目的寄存器，功能部件状态表里面的寄存器Fijk的顺序跟指令的顺序一样
指令状态表
功能部件表
- Busy：忙标志，Yes表示已流出，未写入（完成）。
- no：已完成或未流出。
- Op：正在或将要执行的操作。 Fi：目的寄存器（编号）。
- Fj，Fk：两个源寄存器（编号）；
- Qj，Qk：向两个源寄存器Fj、Fk写数据的功能部件。
- Rj，Rk：标志位，“yes”：Fj，Fk中的操作数可用——就绪且未被取走（已产生但未读）。否则，“no”。
结果寄存器状态表
哪个功能部件将把结果写入该目标寄存器。
F0,F2,F8,F10: 目标寄存器 （F4,F6 :空闲，完成或未流出）
每条指令的执行过程
- 流出（Issue，IS）：若功能部件空闲，目的寄存器可用（无WW冲突），就流出指令，并修改记分牌内记录。否则不流出。检测目的寄存器可用性，解决了WW冲突和结构冲突。
- 读操作数（Read Operands，RO） ：若源操作数可用（就绪且未读），就读出并执行。否则，等待写完成后读出（锁定）
- 执行：取到操作数后功能部件开始执行（可能乱序执行）产生出结果后，通知记分牌已完成执行。
在浮点流水线中，这一段可能要占用多个时钟周期。
其他指令如不与正在执行或被锁定指令相关，可提前执行或完成。 - 执行部件完成后，检测目标寄存器，以避免RW冲突。
- 如检测到RW冲突，不许该指令将结果写到目标寄存器。这发生在以下情况：前面的某条指令还没有读取该操作数（即前指令的源操作数寄存器是本指令的目标寄存器）。在这种情况下，记分牌必须等待，直到该冲突消失
- 如果不存在RW冲突（或冲突已消失），把结果写入目的寄存器，并释放该指令使用的所有资源（指令乱序执行成为可能）， 避免了RW冲突。
指令执行过程的冲突分析
- WW冲突会导致记分牌在流出阶段停顿。
- RW冲突会导致记分牌在写结果阶段停顿。
- 真相关引起的WR冲突会导致记分牌在读操作数阶段停顿。
- 资源冲突会导致记分牌在流出阶段停顿。
通过记分牌控制：避免了 WW、WR、RW冲突及结构冲突。
这里有两道例题，见ppt
具体算法*
记分牌算法的限制性
- 记分牌并不能高效处理WW，WR和RW，只能通过停顿保证指令动态调度的正确性。
- 程序代码中可开发的并行性，即是否存在可以并行执行的不相关的指令。
- 记分牌的容量
- 决定了流水线能在多大范围内寻找不相关指令。
- 流水线中可以同时容纳的指令数量称为指令窗口。
- 功能部件的数目和种类。
- 功能部件的总数决定了结构冲突的严重程度。
- 反相关和输出相关
- 引起记分牌中的WW，RW冲突
托马苏格(Tomasulo)算法
电脑没电了，寄，下课再说