-
Notifications
You must be signed in to change notification settings - Fork 32
/
3、非线性流水调度.md
150 lines (88 loc) · 5.89 KB
/
3、非线性流水调度.md
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
### 非线性流水调度
<img src="https://img-blog.csdnimg.cn/20201225152918991.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" width="45%" />
#### 基础概念
概念
* 启动距离
* 向一条非线性流水线的输入端连续输入两个任务之间的时间间隔称为非线性流水线的启动距离。
* 禁用启动距离
* 会引起非线性流水线功能段使用冲突的启动距离则称为禁用启动距离。
* 启动距离和禁用启动距离一般都用时钟周期数来表示，是一个正整数。
预约表
<img src="https://img-blog.csdnimg.cn/20201225152726916.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" width="35%" />
* 预约表
* 横向（向右）：时间（一般用时钟周期表示）
* 纵向（向下）：流水线的段
* 如果在第n 个时钟周期使用第k 段，则在第k行和第n 列的交叉处的格子里有一个√ 。
* 如果在第k 行和第n 列的交叉处的格子里有一个 个√ ，则表示在第n 个时钟周期要使用第k段 。
禁止表
* 一个由禁用启动距离构成的集合
* 根据预约表写出禁止表F
* 对于预约表的每一行的任何一对√，用它们所在的列号相减（大的减小的），列出各种可能的差值，然后删除相同的，剩下的就是禁止表的元素。
* 在上例中
* 第1行的差值只有一个：8；
* 第2行的差值有3个：1，5，6；
* 第3行只有一个√，没有差值；
* 第4和第5行的差值都只有一个：1；
* 其禁止表是：F= { 1，5，6，8 }
#### 冲突向量
初始冲突向量
* 冲突向量C
* 一个N位的二进制位串
* 根据禁止表F写出初始冲突向量C0
* 设C0 =（cN cN-1 …ci …c2 c1），则：<img src="https://img-blog.csdnimg.cn/20201225152757715.png" width="10%" />
* 当第一个任务流入流水线后，初始冲突向量C0决定了下一个任务需
间隔多少个时钟周期才可以流入
* ci =0 ：允许间隔i个时钟周期后送入后续任务
* ci =1 ：不允许间隔i个时钟周期后送入后续任务
* 对于上面的例子
• F= { 1，5，6，8 }
• C0 =（10110001）
新冲突向量
* 假设第二个任务是在与第一个任务间隔j个时钟周期流入，这时，由于第一个任务已经在流水线中前进了j个时钟周期，其相应的禁止表中各元素的值都应该减去j，并丢弃小于等于0的值。
* 对冲突向量来说，就是逻辑右移j位（左边补0）。
* 在冲突向量上，就是对它们的冲突向量进行“或”运算。
* SHR(j)(C0) ∨ C0
* 注：SHR (j)(C0) 表示对 C0 逻辑右移j位
任意一个任务进入后的新冲突向量
* 推广到更一般的情况
* 假设: Ck 为当前的冲突向量，j: 允许的时间间隔
* 则新的冲突向量为：SHR(j)(Ck) ∨ C0
* 获得所有可能的冲突向量，构成流水线状态集合
* 从初始冲突向量C0 出发，对于所有允许的时间间隔都按上述步骤求出其新的冲突向量，并且把新的冲突向量作为当前冲突向量
* 反复使用上述步骤，直到不再产生新的冲突向量为止。
冲突向量集合
* （1） C0 = （10110001）
* 引入后续任务可用的时间间隔为：2 、3 、4 、7 个时钟周期
如果采用 2 ，则新的冲突向量为：
（ 00101100 ） ∨ （ 10110001 ） = （ 10111101 ）
如果采用 3 ，则新的冲突向量为：
（ 00010110 ） ∨ （ 10110001 ） = （ 10110111 ）
如果采用 4 ，则新的冲突向量为：
（ 00001011 ） ∨ （ 10110001 ） = （ 10111011 ）
如果采用 7 ，则新的冲突向量为：
（ 00000001 ） ∨ （ 10110001 ） = （ 10110001 ）
* （2）对于新向量 （ 10111101 ）
* 其可用的时间间隔为 2 个 和 7 个 时钟周期。
* 用类似上面的方法，可以求出其后续的冲突向量分别为（10111101）和（ 10110001 ）。
* （3）对于其他新向量，也照此处理。
#### 状态转移图
流水线状态转移图三要素
* 流水线状态集合（所有可能的冲突向量）
* 有向弧：表示状态转移的方向
* 弧上的数字：表示引入后续任务（从而产生新的冲突向量）所用的时间间隔（时钟周期数）
<img src="https://img-blog.csdnimg.cn/20201225152826686.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" width="35%" />
调度方案与最优调度方案
* 调度方案
* 根据流水线状态图，由初始状态出发，任何一个闭合回路即为一种调度方案。
* 最优调度方案
* （任务进入流水线的）平均时间间隔最小的调度方案
* 列出所有可能的调度方案，计算出每种方案的平均时间间隔，从中找出其最小者即为最优调度方案。
* 上例中，各种调度方案及其平均间隔时间。
* 各种调度策略及平均延迟拍数
<img src="https://img-blog.csdnimg.cn/20201225152852663.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" width="35%" />
* 最佳方案：（3，4），平均间隔时间：3.5个时钟周期（吞吐率最高）
* 方案（4，3）的平均间隔时间也是3.5 ，但它不是最佳方案
* 等时间间隔调度方案
* 方案（3，4）是一种不等时间间隔的调度方案，与等间隔的调度方案相比，在控制上要复杂得多
* 为了简化控制，也可以采用等间隔时间的调度方案，但吞吐率和效率往往会下降不少
* 在上述例子中，等时间间隔的方案只有一个：（7），其吞吐率下降了一半