北京化工大学
信息学院计算机科学系
Rlzhao@mail.buct.edu.cn.
主讲人：赵瑞莲
第五章 重叠、流水和向量处理机
流水线调度
线性流水线：简单，无反馈，每拍流入一个任务即可。
非线性流水线：由于段间有反馈回路，任务执行过
程中可能会多次通过同一流水段，发生几个任务同时
争用同一流水段的现象，调度相对复杂。
S1 S2 S3 S4 S5
入
①
②
③
④
⑥
⑤
⑦
⑧
⑦
⑨ 出
⑧
·
（ 2 ）由预约表形成禁止表
F
F={ 各段中冲突间隔拍数 }
本例： F={1 ， 5 ， 6 ，
8}
××5
××4
×3
×× ××2
××1
9876543
8
2
7
1
6
t
S
56 81
流水线调度
（ 3 ）由禁止表 F 形成初始冲突向量 C
0
C
0
= （ c
N － 1
…c
1
）， c
i
=1 冲突， c
i
=0 不冲
突。
本例： C
0
= （ 10110001 ）。
流水线调度
F={1 ， 5 ， 6 ， 8}
a. 任务每向前推进一拍， C
0
逻辑右移一位；
10110001
10110111 10111101
10111011
初始状态
3
4
2
7
流水线调度
（ 4 ）由初始冲突向量 C
0
形成状态转换图
C
0
= （ 10110001 ）
00010110
10110001
10110111
00001011
10110001
10111011
00000001
10110001
10110001
00101100
10110001
10111101
