TP?nTpipeline?185(ns?1)

E?400?10850?8?1017?58.82%

段 4_4 4_3 4_2 4_1 3_2 3_1 2 1 11121234 7658 109 99 6 5 34 7810 34 56 78 1010 23 45 67 89 24-1 850ns 时间 3.14 流水线由53、4、5段，第3段的各段的时

水线的输出可以直接返回输入端或

1 2 3-1 3-2 4-2 4-3 4-4 有一条静态多功能段组成，加法用1、乘法用1、2、5段，时间为2△t，其余间均为△t，而且流

4暂存于相应的流水寄存器中。现要在该流水线上计算 ? ( A i i ? B) ，画出其时空图，并计

i?1算其吞吐率、加速比和效率。

1 △t 加法 2△t △t △t 2 △t 3 乘法 4 5

解：首先，应选择适合于流水线工作的算法。对于本题，应先计算A1＋B1、A2＋B2、A3＋B3和A4＋B4；再计算(A1＋B1) ×(A2＋B2)和(A3＋B3) ×(A4＋B4)；然后求总的结果。

其次，画出完成该计算的时空图，如图所示，图中阴影部分表示该段在工作。

A 段 5 4 3 2 1 B C D A×B C×D A×B×C×D A=A1＋B1 B=A2＋B2 C=A3＋B3 D=A4＋B4 输入0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 A B C D A×B C×D 时间 A1 A2 A3 A4 B1 B2 B3 B4

由图可见，它在18个△t时间中，给出了7个结果。所以吞吐率为：

TP?718?t

如果不用流水线，由于一次求积需3△t，一次求和需5△t，则产生上述7个结果共需（4×5+3×3）△t =29△t。所以加速比为：

2 9 ? t

S?18?t?1.61该流水线的效率可由阴影区的面积和5个段总时空区的面积的比值求得： 4 ? 5 ?3 ? 3

E?

5?18?0.3223.15 动态多功能流水线由6个功能段组成，如下图：

加法 S1 S2 S3 S4 S5 S6 乘法

其中，S1、S4、S5、S6组成乘法流水线，S1、S2、S3、S6组成加法流水线，各个功能段时间均为50ns，假设该流水线的输出结果可以直接返回输入端，而且设置有足够的缓冲

5寄存器，若以最快的方式用该流水计算：?xiyizi

i?1（1）画出时空图；

（2）计算实际的吞吐率、加速比和效率。 解：机器一共要做10次乘法，4次加法。

第5章 存储层次

5.2 简述“Cache—主存”层次与“主存—辅存”层次的区别。 答： 存储层次 比较项目 目的 存储管理的实现 访问速度的比值 （第一级比第二级） 典型的块（页）大小 CPU对第二级的访问方式 不命中时CPU是否切换 “Cache—主存”层次 为了弥补主存速度的不足 全部由专用硬件实现 几比一 几十个字节 可直接访问 不切换 “主存—辅存”层次 为了弥补主存容量的不足 主要由软件实现 几万比一 几百到几千个字节 均通过第一级 切换到其它进程

5.3 地址映象方法有哪几种？它们各有什么优缺点？

答：(1) 全相联映象。实现查找的机制复杂，代价高，速度慢。Cache空间的利用率较高，块冲突概率较低，因而Cache的失效率也低。（2）直接映象。实现查找的机制简单，速度快。Cache空间的利用率较低，块冲突概率较高，因而Cache的失效率也高。（3）组相联映象。组相联是直接映象和全相联的一种折衷。

5.4 降低Cache失效率有哪几种方法？简述其基本思想。 答：常用的降低Cache失效率的方法有下面几种：

（1） 增加Cache块大小。增加块大小利用了程序的空间局部性。

（2） 增加Cache的容量。 （3） 提高相联度，降低冲突失效。 （4） 伪相联Cache，降低冲突失效。当对伪相联Cache进行访问时，首先是按与直接映象相同的方式进行访问。如果命中，则从相应的块中取出所访问的数据，送给CPU，访问结束。如果不命中，就将索引字段的最高位取反，然后按照新索引去寻找“伪相联组”中的对应块。如果这一块的标识匹配，则称发生了“伪命中”。否则，就访问下一级存储器。

（5） 硬件预取技术。在处理器提出访问请求前预取指令和数据。 （6） 由编译器控制的预取，硬件预取的替代方法，在编译时加入预取的指令，在数据被用到之前发出预取请求。

（7） 编译器优化，通过对软件的优化来降低失效率。

（8） “牺牲”Cache。在Cache和其下一级存储器的数据通路之间增设一个全相联的小Cache，存放因冲突而被替换出去的那些块。每当发生不命中时，在访问下一级存储器之前，先检查“牺牲”Cache中是否含有所需的块。如果有，就将该块与Cache中某个块做交换，把所需的块从“牺牲”Cache 调入Cache。

5.5 简述减小Cache失效开销的几种方法。

答：让读失效优先于写、写缓冲合并、请求字处理技术、非阻塞Cache或非锁定Cache技术、采用二级Cache。

5.6 通过编译器对程序优化来改进Cache性能的方法有哪几种？简述其基本思想。 答：（1）数组合并。通过提高空间局部性来减少失效次数。有些程序同时用相同的索引来访问若干个数组的同一维，这些访问可能会相互干扰，导致冲突失效，可以将这些相互独立的数组合并成一个复合数组，使得一个Cache块中能包含全部所需元素。（2）内外循环交换。循环嵌套时，程序没有按数据在存储器中的顺序访问。只要简单地交换内外循环，就能使程序按数据在存储器中的存储顺序进行访问。（3）循环融合。有些程序含有几部分独立的程序段，它们用相同的循环访问同样的数组，对相同的数据作不同的运算。通过将它们融合成一个单一循环，能使读入Cache的数据被替换出去之前得到反复的使用。（4）分块。通过改进时间局部性来减少失效。分块不是对数组的整行或整列进行访问，而是对子矩阵或块进行操作。

5.7 在“Cache—主存”层次中，主存的更新算法有哪两种？它们各有什么特点？ 答：（1）写直达法。易于实现，而且下一级存储器中的数据总是最新的。 （2）写回法。速度快，“写”操作能以Cache存储器的速度进行。而且对于同一单元的多个写最后只需一次写回下一级存储器，有些“写”只到达Cache，不到达主存，因而所使用的存储器频带较低。

5.8 组相联Cache的失效率比相同容量直接映象Cache的失效率低。由此能否得出结论：采用组相联一定能带来性能上的提高？为什么？

答：不一定。因为组相联命中率的提高是以增加命中时间为代价的，组相联需要增加多路选择开关。

5.9 写出三级Cache的平均访问时间的公式。

解：平均访存时间 ＝ 命中时间＋失效率×失效开销