cache相关的国内外研究热点Word格式文档下载.docx
《cache相关的国内外研究热点Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《cache相关的国内外研究热点Word格式文档下载.docx（27页珍藏版）》请在冰点文库上搜索。
RingBasedProtocols） 11
2.2.自适应的监听 12
2.3.灵活可变的的监听算法（AlgorithmsforFlexibleSnooping） 14
第3章 互联线对cache性能的影响 16
3.1.互联线相关的cache一致性协议 16
3.2.大型NUCA体系cache的互联线设计 16
第4章 Cache一致性模型和存储器流模型两种存储模型的比较 19
4.1.cache一致性（IncoherentCache-based）模型 19
4.2.流模型（streamMemoryModal） 20
4.3.定性比较 20
4.4.CMP体系架构 21
4.5.评估方法 22
4.6.比较总结 24
个人心得 25
参考文献 26
第1章 新的Cache插入原则
.1. LRU的缺陷
在cache数据插入原则当中，LRU是最好的选择吗？
我之前一直认为LRU是最接近理想状况一直的替换原则，但是事实并非如此。
LRU替换原则存在缺陷。
首先，如果只采用LRU，当需要经常被cache用到的数据大小比cache的size大时，那么采取LRU替换原则会产生thrashing。
这是因为替换前后的数据有一定的相关性，LRU的替换原则是将新数据放到MRU上。
这样一来，可能被替换出去的数据可能马上又会被用到，而很多没有被替换的LRU位置上的数据实际上并不可能总是被用到。
所以cache的访问需要再次accessmemory。
在有大量大块数据需要被替换的情况下，大概有60%的时间花费在L2cache载入数据这个过程中。
如果在正被用作工作的存储空间比cache的可用空间要大，那么留一些活动集和的
cache数据是有利于cache命中的。
MonuddinJ.Q等[1]对于高性能cache提出一种自适应的
cache替换算法。
他们的研究在插入策略上改动了一点点，但是能有效提高需要大量数据存储替换的任务性能。
.2. LIP数据插入原则
数据在插入到MRU位置上时，会被优先得到访问，因为数据遍历是从MRU到LRU
这样的顺序进行的。
对于时间局部性较高的数据而言，如果数据工作集的数据量比可用
cache小的时候，将数据插入到MRU位置上，访问的命中率更高。
但是数据如果工作集数据量要比可用cache的大小大很多时，就会产生thrashing。
因为很有可能刚刚替换进去的数据马上又被替换出来了。
因此，他们提出在LIP（LRUInsertionPolicy）数据插入原则。
过程很简单，只有两个步骤：
（1）如果在经常被cache用到的数据大小比cache的size大时，将所有的新数据放到
LRU位置上，而不是LRU所采用的MRU位置上。
（2）在LRU位置上的数据被处理器访问到之后，这些数据会被迁移到MRU位置上。
如此一来，数据先被放到LRU位置上，处理器开始访问，由于LRU上的数据是处理器正需要的数据，所以马上会被放到MRU位置上，如此一来，无形中扩大了可用cache的大小。
当数据并未被访问到的时候，继续向存储器要数据，但是这个时候并不是全部将需要的数据给替换，根据替换原则，LRU位置上的数据会留下一些fraction，以利于访问命中。
LIP插入原则相对与LRU而言，提高了需要大量数据访问的任务的性能，但是对于需要数据量比可用cache空间小的时候，并没有优势，因为数据访问过程中访问LRU位置上数据的代价要比MRU位置上数据代价大。
因为本身它是与LRU替换原则想背驰的。
.3. BIP插入原则
为了能让替换更有效，采取了BIP（BimodalInsertionPolicy），（LIP经过固定数量的
miss后，新进来的数据被置于MRU的位置上）。
这是因为LIP在处理循环引用模式的miss
hit的数据时，性能并不好。
循环引用数据会引起数据替换的死循环。
BIP控制了一个参数，叫做bimodalthrottleparameter，ε，ε控制了新进来的数据被替换到MRU位置上的百分比。
当ε=0的时候，就是LIP；
ε=1时，就是LRU。
通过改变ε，能够使BIP适应工作集合的改变，并做到thrashing保护。
为了分析LIP和BIP，通过模型分析。
若ai表示cache的数据地址。
（a1，a2,…aT）表示对a1，a2,…aT数据的一次数据引用访问，时序序列（a1，a2,…aT）N表示对该数据引用访问N次。
在（a1，a2,…aT）N后紧跟数据访问（b1,b2…，bT）N，访问的是一个全相连的的cache，包含的可用空间为K（K<
T）。
假如BIP中的ε很小，并且N>
>
T，N>
K/ε。
表1.1给出了LRU,OPT（理想情况），LIP，BIP的命中率。
表1.1LRU,OPT,LIP,BIP对于例子的命中情况
LRU命中率为0是因为发生了thrashing，而LIP由于不允许第二个序列进入到cache的MRU中，导致了第二个序列的零命中。
对于BIP而言，由于其概率性可允许数据进入到MRU位置，第二个序列访问cache时，经过K/ε失配后，所有的数据都会属于第二个序列。
.4. DIP数据插入策略动态选择机制
DIP（DynamicInsertionPolicy），通过评估LRU和BIP失配的比较，动态地在LRU和
BIP中切换policy的机制。
4.1.GlobalDIP动态策略选择机制
图1.1全局DIP
最直观的方法实现DIP是为数据提供全局的tag目录，数据集为LRU和BIP都维持一个tag，跟踪哪种策略实现得更好。
动态得计算数据集分别用LRU和BIP替换策略的失配，通过因子权重计算后做全局决策。
如图1.1所示。
4.2.DSS动态策略选择机制
全局选择机制需要维持两个tag目录，代价比较大。
M.K.Qureshi[2]等提出通过DSS（DynamicSetSample）可以显著减少硬件消耗代价。
SetSample是指在选择DIP策略时候选择数据的集合。
如图1.2所示，部分数据通过LRU替换策略，部分数据集合通过BIP数据调度策略。
划分给LRU策略的数据集合发生cache失配时，递增PESL的值；
划分给BIP策略的数据集合发生cache失配时，递减PESL的值。
当下一个未知的数据集合到来时，如果PESI=0，那么采用LRU，否则采用BIP。
图1.2DSSDIP
DSS牵涉到一个问题，怎样给两种策略分配数据集合。
数据集合策略分配可以是动态分配，也可以是静态设计时候的分配。
他们的研究中给出了一种分配的办法，初始状态下，将部分数据均匀的分配给各种策略。
比如说，有1024个集合，那么每隔33个集合，
0，33……分配给LRU，每隔31个集合，如1，32……分配给BIP。
我个人觉得这个分配有欠妥当，因为一个数据在未知采用何种分配策略更好，就初始化，并不是一个好提议。
文中提到了动态分配未知的，没有说到如何改变已知的，或者我并未彻底了解这个分配的动态变化过程（文献[1]中有一段对setdueling的数学证明，不是
很明白）。
如果要性能达到最好，数据的替换策略不仅仅是动态选择，更是需要动态改变的。
最后，通过与LRU、BIP等做了性能比较，使用DIP后对于标准测试程序的cache命中率有了大幅度提高。
第2章 Cache一致性协议
目前的cache一致性一般靠两种方式实现：
添加公用的cache-to-cache失配（目录协议）或者需要全序的互联线（传统的基于总线的监听协议）。
在实现低延时的cache一致性的问题上，这两种协议性能都很低。
.1. 符号一致性协议（TokenCoherence）
MMartin等[3]陈述了一种新的一致性框架协议，这个协议能优化一般的cache一致性实例，并潜在得解决速率问题、提高安全性、减少了饥饿。
这个协议称作为符号一致性
（TokenCoherence）协议。
他们中的协议由两部分组成：
精确性底层协议和性能协议。
底
层协议提出了数据块的记号机制，将每个数据块都关联固定数量的记号，处理器只有拥有了特定记号数量下才能进行读写访问；
对于避免饿死，底层协议提供持续性消息；
性能协议提出了短暂性请求，并且满足请求的处理方式。
他们还提出了符号一致性中的一个特殊协议，TokenB协议，能够整合无序多处理器，实现低延时。
通过实验表明，在正常工作量下，他们所提出的新的一致性协议要比传统的监听协议和目录协议做得好。
1.1.一个启发式例子
传统的基于无效性的协议允许一个共享数据能够被一个拥有写权限的处理器和一批拥有读权限的处理器共同访问，当然这些处理器不能对该数据不能同时操作。
当一个处理器需要进行读或者写操作时，先通过在无序低延时的互联线上广播一个操作消息。
但是这个操作消息很有可能不正确，因为网络的拓扑结构和消息路由的顺序原因。
一旦不正确，处理器就会读到较旧的数据。
如图2.1 a所示，P0要对一个数据块进行读和写操作，P1只要进行如操作。
在①时刻，
P0将它的操作请求进行广播，在时刻②，P1捕捉到该请求，并在时刻③返回给P0（假设数
据的有效部分在P1所拥有的存储器上，因为存储器返回请求的时间相对于P1时间要长很多）；
在时刻④，P1将它的读请求发送，并在时刻⑤得到满足；
时刻⑥P0的消息达到存储器，而
在时刻⑦，存储器将数据返回给P0。
此时，P0以为它拥有了写权限，而P1以为有了读权限，但是这是不正确的，导致这个不正确的原因正是消息发送时的无序节点互联。
监听协议对例子问题的解决：
传统的监听协议解决例子所产生的问题都是依赖于全序
互联——虚拟总线——给出的一个全序请求访问。
这个全序访问保证了请求是以相同的顺序发送的。
全序保证了操作的正确执行，如本例中当P1获得数据后，P0发出写请求，将把
P1中的数据无效化，所以保证了一致性访问。
但是互联线的全序将导致更大的延时和更多的消耗。
目录协议对例子问题的解决：
当P1的请求先到达家节点的目录时，存储器提供数据。
当P0的数据后来到达的时候，家节点将无效化消息发送给P1。
P0的请求将在P0的无效化操作完成后得到满足。
但是这个解决方案增加了cache-to-cache关键路径的间接访问，消耗增大了。
图2.1一个启发式例子
符号一致性对例子问题的解决：
底层协议保证了处理器在适当的时候安全地最终获得所需的块。
性能协议保证了共有情况下最快的数据移动请求。
1.2.正确性底层（CorrectnessSubstrate）协议
系统把固定数量的记号和共享内存中的数据块关联。
当系统初始化时，系统将每个块赋了T个符号。
初始状态时，家节点拥有每个块的所有符号。
之后，在处理器的cache中和一致性消息中都有符号。
记号和数据只有在拥有以下四个约束时才能被系统转移：
（1）任何时候，所有块的T个记号都存在于系统中。
（2）一个处理器要写某个块时，必须拥有该块所有的T个记号。
（3）处理器只有在拥有该块的一个记号时才能被读
（4）一个一致性消息中包含一个医学上的记号时，必须包含数据。
（1）保证了底层从不创造或者销毁记号，
（2）和（3）保证了当一个处理器在写该块时，没有其他任何处理器在读该块，（4）保证了有块的记号的处理器，必定拥有该块的有效数据拷贝。
将记号数量可以向传统的一致性状态映射，T块为独占或者M，1~T-1为共享，
0个记号为无效。
由于系统在处理过程当中不设计到协议状态、数据回应、请求应答、互联线顺序和系统层次，安全性当然被做得很好。
有时候当需要知道有没有其他处理器共享数据的block时，并不需要将block的数据也返回，这样能降低数据带宽。
底层允许记号在传送时没有带宽，但是必须有一个拥有该记号的处理器的有效位。
其中在传送给owner记号时，即处理器要拥有该数据的拷贝时，必须有该数据的拷贝。
这样一来，当处理器要读取某个块时，消息中必须有记号和该数据的拷贝；
一致性消息中包含主记号（该处理器要拥有该块的拷贝）时，必须包含数据拷贝。
系统组件（处理器和存储器）维护一个有效位，用来指示是否拥有该数据的拷贝。
记号需要2+|log2T|的位来实现，一个有效位，一个主记号位，log2T位用来表示记号。
1.3.持续性请求
他们也提出使用持续性请求（persistent request）来避免饥饿，具体过程通过以下四个步骤进行：
（1）在一定的时间段内，处理器发现如果可能会产生饥饿时，处理器就会发送一个持续性请求。
（2）底层最多激活每个块的一个一致性请求。
（3）系统节点记住所有的一致性请求，并且开始收集该块的记号（
（1）发送的请求包含的数据块）。
（4）当记号数量充分的时候，实行存储器操作，载入或者存储指令，然后解除该持续性请求。
为了保证饿死的自由度，系统必须实现一种公平的机制来激活持续性请求。
当一个处理器对某个数据的访问发生10次cache失配的时候，激活持续性请求。
持续性请求的实现由一个仲裁状态机（arbiterstatemachine）实现。
每个节点有一个仲裁状态机位于家节点上，当检测到可能出现饿死时，仲裁状态机向所有的节点发送持续性请求。
每个节点维持一个8byte*节点数的表，用于指示那个处理器发送了持续性请求。
当持续性请求到达每个节点时，节点将发送节点锁需要的记号和数据都发送给发送节点，并且在持续性消息解除之前把之后到达的相关记号和数据都发送给该节点，直至持续性请求解除。
解除后，家节点向每个处理器发送解除持续性请求消息，删除每个仲裁表中的该项记录。
图2.2 处理器（a）、存储器（b）、持续性请求仲裁器（c）正确性底层状态。
图中所有的记号是和数据一起发送的。
t代表当前记号数量，T代表所有的记号。
实曲线是对于到来消息的回应，虚曲线是性能协议。
当处理器收到其他处理器冲裁器的持续性消息后进入P状态。
每个处理器也需要记住他自己的持续性请求，这个并未在图中标明。
初始状态用粗边界标明
1.4.性能协议（PerformanceProtocols）
实现高性能协议的一种策略是使用短暂性请求（transientrequests）。
性能协议能发现某
个请求没有满足，因为发送请求者会发现还没有足够的记号。
如果没有满足要求，性能协议可能会重新发送该请求或者什么事情都不做（如果不做，如果超时后，处理器会发送持续性消息）。
性能协议也能特殊化短暂性请求的应答策略。
当一个短暂性请求发送后，可以让底层在获得一个或者多个或者全部符号后进行应答。
一个好的性能协议能够让最多的cache失配最快得发送短暂性协议满足cache操作。
TokenB（Token-Coherence-using-Broadcast）通过三方面对于高带宽无序的互联多处理器实现整合。
（1）处理短暂性请求。
处理器广播短暂性请求，这个在中等数量的多处理器、有充分的带宽的系统中工作很好。
（2）回应短暂性请求。
系统组件回应短暂性请求。
对于不拥有记号的组件（状态I，无效）不回应；
拥有非拥有记号（ownertoken）的组件回应忽视所有的共享请求，但是对于独占请求，返回数据和记号；
拥有所有记号和占有记号（ownertoken）回应所有消息，对于共享消息发送一个记号和数据，对于独占消息发送所有的记号和数据。
（3）重新发送短暂性消息。
当短暂性请求无法满足时，再还没有到达持续性请求发送的时间时，再次发送短暂性消息，发送的时间间隔呈指数递减。
1.6.对符号协议性能评估
他们算法通过SIMICS模拟多处理器平台，运行三种商业常规程序
（OLTP、Apache、SPECjbb），使用多种互联（树形和环形）和其他一致性协议（传统的基于虚拟总线的监听协议、目录协议、Hammer协议）进行性能（延时、带宽、cache大小、其他数据结构大小）评估。
发现在运行时间上、延时时间、防死锁的性能上都有很大提高。
并总结TokenB性能的测试结果如下：
（1）重行处理请求（reissued）和持续请求（persistent）量很少，分别只占3.0%和
0.2%。
（2）TokenB要比传统的监听请求快，因为其允许处理器的无序连接。
（3）TokenB要比目录协议快，因为它避免了目录之间的间接访问
（4）目录协议要比TokenB协议使用更少的带宽，但是这些带宽在通用的互联线实现上是微不足道的。
对于中型系统应用来说，TokenB是一种很好的选择，而Token一致性协议是一个创造性的通用框架。
通过在多处理器中嵌入一个向前过滤环
为了支持监听cache一致性，一个简单低开销的方法在多处理器网络中嵌入一个单向环，并且用这个环来监听消息。
其他消息用网络中的任意一个链接进行传送。
这个网络拓扑结构如果被实现得简单的话，网络上回应（response）的时间将会很长，监听到的消息会很多，或者监听的操作比较麻烦。
KarinStrauss等[4]提出一种自适应的向前过滤监听（AdaptiveForwardingandFilteringofSnoops）算法。
在本算法中，一个接受到监听消息的任意一个节点采取两种行动：
一、将该消息向前向另外一个节点传输，并且处理监听；
二、或者向前传输给另外一个节点，
并且继续监听；
三、只是转发，并不监听。
他们所采用的算法与目前最快的监听算法相比，能耗大概降低了9~17%；
与目前一个有效降低能耗的算法相比，虽然多消耗了3~6%的能耗，但是性能上提高了36~42%。
本算法的优势：
1）只要把环嵌套到原来的拓扑网络中。
2）不需要类似广播总线或者目录结构这样的昂贵硬件。
3）环的一系列属性能够使cache实现一致性。
4）不适合大规模计算机使用，适合中间范围的节点适用，比如8到16个节点。
本算法的主要缺点是：
可能导致长时间的延时而导致多次监听和处理操作。
对于多处理器特别是GHz处理器而言，长时间延时是不能容忍的，轻微的能源消耗操作是不被提倡的。
他们主要做了三个工作：
1.介绍了一组自适应的监听算法，通过在多处理器中嵌入环；
2.分析了该算法的设计空间；
3.验证了这些算法，并且证明了这些算法中某些要比当前的监听算法消耗更大。
RingBasedProtocols）
2.1.1一致性消息的冲裁
Cache一致性协议要求相同地址的数据需要被线性顺序访问。
多处理器必须约定以相同的线性顺序执行。
三种监听协议：
1）通过总线监听：
所有的事务共享一个总线连接。
一个时间周期只能有一个事务使用总线。
如果同时有两个事务访问总线，只有一个成功，另外一个强制等待。
现在的高级实现方法包括：
切割事务总线和多总线。
比如sun的Starfire系统使用了四个快速总线监听消息；
数据传输在另外一个网络上进行。
缺点是只有有限的可测量性，一个周期总线只能支持一个事务，需要全局的仲裁周期，频率对其有直接影响。
2）通过目录结构监听：
所有与存储器相关的事务都直接映射到家目录上，通过目录线性化事务。
3）记号一致性协议：
每个处理器上的数据，无论是在存储器上还是在cache上都直接与N个记号相关，N是处理器的数量。
处理器只能至少得到一个数据的line的记号之后才能对其进行读访问；
只有在得到所有的记号之后，才能对其进行写操作。
这个保证了事务存储器数据的线性化。
当某些事务要得到所有的记号时可能会失败，失败了就需要重试。
缺陷也存在：
一个是失败之后的重试，可能导致事务之间的锁关系。
二是每个line需要token，这些token存储在内存中。
三是当这种处理方法用于CMP类型的多处理器时，需要进行括展。
4）通过嵌入单向环监听：
通过嵌入单向环，处理器在环上传输消息。
当一个处理器处理两个请求时，或者提供一个回复时，会产生冲突，这样的话处理器先处理一个消息，另一个消息被标记为挤压的（squashed），这个消息会被下次马上处理；
当两个处事务指向同一个存储器数据时，冲突会马上会被检测搭配。
2.1.2嵌入环的CMP多处理器
CMP处理器能被任何一种物理网络互联，在下图中，一个CMP处理器中嵌入了逻辑环网络。
为了平衡网络负载，数据传输并不使用逻辑环网络。
图2.3为对一个共享二级存储的
CMP体系结构建立了一个逻辑环。
图2.3CMP体系结构逻辑环的建立
通过MESI一致性协议加强状态。
状态有无效（I）、共享（S）、互斥（E）、修改过
（Dirty（D）。
也加入了全局/本地控制量的共享状态（SG 和SL）和Tag（T）状态。
对于
CMP而言，本地cache的数据读取速度要比非本地cache中读取数据速度快，全局共享和局部共享存在效率差异，所以研究中区分了这两种共享状态。
表2.1给出了各种状态的兼容状态。
表2.1各种状态的兼容状态
X.Shen[5]等提出
升级会员 