当前典型多核处理器的cache结构分析.doc

当前典型多核处理器的cache结构分析摘要：对多核处理器发展中高速缓存 Cache 存储层所出现的问题进行分析与研究，主要是多核结构采用的多级分布式 Cache 引发的存储一致性问题。最早的 NUCA研究了对单处理器环境下 NUCA 效应给处理器性能带来的影响。后来针对 NUCA 提出了一种称为动态非一致性访问（Dynamic Non-Uniform Cache Access, DNUCA )的设计来管理大容量 Cache。多核架构下的另一种管理片上大容量 Cache 的思路是采用分布式管理，将片上的 Cache 资源分布到各个处理器内核结点，通过设计划分强调连线的局部性，避免频繁长距离 Cache 通信的产生。1 背景高速缓冲存储器 Cache 是计算机存储系统中最重要的部分，最早由 Wilkes 于1951 年构想出来。Cache 技术的出现正是为了弥补处理器与存贮器之间的速度差异。目前，多核处理器芯片普遍采用在片内集成大容量 Cache 的方式来提高存储系统的性能。大容量 Cache 可以直接增加处理器芯片内 Cache 命中率，减少片外访存的频率，但由于 Cache 面积过大，又分散在芯片的不同位置，在线延迟的影响下，同一层次但不同距离 Cache 的访问呈现出不同的通讯延迟，即所谓的非一致性缓存访问 NUCA (Non-Uniform Cache Access)。2 多核中Cache结构综述2.1多核芯片上的Cache技术多处理器核组织结构主要有UCA（UniformCache Access）和NUCA（Non-Uniform Cache Access）两种（如图1所示）。在UCA结构中，多个处理器核与二级Cache通过互联总线（Bus）或交叉开关（cross switch）互联，所有处理和对二级Cache访问延迟相同；在NUCA结构中，每个处理器核具有本地二级Cache，通过互联系统对其他处理器核的二级Cache访问（延迟变长）。随着集成度的提高，也可以讲三级Cache集成到片内，如图2所示。在以上4种组织中，片内二级或三级Cache均为所有处理器核共享。当一块芯片上集成了多个处理器核时，各个处理器核之间通过共享Cache数据单元实现数据的交换与同步，多核争用Cache中的数据是多核芯片需要解决的一个重要问题。2.2 多核架构对处理器Cache技术的影响最早的 NUCA研究了对单处理器环境下 NUCA 效应给处理器性能带来的影响。后来针对 NUCA 提出了一种称为动态非一致性访问（Dynamic Non-Uniform Cache Access, DNUCA )的设计来管理大容量 Cache。DNUCA 是将大容量 Cache 分为很多小的 Bank，允许 Cache块动态地进行物理位置上的迁移，运行时的热点数据将逐渐集中到离处理器内核较近位置的 Bank 中，以此来降低访问 Cache 的延迟。图3 DNUCA不同映射机制的结构基于片上Cache行迁移的DNUCA技术在实现时主要应解决三个问题：映射(Mapping)：是 Cache 地址与可寻址 Cache 体之间的对应关系，根据映射策略的不同，DNUCA 的三种实现方式如图3所示，即“简单映射”策略是根据几何位置将每一列的 Cache 体编为一个体组，地址与体组具有简单固定的一一对应关系，但是对应 Cache 行在体组内位置是任意的。简单映射实现方式的硬件代价最小，但是由于几何分布的不均，不同体组之间访问延时会不均衡；第二种“公平映射”方式是解决体组访问延迟的非均衡问题，通过对体进行几何位置上的均匀分组使得各体组的平均体访问延迟近似相等，但由此会导致同一体组内复杂的路由管理，增大了硬件实现的开销；第三种“共享映射”设计是为所有体组共享离核最近体的方式，由于需要在不同组间进行容量空间的共享和 Cache 块的交换，组相联方式会受到一定限制。查找(search)：是因为 DNUCA 中 Cache 块不具有固定宿主体位置(home)，查找解决如何定位 Cache 块所存分组的问题。DNUCA 设计了增量查找和广播查找两种方式：增量查找每次查找一个体，缺失后将查找请求传送到下一个体，这种方式的网络流量和功耗开销较小，但查找时间较长；广播方式是一次将查找请求发送到体组内所有的体，可以在最短时间内完成定位，但会增大网络流量和功耗开销。迁移(Movement)：如何在体之间进行 Cache 行的迁移管理。DNUCA 的设计目标是使命中尽可能地在物理距离较近的 Cache 体上发生，理想的迁移策略应该是采用最近最少使用 LRU (Least Recently Used)机制对体组内的Cache 行进行排序。但使用这种策略，Cache 行迁移将带来较大的交换传送开销。在 DNUCA 中采用了一种思想类似于冒泡排序的升级替换算法来解决这个问题，使迁移只在相邻的 Bank 间发生，以此来降低替换时的开销，经过动态预热后，可以获得近似于 LRU 算法的效果。在 NUCA 之后，Beckmann 曾等将单处理器环境下的 DNUCA 技术扩展到多核处理器中，然而性能并不理想。原因在于多核环境中的多线程应用程序存在大量的核间数据共享，在多个处理器内核来回拖动效应下，共享数据将会迁移到距离所有处理器核都较中间的区域，而降低根据 LRU原理进行迁移的效果。DNUCA 存在的另一个弊端是受到 Tag 组相联度的影响，因同一组(set)中只有少数路(way)的 Cache 行能存放于离处理器核较近的体中。针对这个问题，Powell 等提出的 CMP-NuRAPID 技术是对解决片上大容量 Cache 访问延迟的另一种尝试38，该技术同样引入了访问的距离性因素，将片上的大容量Cache 资源按照距离进行分组，但采用了间接索引技术将传统 Tag 与数据存储单元的一一对应关系分离开来。通过在 Tag 中增加额外的索引指针来记录对应数据行的物理位置，而为了在数据替换时能更新对应的 Tag，数据行则增加了一个反向指针(reverse pointer)用于指示其逻辑对应的 Tag。多核架构下的另一种管理片上大容量 Cache 的思路是采用分布式管理，将片上的 Cache 资源分布到各个处理器内核结点，通过设计划分强调连线的局部性，避免频繁长距离 Cache 通信的产生。分布式 Cache 管理的关键是对片上 Cache 容量的高效利用，这包含两个层次的意义：首先是对局部 Cache 容量的有效利用，通过使访问大部分命中本地的Cache，降低对远程 Cache 的访问频率，进而缓解线延迟对性能的制约；其次是对片上 Cache 总容量的高效利用，由于片上 Cache 失效之后会带来数十甚至上百周期的处理器空转，多核芯片的存储系统设计需要尽可能地使访问在片上 Cache 层次的命中，减少对片外存储系统的访问。从目前的研究情况来看，Cache 有效使用的技术采用了两个基本思路：一是充分均衡地利用片上 Cache 的容量，二是减少片上 Cache 中的数据副本。根据 Cache 的共享方式，分布式多核处理器系统依然可以分为独有和共享两种结构。在分布式独有 Cache 结构中，整个片上 Cache 的容量实际被划分成容量较小的子部分，并分布于片上各个结点。与采用集中管理的大容量 Cache 相比，这部分 Cache 容量相对较小，可以采用传统的均衡访问方式进行管理。处理器内核与容量相对较小的本地 Cache 之间保持距离的局部性，具有较快的访问速度，可以在一定程度上避免 NUCA 结构远距离传送数据的延迟问题，但最大的不足是对片上 Cache 资源的利用率不够。当片上线程并行度不足时，独有结构中会出现没有进行有效运算的处理器内核，其所在结点的二级 Cache容量处于闲置状态，得不到充分利用。独有结构的另一问题在于片上二级 Cache层次中出现过多的数据副本，降低了对容量的有效利用。Chishti 等针对独有 Cache容量利用率问题提出了一种“副本控制”、“容量借用”的管理策略。副本控制是针对层次间过多数据副本对容量的消耗，采用了一种“时间换容量”的设计。容量借用则是在 Cache 替换时，将被替换出去的 Cache 块放置到临近结点的 Cache 中，而不是简单写回或丢弃，当出现空闲结点时，此方法可以有效利用空闲结点中的cache资源。在采用分布式共享 Cache 的多核结构中，片上的处理器内核都能直接访问其它结点的 Cache，可以均衡利用所有的片上 Cache 容量。尽管分布式 Cache 能解决容量均衡利用问题，但是因为需要在不同核心地址间进行映射造成了延迟增加。Asanovi 等提出了一种称为替换复制（Victim Replication）的方法以缓解线延迟对共享 Cache 性能的制约。替换复制是对普通分布式共享 Cache 结构的一种改进，它将一级 Cache 中被替换出的块采用独有 Cache 的方式分配到本地的二级 Cache中存放，而不是写回二级 Cache 的宿主结点，这样结点的 Cache 采用介乎独有与共享之间的混合方式进行管理，同时需要修改 Cache 的查找算法。3 小结多核处理器架构中大容量片上 Cache 的有效管理技术借鉴了分布式共享系统的设计思想，将全部 Cache 分布到片上每个处理器内核结点，通过有效利用局部Cache 容量和全部 Cache 容量来降低访存延时，目前来看还没有达到非常满意的程度。因此，对多核处理器片上大容量 Cache 的高效管理还需要进行新的探索。参考文献1M.R.Marty,Cache coherence techniques formulticore processors,University of Wisconsin atMadison,2008,p.205.2 C. Kim,