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

1、2014.2.17,计算机系统结构,1,3.3 非线性流水线调度技术(P64),调度问题的提出： 一个任务在通过非线性流水线时对有些功能段要通过多次（非线性定义），所以容易与紧跟而来的后继任务发生设备争用。 调度机构的作用就是合理安排前后任务进入流水线的时间差，既要避免争用，又要使时间差尽可能少，以提高吞吐率。 下面的实例比较简单，学懂以后再自行阅读教材上的实例。,2014.2.17,计算机系统结构,2,算法：共5个步骤 第1步.分析预约表R 描述非线性流水线有2种图形： (a)连接图，仅给出各段之间的静态 空间连接关系； (b)预约表，就是一个任务通过流水 线的时空图，能全面反映该流水线 的

2、动态特性。 要检验2个任务相距k拍是否冲突，可将它们的预约表错位k列重叠（上图）。 第2步.作禁止表F F是1-N之间可冲突拍数的集合，N是预约表的列数减1。具体操作是将同一行中任意2个标记之间的拍数差记下来，再将各行的这类数字汇成一个集合，即为禁止表。本例中 F = 3，4，6 ,3.3.1 单功能非线性流水线结构调度(P65),2014.2.17,计算机系统结构,3,第3步.作原始冲突向量C,为了设计调度机构，需将禁止表转化为原始冲突向量C（Collision）。 C是含N个分量的布尔向量，一般形式为C = (cN.c1)，其中N是预约表的列数减1，也可以是禁止表中的最大元素。第i个分量取

3、值原则为： 本例中 C = (101100),2014.2.17,计算机系统结构,4,使用冲突向量C实现调度的原理图,动态冲突向量 （初值000000） 右移寄存器：0 010110右移出0 “或”运算器： 按位“或” 0接通 1断开 常量发生器： 101100 原始冲突向量 时钟输入 流水线任务排队 1.每个时钟脉冲使流水线中现有任务前进一步，也使右移寄存器移出一位； 2.如果新任务进入，则用它的原始冲突向量与右移寄存器内容相“或”。,2014.2.17,计算机系统结构,5,第4步.作状态转移图（P66图3.15）,这是为了研究无穷多个任务时任务之间可能存在的合法间隔情况。从表达方便考虑，用

4、动态冲突向量作为状态变量。 具体作图方法是： (1)先画“根结点”，它就是第一个任务进入后的右移寄存器状态，数值等于原始冲突向量； (2)分析当前结点的各位，如果ci=0则发出一个旁标i值的箭头，ci=1则不能发出箭头，因为1表示“禁止”。此外还发出一个旁标“N+1*”的箭头，“N+1*”意为“N+1”； (3)每个箭头末端产生一个新的结点，其 状态等于原结点状态右移i位后与原始冲 突向量相“或”； (4)如果新结点状态与已有的结点重复， 则取消它，箭头指向已有的那个结点。,2014.2.17,计算机系统结构,6,第5步.作平均延迟拍数表（P67表3.1）,(1)在状态转移图中寻找全部简单循

5、环填入右表第1栏。所谓简单循环是 指其中各结点仅通过一次的闭合路 径。注意它不一定要通过根结点； (2)计算各简单循环的平均间隔拍数 填入右表第2栏。平均间隔拍数等于 该简单循环中所有数字之和除以数 字个数； (3)取平均延迟拍数最少的方案作为 最优方案。本例为(1,1,7)； (4)调度机构实现：计数器加译码电路。本例可用模9计数器，译码条件是计数值等于0、1、2时允许进入流水线。,2014.2.17,计算机系统结构,7,状态转移图画法,2014.2.17,计算机系统结构,8,右移相“或”运算的示例,（以课件P100转移图右下角结点为例）：,结果成为该结点上面的新结点。,2014.2.17,计算机系统结构