单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,什么是,cache,Cache又叫高速缓冲存储器，位于CPU与内存之间，是一种特殊的存储器子系统。,目前比较常见的是两极cache结构，即cache系统由一级高速缓存L1 cache和二级高速缓存L2 cache组成，L1 cache通常又分为数据cache（I-Cache）和指令cache（D-Cache），它们分别用来存放数据和执行这些数据的指令。,两极cache相比较而言，L1 cache的容量小，但数据存取速度较快，L2 cache的容量大，但数据存取速度较慢。部分系统中也存在三级cache的结构。,Cache,的作用是什么,Cache,的作用就是为了提高,CPU,对存储器的访问速度。,电脑的内存是以系统总线的时钟频率工作的，这个频率通常也就是,CPU,的外频。但是，,CPU,的工作频率,(,主频,),是外频与倍频因子的乘积。这样一来，内存的工作频率就远低于,CPU,的工作频率了。这样造成的直接结果是：,CPU,在执行完一条指令后，常常需要“等待”一些时间才能再次访问内存，极大降了,CPU,工作效率。在这样一种情况下，,cache,就应运而生了。,指令地址,96,loop:ADD r2,r1,r1,100,SUBI r3,r3,#1,104,BNEZ r3,loop,108,112,典型的内存访问模式,Cache,的工作原理,CPU运行程序是一条指令一条指令地执行的，而且指令地址往往是连续的，意思就是说CPU在访问内存时，在较短的一段时间内往往集中于某个局部，这时候可能会碰到一些需要反复调用的子程序。系统在工作时，把这些活跃的子程序存入比主存快得多的cache 中。,CPU在访问内存时，首先判断所要访问的内容是否在cache中，如果在，则称为命中（hit），此时CPU直接从cache中调用该内容；否则称为未命中（miss），CPU会通过cache对主存中的相应内容进行操作。,Cache,的地址映射方式,Cache,与主存之间可以采取的地址映射方式有以下三种：,全相联映射方式,直接相联映射方式,组组相联映射方式,全相联方式,地址映射规则：主存的任意一块可以映射到,cache,中的任意一块,(1),主存与,cache,分成相同大小的数据块。,(2),主存的某一数据块可以装入,cache,的任意一块空间中。,优点：命中率比较高，,cache,存储空间利用率高。,缺点：访问相关存储器时，每次都要与全部内容比较，速度低，成本高，因而应用少。,直接相联方式,地址映射规则：主存储器中一块只能映射到,cache,的一个特定的块中。,(1),主存与,cache,分成相同大小的数据块。,(2),主存容量应是,cache,容量的整数倍，将主存空间按,cache,的容量分成区，主存中每一区的块数与,cache,的总块数相等。,(3),主存中某区的一块存入,cache,时只能存入缓存中块号相同的位置。,优点：地址映射方式简单，数据访问时，只需检查区号是否相等即可，因而可以得到比较快的访问速度，硬件设备简单。,缺点：替换操作频繁，命中率比较低。,组相联映射方式,地址映射规则：,(1),主存和,cache,按同样大小划分成块。,(2),主存和,cache,按同样大小划分成组。,(3),主存容量是,cache,容量的整数倍，将主存空间按,cache,区的大小分成区，主存中每一区的组数与,cache,的组数相同。,(4),当主存的数据调入,cache,时，主存与,cache,的组号应相等，也就是各区中的某一块只能存入,cache,的同组号的空间内，但组内各块地址之间则可以任意存放，即从主存的组到,cache,的组之间采用直接映射方式；在两个对应的组内部采用全相联映射方式。,优点：块的冲突概率比较低，块的利用率大幅度提高，块失效率明显降低。缺点：实现难度和造价要比直接映射方式高。,块,:,块是,cache,与主存的传输单位。,路（,way,）,:,路是组相联映射方式的,cache,结构中的基本存储单位，每一路存储一个块的数据。,组（,entry,）,:,组是组相联映射方式的,cache,对块进行管理的单位。,区（,tag,）,:,块的地址对应的主存储器中的区。,块内偏移地址（,offset,）,:,用来标示块内一个字节的地址。,组相联映射方式下主存储器的地址空间由，区，组和块内偏移地址组成。,组相联映射方式下,cache,的内部结构。,Cache,的替换算法,Cache,可以采用的替换算法主要有以下几种：,先入后出,(FILO),算法,随机替换,(RAND),算法,先入先出,(FIFO),算法,近期最少使用,(LRU),算法,随机(RAND)法是随机地确定替换的存储块。设置一个随机数产生器，依据所产生的随机数，确定替换块。这种方法简单、易于实现，但命中率比较低。,先进先出(FIFO)法是选择那个最先调入的那个块进行替换。当最先调入并被多次命中的块，很可能被优先替换，因而不符合局部性规律。这种方法的命中率比随机法好些，但还不满足要求。,近期最少使用(LRU)法是依据各块使用的情况，总是选择那个最近最少使用的块被替换。这种方法比较好地反映了程序局部性规律，命中率最高。,如何提高,cache,的性能,提高,cache,的性能也就是要降低主存的平均存取时间,主存平均存取时间,=,命中时间,+,未命中率*未命中惩罚,提高,cache,的性能有以下三种方法：减少命中时间，减少未命中率，减少未命中惩罚。,影响命中率的硬件因素主要有以下四点：,Cache,的容量。,Cache,与主存储器交换信息的单位量（,cache line size,）。,Cache,的组织方式,Cache,的替换算法,代码段,A,for(i=0;i1024;i+),for(j=0;j4;j+),sum+=xij,代码段,B,for(j=0;j4;j+),for(i=0;i1024;i+),sum+=xij,通过优化代码提高cache命中率,对数组,int x10244,进行求和,代码段,A,：,对于数组元素,xi0,（,i=01024,）的访问是,miss,的，但对于,xi1,，,xi2,，,xi3,的访问是,hit,的，因此,miss,的总次数为,1024,次。,代码段,B,：,对于数组元素,xi0,，,xi1,，,xi2,，,xi3,（,i=01024,）,的访问都是,miss,的，他们被,xi+40,，,xi+41,，,xi+42,，,xi+43,所替换，因此,miss,的总次数为,4096,次。,当需要对大量数据访问的时候，一定要注意对内存的访问要尽量是连续而且循环内层的访问接近cache的块大小，以提高cache的命中率，从而提高程序的运行效率。,Cache,的一致性问题,在采用,cache,的系统中，同样一个数据可能既存在于,cache,中，也存在于主存中，两者数据相同则具有一致性，数据不相同就叫做不一致。,Cache,主要有两种写策略写直达法（,write through,）和写回法（,write back,）,写直达法（,write through,）,方法：在对,cache,进行写操作的同时，也将内容写到主存中。,优点：可靠性较高，操作过程比较简单。,缺点：写操作速度得不到改善，与写主存的速度相同。,写回法（,write back,）,方法：在,CPU,执行写操作时，只写入,cache,，不写入主存。,优点：速度较高。,缺点：可靠性较差，控制操作比较复杂。,对于多个主设备的共享存储总线系统，如带有,DMA,的系统，或者多处理器系统，由于其他的主设备也可以改变主存的内容，而这种改变是,cache,无法得知的，因此必须对,cache,的一致性问题进行处理。,可以将主存中的一块地址空间设置为非,cache,访问，,CPU,对这部分地址空间进行直接访问，不经过,cache,处理，对这部分地址空间的访问的效率会变低。,如果要保证更改的数据写入存储器中，则选择,WRITE-THROUGH,方式或者使用,FLUSH,指令，将,cache,内容刷新到主存中。,如果要保证读出的内容就是主存中的内容，则在读之前，先将存储此数据的,cache line,无效，即运行,INVALID,指令。,