解：没有控制相关时流水线的平均CPI＝1 存在控制相关时：由于无条件分支在第二个时钟周期结束时就被解析出来，而条件分支 要到第3个时钟周期结束时才能被解析出来。所以：
（1）若使用排空流水线的策略，则对于条件分支，有两个额外的stall，对无条件分支，有一个额外的stall：
CPI = 1+20%*2+5%*1 = 1.45 加速比S=CPI/1 = 1.45
（2） 若使用预测分支成功策略，则对于不成功的条件分支，有两个额外的stall，对无条件分支和成功的条件分支，有一个额外的stall 1：
CPI = 1+20%*(60%*1+40%*2) +5%*1 = 1.33 加速比S=CPI/1 = 1.33
（3）若使用预测分支失败策略，则对于成功的条件分支，有两个额外的stall；对无条件分支，有一个额外的stall；对不成功的条件分支，其目标地址已经由PC 值给出，不必等待，所以无延迟：
CPI = 1+20%*(60%*2 + 40%*0) +5%*1 = 1.29 加速比S=CPI/1 = 1.29
3.18 在CRAY-1机器上，按照链接方式执行下述4条向量指令（括号中给出了相应功能部件的执行时间），如果向量寄存器和功能部件之间的数据传送需要1拍，试求此链接流水线的通过时间是多少拍？如果向量长度为64，则需多少拍才能得到全部结果？ V0←存储器 （从存储器中取数：7拍） V2←V0+V1 （向量加：3拍）
V3←V2 解：通过时间就是每条向量指令的第一个操作数执行完毕需要的时间，也就是各功能流水线由空到满的时间，具体过程如下图所示。要得到全部结果，在流水线充满之后，向量中后继操作数继续以流水方式执行，直到整组向量执行完毕。 T通过＝（7＋1）＋（1＋3＋1）＋（1＋4＋1）＋（1＋2＋1）＝23（拍）T总共?T通过＋（64－1）＝23＋63＝86（拍）访存存储器V0V1V2V3V4V5向量加左移向量逻辑乘 3.19 某向量处理机有16个向量寄存器，其中V0~V5中分别放有向量A、B、C、D、E、F，向量长度均为8，向量各元素均为浮点数；处理部件采用两条单功能流水线，加法功能部件时间为2拍，乘法功能部件时间为3拍。采用类似于CARY-1的链接技术，先计算（A+B）*C，在流水线不停流的情况下，接着计算（D+E）*F。 （1） 求此链接流水线的通过时间？（设寄存器入、出各需1拍） （2） 假如每拍时间为50ns，完成这些计算并把结果存进相应寄存器，此处理部件的实 word文档 可自由复制编辑 A3 际吞吐率为多少MFLOPS？ 解：（1）我们在这里假设A＋B的中间结果放在V6中，（A＋B）×C地最后结果放在V7中，D＋E地中间结果放在V8中，（D＋E）×F的最后结果放在V9中。具体实现参考下图： V0AV1BV6V2CV7向量加向量乘V3DV4EV8V5FV9 通过时间应该为前者（（A＋B）×C）通过的时间： T通过= (1+2+1)+(1+3+1) =9（拍） （2）在做完（A＋B）×C之后，作（C＋D）×E就不需要通过时间了。 V6←A＋B V7←V6×C V8←D＋E V9←V8×F T?T通过＋（8－1）?8?24（拍）?1200(ns)TP?32?26.67MFLOPST第5章 存储层次 5.1解释下列术语 多级存储层次：采用不同的技术实现的存储器，处在离CPU不同距离的层次上，各存储器之间一般满足包容关系，即任何一层存储器中的内容都是其下一层（离CPU更远的一层）存储器中内容的子集。目标是达到离CPU最近的存储器的速度，最远的存储器的容量。 全相联映象：主存中的任一块可以被放置到Cache中任意一个地方。 直接映象：主存中的每一块只能被放置到Cache中唯一的一个地方。 组相联映象：主存中的每一块可以放置到Cache中唯一的一组中任何一个地方（Cache分成若干组，每组由若干块构成）。 替换算法：由于主存中的块比Cache中的块多，所以当要从主存中调一个块到Cache中时，会出现该块所映象到的一组（或一个）Cache块已全部被占用的情况。这时，需要被迫腾出其中的某一块，以接纳新调入的块。 LRU：选择最近最少被访问的块作为被替换的块。实际实现都是选择最久没有被访问的块作为被替换的块。 写直达法：在执行写操作时，不仅把信息写入Cache中相应的块，而且也写入下一级存储器中相应的块。 写回法：只把信息写入Cache中相应块，该块只有被替换时，才被写回主存。 按写分配法：写失效时，先把所写单元所在的块调入Cache，然后再进行写入。 不按写分配法：写失效时，直接写入下一级存储器中，而不把相应的块调入Cache。 命中时间：访问Cache命中时所用的时间。 失效率：CPU访存时，在一级存储器中找不到所需信息的概率。 失效开销：CPU向二级存储器发出访问请求到把这个数据调入一级存储器所需的时间。 强制性失效：当第一次访问一个块时，该块不在Cache中，需要从下一级存储器中调入Cache， word文档 可自由复制编辑 这就是强制性失效。 容量失效：如果程序在执行时，所需要的块不能全部调入Cache中，则当某些块被替换后又重新被访问，就会产生失效，这种失效就称作容量失效。 冲突失效：在组相联或直接映象Cache中，若太多的块映象到同一组（块）中，则会出现该组中某个块被别的块替换（即使别的组或块有空闲位置），然后又被重新访问的情况。 2：1Cache经验规则：大小为N的直接映象Cache的失效率约等于大小为N /2的两路组相联Cache的实效率。 相联度：在组相联中，每组Cache中的块数。 Victim Cache：位于Cache和存储器之间的又一级Cache，容量小，采用全相联策略。用于存放由于失效而被丢弃（替换）的那些块。每当失效发生时，在访问下一级存储器之前，先检查Victim Cache中是否含有所需块。 故障性预取：在预取时，若出现虚地址故障或违反保护权限，就会发生异常。 非故障性预取：在预取时，若出现虚地址故障或违反保护权限，不发生异常。 非阻塞Cache：Cache在等待预取数据返回时，还能继续提供指令和数据。 尽早重启动：在请求字没有到达时，CPU处于等待状态。一旦请求字到达，就立即发送给CPU，让等待的CPU尽早重启动，继续执行。 请求字优先：调块时，首先向存储器请求CPU所要的请求字。请求字一旦到达，就立即送往CPU，让CPU继续执行，同时从存储器调入该块的其余部分。 虚拟Cache：地址使用虚地址的Cache。 多体交叉存储器：具有多个存储体，各体之间按字交叉的存储技术。 存储体冲突：多个请求要访问同一个体。 TLB：一个专用高速存储器，用于存放近期经常使用的页表项，其内容是页表部分内容的一个副本。 5.2简述“Cache—主存”层次与“主存—辅存”层次的区别。 答： 存储层次 比较项目 目的 存储管理的实现 访问速度的比值 （第一级比第二级） 典型的块（页）大小 CPU对第二级的访问方式 不命中时CPU是否切换 “Cache—主存”层次 为了弥补主存速度的不足 全部由专用硬件实现 几比一 几十个字节 可直接访问 不切换 “主存—辅存”层次 为了弥补主存容量的不足 主要由软件实现 几万比一 几百到几千个字节 均通过第一级 切换到其它进程 5.3地址映象方法有哪几种？它们各有什么优缺点？ 答：(1) 全相联映象。实现查找的机制复杂，代价高，速度慢。Cache空间的利用率较高，块冲突概率较低，因而Cache的失效率也低。（2）直接映象。实现查找的机制简单，速度快。Cache空间的利用率较低，块冲突概率较高，因而Cache的失效率也高。（3）组相联映象。组相联是直接映象和全相联的一种折衷。 5.4降低Cache失效率有哪几种方法？简述其基本思想。 答：常用的降低Cache失效率的方法有下面几种： （1） 增加Cache块大小。增加块大小利用了程序的空间局部性。 （2） 增加Cache的容量。 word文档 可自由复制编辑 （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的平均访问时间的公式。 解：平均访存时间 ＝ 命中时间＋失效率×失效开销 只有第I层失效时才会访问第I＋1。 设三级Cache的命中率分别为HL1、 Hl2、 HL3，失效率分别为Ml1、Ml2、ML3，第三级Cache的失效开销为PL3。 平均访问时间TA ＝HL1＋Ml1{Hl2＋Ml2(HL3＋ML3×PL3)} 5.10 假设对指令Cache的访问占全部访问的75%；而对数据Cache的访问占全部访问的25%。Cache的命中时间为1个时钟周期，失效开销为50 个时钟周期，在混合Cache中一次load或store操作访问Cache的命中时间都要增加一个时钟周期，32KB的指令Cache的失效率为0.39%，32KB的数据Cache的失效率为4.82%，64KB的混合Cache的失效率为 word文档 可自由复制编辑 1.35%。又假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。试问指令Cache和数据Cache容量均为32KB的分离Cache和容量为64KB的混合Cache相比，哪种Cache的失效率更低？两种情况下平均访存时间各是多少？ 解：（1）根据题意，约75%的访存为取指令。 因此，分离Cache的总体失效率为：（75%×0.15%）＋（25%×3.77%）＝1.055%； 容量为128KB的混合Cache的失效率略低一些，只有0.95%。 （2）平均访存时间公式可以分为指令访问和数据访问两部分： 平均访存时间＝指令所占的百分比×（读命中时间＋读失效率×失效开销）＋ 数据所占的百分比×（数据命中时间＋数据失效率×失效开销） 所以，两种结构的平均访存时间分别为： 分离Cache的平均访存时间＝75%×（1＋0.15%×50）＋25%×（1＋3.77%×50） ＝（75%×1.075）＋（25%×2.885）＝1.5275 混合Cache的平均访存时间＝75%×（1＋0.95%×50）＋25%×（1＋1＋0.95%×50） ＝（75%×1.475）＋（25%×2.475）＝1.725 因此，尽管分离Cache的实际失效率比混合Cache的高，但其平均访存时间反而较低。分离Cache提供了两个端口，消除了结构相关。 5.11 给定以下的假设，试计算直接映象Cache和两路组相联Cache的平均访问时间以及CPU的性能。由计算结果能得出什么结论？ （1） 理想Cache情况下的CPI为2.0，时钟周期为2ns，平均每条指令访存1.2次； （2） 两者Cache容量均为64KB，块大小都是32字节； （3） 组相联Cache中的多路选择器使CPU的时钟周期增加了10％； （4） 这两种Cache的失效开销都是80ns； （5） 命中时间为1个时钟周期； （6） 64KB直接映象Cache的失效率为1.4％，64KB两路组相联Cache的失效率为1.0％。 解： 平均访问时间＝命中时间＋失效率×失效开销 平均访问时间1-路=2.0+1.4% *80=3.12ns 平均访问时间2-路=2.0*(1+10%)+1.0% *80=3.0ns 两路组相联的平均访问时间比较低 CPUtime=（CPU执行+存储等待周期）*时钟周期 CPU time=IC（CPI执行+总失效次数/指令总数*失效开销） *时钟周期 =IC（（CPI执行*时钟周期）+（每条指令的访存次数*失效率*失效开销*时钟周期）） CPU time 1-way=IC(2.0*2+1.2*0.014*80)＝5.344IC CPU time 2-way=IC(2.2*2+1.2*0.01*80)＝5.36IC 相对性能比： CPUtime?2wayCPUtime?1way?5.36/5.344=1.003 直接映象cache的访问速度比两路组相联cache要快1.04倍，而两路组相联Cache的平均性能比直接映象cache要高1.003倍。因此这里选择两路组相联。 5.12 假设一台计算机具有以下特性： （1） 95％的访存在Cache中命中； （2） 块大小为两个字，且失效时整个块被调入； （3） CPU发出访存请求的速率为109字/s； （4） 25％的访存为写访问； （5） 存储器的最大流量为109字/s（包括读和写）； word文档 可自由复制编辑