存储器层次结构和缓存
存储器层次结构将存储组织成多个级别——寄存器、缓存、主存储器和后备存储器——以便小型、快速的级别保存最可能被使用的数据，从而给程序提供一个既大又快的存储器错觉。
Definition
存储器层次结构是一种分层排列的存储技术，其速度、成本和容量各不相同，通过管理使得频繁和最近访问的数据驻留在更快、更小的级别（最重要的是缓存）中，以最小化平均访问时间。
Scope
本领域涵盖了存储器为何以及如何利用局部性原理组织成层次结构。它包括缓存结构（放置、替换和写入策略）、多级缓存、跨处理器的缓存一致性、虚拟存储器和地址转换，以及底层的DRAM和新兴存储技术。它不包括处理器执行本身（处理器微体系结构）以及大规模文件和设备存储（存储和I/O系统），尽管它与两者都有关联。
Sub-topics
Core questions
- 为什么引用局部性使分层存储器层次结构有效？
- 缓存是如何在放置、关联性、替换和写入策略方面进行组织的？
- 当多个缓存持有相同存储器副本时，如何维护一致性？
- 虚拟存储器如何转换地址并提供保护和大型存储器的错觉？
- DRAM和新兴存储器的特性如何影响系统性能？
Key concepts
- 时间局部性和空间局部性
- 缓存命中和未命中
- 关联性和替换策略
- 直写和回写
- 多级缓存
- 缓存一致性
- 虚拟存储器和分页
- 转换后备缓冲区
- DRAM和存储器带宽
- 平均存储器访问时间
Key theories
- 引用局部性
- 程序倾向于重用最近访问的数据（时间局部性）并访问相邻地址（空间局部性）；存储器层次结构通过缓存最近使用的块并同时获取相邻块来利用这两者。
- 缓存设计权衡
- 缓存性能受未命中率、未命中惩罚和命中时间的影响，并通过大小、块大小、关联性以及替换和写入策略进行调整；经典分析将强制性未命中、容量未命中和冲突未命中识别为这些选择的目标。
Mechanisms
当处理器请求数据时，首先检查缓存；命中则快速返回数据，而未命中则从较低级别获取一个块，并可能通过替换策略逐出另一个块。写入通过直写或回写方案传播，一致性协议保持多个缓存的一致性。虚拟存储器通过页表和转换后备缓冲区（translation lookaside buffer）增加了一个转换步骤，将程序地址映射到物理DRAM，同时强制执行保护。
Clinical relevance
存储器层次结构经常主导实际性能：由于处理器比主存储器快得多，缓存行为和局部性往往比原始指令速度更重要。缓存感知数据布局、分块和预取是高性能计算、数据库和机器学习内核的核心，而缓存时序已成为安全侧信道的一个来源。
History
Maurice Wilkes于1965年提出了缓存（一种“从属存储器”），缓存随后进入了IBM System/360 Model 85等商用机器。虚拟存储器起源于20世纪60年代初的Atlas计算机，并由Denning的工作集模型正式化。Alan Jay Smith在1982年的调查巩固了缓存设计知识，随着处理器-存储器速度差距的扩大，多级缓存和复杂的一致性协议成为标准。
Debates
- 局部性的硬件管理与软件管理
- 透明的硬件缓存与显式管理的存储器（暂存器、软件控制的预取）之间存在持续的张力：硬件缓存通用且易于编程，而显式管理对于专业工作负载可能更可预测和高效。
Key figures
- Maurice Wilkes
- Alan Jay Smith
- Peter J. Denning
- John L. Hennessy
- David A. Patterson
Related topics
Seminal works
- hennessy2019
- smith1982cache
- patterson2020
Frequently asked questions
- 如果缓存相对于主存储器如此之小，为什么它们仍然有效？
- 因为程序表现出局部性：在任何时刻，它们只重复触及一小部分工作集数据，并且访问集中在相邻地址。因此，一个包含该工作集的小型缓存可以满足绝大多数请求。
- 缓存和虚拟存储器有什么区别？
- 两者都将数据在更快、更小的级别和更慢、更大的级别之间移动。缓存（由硬件管理）保存主存储器的块；虚拟存储器（与操作系统一起管理）将程序地址映射到物理存储器，并将数据分页到磁盘和从磁盘分页，同时还提供保护和比物理RAM更大的地址空间。