《计算机系统结构》电子教案课.ppt

3.3 3.3 非线性流水线调度技术非线性流水线调度技术(P64)P64)调度问题的提出调度问题的提出：一个任务在通过非线性流水线时对有些功能段要通过多次（非线性定一个任务在通过非线性流水线时对有些功能段要通过多次（非线性定义），所以容易与紧跟而来的后继任务发生设备争用。义），所以容易与紧跟而来的后继任务发生设备争用。调度机构的作用就是合理安排前后任务进入流水线的时间差，既要避调度机构的作用就是合理安排前后任务进入流水线的时间差，既要避免争用，又要使时间差尽可能少，以提高吞吐率。免争用，又要使时间差尽可能少，以提高吞吐率。下面的实例比较简单，学懂以后再自行阅读教材上的实例。下面的实例比较简单，学懂以后再自行阅读教材上的实例。1 算法：共算法：共5个步骤个步骤R描述非线性流水线有描述非线性流水线有2种图形：种图形：(a)a)连接图，仅给出各段之间的静态连接图，仅给出各段之间的静态空间连接关系；空间连接关系；(b)b)预约表，就是一个任务通过流水预约表，就是一个任务通过流水线的时空图，能全面反映该流水线线的时空图，能全面反映该流水线的动态特性的动态特性。要检验要检验2 2个任务相距个任务相距k k拍是否冲突，可将它们的预约表错位拍是否冲突，可将它们的预约表错位k k列重叠（上图）。列重叠（上图）。F F是是1-N之间可冲突拍数的集合，之间可冲突拍数的集合，N是预约表的列数减是预约表的列数减1。具体操作是将同一具体操作是将同一行中任意行中任意2 2个标记之间的拍数差记下来，再将各行的这类数字汇成一个集合，个标记之间的拍数差记下来，再将各行的这类数字汇成一个集合，即为禁止表。本例中即为禁止表。本例中 F=3F=3，4 4，6 6 3.3.1 3.3.1 单功能非线性流水线结构调度单功能非线性流水线结构调度(P65)P65)2原始原始冲突向量冲突向量C为了设计调度机构，需将禁止表转化为原始冲突向量为了设计调度机构，需将禁止表转化为原始冲突向量C C（Collision）。）。C C是含是含N N个分量的布尔向量，一般形式为个分量的布尔向量，一般形式为C=(cC=(cN N.c.c1 1)，其中其中N是预约表是预约表的列数减的列数减1，也可以是，也可以是禁止表中的最大元素。第禁止表中的最大元素。第i i个分量取值原则为：个分量取值原则为：本例中本例中 C=(101100)C=(101100)3使用使用冲突向量冲突向量C实现调度的原理图实现调度的原理图 动态冲突向量动态冲突向量 （初值（初值000000）右移寄存器：右移寄存器：0 010110右移出右移出0“或或”运算器：运算器：按位按位“或或”0接通接通1断开断开常量发生器：常量发生器：101100 原始冲突向量原始冲突向量 时钟输入时钟输入 流水线流水线任务排队任务排队1.每个时钟脉冲使流水线中现有任务前进一步，也使右移寄存器移出一位；每个时钟脉冲使流水线中现有任务前进一步，也使右移寄存器移出一位；2.如果新任务进入，则用它的原始冲突向量与如果新任务进入，则用它的原始冲突向量与右移寄存器内容相右移寄存器内容相“或或”。4（P66图图3.15）这是为了研究无穷多个任务时任务之间可能存在的合法间隔情况。从表这是为了研究无穷多个任务时任务之间可能存在的合法间隔情况。从表达方便考虑，用达方便考虑，用动态冲突向量作为状态变量。动态冲突向量作为状态变量。具体作图方法是：具体作图方法是：(1)(1)先画先画“根结点根结点”，它就是第一个任务进入后的，它就是第一个任务进入后的右移寄存器状态右移寄存器状态，数值等，数值等于于原始冲突向量；原始冲突向量；(2)(2)分析当前结点的分析当前结点的各位各位，如果，如果c ci i=0=0则则发出一个旁标发出一个旁标i i值的箭头，值的箭头，c ci i=1=1则不能则不能发出箭头，因为发出箭头，因为1 1表示表示“禁止禁止”。此外还发出一个旁标。此外还发出一个旁标“N+1*”N+1*”的的箭头，箭头，“N+1*”N+1*”意为意为“N+1”；(3)(3)每个箭头末端产生一个新的结点，其每个箭头末端产生一个新的结点，其状态等于原结点状态右移状态等于原结点状态右移i i位后与位后与原始冲原始冲突向量突向量相相“或或”；(4)(4)如果新结点状态与已有的结点重复，如果新结点状态与已有的结点重复，则取消它，箭头指向已有的那个结点。则取消它，箭头指向已有的那个结点。5（P67表表3.1）(1)(1)在状态转移图中寻找全部简单循在状态转移图中寻找全部简单循环填入右表第环填入右表第1 1栏。所谓简单循环是栏。所谓简单循环是指其中各结点仅通过一次的闭合路指其中各结点仅通过一次的闭合路径。注意它不一定要通过根结点；径。注意它不一定要通过根结点；(2)(2)计算各简单循环的平均间隔拍数计算各简单循环的平均间隔拍数填入右表第填入右表第2 2栏。平均间隔拍数等于栏。平均间隔拍数等于该简单循环中所有数字之和除以数该简单循环中所有数字之和除以数字个数；字个数；(3)(3)取取平均延迟拍数最少的方案作为平均延迟拍数最少的方案作为最优方案。本例为最优方案。本例为(1,1,7)；(4)(4)调度机构实现：计数器加译码电路。本例可用模调度机构实现：计数器加译码电路。本例可用模9计数器，译码条件是计计数器，译码条件是计数值等于数值等于0、1、2时允许进入流水线。时允许进入流水线。6状态转移图画法状态转移图画法7右移相右移相“或或”运算的示例运算的示例（以课件（以课件P100转移图右下角结点为例）：转移图右下角结点为例）：结果成为该结点上面的新结点。结果成为该结点上面的新结点。83.3.2 3.3.2 多功能非线性流水线结构调度多功能非线性流水线结构调度(P67)P67)（不讲）（不讲）9各次作业应交的内容各次作业应交的内容作业作业4 4（第（第4 4次课）次课）10