使用 Algorithmica 进行内存组织是一个持续闪耀的资源。

https://t.co/hvIj8m3S5l https://t.co/xItHdn30pv

RAM & CPU 缓存 - Algorithmica

来源：https://en.algorithmica.org/hpc/cpu-cache/ 在上一章（https://en.algorithmica.org/hpc/external-memory）中，我们从理论角度研究了计算机内存，使用了外部内存模型（https://en.algorithmica.org/hpc/external-memory/model）来评估内存密集型算法的性能。

虽然外部内存模型对于涉及 HDD 和网络存储的计算来说或多或少是准确的（因为对内存中值的算术操作成本相对于外部 I/O 操作可以忽略不计），但对于缓存层次结构中的较低层级来说，它过于粗糙了，因为这些层级上的操作成本变得具有可比性。

为了对内存中的算法进行更细粒度的优化，我们必须开始考虑 CPU 缓存系统的许多具体细节。与其研读大量枯燥的 Intel 文档（其中包含干巴巴的规格和理论上可达到的极限），我们将通过运行许多小型基准测试程序来实验性地估计这些参数，这些测试的访问模式类似于实际代码中经常出现的模式。

实验设置

和之前一样，我将在 Ryzen 7 4700U 上运行所有实验，这是一款“Zen 2”CPU，具有以下与缓存相关的主要规格：

• 8 个物理核心（无超线程），主频 2GHz（加速模式下为 4.1GHz——我们禁用了该模式（https://en.algorithmica.org/hpc/profiling/noise））；
• 256K 8 路组相联 L1 数据缓存，即每核心 32K；
• 4M 8 路组相联 L2 缓存，即每核心 512K；
• 8M 16 路组相联 L3 缓存，在 8 个核心之间共享（https://en.algorithmica.org/hpc/cpu-cache/sharing）；
• 16GB（2x8G）DDR4 RAM，频率 2667MHz。

你可以通过运行 dmidecode -t cache 或 lshw -class memory（Linux）或安装 CPU-Z（https://en.wikipedia.org/wiki/CPU-Z）（Windows）来与自己的硬件进行比较。你还可以在 WikiChip（https://en.wikichip.org/wiki/amd/ryzen_7/4700u）和 7-CPU（https://www.7-cpu.com/cpu/Zen2.html）上找到有关 CPU 的更多详细信息。并非所有结论都适用于所有 CPU 平台。

由于难以阻止编译器优化掉未使用的值（https://en.algorithmica.org/hpc/profiling/noise/），本文中的代码片段为了说明目的做了略微简化。如果你想自行重现，请查看代码仓库（https://github.com/sslotin/amh-code/tree/main/cpu-cache）。

致谢

本章的灵感来源于 Igor Ostrovsky 的《处理器缓存效果画廊》（http://igoro.com/archive/gallery-of-processor-cache-effects/）和 Ulrich Drepper 的《每个程序员都应该了解的内存知识》（https://people.freebsd.org/~lstewart/articles/cpumemory.pdf），这两篇文章都可以作为很好的补充阅读材料。