下午 6时 5分 1
第五章 流水线处理技术
5.1 流水处理概述
5.2 流水线工作方式
5.3 流水线调度
5.4 流水中并行性进一步开发
5.5 向量流水处理技术本章重点见书 P193 5,1~5,9
下午 6时 5分 2
5.1 流水线处理概述一,CPU主要工作方式,
顺序
重叠
流水取指令 分析 执行 。。。
每阶段时间为 t，共 n条指令顺序串行 （ sequence）：
n
i
iii tttT
1
)( 执分取设指令工作方式分成取指令、分析、执行指令若各阶段执行时间相等，则共需 3 nt
优点,控制简单；
缺点,速度慢，机器各部件的利用率很低。
下午 6时 5分 3
重叠 （ Overlap）：在两条相近指令的解释过程中，某些不同解释阶段在时间上存在重叠部分。
包括一次重叠、先行控制技术和多操作部件并行。
上一条指令的执行阶段与下一条指令的取指阶段完全重叠； T=（ 2× n+1） t
将相邻两条指令的重叠时间再往前提前一个阶段；
T=3× t+（ n-1） × t=（ n+2） × t
一次重叠：把取指令操作隐含在分析,执行指令过程中,则在任何时候只允许上条指令,执行,与下条指令
,分析,相重叠 。 T=（ n+1） × t
实际执行时间：
n
n
i
ii
ttttT
执执分分
2
11
,m a x
若各段时间不等时，有下午 6时 5分 4
先行控制,分析部件和执行部件能分别连续不断地分析和执行指令，预取和缓冲相结合的技术,通过对指令流和数据流的先行控制，使指令分析器和执行部件能尽量连续并行工作。
执行时间,
n
i
ittT
1
1 执分先行分析 k 执行 k
分析 k+1 执行 k+1
分析 k+2 执行 k+2
多操作部件并行,采用有多个功能部件的处理机，把 ALU的多种功能分散到几个具有专门功能的部件中，这些功能部件可以并行工作，使指令流出速度大大提高。
下午 6时 5分 5
1、流水的概念特点流水,把一个重复时序过程分成若干个子过程，每个子过程都可有效的在其专用功能段上和其它子过程同时执行的一种技术。
5.2、流水工作方式取指 访存执行译码 写回
IF ID EX MEM WB
S1 S2 S3 S4 S5
输入 输出指令的流水处理流水线的基本结构中主要包括三大部分：锁存器,时钟,功能站 。
流水线中每个站都是由一些执行算术和逻辑功能的组合逻辑线路组成的,它们可以互相独立地对流过的信息进行某种操作,
相邻两站由高速锁存器 （ latch） 隔开,信息在各站间的流动靠同时送到各站的时钟信号来控制 。
下午 6时 5分 6
S1 S2 Sk
输入 输出流水线的基本结构
.….…..
时钟下午 6时 5分 7
...1 2 3 4 5,....,n-1 n
...1 2 3 4 5,....,n-1 n
...1 2 3 4 5,....,n-1 n
...1 2 3 4 5,....,n-1 n
1
2
3
4
△ t0 △ t0 △ t0 △ t0
T0=m △ t0
n △ t0
T
(m-1) △ t0
(n-1) △ t0
填入 正常 排空流水时空图空间时间下午 6时 5分 8
2、流水线特点,
1）流水一定重叠，比重叠更苛刻。
2）一条流水线通常有多个流水段组成。
3）每段有专用功能部件，各部件顺序连接，不断流。
4）流水线有建立时间、满载时间、排空时间，
5）各段时间尽量短、一致；不一致时最慢子过程为瓶颈。
6）给出指标如最大吞吐率，为满负载最佳指标。
建立时间,在流水线开始时有一段流水线填入时间,使得流水线填满 。
正常流动时间,流水线正常工作,各功能段源源不断满载工作 。
排空时间,在流水线第一条指令结束时,其他指令还需要一段释放时间 。
下午 6时 5分 9
1 2 3 4
出入非线性流水线
3、流水的分级、分类分级,（处理的级别分类）
部件级：将复杂的算逻运算组成流水工作方式；
指令级：把一条指令解释过程分成多个子过程 ；
处理机级：每个处理机完成某一专门任务，各个处理机所得到的结果需存放在与下一个处理机所共享的存储器中其他分类：
功能：单功能流水线（如 CRAY-1）、多功能流水线
（如 TI-ASC）
工作方式：静态流水线、动态流水线
连接方式：线性、非线性
处理数据：标量流水、向量流水下午 6时 5分 10
(1)ASC算术运算流水线（多功能）
输入减阶对阶移位相加规格化相乘累加输出
1
2
3
4
5
6
7
8
4、流水线举例输入减阶对阶移位相加规格化输出
1
2
3
4
5
8
加输入相乘累加输出
1
6
7
8
乘下午 6时 5分 11
...1 2 3 4,....,n-1 n
...1 2 3 4,..,.,n-1 n
...1 2 3 4,....,n-1 n
...1 2 3 4,.,n-1 n
1
2
3
4
5
8
6
7
...1 2 3 4,.,n-1 n
...1 2 3 4,....,n-1 n
时间空间
(段号 )
浮加一 二 三 四二 三一 二一一定乘
...
...
静态多功能流水线时 -空图静态流水线,只有当进入的是一串相同运算的指令时，流水的效能才得以发挥，才能使各个功能段并行地对多条指令的数据进行流水处理。
下午 6时 5分 12
...1 2 3 4 5,....,n-1 n
...1 2 3 4 5,....,n-1 n
...1 2 3 4 5,....,n-1 n
...1 2 3 4 5,....,n-1 n
1
2
3
4
5
8
6
7
...1 2 3 4 5,....,n-1 n
...1 2 3 4 5,....,n-1 n
时间浮加 定乘一 二 三 四 五 六一 二 三 四 五 六七一 二 三 四 五一 二 三 四动态多功能流水线时 -空图区别,如果从软硬功能分配的观点上来看,静态流水线其实是把功能负担较多地加到软件上,以简化硬件,动态流水线则是把功能负担较多地加在硬件上,以提高流水的效能 。
下午 6时 5分 13
（ 1） VAX8600的流水结构
a,I部件,预取指令，操作码译码，预取操作数，并存放运算结果。
b,E部件,执行指令。
c,F部件 ；浮点加速器。
d,M部件,控制 CPU和输入输出设备对主存的访问，有 16k
字节的 cache和把虚存地址转换成实存地址的地址转换表
（快表）
e,操作台,提供同操作员，引导设备和远程诊断的界面。
指令流水线,一条指令的取指令、译码、取操作数和执行等几个过程能同它前后的指令在时间上重叠，用这种指令重叠的方法构成的流水线就是指令流水线，又叫指令先行控制。
2,VAX8600和长城 386计算机的指令流水线下午 6时 5分 14
操作台
E部件
F部件
I部件 M部件主存标准 SBI
适配器选件 SBI
适配器
SBI
SBI
C总线诊断总线写总线操作数总线虚拟地址存储器数据总线适配器总线数组总线
I/O子系统
I/O子系统
VAX8600的 CPU结构图下午 6时 5分 15
取指令指令译码形成操作数地址取操作数执行指令存储结果
N-1
N-2 N-1
N-2 N-1
N-1
N-1
N-1 N+1
N+1
N+1
N+1
N+1
N+1
N+2
N+2
N+2
周期操作
VAX8600指令流水线的工作顺序实框：表示 CPU在执行一条典型的指令时的动作顺序。
虚线：表示 6个动作是各自分开进行的，可以同其它指令的动作并行进行。
下午 6时 5分 16
（ 2）长城 386指令流水线
内部有六个部件总线接口部件,同外部的接口 取指令、读写数据。
I部件：
指令预取部件,取指令放在 16个字节指令预取队列。
指令译码部件,形成指令微码，指令队列中可放 3条指令
E部件：
执行部件,控制、数据部件、保护测试部件分段部件分页部件 存储管理部件取指令 1 取指令 2 取指令 3 取指令 4 存结果 1 取指令 5 取指令 6
指令译码器 1 指令译码 2 指令译码 3 指令译码 4 指令译码 5
执行 1 执行 2 执行 3 执行 4
地址变换和 MMU 地址变换和 MMU
80386的指令流水处理下午 6时 5分 17
5,2,4 流水线性能分析计算一,技术指标衡量流水线处理机的性能主要是吞吐率,加速比和效率 。
1,吞吐率,单位时间内能处理的指令条数或能输出的数据量 。 吞吐率越高,计算机系统的处理能力就越强 。 就流水线而言,吞吐率就是单位时间内能流出的任务数或能流出的结果数 。
最大吞吐率：流水线达到稳定状态后可获得的吞吐率 。
（ 1） Tpmax=1/?t
（ 2） TPmax=1/ max{?t1,?t2,?t3,?t4}
,瓶颈”子过程：
1 2 3 4
t?t 3?t?t
下午 6时 5分 18
子过程 3为瓶颈段的时空图最大吞吐率 TPmax=1/3?t
S
T
S1
S2
S3
S4
t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t12 t13 t14 t15
1 2 3 4
t11
1 2 3 4
1 2 3 4
1 2 3 4
输出下午 6时 5分 19
1 312 32 33 4
2 1 4
3a
3b
3c
t? t? t? t? t? t?
t?t? t?
t?3
t?3
t?3
瓶颈段细分重复设置瓶颈流水段解决瓶颈有两种方法
A：
B：
下午 6时 5分 20
T
重复设置瓶颈流水段后的工作时空图
S
S1
S2
S3a
S3c
S3b
S4
1 2 3 54 6 7 8 9 10 11 12
1 2 3 54 6 7 8 9 10 11 12
1 4 7 10
2 5 8 11
3 6 9 12
1 2 3 54 6 7 8 9 10 11 12
t1 t12 t17
下午 6时 5分 21
实际吞吐率
（ 1） 完成 n条指令的解释共需时间
T=mt0+(n-1)?t0，
（ 2） 流水线的实际吞吐率为可以看出不仅实际的吞吐率总是小于最大的吞吐率,而且只有当 n>>m时,实际的吞吐率才能接近于理想的最大吞吐率 。
n
m
TP
n
mttntm
nTP
11
m a x
)11(
1
)1(
000
下午 6时 5分 22
2,效率,设备的利用率，直接反映了处理机结构有效程度。
流水线有建立时间、排空时间，不总是满负载工作。
η = N个任务实际占用的时 -空区M各段总的时 -空区各段时间相等：
η = m*Tm*n* △ t =TP △ t
各段时间不等,n *Σ △ ti
m*[Σ △ ti+(n-1)△ tj]m
i=1
η =
m
i=1
下午 6时 5分 23
m
i
ii tn
1
m
i
m
i
jii tnt
1 1
)1(?
其中，分母为 m个段总的加权时空区，分子为 n个任务总的加权时空区设备利用率占整个系统设备利用率的比重不同,可以给每个段赋予不同的,权,值?i,这样,线性流水线总效率的一般式为：
下午 6时 5分 24
Sp=T非流水T流水 = n*m*△ tM*△ t+(n-1)*△ t = n*mm+n-1 = m
1+ nm-1
各段时间相等,
各段时间不等,
Sp= n *Σ △ ti
m
i=1
Σ △ ti+(n-1)*△ tj
m
i=1
3,加速比,M段流水线的速度与等效的非流水线的速度之比。
讨论：
1．减少瓶颈的办法：多套并行和细分慢的子过程。
2．指令串不相同，需功能切换（尽量相同）向量流水。
3．非线性流水控制输入，使不碰头。
4,T尽量小，尽量一致，减少相关。
5．指标给的为最佳值 。
下午 6时 5分 25
五,实例分析,性能分析（实测法,分析法,时空图法）,
例 1,四段流水线,△ t1=△ t3=△ t4=△ t,△ t2=3△ t,4个任务,10
个任务时 TP,η,SP 。
η = N个任务实际占用的时 -空区M各段总的时 -空区
n=10，
η = 6*10△ t4*6△ t+9*3*4△ t = 6024+108 = 115
TP= 106*△ t+3*9* △ t = 1033*△ t
≈45%
（ 1）分析法,各段时间不等
=Sp= n *Σ △ ti
m
i=1
Σ △ ti+(N-1)*△ tj
m
I=1
10*6 △ t
(6+3*9) △ t =
20
11 =1.8
TP= nΣ
△ ti+(n-1)△ tj
m
i=1
下午 6时 5分 26
时间
1 2 3 4
31 1 1 2 2 32 3 4
1 2 3
1 2 3
1
2
3
4
4 4
4
4
3△ t 3△ t
空间
(2) 时空图法,
Tp=4/((6+3*3) △ t)=4/(15△ t)=0.267(1/△ t)
=24 △ t /(4*15△ t)=2/5=40%
Sp=4*6 △ t/15△ t=8/5=1.6
n=4时 ;
n=10时 ;同上,
下午 6时 5分 27
比较,
N=4 0.267
N=10 0.303
N=100 0.33
40
%
45%
49%
1.6
1.8
1.98
n spTp(1/△ t)
n=4,m=4
说明,N>>M流水性能才发挥得更好下午 6时 5分 28
例 2,以浮点加法运算为例（四段流水线）各段时间相等，如何求吞吐率、效率。
求 Z=A+B+C+D+E+F+G+H,TP,η,Sp 注意有相关时间空间
Z=A+B+C+D+E+F+G+H
1 2 3 4
5 6
7
TP=7/15△ t,
η =7*4/(15*4)=7/15
解：
Sp=4*7/15=28/15=1.87
1
1
1
1
2
2
2
2
3
3
3
3
4
4
4
4
5
5
5
5
6
6
6
6
7
7
7
7
下午 6时 5分 29
例 3,ASC计算机功能算术运算流水线各段时间相等,6次浮点加、
5次定点乘的吞吐率,效率,加速比 M=8,N=11.
分析,T加 =6+(6-1)*1=11 (△ t) T乘 =4+(5-1)*1=8 (△ t)
则 TP= 11/(11+8)△ t =11/19 △ t
Sp= 56 △ t /19 △ t =2.94
η = (6*6+5*4) △ t /(19*8△ t)=6/52=7/19
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1
2
3
4
5
8
6
7
1 2 3 4 5 6
1 2 3 4 5 6
时间浮加 定点乘一 二 三 四 五一 二 三 四 五一 二 三 四 五一 二 三 四 五下午 6时 5分 30
1,分段时间 △ t尽量小、尽量一致,TP=1/△ t，则 TP越大；
若 m太多，则处理时间长，锁存器越多。
2,△ t选取,各级微操作需逻辑级门,每个门的延时加走线延时再加 3%冗余量,
3.缓冲深度影响,（缓冲器个数）
4.非线性流水的合理控制
5.2.5 流水的控制和设计一、时序和缓冲二,相关处理定义,相近指令出现某种关联使不能同时执行。
资源相关
数据相关
控制相关下午 6时 5分 31
1,资源相关资源相关是指当有多条指令进入流水线后在同一机器周期内争用同一功能部件所发生的冲突例 1：
435
216
XXX
XXX
两条指令同时要用一个加法器
ALU LOAD/STORE
IF 取指 取指
ID 译码、读寄存器堆 译码、读寄存器堆
EX 执行 计算访存有效地址
MEM - 访存（读或写）
WB 结果写回寄存器堆 将读出的数据写入寄存器堆指 令流水段不同类型指令中各流水段进行的操作下午 6时 5分 32
两条指令同时访存造成资源相关
MEMEXIDIF指令
i+4
WBMEMEXIDIF指令i+3
WBMEMEXIDIF指令i+2
WBMEMEXIDIF指令i+1
WBMEMEXIDIFLoad指令
87654321时钟指令冲突取指 译码 执行 访存 写回例 2：
下午 6时 5分 33
EXIDIF指令
i+4
MEM EXIDIF停顿指令
i+3
WBMEMEXIDIF指令
i+2
WBMEMEXIDIF指令
i+1
WBMEMEXIDIFLoad
指令
87654321时钟指令
9
WB
MEM
使 i+3指令停顿一拍进入流水线，以解决访存相关或重复设置一个存储器解决方法：
下午 6时 5分 34
例：有 i 和 j两条指令,i指令在前,j指令在后，则三种不同类型的数据相关的含义为：
RAW读写 (先写后读 ) - 指令 j 试图在指令 i 写入寄存器前就读出该寄存器内容，这样，指令 j就会错误地读出该寄存器旧的内容。
（改用相关） i,R1+R2->R3 j,R3*R4->R5
WAR写读 (先读后写 ) - 指令 j 试图在指令 i读出寄存器之前就写入该寄存器，这样，指令 i就错误地读得该寄存器新的内容。
（用改相关） i,R3*R4->R5 j,R1+R2->R3
WAW写写 (先写后写 ) - 指令 j试图在指令 i写寄存器之前就写入该寄存器，这样，两次写的先后次序被颠倒，就会错误地使由指令 i写入的值成为该寄存器内容。
（改改相关） i,R1*R2->R3 j,R4+R5->R3
2,数据相关顺序流动不按顺序流动不按顺序流动下午 6时 5分 35
例 1：如果流水线要执行以下的两条指令
X1=X2+X3
X4=X1-X5
这是一个典型的先写后读（ RAW）相关。
例 2：结果寄存器的冲突
X6=X1+X2
X6=X4*X5
这是个先写后写的写 -写相关，两条指令都要用 X6存放结果，此时第二条指令也要等待第一条指令完成后才能写。
例 3：一条指令要把结果存放到上一条指令存放操作数的寄存器中时发生的冲突。
X5=X4*X3
X4=X0+X6
这是个先读后写的写 -读相关。如果这两条指令接连地送到乘法功能部件和加法功能部件中，由于加法比乘法快得多，第二条的结果 X4先产生，但必须等待第一条指令做完后才能送 X4。
下午 6时 5分 36
解决办法主要用软件和硬件技术：
时间推后法
旁路技术或相关专用通路技术例子：流水执行和相关 （资源相关）
有四段流水线,IF（取指令 ）,ID（译码，取数）,
EX（执行） WR（写回）
PC值 指令 流水各段
n,load A IF ID EX WR
n+1,load B IF ID EX WR
n+2,add A,B IF ID 气泡 EX WR
n+3,store C IF ID 气泡 EX WR
n+4,jump K IF ID EX WR
n+5,load E 停顿 停顿 停顿。。
n+6 ……… 停顿 。。。。。。
K,IF ID EX
例子中有资源相关、有控制转移相关，这将影响流水线的指标。
下午 6时 5分 37
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
ADD
R1,R2,R3
SUB R4,R1,R5
AND
R6,R1,R7
OR R8,R1,R9
XOR
R10,R1,R11
定向传递 R1值数据相关和定向传递指令下午 6时 5分 38
IF EX MEM ID R WBW
IF EX MEM ID R WBW
IF EX MEM ID R WBW
IF EX MEM ID R WBW
IF EX MEM ID R WBW
ADD
R1,R2,R3
SUB R4,R1,R5
AND R6,R1,R7
OR R8,R1,R9
XOR R10,R1,R11
定向传递 R1值减少定向传送次数的方法在 ID段读寄存器堆操作安排在后半部分，在 WB段写寄存器堆操作安排在前半部分，以减少定向传输操作。
下午 6时 5分 39
ALU
运算结果写 RF RF 读 RF ALU
操作数寄存器专用通路（旁路）
寄存器堆 RF
多路开关 多路开关
ALU
R4
R1
缓冲寄存器（ R1,R4）
旁路下午 6时 5分 40
3,控制转移冲突,无条件转移和条件转移引起的
（转移指令概率占 1/4左右，不可忽视）
猜测法,按一个方向流水，用历史记录提高猜测率；
预取转移目标,向两个分支方向预取指令；
加快和提前形成条件码,有的指令的条件码并不一定要等执行完毕得到运算结果后才能形成；
优化延迟转移技术
a.将转移指令前的那条指令调度到延迟槽中；
b.将转移目标处的那条指令调度到延迟槽中；
c.将转移不发生时该执行的那条指令调度到延迟槽中。
设置特殊循环指令，加快短循环处理
3.转移处理下午 6时 5分 41
三,中断
流水机器处理中断的关键 不在于如何缩短断流时间，而是如何处理好断点现场及中断后的恢复问题。
不精确断点法 (同外部设备中断处理一样 )：不论第 i条指令在流水线的哪一段发出中断申请，都不再允许那时还未进入流水线的后续指令再进入
精确断点法,不论第 i条指令是在流水线中哪一段发的中断申请，给中断处理程序的现场全都是对应第 i条的，在第 i
条之后进入流水线的指令的原有现场都能恢复 (增加设备，
加许多缓冲器，各功能段状态保留）
下午 6时 5分 42
5.3 先进的流水技术一、先进的流水调度方法 - 动态调度静态调度,借助软件对指令执行顺序进行调度，以减少由于流水线中存在相关冲突而引起流水线的停顿时间。目前比较流行。
动态调度,通过硬件重新安排指令的执行顺序以减少流水的停顿。
优点：
（ 1）能处理某些在编译时无法知道的相关情况
（ 2）能简化编译程序设计
（ 3）使代码有可移植性缺点,相应的硬件较为复杂。
下午 6时 5分 43
IF ID
整数部分浮点加浮点乘浮点除
RF
记录控制器
EX MEM WB
指令控制 /状态 控制 /状态集中式动态调度寄存器堆集中式调度,依靠硬件在程序运行过程中对可能出现的相关情况加以检测，从而保证流水线中的各个功能部件能最大限度地重叠工作。
下午 6时 5分 44
分布式动态调度（比集中式调度更灵活）
对 IBM360/91机是通过给 FLR设置一个“忙”标志来判别指令间所用的数据是否发生相关,另外还有一个标志（即站号）
表示数据由何处来，用站号位控制相关通路连接，采用公共数据总线 CDB来实现内部数据专用通路的连接。
IBM360/91的浮点运算器部分包括了以下主要部件：
（ 1） 运算部件,一个加法部件和一个乘除部件。
（ 2）保存站,加法部件中有 A1~A3三个保存站，乘除部件有 M1和 M2两个保存站，用来保存当前参加运算的数据。
（ 3） 指令操作缓冲栈,存放经分析后由指令部件送来的指令，译码后，
产生相应的控制信号送到各个部件。
（ 4）浮点操作数寄存器（ FLB）,存放由主存预取来的操作数。
（ 5）浮点寄存器（ FLR）,存放操作数的寄存器。
（ 6） 存储数据缓冲站（ SDB）,存放将写入存储器的结果数据，也有站号。
（ 7） 公共数据总线（ CDB）,以上各部件间的连接总线。
下午 6时 5分 45
浮点操作数缓冲器
（ FLB）
控制浮点操作栈
（ FLOS）
站忙 浮点寄存器号位 （ FLR）
控 站 存数缓冲器制 号 （ SDB）
译码器站号 源 1 站号 源 2 控制加 法 器 乘 / 除 法 器存储器总线站号
0001
0110
6
5
4
3
2
1
F7
6
5
4
3
F2
1
F0
1010
1011
1100
A1
A2
A3
M1
M2
1000
1001
指令处理部件
FLB总线 FLR总线站号 源 1 站号 源 2 控制
CDB
公共数据总线下午 6时 5分 46
特点：
（ 1）由于为加法器和乘法部件分别设置了 3个和 2个保存站，
从而减小了资源使用冲突的机会。仅当这些保存站读都处于忙碌状态时，才有可能发生资源使用冲突。
（ 2）调度算法使用保存站，通过对寄存器重新命名（改写站号）自然地消除了 WAR和 WAW数据相关可能性。
（ 3）通过对 FLR寄存器忙位状态的判别，来检测是否存在
RAW数据相关。
（ 4）借助 CDB公共数据总线作为专用相关通路，将有关数据直接送往所有需要它的功能部件，而不必先写入寄存器，
然后再从此寄存器读出。
由于这种调度是通过 各部件‘忙位’、‘站号位’、
‘ CDB数据总线’来实现的故称分布式调度下午 6时 5分 47
预取指令的 PC
=
是否查找 预测 PC值转移发生预测 PC值应送入 PC中预测转移发生或不发生转移不发生，按正常顺序进行动态硬件预测转移方法在程序运行时，借助硬件来动态地预测转移方向。实际上，这是一种尽早生成转移目标地址的方法，它将过去发生过的转移指令地址存入一个由类似 cache、称为 BTB（ Branch target buffer）的转移目标缓冲器中。其中，
转移指令地址作为标志，供检测用。
下午 6时 5分 48
5.4 流水的实现和控制一、非线性流水线的冲突及调度非线性流水线,由于段间有前馈和反馈通路任务，执行过程中可能会多次通过同一流水段，发生几个任务同时争用同一流水段的现象，这就是 功能段的使用冲突 。
解决方法,间隔恰当的拍数后再向流水线送入下一个任务。这就需要对流水线作适当的调度。
流水线调度常借助于二维预约表和状态转换图来进行分析
根据预约表可较容易地推算出一个任务执行时，各段所需的间隔周期拍数。
下午 6时 5分 49
S/t 1 2 3 4 5 6 7 8 9
1 X X
2 X X X
3 X
4 X X
5 X X
二维预约表图中每一行代表 P的一个段,每一列表示相应的时钟周期 。
若某个任务在周期 ti需要使用 Sj段进行处理,则在行 Sj和列 ti
的相交处以,?” 表示 。
条件,非线性、单功能流水线 P，由 K段组成，每个任务流过流水线需 N个时钟周期（ t1,t2,…,t n），段为纵坐标，时间为横坐标禁止表 F={1,5,6,8}
下午 6时 5分 50
10110001
10110111 10111101
1011111110111011
一个 n位的位向量 C=(Cn,Cn-1,...,C2,C1)称为冲突向量。
其中第 i位状态表示于当时相隔 i拍时间时，是否允许输入新任务。如允许输入，则 Ci=0,否则 Ci=1。
非线性流水线预约表相应状态图
4
2
>=7>=7
3 4
>=7
>=7
>=7 原始冲突向量
23
下午 6时 5分 51
过程,
1,按给出的预约表写出允许表和禁止表 F={1,5,6,8}；
2,写出 n位初始冲突向量（ 10110001）；
3,按禁止表约束条件列出新的冲突向量，直到不再生成新的冲突向量为止（当前冲突向量和初始冲突向量按位“或”）；
4,画出用冲突向量表示的流水线状态转移图（两个冲突向量之间用有向弧连接，并用数字表示引入后继任务用的间隔节拍，写出各种可能的状态转换）；
5,列出各种调度方法平均间隔拍数；
6,求出最佳等间隔和非等间隔调度拍数；
本例子中非等间隔调度为 3拍,4拍 ……,平均间隔为 3.5拍，而等间隔调度为 7拍。
下午 6时 5分 52
5.4、流水中指令级并行性的进一步开发粗粒度并行性,在多处理机上分别运行多个进程，由多台处理机合作完成一个程序；
细粒度并行性,指在一个进程中进行操作一级或指令一级的并行处理。
RISC机进一步开发细粒度并行性
5.4.1 超级标量方法每个时钟周期内能启动 n条指令主要特点：
（ 1）配置有多个性能不同的处理部件，采用多条流水线并行处理。
（ 2）能同时对若干条指令进行译码，将可并行的指令送往不同的执行部件，从而达到每个周期启动多条指令。
（ 3）在程序运行期间由硬件（通常是状态记录部件和调度部件）
完成指令调度。
下午 6时 5分 53
0 1 2 3 4 5 6 T
取指 译码 执行 写回每拍启动 3条指令要求并行度 =3
超级标量机
1,超级标量计算机的原理：
配置多个功能部件多个译码器，寄存器端口，总线，能同时执行多个操作。
下午 6时 5分 54
2,超标量流水线调度
按序发射按序完成
按序发射无序完成
无序发射无序完成无论那种调度策略，都要保证程序运行的最终结果是正确的，
Pentium处理器采用的是按序发射按序完成策略
PentiumII/III处理器采用的是按序发射无序完成指令发射：启动指令进入执行段的过程；
指令发射策略：指令发射所使用的协议或规则 。
按序发射：当指令按策划功能序的次序发射时,称之为按序发射 （ in-orderissue） 。
无序发射：为改善流水线性能,可以将有相关的指令推后发射,而将后面的无相关性的指令提前发射,即不按程序原有次序发射指令,称之为无序发射 （ out-of-order） 。
下午 6时 5分 55
以一条长指令实现多个操作的并行执行，减少存储器访问主要特点：
（ 1）单一的控制流。只有一个控制器，每个周期启动一条指令。
（ 2）超长指令字被分成多个控制字段，每个字段直接独立地控制每个功能部件。
（ 3）含有大量的数据通路和功能部件，由于编译器在编译时间已考虑可能出现的数据相关和资源相关，故控制硬件较简单。
（ 4）在编译阶段完成超长指令中多个可并行执行操作的调度。
5.4.2 超长指令字计算机下午 6时 5分 56
0 1 2 3 4 5 6 T
3个操作每拍启动一条长指令，执行 3个操作，相当于 3条指令，要求并行度
=3
超长指令字计算机（ VLIW）的原理结构下午 6时 5分 57
5.4.3 超级流水方法特点,超流水结构是把每一个流水级 （ 一个周期 ） 分成多个
（ 例如 3个 ） 子流水级,而在每一个子流水级中取出的仍只有一条指令,但总的来看,在一个周期内取出了三条指令 。
对于超流水线结构,其中指令部件可以只有一套,也可以有多套独立的执行部件 。 它虽然每个机器周期只能流出一条指令,但它的周期比其它机器短,一台 m度的超级流水线计算机的周期为一般机器周期的 1/m,它的一个操作需要 m个周期,因而在流水线能充分发挥作用时,其并行度能达到 m。
下午 6时 5分 58
每 1/2拍启动一条指令，要求并行度 =2
超级流水线的原理结构图
0 1 2 3 4 5 6
下午 6时 5分 59
这种方法主要通过提高流水线运行速度来增强机器性能。为提高运行速度，必须要加深流水深度，既增加流水段数，以减少每一段的延迟时间，这样就可加快流水线的运行频率。
下面是 R4000超级流水情况分 8段：取指 1（ IF），取指 2（ IS）
读 RF，执行（ EX），取数 1（ DF），取数 2（ DS），标记检查
（ TC），写 RF（ WB）
IF IS RF EX DF DS TC WB
IF IS RF EX DF DS TC WB
IF IS RF EX DF DS TC WB
IF IS RF EX DF DS TC WB
IF IS RF EX DF DS TC WB
IF IS RF EX DF DS TC WB
IF IS RF EX DF DS TC WB
IF IS RF EX DF DS TC WB
流水线周期主时钟周期流水深度 =8
下午 6时 5分 60
5.4.4 超级流水标量计算机可以把超标量技术与超流水技术结合在一起，这就是超标量超流水线处理机。超标量超流水线处理机在一个时钟周期内要发射指令 n次，每次发射指令 m条，因此，超标量超流水线处理机每个时钟周期总共要发射指令 m*n条。
IF
IF
IF
ID
ID
ID EX
EX
EX WR
WR
WR
IF
IF
IF
ID
ID
ID EX
EX
EX WR
WR
WR
IF
IF
IF
ID
ID
ID EX
EX
EX WR
WR
WR
指令
I3
I2
I1
1 2 3 4 5 6
时钟周期超标量超流水线处理机的指令执行时空图下午 6时 5分 61
Pentium流水线结构（五级双流水，满足配对法则）
一个周期执行两条整数指令
11
12
13
14
15
16
17
18
11
12
13
14
15
16
17
18
11
12
13
14
15
16
17
18
11
12
13
14
15
16
17
18
11
12
13
14
15
16
17
18
预取级（取指令）
译码级 1（译码）
译码级 2（计算地址）
执行级（取数、运算）
写回级
U流水 V流水一,Pentium的超标量流水线下午 6时 5分 62
PentiumCPU结构
（ 1）超标量流水线总线部件预取地址
64位数据总线
32位数据总线控制指令指针转移和目标
BTB
转移目标缓冲
TLB 指令
CACH
E
8KB
预取缓冲指令译码控制
ROM
控制部件转移和目标验证地址地址产生
（ U流水线）
地址产生
（ V流水线）
整数寄存器堆ALU(U
流水线 )
ALU(V
流水线 )
桶形位移器
32
32
32 32
32
TLB
数据
CACH
E 8KB
浮点部件控制寄存器堆加法除法乘法
80
80
下午 6时 5分 63
(2)分立的指令 CACHE和数据 CACHE
不仅使指令预取和数据读写能无冲突地同时完成，而且可同时与 U,V两条流水线分别交换数据。
(3)重新设计的浮点运算部件执行过程是分为 8段的流水线。前 4段为指令预取（ PF）、指令译码（ D1）、地址生成（ D2）、取操作数（ EX），在 U,V流水线完成；后 4段为执行 1（ X1）、执行 2（ X2）、结果写回寄存器堆（ WF）、错误报告（ ER），在浮点运算部件中完成。
一般情况下，只能由 U流水线完成一条浮点操作指令；少数情况下,V流水线也能同时完成一条如浮点数交换这样的指令。
(4)以 BTB实现的动态预测
Pentium采用动态转移预测技术，来减少由于过程相关性引起的流水线性能损失 。
(1)超标量流水线有 U和 V两条流水线采用按序发射，按序完成调度策略
Pentium的新型体系结构特点下午 6时 5分 64
例如：向量计算,A*(B+C) 的 循环程序用 C语言为 for( i=1;i<=n;i++)
di=ai*(bi+ci)
水平处理法 (横向 )
d1=a1*(b1+c1)
d2=a2*(b2+c2)
·
·
dn=an*(bn+cn)
垂直处理法（纵向）
B+C?E(1到 n)
A*E?D(1到 n)
5.5 向量的流水处理 5.5.1 向量处理方式适合于流水处理分组纵横处理法分成 k组,每组长度为 m，组内垂直处理，组间水平处理。
n=k*m+r (r为第 k+1组剩余分量 )
Bi+Ci?Ei (1到 m) Bi+Ci?Ei (m+1到 2m)
Ei*Ai?Di (1到 m) Ei*Ai?Di (m+1到 2m) ……
下午 6时 5分 65
5.5.2 向量处理机的结构一,存储器 ——存储器结构参加运算的向量数据在存储器中，运算的结果也送到存储器中，其结构与数据流的示意图如下图所示。如果以向量加法为例子 C=A+B
存储器
A
B
C
流水线运算部件一种能实现两个向量相加的流水结构的加法器下午 6时 5分 66
A
B 1 2 3 4
C=A+B
加法流水线部件
M1
M2
M3
M4
M5
M6
M7
M8
多模块存储器系统的向量处理机
A,B,C的向量长度为 8，
加法流水线分为 4个功能段，
主存储器采取了 8个存储体下午 6时 5分 67
功能部件 4
功能部件 3
功能部件 2
功能部件 1
存储体 M8
存储体 M7
存储体 M6
存储体 M5
存储体 M4
存储体 M3
存储体 M2
存储体 M1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 t
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
RB6 RB6 RA8 RA8 WC4 WC4
RB5 RB5 RA7 RA7 WC3 WC3
RB4 RB4 RA6 RA6 WC2 WC2
RB3 RB3 RA5 RA5 WC1 WC1
RB2 RB2 RA4 RA4
RB1 RB1 RA3 RA3
RA2 RA2
RA1 RA1
WC8 WC8
WC7 WC7
WC6 WC6
WC5 WC5
RB8 RB8
RB7 RB7
C=A+B向量处理时序图下午 6时 5分 68
向量处理机的组成
cray-1机，银河 yh-1,yh-2巨型机。以 CRAY-1机为例
．总体,cpu，存储器,I/O通道，外部设备
,CPU结构向量寄存器 8*64*64 指令缓存器 4*64*16
操作数寄存器 8*64*64 向量屏蔽 Vm 64位向量长度寄存器 Vl
地址寄存器，标量寄存器等。
CPU功能部件
12个可并行单功能流水部件
3个向量部件,加（ 3）逻辑（ 2） 移位（ 4）
3个浮点部件 加（ 6） 乘（ 7） 求倒数（ 14）
4个标量部件 2个地址功能部件存储器存取（ 7）
下午 6时 5分 69
二,寄存器 ——寄存器型（如 CRAY_1机）
主存储器
8个向量寄存器组
8个标量寄存器
8个地址寄存器
256个指令缓冲寄存器整数加 3
位移 4
逻辑 2
向量部件浮点部件浮点加 6
浮点乘 7
浮点倒数
14
整数加 3
整数乘 6
地址运算部件整数加 3
逻辑 1
位移 2-3
计数 3-4
标量部件
Cray_1向量计算机结构下午 6时 5分 70
5.5.3 增强向量处理性能方法
1．多功能部件并行,对于向量处理机浮点处理每个
vi都有单独总线输入到功能部件，每个功能部件有单独总线送到向量寄存器 Vi达到充分并行。每个运算是流水的，和其它操作可重叠。
2．相关时可进行链接处理下午 6时 5分 71
vj sj
…
…
vk
…
vi
1
2.
.
.
n
功能部件 …
vk
…
vi
1
2
.
.
.
n
功能部件
…
vj
主存
1
2
3
4
5
6
访存
7
vjθ vk vi sjθ vk vi mem vj
向量指令四种形式下午 6时 5分 72
3,向量的重叠处理
全并行
V1+V2 → V3
V4*V5→ V6
功能冲突
V1+V2→ V3
V4+V5→ V6
VI冲突
V1+V2 → V3 V1+V2→ V3
V4*V2→ V5 V4*V5→ V3
数据相关和功能部件相关
V1+V2 → V0
V1+V5→ V3
下午 6时 5分 73
链接技术,利用向量指令间存在的先写后读的数据相关性来加快向量指令序列执行速度的技术。
基本规则,只要操作数向量中的第一个元素可用，而且功能部件有空，向量运算可立即开始,只要不发生功能部件冲突和操作数寄存器冲突都可以通过全链接机构使数据相关指令功能并行处理。
适用情况,即第 1条指令的结果，是第 2条指令的操作数，这时
，所得到的第 1条指令的中间结果不必要等待全部向量元素都执行完才进行第二条指令的操作，可以将从一个流水线部件得到的结果直接送入下一个功能流水线部件的向量寄存器，形成两条指令的链接 。
例：
LD V3,A ； V3←A,访主存,读
ADDV V2,V0,V1 ； V2←V0+V1,浮点加
MULTV V4,V2,V3 ； V4←V2*V3,浮点乘下午 6时 5分 74
访存与浮点加并行，
再与浮点乘链接
LD V3,A
ADDV V2,V0,V1
MULTV V4,V2,V3
V0
V4
V1
V2 V31
3
2
4
5
6
1
3
2
4
5
6
1
3
2
4
5
6
浮点加浮点乘
D
B C
访存存储器 A
7
并行和链接操作图下午 6时 5分 75
若三条指令串行执行,即每次只有前条指令结束,才执行后继指令,那么三条指令执行的总时间为：
[(1+6+1)+N-1]+[(1+6+1)+N-1]+[(1+7+1)+N-1]=3N+22(拍 )
若第一,二条指令并行与第三条串行：
[(1+6+1)+N-1]+[(1+7+1)+N-1]=2N+15(拍 )
若第一,二条指令并行与第三条链接：
[(1+6+1)+(1+7+1)+(N-1)]=N+16(拍 )
可以看出采用并行与链接后，可以很有效的改善性能。
如果每一个时钟周期的延迟称为 1拍,在 Cray-1机中 LD指令需要 6拍,浮点加为 6拍,浮点乘为 7拍,假若向量寄存器的存与取的传送各为 1拍,内存的传送为 1拍,分别计算上述三条指令不同的执行方式所需的时间 。
下午 6时 5分 76
向量循环和分段开采技术向量寄存器型的向量机具有一个自然的长度，即每个向量寄存器中的向量元素个数，如 CRAY-1机为 64
一个向量寄存器，存放一代码段操作的长度。用它来控制向量操作的长度（包括向量的装载和存储）。当向量长度大于向量寄存器长度（长度以 MVL表示）时，按向量寄存器长度分段。
分段后，向量操作的长度等于或小于向量寄存器长度。分段后第一段长度为（ n mod MVL)，以后各段长度均为 MVL。一次处理一个向量段，对各段程序循环执行完成稀疏向量和对向量的递归处理都采用了相应改进技术在向量机中，为增加访存速率，大都采用多体存储器低位交叉编址访问，对数组元素有时按行，按列，按对角线访问，
为使访存不发生冲突，常使跨步和存储体数互为质数。
第五章 流水线处理技术
5.1 流水处理概述
5.2 流水线工作方式
5.3 流水线调度
5.4 流水中并行性进一步开发
5.5 向量流水处理技术本章重点见书 P193 5,1~5,9
下午 6时 5分 2
5.1 流水线处理概述一,CPU主要工作方式,
顺序
重叠
流水取指令 分析 执行 。。。
每阶段时间为 t，共 n条指令顺序串行 （ sequence）：
n
i
iii tttT
1
)( 执分取设指令工作方式分成取指令、分析、执行指令若各阶段执行时间相等，则共需 3 nt
优点,控制简单；
缺点,速度慢，机器各部件的利用率很低。
下午 6时 5分 3
重叠 （ Overlap）：在两条相近指令的解释过程中，某些不同解释阶段在时间上存在重叠部分。
包括一次重叠、先行控制技术和多操作部件并行。
上一条指令的执行阶段与下一条指令的取指阶段完全重叠； T=（ 2× n+1） t
将相邻两条指令的重叠时间再往前提前一个阶段；
T=3× t+（ n-1） × t=（ n+2） × t
一次重叠：把取指令操作隐含在分析,执行指令过程中,则在任何时候只允许上条指令,执行,与下条指令
,分析,相重叠 。 T=（ n+1） × t
实际执行时间：
n
n
i
ii
ttttT
执执分分
2
11
,m a x
若各段时间不等时，有下午 6时 5分 4
先行控制,分析部件和执行部件能分别连续不断地分析和执行指令，预取和缓冲相结合的技术,通过对指令流和数据流的先行控制，使指令分析器和执行部件能尽量连续并行工作。
执行时间,
n
i
ittT
1
1 执分先行分析 k 执行 k
分析 k+1 执行 k+1
分析 k+2 执行 k+2
多操作部件并行,采用有多个功能部件的处理机，把 ALU的多种功能分散到几个具有专门功能的部件中，这些功能部件可以并行工作，使指令流出速度大大提高。
下午 6时 5分 5
1、流水的概念特点流水,把一个重复时序过程分成若干个子过程，每个子过程都可有效的在其专用功能段上和其它子过程同时执行的一种技术。
5.2、流水工作方式取指 访存执行译码 写回
IF ID EX MEM WB
S1 S2 S3 S4 S5
输入 输出指令的流水处理流水线的基本结构中主要包括三大部分：锁存器,时钟,功能站 。
流水线中每个站都是由一些执行算术和逻辑功能的组合逻辑线路组成的,它们可以互相独立地对流过的信息进行某种操作,
相邻两站由高速锁存器 （ latch） 隔开,信息在各站间的流动靠同时送到各站的时钟信号来控制 。
下午 6时 5分 6
S1 S2 Sk
输入 输出流水线的基本结构
.….…..
时钟下午 6时 5分 7
...1 2 3 4 5,....,n-1 n
...1 2 3 4 5,....,n-1 n
...1 2 3 4 5,....,n-1 n
...1 2 3 4 5,....,n-1 n
1
2
3
4
△ t0 △ t0 △ t0 △ t0
T0=m △ t0
n △ t0
T
(m-1) △ t0
(n-1) △ t0
填入 正常 排空流水时空图空间时间下午 6时 5分 8
2、流水线特点,
1）流水一定重叠，比重叠更苛刻。
2）一条流水线通常有多个流水段组成。
3）每段有专用功能部件，各部件顺序连接，不断流。
4）流水线有建立时间、满载时间、排空时间，
5）各段时间尽量短、一致；不一致时最慢子过程为瓶颈。
6）给出指标如最大吞吐率，为满负载最佳指标。
建立时间,在流水线开始时有一段流水线填入时间,使得流水线填满 。
正常流动时间,流水线正常工作,各功能段源源不断满载工作 。
排空时间,在流水线第一条指令结束时,其他指令还需要一段释放时间 。
下午 6时 5分 9
1 2 3 4
出入非线性流水线
3、流水的分级、分类分级,（处理的级别分类）
部件级：将复杂的算逻运算组成流水工作方式；
指令级：把一条指令解释过程分成多个子过程 ；
处理机级：每个处理机完成某一专门任务，各个处理机所得到的结果需存放在与下一个处理机所共享的存储器中其他分类：
功能：单功能流水线（如 CRAY-1）、多功能流水线
（如 TI-ASC）
工作方式：静态流水线、动态流水线
连接方式：线性、非线性
处理数据：标量流水、向量流水下午 6时 5分 10
(1)ASC算术运算流水线（多功能）
输入减阶对阶移位相加规格化相乘累加输出
1
2
3
4
5
6
7
8
4、流水线举例输入减阶对阶移位相加规格化输出
1
2
3
4
5
8
加输入相乘累加输出
1
6
7
8
乘下午 6时 5分 11
...1 2 3 4,....,n-1 n
...1 2 3 4,..,.,n-1 n
...1 2 3 4,....,n-1 n
...1 2 3 4,.,n-1 n
1
2
3
4
5
8
6
7
...1 2 3 4,.,n-1 n
...1 2 3 4,....,n-1 n
时间空间
(段号 )
浮加一 二 三 四二 三一 二一一定乘
...
...
静态多功能流水线时 -空图静态流水线,只有当进入的是一串相同运算的指令时，流水的效能才得以发挥，才能使各个功能段并行地对多条指令的数据进行流水处理。
下午 6时 5分 12
...1 2 3 4 5,....,n-1 n
...1 2 3 4 5,....,n-1 n
...1 2 3 4 5,....,n-1 n
...1 2 3 4 5,....,n-1 n
1
2
3
4
5
8
6
7
...1 2 3 4 5,....,n-1 n
...1 2 3 4 5,....,n-1 n
时间浮加 定乘一 二 三 四 五 六一 二 三 四 五 六七一 二 三 四 五一 二 三 四动态多功能流水线时 -空图区别,如果从软硬功能分配的观点上来看,静态流水线其实是把功能负担较多地加到软件上,以简化硬件,动态流水线则是把功能负担较多地加在硬件上,以提高流水的效能 。
下午 6时 5分 13
（ 1） VAX8600的流水结构
a,I部件,预取指令，操作码译码，预取操作数，并存放运算结果。
b,E部件,执行指令。
c,F部件 ；浮点加速器。
d,M部件,控制 CPU和输入输出设备对主存的访问，有 16k
字节的 cache和把虚存地址转换成实存地址的地址转换表
（快表）
e,操作台,提供同操作员，引导设备和远程诊断的界面。
指令流水线,一条指令的取指令、译码、取操作数和执行等几个过程能同它前后的指令在时间上重叠，用这种指令重叠的方法构成的流水线就是指令流水线，又叫指令先行控制。
2,VAX8600和长城 386计算机的指令流水线下午 6时 5分 14
操作台
E部件
F部件
I部件 M部件主存标准 SBI
适配器选件 SBI
适配器
SBI
SBI
C总线诊断总线写总线操作数总线虚拟地址存储器数据总线适配器总线数组总线
I/O子系统
I/O子系统
VAX8600的 CPU结构图下午 6时 5分 15
取指令指令译码形成操作数地址取操作数执行指令存储结果
N-1
N-2 N-1
N-2 N-1
N-1
N-1
N-1 N+1
N+1
N+1
N+1
N+1
N+1
N+2
N+2
N+2
周期操作
VAX8600指令流水线的工作顺序实框：表示 CPU在执行一条典型的指令时的动作顺序。
虚线：表示 6个动作是各自分开进行的，可以同其它指令的动作并行进行。
下午 6时 5分 16
（ 2）长城 386指令流水线
内部有六个部件总线接口部件,同外部的接口 取指令、读写数据。
I部件：
指令预取部件,取指令放在 16个字节指令预取队列。
指令译码部件,形成指令微码，指令队列中可放 3条指令
E部件：
执行部件,控制、数据部件、保护测试部件分段部件分页部件 存储管理部件取指令 1 取指令 2 取指令 3 取指令 4 存结果 1 取指令 5 取指令 6
指令译码器 1 指令译码 2 指令译码 3 指令译码 4 指令译码 5
执行 1 执行 2 执行 3 执行 4
地址变换和 MMU 地址变换和 MMU
80386的指令流水处理下午 6时 5分 17
5,2,4 流水线性能分析计算一,技术指标衡量流水线处理机的性能主要是吞吐率,加速比和效率 。
1,吞吐率,单位时间内能处理的指令条数或能输出的数据量 。 吞吐率越高,计算机系统的处理能力就越强 。 就流水线而言,吞吐率就是单位时间内能流出的任务数或能流出的结果数 。
最大吞吐率：流水线达到稳定状态后可获得的吞吐率 。
（ 1） Tpmax=1/?t
（ 2） TPmax=1/ max{?t1,?t2,?t3,?t4}
,瓶颈”子过程：
1 2 3 4
t?t 3?t?t
下午 6时 5分 18
子过程 3为瓶颈段的时空图最大吞吐率 TPmax=1/3?t
S
T
S1
S2
S3
S4
t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t12 t13 t14 t15
1 2 3 4
t11
1 2 3 4
1 2 3 4
1 2 3 4
输出下午 6时 5分 19
1 312 32 33 4
2 1 4
3a
3b
3c
t? t? t? t? t? t?
t?t? t?
t?3
t?3
t?3
瓶颈段细分重复设置瓶颈流水段解决瓶颈有两种方法
A：
B：
下午 6时 5分 20
T
重复设置瓶颈流水段后的工作时空图
S
S1
S2
S3a
S3c
S3b
S4
1 2 3 54 6 7 8 9 10 11 12
1 2 3 54 6 7 8 9 10 11 12
1 4 7 10
2 5 8 11
3 6 9 12
1 2 3 54 6 7 8 9 10 11 12
t1 t12 t17
下午 6时 5分 21
实际吞吐率
（ 1） 完成 n条指令的解释共需时间
T=mt0+(n-1)?t0，
（ 2） 流水线的实际吞吐率为可以看出不仅实际的吞吐率总是小于最大的吞吐率,而且只有当 n>>m时,实际的吞吐率才能接近于理想的最大吞吐率 。
n
m
TP
n
mttntm
nTP
11
m a x
)11(
1
)1(
000
下午 6时 5分 22
2,效率,设备的利用率，直接反映了处理机结构有效程度。
流水线有建立时间、排空时间，不总是满负载工作。
η = N个任务实际占用的时 -空区M各段总的时 -空区各段时间相等：
η = m*Tm*n* △ t =TP △ t
各段时间不等,n *Σ △ ti
m*[Σ △ ti+(n-1)△ tj]m
i=1
η =
m
i=1
下午 6时 5分 23
m
i
ii tn
1
m
i
m
i
jii tnt
1 1
)1(?
其中，分母为 m个段总的加权时空区，分子为 n个任务总的加权时空区设备利用率占整个系统设备利用率的比重不同,可以给每个段赋予不同的,权,值?i,这样,线性流水线总效率的一般式为：
下午 6时 5分 24
Sp=T非流水T流水 = n*m*△ tM*△ t+(n-1)*△ t = n*mm+n-1 = m
1+ nm-1
各段时间相等,
各段时间不等,
Sp= n *Σ △ ti
m
i=1
Σ △ ti+(n-1)*△ tj
m
i=1
3,加速比,M段流水线的速度与等效的非流水线的速度之比。
讨论：
1．减少瓶颈的办法：多套并行和细分慢的子过程。
2．指令串不相同，需功能切换（尽量相同）向量流水。
3．非线性流水控制输入，使不碰头。
4,T尽量小，尽量一致，减少相关。
5．指标给的为最佳值 。
下午 6时 5分 25
五,实例分析,性能分析（实测法,分析法,时空图法）,
例 1,四段流水线,△ t1=△ t3=△ t4=△ t,△ t2=3△ t,4个任务,10
个任务时 TP,η,SP 。
η = N个任务实际占用的时 -空区M各段总的时 -空区
n=10，
η = 6*10△ t4*6△ t+9*3*4△ t = 6024+108 = 115
TP= 106*△ t+3*9* △ t = 1033*△ t
≈45%
（ 1）分析法,各段时间不等
=Sp= n *Σ △ ti
m
i=1
Σ △ ti+(N-1)*△ tj
m
I=1
10*6 △ t
(6+3*9) △ t =
20
11 =1.8
TP= nΣ
△ ti+(n-1)△ tj
m
i=1
下午 6时 5分 26
时间
1 2 3 4
31 1 1 2 2 32 3 4
1 2 3
1 2 3
1
2
3
4
4 4
4
4
3△ t 3△ t
空间
(2) 时空图法,
Tp=4/((6+3*3) △ t)=4/(15△ t)=0.267(1/△ t)
=24 △ t /(4*15△ t)=2/5=40%
Sp=4*6 △ t/15△ t=8/5=1.6
n=4时 ;
n=10时 ;同上,
下午 6时 5分 27
比较,
N=4 0.267
N=10 0.303
N=100 0.33
40
%
45%
49%
1.6
1.8
1.98
n spTp(1/△ t)
n=4,m=4
说明,N>>M流水性能才发挥得更好下午 6时 5分 28
例 2,以浮点加法运算为例（四段流水线）各段时间相等，如何求吞吐率、效率。
求 Z=A+B+C+D+E+F+G+H,TP,η,Sp 注意有相关时间空间
Z=A+B+C+D+E+F+G+H
1 2 3 4
5 6
7
TP=7/15△ t,
η =7*4/(15*4)=7/15
解：
Sp=4*7/15=28/15=1.87
1
1
1
1
2
2
2
2
3
3
3
3
4
4
4
4
5
5
5
5
6
6
6
6
7
7
7
7
下午 6时 5分 29
例 3,ASC计算机功能算术运算流水线各段时间相等,6次浮点加、
5次定点乘的吞吐率,效率,加速比 M=8,N=11.
分析,T加 =6+(6-1)*1=11 (△ t) T乘 =4+(5-1)*1=8 (△ t)
则 TP= 11/(11+8)△ t =11/19 △ t
Sp= 56 △ t /19 △ t =2.94
η = (6*6+5*4) △ t /(19*8△ t)=6/52=7/19
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1
2
3
4
5
8
6
7
1 2 3 4 5 6
1 2 3 4 5 6
时间浮加 定点乘一 二 三 四 五一 二 三 四 五一 二 三 四 五一 二 三 四 五下午 6时 5分 30
1,分段时间 △ t尽量小、尽量一致,TP=1/△ t，则 TP越大；
若 m太多，则处理时间长，锁存器越多。
2,△ t选取,各级微操作需逻辑级门,每个门的延时加走线延时再加 3%冗余量,
3.缓冲深度影响,（缓冲器个数）
4.非线性流水的合理控制
5.2.5 流水的控制和设计一、时序和缓冲二,相关处理定义,相近指令出现某种关联使不能同时执行。
资源相关
数据相关
控制相关下午 6时 5分 31
1,资源相关资源相关是指当有多条指令进入流水线后在同一机器周期内争用同一功能部件所发生的冲突例 1：
435
216
XXX
XXX
两条指令同时要用一个加法器
ALU LOAD/STORE
IF 取指 取指
ID 译码、读寄存器堆 译码、读寄存器堆
EX 执行 计算访存有效地址
MEM - 访存（读或写）
WB 结果写回寄存器堆 将读出的数据写入寄存器堆指 令流水段不同类型指令中各流水段进行的操作下午 6时 5分 32
两条指令同时访存造成资源相关
MEMEXIDIF指令
i+4
WBMEMEXIDIF指令i+3
WBMEMEXIDIF指令i+2
WBMEMEXIDIF指令i+1
WBMEMEXIDIFLoad指令
87654321时钟指令冲突取指 译码 执行 访存 写回例 2：
下午 6时 5分 33
EXIDIF指令
i+4
MEM EXIDIF停顿指令
i+3
WBMEMEXIDIF指令
i+2
WBMEMEXIDIF指令
i+1
WBMEMEXIDIFLoad
指令
87654321时钟指令
9
WB
MEM
使 i+3指令停顿一拍进入流水线，以解决访存相关或重复设置一个存储器解决方法：
下午 6时 5分 34
例：有 i 和 j两条指令,i指令在前,j指令在后，则三种不同类型的数据相关的含义为：
RAW读写 (先写后读 ) - 指令 j 试图在指令 i 写入寄存器前就读出该寄存器内容，这样，指令 j就会错误地读出该寄存器旧的内容。
（改用相关） i,R1+R2->R3 j,R3*R4->R5
WAR写读 (先读后写 ) - 指令 j 试图在指令 i读出寄存器之前就写入该寄存器，这样，指令 i就错误地读得该寄存器新的内容。
（用改相关） i,R3*R4->R5 j,R1+R2->R3
WAW写写 (先写后写 ) - 指令 j试图在指令 i写寄存器之前就写入该寄存器，这样，两次写的先后次序被颠倒，就会错误地使由指令 i写入的值成为该寄存器内容。
（改改相关） i,R1*R2->R3 j,R4+R5->R3
2,数据相关顺序流动不按顺序流动不按顺序流动下午 6时 5分 35
例 1：如果流水线要执行以下的两条指令
X1=X2+X3
X4=X1-X5
这是一个典型的先写后读（ RAW）相关。
例 2：结果寄存器的冲突
X6=X1+X2
X6=X4*X5
这是个先写后写的写 -写相关，两条指令都要用 X6存放结果，此时第二条指令也要等待第一条指令完成后才能写。
例 3：一条指令要把结果存放到上一条指令存放操作数的寄存器中时发生的冲突。
X5=X4*X3
X4=X0+X6
这是个先读后写的写 -读相关。如果这两条指令接连地送到乘法功能部件和加法功能部件中，由于加法比乘法快得多，第二条的结果 X4先产生，但必须等待第一条指令做完后才能送 X4。
下午 6时 5分 36
解决办法主要用软件和硬件技术：
时间推后法
旁路技术或相关专用通路技术例子：流水执行和相关 （资源相关）
有四段流水线,IF（取指令 ）,ID（译码，取数）,
EX（执行） WR（写回）
PC值 指令 流水各段
n,load A IF ID EX WR
n+1,load B IF ID EX WR
n+2,add A,B IF ID 气泡 EX WR
n+3,store C IF ID 气泡 EX WR
n+4,jump K IF ID EX WR
n+5,load E 停顿 停顿 停顿。。
n+6 ……… 停顿 。。。。。。
K,IF ID EX
例子中有资源相关、有控制转移相关，这将影响流水线的指标。
下午 6时 5分 37
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
ADD
R1,R2,R3
SUB R4,R1,R5
AND
R6,R1,R7
OR R8,R1,R9
XOR
R10,R1,R11
定向传递 R1值数据相关和定向传递指令下午 6时 5分 38
IF EX MEM ID R WBW
IF EX MEM ID R WBW
IF EX MEM ID R WBW
IF EX MEM ID R WBW
IF EX MEM ID R WBW
ADD
R1,R2,R3
SUB R4,R1,R5
AND R6,R1,R7
OR R8,R1,R9
XOR R10,R1,R11
定向传递 R1值减少定向传送次数的方法在 ID段读寄存器堆操作安排在后半部分，在 WB段写寄存器堆操作安排在前半部分，以减少定向传输操作。
下午 6时 5分 39
ALU
运算结果写 RF RF 读 RF ALU
操作数寄存器专用通路（旁路）
寄存器堆 RF
多路开关 多路开关
ALU
R4
R1
缓冲寄存器（ R1,R4）
旁路下午 6时 5分 40
3,控制转移冲突,无条件转移和条件转移引起的
（转移指令概率占 1/4左右，不可忽视）
猜测法,按一个方向流水，用历史记录提高猜测率；
预取转移目标,向两个分支方向预取指令；
加快和提前形成条件码,有的指令的条件码并不一定要等执行完毕得到运算结果后才能形成；
优化延迟转移技术
a.将转移指令前的那条指令调度到延迟槽中；
b.将转移目标处的那条指令调度到延迟槽中；
c.将转移不发生时该执行的那条指令调度到延迟槽中。
设置特殊循环指令，加快短循环处理
3.转移处理下午 6时 5分 41
三,中断
流水机器处理中断的关键 不在于如何缩短断流时间，而是如何处理好断点现场及中断后的恢复问题。
不精确断点法 (同外部设备中断处理一样 )：不论第 i条指令在流水线的哪一段发出中断申请，都不再允许那时还未进入流水线的后续指令再进入
精确断点法,不论第 i条指令是在流水线中哪一段发的中断申请，给中断处理程序的现场全都是对应第 i条的，在第 i
条之后进入流水线的指令的原有现场都能恢复 (增加设备，
加许多缓冲器，各功能段状态保留）
下午 6时 5分 42
5.3 先进的流水技术一、先进的流水调度方法 - 动态调度静态调度,借助软件对指令执行顺序进行调度，以减少由于流水线中存在相关冲突而引起流水线的停顿时间。目前比较流行。
动态调度,通过硬件重新安排指令的执行顺序以减少流水的停顿。
优点：
（ 1）能处理某些在编译时无法知道的相关情况
（ 2）能简化编译程序设计
（ 3）使代码有可移植性缺点,相应的硬件较为复杂。
下午 6时 5分 43
IF ID
整数部分浮点加浮点乘浮点除
RF
记录控制器
EX MEM WB
指令控制 /状态 控制 /状态集中式动态调度寄存器堆集中式调度,依靠硬件在程序运行过程中对可能出现的相关情况加以检测，从而保证流水线中的各个功能部件能最大限度地重叠工作。
下午 6时 5分 44
分布式动态调度（比集中式调度更灵活）
对 IBM360/91机是通过给 FLR设置一个“忙”标志来判别指令间所用的数据是否发生相关,另外还有一个标志（即站号）
表示数据由何处来，用站号位控制相关通路连接，采用公共数据总线 CDB来实现内部数据专用通路的连接。
IBM360/91的浮点运算器部分包括了以下主要部件：
（ 1） 运算部件,一个加法部件和一个乘除部件。
（ 2）保存站,加法部件中有 A1~A3三个保存站，乘除部件有 M1和 M2两个保存站，用来保存当前参加运算的数据。
（ 3） 指令操作缓冲栈,存放经分析后由指令部件送来的指令，译码后，
产生相应的控制信号送到各个部件。
（ 4）浮点操作数寄存器（ FLB）,存放由主存预取来的操作数。
（ 5）浮点寄存器（ FLR）,存放操作数的寄存器。
（ 6） 存储数据缓冲站（ SDB）,存放将写入存储器的结果数据，也有站号。
（ 7） 公共数据总线（ CDB）,以上各部件间的连接总线。
下午 6时 5分 45
浮点操作数缓冲器
（ FLB）
控制浮点操作栈
（ FLOS）
站忙 浮点寄存器号位 （ FLR）
控 站 存数缓冲器制 号 （ SDB）
译码器站号 源 1 站号 源 2 控制加 法 器 乘 / 除 法 器存储器总线站号
0001
0110
6
5
4
3
2
1
F7
6
5
4
3
F2
1
F0
1010
1011
1100
A1
A2
A3
M1
M2
1000
1001
指令处理部件
FLB总线 FLR总线站号 源 1 站号 源 2 控制
CDB
公共数据总线下午 6时 5分 46
特点：
（ 1）由于为加法器和乘法部件分别设置了 3个和 2个保存站，
从而减小了资源使用冲突的机会。仅当这些保存站读都处于忙碌状态时，才有可能发生资源使用冲突。
（ 2）调度算法使用保存站，通过对寄存器重新命名（改写站号）自然地消除了 WAR和 WAW数据相关可能性。
（ 3）通过对 FLR寄存器忙位状态的判别，来检测是否存在
RAW数据相关。
（ 4）借助 CDB公共数据总线作为专用相关通路，将有关数据直接送往所有需要它的功能部件，而不必先写入寄存器，
然后再从此寄存器读出。
由于这种调度是通过 各部件‘忙位’、‘站号位’、
‘ CDB数据总线’来实现的故称分布式调度下午 6时 5分 47
预取指令的 PC
=
是否查找 预测 PC值转移发生预测 PC值应送入 PC中预测转移发生或不发生转移不发生，按正常顺序进行动态硬件预测转移方法在程序运行时，借助硬件来动态地预测转移方向。实际上，这是一种尽早生成转移目标地址的方法，它将过去发生过的转移指令地址存入一个由类似 cache、称为 BTB（ Branch target buffer）的转移目标缓冲器中。其中，
转移指令地址作为标志，供检测用。
下午 6时 5分 48
5.4 流水的实现和控制一、非线性流水线的冲突及调度非线性流水线,由于段间有前馈和反馈通路任务，执行过程中可能会多次通过同一流水段，发生几个任务同时争用同一流水段的现象，这就是 功能段的使用冲突 。
解决方法,间隔恰当的拍数后再向流水线送入下一个任务。这就需要对流水线作适当的调度。
流水线调度常借助于二维预约表和状态转换图来进行分析
根据预约表可较容易地推算出一个任务执行时，各段所需的间隔周期拍数。
下午 6时 5分 49
S/t 1 2 3 4 5 6 7 8 9
1 X X
2 X X X
3 X
4 X X
5 X X
二维预约表图中每一行代表 P的一个段,每一列表示相应的时钟周期 。
若某个任务在周期 ti需要使用 Sj段进行处理,则在行 Sj和列 ti
的相交处以,?” 表示 。
条件,非线性、单功能流水线 P，由 K段组成，每个任务流过流水线需 N个时钟周期（ t1,t2,…,t n），段为纵坐标，时间为横坐标禁止表 F={1,5,6,8}
下午 6时 5分 50
10110001
10110111 10111101
1011111110111011
一个 n位的位向量 C=(Cn,Cn-1,...,C2,C1)称为冲突向量。
其中第 i位状态表示于当时相隔 i拍时间时，是否允许输入新任务。如允许输入，则 Ci=0,否则 Ci=1。
非线性流水线预约表相应状态图
4
2
>=7>=7
3 4
>=7
>=7
>=7 原始冲突向量
23
下午 6时 5分 51
过程,
1,按给出的预约表写出允许表和禁止表 F={1,5,6,8}；
2,写出 n位初始冲突向量（ 10110001）；
3,按禁止表约束条件列出新的冲突向量，直到不再生成新的冲突向量为止（当前冲突向量和初始冲突向量按位“或”）；
4,画出用冲突向量表示的流水线状态转移图（两个冲突向量之间用有向弧连接，并用数字表示引入后继任务用的间隔节拍，写出各种可能的状态转换）；
5,列出各种调度方法平均间隔拍数；
6,求出最佳等间隔和非等间隔调度拍数；
本例子中非等间隔调度为 3拍,4拍 ……,平均间隔为 3.5拍，而等间隔调度为 7拍。
下午 6时 5分 52
5.4、流水中指令级并行性的进一步开发粗粒度并行性,在多处理机上分别运行多个进程，由多台处理机合作完成一个程序；
细粒度并行性,指在一个进程中进行操作一级或指令一级的并行处理。
RISC机进一步开发细粒度并行性
5.4.1 超级标量方法每个时钟周期内能启动 n条指令主要特点：
（ 1）配置有多个性能不同的处理部件，采用多条流水线并行处理。
（ 2）能同时对若干条指令进行译码，将可并行的指令送往不同的执行部件，从而达到每个周期启动多条指令。
（ 3）在程序运行期间由硬件（通常是状态记录部件和调度部件）
完成指令调度。
下午 6时 5分 53
0 1 2 3 4 5 6 T
取指 译码 执行 写回每拍启动 3条指令要求并行度 =3
超级标量机
1,超级标量计算机的原理：
配置多个功能部件多个译码器，寄存器端口，总线，能同时执行多个操作。
下午 6时 5分 54
2,超标量流水线调度
按序发射按序完成
按序发射无序完成
无序发射无序完成无论那种调度策略，都要保证程序运行的最终结果是正确的，
Pentium处理器采用的是按序发射按序完成策略
PentiumII/III处理器采用的是按序发射无序完成指令发射：启动指令进入执行段的过程；
指令发射策略：指令发射所使用的协议或规则 。
按序发射：当指令按策划功能序的次序发射时,称之为按序发射 （ in-orderissue） 。
无序发射：为改善流水线性能,可以将有相关的指令推后发射,而将后面的无相关性的指令提前发射,即不按程序原有次序发射指令,称之为无序发射 （ out-of-order） 。
下午 6时 5分 55
以一条长指令实现多个操作的并行执行，减少存储器访问主要特点：
（ 1）单一的控制流。只有一个控制器，每个周期启动一条指令。
（ 2）超长指令字被分成多个控制字段，每个字段直接独立地控制每个功能部件。
（ 3）含有大量的数据通路和功能部件，由于编译器在编译时间已考虑可能出现的数据相关和资源相关，故控制硬件较简单。
（ 4）在编译阶段完成超长指令中多个可并行执行操作的调度。
5.4.2 超长指令字计算机下午 6时 5分 56
0 1 2 3 4 5 6 T
3个操作每拍启动一条长指令，执行 3个操作，相当于 3条指令，要求并行度
=3
超长指令字计算机（ VLIW）的原理结构下午 6时 5分 57
5.4.3 超级流水方法特点,超流水结构是把每一个流水级 （ 一个周期 ） 分成多个
（ 例如 3个 ） 子流水级,而在每一个子流水级中取出的仍只有一条指令,但总的来看,在一个周期内取出了三条指令 。
对于超流水线结构,其中指令部件可以只有一套,也可以有多套独立的执行部件 。 它虽然每个机器周期只能流出一条指令,但它的周期比其它机器短,一台 m度的超级流水线计算机的周期为一般机器周期的 1/m,它的一个操作需要 m个周期,因而在流水线能充分发挥作用时,其并行度能达到 m。
下午 6时 5分 58
每 1/2拍启动一条指令，要求并行度 =2
超级流水线的原理结构图
0 1 2 3 4 5 6
下午 6时 5分 59
这种方法主要通过提高流水线运行速度来增强机器性能。为提高运行速度，必须要加深流水深度，既增加流水段数，以减少每一段的延迟时间，这样就可加快流水线的运行频率。
下面是 R4000超级流水情况分 8段：取指 1（ IF），取指 2（ IS）
读 RF，执行（ EX），取数 1（ DF），取数 2（ DS），标记检查
（ TC），写 RF（ WB）
IF IS RF EX DF DS TC WB
IF IS RF EX DF DS TC WB
IF IS RF EX DF DS TC WB
IF IS RF EX DF DS TC WB
IF IS RF EX DF DS TC WB
IF IS RF EX DF DS TC WB
IF IS RF EX DF DS TC WB
IF IS RF EX DF DS TC WB
流水线周期主时钟周期流水深度 =8
下午 6时 5分 60
5.4.4 超级流水标量计算机可以把超标量技术与超流水技术结合在一起，这就是超标量超流水线处理机。超标量超流水线处理机在一个时钟周期内要发射指令 n次，每次发射指令 m条，因此，超标量超流水线处理机每个时钟周期总共要发射指令 m*n条。
IF
IF
IF
ID
ID
ID EX
EX
EX WR
WR
WR
IF
IF
IF
ID
ID
ID EX
EX
EX WR
WR
WR
IF
IF
IF
ID
ID
ID EX
EX
EX WR
WR
WR
指令
I3
I2
I1
1 2 3 4 5 6
时钟周期超标量超流水线处理机的指令执行时空图下午 6时 5分 61
Pentium流水线结构（五级双流水，满足配对法则）
一个周期执行两条整数指令
11
12
13
14
15
16
17
18
11
12
13
14
15
16
17
18
11
12
13
14
15
16
17
18
11
12
13
14
15
16
17
18
11
12
13
14
15
16
17
18
预取级（取指令）
译码级 1（译码）
译码级 2（计算地址）
执行级（取数、运算）
写回级
U流水 V流水一,Pentium的超标量流水线下午 6时 5分 62
PentiumCPU结构
（ 1）超标量流水线总线部件预取地址
64位数据总线
32位数据总线控制指令指针转移和目标
BTB
转移目标缓冲
TLB 指令
CACH
E
8KB
预取缓冲指令译码控制
ROM
控制部件转移和目标验证地址地址产生
（ U流水线）
地址产生
（ V流水线）
整数寄存器堆ALU(U
流水线 )
ALU(V
流水线 )
桶形位移器
32
32
32 32
32
TLB
数据
CACH
E 8KB
浮点部件控制寄存器堆加法除法乘法
80
80
下午 6时 5分 63
(2)分立的指令 CACHE和数据 CACHE
不仅使指令预取和数据读写能无冲突地同时完成，而且可同时与 U,V两条流水线分别交换数据。
(3)重新设计的浮点运算部件执行过程是分为 8段的流水线。前 4段为指令预取（ PF）、指令译码（ D1）、地址生成（ D2）、取操作数（ EX），在 U,V流水线完成；后 4段为执行 1（ X1）、执行 2（ X2）、结果写回寄存器堆（ WF）、错误报告（ ER），在浮点运算部件中完成。
一般情况下，只能由 U流水线完成一条浮点操作指令；少数情况下,V流水线也能同时完成一条如浮点数交换这样的指令。
(4)以 BTB实现的动态预测
Pentium采用动态转移预测技术，来减少由于过程相关性引起的流水线性能损失 。
(1)超标量流水线有 U和 V两条流水线采用按序发射，按序完成调度策略
Pentium的新型体系结构特点下午 6时 5分 64
例如：向量计算,A*(B+C) 的 循环程序用 C语言为 for( i=1;i<=n;i++)
di=ai*(bi+ci)
水平处理法 (横向 )
d1=a1*(b1+c1)
d2=a2*(b2+c2)
·
·
dn=an*(bn+cn)
垂直处理法（纵向）
B+C?E(1到 n)
A*E?D(1到 n)
5.5 向量的流水处理 5.5.1 向量处理方式适合于流水处理分组纵横处理法分成 k组,每组长度为 m，组内垂直处理，组间水平处理。
n=k*m+r (r为第 k+1组剩余分量 )
Bi+Ci?Ei (1到 m) Bi+Ci?Ei (m+1到 2m)
Ei*Ai?Di (1到 m) Ei*Ai?Di (m+1到 2m) ……
下午 6时 5分 65
5.5.2 向量处理机的结构一,存储器 ——存储器结构参加运算的向量数据在存储器中，运算的结果也送到存储器中，其结构与数据流的示意图如下图所示。如果以向量加法为例子 C=A+B
存储器
A
B
C
流水线运算部件一种能实现两个向量相加的流水结构的加法器下午 6时 5分 66
A
B 1 2 3 4
C=A+B
加法流水线部件
M1
M2
M3
M4
M5
M6
M7
M8
多模块存储器系统的向量处理机
A,B,C的向量长度为 8，
加法流水线分为 4个功能段，
主存储器采取了 8个存储体下午 6时 5分 67
功能部件 4
功能部件 3
功能部件 2
功能部件 1
存储体 M8
存储体 M7
存储体 M6
存储体 M5
存储体 M4
存储体 M3
存储体 M2
存储体 M1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 t
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
RB6 RB6 RA8 RA8 WC4 WC4
RB5 RB5 RA7 RA7 WC3 WC3
RB4 RB4 RA6 RA6 WC2 WC2
RB3 RB3 RA5 RA5 WC1 WC1
RB2 RB2 RA4 RA4
RB1 RB1 RA3 RA3
RA2 RA2
RA1 RA1
WC8 WC8
WC7 WC7
WC6 WC6
WC5 WC5
RB8 RB8
RB7 RB7
C=A+B向量处理时序图下午 6时 5分 68
向量处理机的组成
cray-1机，银河 yh-1,yh-2巨型机。以 CRAY-1机为例
．总体,cpu，存储器,I/O通道，外部设备
,CPU结构向量寄存器 8*64*64 指令缓存器 4*64*16
操作数寄存器 8*64*64 向量屏蔽 Vm 64位向量长度寄存器 Vl
地址寄存器，标量寄存器等。
CPU功能部件
12个可并行单功能流水部件
3个向量部件,加（ 3）逻辑（ 2） 移位（ 4）
3个浮点部件 加（ 6） 乘（ 7） 求倒数（ 14）
4个标量部件 2个地址功能部件存储器存取（ 7）
下午 6时 5分 69
二,寄存器 ——寄存器型（如 CRAY_1机）
主存储器
8个向量寄存器组
8个标量寄存器
8个地址寄存器
256个指令缓冲寄存器整数加 3
位移 4
逻辑 2
向量部件浮点部件浮点加 6
浮点乘 7
浮点倒数
14
整数加 3
整数乘 6
地址运算部件整数加 3
逻辑 1
位移 2-3
计数 3-4
标量部件
Cray_1向量计算机结构下午 6时 5分 70
5.5.3 增强向量处理性能方法
1．多功能部件并行,对于向量处理机浮点处理每个
vi都有单独总线输入到功能部件，每个功能部件有单独总线送到向量寄存器 Vi达到充分并行。每个运算是流水的，和其它操作可重叠。
2．相关时可进行链接处理下午 6时 5分 71
vj sj
…
…
vk
…
vi
1
2.
.
.
n
功能部件 …
vk
…
vi
1
2
.
.
.
n
功能部件
…
vj
主存
1
2
3
4
5
6
访存
7
vjθ vk vi sjθ vk vi mem vj
向量指令四种形式下午 6时 5分 72
3,向量的重叠处理
全并行
V1+V2 → V3
V4*V5→ V6
功能冲突
V1+V2→ V3
V4+V5→ V6
VI冲突
V1+V2 → V3 V1+V2→ V3
V4*V2→ V5 V4*V5→ V3
数据相关和功能部件相关
V1+V2 → V0
V1+V5→ V3
下午 6时 5分 73
链接技术,利用向量指令间存在的先写后读的数据相关性来加快向量指令序列执行速度的技术。
基本规则,只要操作数向量中的第一个元素可用，而且功能部件有空，向量运算可立即开始,只要不发生功能部件冲突和操作数寄存器冲突都可以通过全链接机构使数据相关指令功能并行处理。
适用情况,即第 1条指令的结果，是第 2条指令的操作数，这时
，所得到的第 1条指令的中间结果不必要等待全部向量元素都执行完才进行第二条指令的操作，可以将从一个流水线部件得到的结果直接送入下一个功能流水线部件的向量寄存器，形成两条指令的链接 。
例：
LD V3,A ； V3←A,访主存,读
ADDV V2,V0,V1 ； V2←V0+V1,浮点加
MULTV V4,V2,V3 ； V4←V2*V3,浮点乘下午 6时 5分 74
访存与浮点加并行，
再与浮点乘链接
LD V3,A
ADDV V2,V0,V1
MULTV V4,V2,V3
V0
V4
V1
V2 V31
3
2
4
5
6
1
3
2
4
5
6
1
3
2
4
5
6
浮点加浮点乘
D
B C
访存存储器 A
7
并行和链接操作图下午 6时 5分 75
若三条指令串行执行,即每次只有前条指令结束,才执行后继指令,那么三条指令执行的总时间为：
[(1+6+1)+N-1]+[(1+6+1)+N-1]+[(1+7+1)+N-1]=3N+22(拍 )
若第一,二条指令并行与第三条串行：
[(1+6+1)+N-1]+[(1+7+1)+N-1]=2N+15(拍 )
若第一,二条指令并行与第三条链接：
[(1+6+1)+(1+7+1)+(N-1)]=N+16(拍 )
可以看出采用并行与链接后，可以很有效的改善性能。
如果每一个时钟周期的延迟称为 1拍,在 Cray-1机中 LD指令需要 6拍,浮点加为 6拍,浮点乘为 7拍,假若向量寄存器的存与取的传送各为 1拍,内存的传送为 1拍,分别计算上述三条指令不同的执行方式所需的时间 。
下午 6时 5分 76
向量循环和分段开采技术向量寄存器型的向量机具有一个自然的长度，即每个向量寄存器中的向量元素个数，如 CRAY-1机为 64
一个向量寄存器，存放一代码段操作的长度。用它来控制向量操作的长度（包括向量的装载和存储）。当向量长度大于向量寄存器长度（长度以 MVL表示）时，按向量寄存器长度分段。
分段后，向量操作的长度等于或小于向量寄存器长度。分段后第一段长度为（ n mod MVL)，以后各段长度均为 MVL。一次处理一个向量段，对各段程序循环执行完成稀疏向量和对向量的递归处理都采用了相应改进技术在向量机中，为增加访存速率，大都采用多体存储器低位交叉编址访问，对数组元素有时按行，按列，按对角线访问，
为使访存不发生冲突，常使跨步和存储体数互为质数。
