流水线习题

1.设一条指令的执行过程分成取指令、分析指令和执行指令三个阶段，每个阶段所需的时间分别为△t、△t和2△t。分别求出下列各种情况下，连续执行N条指令所需的时间。（1）顺序执行方式；（2）只有“取指令”与“执行指令”重叠；（3）“取指令”、“分析指令”与“执行指令”重叠。2.列举出下面循环中的所有相关，包括输出相关、反相关、真相关。for(i=2;i100;i=i+1)a[i]=b[i]+a[i];/*s1*/c[i+1]=a[i]+d[i];/*s2*/a[i-1]=2*b[i];/*s3*/b[i+1]=2*b[i];/*s4*/3.有一指令流水线如下所示入1234出50ns50ns100ns200ns（1）求连续输入10条指令，该流水线的实际吞吐率和效率；（2）该流水线的“瓶颈”在哪一段？请采取两种不同的措施消除此“瓶颈”。对于你所给出的两种新的流水线，连续输入10条指令时，其实际吞吐率和效率各是多少？4.有一个流水线由4段组成，其中每当流经第3段时，总要在该段循环一次，然后才能流到第4段。如果每段经过一次所需要的时间都是t，问：（1）当在流水线的输入端连续地每t时间输入任务时，该流水线会发生什么情况？（2）此流水线的最大吞吐率为多少？如果每t2输入一个任务，连续处理10个任务时的实际吞吐率和效率是多少？（3）当每段时间不变时，如何提高该流水线的吞吐率？仍连续处理10个任务时，其吞吐率提高多少？5.有一条静态多功能流水线由5段组成，加法用1、3、4、5段，乘法用1、2、5段，第3段的时间为2△t，其余各段的时间均为△t，而且流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中。现要在该流水线上计算，画出其时空图，并计算其吞吐率、加速比和效率。6.动态多功能流水线由6个功能段组成，如下图：其中，S1、S4、S5、S6组成乘法流水线，S1、S2、S3、S6组成加法流水线，各个功能段时间均为50ns，假设该流水线的输出结果可以直接返回输入端，而且设置有足够的缓冲寄存器，若以最快的方式用该流水计算：51iiiizyx（1）画出时空图；（2）计算实际的吞吐率、加速比和效率。12345乘法加法△t△t2△t△t△t)(41iiiBAS1S2S3S4S5乘法加法S61.参考答案：解：（1）每条指令的执行时间为：△t＋△t＋2△t＝4△t连续执行N条指令所需的时间为：4N△t（2）连续执行N条指令所需的时间为：4△t＋3（N-1）△t＝（3N＋1）△t（3）连续执行N条指令所需的时间为：4△t＋2（N-1）△t＝（2N＋2）△t2.参考答案：解：展开循环两次：a[i]=b[i]+a[i];/*s1*/c[i+1]=a[i]+d[i];/*s2*/a[i-1]=2*b[i];/*s3*/b[i+1]=2*b[i];/*s4*/a[i+1]=b[i+1]+a[i+1];/*s1’*/c[i+2]=a[i+1]+d[i+1];/*s2‘*/a[i]=2*b[i+1];/*s3‘*/b[i+2]=2*b[i+1];/*s4‘*/输出相关：无反相关：无真相关：S1&S2由于循环引入的相关：S4&S4’（真相关）、S1’&S4（真相关）、S3’&S4（真相关）、S1&S3’（输出相关、反相关）、S2&S3’（反相关）。3.参考答案：解：（1）2200(ns)2009200)10050(50t)1n(tTmaxm1iipipeline)(ns2201TnTP1pipeline45.45%1154400TPmtTPEm1ii（2）瓶颈在3、4段。变成八级流水线（细分）123_13_24_14_4入出50ns50ns50ns50ns50ns50ns850(ns)509850t1)(ntTmaxm1iipipeline)(ns851TnTP1pipeline58.82%17108400TPmtiTPEm1i重复设置部件)(ns851TnTP1pipeline58.82%1710885010400E4.参考答案：解：（1）会发生流水线阻塞情况。第1个任务S1S2S3S3S4第2个任务S1S2stallS3S3S4第3个任务S1stallS2stallS3S3S4第4个任务S1stallS2stallS3S3S4123_13_24_14_24_34_411112222333344445555666677778899101089108910850ns时间段123-13-24-14-24-34-4（2）54.35%925045TPE2310TnTp23T21TPpipelinepipelinemaxtttt（3）重复设置部件tt751410TnTPpipeline吞吐率提高倍数＝tt231075＝1.645.参考答案：解：首先，应选择适合于流水线工作的算法。对于本题，应先计算A1＋B1、A2＋B2、A3＋B3和A4＋B4；再计算(A1＋B1)×(A2＋B2)和(A3＋B3)×(A4＋B4)；然后求总的结果。段时间12341111122222333334444455555666667777788888999991010101010t23123_13_24ΔtΔtΔtΔtΔt段时间1123_13_24111122222333334444455555666667777788888999991010101010t14其次，画出完成该计算的时空图，如图所示，图中阴影部分表示该段在工作。由图可见，它在18个△t时间中，给出了7个结果。所以吞吐率为：tTP817如果不用流水线，由于一次求积需3△t，一次求和需5△t，则产生上述7个结果共需（4×5+3×3）△t=29△t。所以加速比为：该流水线的效率可由阴影区的面积和5个段总时空区的面积的比值求得：6.参考答案：解：机器一共要做10次乘法，4次加法。时间段12345012345678910111213141516输入A1B1A2B2A3B3A4B4ABCDABCDA×BA×BC×DA×B×C×DA=A1＋B1B=A2＋B2C=A3＋B3D=A4＋B4C×D171861.18192ttS223.01853354E