注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

易拉罐的博客

心静自然凉

 
 
 

日志

 
 

转 缓存思想——计算机存储器结构、程序的局部性  

2010-05-23 09:54:50|  分类: 存储器 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
        缓存(Cache)是我们经常听说的一个概念,我们很早就听说过Inter最早的赛扬系列是一个P2取消了L2 Cache的版本,最新的CPU有多少多少L1 Cache,多少多少L2 Cache,某某硬盘有多少多少缓存等等。我们也亲自尝试过如果不打开cache或者代码不是放在cache段,数据不是放在cache段,程序的运行速 度会很慢很慢。或者至少被要求检查过,代码跑的慢是不是因为没开cache或者开的不对,没放在cache区。或许你还知道一般来说,OSD Buffer是不能放在cache区的,甚至亲眼看过如果这样做了会有什么样的后果。等等等等,不一而足。
       但是,究竟什么是Cache呢?为什么会有Cache?Cache是如何工作的?理解它又对我们平时写代码有什么帮助呢?这种思想是否也可以应用到我们的设计中去呢?本文以《CSAPP》为参考,逐步探讨以上内容。
       缓存,顾名思义,就是作为缓冲用的存储器。比如CPU要从内存上读一些数据,那么它会先把这些数据缓冲在缓存里,然后再进行读取,这样如果下次再访问同样 的数据,CPU就可以直接从缓存里读,而不需要访问内存了,访问缓存的速度,要比访问内存快的多,那么很显然后面这一步就能节省大量的时间。但另一方面, 这样似乎反而增加了一个中间步骤的消耗,而且一般来说缓存会比内存小的多,那么判断目标数据是否在缓存中,如果不在还要在进行选择覆盖谁,然后再把新数据 读入缓存,这个过程显然复杂而耗时的多。这种分析显然是没有错的,但实际上这些时间相对于真的访问一次内存来说几乎是可以忽略不计的。而且一般来说,我们 访问了一段数据,接下来马上再访问它的可能性会很大,所有大多数时候这种机制是非常有用的。这个一般性,后面我们也会再详细的介绍。当然了,这里以CPU 与内存之间的缓存为例讲解,实际上任何缓存几乎都是符合这样的特征的。
       那么为什么会产生缓存呢?我们知道,优化程序一般来说,会从系统的瓶颈来进行优化,而现代的计算机系统的发展则出现了两个特征:一是越快的存储器,每兆字 节成本越高,而且其发展趋势是这种差异越来越大,二是CPU与主存之间的速度差距逐步扩大。从1980年到2000年,SRAM的访问速度提高了100 倍,但每兆字节成本下降了200倍;比它慢一些的DRAM的访问速度只提高了大约6倍,但每兆字节成本下降了8000倍;更慢的硬盘虽然访问速度提供了大 约11倍,但每兆字节成本下降达50000倍。而同期CPU的速度提高了大概600倍。很明显,在这种情况下,加大更慢的存储器是一个便宜的改善方案,而 使用少量的更快但更贵的存储器作为缓存则可以解决速度上的瓶颈。另一方面,由于CPU和存储器直接的速度的进一步扩大,现代CPU也越来越平凡的使用基于 SRAM的高速缓存以弥补这个差距。早期的计算机存储器层次只有CPU寄存器、主DRAM和磁盘存储器,后来又逐步加入了L1 Cache和L2 Cache就是这种发展趋势的产物。
转 缓存思想——计算机存储器结构、程序的局部性 - 易拉罐bb - 易拉罐的博客
 
       考虑一个一般的计算机系统,其存储器地址有m位,形成M=2^m个不同的地址,它们被缓存到一个C字节大小的缓存中。一般来说,这个缓存混被分成S= 2^s个缓存组,每个组包括E个缓存行,每行能缓存一个B=2^b字节的数据块。另外,每行还需要一个额外的有效位指标该块是否有意义,以及t=m-(b +s)位的标记位,不过这些都是不算到C里的。然后,我们把一个地址从高位到低位,分别标记为t个标记位,s个组索引位,b个块偏移位。于是当拿到一个地 址的时候,我们先取出其中间的s位组索引,确定该地址如果在缓存中,会属于那个缓存组,然后取出其高位的t个标记位,与该组中的E个行的所有的标记位进行 比较,如果匹配且该行的有效位为1,则表示命中,其低b位就是在该行的数据块中的偏移,否则表示不命中。在地址和缓存中,s、b都是按位索引的,不能使缓 存比主存小,而标记位是一对多的关系,一个缓存行,可能有对应不同的标记位,这让缓存可以也必然比主存小(的多)。同时,从软件的角度来看,查找t位标记 时,有一个在E行中遍历的过程,但在CPU这个级别,这个“遍历”都是硬件完成的,所有速度不成问题,当然成本也不低。

转 缓存思想——计算机存储器结构、程序的局部性 - 易拉罐bb - 易拉罐的博客
 
转 缓存思想——计算机存储器结构、程序的局部性 - 易拉罐bb - 易拉罐的博客
 

       也许你会奇怪,为什么要用中间的位来做组索引,而不是高位呢?下图说明了这个问题,如果用高位做组索引,连续的地址会被映射到相同的组中,这样程序发生常 见的连续地址访问操作时,将只有一个组的缓存发挥作用,缓存利用率低,而使用中间为索引,相邻的地址总是被映射到不同的缓存组,利用率明显提高。当然了, 如果地址访问是跳跃的,即空间局部性不好,这种策略反而会使缓存利用率降低,不过一般来说这种机会不大,而这也是我们的程序需要注意的地方,这个后面会讲。
转 缓存思想——计算机存储器结构、程序的局部性 - 易拉罐bb - 易拉罐的博客
 

       在缓存的情况下,读操作过程非常明显,如果缓存中有,就从缓存中读,否则就从存储器中读到缓存,然后返回数据。写操作则稍微复杂一些,一般来说有两种方 式,即直写,马上将数据写到存储器和写回,直到数据块被替换出缓存区时才真正写到存储器,前者实现简单而后者速度会快的多。当写操作不命中时,同样存在两 种方式,写分配,即先加载数据到缓存再写和非写分配,直接写存储器不加载到缓存。通常写操作是一个复杂而私有的问题,不同的硬件有不同的实现,但我们仍建 议在写程序的时候,将硬件看成一个写回写分配的过程。这是硬件发展的趋势,也是与读操作对称的。
       写到这里,我们基本上就可以解释上面提到过的一个问题了,为什么一般来说,我们会把OSD Buffer放到非cache区呢?我们知道在cache区,由于写回机制的存在,当我们更新OSD Buffer时,真正的显存并不是马上更改的,而是有部分数据还在缓存中,存储器里的数据还是旧的。虽然读缓存机制会很好的处理这部分还在缓存中的数据, 使得读出的数据不会出错,但一般来说OSD Buffer由于大量数据频繁的要交换到显示设备上,都会有专门的硬件或者优化机制来完成这个工作,而不幸的是,在有些平台上,这个机制与缓存机制是独立 的,不能协调工作的。
       关于缓存思想对代码的优化有个非常经典的例子,假设数据是块对齐的,并且初始的时候缓存为空,整个缓存只用来处理数组中的数据,我们看下面的代码:
int sumarraycols(char array[M][N]){
    int sum = 0;
    for(int i=0;i<N;i++){
      for(int j=0;j<M;j++){
       sum += array[j][i];
      }
    }
    return sum;
}
       现在假设缓存块大小是4字节,当缓存总大小小于4*M即,缓存组数小于M时(这是很有可能的),我们来看这个访问过程。由于C语言中,二维数组是行优先 的,所有我们访问地址的顺序实际上是:array+0、array+N、array+2*N、array+3*N、……array+1+0、array+ 1+N、array+1+2*N……array+j+i*N。当我们访问array+0时,array+0——array+3会被加载进缓存,然后是 array+N——array+3+N、array+2*N——array+3+2*N …… array+k*N——array+3+k*N …… array+(M-1)*N——array+3+(M-1)*N,此致正好4*M的缓存逛了一圈,由于缓存无法放下4*M的数据,显然在这个过程中,存在 一个k,使得缓存正好被填满,然后在k+1的时候,就会有数据被移除缓存。无论是采用哪种策略,比如最近未使用、先进现出等,由于没有更多的信息,而前面 所有的数据都是对等的,array+0——array+3都最有可能被移除缓存(随机除外,但这个过程太过随机,暂不考虑),然后是是array+N—— array+3+N …… array+(M-1)*N——array+3+(M-1)*N。无论如何,当j转了一圈,回过头来从0开始访问array[0][1]时,这段数据早已 被移除了缓存,然后又是一系列的不命中,而不命中显然会降低程序的运行速度。以上过程虽然有很多理想化的假设,但大的趋势并没有问题,至少我们能说空间局 部性不好的代码,不利于缓存机制工作。
       回过头来,我们将上面代码中的两个for行互换,再分析不难发现,即使只有一个缓存行,新的代码仍能达到3/4的命中率,对于这种情况的缓存来说,这已经是最好的结果了。
       也许你会说我们程序的瓶颈根本不在类似的位置,或者说它根本不需要对性能有如此高的敏感,但是无论如何,像上面的例子,它是几乎没有代价的,不是吗?不过 这样说来,实际上并没有错,但圣经说太阳底下无新事,我们学习一种东西,最重要的,应该还是它的思想,不是吗?而这种缓存的思想对我们的设计是否也会有帮 助呢?举一个例子吧,开发DVB系统时,是否你经常碰到这样的问题,某些数据的发送周期非常长(比如5分钟),于是我们不得不非常小心的处理这个接收的过 程,如果万一我们遗漏了其中哪怕一个最微不足道的section,那么我们不得不再等待一个周期才能完成接收,这是在很多情况下会是大忌,但往往硬件的性 能又不可能达到实时处理的能力。用缓存思想来解释这个问题就有新的思路了,码流上的数据实际上就是一个每兆字节更便宜(不算终端的成本),访问速度却更慢 (一个访问周期甚至需要5分钟)的存储器,如果我们用本地的内存来cache它,局部化的程序不就是给它加速的好办法吗?实际上大多数的驱动也有这个功 能,但我认为还有更特殊化的改进的余地。
  评论这张
 
阅读(376)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017