《计算机存储与外设》----1.4 Cache设计中要考虑的因素-阿里云开发者社区

开发者社区> 华章出版社> 正文
登录阅读全文

《计算机存储与外设》----1.4 Cache设计中要考虑的因素

简介:

本节书摘来自华章出版社《计算机存储与外设》一书中的第1章,第1.4节,作者Computer Organization and Architecture: Themes and Variations[英]艾伦·克莱门茨(Alan Clements) 著,沈 立 肖晓强 王苏峰 译,更多章节内容可以访问云栖社区“华章计算机”公众号查看。

1.4 Cache设计中要考虑的因素

前面已经说过,由于需要考虑的因素很多,Cache的设计比较复杂,其中一些因素依赖于计算机系统自身的属性。在本节中将讨论一些影响Cache系统设计的因素。


a2aa5827f83cd3e5eb1d0a41d11af0fde2136b46

1.4.1 物理Cache和逻辑Cache

在具有存储器管理单元的计算机系统中,Cache可以位于CPU和MMU之间,也可以位于MMU和物理内存之间。图1-18显示了这两种情况。如果在CPU数据终端上的数据被缓存,该数据称为逻辑数据(logical data),相应的Cache为逻辑Cache(logical Cache)。然而,如果数据经过MMU实现地址转换后被缓存,则该数据称为物理数据(physical data),相应的Cache为物理Cache(physical Cache)。下面将讨论逻辑Cache和物理Cache的含义以及它们之间的权衡。


54ca844ffa93af6bd7ea3735e0f48b0242ff53c7

物理Cache比逻辑Cache具有更长的访问时间,这是因为在物理Cache中直到MMU进行了逻辑地址到物理地址的转换后才可以进行数据访问。逻辑Cache比物理Cache要快,是因为逻辑Cache中的数据可以立刻被访问,而不必等待地址转换。

假设在多任务系统中发生了上下文切换且要执行一个新任务。当新任务开始时,操作系统将相应的地址转换表装入MMU。当逻辑地址到物理地址的映射关系改变时,Cache中数据以及相应的物理数据间的关系被打破;不能使用Cache中的数据,且逻辑Cache必须刷新。物理Cache在上下文切换时就不需要刷新。

然而,使用物理Cache的代价是在存储器访问前需要额外的时间来执行逻辑地址到物理地址的转换。在实践中,如果把Cache页面大小设置为与存储器页面大小一样,就可以实现Cache中的块查找与虚拟地址变换并行工作。微处理器一般使用物理Cache来减少切换上下文之后导致对Cache的刷新。

1.4.2 Cache电气特性

本书将在下一章中介绍主存储器系统,这里先对Cache的电路设计进行简要说明。半导体随机访问存储器有两大类:静态(static)和动态(dynamic)。静态存储器利用传统数字逻辑将一位数据存储在一个触发器中——正如在《计算机组成原理》第2章中描述的那样。静态存储器的特点是低功耗、高速和只要有电就能够保留数据。因此,Cache通常由静态RAM构造。不幸的是,它需要6个晶体管来存储一个比特位,因此,静态存储器单元的物理尺寸(即所占硅片的面积)比DRAM单元要大得多。这意味着,静态存储器比DRAM更昂贵且容量较小,因此不能用来构造大容量的Cache。
动态存储器(DRAM)通过对单个晶体管的电容充上电荷来保存数据。这使得DRAM非常便宜和紧凑,可以用来构造大容量存储器。不幸的是,DRAM需要更多的电量进行控制,且电容中的电量在几ms内就会漏光。为了保存DRAM中的数据,必须每隔4ms左右定期读取存储单元中的数据并将其写回。DRAM不适于构建Cache。

1.4.3 Cache一致性

Cache中的数据也在主存储器中。当处理器在写周期内修改数据元素时,必须对主存储器和Cache中的数据副本进行修改,虽然这种修改不必是同时的。因此,可能会出现一个数据存在两个不同副本的情况。如果Cache中的数据被修改,而主存储器的数据没有被修改(或倒过来),旧的、没有被修改的数据称为过时的(stale)数据。读者可以想象,这种情况可能会导致严重的错误。假设I/O控制器使用DMA试图从主存储器移动一块数据到磁盘上,此时处理器刚刚更新了其Cache中的数据但尚未修改主存储器中的数据副本。I/O控制器将把过时的数据而不是把Cache中最新的数据从主存储器移动到磁盘上。

Cache一致性(cache consistency)有时被称为数据一致性(data consistency)。图1-19中给出了这样一个系统,两个处理器共享一个存储器。假设在此多处理器系统中的处理器1执行了存储器写操作,只更新了自己的局部Cache而没有写入存储器。Cache中的存储器中的数据拷贝是不一致的。这种情况将持续到存储器写回(write back)操作将数据更新。如果处理器2在数据更新前读取存储器中相同位置的数据,它从存储器中访问到的就是过时的数据。


31d8159f4cb95059020ef041891cc57bd2d51b3d

当多个处理器都有自己的局部Cache时也会发生类似的问题。假设处理器X同时更新了自己的局部Cache和共有的存储器。处理器Y也可能在其局部Cache中缓存了相同数据的一个副本。处理器Y并不知道它缓存的数据已经是过时的。Cache一致性这个术语意味着在不同的Cache和主存储器中的数据必须保持同步(即没有过时的数据)。使Cache和主存储器中的数据保持一致(即保证Cache一致性)是设计多处理器系统时需要主要考虑的问题之一。

有些处理器通过一种被称为总线侦听(bus snooping)的技术来保持Cache的一致性。处理器通过监视地址流和数据流发现那些向主存储器的写访问、同时在自己的Cache中也有一个副本的情况。当主存储器中的数据被修改,该处理器局部Cache中的内容可以被标记为无效,或将其Cache更新。

1.4.4 块大小

块是Cache中的基本存储单位。一个重要的问题是,要多大的块才能获得最佳性能?针对块大小和Cache性能之间的关系已经展开了大量的研究,有时是通过模拟软件的Cache操作,有时是通过监控计算机系统中真实Cache的操作。


7d18657d2a07c875f54dee5737c2fbed7a6ccfaa

最佳的块容量取决于几个方面,尤其是正在执行的程序的性质。负责控制处理器和存储器之间数据流量的总线协议也会影响Cache的性能。典型计算机的总线负责将地址传送到主存储器,然后从数据总线发送或接收一个数据字——每次存储器访问都需要一个地址和一个数据元素。假设总线可以工作在突发模式(burst mode),即发送一个地址,然后获得一批连续的数据值。

显然,这样的总线相对每次只能传输一个数据元素的总线来说能更好地传输较大的块。另一个决定最佳块容量的因素是指令和数据的混合情况。针对指令的最佳块容量并不一定与针对数据的最佳块容量相同。

假设块容量非常小。CISC微处理器,如Intel IA32系列,具有可变长度指令,其范围从2个到10个或更多的字节。对于很长的指令,可能会出现指令的一部分在某个块中缓存而另一部分在另一个块中缓存的情况。当读取这样的一条指令时,必须两次访问Cache。增加块大小减小了多次访问Cache(或称为块交叉,line crosser)的现象。

增加块容量会提高Cache的效率,因为数据对象(例如,指令、向量或线性表)是由一组连续的字节组成的,可以利用空间局部性原理。然而,当块容量不断增加,命中率也会下降,因为减少了块的数量使得给定对象被缓存的概率降低。此外,大的块的性能很大程度上依赖于数据访问的局部性。当发生失效将一块调入Cache时,它可能包含不经常访问的数据,反而把经常访问的数据替换出去了。


6e0ebc51fb41135cac3112e9965329acf8ec4975

图1-20给出了数据访问的块容量和Cache容量之间的关系。这些经典的结果是通过模拟得到的,当时Cache的容量比现在的要小得多。图1-20画出的是失效率而不是命中率的情况。每条曲线对应一个特定的Cache容量(从32B~32KB)。图1-21提供指令Cache的相应结果。数据Cache的失效率首先逐渐变好(即越来越小)然后逐渐恶化(即越来越大)直到块容量与Cache容量本身相等;而指令Cache的失效率随块容量的增加而减小。这表明,访问的局部性对指令的作用比对数据的作用更强。一般情况下,只要给定Cache容量就有一个最佳的块容量;例如256B的Cache,最佳块容量为64B。Cache容量越大,最佳的块容量就越大。


cfa097fec9256625e4bb34a1c8944d3dc3e03b12

1.4.5 取指策略

有几种策略可以用于降低失效率,从而提升Cache性能(例如,按需获取、预取、选择性获取)。按需获取(demand fetch)策略在失效后调入所需块,这是一种最简单的选择。预取(prefetch)策略预测未来Cache的需求(例如,如果没有缓存块i+1,当访问块i时也调入第i+1块)。实现预取算法有许多可能的方法。选择性获取(selective fetch)策略在主存储器的部分内容不能被缓存的情况下使用。例如,在多处理器系统中,由多个处理器共享的数据就不应该被缓存,如果这些数据被缓存而处理器修改了存储器中的拷贝,Cache和存储器中的数据将不再保持一致。

如果需要快速访问数据,就应该尽早地获取它。通过预取(prefetch)数据可以最大限度地发挥Cache的作用。一些微处理器的指令集包括预取指令,它只产生操作数地址而不做其他事情。当操作数出现在总线上时,Cache系统自动缓存这个地址上的数据。该指令并没有其他功能,只是一个触发预取的虚拟操作。

如果,在几个指令后,需要访问预取地址中的数据,相应的数据已经在Cache中。该预取操作可由程序员手工完成或编译器自动优化过程来完成。预取不是一门精确的科学。如果预取得太晚,当CPU需要数据时,它可能不在Cache中。另一方面,如果数据预取得太早,Cache要为新的数据块腾出空间,而在CPU有机会访问它之前可能会将其替换出去。这样过早地预取数据又在使用数据之前将其替换,就是Cache污染(cache pollution)的例子。

预取与循环密切相关,这是因为控制结构循环出现使得可以预先知道将使用的数据。预取最简单的方式是在访问数组元素之前包括一个预取地址。考虑表达式S = ∑ai的计算。相应的代码是:


6b22450bc470da1dfc391cffae1ef1c2ad351ddc

根据Wiel和Lilja给出的例子,这里使用fetch(&address)来表示预取操作和预取的地址。预取最简单的例子是在循环中使用地址前访问该地址;即


1c64b1250bf6f56ee92eecc5ba89c3f896b1ad78

这样将产生下次访问的地址,当再次循环时,i+1这个位置已经被访问。可以在下面两个方面改进该段代码:一是初始元素没有被预取;二是由于每次循环只有一个有效操作所以循环效率较低。考虑下面的代码:


af7e92aa1c3936d1df30aec239d8fb24ff61c47f

在这种情况下,一次循环执行4个操作。由于每次取指调入Cache中的数据块中所包含16个字节可以被4个连续的指令使用,因此只需要做一次预取。

1.4.6 多级Cache

在20世纪90年代后期,存储器价格暴跌,半导体技术可以将非常复杂的系统放在芯片上,时钟频率达到了500MHz(时钟周期时间只有2ns)。Cache系统的容量和复杂性都增加了,计算机系统开始实现两级Cache:在CPU内部的一级Cache和在主板上的二级Cache。两级Cache系统中使用少量速度非常高的一级Cache和由大量速度快的存储器构成的二级Cache。换句话说,有两个层次的Cache串在一起。首先访问速度快、容量小的一级Cache。如果没有所需数据,则访问速度较慢、容量较大的二级Cache。如果仍然没有找到数据,则需要访问主存储器。两级Cache系统的访问时间由一级Cache的访问时间加上二级Cache的访问时间再加上主存储器的访问时间;即

tave = h1tc1 + (1-h1)h2tc2 + (1-h1)(1-h2)tm

其中,h1为一级Cache的命中率;tc1为一级Cache的访问时间;h2为二级Cache的命中率,tc2为二级Cache的访问时间。得到这个公式是下面3种概率之和:

tave =访问一级Cache的时间+访问二级Cache的时间+访问主存储器的时间
一级Cache的访问时间是h1tc1。如果一级Cache发生失效且二级Cache命中,访问二级Cache的时间是(1-h1)h2tc2。如果数据不在两级Cache中,访问存储器的时间为(1-h1)(1-h2)tm。因此,总的访问时间为:

tave = h1tc1 + (1-h1)h2tc2 + (1-h1)(1-h2)tm

该公式为一个简化形式,因为没有考虑Cache写回和Cache加载策略。考虑下面这个例子。某计算机有一级Cache和二级Cache。访问一级Cache没有开销,需要1个周期。在二级Cache中命中需要4个周期。如果没有已缓存数据,则访问主存储器,包括Cache加载,需要120个时钟周期。如果假设一级Cache的命中率为95%,二级Cache的后续命中率是80%,平均访问时间是多少?
tave = h1tc1 + (1-h1)h2tc2 + (1-h1)(1-h2)tm

 = 0.95×1 + (1-0.95)×0.80×4 + (1-0.95)×(1-0.80)×120
 = 0.95 + 0.16 + 1.20
 =2.31个时钟周期

来自飞思卡尔半导体公司应用笔记AN2663的图1-22给出了命中率与一级Cache及二级Cache的容量之间的关系,并用三维图形表示。可见,峰值命中率是96%,此时执行了特定的代码(GCC编译器)。该应用笔记的结论是,16KB的一级Cache和1KB的二级Cache的性能与1KB的一级Cache和16KB的二级Cache的性能几乎相同(虽然没有人会设计出一级Cache比二级Cache大的系统)。


5314681698de1dddd0455dc9495141cd1751d88e


0436f7985a274ec39f16ae1db3d01daec5ed5004

1.4.7 指令和数据Cache

数据和指令都是冯·诺依曼概念的核心;即它们共享相同的存储器。Cache设计者可以选择使用混合Cache(unified cache)来缓存数据和指令,或者实现分离的数据和指令Cache(split cache)。将数据和指令Cache分开是很有意义的,因为它们有不同的特性。除了将块调入Cache以外,是不会修改指令Cache中的项目的。此外,不用担心修改那些替换出指令Cache的指令,这是因为程序在其执行过程中不发会变化。由于指令Cache中的内容不会被修改,实现指令Cache要比实现数据Cache容易得多。将指令和数据Cache分别实现可以提高CPU与存储器间的带宽,这是因为指令和数据可以同时读取。对于流水线系统来说,为了实现指令和数据的同时访问,必须采用分离的指令和数据Cache。混合Cache和分离Cache的特点如下:

指令Cache可以为产生指令流而优化。
数据Cache可以为读写操作而优化。
数据Cache可以单独进行优化。
指令Cache并不支持自修改代码。
混合Cache支持自修改代码。
数据Cache可以通过同时操作增加带宽。
混合Cache需要更快速的存储器。
混合Cache更加灵活(分离Cache中可能出现指令Cache满而数据Cache还空着一半的情况)。

今天大多数的处理器都有分离的Cache,即使在具有多级Cache的系统中。高级别的Cache可以采用混合Cache,而低级的Cache需要分离Cache。

图1-23中AMD的Barcelona体系结构演示了如何进行Cache的设计。Barcelona是一个多核系统,每个核心都有它自己的64KB一级Cache和512KB的二级Cache。所有4个核心共享2MB的三级Cache。一级Cache由两个分离的32KB的Cache构成:一个数据Cache和一个指令Cache。传统上,多级Cache的访问顺序是从最低级Cache开始根据失效情况逐渐延伸到更高级的存储层次(先访问一级Cache,然后询问二级Cache,接着是三级Cache、主存储器,直到失效的数据被找到)。在Barcelona体系结构中,一级Cache是所有Cache加载的最终目标,所有取得的数据都放到一级Cache中。二级Cache保存被替换出一级Cache中的数据。因为一级Cache和二级Cache之间是紧耦合的,所以从二级Cache到一级Cache传输数据所产生的延迟较低。
三级Cache被多个核共享。加载数据时将直接从三级Cache传给一级Cache而不通过二级Cache。被传送的数据要么由于需要被多个处理器使用而保持在三级Cache中,要么就因为不需要共享而删除。与二级Cache类似,三级Cache不保存来自存储器的数据,而是保存被替换出二级Cache的数据。


e9414470b35504d3a57a27cc33fd643a44a5cdb7

图1-24给出了与Barcelona同期的Intel Nehalem架构。它的一级Cache、二级Cache和三级Cache的大小分别是32K、256K和8M字节。


20ec10d04ae82c4e3596c135edc2fc38d426c27f

与指令和数据Cache类似,一些计算机还实现了特殊的Cache。例如,在流水线中引入分支目标Cache(branch target cache)。分支目标Cache存储与分支有关的信息,例如分支地址和目标地址处的指令操作码。同样,可以在特殊的返回地址Cache中保存子程序返回地址,以减少当返回地址保存在堆栈中时从子程序返回的开销。

1.4.8 写Cache

到目前为止,本章只考虑了对Cache的读访问(访问最频繁的形式)。现在来看看更复杂的写访问。当处理器写数据到Cache时,在Cache和主存储器中的相应块都需要修改,虽然这两个操作不需要同时执行。然而,必须在下一次访问前确保存储器中的数据元素副本已被更新;即在Cache和存储器中的数据元素必须保持一致。

前面已经指出,在Cache和主存储器并行访问的系统中,平均访问时间是tave = htc + (1-h)tm(其中,h为命中率,tc为Cache访问时间,tm为主存储器访问时间)。如果数据不在Cache中,它必须从存储器中取出,并调入Cache和目的寄存器。假定t1为Cache失效时从主存储器中取出一块并将其放入Cache所需的时间,存储器系统的有效平均访问时间是Cache访问时间、存储器访问时间、由于失效导致的重新装载时间(the reloads due to miss)之和:

tave = htc + (1-h)tm + (1-h)t1

上式中新出现的项(1-h)t1为失效后将取出的块放入Cache的额外时间。该表达式可以改写为:

tave = htc + (1-h) (tm + t1)

访问导致失效的元素与将存储器中的块调入Cache可以同时进行。因此(t1 + tm)项应该是max(t1|tm),因为t1>tm,上式可以写成:

tave = htc + (1-h)t1

现在来看看写回策略对该公式的影响。当处理器执行写操作,数据必须被写到Cache和主存储器。在写入Cache的同时也改写主存储器中的数据,这称为写直达(write-through)策略。该策略导致系统变慢,因为写主存储器的时间比写Cache的时间要长。如果下一个操作是读Cache,主存储器可以同时完成更新(即写直达策略并不一定会遭受过多的惩罚)。

相对较少的存储器访问操作为写操作。实际上,写访问约占访存操作的5%~30%。接下来,使用w表示写操作的比例(0

tave = htc + (1-h) (1-w)t1 + (1-h)wtm

其中:t1为Cache失效时重新装载所需的时间(这里假设采用不按写分配(no-write-allocate)策略,即写失效时数据不调入Cache)。

(1-h) (1-w)t1这项代表读失效时重新加载Cache所需的时间,而(1-h)wtm表示写失效时写入存储器所需的时间。由于处理器可以在更新主存储器时继续完成另一个操作,(1-h)wtm这一项往往可以忽略,这是因为主存储器有时间按照写直达方式完成两个连续的写操作。由于假定计算机在写失效时不更新Cache,故该公式不包括写失效时将数据载入Cache的情况。

Cache的性能可以通过写缓冲(write buffer)来改进,它保存了等待写入存储器的数据。典型的写缓冲保存4个地址/数据对。当然,必须保证处理器要访问的数据刚被更新、不在存储器而在缓冲区中,此时,处理器可以访问缓冲区。一种解决方案是在执行读操作之前允许写缓冲完成存储器更新。

另一种修改存储器的策略被称为写回(write-back)。在具有写回策略的Cache系统中,向主存储器的写操作只有在Cache块被替换时才会发生,即对Cache的写操作并不会每次都导致对主存储器的更新。只有在某块由于读失效而被替换出去时才将该块写回存储器。因此上式可以写为:

``tave = htc + (1-h) (1-w)t1 + (1-h) (1-w)t1

  = htc + 2(1-h) (1-w)t1``

注意出现了两个(1-h) (1-w)t1,这是因为读失效导致被替换的块写回存储器,同时新的块被调入Cache。

Cache中的每一块都有一个标志来描述当前块的状态。例如,每个块都有一个脏(dirty)位来表示它调入Cache后是否被修改过。如果该块没有被修改,在其被替换出Cache时就不需要写回存储器。具有这种写回策略Cache的平均访问时间由下式给出:

tave = htc + (1-h) (1-w)t1 + (1-h) pwwt1
其中,pw为块需要被写回主存储器的概率。

图1-25给出了具有写回策略Cache的存储器系统的决策树。该图描述了在读失效时如何修改Cache以及块被修改后如何写回。发生写失效时,Cache中的块被写回,并将新的块装入Cache。这些参数导致的平均访问时间为:

tave = htc + (1-h) (1-w) (1-pw) t1 + (1-h) (1-w) pw·2t1 + (1-h) w·2t1


d10452b936cd7662283440b13431678470c20ece

上面给出了不同Cache策略下系统平均访问时间的表达式。这些表达式都是近似的,真实系统的行为将取决于其具体实现。


f5ada8e2c3a522bef1cd31d8dc32dbf40e97c522


4ece1ca1c15ae3a58e0bddfc61c10cd9a9cb9282

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: