计算机体系结构第5章答案

一填空题五、存储层次1、速度容量2、容量速度3、高程序局部性4、指令数据5、映象规则查找算法6、组相联直接7、018、Cache块数9、有效位标识10、组相联映象全相联映象11、按写分配法不按写分配法12、写回法写直达法13、随机法先进先出法（FIFO法）14、先进先出法（FIFO法）最近最少使用法（LRU）15、CPU访问Cache失效Cache块已全部被占满16、随机法最近最少使用法（LRU）17、写回法写直达法18、写回法写直达法19、速度快所使用的存储器频带较低20、易于实现一致性好21、25622、失效率23、减少失效开销减少Cache命中时间24、强制性失效容量失效冲突失效25、强制性冷启动（首次访问）容量26、组相联直接碰撞（干扰）27、冲突失效强制性容量28、强制性容量29、N/22：1的Cache经验规则30、强制性冲突31、失效开销命中时间32、伪相联CacheVictimCache33、执行指令和读取数据能重叠执行循环34、编译器优化35、Cache块较小下一条指令正好访问同一Cache块的另一部分36、非阻塞Cache37、小快38、快速命中减少失效次数39、容量小、结构简单的Cache虚拟Cache写操作流水化40、延迟带宽41、大小相同的块可变长的块三名词解释五、存储层次（20个）5.1存储器的层次结构1、存储层次：采用多种存储器技术，构成存储层次以实现存储器的大容量、高速度和低价格要求。2、失效率：CPU访存时，在一级存储器中找不到所需信息的概率。3、失效开销：CPU向二级存储器发出访问请求到把这个数据调入一级存储器所需的时间。5.2Cache基本知识4、全相联映象：主存中的任一块可以被放置到Cache中任意一个地方。5、直接映象：主存中的每一块只能被放置到Cache中唯一的一个地方。6、组相联映象：主存中的每一块可以放置到Cache中唯一的一组中任何一个地方（Cache分成若干组，每组由若干块构成）。7、替换算法：由于主存中的块比Cache中的块多，所以当要从主存中调一个块到Cache中时，会出现该块所映象到的一组（或一个）Cache块已全部被占用的情况。这时，需要被迫腾出其中的某一块，以接纳新调入的块。8、LRU：选择最近最少被访问的块作为被替换的块。实际实现都是选择最久没有被访问的块作为被替换的块。9、写直达法：在执行写操作时，不仅把信息写入Cache中相应的块，而且也写入下一级存储器中相应的块。写回法：只把信息写入Cache中相应块，该块只有被替换时，才被写回主存。10、按写分配法：写失效时，先把所写单元所在的块调入Cache，然后再进行写入。11、不按写分配法：写失效时，直接写入下一级存储器中，而不把相应的块调入Cache。5.3降低Cache失效率的方法12、强制性失效：当第一次访问一个块时，该块不在Cache中，需要从下一级存储器中调入Cache，这就是强制性失效。13、容量失效：如果程序在执行时，所需要的块不能全部调入Cache中，则当某些块被替换后又重新被访问，就会产生失效，这种失效就称作容量失效。14、冲突失效：在组相联或直接映象Cache中，若太多的块映象到同一组（块）中，则会出现该组中某个块被别的块替换（即使别的组或块有空闲位置），然后又被重新访问的情况。15、2：1Cache经验规则——大小为N的直接映象Cache的失效率约等于大小为N/2的两路组相联Cache的实效率。16、VictimCache——位于Cache和存储器之间的又一级Cache，容量小，采用全相联策略。用于存放由于失效而被丢弃（替换）的那些块。每当失效发生时，在访问下一级存储器之前，先检查VictimCache中是否含有所需块。17、伪相联Cache——一种既能获得多路组相联Cache的低失效率，又能获得直接映象Cache的命中速度的相联办法。5.4减少Cache失效开销18、子块放置技术——把一个Cache块划分为若干小块，称为子块（sub-blocks），并为每个子块赋予一位有效值，用于说明该子块中的数据是否有效。失效时，只需从下一级存储器调入一个子块。19、请求字优先——调块时，首先向存储器请求CPU所要的请求字。请求字一旦到达，就立即送往CPU，让CPU继续执行，同时从存储器调入该块的其余部分。5.5减少命中时间5.6主存20、独立存储体：设置多个存储控制器，使多个体能独立操作，以便能同时进行多个独立的访存。四简答题五、存储层次（16个）5.1存储器的层次结构1、对于理解一个具体存储层次的工作原理，需搞清楚哪些问题？答：对于一个存储层次，需搞清楚以下4个问题：（1）当把一个块调入高一层(靠近CPU)存储器时，可以放在哪些位置上?即映象规则问题；（2）当所要访问的块在高一层存储器中时，如何找到该块?即查找算法问题；（3）当发生失效时，应替换哪一块？即替换算法；（4）当进行写访问时，应进行哪些操作?即写策略。2、简述“Cache—主存”和“主存—辅存”层次的区别。存储层次比较项目“Cache—主存”层次“主存—辅存”层次目的为了弥补主存速度的不足为了弥补主存容量的不足存储管理实现全部由专用硬件实现主要由软件实现访问速度的比值（第一级比第二级）几比一几百比一典型的块（页）大小几十个字节几百到几千个字节CPU对第二级的访问方式可直接访问均通过第一级失效时CPU是否切换不切换切换到其它进程5.2Cache基本知识1、映象规则解决什么问题，各映象规则具体是什么？2、在“Cache-主存”存储层次中，地址映象方法有哪几种，它们是怎样进行地址映象的？各有何优缺点？3分答：设主存和Cache块地址分别为i和j。地址映象有以下三种：（1）直接映象法主存的一块只能映象到Cache中唯一的位置。1分（2）组相联映象，将Cache空间首先划分为组，一组内有多块(2g块)，组间主存的一块楞以映象到Cache中的唯一的一组中的任意一块。1分（3）全相联映象：主存的一块可以映象到Cache中的任意一块。1分优缺点：直接映象Cache命中时间小，失效率最高；全相联映象命中时间最长，失效率最低。2分3、在“Cache-主存”存储层次中，主存的更新算法有哪两种？它们各有何特点？更新算法名称各1分，两种算法特点各2分答：主存的更新算法有以下两种：（1）写直达法易于实现，而且下一级存储器中的数据总是最新的，但是增加多次不必要的向主存写入，采用写直达法的机器，一般设置写缓冲器。（2）写回法速度快，“写”操作能以Cache存储器的速度进行。而且对于同一单元的多个写最后只需一次写回下一级存储器，有些“写”只到达Cache，不到达主存，因而所使用的存储器频带较低，一般在cache的目录表（标识存储器）中设有“污染位”。4、在Cache中，查找方法怎样进行？答：CPU发出访存地址，如何根据这个访存地址来确定Cache中是否有所要访问的块，若有的话如何确定其位置，这就是查找方法。其具体实现是通过查找目录表来实现。目录表的结构包括有效位和标识。控制器通过比较目录表数据块的标识和CPU发来的主存地址标识部分进行比较，若相同且有效位为1，表示访问Cahe命中。若标识不相同或者标识相同但有效位不为1，则表示访问Cache失效。5、替换在什么情况下进行，替换算法有哪些？答：所要解决的问题：当新调入一块到Cache时，而Cache又已被占满时，替换哪一块出Cache？a.随机法:随机的选择被替换的块优点：实现简单b.先进先出法FIFO（Fisrt-In-First-Out）:选择最早调入的块作为被替换的块。c.最近最少使用法LRU(LeastRecentlyUsed):选择最久没有被访问的块作为被替换的块。5.3降低Cache失效率的方法1、失效的类型有哪些，在什么情况下产生？答：(1)强制性失效(Compulsorymiss)：当第一次访问一个块时，该块不在Cache中，需从下一级存储器中调入Cache，这就是强制性失效。也叫冷启动失效，首次访问失效。(2)容量失效(Capacitymiss)：如果程序执行时所需的块不能全部调入Cache中，则当某些块被替换后，若又重新被访问，就会发生失效。这种失效称为容量失效。(3)冲突失效(Conflictmiss)在组相联或直接映象Cache中，若太多的块映象到同一组(块)中，则会出现该组中某个块被别的块替换(即使别的组或块有空闲位置)，然后又被重新访问的情况。这就是发生了冲突失效。也叫碰撞失效，干扰失效。2、增加Cache块大小，对Cache性能有何影响？其原因是什么？答：(1)对于给定的Cache容量，当块大小增加失效率开始是下降，后来反而上升了；(2)Cache容量越大，使失效率达到最低的块大小就越大。导致上述失效率先下降后上升的原因，在于增加块大小会产生双重作用。一方面它减少了强制性失效，因为局部性原理有时间局部性和空间局部性两方面的含义，增加块大小利用了空间局部性；另一方面，由于增加块大小会减少Cache中块的数目，所以有可能会增加冲突失效。在Cache容量较小时，甚至还会增加容量失效。刚开始增加块大小时，由于块大小还不是很大，上述的第一种作用超过第二种作用，从而使失效率下降。但等到块大小较大时，第二种作用超过第一种作用，使失效率上升。3、VictimCache的实现思想是怎样的？答：在Cache和它从下一级存储器调数据的通路之间设置一个全相联的小Cache，称为VictimCache。VictimCache中存放由于失效而被替换出去的那些块（即Victim）。当发生失效时，在访问下一级存储器之前，先检查VictimCache中是否含有所需的块。如果有，就将该块与Cahce中某个块做交换。VictimCahce对于减小冲突失效很有效，特别是对于小容量的直接映象数据Cache，作用尤其明显。4、通过编译器对程序优化来改进Cache性能的方法有哪几种？简述其基本思想。答：（1）数组合并，通过提高空间局部性来减少失效次数。有些程序同时用相同的索引来访问若干个数组的同一维，这些访问可能会相互干扰，导致冲突失效，可以将这些相互独立的数组合并成一个复合数组，使得一个Cache块中能包含全部所需元素。（2）内外循环交换。循环嵌套时，程序没有按数据在存储器中的循序访问。只要简单地交换内外循环，就能使程序按数据在存储器中的存储循序进行访问。（3）循环融合。有些程序含有几部分独立的程序断，它们用相同的循环访问同样的数组，对相同的数据作不同的运算。通过将它们融合成一个单一循环，能使读入Cache的数据被替换出去之前得到反复的使用。（4）分块。通过改进时间局部性来减少失效。分块不是对数组的整行或整列进行访问，而是对子矩阵或块进行操作。5、简述减小Cache失效的几种方法。写出6种以上得全分，1种方法1分答：常用的降低Cache失效率的方法有下面几种：（1）增加Cache块大小。增加块大小利用了程序的空间局部性。（2）提高相联度，降低冲突失效。（3）VictimCache，降低冲突失效。（4）伪相联Cache，降低冲突失效。（5）硬件预取技术，指令和数据都可以在处理器提出访问请求前进行预取。（6）由编译器控制的预取，硬件预取的替代方法，在编译时加入预取的指令，在数据被用到之前发出预取请求。（7）编译器优化，通过对软件的优化来降低失效率。5.4减少Cache失效开销1、什么是请求字处理技术？请求字处理技术有哪两种方案，具体是怎样实现的？答：从下一级存储器调入Cache的块中，只有一个字是立即需要的。这个字称为请求字。请求字处理技术正是着眼于这种每次调块时CPU只用到请求字的特性。当CPU所请求的字到达时，不等整个块都调入Cache，就可以把该字发送给CPU并重启动CPU。有两种具体的方案：尽早重启动：调块时，从块的起始位置开始读起。一旦请求字到达，就立即发送给CPU，让CPU继续执行。请求字优先：调块时，从请求字所在的位置读起。这样，第一个读出的字便是请求字。将之立即发送给CPU。2、简述减小Cache失效开销的几种方