7计算机系统结构(第七讲).pptVIP

计算机系统结构(第七讲) 厦门大学计算机科学系 陆达 2004年11月28日 第五章 标量处理机 5.2 流水线处理机 5.2.3 线性流水线的性能分析 5.2.3.5 流水线性能分析举例 单功能、线性流水线，输入任务连续 单功能、线性流水线，输入任务不连续 多功能、线性流水线，输入任务不连续 非线性流水线 例5.1：单功能、线性流水线，输入任务不连续 Z=A+B+C+D+E+F+G+H Z=[(A+B)+(C+D)]+[(E+F)+(G+H)] 图5.42：用一条4段浮点加法器流水线求8个数之和的流水线时空图 吞吐率：TP=n/Tk=7/(15*△t)=0.47*(1/△t) 加速比：S=T0/Tk=(4*7*△t)/(15*△t)=1.87 效率：E=T0/(k*Tk)=(4*7*△t)/(4*15*△t)=0.47 例5.2：多功能、线性流水线，输入任务不连续 Z=AB+CD+EF+GH Z=[AB+CD]+[EF+GH] 图5.43：用TI-ASC多功能静态流水线求两个向量点积的流水线时空图 吞吐率：TP=n/Tk=7/(20*△t)=0.35*(1/△t) 加速比：S=T0/Tk=(4*4*△t+ 3*6*△t)/(20*△t)=1.70 效率：E=T0/(k*Tk)=(4*4*△t+ 3*6*△t)/(8*20*△t)=0.21 该流水线的效率很低，原因主要有四个：p294 5.2.4 非线性流水线的调度技术 功能部件冲突，或流水线冲突 采用延迟输入新任务的方法 非线性流水线的调度问题 非线性流水线调度的任务：要找出一个最小的循环周期，按照这个周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高 5.2.4.1 非线性流水线的表示 图5.44(a)：非线性流水线的连接图 图5.44(b)：非线性流水线的预约表 预约表的横坐标（列数）：流水线工作的时钟周期数，或流水线的功能求值时间，或流水线的装入时间 预约表的纵坐标（行数）：流水线的功能段 一张非线性流水线的预约表可能与多个非线性流水线连接图相对应，如图5.45 一个非线性流水线的连接图也可能对应有多张预约表，如图5.46 5.2.4.2 非线性流水线的冲突 启动距离（initiation interval），或等待时间（latency） 非线性流水线中的冲突（collision） 图5.47：启动距离为3的流水线冲突情况 图5.48：启动距离为2的流水线冲突情况 禁止启动距离：如启动距离3、启动距离2 图5.49：启动距离为5的流水线预约表（任何一个功能段在任何一个时钟周期都不发生冲突） 非线性流水线的启动循环：如启动循环(1,7) 图5.50：启动距离为(1,7)循环时的流水线预约表 恒定循环：如启动循环(5) 非线性流水线的禁止向量 如何由预约表得到禁止向量？P297-298 平均启动距离：如启动循环(1,7)的平均启动距离为4；启动循环(5)的平均启动距离为5 5.2.4.3 无冲突调度方法 目的是要找出具有最小平均启动距离的启动循环 E.S.Davidson及其学生1971年提出 冲突向量：可由一张预约表的禁止向量得到，如禁止向量为(3,4,6)，则冲突向量为C=(CmCm-1···C2C1)=(101100) 状态图：由冲突向量构造而成 m位逻辑右移移位器：当移出的位为0时，用移位器中的值与初始冲突向量作“按位或”运算，得到一个新的冲突向量；若移出的位为1，不作任何处理 图5.51：非线性流水线的状态图 与一张预约表相对应，只有唯一的一个状态图 从预约表可以画出状态图，但从状态图不能得到预约表 在状态图中可以找到很多不发生功能冲突的启动循环 简单循环：表5.1 (各冲突相量只经过一次的启动循环） 最小启动循环：如启动循环(1,1,7) 图5.52：最小启动循环(1,1,7)的流水性预约表 恒定循环：如启动循环(5) 5.2.4.4 优化调度方法 L.E.Shar在1971年提出了流水线最小平均启动距离的限制范围，对于一条静态可重构的流水线，通过预约表可以得到其最小平均启动距离的范围。共有三个方面，见P301 采用预留算法来调度非线性流水线，可以达到最优调度。具体方法有三条，见P301 图5.53：采用预留算法调度的预约表、连接图（有非计算延迟的非线性流水线） 图5.54：与图5.53相对应的流水线状态图（有非计算延迟的流水线状态图） 图5.55：按照最小启动循环(3)工作的流水线预约表 单功能非线性流水线 静态多