cache一致性问题和解决方法

cache一致性问题和解决方法作者 辽宁工程技术大学摘要 高速缓冲存储器一致性问题是指高速缓冲存储器中的数据必须与内存中的数据保持同步(一致) 。多核处理器将一个以上的计算内核集成在一个处理器中，通过多个核心的并行计算技术，增强处理器计算性能。单片多处理器结构(CMPChipMultiprocessor)又是该领域中备受关注的问题。本文简要论述了CMP的多级Cache存储结构，多级结构引起了Cache一致性问题，一致性协议的选取对CMP系统的性能有重要影响。使用何种Cache一致性模型以及它的设计方案是本文重点研究的内容。关键词：CMP；Cache一致性；存储器；协议；替换策略Cacheconsistencyproblem and solving methodAbstract Cacheconsistencyrefers tothe data in the cache memorymust be synchronized withthe data in memory(the same).Multicore processor was the integration of multiple computing cores on a single processoL which improved processor computing ability through the parallelcomputing Technology of multi-coreprocessorsSingle chip multi-processorarchitecture(CMP-ChipMulfiprocessor)was hot spots in this areaThe CMPmulti-level Cache storage structure was briefly discussed in this paper,which led to Cache coherence problem，the selection of consistency protocol had a major impact on the performance of the CMP systemThe selection of model of theCache Coherence and methods of its design will have a significant impact ofoverall design and development of CMP Key words：CMPCache;consistency;memory;protocol;replacement strategy1引言在过去的二十年中，计算机处理器设计工艺和处理器体系结构发展迅速，计算机也能够完成所赋予它的大部分任务。因此，在各种领域得到迅速和广泛的应用。同时，广泛的应用也带来了对高性能和低功耗处理器的强劲需求。而以往通过在单核处理器中集成更多的晶体管，提升处理器频率的方法，随着摩尔定律和处理器功耗的畸形不对称，使得高频处理器将会带来以往无法预计的功耗问题。多核处理器技术的出现解决了上述问题。2 国内外发展现状21 CMP体系结构研究现状近年来，很多大学以及研究机构在从事CMP的研究，一些著名大学及研究机构已经有相当深入的工作，其中比较有影响的有国外的Standford大学、MIT等，国内的清华大学、国防科技大学在CMP研究方面也取得了一定的研究成果。Standford大学研究的Hydra片上多处理器集成了4个MIPSR 3000处理器核心，每个微处理器核心具有私有的指令Cache和一级数据Cache，所有的处理器核心共享一个片上二级Cache进行通信和共享数据。Hydra CMP还支持线程级猜测执行，可以将程序段并行化，让多个线程来执行这段程序。Hydra综合了共享Cache多处理器系统结构、革新性的同步机制、高级集成电路技术和并行编译技术，即使在执行顺序应用程序时，Hydra CMP能够获得比宽发射超标量微处理器更好的性能。MIT的MMachine片上集成了三个微处理器核心，它们通过交叉开关进行快速的寄存器级间的通信。程序在MMachine上通过寄存器间的快速通信以及同步机制来确保程序的细粒度并行，并且以一种极细粒度的机制来实现线程的并行性。清华大学微处理器和SoC研究中心从2003年开始着手进行CMP的调研工作，于2005年年初基本完成了Thump CMP模拟器的设计工作。ThumpCMP采用了清华大学自主研制的支持MIPS指令集的32位微处理器Thumpl07作为处理器核心，目前的Thump CMP模拟器集成了两个Thumpl07内核，每个内核具有独立的一级Cache，两个内核共享一个二级Cache。国防科技大学提出一种单芯片多处理器体系结构模型珙享多端口数据Cache结构模型，片上集成P个处理器核，每个处理器核有私有的指令Cache，所有的处理器核通过交叉开关共享一个具有q个访问端口的一级数据。除了上述一些大学和研究机构，商业应用中各大厂商都在陆续推出各自的片内多处理器产品。2006年，IBM公司公布了Power 6处理器的部分结构设计与性能参数。Power 6处理器包含两个处理器内核，每个处理器内核支持两个线程。Power6处理器的每个内核有一个私有的8路组相联，64KB的一级数据Cache，一个4MB的二级Cache。Power 6中的私有二级缓存之间可通过高速链路进行数据交换，而无需通过速度相对较慢的三级缓存交换。Power 6采用65nm的SOl工艺，10层金属板，芯片面积为344砌。SUN公司在2005年推出的UltraSPARC T1(开发代号“Niagara”)处理器，主要定位于大规模网络应用服务器市场。Niagara包含8个处理器内核，每个处理器内核支持4个线程。2007年Sun公司推出了二代CMP处理器UltraSPARC T2(开发代号“Niagara 2”1，Niagara 2由8个UltraSPARC内核构成，每个UltraSPARC内核可支持8路多线程，UltraSPARC内核在每个线程的一级指令Cache后设立了指令缓冲区，还增加了一个新的流水级，专门用来选择就绪执行线程。并且，Niagara 2还包含一个浮点运算单元，一级Cache采用8路组相联结构。Niagara 2中所有的处理器内核共享4MB的二级Cache，二级Cache行长度为64字节，采用16路组相联结构、写回和写分配策略设计。由于UltraSPARC T1的4存储体结构在64线程下将会带来15的性能损失，所以二级Cache分为8个分叉存取模块嘲。2.2 Cache一致性协议相关研究 在个允许缓冲共享数据的系统中，同一主存单元的数据可能在多个Cache中都有备份。Cache一致性研究的主要内容就是怎样才能更加有效的维护同一主存单元的多个数据备份的一致性。即如何让多个数据备份保持最新的数据，从而避免由多个Cache带来的数据不同步问题。常见的Cache一致性协议分为总线监听协议和目录协议两种。总线监听协议使系统中所有处理器都能检测到存储器J下在进行的事务活动。所有处理器监视总线上的活动后，根据总线上广播的命令做出相应的操作。如果总线事务操作破坏了本地Cache中数据的一致性状态，那么Cache控制器就应采取相应的动作无效或更新本地Cache中的拷贝。在总线监听协议设计中，主要有两种策略可供选择：1是写通过法(WriteThrough)，还是写回法(Write Back)；2是写无效(Write Invalidate)，还是写更新(Write Update)。目前，广泛使用的写无效协议有MSI、MESI等；广泛使用的写更新有Dragon掣71。在总线监听协议中，虽然总线本身是一种廉价而有效的广播工具，但它是一种独占性资源，可伸缩性有限，而且总线延迟随处理器数目的增加而增加，与总线长度仲裁和总线阻抗等因素有密切关系。当处理器个数增加时，一般不用总线结构，而采用多级互连网络。可扩展的CMP系统用多级网络实现处理器互连或用点对点的短线直接地实现处理器互连。与采用总线连接的情况不同，这些网络的频宽随系统中处理器数目的增加而增加，这类系统常采用目录协议。1976年，Tang提出采用集中式目录方式，用一个中心目录存放所有Cache目录的副本，它能提供为保证一致性所需要的所有信息。它的不足之处是容量非常大，必须采用联想方法来检查，冲突多，检索时间偏长。1978年，Censier和Feautrier提出采用分布式目录的协议，与集中式目录不同的是，由每个存储模块维护各自的目录，目录用来记录每个存储块的当前信息。当前信息指明哪些Cache有该存储块的副本。与总线监听方式相比，目录实现方法中采取“以空间换取时间”的策略，虽然减少了访问次数，但增加了目录存储器，占用了大量的存储空间。3 Cache存储器3.1 Cache存储器的结构与原理311基本结构 Cache由Cache存储体、地址映象变换机构、Cache替换机构几大模块组成。在Cache中把Cache和主存机械地等分成相同大小的块(或行)。每一块由若干个字(或字节)组成。每当给出一个主存地址进行访存时，都必须通过主存Cache地址映象机构判定该访问字所在的块是否己在Cache中。如果在Cache中(Cache命中)，则经地址映象变换机构将主存地址变换成Cache地址去访Cache，这时Cache与CPU之间进行单字宽信息的交往；如果不在Cache中(Cache未命中)，则产生Cache失效，这时就需要从访主存的通路中把包含该字的一块信息通过多字宽通路调入Cache，同时将被访问字直接从单字宽通路送往CPU。如果Cache中已装不进了，即发生块冲突，就需要按所选择的替换算法将该块替换进Cache，并修改地址映象表中有关的地址映象关系和修改Cache各块使用状态标志等信息312工作原理 Cache的工作原理是基于程序访问的局部性原理。在分析大量典型程序运行情况后，得到这样的结论：在一个较短的时间哈尔滨工程大学硕+学位论文间隔内，由程序产生的地址常集中在存储器逻辑地址空间的小部分范围内。指令地址的分布本来就是连续的，再加上循环程序段和子程序段要反复执行多次，因此，对这些地址的访问就自然地具有时间上集中分布的倾向。在指令分布中这种集中倾向并不明显，但对数组的存储和访问以及工作单元的选择都可以使存储器地址相对集中。这种对局部范围的存储器地址访问频繁，而对此范围以外的地址则很少访问的现象，就称为程序访问的局部性。图31 Cache存储器的基本结构基于程序的局部性原理，在介于主存和CPU之间设置高速小容量存储器，称作Cache存储器，把正在执行的指令地址附近的部分指令或数据从主存调入到这个存储器中，供CPU在一段时间内访问，这对加快程序的运行速度有很大的作用。CMP系统正是依据此原理，不断地将与当前指令集相关联的一个小的后继指令集从主存读到Cache，然后再与CPU之间进行高速传送，从而达到速度匹配。3.2 Cache存储器的算法与分析321技术分析1读取顺序CPU要读取数据时，首先在Cache中查找，如果找到就立即读取并送给CPU处理；如果没有找到，就用相对慢的速度从主存中读取并送给CPU处理，同时把这个数据所在的数据块调入Cache中，可以使得以后对整块数据的读取都从Cache中进行，不必再调用主存2缓存分Cache通常分为一级高速缓存L1和二级高速缓存L2。L1Cache是集成在CPU中的，被称为片内Cache。在L1Cache中还分指令Cache(I-Cache)和数据Cache(DCache)。它们分别用来存放指令和执行这些指令的数据，而且CPU可以同时访问这两个Cache，减少了争用Cache所造成的延时冲突，提高了处理器性能。早期的L2Cache并不是集成在CPU中，而是在主板上或与CPU集成在同一块电路板上，因此也被称为片外Cache。随着工艺的提高，L2Cache被集成在CPU内核中，以相同于主频的速度工作，L2Cache与L1Cache在性能上达到平等，得到更高的传输速度。L2Cache只用来存储数据，没有数据Cache和指令Cache之分。在CPU核心不变的情况下，增加L2Cache的容量能使性能得到很大的提升，可见L2Cache的重要性。现在CPU的L1Cache与L2Cache的区别仅在于读取顺序。3命中率CPU访问Cache并得到所需数据时称为命中，当Cache中不存在CPU所需的数据时称为未命中，此时CPU访问主存。从理论上讲，在一个拥有二级Cache的CPU中，LICache的命中率为80。也就是说，CPU从L1Cache中找到的有用数据占数据总量的80，剩下的20从L2Cache读取。由于不能准确预测将要执行的数据，L2Cache的命中率也在80左右，因此从L2Cache读到有用的数据占总数据的16。在一些高端领域的CPU中，存在L3Cache，它是为读取L2Cache后未命中的数据设计的一种Cache，在拥有L3Cache的CPU中，约5的数据需要从主存中读取，这进一步提高了CPU的效率。为了确保CPU访问时有较高的命中率，Cache中的内容应该按一定的算法替换。322替换策略当一个最新的主存块要拷贝到Cache，而可以存放此块的行都被其它主存块占满时，由于要求Cache中应尽量保存最新的数据，就要产生替换。采用替主要少的问一次该行的计数器增1。当需要替换时，对这些特定行的计数值进行比较，将计数最小的行换出，同时将这些特定行的计数器都清零。将计数比较的周期限定在对这些特定行两次替换之间的间隔期间。LFU算法的不足是这段期间访问情况不能严格反映近期访问情况。例如特定行中的A、B两行，A行在前段时间多次被访问而后段时间未被访问但总计数值很大，B行是前段时间不常用而后一段时间却正被频繁访问，但可能由于总计数值小于A行而被LFU算法换出了。2近期最少使用算法LRU(Least RecentlyUsed)算法是将近期内长时间未被访问过的行替换出。为此每行同样设置一个计数器，但它们是Cache每命中一次，命中行计数器清零，其它各行计数器增1，因此它是未访问次数的计数器。当需要替换时，比较各特定行的计数值，将计数值最大的行换出。这种算法显然保护了刚拷贝进新数据的行，符合Cache工作原理，因而使Cache有较高的命中率。Pentium片内的数据Cache采用的就是这种简单的LRU替换策略。3随机替换随机替换(Random Replacement)策略指随机的选取特定的行位置中的一行换出即可。这种策略以硬件实现最容易，而且速度也比前两种策略快。缺点是随意换出的数据很可能马上又要用，从而增加了映射次数，降低了命中率和Cache的工作效率。323写策略Cache的内容是部分主存内容的副本，应该与主存内容相同。而CPU对Cache的写操作更新了Cache内容，为了与主存内容保持一致有两种写操作方法可以采用，统称为写策略。1写回法使用写回法策略时，CPU写命中Cache时，只更新Cache的内容不同时写入主存，只有此行被替换时才写入主存。这种策略使Cache在CPU和主存之间的读或写访问上都起到高速缓存作用。对一个Cache行的多次写命中都在Cache中快速完成更新，只是被替换时才写回速度较慢的主存，减少了访问主存的次数从而提高了效率。Cache写未命中时，写回法的处理是先在Cache中为包含待写副本的主存块再分配一行，将此块整个拷贝到Cache后对其进行修改，因为以后对此块的多次读或写访问的可能性很大。拷贝主存块时虽已读访问到主存，但此时并不对主存块更新。因为换出的Cache很可能此期间要写回主存，为避免此过程耗时太长，写未命中时将新块读入主存后，只在Cache中进行写更新。统一地将主存写更新操作留待换出时进行。可见，这种写Cache与写主存分开进行方法明显减少写主存次数，但写回法也带来了Cache与主存严重的不一致性。2写通过法写通过法是当Cache写命中时，Cache与主存同时发生写更新。这种策略显然较好地维护了Cache与主存的内容一致性，但是还存在一定的问题。例如：在CMP系统中各CPU都有私有的Cache，一个主存块在多个Cac中都有一份副本的情况下，某个CPU以写通过法来更新它的Cache和主存时，其它Cache中的原副本就过时了。当Cache写未命中时，直接向主存写入，但此时是否将修改过的主存块拷贝到Cache中，写通过法却有两种选择。一种是取来并且在Cache中为它分配一个行位雹，称为WTWA法(writethroughwithwriteallocate)。另一种是不取称为WTNWA法。前一种方法保持了Cache主存的一致性，但操作复杂，而后一种方法操作简单，但命中率降低，主存的修改块只有在发生读未命中导致对Cache进行替换时，才有可能映射到Cache中。这种策略的优点是保持主存与Cache的一致性，缺点是增加数据传送量，并且写存储器要花费较长时间。3.3 一致性问题331一致性问题的几种常见原因产生不一致性的原因有三种：1共享可写数据引起的不一致；2进程迁移引起的不一致；3绕过Cache的IO操作引起的不一致。下面分别讨论产生不一致性的各种可能的情况。1共享可写数据引起的不一致。如果处理器P1将一个新的数据Y 7写入Cache中，如果采用写通过策略立即更新主存，在这种情况下，两个Cache中的两份副本Y与Y就不一致了；如果采用写回策略，只有当Cache中修改的数据被替换或变成无效时，主存的内容才被更新，这样也会产生不一致性。2进程迁移引起的不一致。如果采用写通过策略，处理器P1修改变量为Y7，同时更新主存中变量值为Y，包含共享变量的进程从处理器P1迁移到处理器P2时，P2中的变量值仍为Y，也会出现不一致性；如果采用写回策略，进程将处理器P1的私有Cache中变量值修改为Y，进程从处理器P1迁移到处理器P2时，由于采用写回策略，则处理器P2将从主存中获得变量值，仍为Y，则出现不一致性。3绕过Cache的IO操作引起的不一致性。当IO处理器将一个新的数据Y写入主存时，绕过采用写通过策略的Cache，则在C1和主存之间产生了不一致性。当绕过Cache直接从主存输出数据时，采用写回策略的Cache也会产生不一致性。例如，以DMA方式传送数据，DMA控制器直接对存储器进行操作(读或写)，但此时各个Cache中可能有相应数据的副本，就会造成存储器与Cache之间的不一致性，对于进程迁移引起的Cache不一致，可以通过禁止进程迁移的方法来解决。2写更新任一个处理器写它的私有Cache时，通过总线把新的数据块广播给含该数据块的所有其他Cache同时改写其他所有的副本。对于写通过，它也更新主存中的副本。对于写回，对存储器中副本的更新延迟到这个Cache被置换的时刻。332现有协议分析CMP系统中常用的Cache一致性协议可分为监听一致性协议和目录一致性协议两大类。1监听协议监听协议使用共享总线连接多个处理器内核的私有Cache和主存，共享总线保证所有处理器内核的数据请求串行执行。任何处理器发出的数据请求将被广播到所有处理器内核结点，所有处理器内核的Cache控制器都时刻监视着总线。如果收到读请求，数据所有者将把有效数据返回给发出此请求的处理器内核；如果收到写请求，拥有有效副本的处理器内核便无效或更新本处理器上的数据，数据所有者将把有效数据返回到发出此请求的处理器内核。数据所有者可能是处理器内核，也可能是主存。下面介绍三种总线监听协议，分别是MSI、MESI和Dragon协议。其中，MESI是MSI的扩展协议(1)MSI和MESI协议由于Cache本身的特点，对Cache的访问是以Cache行为单位进行，一个Cache行通常为32或64字节，统计结果表明这样大小的C