Advanced Cache
Processors with Shared Memory
A multiprocessor with shared-memory offers multiple cores / processors a single, shared, coherent memory. Should be called shared-address multiprocessor, because all processors share single physical address space.
光看一个处理器,对于它来说,内存访问依然是性能的瓶颈。因此对于每一个处理器来说,最好,现实中也是,有自己的private cache来减少对于内存的demand次数。对于每一个处理器本身来说,只有它们的private cache miss了之后,才会access shared common memory。
考虑这样的一个情况:处理器1访问地址A,cache1中存了地址A的值;处理器2也访问了地址A,cache2中也存了地址A的值。这两个cache中的值是一样的。但是如果再之后,处理器1在地址A写入了一个新值,且因为write through,cache中存的也是新值。这样就发生了cache incoherence。
Cache Coherence
New cache miss type: coherence miss (a.k.a. communication miss), caused by writes to shared data made by other processors.
在上述发生的情况,加入再之后处理器2访问地址A,那么将不会访问内存中的地址A的新值,而是直接看cache2中的旧值了。这就不妙了。
那么什么是一致,coherent? 任何一次读取操作都必须返回该数据项最近写入的值。多个处理器共享内存,各自拥有本地缓存,如果不加控制,就会出现缓存中的数据彼此不一致的情况。解决思路是什么?当某个处理器发生缓存未命中(miss)或进行写操作时,要通过总线(Bus)通知其他处理器。通知的逻辑:
- 如果是“读取”操作(read):多个处理器可以同时拥有相同副本(不会有冲突)。
- 如果是“写入”操作(write):必须让其他缓存中的副本失效(invalidate),确保一致性。
缓存一致性协议(Cache Coherence Protocol):每个缓存控制器都会“监听(snoop)”总线上发生的写操作,总线是广播媒介(broadcast medium),所有处理器都能看到总线上的消息。
总结的工作流程如下:某处理器写数据 → 发出写请求到总线。其他缓存控制器监听到这个写请求。如果某控制器发现自己也有这块缓存数据的副本:立即让它失效(invalidate),以防使用旧数据。更详细的来说,这种解决方式叫做:Snoopy Protocols
Snoopy Cache
核心思想:缓存要“观察”(snoop)总线上其它处理器的内存事务;监听后要“做出正确的反应”(do the right thing):比如:监听到写操作,就使自己缓存的对应块失效。Snoopy Cache 是双端口的(dual-ported):一个端口用于处理器正常读写,一个端口用于监听总线事务。
一般来说,在L2 cache上进行优化比较好。因为L1比较小,而L2比较大。而且它们都在chip上。Furthermore,在L1的数据必定在L2中也有。因此如果L2中的缓冲块被失效了,那么要确保L1中的也失效。更重要的是,在传输信息的bandwidth角度上,L1的位宽十分珍贵,让L2来允出位宽来监听总线是很合理的。
还有一个重要的点:缓存一致性协议是以缓存块(block)为单位追踪的,而不是变量。一个缓存块中可能包含多个变量(如 D0, D1),那么假如core0写D0,core1写D1,而且core 0 and 1的一个cache block上面都有D0 and D1,那么它们都会invalidate两次。明明没共享的数据,却频繁失效,这就是“False Sharing”。
解决建议:从硬件角度,缓存块比较小;从软件开发角度,应把频繁访问的变量之间保持足够距离(至少一个缓存块大小以上):比如使用 padding 或 struct 对齐等技术。
Write Invalidate
- 处理器 k 想写某个地址时:
- 抢占总线的使用权;
- 发送一个 写失效(write invalidate) 消息。
- 其他处理器监听到此消息后:
- 失效(invalidate)自己缓存中对应的缓存行(cache line)副本。
- 处理器 k 在自己的缓存中写入数据(假设写通内存)。
- 其他处理器在之后访问这个地址时:
- 由于缓存行失效,会出现缓存未命中(cache miss);
- 重新从内存加载最新数据。
优点:
- 节省宝贵的带宽,避免频繁广播写数据。
- 这是目前普遍采用的首选写策略。
Optimized Snoop with WAW
使用有效位(valid bit)卸载缓存行,减少无效缓存。
对于写回缓存(write-back cache),每个缓存行有一个脏位(dirty bit):
- 脏位表示:当前缓存行只被一个处理器使用;
- 当处理器 0 第二次写该缓存行时,不需要再广播消息,减少总线负担。
Write Update
CPU 想写时,抢占总线,广播新的数据(而不是失效消息);所有监听缓存的处理器都更新自己缓存中的数据副本。
Implementation Issue
-
如何知道缓存值是否被共享?
-
如果知道缓存值没有被其他缓存复制(即不共享),可以避免发送无用的消息,减少总线带宽占用。
- 但如果结合“写回(write-back)”策略使用:
-
其他处理器可能重新获取的是旧值,因为写回意味着数据只写回主存时才更新。
-
需要协议来处理这个问题
-
缓存一致性协议必须解决缓存行的迁移和复制问题,确保数据的一致视图。
-
缓存行具有状态
-
每个缓存行在缓存中会有一个状态,表明其当前数据是共享的、独占的、修改的还是无效的等。
一下是MOESI协议的例子:
Advanced Cache
Example
图中展示了Intel Ivy Bridge架构:
- 每个核心有独立的L1指令缓存(32KB)和L1数据缓存(32KB);
- 共有的L2缓存(256KB);
- 以及统一的三级缓存(LLC,6MB)。
Cache Relationships
Sneaky LRU
在包容性(inclusive)缓存中(LLC 包含 L1 中所有块),LRU策略会存在“悄悄的”副作用。
过程说明
- A块频繁在L1中被命中,成为L1中最近使用(MRU)块。
- 但在LLC中,A块却是最近最少使用(LRU)块。
- 由于LLC中的LRU块会被驱逐,A块可能被错误地驱逐。
- 这样,MRU块反而被剔除,造成性能损失。
Last-Level Cache (LLC) is not Monolithic
传统观点认为LLC对所有核心是统一整体,任何核心访问缓存块成本相同。
新观点(Intel Xeon E5-2667 v3):
- LLC被划分为多个切片(slice),比如8个slice。
- 每个切片分布在不同物理位置,访问延迟和带宽可能不同。
基于切片的内存管理(Slice-aware Memory Management):
理念
- 将数据尽量放置到接近程序运行核心(core)的内存切片中,减少访问延迟。
实践难点
- 缓存管理复杂,尤其是对细粒度切片的管理。
- 缺乏详细文档,研究难度大。
研究成果
- 研究团队通过优化切片感知管理,提升了键值存储GET操作的平均性能12.2%。
- 这个提升在大规模应用(如Google、淘宝、腾讯、京东等)中非常显著。
总结
主题 | 关键点 |
---|---|
包容性缓存的LRU问题 | LLC中的LRU可能误驱逐L1中频繁使用的数据 |
LLC非单片设计 | LLC由多个物理切片组成,访问延迟不均等 |
切片感知内存管理 | 数据放置更靠近核心,但管理复杂,需研究支持 |