计算机系统结构笔记(三)

¶基本概念

实施流水线的两个基本步骤

第一步，把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。
第二步，多个任务在时间上错开，依次通过各功能段，这样，每个子过程就可以与其它的子过程并行进行

流水线的段(级)

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

流水线的瓶颈

流水线中执行时间最长的段。

时空图: 横坐标代表时间,纵坐标代表流水线的各个段

只有那些有多个密集达到的相同或类似任务的场景中，流水线才能有效的改善系统性能。

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

按用于计算机系统的等级划分，流水线可分为：

部件级: 例如浮点加法流水线
处理机级: 又称为指令流水线,将一条指令的执行过程分为若干个子过程,每个子过程在独立的功能部件中执行.例如5段MIPS流水线(取值,译码,执行,访存,写回)
处理机间流水线: 将多台处理机串接起来,对同一数据流进行处理,每个处理机完成整个任务中的一部分.例如MAP Reduce框架

按所完成的功能划分，流水线可分为单功能流水线与多功能流水线。

只能完成一种固定功能的流水线。如图就是一条典型的单功能流水线，只能完成浮点加法功能。
各段可以进行不同的连接，从而实现不同功能的流水线。

多功能流水线可以进一步细分为静态与动态流水线。区别在于两种任务在时间上能否重叠。

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

按照是否有反馈回路,将流水线分为线性和非线性

数据通过流水线中的各段时，每个段最多只流过一次。前面讲到的流水线例子均为线性流水线。
流水线中除了有串行的连接外，还有反馈回路，这称为非线性流水线。同一个任务可能多次通过同一个段.

按任务流入和流出的顺序是否相同，流水线技术可以划分为：

顺序流水线: 流水线输出端任务流出的顺序与输入端任务流入的顺序完全相同。
乱序流水线: 流水线输出端任务流出的顺序与输入端任务流入的顺序可以不同

¶性能指标

吞吐率

吞吐率通常使用缩写$TP$表示，是指在单位时间内流水线所完成的任务数量或输出结果的数量。
$$
TP = \frac{n}{T_k}
$$

吞吐率分析：各段时间均等.$k$段线性流水线完成$n$个任务所需要的总时间为$T_k = (k+n-1) \Delta t$

实际吞吐率:
$$
TP = \frac{n}{(k+n-1)\Delta t}
$$
最大吞吐率:
$$
TP_{max} = \frac{1}{\Delta t}
$$

根据上面的关系式可知,只有$n$远大于$k$的时候才有$TP$约等于$TP_{max}$,实际上
$$
TP = \frac{n}{k+n-1}TP_{max}
$$

吞吐率分析：各段时间不全相等.

此时最大吞吐率为
$$
TP_{max} = \frac{1}{\max (\Delta t_1,…,\Delta t_2)}
$$

由此引出了流水线瓶颈问题

流水线中执行时间最长的段称为流水线的瓶颈段.

解决流水线瓶颈的方法

细分瓶颈段
重复设置瓶颈段

加速比

完成同样一批任务，不使用流水线所用的时间与使用流水线所用的时间之比。即
$$
S = \frac{T_s}{T_k}
$$

加速比分析：各段时间均等

实际加速比
$$
S = \frac{nk}{k+n-1}
$$
最大加速比
$$
S_{max}= k
$$

效率

流水线中的设备实际使用时间与整个运行时间的比值.

如果各段时间均等,各段的效率$e_i$相同
$$
E=e_1=e_2=…=e_k=\frac{n\Delta t}{T_k} = \frac{n}{k+n-1}
$$
当n远大于k时,有$E_{max} = 1$

效率与其他指标的关系

当流水线各段时间相等时,流水线的效率与吞吐率成正比,等于实际加速比和最大加速比的比值
$$
E = TP \times \Delta t
$$
$$
E = \frac{S}{S_{max}}
$$

更直观的描述可以利用时空图,有以下关系
$$
E = \frac{n个任务所占有的时空区}{k个段总的时空区}
$$

¶例题

适合流水线的算法

先计算$A_i+B_i$

再计算$(A_1+B_1) \times (A_2+B_2)和(A_3+B_3) \times (A_4+B_4)$

最后求总的乘积

画出时空图

$$
TP = \frac{7}{18 \Delta t}
$$
$$
S = \frac{36 \Delta t}{18 \Delta t} =2
$$
$$
E = \frac{4 \times 6 + 3 \times 4}{8\times 18}=0.25
$$

总结:影响(多功能流水线性能的原因)

多功能流水线在做某一种运算时，总有一些段是空闲的
静态流水线在进行功能切换时，要等前一种运算全部流出流水线后才能进行后面的运算
运算之间存在关联，后面有些运算要用到前面运算的结果；
流水线的工作过程有建立与排空部分

¶流水线设计中的重要问题

瓶颈问题

理想情况下，流水线在工作时，其中的任务是同步地每一个时钟周期往前流动一段
当流水线各段不均匀时，机器的时钟周期取决于瓶颈段的延迟时间
在设计流水线时，要尽可能使各段时间相等

流水线的额外开销

流水寄存器需要建立时间和传输延迟
时钟偏移开销:流水线中，时钟到达各流水寄存器的最大差值时

结论

流水线并不能减少（而且一般是增加）单条指令的执行时间，但却能提高吞吐率。
增加流水线的深度（段数）可以提高流水线的性能
流水线的深度受限于流水线的额外开销(当时钟周期小到与额外开销相同时，流水已没意义。因为这时在每一个时钟周期中已没有时间来故有用的工作)

¶单功能非线性流水线的调度

基本概念

启动距离: 向一条非线性流水线的输入端连续输入两个任务之间的时间间隔称为非线性流水线的启动距
禁用启动距离: 会引起非线性流水线功能段使用冲突的启动距离则称为禁用启动距离
启动距离和棼用启动距离一般都用时钟周期数来表示，是一个正整数。

预约表

横向（向右）：时间（一般用时钟周期表示）
纵向（向下）：流水线的段
如果在第n个时钟周期使用第k段，则在第k行和第n列的交叉处的格子里有一个勾

如下图

禁止表:一个由禁用启动距离构成的集合

可以根据预约表写出禁止表,如上例禁止表为F = { 1,5,6,8 }

冲突向量$C$

从由至左
$c_i=0$,允许间隔$i$个时钟周期后送入后续任务
$c_i=1$,不允许间隔$i$个时钟周期后送入后续任务
先构建$C_0$,例如上面的例子的$C_0=10110001$
假设第二个任务是在与第一个任务间隔j个时钟周期流入，这时，由于第一个任务已经在流水线中前进了j个时钟周期，其相应的禁止表中各元素的值都应该减去j，并丢弃小于等于0的值
后续冲突向量表达式:$SHR^{j}(C_0) V C_0$

冲突向量集合的构建

流水线状态图

状态节点(即一个冲突向量)
有向弧(表示转移方向)
权值(引入后续任务的时间间隔)

如下图

调度方案
- 根据流水线状态图，由初始状态出发，任何一个闭合回客即为一种调度方案。
最优调度方案
- （任务进入流水线的）平均时间间隔最小的调度方案
- 列出所有可能的调度方案，计算出每种方案的平均时间间隔，从中找出其最小者即为最优调度方案。

上例中,最佳方案为(3,4),平均时间间隔为3.5个时钟周期.(4,3)也是3.5个时钟周期,但不是最佳方案,因为对于偶数个任务,(3,4)的时钟周期总数少一个.

方案（3,4）是一种不等时间间隔的调度方案，与等间隔的调度方案相比，在控制上要复杂得多

为了简化控制，也可以采用等间隔时间的调度方案，但吞吐率和效率往往会下降不少.

¶相关

两条指令之间存在某种依赖关系,称为相关.

数据相关
名相关
控制相关

需要注意的是,相关不意味着冲突,例如名相关就没有冲突?

数据相关

指令$j$使用指令$i$的结果
指令$j$和$k$相关,而指令$k$又和指令$i$相关

数据相关的检测

寄存器编号
存储器(较复杂)

名

指令所访问的寄存器或存储器单元的名称
如果两条指令使用相同的名,然而没有数据流动,则这两条指令存在名相关
反相关: 指令$j$和指令$i$的名分别用作读和写,称指令$i$和$j$发生了反相关
输出相关: 两条指令的输出名一样

注意不存在输入相关

名相关特点

名相关中一条指令名改变,不影响另一条指令的执行
可以通过换名技术消除名相关

控制相关

由分支指令引起的相关
指令顺序不可以改变

¶流水线冲突

由于相关等原因的存在,使得指令流中的下一条指令不能在指定的时钟周期执行

结构冲突: 因硬件资源不足导致的冲突
数据冲突: 指令在流水线重叠执行由于指令之间的数据相关导致的冲突
控制冲突: 流水线遇到分支指令等影响PC的指令所引起的冲突

可能导致的问题

导致错误的执行结果
降低效率和实际加速比

解决流水线的基本方法是暂停部分指令执行

结构冲突的解决方案

插入流水线气泡(插入暂停周期),这样就拉开了两条冲突指令的距离
设置相互独立的存储器,分别存储指令和数据(哈佛结构)
由于硬件成本的考虑,设计者会允许一定的结构冲突

数据冲突的解决方案

分类(这些都是考虑了编译器重新排序的作用)
- 写后读冲突(对应真数据相关)
- 写后写冲突(对应输出相关)
- 读后写冲突(对应反相关)
定向技术
- 这是一种基于硬件的解决方案
- 缓解数据冲突(减少冲突引起的停顿时间)的典型方法
- 增加了新的指令间传输数据的路径
- 不能解决所有数据冲突(例如时序上生产者的产生晚于消费者的消费)

控制冲突的解决方案

每3到4条指令就有一条是分支指令
最简单的方法就是冻结和排空流水线,即遇到分支时后面的就暂停下来
简单的基于硬件的解决方案
- 通过设置专用的处理单元,在流水线中尽早判断分支指令转移是否成功以及分支目标地址.
采用基于编译器的软件方法
- 在编译过程中完成,对分支的处理方法在程序的执行过程中时终是不变的
- 预测分支失败
  - 实际为不跳转,流水线继续运行(能够减少一个时终周期的延迟,相对于冻结方法)
  - 实际为跳转,流水线将分支指令后取出的所有指令转换为空操作,并将分支目的重新取指令执行
  - 注意,分支结果出来之前不能修改处理机的状态,以便猜错时处理机能够回退到原来的状态
- 预测分支成功
  - 五段流水线中,这样操作没有什么好处…因为分支目标地址和分支是否成功是同时计算出来的
- 延迟分支
  - 从逻辑上延长分支指令的执行时间(原来的分支指令+若干个延迟槽)
  - 无论分支成功还是失败,都能够减少一个时终周期的延迟
  - 调度策略: 从前调度,从目标调度,从失败处调度
  - 无论分支是否成功，从前调度均能消除控制冲突。(这个指令要和当前分支无关,极少!)
  - 只有当分支成功时，从目标处调度才能消除控制沖冲突。
  - 只有当分支失败时，从失败处调度才能消除控制冲突。
  - 进一步优化,分支取消机制.

之所以分支指令会造成控制冲突的原因是,如果分支跳转了,那么后面读取的指令就作废了.这样就要重新读入指令,会造成一定的延时损失.

mooc中提到,如果分支指令出现的频度是30%，且流水线理想CPI=1。流水线的实际CPI=1.9,这个如何理解呢?

首先假设有n个任务,如果不存在分支指令,那么五段流水线完成10个任务所用时间为$T_1 = (5+n-1) \Delta t= n+4 \Delta t$

如果存在分支指令,那么由于分支的冻结,那么一条分支指令会造成3个$\Delta t$的延时,最后所用时间为$T_2 = T_1 + 0.3n \times 3 \Delta t= (n+4+0.9n) \Delta t$

又因为:
$$
\frac{CPI_{理想}}{CPI_{实际}} = \frac{T_1}{T_2}
$$

n趋近无穷大时(即指令足够多),可知$CPI_{实际} = 1.9 CPI_{理想} = 1.9$

同样,容易理解为什么简单的基于硬件的解决方案中,如果把分支指令的判断提前在$ID$段实现,$CPI_{实际}=1.3$,因为此时只会造成一个延时

¶流水线的实现

¶课后作业

解:

首先设计算法,如下所示:

计算$A1 \times B1$,$A2 \times B2$,$A3 \times B3$和$A4 \times B4$
计算$(A1 \times B1)+ (A2 \times B2)$和$(A3 \times B3) + (A4 \times B4)$,然后求出总的和

画出时空图,如下图所示

最后可计算得:
吞吐率 $TP = \frac{7}{18 \Delta t}$
加速比 $S = \frac{28 \Delta t}{18 \Delta t} \approx 1.56$
效率 $E = \frac{4 \times 4+3 \times 4}{5 \times 18} \approx 0.31$

解:

(1) 禁止表$F=\{6,3,1 \}$,$C_0=(100101)$,依次计算后继冲突向量,最后绘制得状态转移图如下

(2) 如下表所示

调度策略	平均延迟时间/$\Delta$
(2,2,5)	3
(2,5)	3.5
(4)	4
(4,5)	4.5
(5)	5

结论:

不等时间间隔最佳调度策略为(2,2,5),最大吞吐率为$\frac{1}{3 \Delta t}$
等时间间隔最佳调度策略为(4),最大吞吐率为$\frac{1}{4 \Delta t}$

(3)
按调度策略(2,2,5),实际吞吐率$TP_1 = \frac{5}{17 \Delta t}$,加速比$S_1 = \frac{10 \times 7 \Delta t}{34 \Delta t} = 2.06$
按调度策略(4),实际吞吐率$TP_2 = \frac{10}{43 \Delta t}$,$S_1 = \frac{10 \times 7 \Delta t}{43 \Delta t} = 1.63$

解:
(1) 流水线时空图如下

每次循环需17个时钟周期,需要进行$\frac{364}{4}=99$次循环,所以总共需要$99 \times 17 +1 = 1684$个时终周期
(2) 流水线时空图如下

类似(1)中计算思路,这里每次循环需要10个时钟周期,因此总的时钟周期为$99 \times 10 + 1 = 991$
(3)
调度为

lw r1,0(r2)
addi r2,r2,#4
addi r1,r1,#1
Sub r4,r3,r2
bnez r4,Loop
sw -4(r2),r1

流水线时空图为

总的时钟周期数为$98 \times 6 + 10 =598$

¶补充

MIPS五段流水线(参考):

IF(Instruction Fetch): 取指令
ID(Instruction Decode): 指令译码
EX(Execute): 执行指令
MEM(Memory): 访存
- load或store指令,则访问
- branch指令,则改变PC
- 否则什么都不做
WB(Write Back): 写回