计算机系统结构__《张晨曦、王志英》课后习题参考答案

相联度:在组相联中,每组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的容量。 (3) 提高相联度,降低冲突失效。 (4) 伪相联Cache,降低冲突失效。当对伪相联Cache进行访问时,首先是按与直接映象相同的方式进行访问。

26

如果命中,则从相应的块中取出所访问的数据,送给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的失效率为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)平均访存时间公式可以分为指令访问和数据访问两部分:

平均访存时间=指令所占的百分比×(读命中时间+读失效率×失效开销)+ 数据所占的百分比×(数据命中

27

时间+数据失效率×失效开销)

所以,两种结构的平均访存时间分别为:

分离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(包括读和写); (6) 主存每次只能读或写一个字; (7) 在任何时候,Cache中有30%的块被修改过; (8) 写失效时,Cache采用按写分配法。

现欲给该计算机增添一台外设,为此首先想知道主存的频带已用了多少。试对于以下两种情况计算主存频带的平均使用比例。

(1) 写直达Cache; (2) 写回法Cache。 解:采用按写分配

(1)写直达cache访问命中,有两种情况:

读命中,不访问主存;

28

写命中,更新cache和主存,访问主存一次。 访问失效,有两种情况:

读失效,将主存中的块调入cache中,访问主存两次;

写失效,将要写的块调入cache,访问主存两次,再将修改的数据写入cache和主存,访问主存一次,共三次。上述分析如下表所示。

访问命中 Y Y N N 访问类型 读 写 读 写 频率 95%*75%=71.3% 95%*25%=23.8% 5%*75%=3.8% 5%*25%=1.3% 访存次数 0 1 2 3 一次访存请求最后真正的平均访存次数=(71.3%*0)+(23.8%*1)+(3.8%*2)+(1.3%*3)=0.35

已用带宽=0.35×109/10 9 =35.0%

(2)写回法cache访问命中,有两种情况:

读命中,不访问主存;

写命中,不访问主存。采用写回法,只有当修改的cache块被换出时,才写入主存;

访问失效,有一个块将被换出,这也有两种情况:

如果被替换的块没有修改过,将主存中的块调入cache块中,访问主存两次; 如果被替换的块修改过,则首先将修改的块写入主存,需要访问主存两次;然后将主存中的块调入cache块中,需要访问主存两次,共四次访问主存。 访问命中 Y Y N N

所以:

一次访存请求最后真正的平均访存次数=66.5%*0+28.5%*0+3.5%*2+1.5%*4=0.13

已用带宽=0.13×10 9/10 9=13%

5.13 在伪相联中,假设在直接映象位置没有发现匹配,而在另一个位置才找到数据(伪命中)时,不对这两个位置的数据进行交换。这时只需要1个额外的周期。假设失效开销为50个时钟周期,2KB直接映象Cache的失效率为9.8%,2路组相联的失效率为7.6%;128KB直接映象Cache的失效率为1.0%,2路组相联的失效率为0.7%。

(1) 推导出平均访存时间的公式。 (2) 利用(1)中得到的公式,对于2KBCache和128KBCache,计算伪相联的平均访存时间。 解:

不管作了何种改进,失效开销相同。不管是否交换内容,在同一“伪相联”组中的两块都是用同一个索引得到的,因此失效率相同,即:失效率伪相联=失效率2路。

伪相联cache的命中时间等于直接映象cache的命中时间加上伪相联查找过程中的命中时间*该命中所需的额外开销。

命中时间伪相联=命中时间1路+伪命中率伪相联×1

交换或不交换内容,伪相联的命中率都是由于在第一次失效时,将地址取反,再在第二次查找带来的。 因此 伪命中率伪相联=命中率2路-命中率1路=(1-失效率2路)-(1-失效率1路)

=失效率1路-失效率2路。交换内容需要增加伪相联的额外开销。

平均访存时间伪相联=命中时间1路+(失效率1路-失效率2路)×1

29

块为脏 N Y N Y 频率 95%*70%=66.5% 95%*30%=28.5% 5%*70%=3.5% 5%*30%=1.5% 访存次数 0 0 2 4 +失效率2路×失效开销1路

将题设中的数据带入计算,得到:

平均访存时间2Kb=1+(0.098-0.076)*1+(0.076 *50 ) =4.822 平均访存时间128Kb=1+(0.010-0.007)*1+(0.007 *50 ) =1.353 显然是128KB的伪相联Cache要快一些。

5.14 假设采用理想存储器系统时的基本CPI是1.5,主存延迟是40个时钟周期;传输速率为4字节/时钟周期,且Cache中50%的块是修改过的。每个块中有32字节,20%的指令是数据传送指令。并假设没有写缓存,在TLB失效的情况下需要20时钟周期,TLB不会降低Cache命中率。CPU产生指令地址或Cache失效时产生的地址有0.2%没有在TLB中找到。

(1) 在理想TLB情况下,计算均采用写回法16KB直接映象统一Cache、16KB两路组相联统一Cache和32KB直

接映象统一Cache机器的实际CPI;

(2) 在实际TLB情况下,用(1)的结果,计算均采用写回法16KB直接映象统一Cache、16KB两路组相联统一

Cache和32KB直接映象统一Cache机器的实际CPI;

其中假设16KB直接映象统一Cache、16KB两路组相联统一Cache和32KB直接映象统一Cache的失效率分别为2.9%、2.2%和2.0%;25%的访存为写访问。

解: CPI=CPI 执行+存储停顿周期数/指令数

存储停顿由下列原因引起:

? 从主存中取指令

? load和store指令访问数据 ? 由TLB引起

存储停顿周期数取指令停顿数据访问停顿+TLB停顿=+指令数指令数指令数停顿周期数存储访问 =?失效率?失效开销指令数指令数存储停顿周期数TLB停顿??R指令P指令?+(f数据R数据P数据)+指令数指令数(1)对于理想TLB,TLB失效开销为0。而对于统一Cache,R指令=R数据

P指令=主存延迟+传输一个块需要使用的时间=40+32/4=48(拍)

若为读失效,P数据=主存延迟+传输一个块需要使用的时间=40+32/4=48(拍) 若为写失效,且块是干净的,

P数据=主存延迟+传输一个块需要使用的时间=40+32/4=48(拍)

若为写失效,且块是脏的,

P数据=主存延迟+传输两个块需要使用的时间=40+64/4=56(拍)

CPI=1.5+[RP+(RP*20%)+0 ]

指令访存全是读,而数据传输指令Load或Store指令,

f数据*P数据=读百分比*(f数据*P数据)+写百分比*(f数据*P干净数据*其对应的百分比

+f数据*P脏数据*其对应的百分比)

=20%*(75%×48+25%*(50%*48+50%*(48+16)))=50(拍)

代入上述公式计算出结果为:

配置 16KB 直接统一映象 16KB两路统一映象 32KB直接统一映象 失效率 0.029 0.022 0.020 CPI 4.4 3.4 3.2 (2)

TLB停顿存储访问次数TLB访问?(?)?TLB失效率?TLB失效开销

指令数指令数存储访问次数30

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4