31

我在理解参考位置时遇到问题。谁能帮助我理解它的含义和含义，

  • 参考空间位置
  • 参考的时间局部性
4

4 回答 4

55

如果您的计算机充满了超高速内存，这无关紧要。

但不幸的是，情况并非如此，计算机内存看起来像这样1：

+----------+
| CPU      |  <<-- Our beloved CPU, superfast and always hungry for more data.
+----------+
|L1 - Cache|  <<-- ~4 CPU-cycles access latency (very fast), 2 loads/clock throughput
+----------+
|L2 - Cache|  <<-- ~12 CPU-cycles access latency (fast)
+----+-----+
     |
+----------+
|L3 - Cache|  <<-- ~35 CPU-cycles access latency (medium)
+----+-----+       (usually shared between CPU-cores)
     |
     |   <<-- This thin wire is the memory bus, it has limited bandwidth.
+----+-----+
| main-mem |  <<-- ~100 CPU-cycles access latency (slow)
+----+-----+  <<-- The main memory is big but slow (because we are cheap-skates)
     |
     |   <<-- Even slower wire to the harddisk
+----+-----+
| harddisk | <<-- Works at 0,001% of CPU speed
+----------+

空间局部性
在此图中，数据离 CPU 越近，CPU 获取数据的速度就越快。
这与Spacial Locality. 如果数据在内存中靠得很近，则数据具有空间局部性。
由于我们是 RAM 并不是真正的随机存取，而是真正Slow if random, less slow if accessed sequentially Access Memory的 SIRLSIAS-AM。DDR SDRAM 为一个读取或写入命令传输整个 32 或 64 字节的突发。
这就是为什么将相关数据保持在一起是明智的，这样您就可以顺序读取一堆数据并节省时间。

时间局部性
数据保留在主内存中，但不能保留在缓存中，否则缓存将不再有用。只能在缓存中找到最近使用的数据；旧数据被推出。
这与temporal locality. 如果同时访问数据，则数据具有很强的时间局部性。
这很重要，因为如果项目 A 在缓存中（好），那么项目 B（对 A 具有很强的时间局部性）很可能也在缓存中。

脚注1：

这是从各种 cpu估计的延迟周期计数的简化，但为典型 CPU 提供了正确的数量级概念。

实际上，延迟和带宽是独立的因素，对于远离 CPU 的内存，延迟更难改善。但是在某些情况下，硬件预取和/或乱序执行可以隐藏延迟，例如遍历数组。由于不可预测的访问模式，有效的内存吞吐量可能远低于 L1d 缓存的 10%。

例如，L2 缓存带宽不一定比 L1d 带宽差 3 倍。（但如果您使用 AVX SIMD 在 Haswell 或 Zen2 CPU 上从 L1d 的每个时钟周期执行 2x 32 字节加载，则它会更低。）

这个简化版本还省略了 TLB 效应（页面粒度局部性）和 DRAM 页面局部性。（与虚拟内存页面不同）。要更深入地了解内存硬件和调整软件，请参阅每个程序员应该了解的内存知识？

相关：为什么在大多数处理器中，L1 缓存的大小都小于 L2 缓存的大小？解释了为什么需要多级缓存层次结构来获得我们想要的延迟/带宽和容量（和命中率）的组合。

一个巨大的快速 L1 数据高速缓存会非常耗电，而且在延迟低的情况下仍无法实现现代高性能 CPU 中的小型快速 L1d 高速缓存。

在多核 CPU 中，L1i/L1d 和 L2 高速缓存通常是每核专用高速缓存，具有共享的 L3 高速缓存。不同的内核必须相互竞争 L3 和内存带宽，但每个内核都有自己的 L1 和 L2 带宽。看看缓存怎么能这么快？对于双核 3GHz IvyBridge CPU 的基准测试结果：两个内核上的总 L1d 缓存读取带宽为 186 GB/s，而两个内核均处于活动状态时 DRAM 读取带宽为 9.6 GB/s。（因此，单核的内存 = 10% L1d 对于那一代台式机 CPU 来说是一个很好的带宽估计，只有 128 位 SIMD 加载/存储数据路径）。1.4 ns 的 L1d 延迟与 72 ns 的 DRAM 延迟

于 2011-10-03T18:20:10.843 回答
9
  • 这是一个原则，即如果程序引用了某些变量，则很有可能再次引用相同的变量（稍后时间 - 也称为时间局部性）。
  • 也很有可能更快地引用内存中的任何连续存储（空间局部性）

在此处输入图像描述

于 2018-03-16T16:10:01.357 回答
5

首先，请注意，这些概念不是普遍规律，它们是对常见代码行为形式的观察，允许 CPU 设计人员优化他们的系统，以便在大多数程序上执行得更好。同时，这些是程序员寻求在他们的程序中采用的属性，因为他们知道这就是内存系统的构建方式，也是 CPU 设计人员优化的目标。

空间局部性是指某些（实际上是大多数）应用程序以顺序或跨步方式访问内存的属性。这通常源于最基本的数据结构构建块是数组和结构，它们都将多个元素相邻地存储在内存中。事实上，许多语义链接的数据结构（图、树、跳过列表）的实现都在内部使用数组来提高性能。

空间局部性允许 CPU 提高内存访问性能，这要归功于：

  • 内存缓存机制（如缓存、页表、内存控制器页面）在设计上已经比单次访问所需的更大。这意味着，一旦您为从远内存或较低级别的缓存中获取数据而付出了内存代价，您可以从中消耗的额外数据越多，您的利用率就越高。

  • 目前几乎所有 CPU 上都存在的硬件预取通常涵盖空间访问。每次您获取 addr X 时，预取器可能会获取下一个缓存行，并且可能会获取更前面的其他缓存行。如果程序表现出恒定的步幅，大多数 CPU 也能够检测到这一点并推断以预取相同步幅的更进一步的步骤。现代空间预取器甚至可以预测可变的重复步幅（例如VLDP、SPP）

时间局部性是指内存访问或访问模式重复自身的属性。在最基本的形式中，这可能意味着如果地址 X 曾经被访问过，它也可能在将来被访问，但是由于缓存已经在一定时间内存储了最近的数据，这种形式不太有趣（尽管某些 CPU 上的机制旨在预测哪些行可能很快会再次被访问，哪些不会）。

一种更有趣的时间局部性形式是，观察到一次的两个（或多个）时间上相邻的访问可能会再次一起重复。也就是说 - 如果您曾经访问过地址 A 并在该地址 B 之后不久，并且稍后 CPU 检测到对地址 A 的另一次访问 - 它可能会预测您可能很快会再次访问 B，并继续提前预取它。旨在提取和预测此类关系的预取器（时间预取器）通常使用相对较大的存储空间来记录许多此类关系。（参见马尔可夫预取，以及最近的ISB、STMS、Domino等。）

顺便说一句，这些概念绝不是排他性的，一个程序可以展示两种类型的位置（以及其他更不规则的形式）。有时，两者甚至在术语时空局部性下组合在一起以表示局部性的“常见”形式，或者时间相关性连接空间构造的组合形式（例如地址增量总是跟随另一个地址增量）。

于 2019-06-23T15:08:06.317 回答
0

参考的时间局部性 - 最近使用过的内存位置更有可能再次被访问。例如，循环中的变量。同一组变量（内存位置的符号名称）用于循环的某些i次迭代。

参考的空间局部性 - 靠近当前访问的内存位置的内存位置更有可能被访问。例如，如果您声明 int a,b; 浮动c，d；编译器可能会为它们分配连续的内存位置。因此，如果正在使用 a，那么很可能在不久的将来会使用 b、c 或 d。这是 32 或 64 字节的缓存线如何提供帮助的一种方式。它们的大小不是 4 或 8 字节（典型的 int、float、long 和 double 变量大小）。

于 2020-08-14T09:52:10.727 回答