Roofline模型:计算操作强度

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 Byte (即足够大)。然后，我将有(每帧)基本上2次访问RAM和3次失败：

• 1(缓存)读取访问:加载所有3 x[i-1], x[i], x[i+1]
• 1写访问:存储y[i]
• 3次失败(1μl，1相加，1次)

操作强度为ergo。

OI =3触发器/(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]

或者仍然有两个RAM访问。

• 1(缓存)读:加载x[i-1], x[i], x[i+1]
• 1(缓存)写:存储x[i]

因为操作强度OI在两种情况下都是不同的。有人能说出这件事吗？或者澄清一些事情。谢谢

Answer 1

免责声明:到目前为止，我从未听说过roofline性能模型。据我所知，它试图计算算法的“算术强度”的理论界限，即每字节访问数据的失败次数。当N的大小越来越大时，这样的度量对于比较类似的算法可能是有用的，但对于预测现实世界的性能却不是很有帮助。

作为一般的经验法则，现代处理器执行指令的速度比它们能够获取/存储数据的速度要快得多(当数据开始大于缓存的大小时，这种情况会变得更加明显)。因此，与人们可能预期的相反，具有较高算术强度的循环可能比算术强度较低的循环运行得快得多；最重要的是N扩展了所接触的总数据量(只要内存仍然比处理器慢得多(就像现在的普通桌面和服务器系统一样)，这是正确的)。

总之，不幸的是，x86 CPU太复杂，无法用这样简单的模型精确地描述。在访问内存之前，对内存的访问要经过几层缓存(通常是L1、L2和L3)。也许你所有的数据都适合L1 --当你第二次运行你的循环时，可能根本就没有内存访问。

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

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

编译器如何分配寄存器，如果它尝试循环展开，自动矢量化，指令调度模型(为了避免指令之间的数据依赖而交织指令)等，都会影响算法的实际吞吐量。

因此，最后，根据生成的代码、CPU模型、处理的数据量和各种缓存的状态，该算法的延迟将按数量级变化。因此，仅通过检查代码(甚至生成的程序集)无法确定循环的操作强度，因为有许多其他(非线性)因素在起作用。

但是，为了解决您的实际问题，就我所看到的此处概述的定义而言，第二个循环将被计算为每次迭代平均增加一个4字节的访问，因此它的OI将是θ(3N触发器/ 4N字节)。直观地说，这是有意义的，因为缓存已经加载了数据，而写可以直接更改缓存，而不是返回到主内存(数据最终必须写回，但是这一要求与第一个循环没有变化)。