8

假设我有一个这样的玩具循环

float x[N];
float y[N];
for (int i = 1; i < N-1; i++)
    y[i] = a*(x[i-1] - x[i] + x[i+1])

我假设我的缓存线是64 字节（即足够大）。然后我将（每帧）基本上 2 次访问 RAM 和 3 次 FLOP：

  • 1（缓存）读取访问：加载所有 3x[i-1], x[i], x[i+1]
  • 1个写访问：存储y[i]
  • 3 FLOP (1 mul, 1 add, 1 sub)

操作强度是ergo

OI = 3 FLOP/(2 * 4 字节)

现在如果我做这样的事情会发生什么

float x[N];
for (int i = 1; i < N-1; i++)
    x[i] = a*(x[i-1] - x[i] + x[i+1])

请注意，现在没有y了。这是否意味着我现在只有一个 RAM 访问权限

  • 1（缓存）读/写：加载x[i-1], x[i], x[i+1]，存储x[i]

或仍然有 2 个 RAM 访问

  • 1（缓存）读取：加载 x[i-1], x[i], x[i+1]
  • 1（缓存）写入：存储x[i]

因为在任何一种情况下，操作强度OI都会不同。任何人都可以谈谈这件事吗？或者也许澄清一些事情。谢谢

4

1 回答 1

3

免责声明：直到今天，我才听说过车顶线性能模型。据我所知，它试图计算算法“算术强度”的理论界限，即每访问数据字节的 FLOPS 数。随着规模变大，这样的度量可能有助于比较相似的算法N，但对于预测现实世界的性能不是很有帮助。

作为一般经验法则，现代处理器执行指令的速度比它们获取/存储数据的速度要快得多（随着数据开始增长到大于缓存的大小，这变得更加明显）。因此，与人们预期的相反，具有较高算术强度的循环可能比具有较低算术强度的循环运行得快得多。对于规模而言，最重要的N是所触及的数据总量（只要内存仍然比处理器慢得多，就像当今常见的台式机和服务器系统一样）。

简而言之，不幸的是，x86 CPU 过于复杂，无法用如此简单的模型准确描述。在访问 RAM 之前，对内存的访问要经过几层缓存（通常是 L1、L2 和 L3）。也许您的所有数据都适合 L1 - 第二次运行循环时可能根本没有 RAM 访问。

而且不仅仅是数据缓存。不要忘记代码也在内存中，并且必须加载到指令缓存中。每个读/写也是从/到一个虚拟地址完成的，硬件 TLB 支持该地址（在极端情况下，这可能会触发页面错误，例如，导致操作系统在循环中间将页面写入磁盘）。所有这一切都假设您的程序将硬件全部独占（在非实时操作系统中，情况并非如此，因为其他进程和线程正在竞争相同的有限资源）。

最后，执行本身不是（直接）通过内存读取和写入完成的，而是首先将数据加载到寄存器中（然后存储结果）。

编译器如何分配寄存器，如果它尝试循环展开，自动向量化，指令调度模型（交错指令以避免指令之间的数据依赖）等也会影响算法的实际吞吐量。

因此，最后，根据生成的代码、CPU 型号、处理的数据量以及各种缓存的状态，算法的延迟会发生数量级的变化。因此，循环的操作强度不能通过单独检查代码（甚至生成的程序集）来确定，因为还有许多其他（非线性）因素在起作用。

但是，为了解决您的实际问题，据我在这里概述的定义所见，第二个循环平均每次迭代将计为一个额外的 4 字节访问，因此它的 OI 将是 θ(3N FLOPS / 4N 字节）。直观地说，这是有道理的，因为缓存已经加载了数据，并且写入可以直接更改缓存而不是回到主内存（数据最终必须写回，但是这个要求与第一次相比没有改变环形）。

于 2016-11-23T01:00:27.600 回答