计算机体系结构(计算)

1、有一条流水线如下所示。 123450ns50ns100ns200ns

Èë³ö

（1） 求连续输入10条指令，该流水线的实际吞吐率和效率； （2） 该流水线的瓶颈在哪一段？请采取三种不同的措施消除此“瓶颈”。对于你所给出的新流水线，计算连续输入10条指令时，其实际吞吐率和效率。

解：（1）2200(ns)2009200)10050(50t)1n(tTmaxm1iipipeline

)(ns2201TnTP1pipeline45.45%1154400TPmtTPEm1ii

（2）瓶颈在3、4段。  变成八级流水线（细分）

123_13_24_14_4Èë³ö

50ns50ns50ns50ns50ns50ns

850(ns)509850t1)(ntTmaxm1iipipeline)(ns851TnTP1pipeline

58.82%17108400TPmtiTPEm1i

 变成两级流水线（合并） 1234Èë³ö

200ns200ns2200(ns)20092200t1)(ntTmaxm1iipipeline



)(ns2201TnTP1pipeline 90.91%11102400TPmtiTPEm1i  重复设置部件 123_13_24_14_24_34_4

11112222333344445555666677778899101089108

910

850nsTime

Stage

)(ns851TnTP1pipeline58.82%1710885010400E 2、如果流水线有m段，各段的处理时间分别是ti（i=1，2，…，m），现在有n个任务需要完成，且每个任务均需流水线各段实现，请计算： （1） 流水线完成这n个任务所需要的时间； （2） 和非流水线实现相比，这n个任务流水实现的加速比是多少？加速比的峰值是多少？

解：（1）m1imaxipipelinet1)(ntT

（2）m1iinopipelinetnT

m)Speedupm,(n)t(t1nmnmSpeedupt1)(nttnTTSpeedup0imaxm1imaxim1iipipelinenopipeline





1 2 3-1 3-2

4-1 4-2 4-3 4-4 3、假设某应用程序中有4类操作，通过改进，各操作获得不同的性能提高。具体数据如下表所示：

操作类型 程序中的数量 （百万条指令） 改进前的执行时间 （周期） 改进后的执行时间 （周期） 操作1 10 2 1 操作2 30 20 15 操作3 35 10 3 操作4 15 4 1 （1）改进后，各类操作的加速比分别是多少？ （2）各类操作单独改进后，程序获得的加速比分别是多少？ （3）4类操作均改进后，整个程序的加速比是多少？

解：根据Amdahl定律SeFeFeSn)1(1可得

操作类型 各类操作的指令条数在程序中所占的比例Fi 各类操作的加速比Si 各类操作单独改进后，程序获得的加速比 操作1 11.1% 2 1.06 操作2 33.3% 1.33 1.09 操作3 38.9% 3.33 1.37 操作4 16.7% 4 1.14

4类操作均改进后，整个程序的加速比： 2.16)1(1iiinSFFS

3、计算题：Amdahl定律：加快某部件执行速度所能获得的系统性能加速比，受限于该部件的执行时间占系统中总执行时间的百分比（P7页）。 向上（下）兼容：按某档机器编制的程序，不加修改就能运行于比它高（低）档的机器。 向前（后）兼容：按某个时期投入市场的某种型号机器编制的程序，不加修改地就能运行于在它之前（后）投入市场的机器。向后兼容是系列机的根本特征。 兼容机：由不同公司厂家生产的具有相同系统结构的计算机 。 4、计算题：哈夫曼树 哈弗曼编码方法的计算（1）码长表示法（2）码点表示法 1）码长表示法：2—4—6(有三种长度，两位的、四位的、六位的) 2）码点表示法：3/6/4（最短的有三条，最长的有四条，中间长度对应为6条） 3）2—4最多码点数：13 解释：2可以有00、01、10、11四种，但是必须是2-4扩展至少有一个为两位，其他的可以在前面扩展两位，每个可以对应四种例如对于01可以变成：0001、0101、1001、1101，所以总共加起来最多只能是3*4+1=13种 4）以下四种编码中：不是2-4扩展的是（D） A:1/2 B:2/8 C:3/4 D:4/8

时间 机器档次 高

低 向上兼容 向下兼容 向前兼容 向后兼容 当前机器 大题：有一台模型机，有以下七种不同的指令，使用频率表示如下： T1: 20% T2: 12% T3:11% T4: 15% T5: 8% T6:3% T7: 2% T8:18% T9: 10% T10: 1% （1） 上图为哈夫曼编码图：平均长度为 2*20%+3*（10%+11%+12%+15%+18%）+4*8%+5*3%+6*(1%+2%)=3.03 可以表示成：00、010、011、100、101、110、1110、11110、111110、111111 （2）若用定长操作码表示至少需要多少位？ 答：至少需要4位 （3）用扩展操作码（只有两位）可以有多种方式表示，要求平均长度不能大于3.2，给出最合理的编码方式，并求出平均编码长度？ ①采用扩展操作码可以用2—4扩展操作码的码点1/9表示：求得平均长度为：1*（20%）+4（80%）=3.4>3.2不符合 ②3—4的6/4编码方式：平均长度为3*（10+11+12+15+18+20）%+4*(1+2+3+8)% =3.14<3.2符合条件 ③4—5编码6/4方式：4*（10+11+12+15+18+20）%+5*(1+2+3+8)%>3.2 ④2—5编码中的3/7方式：2*（15+18+20）%+5*（1+2+3+8+10+11+12）%=3.41>3.2不符合 5、流水线指标：吞吐率、加速比、效率 A吞吐率是指单位时间内流水线所完成的任务数或输出结果的数量。 最大吞吐率是指流水线在连续流动达到稳定状态后所得到的吞吐率。 第一种情况：各段时间相等（设为△t0） 假设流水线由 m 段组成，完成 n 个任务。 完成 n 个任务所需的时间

第二种情况：各段时间不等 B加速比是指流水线的速度与等功能非流水线的速度之比。S＝T非流水／T流水 若流水线为 m 段，且各段时间相等，均为△t0 ，则： T非流水＝n m△t0 T流水＝m△t0＋(n－1)△t0 (公式自己代入) C (1)若各段时间相等，则各段的效率ei相等，即e1＝e2 ＝e3＝、、、＝em＝n△t0／T流水 整个流水线的效率为:E=n△t0/T流水=n/（n+m-1） (2)从时－空图上看，效率实际上就是 n 个任务所占的时空区与 m 个段总的时空区之比， 即： n 个任务占用的时空区 E ＝━━━━━━━━━━━━━ m 个段总的时空区 实例分析:性能分析（分析法, 时空图法）. 例1. 四段流水线, △t1=△t3=△t4=△t, △t2=3△t,4个任务、10个任务时TP，η、SP 。 （1）分析法: 各段时间不等

(2) 时空图法:

比较说明:N>>M流水性能才发挥得更好 交换函数：实现二进制地址编码中第k位互反的输入端与输出端之间的连接

主要用于构造立方体互连网络和各种超立方体互连网络。它共有n＝log2N种互连函数。（N为结点个数）当N＝8时，n＝3，可得到常用的立方体互连函数：

N=8 的立方体交换函数

011121011121xxxxxxxxxxxxxxEkkknnkkknn

0120122

0120121

0120120xxxxxxCxxxxxxCxxxxxxC

 均匀洗牌函数：将输入端分成数目相等的两半，前一半和后一半按类似均匀混洗扑克牌的方式交叉地连接到输出端（输出端相当于混洗的结果）。 函数关系

即把输入端的二进制编号循环左移一位。 N=8 的均匀洗牌和逆均匀洗牌函数 逆均匀洗牌函数：将输入端的二进制编号循环右移 一位而得到所连接的输出端编号。 互连函数

逆均匀洗牌是均匀洗牌的逆函数 6、三种通道类型，三种通道与CPU、设备控制器和外设的连接关系，三种类型通道的流量 （1）字节多路通道 a为多台低速或中速的外设服务。b以字节交叉的方式分时轮流地为它们服务。c字节多路通道可以包含多个子通道，每个子通道连接一台设备控制器。 （2）选择通道 a为多台高速外围设备服务。 b在一段时间内只为一台高速外设独占使用。c选择通道的硬件包括5个寄存器、格式变换部件及通道控制部件 （3）数组多路通道 a适用于高速设备。b每次选择一个高速设备后传送一个数据块，轮流为多台外围设备服务。c数组多路通道之所以能够并行地为多台高速设备服务，是因为虽然其所连设备的传输速率很高，但寻址等辅助操作时间很长。 通道流量：一个通道在数据传送期间，单位时间内能够传送的最大数据量，一般用字 节个数来表示。又称为通道吞吐率，通道数据传输率等。 通道最大流量，一个通道在满负荷工作状态下的流量。 TS：设备选择时间。 TD：传送一个字节所用的时间。 p： 在一个通道上连接的设备台数，且这些设备同时都在工作。 n: 每台设备传送的字节数，这里假设每台设备传送的字节数都相同。 k： 数组多路通道传输的一个数据块中的包含的字节数。在一般情况下，k磁带等磁表面存储器，通常k=512。 T： 通道完成全部数据传送工作所需时间。 字节多路通道：

选择通道： 数组多路通道：

0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (a) C0交换函数 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7

(b) C1交换函数 (c) C2交换函数

0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 (a) 均匀洗牌函数 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7

(b) 逆均匀洗牌函数

101320121nnnnnxxxxxxxxxS

121001211xxxxxxxxSnnnn

np)T(TTDSBYTEnp)TnT(TDSSELECTnp)TkT(TDSBLOCK