第三章 流水线技术
3.1名词解释流水线——将一个重复的时序过程，分解为若干个子过程，而每一个子过程都可有效地在其专用功能段上与其他子过程同时执行。
单功能流水线——只能完成一种固定功能的流水线。
多功能流水线——流水线的各段可以进行不同的连接，从而使流水线在不同的时间，或者在同一时间完成不同的功能。
静态流水线——同一时间内，流水线的各段只能按同一种功能的连接方式工作。
动态流水线——同一时间内，当某些段正在实现某种运算时，另一些段却在实现另一种运算。
部件级流水线——（运算操作流水线）把处理机的算术逻辑部件分段，以便为各种数据类型进行流水操作。
处理机级流水线——（指令流水线）把解释指令的过程按照流水方式处理。
处理机间流水线——（宏流水线）由两个以上的处理机串行地对同一数据流进行处理，每一个处理机完成一项任务。
线性流水线——指流水线的各段串行连接，没有反馈回路。
非线性流水线——指流水线中除有串行连接的通路外，还有反馈回路。
标量流水处理机——处理机不具有向量数据表示，仅对标量数据进行流水处理。
向量流水处理机——处理机具有向量数据表示，并通过向量指令对向量的各元素进行处理。
结构相关——某些指令组合在流水线中重叠执行时，发生资源冲突，则称该流水线有结构相关。
数据相关——当指令在流水线中重叠执行时，流水线有可能改变指令读/写操作的顺序，使得读/写操作顺序不同于它们非流水实现时的顺序，将导致数据相关。
定向——将计算结果从其产生的地方直接送到其他指令需要它的地方，或所有需要它的功能单元，避免暂停。
RAW——两条指令i，j，i在j前进入流水线，j执行要用到i的结果，但当其在流水线中重叠执行时，j可能在i写入其结果之前就先行对保存该结果的寄存器进行读操作，得到错误值。
WAW——两条指令i，j，i在j前进入流水线，j、i的操作数一样，在流水线中重叠执行时，j可能在i写入其结果之前就先行对保存该结果的寄存器进行写操作，导致写错误。
WAR——两条指令i，j，i在j前进入流水线，j可能在i读某个寄存器之前对该寄存器进行写操作，导致i读出数据错误。
3.2 简述流水线技术的特点。
流水过程由多个相联系的子过程组成，每个过程称为流水线的“级”或“段” ；
每个子过程由专用的功能段实现；
各个功能段所需时间应尽量相等，否则，时间长的功能段将成为流水线的瓶颈，会造成流水线的“堵塞”和“断流”；
流水线需要有“通过时间”(第一个任务流出结果所需的时间)，在此之后流水过程才进入稳定工作状态，每一个时钟周期(拍)流出一个结果；
流水技术适合于大量重复的时序过程，只有在输入端能连续地提供任务，流水线的效率才能充分发挥。
3.3 请画出DLX基本流水线，并简述其工作原理。
工作原理：把一条DLX指令在5个周期内实现，将每一个时钟周期看作是流水线的一个时钟周期，硬件每个时钟周期启动一条新的指令，并执行5条不同指令中的某一部分。每条指令虽仍需5个时钟周期完成，但提高了吞吐率，实现了流水。
指令/时钟
1
2
3
4
5
6
7
8
9
I
IF
ID
EX
MEM
WB
I+1
IF
ID
EX
MEM
WB
I+2
IF
ID
EX
MEM
WB
I+3
IF
ID
EX
MEM
WB
I+4
IF
ID
EX
MEM
WB
3.5 解决流水线结构相关的方法有哪些？
流水化功能单元资源重复暂停流水线
3.6 降低流水线分支损失的方法有哪些？
（1）在流水线中尽早判断出分支转移是否成功；
（2）尽早计算出分支转移成功时的PC值（即分支的目标地址）
“冻结”或“排空”流水线的方法预测分支失败预测分支成功延迟分支
3.7 请对延迟分支办法中的三种调度策略进行评价。
1．从前调动：分支必须不依赖于被调度的指令，总是可以有效提高流水线性能。
2．从目标处调度：若分支转移失败，必须保证被调度的指令对程序的执行没有影响，可能需要复制被调度指令。分支转移成功时，可提高流水线性能。但由于复制指令，可能加大程序空间。
3．从失败处调度：若分支转移成功，必须保证被调度的指令对程序的执行无影响。分支转移失败时，可提高流水线性能。
3.8 简述三种向量处理方法，它们对向量处理机的结构要求有什么不同？
1．水平处理方式：若向量长度为N，则水平处理方式相当于执行N次循环。若使用流水线，在每次循环中可能出现数据相关和功能转换，不适合对向量进行流水处理。
2．垂直处理方式：将整个向量按相同的运算处理完毕之后，再去执行其他运算。适合对向量进行流水处理，向量运算指令的源/目向量都放在存储器内，使得流水线运算部件的输入、输出端直接与存储器相联，构成M-M型的运算流水线。
3．分组处理方式：把长度为N的向量分为若干组，每组长度为n，组内按纵向方式处理，依次处理各组，组数为，适合流水处理。可设长度为n的向量寄存器，使每组向量运算的源/目向量都在向量寄存器中，流水线的运算部件输入、输出端与向量寄存器相联，构成R-R型运算流水线。
有一条流水线如下所示。
求连续输入10条指令，该流水线的实际吞吐率和效率；
该流水线的瓶颈在哪一段？请采取三种不同的措施消除此“瓶颈”。对于你所给出的新流水线，计算连续输入10条指令时，其实际吞吐率和效率。
解：（1）
（2）瓶颈在3、4段。
变成八级流水线（细分）
变成两级流水线（合并）
重复设置部件
3.10 一个流水线由四段组成，其中每当流经第三段时，总要在该段循环一次才能流到第四段。如果每段经过一次的时间都是△t，问：
当在流水线的输入端每△t时间输入任务时，该流水线会发生什么情况？
此流水线的实际吞吐率为多少？如果每2△t输入一个任务，连续处理10个任务的实际吞吐率和效率是多少？
当每段时间不变时，如何提高该流水线的吞吐率？仍连续处理10个任务 时，其吞吐率提高多少？
解：（1）会发生流水线阻塞情况。
（2）
（3）重复设置部件
吞吐率提高倍数＝＝1.64
3.11 如果流水线有m段，各段的处理时间分别是ti（i=1，2，…，m），现在有n个任务需要完成，且每个任务均需流水线各段实现，请计算：
流水线完成这n个任务所需要的时间；
和非流水线实现相比，这n个任务流水实现的加速比是多少？加速比的峰值是多少？
解：（1）
（2）
3.12 在改进的DLX流水线上运行如下代码序列：
LOOP: LW R1,0(R2)
ADDI R1,R1,#1
SW 0(R2),R1
ADDI R2,R2,#4
SUB R4,R3,R2
BNZ R4,LOOP
其中，R3的初始值是R2＋396。假设：在整个代码序列的运行过程中，所有的存储器访问都是命中的，并且在一个时钟周期中对同一个寄存器的读操作和写操作可以通过寄存器“定向”。问：
在没有任何其它定向（或旁路）硬件的支持下，请画出该指令序列执行的流水线时空图。假设采用排空流水线的策略处理分支指令，且所有的存储器访问都可以命中Cache，那么执行上述循环需要多少个时钟周期？
假设该DLX流水线有正常的定向路径，请画出该指令序列执行的流水线时空图。假设采用预测分支失败的策略处理分支指令，且所有的存储器访问都可以命中Cache，那么执行上述循环需要多少个时钟周期？
假设该DLX流水线有正常的定向路径，请对该循环中的指令进行调度。注意可以重新组织指令的顺序，也可以修改指令的操作数，但是不能增加指令的条数。请画出该指令序列执行的流水线时空图，并计算执行上述循环需要的时钟周期数？
解：
寄存器读写可以定向，无其他旁路硬件支持。排空流水线。
第i次迭代（i＝0..98）开始周期：1＋（i×17）
总的时钟周期数：（98×17）＋18＝1684
有正常定向路径，预测分支失败。
第i次迭代（i＝0..98）开始周期：1＋（i×10）
总的时钟周期数：（98×10）＋11＝991
有正常定向路径。单周期延迟分支。
Loop,lw r1,0(r2)
addi r2,r2,#4
addi r1,r1,#1
sub r4,r3,r2
bnz r4,loop
sw r1,-4(r2)
第i次迭代（i ＝0..98）开始周期：1＋（i ×6 ）
总的时钟周期数：（98×6）＋10＝598
3.13 假设各种分支所占指令数地百分比如下表所示：
条件分支
20％（其中60％是成功的）
跳转和调用
5％
现有一深度为4地流水线（流水线有4段），无条件分支在第二个时钟周期结束时就被解析出来，而条件分支要到第三个时钟周期结束时才能被解析出来。第一个流水段是完全独立于指令类型的，即所有的指令都必须经过第一个流水段的处理。请问在没有任何结构相关地情况下，该流水线相对于存在上述结构相关情况下地加速比是多少？
解：在不存在结构相关时，每条指令的平均执行时间是1个时钟周期，而存在上述条件相关的情况下，并假设条件分支预测成功，那么无条件分支和成功的条件分支的等待时间都是1，而不成功地条件分支等待时间是2个周期；所以加速比就等于存在相关的每条指令的平均执行时间和不存在相关的每条指令的执行时间1的比值：
每条指令的平均等待时间：
所以：
CRAY-1机器上，按照链接方式执行下述4条向量指令（括号中给出了相应功能部件的时间），如果向量寄存器和功能部件之间数据传输需要1拍，试求此链接流水线的通过时间是多少拍？如果向量长度为64，则需要多少拍才能得到全部结果。
V0←存储器 （从存储器中取数：7拍）
V2←V0＋V1 （向量加：3拍）
V2←V2 < A3 （按(A3)左移：4拍）
V5←V3∧V4 （向量逻辑乘：2拍）
解：通过时间就是每条向量指令的第一个操作数执行完毕需要的时间，也就是各功能流水线由空到满的时间，具体过程如下图所示。要得到全部结果，在流水线充满之后，向量中后继操作数继续以流水方式执行，直到整组向量执行完毕。
向量处理机有16个向量寄存器，其中V0～V5中分别存放有向量A、B、C、D、E、F，向量长度均为8，向量各元素均为浮点数；处理部件采用两个单功能流水线，加法功能部件时间为2拍，乘法功能部件时间为3拍。采用类似CRAY-1的链接技术，先计算（A＋B）*C，在流水线不停留的情况下，接着计算（D＋E）*F。
求此链接流水线的通过时间为多少拍？（设寄存器入、出各需1拍）
假如每拍时间为50ns，完成这些计算并把结果存进相应寄存器，此处理部件地实际吞吐率为多少MFLOPS？
解：（1）我们在这里假设A＋B的中间结果放在V6中，（A＋B）*C地最后结果放在V7中，D＋E地中间结果放在V8中，（D＋E）*F的最后结果放在V9中。具体实现参考下图：
通过时间应该为前者（（A＋B）*C）通过的时间：
T通过= (1+2+1)+(1+3+1) =9（拍）
（2）在做完（A＋B）*C之后，作（C＋D）*E就不需要通过时间了。
