2.6 Cache Never Block

集微笔记 2013-08-05

展开全文

在一个微架构中，有两条值得重点关注的流水线，一个是指令流水线。另一个是Cache Controller使用的流水线，下文将其简称为Cache流水线。这两条流水线的实现对于微架构的性能至关重要。指令流水线的设计与Cache流水线相关，反之亦然。

1967年6月，来自IBM的ROBERT MACRO TOMASULO先生发明了最后以自己名字命令的算法[48]，这个算法最终使得Alpha处理器，MIPS处理器，Power处理器，x86处理器，ARM系列处理器，所有采用OOO技术的处理器成为可能。1997年Eckert-Mauchly Award正式授予TOMASULO先生, for the ingenious Tomasulo's algorithm, which enabled out-of-order execution processors to be implemented.

2008年4月3日，TOMASULO先生永远离开我们。他的算法也历经了多轮改进。即便在针对ILP的优化因为Memory Stall而处境艰难，TOMASULO算法也并不过时。虽然本篇文章的重点并不在Superscalar和OOO，仍然建议所有读者务必能够清晰地理解TOMASULO算法和Superscalar指令流水的细节。为节约篇幅，本篇不会对这些知识做进一步的说明。

而在Cache流水线中，Non-Blocking几乎等同于TOMASULO算法在指令流水中的地位。在现代处理器中，几乎所有Cache Hierarchy的设计都采用了Non-Blocking策略。Non-Blocking Cache实现为Superscalar处理器能够进一步发展提供了可能。

假设在一个Superscalar处理器中，一个时钟周期能够发射n条指令。这要求该处理器需要设置多个执行部件，提供充分的并行性。假设在这个处理器中，某类功能部件x所能提供的带宽为BW_X，此处的带宽是借用存储器的概念，如果该功能部件需要4拍才能完成一次操作，那么该功能部件为指令流水线所提供的带宽为1/4。

在一个应用的执行过程中使用这类功能部件所占的百分比为f_X。那么只有当BW_X/f_X不小于n时，Superscalar处理器才能够充分的并行，否则该功能部件必将成为瓶颈。因此在微架构的设计中，通常并行设置多个执行较慢的功能部件以提高BW_X参数，当然还有一个方法是缩小f_X参数。如何缩小f_X参数并不是微架构的关注领域，因为在一个给定的应用中，从微架构设计的角度上看，f_X参数没有太大的变化空间。

我们可以将BW_X/f_X公式扩展到存储器读写指令。假设BW_S为提供给指令流水线的存储器访问带宽，而f_M为存储器读写指令所占的比例，那么只有在BW_S/f_M不小于n时，存储器访问单元才不会成为指令流水线的瓶颈。

为此我们建立一个基本的存储器访问模型。为简化起见，假设在一个Superscalar处理器中，存储器结构的最顶层为L1 Cache，其中L1 Cache由指令和数据Cache两部分组成，并使用Write Back方式进行回写，L1 Cache通过L1-L2 Bus与L2 Cache连接。L2 Cache与主存储器系统直接连接。处理器在访问存储器时，首先通过L1 Cache之后再经过L2 Cache，最后到达主存储器系统。该模型也可以进一步扩展到L3 Cache和更多的Cache层次，但是为了简化起见，我们仅讨论L1和L2 Cache的情况。在这个前提之下，我们讨论与Cache相关的延时与带宽，重点关注Cache Hierarchy为指令流水提供的有效带宽，即BW_S参数。

当微架构进行存储器访问时，将首先访问L1 Cache，此时有Hit与Miss两种情况。如果为Hit，L1 Cache将直接提供数据；如果为Miss，L1 Cache将产生一个Miss请求，并通过L1-L2 Bus从L2 Cache中获得数据。

通常情况下Cache Miss会引发Cache Block的Replacement，如果被替换的Cache Block为Dirty时，还需要向L1-L2 Bus提交Writeback请求，此时L1 Cache Controller将向L2 Cache发送两类数据请求，一个是Cache Miss Request，一个是Write Back Request。为了提高Miss Request的处理效率，在绝大多数微架构中首先向L2 Cache发送Cache Miss Request，之后再发送Write Back Request。

由上文的分析可以发现，BW_S参数不能通过简单的计算迅速得出，必须要考虑整个Cache Hierarchy的实现方式。BW_S参数与L1-L2 Bus的实现方式，与是否采用了Non-Blocking Cache的设计密切相关。

在现代微架构中很少再继续使用Blocking Cache实现方式，但是我们依然需要分析为什么不能使用这种技术。在使用Blocking Cache的微架构中，存储器访问如果在L1 Cache中Hit时，可以直接获得数据，不会影响指令流水。

但是出现Cache Miss时，由于Cache Blocking的原因，L1-L2 Bus将被封锁，直到从其下的存储器子系统中获得数据。由于采用这种技术L1-L2 Bus一次仅可处理一个L1 Cache Miss，如果出现多个Cache Miss的情况时，这些Miss请求将逐一排队等待上一个Miss获得数据。这种做法严重降低了BW_S参数，从而极大影响了Superscalar处理器的并行度。

从以上说明可以发现Blocking Cache的主要问题是处理Cache Miss时，使用了停等模型，L1 Cache最多仅能处理一个Pending的Miss请求。而L1-L2 Bus一次也只能处理一种数据请求，或者是Miss请求，或者是Writeback请求。

在否定Blocking Cache之前，我们需要对BW_S参数做进一步的分析。假设在一段程序中一共进行了H M次存储器请求，其中H是L1 Cache的Hit次数，而M为Miss次数。由于本次模型规定存储器访问不得Bypass L1 Cache，所以在L1 Cache中Hit和Miss次数之和即为存储器访问请求的总和。

在现代处理器中L1 Cache通常设置两个Ports，但是为了简化模型，我们假设在L1 Cache中只含有一个Port。假设L1 Cache在Hit的情况下，一个Cycle即可将数据读出，此时处理H个Hit操作，L1 Cache一共需要使用H个Cycle，如果所有存储器访问都能命中L1 Cache，BW_S参数为1。但是L1 Cache不可能永远Hit，因此在计算BW_S参数时，必须要考虑M个Cache Miss的情况。

L1 Cache处理一次Miss所需的时间为 T_M B，而L1-L2 Bus在处理一次Miss所需的时间为[T_M B(1 d)]。其中T_M是指L1 Cache发出Miss请求之后，L2 Cache可以提供有效数据Block的时延；B指L2 Cache通过L1-L2 Bus向L1 Cache提交一个数据Block的时间；d指需要进行Writeback请求的比例。

在Blocking Cache中，由于Hit和Miss操作不能流水处理，因此L1 Cache和L1-L2 Bus在处理H M次存储器请求时，一共需要(H M[T_M B])和M?[T_M B(1 d)]个Cycle。在这样一个处理器系统中，BW_S参数为L1 Cache和L1-L2 Bus所提供带宽的最小值，如公式2?5所示。

其中m为Miss Ratio，即M/(H M)。由公式2?5可以发现，当m增加时BW_S参数将等比例降低。考虑m等于0.05，T_M等于10，B等于1，d等于0这个理想状态时，BW_S参数也仅为0.67。此时如果f_M参数为0.4，BW_S与f_M参数的比值为1.67。由此可以得出在这种模型下，一个Superscalar处理器不管内部具有多少可以并行执行的模块，但是一次发射的指令都不能超过两条，否则存储器读写必将成为瓶颈，最终阻塞整个流水线。这一发现使Superscalar处理器因为Cache Blocking的原因几乎无法继续发展。

因此必须有效的提高BW_S参数。提高BW_S参数有两个有效途径，一个是增加命中L1 Cache后的带宽，也由此带来了多端口Cache的概念。正如上文的讨论结果，Cache上每增加一个端口，需要耗费巨大的开销，而且Cache容量越大，这类开销越大。在现代处理器中，L1 Cache多由两个端口组成，如图2?9所示。为了进一步提高并行度，Superscalar处理器还可以使用更多的端口，但是这将使用更多的资源。

在对Cost/Performance进行Trade-Off之后，Cache设计引入了Multi-Bank的概念。一些量化分析的结果证明，与单纯的Multi-Port Cache实现相比，Multi-Bank与更少的Port组合在经过一些简单的消除Bank Conflict的优化之后，可以获得更高的Cost/Performance比[50]。这使得MBMP(Multi-Banks and Multi-Ports)结构在现代微架构的Cache设计中得到了广泛应用。Opteron的L1 Data Cache使用了8-Banks 2-Ports的组成结构[6]。

这些优化依然只是提高了Cache Hit时的Cache带宽。如公式2?5所示，计算Cache的总带宽需要考虑Cache Miss时的情况。因此即便我们将Hit时的Cache带宽提高到Infinite，依然不能解决全部问题，必须要考虑1/(m?[T_M (1 d)?B])这部分带宽。

当m和T_M参数都非常小，而且B等于1时，这部分带宽并不值得仔细计算。但是事实并非如此，随着计算机主频的不断攀升，T_M参数的相对值一直在不断提高；而主存储器的快速增加，L1 Cache相对变得更小，使得m参数进一步提高。这使得Miss时使用的带宽备受关注。最自然的想法是使用流水方式将多个Outstanding Cache Miss并行处理，使得多个Miss可以Amortize T_M参数，从而最终有效提高BW_S参数。

这一构想使David Kroft在1981年正式提出了Lockup-Free Cache(Non-Blocking Cache)[51]这个重要的概念。Kroft建议设置一组MSHR(Miss Information/Status Holding Registers)暂存Miss请求。其中每一个MSHR与一个Outstanding Miss相对应。当MSHR的个数为N时，该Cache结构即为Non-Blocking(N) Cache。Non-Blocking(N) Cache可以并行处理N个Outstanding Cache Miss，而且在处理Cache Miss的同时可以并行处理Cache Hit，修正了Blocking Cache存在的诸多问题，使得Superscalar处理器得以继续。

David Kroft，这个毕生都没有发表过几篇文章的，也许是普通的再也不能普通的工程师学者，让众多拥有几十篇，甚至几百篇的教授和Fellow汗颜。他在Retrospective中这样评价着这个算法。

How does one begin to describe the dreams, thoughts and fears that surround a discovery of a different view of some old concepts or the employment of old accepted methodology to new avenues? It is probably best to start the account by describing the field of Computer Architecture, in particular, the area of hierarchical memory design, that was prevalent around and before the time the ideas came to light.

...

As indicated at the beginning, a discovery is just a different look at some old concepts or the use of some old concepts for new mechanisms. Mine was the latter [52].

从今天对Cache的认知上看，David Kroft的建议顺理成章，几乎每一个人都可以想到。而在David Kroft提出这个设想的那个年代，Miss Blocking几乎是理所应当的，可以极大简化Cache的设计。David Kroft所以能够提出这个建议更深层次的原因，是他具有向已知的结论挑战的勇气。

我目睹过一些填鸭式的魔鬼训练营。那里逼迫着诸多才智之士强记着几乎不会出错的结论，强化着比拼编码速度的各类实现。直接使用结论比从学习基础的原理并推导出结论快得多。按部就班是过于漫长的，是无法速成的。这样做似乎是一条捷径。只是伏久者，飞必高；开先者，谢独早。世上没有捷径，起初的捷径必为将来付出惨痛的代价。

依靠速成得来的这些结论和已知实现虽然可以被信手拈来，用于构建各类设计，却更加容易使人忽略一些更加基础的知识。最重要的是这些结论会很容易在心中生根发芽。在经过多次反复后，这些才智之士不会没有挑战结论的勇气，只是失去了挑战结论的想法。诸恶之恶，莫过于此。以中国的人口基数，却远没有获得与此对应的成就，在Cache Memory，处理器，计算机科学，在更多的领域。生于斯，长于斯，愧于斯。

David Kroft提出了Non-Blocking Cache的同时，打开了潘多拉魔盒，这个领域奋战着的Elite万劫不复。在Lockup-Free Cache出现后的不长时间内，经历了许多修改，使得CPU Core-L1 Bus，L1-L2 Bus，其后的Bus设计进一步复杂化。

David Kroft提出的算法只有4页纸的描述，更多的是春秋笔法，以至于很难根据这个论文，实现出可用的Non-Blocking Cache结构。这些已不再重要。David Kroft当时的想法基于当时的认知，很难突破当时的认知，绝非完美，可能只适用于Statically-Scheduled架构，依然指明了前进之路。其后Dynamically-Scheduled架构进一步改进了Lockup-Free Cache结构。这也是现代微架构在进行Cache设计时常用的方法。

对于Dynamically-Scheduled的处理器，Non-Blocking Cache有多种实现方法，Address Stack，Load Queue，Address-Reorder Buffer或者其他方法。本篇仅介绍Address Stack实现机制，该机制的实现较为直观，其基本组成结构如图2?21所示。

以上Non-Blocking Cache的实现中，包含5个MSHRs，Address Stack的Entries数目为16。在这种实现中，如果微架构访问存储器出现Cache Miss时，需要首先判断本次访问所需要的数据是否正在被预取到Cache Block中，该功能由MSHRs寄存器组及相应控制逻辑实现；当数据从存储器子系统中返回时，需要解决所有依赖这个数据的Pending Cache Miss，该功能由Address Stack及相应的控制逻辑实现。

每个MSHR至少包含3个数据单元，Block Valid Bit，Block Address和Destination Bits。其中Block Valid Bit有效表示地址为Block Address的Cache Block发生过Fetch，从IC Design的角度上看，Cache Block是有地址的，上文已经对此进行过描述。

当Cache Miss时，Cache流水线将首先并行查找MSHRs寄存器组的Block Address，判断即将访问的Cache Block是否正在被Fetch。如果在MSHRs寄存器组中命中，本次Cache Miss即为Secondary Cache Miss，否则为Primary Cache Miss。

对于Primary Cache Miss，需要在MSHRs寄存器组中获得一个空闲Entry，并填写相应的Block Address，设置Block Valid Bit，同时向其下的存储器系统发送Fetch请求；如果当前MSHRs寄存器组中没有空闲Entry，之后微架构将不能继续issue存储器请求，Cache流水线将被Stall，直到之前发出的Fetch请求返回，释放MSHRs寄存器组中的对应Entry。

Secondary Miss的处理相对较为复杂。此时需要视不同情况讨论。不同的微架构采用了不同的策略处理Secondary Miss。在Kroft的建议中，Cache Block的管理按照Word进行分组。因此只有Secondary Miss访问的Word并与Pending Miss请求完全一致时，Cache流水线才会Stall，这种MSHRs也被称为Implicitly Addressed MSHRs[54]。与此对应的概念还有Explicitly Addressed MSHRs，采用这种组成方式，可以解决对同一地址进行访问时，不会Stall Cache流水线，其详细实现见[54]。

一个很容易想到的，更加高效的方法是将Primary Miss和其后若干个Secondary Miss合并为一个Fetch请求。但是这种Merge是有条件的，需要更多的Buffer实现。这种方式不仅带来延时，更为Memory Consistency制造了不小的麻烦。

当Cache Miss引发的Fetch请求最终返回，并从其下的存储器系统中获得Cache Block之后。Cache流水线将并行检查MSHRs寄存器组，并获得对应的Destination Bits，并依此判断，所获得的数据是发向指令Cache，数据Cache，还是某个定点或者浮点寄存器。然而在Dynamically-Scheduled架构中，为了维护Cache Consistency，问题更加复杂。

在Dynamically-Scheduled架构中，由于Load Speculation的存在，存储器读操作在微架构出现Mispredicted的转移指令，或者Exception时，需要抛弃之前的Speculative Load请求，此时可以采用Address Stack处理这种情况。

Address Stack为Fully-Associative Buffer，由Address Valid Bit, Physical Address, Instruction ID三个字段组成。当微架构发射存储器读写指令时，将首先计算Physical Address，之后并行查找Address Stack，获得空余的Entry。如果Address Stack中没有空余的Entry，将产生Structural Hazard，已发射的存储器指令不断重试，直到获得空余的Entry；如果有空余，则设置该Entry的Address Valid Bit，填写Physical Address，并向其下存储器系统发送Fetch请求。

当Fetch的Cache Block返回时，会并行查找Address Stack，如果Match，返回的数据将进入相应的Cache，可能还会传递给某个寄存器。指令流水线的设计者可以决定是在存储器读写指令在Complete还是在最后的Commit阶段时，才真正释放Address Stack的Entry。前者实现较为复杂，后者较为简单。

在一切都是“正常”的情况下，返回的Cache Block并行查找Address Stack似乎是冗余的。但是考虑Misprediction转移和Exception处理之后，我们不能得出这样的结论。当发生这两种情况时，在刷新微架构状态时，所有Speculative Store/Load指令也需要被刷新。

使用Address Stack方法设计Non-Blocking Cache时，处理这些异常需要清除相应Entry的Address Valid Bit。当数据返回时，将无法在Address Stack中找到合适的Entry。对于存储器读请求，数据将不会写入Physical Register，对于存储器写请求，数据不会真正写入，以避免各类潜在的错误。

由以上描述，可以发现这种Non-Blocking设计由两部分组成，一个是Cache Miss时使用的Address Queue，和处理数据返回使用的Address Stack。不同的微架构使用的Non-Blocking Cache设计方法大同小异，要点是设置专门的Buffer处理多个Cache Miss，采用流水方式，使多个Cache Miss请求最终可以Amortize T_M参数，最终有效提高BW_S参数。

Non-Blocking Cache的概念不难理解，重要的是实现。总线技术的不断发展，使得这些实现愈发困难。在现代微架构中，用于Cache间互联的总线，大多被分解为若干个子总线，由Data，Request，Ack和Snoop四条子总线组成，而在这四条子总线中还会继续分级，以进一步扩展带宽。这些变化使得Non-Blocking Cache的话题离学术界渐行渐远。

在系统总线设计中出现的这些变化极大增加了Cache流水线的设计难度。我们进一步考虑Cache的层次结构从L1，L3到EDRAM，进一步考虑处理器系统从CMP，SMP到ccNUMA，进一步考虑Memory Consistency从Strict consistency，Sequential Consistency到Weak Consistency，进一步考虑各类细节和不断攀升的Cache运行频率，会使最具睿智的一群人为之魂系梦牵。他们明白世上再无任何数字逻辑能够如此忘情。