车顶线模型:计算操作强度

Question

说我有这样的玩具循环

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(缓存)读访问:加载全部3 x[i-1], x[i], x[i+1]
• 1写访问:存储 y[i]
• 3 FLOP(1 mul,1 add,1 sub)

操作强度是错误的

OI = 3 FLOP /(2*4 BYTE)

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

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都是不同的.谁能说出这个呢？或者澄清一些事情.谢谢

Answer 1

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

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n\n\n\n

不过，为了解决您的实际问题，据我从此处概述的定义来看，第二个循环将算作平均每次迭代的单个附加 4 字节访问，因此其 OI 将为 \xce\xb8(3N FLOPS / 4N 字节）。直观上，这是有道理的，因为缓存已经加载了数据，并且写入可以直接更改缓存，而不是返回到主内存（但是，数据最终必须写回，但该要求与第一次相同）环形）。

\n