1
第五章 标量流水线技术 (P253)
5.1 基本名词术语 (P253)
标量处理机,标量处理机指只能直接进行标量运算的处理机。 提高处理机指令执行速度的主要途径有：
① 提高主频；
② 设计更好的算法和功能部件；
③ 指令级并行 ——主要方法,又可分为：
a,流水线技术和超流水线技术；
b,超标量技术 ；
c,VLIW；
指令级并行技术,指能使多条指令并行执行的技术，包括流水技术、多操作部件技术和超长指令字技术；
流水线处理机,指用流水作业方式并行解释多条指令的处理机。
本章学习标量计算机上使用的流水加速技术。主要内容有 流水技术的分类,流水线性能指标计算,非线性流水线的调度算法 。
2
基本名词术语（ P253）
标量处理机,超标量处理机,标量处理机指只能进行标量运算的处理机，超标量处理机指能在一个时钟周期内同时发射多条指令的处理机；
流水线处理机,超流水线处理机,流水线处理机指用流水作业方式并行解释多条指令的处理机，超流水线处理机指能在一个时钟周期内分时发射多条指令的处理机；
超长指令字技术 VLIW：指让一条指令包含多个独立的操作字段，
并且分别控制多个功能部件并行工作的技术。
3
5.1 流水处理的基本思想
4
5
6
流水技术
流水技术,将一个重复的时序过程分解成为若干个子过程，而每个子过程都可有效地在其专用功能段上与其他子过程同时执行。
时－空图 从时间和空间两个方面描述了流水线的工作过程。时－空图中，横坐标代表时间，纵坐标代表流水线的各个段。
CPU中的各个部件按流水处理顺序连接起来，就称为一条 流水线 。
7
流水线结构图 (P278) Δ t 1 Δ t 2 Δ t 3 Δ t 4
入口 Ⅰ Ⅱ Ⅲ Ⅳ 出口图 5.1 流水线结构图
流水线工作时空图 (P278—P279)
8
5.2 流水处理
顺序方式 是解释完一条指令再开始解释下一条 (P254)；
重叠方式 是一种简单的流水方式，它把指令分成 2个子过程，每条指令只与下一条指令相重叠 (P255)。
流水方式 是把一个重复的过程分解为若干个子过程，每个子过程可以与其它子过程同时进行，以此提高单位时间内解释指令的数目 (P277)；
流水线是一种通过改进ＣＰＵ结构来提高程序解释速度的方法。
5.2.1 流水线工作原理处理机解释程序的方式有 顺序方式,重叠方式,流水方式 等。
9
重叠方式流水线
当分析部件完成上一条指令的“分析”后，就立即将之送入执行部件，同时分析部件可以开始处理下一条指令。
虽然从执行一条指令的全过程来看，仍需要 2?t的时间，
但从机器的输出端来看，却是每隔一个?t就能给出一条指令的执行结果。
10
空间 （段号）
Ⅳ 1 2 3 4
Ⅲ 1 2 3 4
Ⅱ 1 2 3 4
Ⅰ 1 2 3 4
16 时间 （拍）
(a) 顺序方式空间 （段号）
Ⅱ 1 2 3 4
Ⅰ 1 2 3 4
10 时间 （拍）
(b) 重叠方式空间 （段号）
Ⅳ 1 2 3 4
Ⅲ 1 2 3 4
Ⅱ 1 2 3 4
Ⅰ 1 2 3 4
7 时间 （拍）
Δ t
(c) 流水方式图 3.2 CPU工作时空图
11
1,流水过程由多个相联系的子过程组成，每个子过程称为流水线的 级 或段,段的数目称为流水线的 深度 。
2,把一个任务分解为几个有联系的子任务，每个子任务由一个专门的功能部件来实现。
3,在流水线的每一个功能部件的后面都要有一个缓冲器，用于保存本段的执行结果。
4,各个功能段所需时间应尽量相等，否则时间长的功能段将成为流水线的,瓶颈,，会造成流水线的,堵塞,和,断流,。这个时间一般为一个时钟周期（节拍） 。
5,在流水线中处理的必须是连续任务，只有不断的提供任务才能充分发挥流水线的效率。
6,流水线需要有,装入时间,和,排空时间,。
流水线的特点
12
5.2 流水技术的分类 (P280)
线性 /非线性（ P280）：
部件级 /处理机级 /处理机间级（宏流水线）（ P281）：
单功能 /多功能（ P282）：
静态 /动态（ P283）：
标量 /向量（ P285）：
同步 /异步（ P285）：
顺序 /乱序（ P285,P304）：
13
2,部件级 /处理机级 /处理机间级（宏流水线） (P281)
功能部件级：运算操作流水线处理机级：指令流水线处理机间级：宏流水线
14
1,线性 /非线性 (P280)——功能段间是否有反馈信号
15
3,单功能 /多功能
(P282)
单功能流水线：
只能完成一种固定功能。
多功能流水线：
流水线各段可以进行不同连接，实现不同功能。 P283
图 5.32
16
4,静态 /动态 (P283)——（对多功能流水）
静态：一段时间内一种固定方式连接，实现一种固定功能；
动态：一段时间内，各段按不同方式连接，同时执行多种功能。
17
5,标量 /向量 (P285) ----数据表示不同
6,同步 /异步 (P285) ——对线性流水线的控制方式不同
7,顺序 /乱序 (P285,P304) ——输出与输入任务的顺序是否相同
18
5.3 逻辑相关 (P263-276)
全局性相关 /局部性相关 (P312,P269/P263,P303)；
控制相关,控制相关是指由条件分支指令,转子程序指令,中断等引起的相关数据相关,在执行本条指令过程中,若用到的指令,操作数,变址偏移量等正好是前面指令的执行结果,则须等待前面指令执行完成,并把结果写到内存或通用寄存器之后,本条指令才能开始执行,这种相关称为数据相关 。
1）,先写后读,相关 (p306) （ 1） 延迟执行
2）“先读后写”相关 （ 2）专用路径
3）“写 -写”相关 （ 3） sw/hw避免相关
指令相关 /数相关 (P264/P263)；
主存数相关 /寄存器数相关 (P265/P266)；
数值相关 /变址值相关 (P266/P268)。
相关的定义,(P263倒数第 4段 )所谓相关（ correlation） 流水线中的相关是指相邻或相近的指令因存在某种关联，后面的指令不能在原指定的时钟周期开始执行。
相关的分类及其对策：
19
5.4.1 吞吐率 TP(P285)
吞吐率（ TP ─ ThroughPut rate）指流水线在单位时间内执行的任务数，可以用输入任务数或输出任务数表示。
，其中 n为任务数,k表示流水线划分的段数,Tk是处理完 n个任务所用时间。
实际吞吐率 /最大吞吐率
5.4 线性流水线性能分析 (P285)--吞吐率 TP
kT
nTP?
20
当满足 且无相关条件时，有tt
i tknT k )1(
5.4 线性流水线性能分析实际吞吐率：
最大吞吐率：
21
流水线各段的执行时间不等
22
流水线各段的执行时间不等
实际吞吐率：
最大吞吐率：
),.,,,,m a x ()1( 11
1
k
k
i
i tttnt
TP n
),.,,,,m a x (m a x 11
1
kttt
TP
23
tTP 1m a x
5.4 线性流水线性能分析 --细分,瓶颈”
流水线各段的执行时间不等，则执行时间最长的段就是流水线的 "瓶颈 "。解决 "瓶颈 "的方法是：
① 再细分,瓶颈”段 ─── 将瓶颈设备再细分为下一级流水线
24
5.4 线性流水线性能分析 --并行设置
② 并行设置 ─── 将瓶颈设备重复设置多套，轮番接受任务注意两种方法的时空图不同。
tTP 1m a x
25
一般表示：
实际加速比：
最大加速比：
=流水深度其中
k
o
T
TS
k
i
io tnT
1
knk nkL i mS
n
)1(
*
m a x
1
*
)1(
**
nk
nk
tnk
tnkS
5.4.2 加速比 (P288)不使用流水线所用的时间与使用流水线所用的时间之比
5.4 线性流水线性能分析 --加速比
26
Pipeline Illustrated:
G a t e
D e l a y
C o m b,L o g i c
n G a t e D e l a y
G a t e
D e l a y
L
G a t e
D e l a y
L
L
G a t e
D e l a y
L
G a t e
D e l a y
L
L B W = ~ ( 1 / n )
n
--
2
n
--
2
n
--
3
n
--
3
n
--
3
B W = ~ ( 2 / n )
B W = ~ ( 3 / n )
5.4 线性流水线性能分析 — 流水深度 k
27
Performance Model
Starting from an unpipelined
version with propagation delay T
and BW = 1/T
Ppipelined=BWpipelined = 1 / (T/ k +S )
where
S = delay through latch
T
S
S
T/k
T/k
k-stage
pipelinedunpipelined
5.4 线性流水线性能分析 — 流水深度
28
Hardware Cost Model
Starting from an unpipelined version
with hardware cost G
Costpipelined = kL + G
where
L = cost of adding each latch,and
k = number of stages
G
L
L
G/k
G/k
k-stage
pipelinedunpipelined
5.4 线性流水线性能分析 — 流水深度
29
Cost/Performance,
C/P = [Lk + G] / [1/(T/k + S)] = (Lk + G) (T/k + S)
= LT + GS + LSk + GT/k
Optimal Cost/Performance,find min,C/P?k
Cost/Performance Trade-off
kd
d L k G+
1
T
k
--- S+
------------
----------------
0 0 L S
G T
k
2
-------–+ +=
k o p t G TL S-------=L S
G T
k 2
-------– 0=
k
C/P
G =an unpipelined version
with hardware cost
T =an unpipelined version
with propagation delay
S = delay through latch
L = cost of adding each latch
5.4 线性流水线性能分析 — 流水深度
30
段效率：,各段平均效率：
其中 表示第 i段设备量占整条流水线全部设备量的百分比 。
当满足 条件 （ 即 "等长 ","等权 "） 时,有：
k
i
i T
tnE
k
i
ii EE
1
)(?
ktt ii
1和
i?
k
S
Tk
Tt
Tk
nE
kE
k
i
k
i k
o
i
k
i
1 1
)(1
上式指出,S=E× k，就是说当效率达到 100%时，流水方式（一个任务 /Δ t） 吞吐率 为顺序方式（一个任务 /(k× Δ t)）的 k倍。
5.4.3 效率（设备利用率,P289）
5.4 线性流水线性能分析 --效率
31
32
例 5.1(P292)
分析：已知下列表达式,有相关,单功能,k = 4,n = 7。 要求最少相关,
用,二叉树算法,以减少相关 。
Z = A + B + C + D + E + F + G + H
① ② ③ ④
⑤ ⑥
⑦
5.4.4 性能分析实例 (P292)
33
例 5.2(P293)
分析：已知下列表达式，二功能，有切换，有相关,k = 8,n = 7。要求用最少切换、最少相关算法。
Z = A? B + C? D + E? F + G? H
乘法,① ② ③ ④
加法,⑤ ⑥
加法,⑦
34
5.5 非线性流水线调度技术 (P294)
调度问题的提出,
一个任务在通过非线性流水线时对有些功能段要 通过多次 （非线性定义），所以容易与紧跟而来的后继任务发生 设备争用 。
调度机构的作用就是合理安排前后任务进入流水线的 相差时间,既要 避免争用,又要使 相差时间尽可能少,以提高吞吐率。
35
1,非线性流水线的表示
S1 S2 S3 S4
一条非线性流水线一般需要一个各功能段间的连接图和一张预约表共同表示。
下图是一条 4个功能段组成的非线性流水线，它有从 S1到 S4 的单方向传输线。但它有两条反馈线和一条前馈线；输出端不一定在最后一个功能段，而可能从任意一个功能段输出。
输出输入
36
2,非线性流水线的预约表
×S4
××S3
××S2
×××S1
7654321
时间功能段
37
3,对于非线性流水线的表示预约表的横坐标表示流水线的 时钟周期,纵坐标表示流水线的 功能段,中间有,×,的表示该功能段在这一个时钟周期处于工作状态，
即在这个时钟周期有任务通过这个功能段；空白的表示该功能段在这一个时钟周期不处于工作状态。
预约表行数是非线性流水线的 段数 ；而列数是一个任务从进入流水线到从流水线中输出所经历的 时钟周期数 。
一张非线性流水线的预约表可能与 多个 非线性流水线连接图相对 应；
同样，一个非线性流水线的连接图也可能对应有 多张 预约表。
38
4,非线性流水线的冲突非线性流水线的启动距离,向一条非线性流水线的输入端连续输入两个任务之间的时间间隔 。
非线性流水线的冲突,当以某一个启动距离向一条非线性流水线连续输入任务时，可能在某一个功能段或某几个功能段中发生有几个任务同时争用同一个功能段的情况。
5,无冲突调度方法目标,找出具有最小平均启动时间的启动循环，按照这样的启动循环向非线性流水线的输入端输入任务，流水线的工作速度最快，而且所有功能段在任何时间都没有冲突。
39
算法,共 5个步骤第 1步,分析 预约表 R（ P295图 5.44）
描述非线性流水线有 2种图形：
(a)连接图,仅给出各段之间的静态空间连接关系；
(b)预约表,就是一个任务通过流水线的时空图，能全面反映该流水线的动态特性 。
要检验 2个任务相距 k拍是否冲突，可将它们的预约表错位 k列重叠（上图）。
第 2步,作 禁止表 F（ P297倒数第 2段） F是 1-N之间可冲突拍数的集合,N是预约表的列数减 1。 具体操作是将同一行中任意 2个标记之间的拍数差记下来，再将各行的这类数字汇成一个集合，即为禁止表。本例中 F = { 3,4,6 }
5.5.1 不改变流水线结构的调度方法 (P295)
时间段
1 2 3 4 5 6 7
S1 1 1 1
S2 1 1
S3 1 1
S4 1
时间段
1 2 3 4 5 6 7
S1 2 2 2
S2 2 2
S3 2 2
S4 2
40
第 3步,作 原始 冲突向量 C（ P298倒数第 3段）
为了设计调度机构，需将禁止表转化为 原始冲突向量 C。
C是含 N个分量的布尔向量，一般形式为 C = (cN...c1)，其中 N是预约表的列数减 1，也可以是 禁止表中的最大元素。第 i个分量取值原则为：
本例中 C = (101100)
Fi
Fic
i,当
，当
1
0
41
动态冲突向量 （初值 000000）
右移寄存器,0 010110 右移出 0
“或”运算器,按位“或” 0接通
1断开常量发生器,101100
原始冲突向量时钟输入流水线 任务排队
1.每个时钟脉冲使流水线中现有任务前进一步，也使右移寄存器移出一位；
2.如果新任务进入，则用它的原始冲突向量与 右移寄存器内容相“或”。
使用 冲突向量 C实现调度的原理图
42
第 4步,作 状态转移图 （ P299图 5.51）
这是为了研究 无穷多个任务时任务之间可能存在的合法间隔情况 。从表达方便考虑，用 动态冲突向量作为状态变量。
具体作图方法是：
(1)先画“根结点”,它就是第一个任务进入后的 右移寄存器状态,数值等于原始冲突向量；
(2)分析当前结点的 各位,如果 ci=0则 发出一个旁标 i值的箭头,ci=1则不能 发出箭头，因为 1表示“禁止”。此外还发出一个旁标,N+1＊” 的 箭头，,N+1
＊” 意为,≥N+1” ；
(3)每个箭头末端产生一个新的结点，其状态等于原结点状态右移 i位后与 原始冲突向量 相“或”；
(4)如果新结点状态与已有的结点重复，
则取消它，箭头指向已有的那个结点。
000000 初态
1 7*
101100
7* 7* 1 5 2 7* 7*
111110 101111
1 5 2
111111 101101
5
43
第 5步,作平均延迟拍数表 （ P300表 5.1）
(1)在状态转移图中寻找全部简单循环填入右表第 1栏。 所谓简单循环是指其中各结点仅通过一次的闭合路径。 注意它不一定要通过根结点 ；
(2)计算各简单循环的平均间隔拍数填入右表第 2栏。 平均间隔拍数等于该简单循环中所有数字之和除以数字个数；
(3)取 平均延迟拍数最少的方案作为最优方案。本例为 (1,1,7)；
(4)调度机构实现,计数器加译码电路 。本例可用模 9计数器，译码条件是计数值等于 0,1,2时允许进入流水线。
简单循环 平均启动距离
（ 1,7） 4
（ 1,1,7） 3
（ 2,7） 4.5
（ 2,5） 3.5
（ 2,5,7） 7
（ 5,7） 6
（ 5） 5
（ 7） 7
（ 5,2,7） 4.7
44
45
时间功能段 1
S1
S2
S3
S4
2 3 4 5 6 7 8 9 10 11 …
1
1
1
1
1,2
1,2
1
1,2,3
2
2
2
2
2
,3
3
3
,3
3,4 …
…
…
…
,4
4
46
5.5.2 改变流水线结构的优化调度方法 ── 预留算法
(P301)
目的,等间隔的最小延迟调度方案
方法,插入延迟器件第 1步,确定 相邻任务间隔拍数,因为最小间隔拍数是一行内,×,的最大数目（第 11行），取最小间隔拍数 。
第 2步,确定插入延迟器件位置的原则（ P302第 2行 ）,从第一个,×,
开始，凡是相距 最小间隔 拍数整倍数位置的,×,都要向后推迟。
实例（ P301倒数第 7行）：
1.确定间隔拍数（最多 3个,×,,所以是 3拍 ）；
2.插入延迟器件（使各行,×,的间距不为 3的倍数 ）；
3.修改预约表（ P302图 5.53(a)）；
4.写调度方案（ 3）。
（示意图见下页）
47
48
a,未插入延迟段（每隔 3 拍启动一个任务）
时间功能段
1 2 3 4
1
5
2
6
3
7
4
1
8
5
2
9
6
3
10
7
4
11
8
5
12
9
6
S1 1 1,2 1,2,3 2,3,4
S2 1 1,2 2,3 3,4
S3 1 2 1 3 2 4 3
S4 1 2 3 4
b,仅插入 1 个延迟段 D1 （每隔 3 拍启动一个任务）
时间功能段
1 2 3 4
1
5
2
6
3
7
4
1
8
5
2
9
6
3
10
7
4
11
8
5
12
9
6
S1 1 2 1 3 1,2 4 2,3
S2 1 2 1 3 2 4 3
S3 1 2 1 3 2 4
S4 1 2 3 4
D1 1 2 3
c,插入 2 个延迟段 D1,D2 （每隔 3 拍启动一个任务）
时间功能段
1 2 3 4
1
5
2
6
3
7
4
1
8
5
2
9
6
3
10
7
4
11
8
5
12
9
6
S1 1 2 1 3 2 1 4 3 2
S2 1 2 1 3 2 4 3
S3 1 2 1 3 2 4
S4 1 2 3 4
D1 1 2 3
D2 1 2
49
5.6 超标量 /超流水 /超长指令字技术（ P320）
本节学习其它指令级并行技术。主要内容有 超标量技术,超流水技术,
多操作部件技术,超长指令字技术 。
指令级并行技术,指能使多条指令并行执行的技术，包括流水技术、多操作部件技术和超长指令字技术；
下面是一些相关的名词术语（ P253）
超标量处理机,指能在一个时钟周期内同时发射多条指令的处理机；
超流水线处理机,超流水线处理机指能在一个时钟周期内分时发射多条指令的处理机；
超长指令字技术 VLIW,指让一条指令包含多个独立的操作字段，并且分别控制多个功能部件并行工作的技术。
50
一、超标量处理机
1,普通标量处理机 --只有一条流水线，每个时钟周期只有一条指令流入流水线。
分为两种类型。
（ 1） 单操作部件流水线处理机
ILP<1
51
（ 2） 多操作部件流水线处理机
ILP<1
52
2．单发射与多发射处理机
（ 1）单发射处理机 —— 只有一套指令部件（取指部件和译码部件），并且每个时钟周期只取一条指令，
只对一条指令进行译码。
53
单发射处理机,ILP<1
54
（ 2）多发射处理机 —— 有多套（ m）指令部件
（取指部件和译码部件），能在每个时钟周期同时取出多条指令，并同时对多条指令进行译码。
55
m>ILP>1
56
二。超标量处理机：
通常，把 一个时钟周期内能够 同时 发射多条指令的处理机称为 超标量处理机 。 （ P324倒 2行）
超标量处理机最基本的要求是必须有 两套或两条以上完整的指令执行部件 。为了能够在一个时钟周期内同时发射多条指令，超标量处理机必须有两条或两条以上能够同时工作的指令流水线。
超标量处理机指令调度要解决的问题
·数据相关
·控制相关
·功能部件冲突 (指令序列要求）
57
超标量技术,时空图见 P323图 5.71（ b）。
指令
9 9 9 9
8 8 8 8
7 7 7 7
6 6 6 6
5 5 5 5
4 4 4 4
3 3 3 3
2 2 2 2
1 1 1 1
1 2 3 4 5 6 节拍
58
超流水技术：（ P333第 1行） 在一个基本时钟周期内能够 分时发射多条指令的处理机称为超流水线处理机 。
在有些资料上把指令流水线的级数为 8级或超过 8级的流水线处理机称为超流水线处理机。
时空图见 P333图 5.79。
指令
9 9 9 9
8 8 8 8
7 7 7 7
6 6 6 6
5 5 5 5
4 4 4 4
3 3 3 3
2 2 2 2
1 1 1 1
1 2 3 4 5 6 节拍
59
超流水线处理机工作方式与超标量处理机不同,
超标量处理机是通过重复设置多个“取指令”部件，
设置多个“译码”、“执行”和“写回结果”部件，
并且让这些功能部件同时工作来提高指令的执行速度，
实际上是以增加硬件资源为代价来换取处理机性能的；
超流水线处理机则只需要 增加少量硬件,是 通过各部分硬件的充分重叠工作来提高处理机性能 的。
从流水线时空图上看，超标量处理机采用的是空间并行性，而超流水线处理机采用的是时间并行性。
60
3．典型结构
在早期生产计算机，巨型计算机 CRAY-1和大型计算机 CDC－
7600属于超流水线处理机,ILP=3。
在目前大量使用的微处理器中，只有 SGI公司 MIPS
（ microprocessor without Interlocked piped stages）系列属超流水线处理机。 （ MIPS是除 Intel公司 X86系列微处理器外，生产量最大的一种微处理器） MIPS系列微处理器主要有 R2000,R3000、
R4000,R5000和最近刚投放市场的 R10000几种。
R4000的指令流水线有 8级，如下图。采用超流水线结构，取指令和访问数据都要跨越两个流水级；每个时钟周期包含两个流水级，处理器取第一条指令（ IF）和取第二条指令（ IS）
61
两个 流水级都要访问指令 Cache，这两个流水级为一个时钟周期。
62
63
四 超标量与超流水处理机超标量超流水线处理机 在一个时钟周期内要发射指令 n次，每次发射指令 m条,因此，超标量超流水线处理机 每个时钟周期总共要发射指令 mn条 。
64
m
n
图中每一时钟周期分为 3个流水线周期，每一流水线周期发射 3条指令。
每个时钟周期能够发射并执行完成 9条指令。理想情况下，超标量超流水线处理机执行程序速度是超标量处理机和超流水线处理机执行程序速度的乘积。
65
超标量 /超流水线 /超标量超流水线处理机机器类型 K段流水线基准标量处理机
M度超标量处理机
N度超流水线处理机
（ M,N）
超标量超流水线处理机机器流水线周期 1个时钟周期
1 1/N 1/N
同时发射指令条数 1条 M 1 M
指令发射等待时间 1个时钟周期
1 1/N 1/N
指令级并行度 1 M N M*N
66
主要特点：
（ 1）单一控制流。只有一个控制器，每个周期启动一条指令。
（ 2）超长指令字被分成多个控制字段，每个字段直接独立地控制每个功能部件。
（ 3）含有大量的数据通路和功能部件，由于编译器在编译时已考虑可能的数据相关和资源相关，故控制硬件较简单。
（ 4）编译阶段完成超长指令中多个可并行执行操作的调度。
超长指令字技术 VLIW
指让一条指令包含多个独立的操作字段，并且分别控制多个功能部件并行工作的技术。
67
VLIW hardware is simple and straightforward,like SIMD
machines.
While SIMD broadcasts one instruction,VLIW separately
directs each functional unit
add r1,r2,r3
FU FU FU FU
add r1,r2,r3
FU FU FU FU
load r4,r5+4 mov r6,r2 mul r7,r8,r9
SIMD
Instruction
Execution
VLIW
Instruction
Execution
68
0 1 2 3 4 5 6 T
3个操作每拍启动一条长指令，执行 3个操作，相当于 3条指令，要求并行度
=3
超长指令字计算机（ VLIW）的原理结构
69
5.7 精简指令系统（ RISC）技术 (P111)
什么是 RISC？（ P107）
CISC和 RISC是指令系统设计的两种思路,前者注重功能多，后者注重速度快。 双方各自发展了很多特色技术。
RISC主要用于工作站和其它高性能计算机，以 UNIX操作系统为主。 IBM-PC个人计算机以 CISC为主，吸收了 RISC若干适宜技术。
20%与 80%规律 （ P112）,统计表明,CISC中 20%常用指令使用率高达 80%，其它为非常用指令。
RISC定义与特点 （ P115）
①一个周期；②一种访存寻址方式；③硬联译码；④简化指令；⑤
固定指令格式；⑥优化译码。
减少 CPI是 RISC思想的精华 （ P116）
分析公式,T = IC · CPI · CYCLE,RISC使 IC增加，其它两项减少。
70
RISC的关键技术 (P118)
1,延时转移技术,将转移指令与它前面的不相关指令对调位置，以利用计算目的地址的时间。
2,指令取消技术,在条件转移指令解释期间提前启动最有可能的一个分支的后继指令，如果“猜”错则及时取消，“猜”
对则赢得了时间。
3,重叠寄存器窗口技术,用寄存器组代替堆栈传递参数，减少访问主存。
4,指令流调整技术,用换名消除相关，消除不了的相关就调整顺序。
5,少数复杂指令用微程序实现,不常用的复杂指令用微程序实现，避免专设电路，对平均速度影响也不大。
71
72
本章小结
(1) 流水处理与相关的概念；
(2) 时空图画法及其应用；
(3) 7种流水线分类方法；
(4) 3个流水线性能指标；
(5) 2种,瓶颈”解决方法 ；
(6) 2种非线性流水线调度方法；
(7) 超标量与超流水技术的概念 ；
(8) 精简指令系统（ RISC）技术。
习题,P343，题 9，题 15。
73
补充
74
通常，把一个时钟周期内能够同时发射多条指令的处理机称为超标量处理机。超标量处理机最基本的要求是必须有 两套或两条 以上完整的指令执行部件。上图是典型超标量处理机的指令流水线，为了能够在一个时钟周期内同时发射多条指令，超标量处理机必须有两条或两条以上能够同时工作的指令流水线。
目前，在多数超标量处理机中，每个时钟周期发射 两条指令,通常不超过 4条 。由于存在有数据相关和条件转移等问题，采用一般的指令调度技术，理论上的最佳情况是每个时钟周期发射 3条指令。对大量程序的模拟统计结果也表明，每个时钟周期发射 2至 4条指令比较合理。
例如,Intel公司的 i860,i960,Pentium处理机,Motolora公司的
MC88110处理机,IBM公司的 Power 6000处理机等每个时钟周期都发射两条指令；美国德州仪器公司（ TI）为 SUN公司生产
SuperSPARC处理机每个时钟周期发射三条指令。
超标量技术
75
超标量处理机指令调度要解决的问题
数据相关
控制相关
功能部件冲突
多发射流水线的调度问题（例子说明）
76
共需 10个周期。有 8个空闲周期，其中 4个是为了保证指令的顺序发射顺序完成。
（ 1）顺序发射顺序完成
77
（ 2） 顺序发射乱序完成共需 9个周期。仅有 3个空闲周期。
78
（ 3）乱序发射乱序完成共需 8个周期，无空闲周期。
79
2,超标量超流水线处理机的性能
（ 1） 性能在一台指令级并行度为（ m,n）的超标量超流水线处理机上，
连续执行 N条没有资源冲突、没有数据相关和控制相关的指令所需要的时间为：
其中,k是指令流水线的时钟周期数，而不是流水线级数。△ t是一个时钟周期的时间长度。上式中的第一项是开始 m条指令通过指令流水线所需要的时间，第二项是执行其余 N - m条指令所需要的时间；这时，每一个时钟周期平均执行完成 m× n条指令，也就是每一个流水线周期平均执行完成 n条指令。
(,) ( )NmT m n k tmn
80
（ 2） 性能比较
81
（ 3） 结论,
① 超标量处理机的相对性能最高，其次是超标量超流水线处理机，
超流水线处理机的相对性能最低,主要原因如下,
a) 超标量处理机在每个时钟周期的一开始就同时发射多条指令，
而超流水线处理机则要把一个时钟周期平均分成多个流水线周期，每个流水线周期发射一条指令。因此，超流水线处理机的启动延迟比超标量处理机大。
b) 条件转移造成的损失，超流水线处理机要比超标量处理机大。
c) 在指令执行过程中的每一个功能段，超标量处理机都重复设置有多个相同的指令执行部件，而超流水线处理机只是把同一个指令执行部件分解为多个流水级。
因此，超标量处理机指令执行部件的冲突要比超流水线处理机小。
82
② 当横坐标给出的设计指令级并行度比较低时，处理机实际指令级并行度的提高比较快。但是，当设计指令级并行度进一步增加时，处理机实际指令级并行度提高的速度越来越慢。因此，在实际设计超标量、超流水线、超标量超流水线处理机的指令级并行度时要适当；
否则，有可能造成花费了大量的硬件，但实际上处理机所能达到的指令级并行度并不高。目前，一般认为 m和 n都不要超过 4。
③ 一个特定程序由于受到本身的数据相关和控制相关的限制，它的指令级并行度的最大值是确定的。这个最大值主要由程序自身的语义来决定，与这个程序运行在那一种处理机上无关。因此，上图中的三条曲线，对于某一个特定的程序，最终都要收拢到同一个点上。
当然，对于各个不同程序，这个收拢点的位置也是不同的。
83
④ 一个程序能够达到的实际指令级并行度还与所采用的调度算法有关。目前，国际上已经提出了多种开发指令级并行性的优化调度算法。对于没有条件转移操作，没有输入输出，没有程序调用和程序中断，单入口单出口的基本块程序，实现最优调度并不十分困难。但是，对于一般程序，要充分开发程序中的指令级并行性，
实现最优调度非常复杂，已经证明，这是一个 NP完全问题。
⑤ 另外，实现最优调度所需要的代价很大，包括硬件代价和软件代价，通常需要编译器和硬件的结合才能获得比较好的调度效果。
目前，开发程序指令级并行性的许多优化调度算法及编译技术还在进一步研究中。
84
超线程技术
,Hyper-Threading Technology（ 超线程技术,以下简称 HTT技术）”
。
对于计算机微处理器而言，程序只是一组编译过的机器代码，可以执行相关的数据计算与操作，这些代码由一条条的指令组成，每一个代码组就是一条 线程 。
单 CPU系统中，在执行指令的时候,CPU先找出相应指令所在的内存位置，执行下一条指令，再转换到另一个位置，在同一时间内 CPU只能对应一个指令。线程可以中断，并把中间结果暂存在另一个特殊位置（堆栈），不同的线程可以交叉运行，实现多任务，但每次运行的线程仍然仅有一条，千万不要把 多任务和多线程 混淆了。
既然一个 CPU是单线程，那么两个 CPU自然就可以双线程啦，如此类推，就会出现四路、八路系统。但双处理器系统的性能并不能达到单处理器的两倍，通常只有 33%的性能增益。
85
为了提高 CPU的性能，厂商通常采用增加 工作频率和缓存容量 的方法来提升速度，但这是治标不治本的方法,CPU只提高了速度，其内在潜力依然未能完全发挥,CPU的 执行单元 没有被充分利用，于是设计者就在 CPU中 加入两个逻辑处理单元,同时管理 CPU的全部资源，直接提高 CPU内核的工作效率。
简而言之：超线程技术就是利用特殊的硬件指令，把两个 逻辑内核 模拟成两个 物理芯片,让单个处理器都能使用线程级并行计算。从而兼容多线程操作系统和软件，提高处理器的性能。
操作系统或者应用软件的多线程可以同时运行于一个 HTT处理器上，
两个逻辑处理器共享 一组处理器执行单元,并行完成加、乘、负载等操作。这样就可以使得运行性能提高 30%，这是因为在同一时间里，
应用程序可以使用芯片的不同部分。
虽然单线程芯片每秒钟能够处理成千上万条指令，但是在任一时刻只能够对一条指令进行操作。而“超线程”技术可以使芯片同时进行多线程处理，使芯片性能得到提升。
86
例如,Office等商业软件主要使用整数运算单元和读写 /存储单元，
几乎不涉及浮点运算单元,3D渲染软件主要使用浮点运算单元，很少涉及整数运算单元，很明显，这种设计造成了很大的浪费。如 P4
处理器内部有 7个执行单元，每个时钟周期内，约有 2个执行单元工作，它们共执行两次操作，那么，其它 5个单元完全没有用到。
超线程技术对商用和家用电脑而言，除了全面提升系统性能以外，
还增加系统平台所能支持用户的数量，大幅降低系统的反应潜伏时间（因为任务能被分为几个隔离的线程来同时执行），增加系统的指令执行数量，还有一点很关键的是，即使对于现有的 IA-32体系软件它也能很好地兼容。因为,HTT处理器还提供一个中断指令，在执行适合单处理器的任务时，暂停其中一个逻辑内核，让操作系统识别为单处理器，在执行适合多处理器的任务时，重新打开逻辑内核，利用 HTT来增加整体效率。
87
支持超线程技术需软硬件的支持，硬件方面需要 主板北桥芯片 的支持。
超线程技术还需要主板对 CPU的电源 支持，需要主板能提供给处理器高达 70A的电流，否则系统可能不能长期稳定工作。除此之处还需要主板 BIOS的支持，需要 BIOS加入特定的支持 HTT处理器的代码。当 BIOS检测到是超线程处理器时，在 BIOS设置菜单中出现 CPU Hyper-Threading（ Enabled or Disabled）的选项。
超线程技术还需要 操作系统 的支持。目前支持超线程技术的有
Windows XP和 Linux 2.4.X。这不同于传统的处理器安装的
Windows XP，使用超线程技术的处理器安装完 Windows XP后在设备管理器中能显示有两个处理器和 ACPI Multiprocessor PC。
第五章 标量流水线技术 (P253)
5.1 基本名词术语 (P253)
标量处理机,标量处理机指只能直接进行标量运算的处理机。 提高处理机指令执行速度的主要途径有：
① 提高主频；
② 设计更好的算法和功能部件；
③ 指令级并行 ——主要方法,又可分为：
a,流水线技术和超流水线技术；
b,超标量技术 ；
c,VLIW；
指令级并行技术,指能使多条指令并行执行的技术，包括流水技术、多操作部件技术和超长指令字技术；
流水线处理机,指用流水作业方式并行解释多条指令的处理机。
本章学习标量计算机上使用的流水加速技术。主要内容有 流水技术的分类,流水线性能指标计算,非线性流水线的调度算法 。
2
基本名词术语（ P253）
标量处理机,超标量处理机,标量处理机指只能进行标量运算的处理机，超标量处理机指能在一个时钟周期内同时发射多条指令的处理机；
流水线处理机,超流水线处理机,流水线处理机指用流水作业方式并行解释多条指令的处理机，超流水线处理机指能在一个时钟周期内分时发射多条指令的处理机；
超长指令字技术 VLIW：指让一条指令包含多个独立的操作字段，
并且分别控制多个功能部件并行工作的技术。
3
5.1 流水处理的基本思想
4
5
6
流水技术
流水技术,将一个重复的时序过程分解成为若干个子过程，而每个子过程都可有效地在其专用功能段上与其他子过程同时执行。
时－空图 从时间和空间两个方面描述了流水线的工作过程。时－空图中，横坐标代表时间，纵坐标代表流水线的各个段。
CPU中的各个部件按流水处理顺序连接起来，就称为一条 流水线 。
7
流水线结构图 (P278) Δ t 1 Δ t 2 Δ t 3 Δ t 4
入口 Ⅰ Ⅱ Ⅲ Ⅳ 出口图 5.1 流水线结构图
流水线工作时空图 (P278—P279)
8
5.2 流水处理
顺序方式 是解释完一条指令再开始解释下一条 (P254)；
重叠方式 是一种简单的流水方式，它把指令分成 2个子过程，每条指令只与下一条指令相重叠 (P255)。
流水方式 是把一个重复的过程分解为若干个子过程，每个子过程可以与其它子过程同时进行，以此提高单位时间内解释指令的数目 (P277)；
流水线是一种通过改进ＣＰＵ结构来提高程序解释速度的方法。
5.2.1 流水线工作原理处理机解释程序的方式有 顺序方式,重叠方式,流水方式 等。
9
重叠方式流水线
当分析部件完成上一条指令的“分析”后，就立即将之送入执行部件，同时分析部件可以开始处理下一条指令。
虽然从执行一条指令的全过程来看，仍需要 2?t的时间，
但从机器的输出端来看，却是每隔一个?t就能给出一条指令的执行结果。
10
空间 （段号）
Ⅳ 1 2 3 4
Ⅲ 1 2 3 4
Ⅱ 1 2 3 4
Ⅰ 1 2 3 4
16 时间 （拍）
(a) 顺序方式空间 （段号）
Ⅱ 1 2 3 4
Ⅰ 1 2 3 4
10 时间 （拍）
(b) 重叠方式空间 （段号）
Ⅳ 1 2 3 4
Ⅲ 1 2 3 4
Ⅱ 1 2 3 4
Ⅰ 1 2 3 4
7 时间 （拍）
Δ t
(c) 流水方式图 3.2 CPU工作时空图
11
1,流水过程由多个相联系的子过程组成，每个子过程称为流水线的 级 或段,段的数目称为流水线的 深度 。
2,把一个任务分解为几个有联系的子任务，每个子任务由一个专门的功能部件来实现。
3,在流水线的每一个功能部件的后面都要有一个缓冲器，用于保存本段的执行结果。
4,各个功能段所需时间应尽量相等，否则时间长的功能段将成为流水线的,瓶颈,，会造成流水线的,堵塞,和,断流,。这个时间一般为一个时钟周期（节拍） 。
5,在流水线中处理的必须是连续任务，只有不断的提供任务才能充分发挥流水线的效率。
6,流水线需要有,装入时间,和,排空时间,。
流水线的特点
12
5.2 流水技术的分类 (P280)
线性 /非线性（ P280）：
部件级 /处理机级 /处理机间级（宏流水线）（ P281）：
单功能 /多功能（ P282）：
静态 /动态（ P283）：
标量 /向量（ P285）：
同步 /异步（ P285）：
顺序 /乱序（ P285,P304）：
13
2,部件级 /处理机级 /处理机间级（宏流水线） (P281)
功能部件级：运算操作流水线处理机级：指令流水线处理机间级：宏流水线
14
1,线性 /非线性 (P280)——功能段间是否有反馈信号
15
3,单功能 /多功能
(P282)
单功能流水线：
只能完成一种固定功能。
多功能流水线：
流水线各段可以进行不同连接，实现不同功能。 P283
图 5.32
16
4,静态 /动态 (P283)——（对多功能流水）
静态：一段时间内一种固定方式连接，实现一种固定功能；
动态：一段时间内，各段按不同方式连接，同时执行多种功能。
17
5,标量 /向量 (P285) ----数据表示不同
6,同步 /异步 (P285) ——对线性流水线的控制方式不同
7,顺序 /乱序 (P285,P304) ——输出与输入任务的顺序是否相同
18
5.3 逻辑相关 (P263-276)
全局性相关 /局部性相关 (P312,P269/P263,P303)；
控制相关,控制相关是指由条件分支指令,转子程序指令,中断等引起的相关数据相关,在执行本条指令过程中,若用到的指令,操作数,变址偏移量等正好是前面指令的执行结果,则须等待前面指令执行完成,并把结果写到内存或通用寄存器之后,本条指令才能开始执行,这种相关称为数据相关 。
1）,先写后读,相关 (p306) （ 1） 延迟执行
2）“先读后写”相关 （ 2）专用路径
3）“写 -写”相关 （ 3） sw/hw避免相关
指令相关 /数相关 (P264/P263)；
主存数相关 /寄存器数相关 (P265/P266)；
数值相关 /变址值相关 (P266/P268)。
相关的定义,(P263倒数第 4段 )所谓相关（ correlation） 流水线中的相关是指相邻或相近的指令因存在某种关联，后面的指令不能在原指定的时钟周期开始执行。
相关的分类及其对策：
19
5.4.1 吞吐率 TP(P285)
吞吐率（ TP ─ ThroughPut rate）指流水线在单位时间内执行的任务数，可以用输入任务数或输出任务数表示。
，其中 n为任务数,k表示流水线划分的段数,Tk是处理完 n个任务所用时间。
实际吞吐率 /最大吞吐率
5.4 线性流水线性能分析 (P285)--吞吐率 TP
kT
nTP?
20
当满足 且无相关条件时，有tt
i tknT k )1(
5.4 线性流水线性能分析实际吞吐率：
最大吞吐率：
21
流水线各段的执行时间不等
22
流水线各段的执行时间不等
实际吞吐率：
最大吞吐率：
),.,,,,m a x ()1( 11
1
k
k
i
i tttnt
TP n
),.,,,,m a x (m a x 11
1
kttt
TP
23
tTP 1m a x
5.4 线性流水线性能分析 --细分,瓶颈”
流水线各段的执行时间不等，则执行时间最长的段就是流水线的 "瓶颈 "。解决 "瓶颈 "的方法是：
① 再细分,瓶颈”段 ─── 将瓶颈设备再细分为下一级流水线
24
5.4 线性流水线性能分析 --并行设置
② 并行设置 ─── 将瓶颈设备重复设置多套，轮番接受任务注意两种方法的时空图不同。
tTP 1m a x
25
一般表示：
实际加速比：
最大加速比：
=流水深度其中
k
o
T
TS
k
i
io tnT
1
knk nkL i mS
n
)1(
*
m a x
1
*
)1(
**
nk
nk
tnk
tnkS
5.4.2 加速比 (P288)不使用流水线所用的时间与使用流水线所用的时间之比
5.4 线性流水线性能分析 --加速比
26
Pipeline Illustrated:
G a t e
D e l a y
C o m b,L o g i c
n G a t e D e l a y
G a t e
D e l a y
L
G a t e
D e l a y
L
L
G a t e
D e l a y
L
G a t e
D e l a y
L
L B W = ~ ( 1 / n )
n
--
2
n
--
2
n
--
3
n
--
3
n
--
3
B W = ~ ( 2 / n )
B W = ~ ( 3 / n )
5.4 线性流水线性能分析 — 流水深度 k
27
Performance Model
Starting from an unpipelined
version with propagation delay T
and BW = 1/T
Ppipelined=BWpipelined = 1 / (T/ k +S )
where
S = delay through latch
T
S
S
T/k
T/k
k-stage
pipelinedunpipelined
5.4 线性流水线性能分析 — 流水深度
28
Hardware Cost Model
Starting from an unpipelined version
with hardware cost G
Costpipelined = kL + G
where
L = cost of adding each latch,and
k = number of stages
G
L
L
G/k
G/k
k-stage
pipelinedunpipelined
5.4 线性流水线性能分析 — 流水深度
29
Cost/Performance,
C/P = [Lk + G] / [1/(T/k + S)] = (Lk + G) (T/k + S)
= LT + GS + LSk + GT/k
Optimal Cost/Performance,find min,C/P?k
Cost/Performance Trade-off
kd
d L k G+
1
T
k
--- S+
------------
----------------
0 0 L S
G T
k
2
-------–+ +=
k o p t G TL S-------=L S
G T
k 2
-------– 0=
k
C/P
G =an unpipelined version
with hardware cost
T =an unpipelined version
with propagation delay
S = delay through latch
L = cost of adding each latch
5.4 线性流水线性能分析 — 流水深度
30
段效率：,各段平均效率：
其中 表示第 i段设备量占整条流水线全部设备量的百分比 。
当满足 条件 （ 即 "等长 ","等权 "） 时,有：
k
i
i T
tnE
k
i
ii EE
1
)(?
ktt ii
1和
i?
k
S
Tk
Tt
Tk
nE
kE
k
i
k
i k
o
i
k
i
1 1
)(1
上式指出,S=E× k，就是说当效率达到 100%时，流水方式（一个任务 /Δ t） 吞吐率 为顺序方式（一个任务 /(k× Δ t)）的 k倍。
5.4.3 效率（设备利用率,P289）
5.4 线性流水线性能分析 --效率
31
32
例 5.1(P292)
分析：已知下列表达式,有相关,单功能,k = 4,n = 7。 要求最少相关,
用,二叉树算法,以减少相关 。
Z = A + B + C + D + E + F + G + H
① ② ③ ④
⑤ ⑥
⑦
5.4.4 性能分析实例 (P292)
33
例 5.2(P293)
分析：已知下列表达式，二功能，有切换，有相关,k = 8,n = 7。要求用最少切换、最少相关算法。
Z = A? B + C? D + E? F + G? H
乘法,① ② ③ ④
加法,⑤ ⑥
加法,⑦
34
5.5 非线性流水线调度技术 (P294)
调度问题的提出,
一个任务在通过非线性流水线时对有些功能段要 通过多次 （非线性定义），所以容易与紧跟而来的后继任务发生 设备争用 。
调度机构的作用就是合理安排前后任务进入流水线的 相差时间,既要 避免争用,又要使 相差时间尽可能少,以提高吞吐率。
35
1,非线性流水线的表示
S1 S2 S3 S4
一条非线性流水线一般需要一个各功能段间的连接图和一张预约表共同表示。
下图是一条 4个功能段组成的非线性流水线，它有从 S1到 S4 的单方向传输线。但它有两条反馈线和一条前馈线；输出端不一定在最后一个功能段，而可能从任意一个功能段输出。
输出输入
36
2,非线性流水线的预约表
×S4
××S3
××S2
×××S1
7654321
时间功能段
37
3,对于非线性流水线的表示预约表的横坐标表示流水线的 时钟周期,纵坐标表示流水线的 功能段,中间有,×,的表示该功能段在这一个时钟周期处于工作状态，
即在这个时钟周期有任务通过这个功能段；空白的表示该功能段在这一个时钟周期不处于工作状态。
预约表行数是非线性流水线的 段数 ；而列数是一个任务从进入流水线到从流水线中输出所经历的 时钟周期数 。
一张非线性流水线的预约表可能与 多个 非线性流水线连接图相对 应；
同样，一个非线性流水线的连接图也可能对应有 多张 预约表。
38
4,非线性流水线的冲突非线性流水线的启动距离,向一条非线性流水线的输入端连续输入两个任务之间的时间间隔 。
非线性流水线的冲突,当以某一个启动距离向一条非线性流水线连续输入任务时，可能在某一个功能段或某几个功能段中发生有几个任务同时争用同一个功能段的情况。
5,无冲突调度方法目标,找出具有最小平均启动时间的启动循环，按照这样的启动循环向非线性流水线的输入端输入任务，流水线的工作速度最快，而且所有功能段在任何时间都没有冲突。
39
算法,共 5个步骤第 1步,分析 预约表 R（ P295图 5.44）
描述非线性流水线有 2种图形：
(a)连接图,仅给出各段之间的静态空间连接关系；
(b)预约表,就是一个任务通过流水线的时空图，能全面反映该流水线的动态特性 。
要检验 2个任务相距 k拍是否冲突，可将它们的预约表错位 k列重叠（上图）。
第 2步,作 禁止表 F（ P297倒数第 2段） F是 1-N之间可冲突拍数的集合,N是预约表的列数减 1。 具体操作是将同一行中任意 2个标记之间的拍数差记下来，再将各行的这类数字汇成一个集合，即为禁止表。本例中 F = { 3,4,6 }
5.5.1 不改变流水线结构的调度方法 (P295)
时间段
1 2 3 4 5 6 7
S1 1 1 1
S2 1 1
S3 1 1
S4 1
时间段
1 2 3 4 5 6 7
S1 2 2 2
S2 2 2
S3 2 2
S4 2
40
第 3步,作 原始 冲突向量 C（ P298倒数第 3段）
为了设计调度机构，需将禁止表转化为 原始冲突向量 C。
C是含 N个分量的布尔向量，一般形式为 C = (cN...c1)，其中 N是预约表的列数减 1，也可以是 禁止表中的最大元素。第 i个分量取值原则为：
本例中 C = (101100)
Fi
Fic
i,当
，当
1
0
41
动态冲突向量 （初值 000000）
右移寄存器,0 010110 右移出 0
“或”运算器,按位“或” 0接通
1断开常量发生器,101100
原始冲突向量时钟输入流水线 任务排队
1.每个时钟脉冲使流水线中现有任务前进一步，也使右移寄存器移出一位；
2.如果新任务进入，则用它的原始冲突向量与 右移寄存器内容相“或”。
使用 冲突向量 C实现调度的原理图
42
第 4步,作 状态转移图 （ P299图 5.51）
这是为了研究 无穷多个任务时任务之间可能存在的合法间隔情况 。从表达方便考虑，用 动态冲突向量作为状态变量。
具体作图方法是：
(1)先画“根结点”,它就是第一个任务进入后的 右移寄存器状态,数值等于原始冲突向量；
(2)分析当前结点的 各位,如果 ci=0则 发出一个旁标 i值的箭头,ci=1则不能 发出箭头，因为 1表示“禁止”。此外还发出一个旁标,N+1＊” 的 箭头，,N+1
＊” 意为,≥N+1” ；
(3)每个箭头末端产生一个新的结点，其状态等于原结点状态右移 i位后与 原始冲突向量 相“或”；
(4)如果新结点状态与已有的结点重复，
则取消它，箭头指向已有的那个结点。
000000 初态
1 7*
101100
7* 7* 1 5 2 7* 7*
111110 101111
1 5 2
111111 101101
5
43
第 5步,作平均延迟拍数表 （ P300表 5.1）
(1)在状态转移图中寻找全部简单循环填入右表第 1栏。 所谓简单循环是指其中各结点仅通过一次的闭合路径。 注意它不一定要通过根结点 ；
(2)计算各简单循环的平均间隔拍数填入右表第 2栏。 平均间隔拍数等于该简单循环中所有数字之和除以数字个数；
(3)取 平均延迟拍数最少的方案作为最优方案。本例为 (1,1,7)；
(4)调度机构实现,计数器加译码电路 。本例可用模 9计数器，译码条件是计数值等于 0,1,2时允许进入流水线。
简单循环 平均启动距离
（ 1,7） 4
（ 1,1,7） 3
（ 2,7） 4.5
（ 2,5） 3.5
（ 2,5,7） 7
（ 5,7） 6
（ 5） 5
（ 7） 7
（ 5,2,7） 4.7
44
45
时间功能段 1
S1
S2
S3
S4
2 3 4 5 6 7 8 9 10 11 …
1
1
1
1
1,2
1,2
1
1,2,3
2
2
2
2
2
,3
3
3
,3
3,4 …
…
…
…
,4
4
46
5.5.2 改变流水线结构的优化调度方法 ── 预留算法
(P301)
目的,等间隔的最小延迟调度方案
方法,插入延迟器件第 1步,确定 相邻任务间隔拍数,因为最小间隔拍数是一行内,×,的最大数目（第 11行），取最小间隔拍数 。
第 2步,确定插入延迟器件位置的原则（ P302第 2行 ）,从第一个,×,
开始，凡是相距 最小间隔 拍数整倍数位置的,×,都要向后推迟。
实例（ P301倒数第 7行）：
1.确定间隔拍数（最多 3个,×,,所以是 3拍 ）；
2.插入延迟器件（使各行,×,的间距不为 3的倍数 ）；
3.修改预约表（ P302图 5.53(a)）；
4.写调度方案（ 3）。
（示意图见下页）
47
48
a,未插入延迟段（每隔 3 拍启动一个任务）
时间功能段
1 2 3 4
1
5
2
6
3
7
4
1
8
5
2
9
6
3
10
7
4
11
8
5
12
9
6
S1 1 1,2 1,2,3 2,3,4
S2 1 1,2 2,3 3,4
S3 1 2 1 3 2 4 3
S4 1 2 3 4
b,仅插入 1 个延迟段 D1 （每隔 3 拍启动一个任务）
时间功能段
1 2 3 4
1
5
2
6
3
7
4
1
8
5
2
9
6
3
10
7
4
11
8
5
12
9
6
S1 1 2 1 3 1,2 4 2,3
S2 1 2 1 3 2 4 3
S3 1 2 1 3 2 4
S4 1 2 3 4
D1 1 2 3
c,插入 2 个延迟段 D1,D2 （每隔 3 拍启动一个任务）
时间功能段
1 2 3 4
1
5
2
6
3
7
4
1
8
5
2
9
6
3
10
7
4
11
8
5
12
9
6
S1 1 2 1 3 2 1 4 3 2
S2 1 2 1 3 2 4 3
S3 1 2 1 3 2 4
S4 1 2 3 4
D1 1 2 3
D2 1 2
49
5.6 超标量 /超流水 /超长指令字技术（ P320）
本节学习其它指令级并行技术。主要内容有 超标量技术,超流水技术,
多操作部件技术,超长指令字技术 。
指令级并行技术,指能使多条指令并行执行的技术，包括流水技术、多操作部件技术和超长指令字技术；
下面是一些相关的名词术语（ P253）
超标量处理机,指能在一个时钟周期内同时发射多条指令的处理机；
超流水线处理机,超流水线处理机指能在一个时钟周期内分时发射多条指令的处理机；
超长指令字技术 VLIW,指让一条指令包含多个独立的操作字段，并且分别控制多个功能部件并行工作的技术。
50
一、超标量处理机
1,普通标量处理机 --只有一条流水线，每个时钟周期只有一条指令流入流水线。
分为两种类型。
（ 1） 单操作部件流水线处理机
ILP<1
51
（ 2） 多操作部件流水线处理机
ILP<1
52
2．单发射与多发射处理机
（ 1）单发射处理机 —— 只有一套指令部件（取指部件和译码部件），并且每个时钟周期只取一条指令，
只对一条指令进行译码。
53
单发射处理机,ILP<1
54
（ 2）多发射处理机 —— 有多套（ m）指令部件
（取指部件和译码部件），能在每个时钟周期同时取出多条指令，并同时对多条指令进行译码。
55
m>ILP>1
56
二。超标量处理机：
通常，把 一个时钟周期内能够 同时 发射多条指令的处理机称为 超标量处理机 。 （ P324倒 2行）
超标量处理机最基本的要求是必须有 两套或两条以上完整的指令执行部件 。为了能够在一个时钟周期内同时发射多条指令，超标量处理机必须有两条或两条以上能够同时工作的指令流水线。
超标量处理机指令调度要解决的问题
·数据相关
·控制相关
·功能部件冲突 (指令序列要求）
57
超标量技术,时空图见 P323图 5.71（ b）。
指令
9 9 9 9
8 8 8 8
7 7 7 7
6 6 6 6
5 5 5 5
4 4 4 4
3 3 3 3
2 2 2 2
1 1 1 1
1 2 3 4 5 6 节拍
58
超流水技术：（ P333第 1行） 在一个基本时钟周期内能够 分时发射多条指令的处理机称为超流水线处理机 。
在有些资料上把指令流水线的级数为 8级或超过 8级的流水线处理机称为超流水线处理机。
时空图见 P333图 5.79。
指令
9 9 9 9
8 8 8 8
7 7 7 7
6 6 6 6
5 5 5 5
4 4 4 4
3 3 3 3
2 2 2 2
1 1 1 1
1 2 3 4 5 6 节拍
59
超流水线处理机工作方式与超标量处理机不同,
超标量处理机是通过重复设置多个“取指令”部件，
设置多个“译码”、“执行”和“写回结果”部件，
并且让这些功能部件同时工作来提高指令的执行速度，
实际上是以增加硬件资源为代价来换取处理机性能的；
超流水线处理机则只需要 增加少量硬件,是 通过各部分硬件的充分重叠工作来提高处理机性能 的。
从流水线时空图上看，超标量处理机采用的是空间并行性，而超流水线处理机采用的是时间并行性。
60
3．典型结构
在早期生产计算机，巨型计算机 CRAY-1和大型计算机 CDC－
7600属于超流水线处理机,ILP=3。
在目前大量使用的微处理器中，只有 SGI公司 MIPS
（ microprocessor without Interlocked piped stages）系列属超流水线处理机。 （ MIPS是除 Intel公司 X86系列微处理器外，生产量最大的一种微处理器） MIPS系列微处理器主要有 R2000,R3000、
R4000,R5000和最近刚投放市场的 R10000几种。
R4000的指令流水线有 8级，如下图。采用超流水线结构，取指令和访问数据都要跨越两个流水级；每个时钟周期包含两个流水级，处理器取第一条指令（ IF）和取第二条指令（ IS）
61
两个 流水级都要访问指令 Cache，这两个流水级为一个时钟周期。
62
63
四 超标量与超流水处理机超标量超流水线处理机 在一个时钟周期内要发射指令 n次，每次发射指令 m条,因此，超标量超流水线处理机 每个时钟周期总共要发射指令 mn条 。
64
m
n
图中每一时钟周期分为 3个流水线周期，每一流水线周期发射 3条指令。
每个时钟周期能够发射并执行完成 9条指令。理想情况下，超标量超流水线处理机执行程序速度是超标量处理机和超流水线处理机执行程序速度的乘积。
65
超标量 /超流水线 /超标量超流水线处理机机器类型 K段流水线基准标量处理机
M度超标量处理机
N度超流水线处理机
（ M,N）
超标量超流水线处理机机器流水线周期 1个时钟周期
1 1/N 1/N
同时发射指令条数 1条 M 1 M
指令发射等待时间 1个时钟周期
1 1/N 1/N
指令级并行度 1 M N M*N
66
主要特点：
（ 1）单一控制流。只有一个控制器，每个周期启动一条指令。
（ 2）超长指令字被分成多个控制字段，每个字段直接独立地控制每个功能部件。
（ 3）含有大量的数据通路和功能部件，由于编译器在编译时已考虑可能的数据相关和资源相关，故控制硬件较简单。
（ 4）编译阶段完成超长指令中多个可并行执行操作的调度。
超长指令字技术 VLIW
指让一条指令包含多个独立的操作字段，并且分别控制多个功能部件并行工作的技术。
67
VLIW hardware is simple and straightforward,like SIMD
machines.
While SIMD broadcasts one instruction,VLIW separately
directs each functional unit
add r1,r2,r3
FU FU FU FU
add r1,r2,r3
FU FU FU FU
load r4,r5+4 mov r6,r2 mul r7,r8,r9
SIMD
Instruction
Execution
VLIW
Instruction
Execution
68
0 1 2 3 4 5 6 T
3个操作每拍启动一条长指令，执行 3个操作，相当于 3条指令，要求并行度
=3
超长指令字计算机（ VLIW）的原理结构
69
5.7 精简指令系统（ RISC）技术 (P111)
什么是 RISC？（ P107）
CISC和 RISC是指令系统设计的两种思路,前者注重功能多，后者注重速度快。 双方各自发展了很多特色技术。
RISC主要用于工作站和其它高性能计算机，以 UNIX操作系统为主。 IBM-PC个人计算机以 CISC为主，吸收了 RISC若干适宜技术。
20%与 80%规律 （ P112）,统计表明,CISC中 20%常用指令使用率高达 80%，其它为非常用指令。
RISC定义与特点 （ P115）
①一个周期；②一种访存寻址方式；③硬联译码；④简化指令；⑤
固定指令格式；⑥优化译码。
减少 CPI是 RISC思想的精华 （ P116）
分析公式,T = IC · CPI · CYCLE,RISC使 IC增加，其它两项减少。
70
RISC的关键技术 (P118)
1,延时转移技术,将转移指令与它前面的不相关指令对调位置，以利用计算目的地址的时间。
2,指令取消技术,在条件转移指令解释期间提前启动最有可能的一个分支的后继指令，如果“猜”错则及时取消，“猜”
对则赢得了时间。
3,重叠寄存器窗口技术,用寄存器组代替堆栈传递参数，减少访问主存。
4,指令流调整技术,用换名消除相关，消除不了的相关就调整顺序。
5,少数复杂指令用微程序实现,不常用的复杂指令用微程序实现，避免专设电路，对平均速度影响也不大。
71
72
本章小结
(1) 流水处理与相关的概念；
(2) 时空图画法及其应用；
(3) 7种流水线分类方法；
(4) 3个流水线性能指标；
(5) 2种,瓶颈”解决方法 ；
(6) 2种非线性流水线调度方法；
(7) 超标量与超流水技术的概念 ；
(8) 精简指令系统（ RISC）技术。
习题,P343，题 9，题 15。
73
补充
74
通常，把一个时钟周期内能够同时发射多条指令的处理机称为超标量处理机。超标量处理机最基本的要求是必须有 两套或两条 以上完整的指令执行部件。上图是典型超标量处理机的指令流水线，为了能够在一个时钟周期内同时发射多条指令，超标量处理机必须有两条或两条以上能够同时工作的指令流水线。
目前，在多数超标量处理机中，每个时钟周期发射 两条指令,通常不超过 4条 。由于存在有数据相关和条件转移等问题，采用一般的指令调度技术，理论上的最佳情况是每个时钟周期发射 3条指令。对大量程序的模拟统计结果也表明，每个时钟周期发射 2至 4条指令比较合理。
例如,Intel公司的 i860,i960,Pentium处理机,Motolora公司的
MC88110处理机,IBM公司的 Power 6000处理机等每个时钟周期都发射两条指令；美国德州仪器公司（ TI）为 SUN公司生产
SuperSPARC处理机每个时钟周期发射三条指令。
超标量技术
75
超标量处理机指令调度要解决的问题
数据相关
控制相关
功能部件冲突
多发射流水线的调度问题（例子说明）
76
共需 10个周期。有 8个空闲周期，其中 4个是为了保证指令的顺序发射顺序完成。
（ 1）顺序发射顺序完成
77
（ 2） 顺序发射乱序完成共需 9个周期。仅有 3个空闲周期。
78
（ 3）乱序发射乱序完成共需 8个周期，无空闲周期。
79
2,超标量超流水线处理机的性能
（ 1） 性能在一台指令级并行度为（ m,n）的超标量超流水线处理机上，
连续执行 N条没有资源冲突、没有数据相关和控制相关的指令所需要的时间为：
其中,k是指令流水线的时钟周期数，而不是流水线级数。△ t是一个时钟周期的时间长度。上式中的第一项是开始 m条指令通过指令流水线所需要的时间，第二项是执行其余 N - m条指令所需要的时间；这时，每一个时钟周期平均执行完成 m× n条指令，也就是每一个流水线周期平均执行完成 n条指令。
(,) ( )NmT m n k tmn
80
（ 2） 性能比较
81
（ 3） 结论,
① 超标量处理机的相对性能最高，其次是超标量超流水线处理机，
超流水线处理机的相对性能最低,主要原因如下,
a) 超标量处理机在每个时钟周期的一开始就同时发射多条指令，
而超流水线处理机则要把一个时钟周期平均分成多个流水线周期，每个流水线周期发射一条指令。因此，超流水线处理机的启动延迟比超标量处理机大。
b) 条件转移造成的损失，超流水线处理机要比超标量处理机大。
c) 在指令执行过程中的每一个功能段，超标量处理机都重复设置有多个相同的指令执行部件，而超流水线处理机只是把同一个指令执行部件分解为多个流水级。
因此，超标量处理机指令执行部件的冲突要比超流水线处理机小。
82
② 当横坐标给出的设计指令级并行度比较低时，处理机实际指令级并行度的提高比较快。但是，当设计指令级并行度进一步增加时，处理机实际指令级并行度提高的速度越来越慢。因此，在实际设计超标量、超流水线、超标量超流水线处理机的指令级并行度时要适当；
否则，有可能造成花费了大量的硬件，但实际上处理机所能达到的指令级并行度并不高。目前，一般认为 m和 n都不要超过 4。
③ 一个特定程序由于受到本身的数据相关和控制相关的限制，它的指令级并行度的最大值是确定的。这个最大值主要由程序自身的语义来决定，与这个程序运行在那一种处理机上无关。因此，上图中的三条曲线，对于某一个特定的程序，最终都要收拢到同一个点上。
当然，对于各个不同程序，这个收拢点的位置也是不同的。
83
④ 一个程序能够达到的实际指令级并行度还与所采用的调度算法有关。目前，国际上已经提出了多种开发指令级并行性的优化调度算法。对于没有条件转移操作，没有输入输出，没有程序调用和程序中断，单入口单出口的基本块程序，实现最优调度并不十分困难。但是，对于一般程序，要充分开发程序中的指令级并行性，
实现最优调度非常复杂，已经证明，这是一个 NP完全问题。
⑤ 另外，实现最优调度所需要的代价很大，包括硬件代价和软件代价，通常需要编译器和硬件的结合才能获得比较好的调度效果。
目前，开发程序指令级并行性的许多优化调度算法及编译技术还在进一步研究中。
84
超线程技术
,Hyper-Threading Technology（ 超线程技术,以下简称 HTT技术）”
。
对于计算机微处理器而言，程序只是一组编译过的机器代码，可以执行相关的数据计算与操作，这些代码由一条条的指令组成，每一个代码组就是一条 线程 。
单 CPU系统中，在执行指令的时候,CPU先找出相应指令所在的内存位置，执行下一条指令，再转换到另一个位置，在同一时间内 CPU只能对应一个指令。线程可以中断，并把中间结果暂存在另一个特殊位置（堆栈），不同的线程可以交叉运行，实现多任务，但每次运行的线程仍然仅有一条，千万不要把 多任务和多线程 混淆了。
既然一个 CPU是单线程，那么两个 CPU自然就可以双线程啦，如此类推，就会出现四路、八路系统。但双处理器系统的性能并不能达到单处理器的两倍，通常只有 33%的性能增益。
85
为了提高 CPU的性能，厂商通常采用增加 工作频率和缓存容量 的方法来提升速度，但这是治标不治本的方法,CPU只提高了速度，其内在潜力依然未能完全发挥,CPU的 执行单元 没有被充分利用，于是设计者就在 CPU中 加入两个逻辑处理单元,同时管理 CPU的全部资源，直接提高 CPU内核的工作效率。
简而言之：超线程技术就是利用特殊的硬件指令，把两个 逻辑内核 模拟成两个 物理芯片,让单个处理器都能使用线程级并行计算。从而兼容多线程操作系统和软件，提高处理器的性能。
操作系统或者应用软件的多线程可以同时运行于一个 HTT处理器上，
两个逻辑处理器共享 一组处理器执行单元,并行完成加、乘、负载等操作。这样就可以使得运行性能提高 30%，这是因为在同一时间里，
应用程序可以使用芯片的不同部分。
虽然单线程芯片每秒钟能够处理成千上万条指令，但是在任一时刻只能够对一条指令进行操作。而“超线程”技术可以使芯片同时进行多线程处理，使芯片性能得到提升。
86
例如,Office等商业软件主要使用整数运算单元和读写 /存储单元，
几乎不涉及浮点运算单元,3D渲染软件主要使用浮点运算单元，很少涉及整数运算单元，很明显，这种设计造成了很大的浪费。如 P4
处理器内部有 7个执行单元，每个时钟周期内，约有 2个执行单元工作，它们共执行两次操作，那么，其它 5个单元完全没有用到。
超线程技术对商用和家用电脑而言，除了全面提升系统性能以外，
还增加系统平台所能支持用户的数量，大幅降低系统的反应潜伏时间（因为任务能被分为几个隔离的线程来同时执行），增加系统的指令执行数量，还有一点很关键的是，即使对于现有的 IA-32体系软件它也能很好地兼容。因为,HTT处理器还提供一个中断指令，在执行适合单处理器的任务时，暂停其中一个逻辑内核，让操作系统识别为单处理器，在执行适合多处理器的任务时，重新打开逻辑内核，利用 HTT来增加整体效率。
87
支持超线程技术需软硬件的支持，硬件方面需要 主板北桥芯片 的支持。
超线程技术还需要主板对 CPU的电源 支持，需要主板能提供给处理器高达 70A的电流，否则系统可能不能长期稳定工作。除此之处还需要主板 BIOS的支持，需要 BIOS加入特定的支持 HTT处理器的代码。当 BIOS检测到是超线程处理器时，在 BIOS设置菜单中出现 CPU Hyper-Threading（ Enabled or Disabled）的选项。
超线程技术还需要 操作系统 的支持。目前支持超线程技术的有
Windows XP和 Linux 2.4.X。这不同于传统的处理器安装的
Windows XP，使用超线程技术的处理器安装完 Windows XP后在设备管理器中能显示有两个处理器和 ACPI Multiprocessor PC。
