2.2 Cache的组成结构

由上文所述，在一个Cache中包含多行多列，存在若干类组成方式。在处理器体系结构的历史上，曾出现过更多的的组成结构，最后剩余下来的是我们耳熟能详的Set-Associative组成结构。这种结构在现代处理器微架构中得到了大规模普及。

在介绍Set-Associative组成结构之前，我们简单回顾另外一种Cache组成结构，Sector Buffer方式[23]。假定在一个微架构中，Cache大小为16KB，使用Sector Buffer方式时，这个16KB被分解为16个1KB大小的Sector，CPU可以同时查找这16个Sector。

当CPU访问的数据不在这16个Sector中命中时，将首先进行Sector淘汰操作，在获得一个新的Sector后，将即将需要访问的64B数据填入这个Sector。如果CPU访问的数据命中了某个Sector，但是数据并不包含在Sector时，将相应的数据继续读到这个Sector中。采用这种方法时，Cache的划分粒度较为粗略，对程序的局部性的要求过高。Cache的整体命中率不如采用Set-Associative的组成方式[23]。

在狭义Cache的设计中，这种方法已经不在使用。但是这种方法依然没有完全失效。处理器体系结构是尺有所短，寸有所长。在一些广义Cache的设计中，Sector Buffer方式依然是一种行之有效的Buffer管理策略。有很多程序员仍在不自觉地使用这种方式。这种不自觉的行为有时是危险的，太多不自觉的存在有时会使人忘记了最基础的知识。

我曾经逐行阅读过一些工作了很多年的工程师的Verilog代码，在这些代码中使用了一些算法，这些算法我总感觉似曾相识，却已物是人非。他们采用的算法实际上有许多经典的实现方式，已经没有太多争论，甚至被列入了教科书中。有些工程师却忘记了这些如教科书般的经典，可能甚至没有仔细阅读过这些书籍，在原本较为完美的实现中填入蛇足。更为糟糕的是，一些应该存在的部件被他们轻易的忽略了。

有时间温故这些经典书籍是一件很幸运的事情。我手边常备着A Quantitative Approach和The Art of Computer Programming这些书籍，茶余饭后翻着，总能在这些书籍中得到一些新的体会。时间总是有的。很多人一直在抱怨着工作的忙碌，没有空余，虽然他们从未试图去挤时间的海绵，总是反复做着相同的事情。多次反复最有可能的结果是熟能生巧而为匠，却很难在这样近乎机械的重复中出现灵光一现的机枢。这些机枢可能发生在你多读了几行经文，或受其他领域的间接影响，也许并不是能够出现在日常工作的简单重复之上。

写作时回忆SectorBuffer机制时写下了这些文字。在现代处理器中，Cache Block的组成方式大多都采用了Set-Associative方式。与Set-Associative方式相关的Cache Block组成方式还有Direct Mapped和Fully-Associative两种机制。Direct Mapped和Fully-Associative也可以被认为是Set-Associative方式的两种特例。

在上世纪90年代，Direct Mapped机制大行其道，在Alpha 21064，21064A和21164处理器中，L1 I Cache和D Cache都使用了Direct Mapped方式和Write Through策略。直到Alpha 21264，在L1 Cache层面才开始使用2-Way Associative方式和Write Back策略[16][17][18]。即便如此Alpha 21264在L1 I Cache仍然做出了一些独特设计，采用了2-Way Set-Predict结构，在某种程度上看使用这种方式，L1 I Cache相当于工作在Direct Mapped方式中。

在90年代，世界上没有任何一个微架构能够与Alpha相提并论，没有任何一个公司有DEC在处理器微架构中的地位，来自DEC的结论几乎即为真理，而且这些结论都有非常深入的理论作为基础。与Fully-Associative和Set-Associative相比，Direct Mapped方式所需硬件资源非常有限，每一次存储器访问都固定到了一个指定的Cache Block。这种简单明了带来了一系列优点，最大的优点是在200~300MHz CPU主频的情况下，Load-Use Latency可以是1个Cycle。天下武功无坚不破，唯快不破。

至今很少有微架构在L1层面继续使用Direct Mapped方式，但是这种实现方式并没有如大家想象中糟糕。围绕着Direct Mapped方式，学术界做出了许多努力，其中带来最大影响的是Normal P. Jouppi书写的“Improving Direct-Mapped Cache Performance by Additionof a Small Fully-Associative Cache and PrefetchBuffers”，其中提到的Victim Cache，Stream Buffer[20]至今依然在活跃。

使DirectMapped方式逐步退出历史舞台的部分原因是CPU Core主频的增加使得Direct Mapped方式所带来的Load-Use Latency在相对缩小，更为重要的是呈平方级别增加的主存储器容量使得Cache容量相对在缩小。