计算机系统结构（1月31日）

效率：

计算流水效率的一般公式：E=n个任务占用的时空区/k个流水段的总的时空区 = T0/k*Tk

各流水段执行时间相等，输入n个连续任务：

流水线的效率为：E = n/k+n-1

流水线的最高效率为1

各流水线执行时间不相等，输入n个连续任务：

流水线最佳段数的选择：采用顺序执行方式完成一个任务的时间为t

在同等速度的k段流水线上执行一个任务的时间为：t/k+d，其中：d为流水锁存器的延迟时间

流水线的最大吞吐率：p=1/(t/(k+d))

流水线的总价格估计为：c=a+bk

其中：a为所有功能段本身的总价格，b为每个锁存器的价格

A.G.Larson把流水线的性能价格比PCR定义为：PCR=P/C=(1/(t/(k+d)))*(1/a+bk)

求得到PCR的最大值为：k0=(t×a/d*b)的1/2次幂

流水线性能分析举例

对于单功能线性流水线，输入连续任务的情况，通过上面给出的公式很容易计算出流水线的吞吐率、加速比和效率

例如：用一条4段浮点加法器流水线求8个浮点数的和：

Z=A+B+C+D+E+F+G+H

解：Z=[(A+B)+(C+D)]+[(E+F)+(G+H)]

用一段4段浮点加法器流水线求8个数之和的流水线时空图

7个浮点加法共用了15个时钟周期

流水线的吞吐率为：TP = n/Tk = 7/15*△t

流水线的加速比：S = T0/Tk = 4*7/15 = 1.87

流水线的效率为：E = T0/kTk = 47/4*15 = 0.47

非线性流水线的调度技术：

非线性流水线调度的任务是要找出一个最小的循环周期，按照这周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高

1、非线性流水线的表示

线性流水线能够用流水线连接图唯一表示

连接图不能用唯一表示非线性流水线的工作流程，因此，引入流水线预约表

非线性流水线的冲突：

流水线的启动距离：连续输入两个任务之间的时间间隔

流水线的冲突：几个任务争用同一个流水段

无冲突调度方法：由E.S.Davidson及其学生于1971年提出：非流水线的禁止启动集合：预约表中每一行任务两个X之间的距离都计算出来，去掉重复的

由禁止启动集合得到冲突向量：C=（CmCm-1...C2C1）,其中m是禁止向量中的最大值，如果i在禁止向量中，则Ci=1，否则Ci=0

由冲突向量构造状态图：

把冲突向量送入一个m位逻辑右移移位器：如果移位器移出0，用移位器中的值与初始冲突向量作“按位或”运算，得到一个新的冲突向量；否则不作任何处理，如此重复m次

对于中间形成的每一个新的冲突向量，也要按照这一方法进行处理

在初始冲突向量和所有的新形成的冲突向量之间用带箭头的线连接，当新形成的冲突向量出现重复时可以合并到一起

例如：一条有4个功能段的非线性流水线，每个功能段的延迟时间都相等，它的预约表如下：

  1      2      3     4     5    6    7

S1 X X

S2 X X

S3 X X

S4 X

（1）写出流水线的禁止集合和初始冲突向量

（2）画出调度流水线的状态图

（3）求流水线的最小启动循环和最小平均启动距离

（4）求平均启动距离最小的恒定循环

解：（1）禁止集合为：（2,4,6），初始冲突向量101010

（2）初始冲突向量逻辑右移2,4，6位时，不作任何处理，逻辑右移1,3,5和大于等于7时，要进行处理

初始冲突向量右移1位之后 010101 按位或 101010 = 111111

初始冲突向量右移3位之后 000101 按位或 101010 = 101111

初始冲突向量右移5位之后 000001 按位或 101010 = 101011

初始冲突向量右移7位或大于7位后：还原到它本身

中间冲突向量101111右移5位之后：000001 按位或 101010 = 101011

中间冲突向量101011右移3位之后：000101 按位或 101010 = 101111

中间冲突向量101011右移5位之后：000001 按位或 101010 = 101011

预约表与状态图是唯一对应，但不同的预约表也可能有相同的状态图

简单循环：状态图中各种冲突向量只经过一次的启动循环

简单循环的个数是有限的，由简单循环计算平均启动距离

简单循环 平均启动距离

（1,7） 4

（3,7） 5

（5,7） 6

（3,5,7） 5

（5,3,7） 5

（3,5） 4

（5） 5

（7） 7

最小的启动循环为（1,7）和（3,5），平均启动距离为4

启动距离最小的恒定循环是（5）

优化调度方法

L.E.Shar于1972年提出流水线最小平均启动距离的限制范围

（1）下限是预约表中任意一行里X的最多个数

（2）小于或等于状态图中任意一个简单循环的平均启动距离

（3）最小平均启动距离的上限是冲突向量中1的个数再加上1

1992年，L.E.Shar又证明了上述限制范围。

最有用的是第1条。预约表中x最多的行一定是瓶颈流水段

采用预留算法来调度非线性流水线，可以达到最优调度：

（1）确定最小平均启动距离（MAL），预约表任一行中X的最多个数

（2）确定最小启动循环。一般恒定循环作为最小启动循环

（3）通过插入非计算延迟段——修改预约表实现最小启动循环

对于上面的例子：最小平均启动距离为2.最小启动循环为恒定循环（2）

任一行中与第1个X的距离为2的倍数的周期都要预留出来

在非线性流水线中，X最多的流水段一定是瓶颈流水段

实现最优调度的目标是使瓶颈流水段处于忙碌状态，没有空闲周期

最优调度方法能够使非线性流水线的吞吐率、加速比和效率达到最优

动态调度方法：

一个启动调度C，从C推导出各个起始之间所有可能的时间间隔集合Gc，称为启动间隔集合：

C=（2,3,2,5）

Gc = （2,3,5,7,9,10，14,15,17,19,21,22,24,26...）

间隔并不限于两个相邻的起始

取Gc（mod p），p为循环周期

p=12的循环C=（2,3,2,5）

Gc（mod 12） = {0,2,3,5,7,9,10}

在禁止启动集合为F的流水线中，iff：F（mod p）与Gc（mod p）相交为空时，周期为p和启动间隔集合Gc的启动循环C才是可以允许的。

高级流水线技术

1、超标量流水线

2、超流水线

3、超标量超流水线

超标量处理机

基本结构

三种主流处理机：

超标量处理机：Intel公司的i860、i960、Pentium处理机，motolora公司的MC88110，IBM公司的Power 6000，SUN公司的SPARC、SuperSPARC、UltraSPARC等

超标量：两条流水线以上，通过资源的并行提高指令的并行度

超流水线处理机：SGI公司的MIPS R4000、R5000、R10000等

超流水线：流水线段数比较多

超标量超流水线处理机：DEC公司的Alpha等

超标量超流水线：流水线段数比较多，流水线比较多

流水线多功耗也大

一般流水线处理机：一条指令流水线，一个多功能操作部件，每个时钟周期平均执行指令的条数小于1

多操作部件处理机：一条指令流水线，多个独立的操作部件，可以采用流水线，可以不流水。多操作部件处理机的指令级并行度小于1

超标量处理机典型结构：

多条指令流水线

先进的超标量处理机有：定点处理部件CPU，浮点处理部件FPU，图形加速部件GPU，大量的通用寄存器，两个一级Cache

超标量处理机的指令级并行度ILP大于1

Motorola公司的MC8810，有10个操作部件：

两个寄存器堆：整数部件通用寄存器堆，32个32位寄存器；浮点部件扩展寄存器堆，32个80位寄存器

缓冲深度为4的先行读数栈，缓冲深度为3的后行写数栈

两个独立的高速Cache中，各为8KB，采用两路组相联方式

转移目标指令Cache，存放一条分支以上的指令

单发射与多发射

单发射处理机：每个周期只取一条指令，只译码一条指令，只执行一条指令，只写回一个运算结果

取指令部件和指令译码部件或设置多个独立的操作部件；

操作部件中可以采用流水线结构，也可以不采用流水线结构

目标是每个时钟周期平均执行一条指令，ILP的期望值为1

多发射处理机：每个周期同时取多条指令，同时译码多条指令，同时执行多条指令，同时写回多个运算结果

需要多个取指令部件，多个指令译码部件和多个写结果部件

设置多个指令执行部件，有些指令执行部件采用流水线结构

目标是每个时钟周期平均执行多条指令，ILP的期望值大于1

超标量处理机：一个时钟周期能同时发射多条指令的处理机，必须由两条或两条以上能够同时工作的指令流水线

先行指令窗口：能够从指令Cache中预取多条指令

能够对窗口内的指令进行数据相关性分析和功能部件冲突检测

先行指令窗口的大小：一般为2至8条指令

目前的指令调度技术，每个周期发射2至4条指令比较合理

例如：Intel公司的i860、i960、Pentium，Motolora公司的MC88110、IBM公司的Power 6000等每个周期都发射两条指令；TI公司生产的SuperSPARC，PentiumIII每个周期发射三条指令。

操作部件的个数一般多于每个周期发射的指令条数。通常为4个至16个操作部件。

超标量处理机的指令级并行度：1<ILP<m,m为每个周期发射的指令条数

多流水线调度

多流水线的调度问题是一个NP完全问题，顺序发射（in-order issue）与乱序发射（out-order issue）：指令发射顺序是按照程序中指令排列顺序进行的称为顺序发射

顺序完成（in-order completion）与乱序完成（out-order completion）,指令完成顺序是按照程序中指令排列顺序进行的称为顺序完成

多流水线的调度主要由三种方式：顺序发射顺序完成，顺序发射乱序完成，乱序发射乱序完成

资源冲突

如果操作部件采用流水线结构，发生资源冲突的可能性很小；如果不采用流水线结构，发生资源冲突的可能性就大

超标量处理机性能

单流水线普通标量处理机的指令级并行度记作（1,1）

超标量处理机的指令级并行度记作（m，1）

超流水线处理机的指令级并行度记作（1，n）

而超标量超流水线处理机的指令级并行度记作（m，n）

在理想情况下，N条指令在单流水线标量处理机上的执行时间为：T（1,1）=（k+N-1）△t

在每个周期发射m条指令的超标量处理机上执行的时间为 T（m，1）=（k+（N-m）/m）△t

超标量处理机相对于单流水线标量处理机的加速比为：S（m，1）=T（1,1）/T(m,1)=m(k+N-1)/N+m(k-1)

超标量处理机的加速比的最大值为：S（m，1）max=m

超流水线处理机：

两种定义：在一个周期内能够分时发射多条指令的处理机，指令流水线的功能段数为8段或超过8段的流水线处理机

提高处理机性能的不同方法：超标量处理机：通过增加硬件资源来提高处理机性能；超流水线处理机：通过各部分硬件的重叠工作来提高处理机性能

两种不同并行性：超标量处理机采用的是空间并行性；超流水线处理机采用的是时间并行性

指令执行时序

每隔1/n个时钟周期发射一条指令，即处理机的流水线周期为1/n个时钟周期

在超标量处理机中，流水线的有些功能段还可以进一步细分

典型处理机结构：

MIPS R4000处理机，每个时钟周期包含两个流水段，是一种很标准的超流水线处理机结构。指令流水线有8个流水段

有两个Cache，指令Cache和数据Cache的容量各为8KB，每个时钟周期可以访问Cache两次，因此在一个时钟周期内可以从指令Cache中读出两条指令，从数据Cache中读出或写入两个数据

主要运算部件有整数部件和浮点部件

超流水线处理机性能：

指令级并行度为（1，n）的超流水线处理机，执行N条指令所用的时间为：T（1，n）= （k+（N-1）/n）△t

超流水线处理机相对于单流水线普通标量处理机的加速比为S（1，n）= T（1,1）/T(1,n)= n(k+N-1)/nk+N-1

超流水线处理机的加速比的最大值为：S（1，n）max=n

超标量超流水线处理机：把超标量和超流水线技术结合在一起

超标量超流水处理机在一个时钟周期内分时发射指令m次，每次同时发射指令n条

超标量超流水线处理机每个时钟周期总共发射指令mn条

典型处理机结构：

DEC公司的Alpha处理机采用超标量超流水线结构，主要由四个功能部件和两个cache组成

四个功能部件：整数部件EBOX、浮点部件FBOX、地址部件ABOX和中央控制部件IBOX

中央控制部件IBOX能够同时读出两条指令，同时对两条指令进行译码，作资源冲突检测，进行数据相关性和控制相关性分析。如果资源和相关性允许，IBOX就把两条指令同时发射给EBOX、ABOX和FBOX三个执行部件中的两个

指令流水线采用顺序发射乱序完成的控制方式。

在指令Cache中有一个转移历史表，实现条件转移的动态预测。

在EBOX内还有多条专用数据通路，可以把运算结果直接送到执行部件

Alpha 21064处理机共有三条指令流水线，

（1）整数操作流水线为7个流水段，其中，

取指令为2个流水段

分析指令为2个流水段

运算为2个流水段

写结果为1个流水段

（2）访问存储器流水线为7个流水段

（3）浮点操作流水线分为10个流水段，其中，浮点执行部件FBOX的延迟时间为6个流水段

因为三条指令流水线的平均段数为8，且每个时钟周期发射两条指令。因此Alpha 21064处理机是超标量超流水线处理机所有指令执行部件，包括EBOX、IBOX、ABOX和FBOX中都设置有专用数据通路。

超标量超流水线处理机性能

指令级并行度为（m，n）的超标量超流水线处理机，连续执行N条指令所需要的时间为：T（m，n）=（k+（N-m）/m*n）△t

超标量超流水线处理机相对于单流水线标量处理机的加速比为：s(m,n)=S(1,1)/S(m,n)=(k+N-1)△t/(k+(N-m)/mn)△t=(mn(k+N-1))/(mnk+N-m)

在理想情况下，超标量超流水线处理机加速比的最大值为：S(m,n)max=mn

性能比较上：超标量处理机性能最好（资源并行），超标量超流水线处理机其次，超流水线处理机最差（冲突的概率特别大）