系统结构chpt5补充.pptx

2024年8月12日计算机系统结构 第五章11 1、非线性流水线的表示、非线性流水线的表示 线性流水线能够用流水线 连接图唯一表示 连接图不能唯一表示非线 性流水线的工作流程，因此，引入流水线预约表2 3 2024年8月12日计算机系统结构 第五章4 一张预约表可能与多个流水一张预约表可能与多个流水线连接图相对应线连接图相对应2024年8月12日计算机系统结构 第五章5 一个流水线连接图对应与多一个流水线连接图对应与多张预约表张预约表62 2、非线性流水线的冲突、非线性流水线的冲突 流水线的启动距离：流水线的启动距离：向流水线连续输入两个任向流水线连续输入两个任务之间的时间间隔务之间的时间间隔 流水线的冲突：流水线的冲突：几个任务争用同一个流水段72024年8月12日计算机系统结构 第五章82024年8月12日计算机系统结构 第五章9103 3、无冲突调度方法、无冲突调度方法 非线性流水线的非线性流水线的禁止向量禁止向量：预约表中每一行任意两个“”之间的距离都计算出来，去掉重复的。例如，例如，前图所示的预约表的禁止向量为（3，4，6）由禁止向量得到由禁止向量得到冲突向量冲突向量：C（CmCm-1C2C1）其中：m是禁止向量中的最大值。如果i在禁止向量中，则Ci1，否则Ci0。例如：例如：对于上面的预约表，C（101100）。11 由冲突向量构造由冲突向量构造状态图状态图：把冲突向量送入一个把冲突向量送入一个m位逻辑右移移位器；如位逻辑右移移位器；如果移位器移出果移位器移出0 0，用移位器中的值与初始冲突向量作，用移位器中的值与初始冲突向量作“按位或按位或”运算，得到一个新的冲突向量；否则不运算，得到一个新的冲突向量；否则不作任何处理；如此重复作任何处理；如此重复m次。次。对于中间形成的每一个新的冲突向量，也要按对于中间形成的每一个新的冲突向量，也要按照这一方法进行处理。照这一方法进行处理。在初始冲突向量和所有的新形成的冲突向量之在初始冲突向量和所有的新形成的冲突向量之间用带箭头的线连接，当新形成的冲突向量出现重间用带箭头的线连接，当新形成的冲突向量出现重复时可以合并到一起复时可以合并到一起。2024年8月12日计算机系统结构 第五章12例例5.35.3：一条有：一条有4 4个功能段的非线性流水线，每个功能段的个功能段的非线性流水线，每个功能段的延迟时间都相等，它的预约表如下：延迟时间都相等，它的预约表如下：(1)(1)写出流水线的禁止向量和初始冲突向量。写出流水线的禁止向量和初始冲突向量。(2)(2)画出调度流水线的状态图。画出调度流水线的状态图。(3)(3)求流水线的最小启动循环和最小平均启动距离。求流水线的最小启动循环和最小平均启动距离。(4)(4)求平均启动距离最小的恒定循环。求平均启动距离最小的恒定循环。2024年8月12日计算机系统结构 第五章13解：禁止向量为：（解：禁止向量为：（2 2，4 4，6 6）初始冲突向量：初始冲突向量：101010101010 初始冲突向量逻辑右移初始冲突向量逻辑右移2 2、4 4、6 6位时，不作任位时，不作任何处理何处理 逻辑右移逻辑右移1 1、3 3、5 5和大于等于和大于等于7 7时，要进行处理时，要进行处理。14 初始冲突向量右移初始冲突向量右移1 1位之后：位之后：010101101010010101101010111111111111，初始冲突向量右移初始冲突向量右移3 3位之后：位之后：000101101010000101101010101111101111，初始冲突向量右移初始冲突向量右移5 5位之后：位之后：000001101010000001101010101011101011，初始冲突向量右移初始冲突向量右移7 7位或大于位或大于7 7位后：还原到它本身。位后：还原到它本身。15 中间冲突向量中间冲突向量101111101111右移右移5 5位之后：位之后：000001101010000001101010101011101011，中间冲突向量中间冲突向量101011101011右移右移3 3位之后：位之后：000101101010000101101010101111101111，中间冲突向量中间冲突向量101011101011右移右移5 5位之后：位之后：000001101010000001101010101011101011。2024年8月12日计算机系统结构 第五章16 简单循环：简单循环：状态图中各种冲突向量只经过一次的启动循环。简单循环的个数一般是有限的。由简单循环计算平均启动距离。最小的启动循环为（1，7）和（3，5）。平均启动距离为平均启动距离为 4 4。启动距离最小的恒定循环是（。启动距离最小的恒定循环是（5 5）。）。2024年8月12日计算机系统结构 第五章172024年8月12日计算机系统结构 第五章18