L06 Memory

这张幻灯片主要讨论了流水线设计中的复杂问题及其解决方法，重点介绍了如何处理复杂顺序执行的流水线，特别是针对写回延迟的问题。

上次课程回顾：

处理流水线中的异常：在流水线机器中，通过将异常沿着流水线传递，直到指令顺序通过提交点，以处理异常。这种方法确保异常处理不会影响流水线的顺序执行。
旁路网络（Bypass Network）：在指令尚未提交之前，通过旁路网络可以使用计算结果，这样可以减少等待写回阶段的延迟，优化流水线效率。
避免流水线冒险：使用软件技术（如调度和循环展开）来避免流水线冒险（Hazard）。通过调整代码顺序或增加循环中的并行性，可以减少数据依赖带来的阻塞。
解耦架构：在“访问（Access）”和“执行（Execute）”流水线之间使用队列，可以容忍较长的内存访问延迟。这种解耦设计增加了处理器对内存访问延迟的适应性，特别是在数据依赖较少的情况下。
统一功能单元延迟：通过让所有功能单元具有相同的延迟，简化复杂流水线设计，避免结构冒险（Structural Hazard）。这种方法也可以扩展到顺序超标量设计（In-order Superscalar Design），从而提高性能。

更复杂的顺序流水线设计（More Complex In-Order Pipeline）：

这一部分展示了一个更加复杂的顺序执行流水线设计：

写回阶段的延迟：为了保证所有操作在写回阶段拥有相同的延迟，设计中会延迟写回操作。这可以防止写端口的过度使用，即每个周期只有一个指令进入并有一个指令完成。
处理长延迟操作：对于像除法（Divides）或缓存未命中（Cache Misses）等长延迟操作，流水线会被阻塞，直到这些操作完成。通过这种方式，系统可以避免无序的写回和数据竞争。
异常处理：所有的异常都在提交点（Commit Point）进行处理，确保指令顺序的完整性。

写回延迟问题的解决方法：

写回延迟会影响单周期整数操作的效率。为了防止这些操作因写回延迟而减速，使用了旁路技术（Bypassing）。旁路技术允许在写回之前使用指令的计算结果，减少了数据依赖导致的流水线阻塞。

总结：

这张幻灯片强调了在更复杂的顺序执行流水线中，通过旁路和延迟写回技术来优化性能，同时通过功能单元统一延迟来简化结构冒险的处理。

In-Order Superscalar Pipeline（顺序超标量流水线）

顺序超标量流水线是一种通过同时发射多条指令来提高处理器性能的架构。在这张幻灯片中，顺序超标量流水线的设计展示了如何在单一周期内处理多条指令，从而加快指令吞吐量。

主要特点：

每个周期提取两条指令：在每个周期中，流水线可以提取两条指令，其中一条指令可以是整数或内存指令，另一条则是浮点指令。这样可以充分利用处理器的多个功能单元。
同时发射整数/内存和浮点指令：浮点和整数指令可以同时发射到各自的执行单元。通过这种方式，可以有效地增加处理器的并行度，而不会增加过多的复杂性。
通过复制功能单元增加吞吐量：通过复制功能单元（例如Alpha 21064和MIPS R5000系列），处理器可以进一步提高并行指令的数量。虽然这种方式有效增加了吞吐量，但需要注意的是，复制功能单元也会带来寄存器文件端口和旁路的设计挑战和成本。
典型例子：典型的顺序超标量设计包括Alpha 21064（1992年）和MIPS R5000（1996年），这些处理器采用了廉价的方法增加了吞吐量。
扩展性问题：这种设计可以通过复制更多的功能单元扩展为更高吞吐量的架构，例如UltraSPARC和Alpha 21164的四发射设计，但在扩展时寄存器文件端口和旁路网络的成本会迅速增加。

早期只读存储器技术（Early Read-Only Memory Technologies）

这部分介绍了早期的只读存储器（ROM）技术的发展历程。ROM 是指只能读取、不能写入的存储器，通常用于存储指令或数据。在早期的计算机设计中，ROM 扮演着重要的角色，用来存储程序的操作码或控制指令。

穿孔卡片（Punched Cards）：从18世纪初期的雅卡尔织机（Jacquard Loom）开始，穿孔卡片被广泛用于早期的计算设备，如巴贝奇的分析机和IBM的计算系统。每张卡片代表一组指令或数据，通过读卡器来读取。
穿孔纸带（Punched Paper Tape）：类似穿孔卡片，穿孔纸带被用于哈佛Mark 1等早期计算机系统，用于输入指令流。纸带是可连续读取的长卷纸，有效地解决了穿孔卡片需要一张张更换的缺点。
二极管矩阵（Diode Matrix）：在EDSAC-2的微代码存储器中，二极管矩阵被用于实现只读存储器。通过设置二极管连接与不连接的状态，来存储指令或数据。
IBM卡电容ROS（Card Capacitor ROS）：这是IBM的早期只读存储技术之一，使用电容来存储只读数据。这种设计在某些存储应用中提供了高效的解决方案。
IBM平衡电容ROS（Balanced Capacitor ROS）：类似于卡电容ROS，IBM还开发了平衡电容存储系统，这种设计进一步优化了存储的可靠性和读取效率。

总结：

这两部分分别介绍了处理器设计中的顺序超标量流水线架构，以及早期计算机系统中用于存储指令和数据的只读存储器技术。

Early Read/Write Main Memory Technologies（早期读写主存储技术）

机械轮存储（Mechanical Wheels Storage, Babbage, 1800s）

巴贝奇的分析机是最早的机械计算设备之一，其存储技术基于机械轮子，数据（数字）以物理位置和角度的方式存储。尽管它没有被完整制造出来，但它展示了早期存储思想的雏形。

Williams Tube（威廉姆斯管, Manchester Mark 1, 1947）

威廉姆斯管是第一种电子随机存取存储器（RAM），它将数据存储为阴极射线管（CRT）上的电荷图案。通过监测管屏上的点亮状态来表示位的0和1，数据可以快速读写。尽管不太稳定，威廉姆斯管标志着从机械存储向电子存储的过渡。

IBM 650 磁鼓存储器（Rotating Magnetic Drum Memory, 1954）

IBM 650使用旋转磁鼓作为存储设备，数据通过磁化鼓表面的不同位置进行存储。磁鼓存储的工作原理类似于现代硬盘，依靠旋转存取。它能够同时存储和读取数据，广泛用于早期的商业和科学计算中，成为了当时非常普及的存储方案之一。

MIT Whirlwind Core Memory, 1950（MIT旋风核心存储器, 1950年）

核心存储器（Core Memory）

核心存储器是第一个大规模、可靠的主存储解决方案，由Forrester在20世纪40年代末至50年代初在MIT的旋风项目中发明。
存储原理：核心存储器将数据存储为小型铁氧体磁芯的磁化极性。通过在线性排列的二维网格线中通电流脉冲来控制每个磁芯的磁化方向，从而实现数据的写入或读取。
- 毁灭性读取（Destructive Reads）：读取数据时，由于需要检测磁化极性，因此会破坏原有的状态，必须在读取后立即恢复。
特点：核心存储器是一种坚固、非易失性的存储方式，能够在断电后保留数据，因此被用于像航天飞机这样的高可靠性环境。
生产挑战：每个核心磁环必须由人工穿线，在核心存储技术的高峰期，每年生产约250亿个磁芯。
访问速度：核心存储器的典型访问时间约为1微秒，尽管在今天看来较慢，但在当时已经是非常高效的存储技术。

Semiconductor Memory（半导体存储器）

半导体存储器的兴起

1970年代初，半导体存储器开始在存储器市场中占据竞争优势。英特尔公司成立的初衷就是为了开发半导体存储器市场。
早期的半导体存储器 是静态随机存取存储器（SRAM），其基本单元是类似锁存器的结构（交叉耦合反相器）。这种存储器速度快，但成本较高，存储密度较低。

第一款商用动态随机存取存储器（DRAM）

英特尔1103 是首款商用DRAM，具有1Kb的存储容量。
工作原理：通过电容存储电荷来保存数据。虽然需要定期刷新，但它极大地提高了存储密度，降低了成本。

半导体存储器 在20世纪70年代迅速取代了核心存储器，成为主流技术。

One-Transistor Dynamic RAM（1T-DRAM 单晶体管动态RAM, Dennard, IBM）

1T-DRAM单元结构：
- 由一个访问晶体管和一个存储电容组成。
- 存储过程：通过电容来存储数据位（0或1），通过访问晶体管控制存储或读取操作。
- 存储单元必须定期刷新，因为电容上的电荷会随时间泄露。
工作机制：
- 在访问数据时，通过施加电压控制访问晶体管打开或关闭。通过检测电容上的电荷状态，可以读取出数据。
材料和结构：
- 图中展示了现代DRAM中的电容和晶体管结构。材料包括钽五氧化物（Ta₂O₅）作为介电层，钛氮化物（TiN）作为电极，以及钨（W）电极。

Modern DRAM Structure（现代DRAM结构）

现代DRAM结构已经发展到纳米级别制造工艺。图中展示了三星公司制造的亚70纳米DRAM，使用了密集的电容结构以提高存储密度。
圆柱形电容 被广泛用于现代DRAM芯片中，以最大化存储密度，同时保持较高的可靠性和性能。这种高密度的结构使得DRAM能够在极小的空间内存储大量数据，推动了计算机内存的大幅度扩展。

DRAM Architecture（DRAM 架构）

DRAM 存储结构

位存储结构：在 DRAM 芯片上，位（bit）被存储在一个二维数组中，行（word lines）和列（bit lines）构成了整个存储单元的地址系统。每一个存储单元通常由一个电容和一个晶体管组成，用于存储单个位的数据。
地址解码：
- 行地址解码器（Row Address Decoder） 负责选择存储阵列中的某一行，激活该行以读取或写入数据。
- 列解码器（Column Decoder） 和 感应放大器（Sense Amplifiers） 负责选择特定的列，并将存储的数据从存储单元读取出来或将数据写入相应单元。
现代 DRAM 芯片 通常拥有 4-8 个逻辑存储银行（logical banks），每个银行又由多个较小的存储阵列物理实现。这种设计可以提高并行数据访问的能力，从而提高 DRAM 的效率。

DRAM Packaging（DRAM 封装）

封装结构与工作原理

时钟与控制信号：约 7 条引脚负责时钟和控制信号，确保 DRAM 芯片和主机系统的同步。
地址线复用：地址线通过复用技术传递行地址和列地址（约 12 条引脚）。在访问数据时，首先发送行地址，选择相应的行，然后发送列地址，选择该行中的特定列，最终进行数据读写操作。
数据总线：数据总线宽度通常为 4 位、8 位、16 位或 32 位，用于传输数据。在高性能系统中，多个 DRAM 芯片会并行工作，以通过更宽的数据总线（如64位）返回数据。

DIMM 模块

双列直插内存模块（DIMM）：

DIMM 是现代计算机中广泛使用的内存模块，它包含多个 DRAM 芯片，并将时钟、控制、地址信号以及数据总线引脚统一分配到多个芯片上。
- 这些信号通过内存控制器同步发送，部分信号需要缓冲器以确保能够驱动多个芯片。
- 多个 DRAM 芯片的数据引脚协同工作，组成宽度较大的数据总线。例如，一个16x4位的DRAM芯片可以组合成一个64位的数据总线。

DRAM Packaging, Apple M1

Apple M1的封装设计

在 Apple M1 处理器中，两个 DRAM 芯片与系统 SoC （System on Chip）集成在同一封装内。该封装设计旨在提高数据传输速率和带宽。关键规格如下：

128 位数据总线，通过 4.2Gb/s 的速率运行，能够高效地传输数据。
68GB/s 的带宽，确保了系统的高性能和大数据吞吐能力。这种高带宽设计对于处理图像、视频处理等高性能任务非常重要。

DRAM Operation（DRAM操作原理）

DRAM 读写访问过程

DRAM 的读写访问主要包含三个步骤：

行访问（RAS，Row Access Strobe）：
- 解析行地址，激活选中的行（通常是多个KB的一整行数据）。
- 位线（bitlines）与存储单元共享电荷，感应放大器会检测电压的微小变化，并将整行的位数锁存。
- 感应放大器在访问结束后将位线充满电荷以恢复存储单元的状态。
列访问（CAS，Column Access Strobe）：
- 解析列地址，选择感应放大器锁存的位数（通常是 4、8、16 或 32 位，视 DRAM 封装而定）。
- 读取操作：感应放大器锁存的位数通过数据引脚输出到芯片。
- 写入操作：感应放大器根据新的值改变存储单元中的数据电荷。
- 多次列访问可以在同一行内连续进行，而无需重新访问行数据，这种方式被称为 突发模式（Burst Mode）。
预充电（Precharge）：
- 在访问新的行之前，位线需要被预充电到已知的电压值，以确保下一次访问的准确性。

延迟与标准

每个步骤的延迟在现代 DRAM 中大约为 15-20ns。
不同的 DRAM 标准（如 DDR、RDRAM 等）通过不同的信号编码方式实现数据传输，但它们共享相同的核心架构。

Double-Data Rate (DDR2) DRAM

DDR2 DRAM 工作流程

在图中展示的DDR2 DRAM时序图中，详细展示了行访问、列访问、预充电等操作如何在200MHz时钟频率下进行。DDR2使用的是双倍数据速率，意味着在时钟信号的上升沿和下降沿都可以传输数据，这使得其数据速率可以达到400Mb/s，尽管时钟频率仅为200MHz。

行操作（Row Access）：
- 通过行地址解码器（RA）选中某一行，激活这一行中的所有存储单元，准备进行后续的数据访问。这一步的指令为ACT（Activate），它标志着开始选取行地址。
- 选中的行会保持激活状态，直到所有相关的列操作完成，随后进入预充电阶段。
列操作（Column Access）：
- 在行激活后，系统通过列地址选择特定的存储单元。这一步由读取指令READ2进行。
- 选中的列地址会通过感应放大器锁存该列的数据，并将数据输出至数据线（DQ）。
- 这一阶段的数据传输速度能够达到400Mb/s（双倍数据速率），显著提升了数据处理能力。
预充电（Precharge）：
- 在数据传输完毕后，必须对行进行预充电（PRE）。预充电将位线电压恢复到初始状态，为下一次的行访问做好准备。
- 预充电过程之后，系统会进入一个短暂的空闲阶段，等待下一个行激活指令。
行预取与数据传输：
- 图中可以看到，数据在读取指令发出后，通过行地址解码器选取的位会进入列选择阶段，最后通过数据引脚（DQ1）进行传输。

关键时序参数

tRCD（行至列延迟）：行地址选定到列地址选定的时间间隔。
tRAS（行激活时间）：行保持激活的最短时间，确保该行内所有列能够被正确访问。
tRP（预充电时间）：为新的行激活做准备的时间。

Computer Architecture Terminology

Latency（延迟）

延迟是从操作启动到结果完成的时间（以秒或周期为单位）。在DRAM中，延迟指的是从开始访问存储单元到数据可用的时间。

Bandwidth（带宽）

带宽是单位时间内可以执行的操作次数，通常以每秒的操作数或每个周期的操作数来衡量。DDR2 DRAM的带宽取决于其数据传输速率，图中显示其速率可达到400Mb/s。

Occupancy（占用时间）

占用时间是指在某个操作完成期间，系统的资源被该操作占用的时间。在DRAM操作中，占用时间通常反映了特定的操作（如行激活或预充电）在执行期间占用资源的时长。

特别注意

占用时间可能小于延迟：当一个功能单元在完成一个操作后不再被占用时，占用时间可以小于实际延迟。
占用时间可能大于延迟：如果操作有额外的依赖或资源竞争，占用时间可能大于延迟。
带宽可以大于1/延迟：通过增加并行度，可以在延迟未结束时继续执行操作，从而提升带宽。
带宽可以小于1/延迟：当系统资源有限，操作频繁冲突或被阻塞时，带宽可能下降。

总结

DDR2 DRAM通过双倍数据速率和精心优化的时序管理，大幅提高了数据处理能力。通过合理的行、列访问调度以及预充电操作，DDR2有效减少了延迟，并最大化了内存的使用效率。

CS152 Administrivia

HW1 Released

截止日期：今天

Lab1 Released

截止日期：2月9日

实验报告要求

实验报告必须是可读的英文摘要，不能只是日志文件的输出！
奖励优秀报告，惩罚无法解读的报告。
请确保报告在规定的页数内，详情见实验说明或Ed讨论区。

讲座Ed讨论区

每次讲座有一个对应的讨论帖。
请按照以下格式提问：
- [幻灯片编号] + 你的问题
教学团队会异步回复和澄清问题。

反馈

请告诉我们你的想法：CS152反馈表

CS252 Administrivia

阅读材料

阅读材料在 HotCRP
请在每周三之前通过HotCRP上传阅读报告：
- 写一段关于论文主要内容的总结，包含论文的优缺点。
- 提出1到3个与论文相关的问题，作为讨论的基础。
- 本周讨论的两篇论文为“360 Architecture”和“VAX11-780”。
讨论时间：周三下午2-3点，地点：Soda 606或Zoom。

CS252 项目时间线

项目提案截止日期：2月22日（周三）。
请利用252A助教（Abe和Prashanth）及我的办公时间获得反馈。

CPU-Memory Bottleneck

性能瓶颈的原因

高性能计算机的整体性能通常受到内存带宽和延迟的限制。在现代计算机系统中，CPU和内存之间的通信速度差异巨大，这就是所谓的CPU-内存瓶颈。瓶颈主要表现为两个方面：

延迟（Latency）：
- 内存访问所需的时间远远大于处理器的周期时间。处理器运行越来越快，而内存访问的延迟改善速度相对较慢，导致了处理器在等待数据时经常空闲。
- 内存访问延迟不仅影响单次访问，还可能导致后续一系列指令被阻塞，进一步拖累整体性能。
带宽（Bandwidth）：
- 带宽指的是单位时间内可以进行的内存访问次数。如果一定比例的指令需要访问内存，则每条指令平均需要进行1 + m次内存引用，其中m表示访问内存的指令比例。
- 当带宽不足时，内存无法满足处理器的高频数据请求，进一步限制了系统的吞吐量。
占用时间（Occupancy）：
- 占用时间是指一个内存模块处理一次请求所需的时间。在高负载下，内存占用时间的增长会导致其他请求等待时间增加，进一步加剧性能瓶颈。

处理器和内存性能差距

从图中可以看到，处理器和DRAM之间的性能差距随着时间的推移不断扩大。自1980年以来，处理器性能每年平均增长约60%，而DRAM性能的增长速度仅为每年7%。这种差距使得现代处理器在等待内存数据时效率大大降低，形成了显著的处理器-内存性能差距。

性能差距的影响

图中显示了这一差距的影响：到1990年代末，处理器的性能已经超出了内存的响应能力。例如，在一个四发射3GHz超标量处理器上，内存访问延迟为100纳秒，这意味着处理器在等待一次内存访问的时间里可以执行多达1200条指令。这个差距使得处理器的高性能无法充分发挥，内存成为系统性能的主要瓶颈。

结论

CPU和内存之间的性能差距已成为现代计算系统中的关键挑战之一。尽管处理器性能飞速提升，但内存技术的发展速度较慢，这导致了越来越严重的瓶颈问题。为了解决这一问题，现代系统中广泛采用了多级缓存、预取机制等技术来缩短延迟并增加带宽，尽可能缓解处理器的等待时间。

Physical Size Affects Latency

物理尺寸对延迟的影响

存储器的物理尺寸在很大程度上影响了其访问延迟。小型存储器与处理器之间的信号传输距离较短，能够快速响应，而大型存储器中的信号需要在更远的距离上传播，并且还需要扩展到更多的存储单元位置，这大幅增加了访问延迟。

信号传播距离：大型存储器中的信号需要更长的时间从CPU传输到数据存储的位置。
信号扩展：大型存储器中的地址解码和信号传递需要同时覆盖更多的存储单元，增加了复杂度和响应时间。

因此，存储器的物理尺寸和布局直接影响数据访问的延迟，尤其在处理大规模数据时，较大的物理尺寸会导致更高的延迟。

Memory Hierarchy

存储层次结构

为了解决不同存储介质的延迟和容量差异，现代计算机系统设计了存储层次结构，将不同速度、容量的存储器结合在一起，以优化性能。

小型、快速存储器（Small, Fast Memory）：
- 包括寄存器文件（RF）和静态随机存取存储器（SRAM），通常用于存储频繁使用的数据。由于它们靠近CPU且物理尺寸小，访问延迟非常低，带宽很高。
大型、缓慢存储器（Big, Slow Memory）：
- 大多数主存储器使用动态随机存取存储器（DRAM）。尽管容量大，但由于其物理尺寸较大且位于芯片外，访问延迟较高，带宽较低。

存储层次结构的特点

容量：寄存器 « SRAM « DRAM。寄存器容量最小，但访问速度最快；DRAM容量最大，但访问延迟最长。
延迟：寄存器 « SRAM « DRAM。寄存器的延迟最低，SRAM稍高，而DRAM具有显著的访问延迟。
带宽：芯片内存储器（如寄存器和SRAM）带宽远高于芯片外存储器（如DRAM），这是因为芯片内部数据传输不受外部总线的限制。

数据访问的优化

低延迟访问：如果数据保存在小型快速存储器中（例如SRAM），处理器可以快速访问数据，延迟较低。
高延迟访问：如果数据不在快速存储器中，处理器需要从大型慢速存储器（例如DRAM）获取数据，导致高延迟。

总结

存储层次结构的设计目的是利用不同存储器的特性，用小型快速存储器存储频繁使用的数据，从而加速数据访问，并尽量减少与大型慢速存储器打交道的频率。这种结构在提高系统整体性能的同时，平衡了延迟和容量的矛盾。

Management of Memory Hierarchy

小型/快速存储器（例如寄存器）

寄存器是计算机系统中速度最快的存储设备，地址通常在指令中直接指定。寄存器的管理通常通过硬件直接实现，作为寄存器文件的一部分，用来存储处理器频繁访问的数据。

指令中的地址指定：寄存器的地址直接通过指令中指定，这意味着处理器可以快速确定要访问的数据位置。
硬件管理：硬件层面可能会在软件不知情的情况下进行一些优化操作，如栈管理（在处理函数调用时）和寄存器重命名（在避免寄存器冲突时）。

这些硬件层面的优化可以提高寄存器的使用效率，减小寄存器相关的瓶颈。

大型/慢速存储器（例如主存）

主存（通常为DRAM）相对于寄存器和缓存来说，存取速度较慢。主存中的数据通常需要通过寄存器的值来计算地址，然后通过缓存层次结构进行管理。

地址计算：主存地址通常是根据寄存器的值计算得到的，而不是直接指定在指令中。
硬件管理的缓存层次结构：硬件决定哪些数据应该保存在快速缓存中，以减少处理器对慢速主存的直接访问。
- 虽然硬件自动管理大部分缓存行为，但软件可以提供“提示”，如预取（Prefetch）指令，帮助硬件更高效地管理缓存和主存之间的数据移动。

Real Memory Reference Patterns

实际内存引用模式

图中展示了程序运行时的内存访问模式，清楚地显示了在不同的时间内，不同内存地址的访问分布。这些分布通常表现出局部性原理，即程序在短时间内倾向于访问相同或邻近的内存地址。

时间轴表示程序的执行过程，而内存地址轴表示程序访问的内存地址范围。
内存访问模式通常表现出聚集现象，比如：
- 局部存储访问
- 频繁的栈访问
- 重复的指令取回

这些模式可以帮助理解程序的运行特性，并为缓存和内存优化提供依据。

Typical Memory Reference Patterns

常见的内存访问模式

不同类型的内存访问具有不同的模式：

指令取回：
- 循环指令表现出规律性的重复访问模式，如图中所示的循环迭代（n loop iterations）。程序每次迭代都会访问相同的指令区域。
栈访问：
- 函数调用和返回涉及对栈的访问，如子程序调用（subroutine call）和参数访问（argument access）。栈访问通常在函数调用和返回时表现为快速的局部访问。
数据访问：
- 数据访问模式取决于程序操作的数据类型。对于向量操作，内存访问往往表现为线性增长的模式（vector access），而标量访问则更加分散（scalar accesses）。

总结

不同的内存访问模式反映了程序中指令、栈和数据的访问行为。理解这些模式有助于优化缓存设计和内存管理策略，提高系统性能。

Two Predictable Properties of Memory References

Temporal Locality

时间局部性指的是：如果某个内存地址被访问，那么在不久的将来它很可能会再次被访问。时间局部性通常出现在循环、函数调用等结构中，程序重复访问相同的指令或数据。

Spatial Locality

空间局部性指的是：如果某个内存地址被访问，那么它附近的地址很可能在不久的将来也会被访问。空间局部性通常与顺序访问数据有关，如数组遍历或连续的数据结构操作。

Memory Reference Patterns

图中的内存引用模式进一步解释了时间和空间局部性的概念：

Temporal Locality（时间局部性）：在图中展示的某些区域中，某些内存地址反复被访问，这表明程序存在对相同数据或指令的重复访问。
Spatial Locality（空间局部性）：图中也显示了某些区域内的地址被顺序访问，这表明程序对相邻内存地址进行了持续的访问操作。

Caches Exploit Both Types of Predictability

缓存利用了这两种局部性来提高内存访问效率：

时间局部性：缓存通过保存最近访问的数据或指令来利用时间局部性。因为这些内容很可能会被再次访问，缓存可以显著减少对慢速主存的访问需求。
空间局部性：缓存通过预取最近访问地址附近的数据块，利用空间局部性。当程序需要访问邻近的内存地址时，数据已经在缓存中，减少了主存访问的延迟。

通过同时利用时间和空间局部性，缓存极大提高了处理器的内存访问效率，缩短了等待数据的时间，改善了整体系统性能。

Inside a Cache

缓存的基本结构

缓存是一种位于处理器和主存之间的高速存储器，用于临时存放最近使用的内存数据，以加快数据访问速度。当处理器请求数据时，它首先从缓存中查找，若命中（hit），则直接从缓存返回数据，若未命中（miss），则需要从主存读取数据。

地址标签（Address Tag）：每个缓存行存储的是主存中某个位置的副本，缓存通过地址标签识别数据属于主存的哪个位置。处理器提供的地址被用作查询缓存的标签字段，寻找匹配的数据。
缓存行（Line）：每个缓存行不仅存储单个数据字节，还存储数据块。每个数据块包含多个字节的数据，这样即使只访问一个字节，缓存也可以预取附近的字节以加速后续的访问（利用空间局部性）。
数据块（Data Block）：当缓存命中时，整个数据块被返回给处理器。如果未命中，则缓存从主存中读取整个数据块，并将其存放在缓存中供将来使用。

Cache Algorithm (Read)

缓存的读取过程如下：

查找地址：处理器生成一个内存地址，该地址被用来查询缓存中的标签字段，判断所需的数据是否在缓存中。
命中（HIT）：如果地址标签匹配，则发生缓存命中，缓存返回存储的数据副本，处理器直接从缓存读取数据，无需访问主存。
未命中（MISS）：如果地址标签不匹配，发生缓存未命中，此时需要从主存读取数据：
- 缓存请求主存中的对应数据块。
- 主存返回数据块。
- 缓存更新自身，将新数据块存储在合适的缓存行中，同时将数据返回给处理器。

替换策略

当缓存已满且发生缓存未命中时，系统必须决定替换哪一行来存放新读取的数据块。这涉及到缓存替换策略的选择，如LRU（Least Recently Used），FIFO（First In, First Out）等。

总结

缓存通过在处理器和主存之间提供一个快速数据访问层，利用时间和空间局部性，大幅减少处理器对慢速主存的依赖，提升系统性能。

Placement Policy

缓存的放置策略决定了主存中的数据块（block）可以放置在缓存中的哪个位置。根据缓存结构的不同，常见的放置策略有三种：

完全相联（Fully Associative）：
- 数据块可以放置在缓存的任意位置。这种策略最灵活，但实现复杂且查找速度较慢。
- 比如，主存中的第12块可以放置在缓存的任何位置。
组相联（Set-Associative）：
- 缓存被分成多个集合（sets），数据块只能放置在特定集合中的任意位置。
- 例如，2路组相联缓存中，主存中的第12块只能放置在集合0（12 mod 4 = 0）中，但在这个集合内有多个可能的缓存行可选。
直接映射（Direct Mapped）：
- 每个主存数据块只能映射到缓存的一个固定位置，直接由地址决定。
- 比如，主存中的第12块只能映射到缓存中的第4行（12 mod 8 = 4）。虽然这种策略简单且速度快，但会因为固定映射导致冲突。

Direct-Mapped Cache

直接映射缓存的工作原理

在直接映射缓存中，每个数据块只能映射到缓存中的唯一一行，地址被分为三部分：

标签（Tag）：用于标识该块在主存中的具体位置。处理器从主存中取数据时，首先根据标签比较缓存行中的内容是否为所需的数据块。
索引（Index）：用来决定主存数据块在缓存中的具体位置（行号）。索引帮助缓存快速找到数据块对应的行，但不能确定该行中的数据是否是所需的块。
块偏移（Block Offset）：用于从数据块内选择具体的字或字节。每个数据块包含多个字节，块偏移决定了在数据块中具体读取哪一部分数据。

直接映射缓存的命中与未命中

命中（Hit）：如果找到的缓存行中的标签与请求的主存地址匹配，则发生缓存命中，处理器从缓存中直接获取数据。
未命中（Miss）：如果标签不匹配，发生缓存未命中，系统需要从主存中读取该数据块并更新缓存中的对应行。

Direct Map Address Selection

在直接映射缓存中，地址选择非常重要。高位地址位通常用于标签字段，而低位地址位用于索引和块偏移。索引位数决定了缓存的行数，块偏移位数决定了每行缓存中数据块的大小。通过这种分割方式，缓存可以快速定位并验证数据是否存在，进而决定是否需要访问主存。

2-Way Set-Associative Cache

工作原理

在2路组相联缓存中，缓存被分为多个集合（sets），每个集合包含多个缓存行。每个主存数据块根据其地址可以映射到特定的集合，但在该集合内，它可以存放在任意一个缓存行中。

地址分解：
- 地址被分为三部分：标签（Tag）、索引（Index）和块偏移（Block Offset）。
- 索引部分用于确定缓存中的集合。
- 标签部分用来比较集合中的缓存行，确定数据是否在缓存中。
工作流程：
1. 处理器提供内存地址，索引用于定位缓存中的特定集合。
2. 缓存会检查该集合中的所有缓存行，并使用标签进行匹配。
3. 如果有匹配的标签，缓存命中（Hit），返回对应的数据块。
4. 如果没有匹配，则发生未命中（Miss），需要从主存加载数据，并选择集合中的某个缓存行进行替换。
优势：
- 组相联缓存的灵活性较高，相比直接映射缓存更能减少冲突未命中，因为每个集合中有多条缓存行可以存放数据。
- 比如，在2路组相联缓存中，同一个主存块可以存储在集合的两个缓存行中的任意一个。

Fully Associative Cache

工作原理

在完全相联缓存中，主存中的数据块可以存储在缓存中的任何位置，没有固定的映射规则。这使得完全相联缓存的查找灵活性最大化，但实现起来最为复杂。

地址分解：
- 地址同样被分为标签和块偏移，但没有索引部分。
- 每次查找时，缓存必须将提供的标签与缓存中所有缓存行的标签进行比较，以确定数据是否存在。
工作流程：
1. 处理器提供内存地址，缓存中的每一行都会比较它们的标签。
2. 如果找到匹配的标签，则缓存命中，返回对应的数据块。
3. 如果没有匹配，则发生未命中，需要从主存加载数据并选择某个缓存行替换。
优势与劣势：
- 优点：完全相联缓存几乎不会发生冲突未命中，因为任何数据块都可以存放在缓存中的任意行。
- 缺点：由于每次都需要比较所有缓存行的标签，这种结构实现起来复杂且耗时。

对比

2路组相联缓存提供了折中方案，既减少了完全相联缓存的复杂性，又比直接映射缓存更具灵活性。
完全相联缓存则提供了最大的灵活性，但其查找开销也最大。

这两种缓存结构都在不同的应用场景中提供了有效的缓存管理方案，根据系统需求和硬件复杂性进行权衡。