我试图理解为什么可以使用数组(例如矩阵乘法(的程序以某种方式编写以利用缓存的空间局部性。
-
缓存提供的空间局部性是指虚拟内存、物理内存或两者中的局部性？ 当计算机系统将数据块从主内存带到 CPU 缓存时，它是否会将虚拟或物理上连续的数据对象带入 CPU 缓存？
-
当我们非动态或动态(通过 malloc(((定义数组或结构的对象时，连续分配这样的数组或对象是否正确？"连续"是指虚拟内存还是物理内存，还是两者兼而有之？
如果缓存的空间局部性是针对物理内存的，而不一定是虚拟内存，并且操作系统可以分配给 C 程序，而不一定是物理上连续的数组，那么我们如何编写程序来利用缓存的空间局部性？
谢谢。
1(实际上两者都有，但为什么是微妙的。
2(缓存对称为行的数据块进行操作，并且行内的字节在虚拟和物理上都是连续的。 典型的行大小为 16,32,64 字节。 如果两个相邻的缓存行位于同一页面中，则它们必须在物理上连续。 典型的页面大小为 4,8,16 K。 因此，具有 32 字节缓存行和 4K 基本页面的计算机每页有 128 行。
3,4(在C中，结构的成员，联合或数组实际上是连续的。 这取决于操作系统是否在物理上是连续的。
(1( 第 2 部分：还有另一个称为翻译后备缓冲区 (TLB( 的缓存，它保留最近使用的页面映射。 如果没有这样的机制，每个内存引用都需要两个物理内存引用：一个用于加载内存地址转换，然后应用于生成所需的内存引用。
假设你的TLB有32个条目(现在非常小(，并且你有这样的数组的代码：
char *p;
for (p = array; p < array + 4096; p++) {
char *q;
for (q = p; q < p + 32 * 4096; q += 4096) {
*q += 1;
}
}
您将有效地模仿没有TLB的机器，因为"*q"的每个内存引用都会在TLB中丢失，并且需要从内存中获取。
如果你知道缓存关联性和大小的细节，你可以为内存缓存构建一个类似的病理案例;或者如果你不走运，你可能会不小心撞到它，想知道为什么你的程序这么慢。
假设您使用的编程语言仅支持一维数组。假设您有一个 3x3 矩阵。 您通过以下方式实现二维数组
a [i, j] = a (i*3 + j)
如果您构建阵列访问。如果你遍历数组的元素，如果你的外循环索引是 i，你的内循环索引是 j，你按顺序访问：
a(0), a(1), a(2), ..... a(8)
如果将 j 作为外部循环索引，将 i 作为内部循环索引，则按顺序访问：
a(0), a(3), a(6), a(1), a(4), a(7), a(2), a(5), a(8)
你在阵列中跳来跳去。这种跳转会导致缓存严重破坏，因为缓存希望成组地获取内存。
这个问题在具有多维数组的编程语言中仍然存在。在这种情况下，编译器会将多个维度转换为单个维度。您遇到的问题是不同的编程语言以不同的方式处理下标的顺序。