高级时间体系结构ppt课件——第3章.ppt

《高级时间体系结构ppt课件——第3章.ppt》由会员分享，可在线阅读，更多相关《高级时间体系结构ppt课件——第3章.ppt（206页珍藏版）》请在三一办公上搜索。

1、第3章 流水线技术张晨曦 刘依www.GotoS,3.1重叠执行和先行控制3.2流水线的基本概念3.3流水线的性能指标3.4流水线的相关与冲突 3.5流水线的实现3.6向量处理机,将一条指令的执行过程分为三个阶段,3.1 重叠执行和先行控制,3.1.1 重叠执行,一条指令的执行过程,3.1 重叠执行和先行控制,取指令按照指令计数器PC的内容访问主存，取出一条指令 送到指令寄存器。指令分析对指令的操作码进行译码，按照给定的寻址方式和 地址字段形成操作数的地址，并用这个地址读取操 作数。指令执行按照操作码的要求，完成指令规定的功能。 在指令的执行过程中还要更新PC值，为读取下一 条指令做好准备。,

2、3.1 重叠执行和先行控制,三种执行方式顺序执行方式一次重叠执行方式二次重叠执行方式,3.1 重叠执行和先行控制,执行n条指令所花的时间,顺序执行方式指令的执行过程,3.1 重叠执行和先行控制,如果取指令、指令分析和指令执行的时间相等， 都是t，则 T=3nt 优点控制简单，节省设备。主要缺点 处理机执行指令的速度慢 功能部件的利用率很低,3.1 重叠执行和先行控制,一次重叠执行方式 指令的执行过程,执行第k条指令与取第k+l条指令同时进行。（一种最简单的重叠方式）,3.1 重叠执行和先行控制,如果执行一条指令的3个阶段的时间相等，都是 t，则执行n条指令所花的时间为 T=(1+2n)t 优点

3、程序的执行时间减少了近1/3。功能部件的利用率明显提高。缺点需要增加一些硬件，控制过程变复杂了。,3.1 重叠执行和先行控制,二次重叠执行方式 指令的执行过程,取第k+l条指令提前到与分析第k条指令同时进行，分析第k+l条指令与执行第k条指令同时进行。,3.1 重叠执行和先行控制,如果执行一条指令的3个阶段的时间相等，都是 t，则执行n条指令所花的时间为 T= (2+n)t 优点与顺序执行方式相比，执行时间缩短了近2/3。部件的利用率有了进一步的提高。缺点需要增加更多的硬件。需要设置独立的取指令部件、指令分析部件和指令执行部件。,3.1 重叠执行和先行控制,访问主存的冲突问题 4种解决方法设置

4、两个独立编址的存储器： 指令存储器（存放指令）、数据存储器（存放数据）指令和数据仍然混合存放在同一个主存中，但设置 两个Cache： 指令Cache、数据Cache 程序空间和数据空间相互独立的系统结构被称为哈佛结构。 指令和数据仍然混合存放在同一个主存中，但主存采用 多体交叉结构。 （有一定的局限性）,3.1 重叠执行和先行控制,在主存和指令分析部件之间增设指令缓冲站 （又被称为先行指令缓冲站 ）主存不是满负荷工作的，插空从主存中预先把后面将要执行的指令取出来，存放到指令缓冲站中。在“取指令”阶段从指令缓冲站读取指令（如果指令缓冲站不为空），而不用去访问主存。,3.1 重叠执行和先行控制,先

5、行指令缓冲站先行指令缓冲站的组成,3.1 重叠执行和先行控制,指令缓冲存储区和相应的控制逻辑按队列方式工作。只要指令缓冲站不满，它就自动地向主存控制器发 取指令请求，不断地预取指令。指令分析部件每分析完一条指令，就自动向指令缓冲站发出取下 一条指令的请求。指令取出之后就把指令缓冲站中 的该指令作废。指令缓冲站中存放的指令的条数是动态变化的。两个程序计数器,3.1 重叠执行和先行控制,先行程序计数器PC1：用于从主存预取指令；现行程序计数器PC：用来记录指令分析部件当前正在 分析的指令的地址。先行控制方式中的一次重叠执行 若取指令阶段的时间很短，可以把这个操作合并 到分析指令中。上述的二次重叠就

6、演变成了一次重叠把一条指令的执行过程分为分析和执行两个阶段；让前一条指令的执行与后一条指令的分析重叠进行。,3.1 重叠执行和先行控制,如果指令分析和指令执行所需要的时间都是t，则采用这种方式连续执行n条指令所需要的时间为： T= (1+n)t控制方式比较简单，得到了广泛应用。,3.1 重叠执行和先行控制,当指令分析和指令执行所需要的时间不相等时， 其执行过程为：,指令分析部件和指令执行部件存在相互等待的时候，会出现部件空闲的情况。,3.1 重叠执行和先行控制,先行控制技术：缓冲技术和预处理技术的结合缓冲技术：在工作速度不固定的两个功能部件之间设置缓冲器，用以平滑它们的工作。预处理技术：预取指

7、令、对指令进行加工以及预取操作数等。采用先行控制方式的处理机结构,3.1.2 先行控制,3.1 重叠执行和先行控制,3.1 重叠执行和先行控制,设置了4个缓冲站（平滑主存、指令分析部件、运算器三者之间的工作）先行指令缓冲站（前面已讲述）先行操作站先行读数站后行写数站 共同特点：按先进先出的方式工作，而且都是由一组若 干个能快速访问的存储单元和相关的控制逻 辑组成。,3.1 重叠执行和先行控制,先行操作站在指令分析部件和运算器之间提供缓冲 先行：因为其中的指令对于运算器正在执行的 指令来说是后续的，但却被先行取出并预处理。指令分析部件 从先行指令缓冲站取指令，并进行预处理，加工成 统一格式的RR

8、型操作命令，然后送入先行操作站。 对于不同指令做不同的处理。,3.1 重叠执行和先行控制,寄存器-寄存器型（RR型）指令：可以不作任何处理，直 接送入。操作数来自主存的运算指令：计算出操作数的有效地 址，并将该地址送入先行读数站的某个存储单元（设其地址为i），同时用i替换原来指令中的操作数地址码字段。向主存“写数”的指令：把形成的有效地址送入后行写 数站的某个存储单元（设其地址为j），同时用j替换原来指令中的目标地址码字段。立即数型指令：把指令中的立即数送入读数站（设为第l 个存储单元），同样也用l替换原来指令中的立即数字 段。,3.1 重叠执行和先行控制,运算器从先行操作站取出RR型操作命令

9、并执行。每执行完一条，将运算结果写入通用寄存器组或者 后行写数站。继续执行先行操作站中的后续命令。 先行读数站作用：接收指令分析部件送来的访问主存的有效地 址，按顺序依次从主存读取操作数，提供给运算器 使用。先行：因为对于正在执行的指令来说，先行读数站 中的操作数是先行取出的。,3.1 重叠执行和先行控制,每个存储单元由3部分组成： 先行地址字段、先行操作数字段、标志字段每当从指令分析部件接收有效地址时，将之放入先行地址字段，并将地址有效标志置位。等到该单元成为队列的第一项时，先行读数站会用该地址向主存发出读请求，把取来的操作数放入该单元的先行操作数字段，同时将数据有效标志置位。当以后运算器需

10、要该操作数时，就可以直接从先行读数站取得，而不必去访问主存。,3.1 重叠执行和先行控制,后行写数站作用：接收从运算器送来的结果数据，并负责将之 写入主存。后行：因为站在运算器的角度来看，结果数据不是在相应的指令运算完后立即写入主存，而是由后行写数站滞后写入的。每一个存储单元由3部分组成： 后行地址字段、后行数据字段、标志字段 每当从运算器接收数据时，将之放入后行数据字段，并把相应的数据有效标志置位。后行写数站的控制逻辑自动向主存发出写数请求。当写数据操作完成后，也要置位有关标志。,3.1 重叠执行和先行控制,采用先行控制后的一次重叠执行,指令分析部件在不间断地分析指令，而指令执行部件则在不间

11、断地执行指令，它们都始终处于忙碌状态。,3.1 重叠执行和先行控制,理想情况下，指令执行部件应该是一直忙碌的。处理机连续执行n条指令所需要的时间为,工业生产流水线 下面通过一个例子来说明流水线的好处:两种方案两种方案的工作过程对比流水线生产过程的抽象描述这种流水工作方式的主要特点,3.2 流水线的基本概念,3.2.1 什么是流水线,3.2 流水线的基本概念,流水线技术把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。把多个处理过程在时间上错开，依次通过各功能段，这样，每个子过程就可以与其他的子过程并行进行。流水线中的每个子过程及其功能部件称为流水线的级或段，段与段相互连接形

12、成流水线。流水线的段数称为流水线的深度。,3.2 流水线的基本概念,指令流水线把指令的解释过程分解为分析和执行两个子过程，并让这两个子过程分别用独立的分析部件和执行部件来实现。理想情况：速度提高一倍4段指令流水线,3.2 流水线的基本概念,浮点加法流水线把流水线技术应用于运算的执行过程，就形成了 运算操作流水线，也称为部件级流水线。把浮点加法的全过程分解为求阶差、对阶、尾数 相加、规格化4个子过程。 理想情况：速度提高3倍,时空图时空图从时间和空间两个方面描述了流水线的工作过程。时空图中，横坐标代表时间，纵坐标代表流水线的各个段。 4段指令流水线的时空图,3.2 流水线的基本概念,流水技术的特

13、点流水线把一个处理过程分解为若干个子过程（段），每个子过程由一个专门的功能部件来实现。流水线中各段的时间应尽可能相等，否则将引起流水线堵塞、断流。 时间长的段将成为流水线的瓶颈。流水线每一个功能部件的后面都要有一个缓冲寄存器（锁存器），称为流水寄存器。作用：在相邻的两段之间传送数据，以保证提供后 面要用到的数据，并把各段的处理工作相互隔离。,3.2 流水线的基本概念,流水技术适合于大量重复的时序过程，只有在输入端不断地提供任务，才能充分发挥流水线的效率。 流水线需要有通过时间和排空时间。通过时间：第一个任务从进入流水线到流出结果 所需的时间。排空时间：最后一个任务从进入流水线到流出结 果所需的

14、时间。,3.2 流水线的基本概念,从不同的角度和观点，把流水线分成多种不同的种类。单功能流水线与多功能流水线 （按照流水线所完成的功能来分类）单功能流水线：只能完成一种固定功能的流水线。多功能流水线：流水线的各段可以进行不同的 连接，以实现不同的功能。例： ASC的多功能流水线,3.2.2 流水线的分类,3.2 流水线的基本概念,静态流水线与动态流水线（按照同一时间内各段之间的连接方式对多功能流水线做进一步的分类）静态流水线：在同一时间内，多功能流水线中的 各段只能按同一种功能的连接方式工作。对于静态流水线来说，只有当输入的是一串相同的 运算任务时，流水的效率才能得到充分的发挥。例如：ASC的

15、8段流水线,3.2 流水线的基本概念,动态流水线：在同一时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。 动画优点 灵活，能够提高流水线各段的使用率，从而 提高处理速度。缺点 控制复杂。静、动态流水线时空图的对比,3.2 流水线的基本概念,部件级、处理机级及处理机间流水线（按照流水的级别来进行分类）部件级流水线（运算操作流水线）：把处理机的算术逻辑运算部件分段，使得各种类型的运算操作能够按流水方式进行。处理机级流水线（指令流水线）：把指令的解释执行过程按照流水方式处理。把一条指令的执行过程分解为若干个子过程，每个子过程在独立的功能部件中执行。 例如：前面的4段指令流水线,

16、3.2 流水线的基本概念,处理机间流水线（宏流水线）：它是由两个或者 两个以上的处理机串行连接起来，对同一数据流 进行处理，每个处理机完成整个任务中的一部 分。 动画解析,3.2 流水线的基本概念,线性流水线与非线性流水线（按照流水线中是否有反馈回路来进行分类）线性流水线：流水线的各段串行连接，没有反馈回路。数据通过流水线中的各段时，每一个段最多只流过一次。非线性流水线：流水线中除了有串行的连接外，还有反馈回路。 （举例）非线性流水线的调度问题确定什么时候向流水线引进新的任务，才能使该任务不会与先前进入流水线的任务发生冲突争用流水段。,3.2 流水线的基本概念,3.2 流水线的基本概念,顺序流

17、水线与乱序流水线（根据任务流入和流出的顺序是否相同来进行分类）顺序流水线：流水线输出端任务流出的顺序与输 入端任务流入的顺序完全相同。每一个任务在流 水线的各段中是一个跟着一个顺序流动的。乱序流水线：流水线输出端任务流出的顺序与输 入端任务流入的顺序可以不同，允许后进入流水 线的任务先完成（从输出端流出）。 也称为无序流水线、错序流水线、异步流水线,3.2 流水线的基本概念,标量处理机与向量流水处理机 把指令执行部件中采用了流水线的处理机称为流 水线处理机。标量处理机：处理机不具有向量数据表示和向量 指令，仅对标量数据进行流水处理。向量流水处理机：具有向量数据表示和向量指令 的处理机。 向量数

18、据表示和流水技术的结合。,吞吐率：在单位时间内流水线所完成的任务数量或输 出结果的数量。,3.3 流水线的性能指标,3.3.1 吞吐率,n：任务数Tk：处理完成n个任务所用的时间,3.3 流水线的性能指标,各段时间均相等的流水线各段时间均相等的流水线时空图,3.3 流水线的性能指标,流水线完成n个连续任务所需要的总时间为（假设一条k段线性流水线）Tkkt(n-1)t(kn-1)t 流水线的实际吞吐率,最大吞吐率,3.3 流水线的性能指标,最大吞吐率与实际吞吐率的关系,流水线的实际吞吐率小于最大吞吐率，它除了与每个段的时间有关外，还与流水线的段数k以及输入到流水线中的任务数n等有关。只有当nk时

19、，才有TPTPmax。,3.3 流水线的性能指标,各段时间不完全相等的流水线 各段时间不等的流水线及其时空图 举例（时空图）一条4段的流水线S1，S3，S4各段的时间：tS2的时间：3t （瓶颈段）流水线中这种时间最长的段称为流水线的瓶颈段。,3.3 流水线的性能指标,3.3 流水线的性能指标,各段时间不等的流水线的实际吞吐率：（ ti为第i段的时间，共有k个段 ）,流水线的最大吞吐率为,3.3 流水线的性能指标,例如：一条4段的流水线中，S1，S2，S4各段的时间都是t，唯有S3的时间是3t。,最大吞吐率为,3.3 流水线的性能指标,解决流水线瓶颈问题的常用方法 举例细分瓶颈段 例如：对前面

20、的4段流水线把瓶颈段S3细分为3个子流水线段：S3a，S3b，S3c,改进后的流水线的吞吐率 ：,3.3 流水线的性能指标,重复设置瓶颈段举例：时空图缺点：控制逻辑比较复杂，所需的硬件增加了。例如：对前面的4段流水线 重复设置瓶颈段S3：S3a，S3b，S3c,3.3 流水线的性能指标,重复设置瓶颈段后的时空图,3.3 流水线的性能指标,加速比：完成同样一批任务，不使用流水线所用的时间 与使用流水线所用的时间之比。假设：不使用流水线（即顺序执行）所用的间为Ts，使用流水线后所用的时间为Tk，则该流水线的加速比为,3.3.2 加速比,3.3 流水线的性能指标,流水线各段时间相等（都是t）一条k段

21、流水线完成n个连续任务 所需要的时间为 Tk = (kn-1)t顺序执行n个任务 所需要的时间： Ts= nkt （解释）流水线的实际加速比为,3.3 流水线的性能指标,最大加速比,当nk时，S k思考：流水线的段数愈多愈好？,3.3 流水线的性能指标,流水线的各段时间不完全相等时一条k段流水线完成n个连续任务的实际加速比为,3.3 流水线的性能指标,效率：流水线中的设备实际使用时间与整个运行时间 的比值，即流水线设备的利用率。 由于流水线有通过时间和排空时间，所以在连续完成n个任务的时间内，各段并不是满负荷地工作。各段时间相等各段的效率ei相同 (解释),3.3.3 效率,3.3 流水线的性

22、能指标,整条流水线的效率为,可以写成,最高效率为,当nk时，E1。,3.3 流水线的性能指标,当流水线各段时间相等时，流水线的效率与吞吐率 成正比。 E=TPt 流水线的效率是流水线的实际加速比S与它的最大加速 比k的比值。,当E=1时，S=k，实际加速比达到最大。,3.3 流水线的性能指标,从时空图上看，效率就是n个任务占用的时空面积和 k个段总的时空面积之比。,当各段时间不相等时,3.3 流水线的性能指标,例3.1 设在下图所示的静态流水线上计算： 流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中，试计算其吞吐率、加速比和效率。,3.3.4 流水线的性能分析举例,(每段的时间都为t

23、),3.3 流水线的性能指标,解：（1）选择适合于流水线工作的算法先计算A1+B1、A2+B2、A3+B3和A4+B4；再计算(A1+B1)(A2+B2)和(A3+B3)(A4+B4)；然后求总的乘积结果。（2）画出时空图,3.3 流水线的性能指标,3.3 流水线的性能指标,在18个t时间中，给出了7个结果。吞吐率为：,不用流水线，由于一次求和需6t，一次求积需4t， 则产生上述7个结果共需（46+34）t = 36t 加速比为,（3）计算性能,3.3 流水线的性能指标,流水线的效率,可以看出，在求解此问题时，该流水线的效率不高。 (原因),3.3 流水线的性能指标,主要原因多功能流水线在做某

24、一种运算时，总有一些段是空闲的。静态流水线在进行功能切换时，要等前一种运算全部流出流水线后才能进行后面的运算。运算之间存在关联，后面有些运算要用到前面运算的结果。流水线的工作过程有建立与排空部分。,3.3 流水线的性能指标,例3.2 有一条动态多功能流水线由5段组成，加法用1、3、4、5段，乘法用1、2、5段，第2段的时间为2t，其余各段时间均为t，而且流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中。若在该流水线上计算: 试计算其吞吐率、加速比和效率。,3.3 流水线的性能指标,解: (1) 选择适合于流水线工作的算法应先计算A1B1、A2B2、A3B3和A4B4；再计算(A1B1)

25、(A2B2) (A3B3)(A4B4)；然后求总的累加结果。(2) 画出时空图(3) 计算性能,3.3 流水线的性能指标,3.3 流水线的性能指标,下面我们再看一个例子： 例 在静态流水线上计算: 求：吞吐率，加速比，效率。解： (1) 确定适合于流水处理的计算过程 (2) 画时空图 (3) 性能计算 吞吐率 TP7(20t) 加速比 S(34t)(20t)1.7 效率 E(4436)(820)0.21,3.3 流水线的性能指标,3.3 流水线的性能指标,可以看出，在求解此问题时，该流水线的效率不高。 动态流水线的时空图 举例举例 : 这样行不行？ 正确答案,3.3 流水线的性能指标,瓶颈问题

26、理想情况下，流水线在工作时，其中的任务是同步地每一个时钟周期往前流动一段。当流水线各段不均匀时，机器的时钟周期取决于瓶颈段的延迟时间。在设计流水线时，要尽可能使各段时间相等。流水线的额外开销流水寄存器延迟时钟偏移开销,3.3.5 流水线设计中的若干问题,3.3 流水线的性能指标,流水寄存器需要建立时间和传输延迟建立时间：在触发写操作的时钟信号到达之前，寄 存器输入必须保持稳定的时间。传输延迟：时钟信号到达后到寄存器输出可用的时 间。时钟偏移开销流水线中，时钟到达各流水寄存器的最大差值时间。（时钟到达各流水寄存器的时间不是完全相同）,3.3 流水线的性能指标,几个问题流水线并不能减少（而且一般是

27、增加）单条指令的执行时间，但却能提高吞吐率。增加流水线的深度（段数）可以提高流水线的性能。流水线的深度受限于流水线的额外开销。当时钟周期小到与额外开销相同时，流水已没意义。因为这时在每一个时钟周期中已没有时间来做有用的工作。冲突问题 流水线设计中要解决的重要问题之一。,介绍一个经典的5段RISC流水线 首先讨论在非流水情况下是如何实现的一条指令的执行过程分为以下5个周期：取指令周期（IF）IR MemPC 。PC值加4。（假设每条指令占4个字节）,3.4 流水线的相关与冲突,3.4.1 一个经典的5段流水线,3.4 流水线的相关与冲突,指令译码/读寄存器周期（ID）译码。用IR中的寄存器编号去

28、访问通用寄存器组，读出所需的操作数。执行/有效地址计算周期（EX） 不同指令所进行的操作不同：存储器访问指令：ALU把所指定的寄存器的内容与偏 移量相加，形成用于访存的有效地址。寄存器寄存器ALU指令：ALU按照操作码指定的操 作对从通用寄存器组中读取的数据进行运算。,3.4 流水线的相关与冲突,寄存器立即数ALU指令：ALU按照操作码指定的操 作对从通用寄存器组中读取的第一操作数和立即数 进行运算。分支指令：ALU把偏移量与PC值相加，形成转移目标 的地址。同时，对在前一个周期读出的操作数进行 判断，确定分支是否成功。存储器访问分支完成周期（MEM） 该周期处理的指令只有load、store

29、和分支指令。 其他类型的指令在此周期不做任何操作。,3.4 流水线的相关与冲突,load和store指令load指令：用上一个周期计算出的有效地址从存储器中 读出相应的数据。store指令：把指定的数据写入这个有效地址所指出的存 储器单元。分支指令 分支“成功”，就把转移目标地址送入PC。 分支指令执行完成。,3.4 流水线的相关与冲突,写回周期（WB） ALU运算指令和load指令在这个周期把结果数据写入通用寄存器组。 ALU运算指令：结果数据来自ALU。 load指令：结果数据来自存储器系统。 在这个实现方案中：分支指令需要4个时钟周期（如果把分支指令的执行 提前到ID周期，则只需要2个周

30、期）。store指令需要4个周期。其他指令需要5个周期才能完成。,将上述实现方案修改为流水线实现一个经典的5段流水线 每一个周期作为一个流水段。在各段之间加上锁存器（流水寄存器）。,3.4 流水线的相关与冲突,5段流水线的两种描述方式第一种描述（类似于时空图）,第二种描述（按时间错开的数据通路序列）,采用流水线方式实现时，应解决以下几个问题：要保证不会在同一时钟周期要求同一个功能段做 两件不同的工作。例如，不能要求ALU同时做有效地址计算和算术运算。避免IF段的访存（取指令）与MEM段的访存（读/写数据）发生冲突。可以采用分离的指令存储器和数据存储器；一般采用分离的指令Cache和数据Cach

31、e。ID段和WB段都要访问同一寄存器文件。 ID段：读WB段：写,3.4 流水线的相关与冲突,3.4 流水线的相关与冲突,如何解决对同一寄存器的访问冲突？ 把写操作安排在时钟周期的前半拍完成，把读操作安排在后半拍完成。考虑PC的问题流水线为了能够每个时钟周期启动一条新的指令，就必须在每个时钟周期进行PC值的加4操作，并保留新的PC值。这种操作必须在IF段完成，以便为取下一条指令做好准备。 （需设置一个专门的加法器）但分支指令也可能改变PC的值，而且是在MEM段进行，这会导致冲突。请考虑一下，如何处理分支指令？,3.4 流水线的相关与冲突,相关：两条指令之间存在某种依赖关系。 如果两条指令相关，

32、则它们就有可能不能在流水线中重叠执行或者只能部分重叠执行。相关有3种类型数据相关（也称真数据相关）名相关控制相关,3.4.2 相关与流水线冲突,3.4.2.1 相关,3.4 流水线的相关与冲突,数据相关 对于两条指令i（在前，下同）和j（在后，下同），如果下述条件之一成立，则称指令j与指令i数据相关。 指令j使用指令i产生的结果；指令j与指令k数据相关，而指令k又与指令i数据相关。数据相关具有传递性。 数据相关反映了数据的流动关系，即如何从其产 生者流动到其消费者。,3.4 流水线的相关与冲突,例如：下面这一段代码存在数据相关。,Loop： L.D F0，0（R1）/ F0为数组元素 ADD.

33、D F4，F0，F2/ 加上F2中的值 S.D F4，0（R1）/ 保存结果 DADDIU R1，R1，8/ 数组指针递减8个字节 BNE R1，R2，Loop/ 如果R1R2，则分支,3.4 流水线的相关与冲突,当数据的流动是经过寄存器时，相关的检测比较 直观和容易。当数据的流动是经过存储器时，检测比较复杂。相同形式的地址其有效地址未必相同。形式不同的地址其有效地址却可能相同。名相关名：指令所访问的寄存器或存储器单元的名称。如果两条指令使用相同的名，但是它们之间并没有数据流动，则称这两条指令存在名相关。,3.4 流水线的相关与冲突,指令j与指令i之间的名相关有两种：反相关：如果指令j写的名与

34、指令i读的名相同，则 称指令i和j发生了反相关。 指令j写的名指令i读的名输出相关：如果指令j和指令i写相同的名，则称指 令i和j发生了输出相关。 指令j写的名指令i写的名,3.4 流水线的相关与冲突,名相关的两条指令之间并没有数据的传送。如果一条指令中的名改变了，并不影响另外一条指令的执行。换名技术换名技术：通过改变指令中操作数的名来消除名相关。对于寄存器操作数进行换名称为寄存器换名。既可以用编译器静态实现，也可以用硬件动态完成。,3.4 流水线的相关与冲突,例如：考虑下述代码： DIV.DF2，F6，F4 ADD.DF6，F0，F12 SUB.DF8，F6，F14 DIV.D和ADD.D存

35、在反相关。 进行寄存器换名（F6换成S）后，变成： DIV.DF2，F6，F4 ADD.DS，F0，F12 SUB.DF8，S，F14,3.4 流水线的相关与冲突,控制相关 控制相关是指由分支指令引起的相关。为了保证程序应有的执行顺序，必须严格按控制相 关确定的顺序执行。典型的程序结构是“if-then”结构。请看一个示例：,if p1 S1； ；S；if p2 S2； ；,3.4 流水线的相关与冲突,控制相关带来了以下两个限制：与一条分支指令控制相关的指令不能被移到该分支 之前，否则这些指令就不受该分支控制了。 对于上述的例子，then 部分中的指令不能移到if语句之前。 如果一条指令与某分

36、支指令不存在控制相关，就不 能把该指令移到该分支之后。对于上述的例子，不能把S移到if语句的then部分中。,3.4 流水线的相关与冲突,流水线冲突是指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。 流水线冲突有3种类型：结构冲突：因硬件资源满足不了指令重叠执行的要 求而发生的冲突。数据冲突：当指令在流水线中重叠执行时，因需要 用到前面指令的执行结果而发生的冲突。控制冲突：流水线遇到分支指令和其他会改变PC值 的指令所引起的冲突。,3.4.2.2 流水线冲突,3.4 流水线的相关与冲突,带来的几个问题：导致错误的执行结果。流水线可能会出现停顿，从而降低

37、流水线的效率 和实际的加速比。我们约定 当一条指令被暂停时，在该暂停指令之后流出的所有指令都要被暂停，而在该暂停指令之前流出的指令则继续进行（否则就永远无法消除冲突）。,3.4 流水线的相关与冲突,结构冲突在流水线处理机中，为了能够使各种组合的指令 都能顺利地重叠执行，需要对功能部件进行流水 或重复设置资源。如果某种指令组合因为资源冲突而不能正常执 行，则称该处理机有结构冲突。常见的导致结构相关的原因：功能部件不是完全流水资源份数不够,3.4 流水线的相关与冲突,结构冲突举例：访存冲突 有些流水线处理机只有一个存储器，将数据和指令放在一起，访存指令会导致访存冲突。解决办法：插入暂停周期 （“流

38、水线气泡”或“气泡”） 引入暂停后的时空图解决方法： 设置相互独立的指令存储器和数据存储器 或设置相互独立的指令Cache和数据Cache。,3.4 流水线的相关与冲突,由于访问同一个存储器而引起的结构冲突,3.4 流水线的相关与冲突,为消除结构冲突而插入的流水线气泡,3.4 流水线的相关与冲突,引入暂停后的时空图,3.4 流水线的相关与冲突,有时流水线设计者允许结构冲突的存在主要原因：减少硬件成本如果把流水线中的所有功能单元完全流水化，或者 重复设置足够份数，那么所花费的成本将相当高。数据冲突 当相关的指令靠得足够近时，它们在流水线中的重叠执行或者重新排序会改变指令读/写操作数的顺序，使之不

39、同于它们非流水实现时的顺序，则发生了数据冲突。,3.4 流水线的相关与冲突,举例： DADD R1，R2，R3 DSUB R4，R1，R5 XOR R6，R1，R7 AND R8，R1，R9 OR R10，R1，R11,3.4 流水线的相关与冲突,流水线的数据冲突举例,3.4 流水线的相关与冲突,根据指令读访问和写访问的顺序，可以将数据冲 突分为3种类型。 考虑两条指令i和j ，且i在j之前进入流水线，可能发生的数据冲突有：写后读冲突（RAW） 在 i 写入之前，j 先去读。 j 读出的内容是错误的。 这是最常见的一种数据冲突，它对应于真数据相关。,3.4 流水线的相关与冲突,写后写冲突（WA

40、W） 在 i 写入之前，j 先写。 最后写入的结果是 i 的。错误！ 这种冲突对应于输出相关。 写后写冲突仅发生在这样的流水线中：流水线中不只一个段可以进行写操作。当先前某条指令停顿时，允许其后续指令继续前进。 前面介绍的5段流水线不会发生写后写冲突。（只在WB段写寄存器）,3.4 流水线的相关与冲突,读后写冲突（WAR） 在 i 读之前，j 先写。 i 读出的内容是错误的！ 由反相关引起。 这种冲突仅发生在这样的情况下：有些指令的写结果操作提前了，而且有些指令 的读操作滞后了。指令被重新排序了。 读后写冲突在前述5段流水线中不会发生。（读操作（在ID段）在写结果操作（在WB段）之前）,3.4

41、 流水线的相关与冲突,通过定向技术减少数据冲突引起的停顿 （定向技术也称为旁路或短路）关键思想：在某条指令产生计算结果之前，其他指 令并不真正立即需要该计算结果，如果能够将该计 算结果从其产生的地方直接送到其他指令需要它的 地方，那么就可以避免停顿。采用定向技术消除上例中的相关 工作过程演示,3.4 流水线的相关与冲突,采用定向技术后的流水线数据通路,3.4 流水线的相关与冲突,当定向硬件检测到前面某条指令的结果寄存器就是当前指令的源寄存器时，控制逻辑会将前面那条指令的结果直接从其产生的地方定向到当前指令所需的位置。结果数据不仅可以从某一功能部件的输出定向到其自身的输入，而且还可以定向到其他功

42、能部件的输入。 举例:,DSUB R1，R2，R3LD R5，0（R1）SD R5，12（R1）,3.4 流水线的相关与冲突,更多的定向路径,3.4 流水线的相关与冲突,需要停顿的数据冲突 并不是所有的数据冲突都可以用定向技术来解决。 举例:,LD R1，0（R2）DADD R4，R1，R5AND R6，R1，R7XOR R8，R1，R9,增加流水线互锁硬件，插入“暂停”。 作用：检测发现数据冲突，并使流水线停顿，直至冲突消失。 举例：演示A 演示B,3.4 流水线的相关与冲突,无法将LD指令的结果定向到DADD指令,3.4 流水线的相关与冲突,流水线互锁机制插入气泡后的执行过程,3.4 流水

43、线的相关与冲突,插入停顿前后的流水线时空图,3.4 流水线的相关与冲突,依靠编译器解决数据冲突 让编译器重新组织指令顺序来消除冲突，这种技术称为指令调度或流水线调度。例如：采用典型的代码生成方法， 表达式ABC的代码会导致暂停,举例： 请为下列表达式生成没有暂停的指令序列: ABC ； DEF ； 假设载入延迟为1个时钟周期。 题解,3.4 流水线的相关与冲突,控制冲突 执行分支指令的结果有两种分支成功：PC值改变为分支转移的目标地址。 在条件判定和转移地址计算都完成后，才改变PC值。不成功或者失败：PC的值保持正常递增， 指向顺序的下一条指令。处理分支指令最简单的方法：“冻结”或者“排空”流

44、水线 。 优点：简单。前述5段流水线中，改变PC值是在MEM段进行的。 给流水线带来了3个时钟周期的延迟。,简单处理分支指令：分支成功的情况,简单处理分支指令：分支失败的情况,3.4 流水线的相关与冲突,把由分支指令引起的延迟称为分支延迟。分支指令在目标代码中出现的频度每34条指令就有一条是分支指令。 假设：分支指令出现的频度是30， 流水线理想 CPI1， 那么：流水线的实际 CPI 1.9。可采取两种措施来减少分支延迟。在流水线中尽早判断出分支转移是否成功；尽早计算出分支目标地址。,3.4 流水线的相关与冲突,下面的讨论中，我们假设： 这两步工作被提前到ID段完成，即分支指令是在ID段的末

45、尾执行完成，所带来的分支延迟为一个时钟周期。,3.4 流水线的相关与冲突,3种通过软件（编译器）来减少分支延迟的方法 共同点：对分支的处理方法在程序的执行过程中始终是 不变的，是静态的。要么总是预测分支成功，要么总是预测分支失败。预测分支失败 允许分支指令后的指令继续在流水线中流动，就 好象什么都没发生似的。若确定分支失败，将分支指令看作是一条普通指 令，流水线正常流动。,3.4 流水线的相关与冲突,若确定分支成功，流水线就把在分支指令之后 取出的所有指令转化为空操作，并按分支目地 重新取指令执行。要保证：分支结果出来之前不会改变处理机的状态，以 便一旦猜错时，处理机能够回退到原先的状态。流水

46、线的处理过程,3.4 流水线的相关与冲突,预测分支成功 假设分支转移成功，并从分支目标地址处取指令执行。起作用的前题：先知道分支目标地址，后知道分支是否 成功。前述5段流水线中，这种方法没有任何好处。延迟分支主要思想： 从逻辑上“延长”分支指令的执行时间。把延迟分支看成是由原来的分支指令和若干个延迟槽构成，不管分支是否成功，都要按顺序执行延迟槽中的指令。延迟分支以及指令的执行顺序,具有一个分支延迟槽的流水线的执行过程,分支延迟槽中的指令“掩盖”了流水线原来必须插入的暂停周期。,3.4 流水线的相关与冲突,分支延迟指令的调度任务：在延迟槽中放入有用的指令。由编译器完成。能否带来好处取决于编译器能

47、否把有用的指令调度到延迟槽中。三种调度方法： 从前调度从目标处调度从失败处调度,调度前和调度后的代码,3.4 流水线的相关与冲突,三种方法的要求及效果,调 度 策 略,对调度的要求,什么情况下起作用,从 前 调 度,从目标处调度,从失败处调度,必须保证在分支失败时执行被调度的指令不会导致错误。有可能需要复制指令,被调度的指令必须与分支无关,必须保证在分支成功时执行被调度的指令不会导致错误,任何情况,分支成功时(但由于复制指令，有可能会增大程序空间),分支失败时,3.4 流水线的相关与冲突,分支延迟受到两个方面的限制：可以被放入延迟槽中的指令要满足一定的条件。编译器预测分支转移方向的能力。进一步

48、改进：分支取消机制（取消分支） 当分支的实际执行方向和事先所预测的一样时，执行分支延迟槽中的指令，否则就将分支延迟槽中的指令转化成一个空操作。“预测成功取消”分支的执行过程,预测分支成功的情况下，分支取消机制的执行情况,实现MIPS指令子集的一种简单数据通路。该数据通路的操作分成5个时钟周期取指令指令译码/读寄存器执行/有效地址计算存储器访问/分支完成写回 只讨论整数指令的实现（包括：load和store，等于0转移，整数ALU指令等。）,3.5 流水线的实现,3.5.1 MIPS的一种简单实现,3.5 流水线的实现,一条MIPS指令最多需要以下5个时钟周期：取指令周期（IF） 操作IRMem

49、PCNPCPC+4指令译码/读寄存器周期（ID） 操作A RegsrsB RegsrtImm （IR16）16#IR16.31） 指令的译码操作和读寄存器操作是并行进行的。 原因：在MIPS指令格式中，操作码字段以及rs、rt 字段都是在固定的位置。 这种技术称为固定字段译码技术。,3.5 流水线的实现,执行/有效地址计算周期（EX） 不同指令所进行的操作不同：存储器访问指令 操作 ALUoA + Imm寄存器寄存器ALU指令 操作 ALUoA func B寄存器立即值ALU指令 操作 ALUoA op Imm分支指令 操作 ALUoNPC+（Imm2）； cond（A = = 0）,3.5

50、流水线的实现,将有效地址计算周期和执行周期合并为一个时钟周期，这是因为MIPS指令集采用loadstore结构，没有任何指令需要同时进行数据有效地址的计算、转移目标地址的计算和对数据进行运算。存储器访问/分支完成周期（MEM）所有指令都要在该周期对PC进行更新。 除了分支指令，其他指令都是做PCNPC在该周期内处理的MIPS指令仅仅有load、store和分支三种指令。,3.5 流水线的实现,存储器访问指令 操作 LMDMemALUo 或者 MemALUoB分支指令 操作 if （cond） PC ALUo else PCNPC写回周期（WB）不同的指令在写回周期完成的工作也不一样。寄存器寄存