c - 缓存阻塞实际上是如何提高性能的?
问题描述
我正在阅读有关此英特尔页面上的缓存阻塞的信息。
它说:
阻塞是一种众所周知的优化技术,可以帮助避免许多应用程序中的内存带宽瓶颈。阻塞背后的关键思想是通过确保数据在多次使用中保留在缓存中来利用应用程序中可用的固有数据重用。
提供一个例子
for (body1 = 0; body1 < NBODIES; body1 ++) { for (body2=0; body2 < NBODIES; body2++) { OUT[body1] += compute(body1, body2); } }
在此示例中,数据 (body2) 从内存中流式传输。假设 NBODIES 很大,我们将无法在缓存中重用。此应用程序受内存带宽限制。该应用程序将以内存速度运行到 CPU 速度,低于最佳速度。
优化为
for (body2 = 0; body2 < NBODIES; body2 += BLOCK) { for (body1=0; body1 < NBODIES; body1 ++) { for (body22=0; body22 < BLOCK; body22 ++) { OUT[body1] += compute(body1, body2 + body22); } } }
阻塞代码...是通过将 body2 循环拆分为一个在多个 BLOCK 中迭代主体的外部循环和一个在块内迭代元素的内部 body22 循环,并将 body1 和 body2 循环交错而获得的。此代码在 body1 循环的多次迭代中重用一组 BLOCK body2 值。如果选择 BLOCK 以使这组值适合高速缓存,则内存流量会减少一个 BLOCK 因子。
老实说,我不明白随附的解释。
我也不明白内存流量是如何降低的,以及为什么被阻止的例子会更快。
请有人可以帮助解释缓存阻塞以及它实际上如何加速循环?
维基百科同样有一个例子:
for (i=0; i<N; ++i) { ... }
可以通过将其替换为块大小 B 来阻止它
for (j=0; j<N; j+=B) { for (i=j; i<min(N, j+B); ++i) { .... } }
我不知道为什么这会更快。
为什么这会利用缓存?
解决方案
那篇英特尔论文很糟糕,因为它没有明确索引body2
与数据在内存中的位置之间的关联,或者与内存中的数据之间的关联body1
。这个想法是OUT[body1]
要使用来自同一个缓存块的多个元素来获取body1
. 然而,这些连续值的使用body1
不会一个接一个地出现。它们是分散的,因为整个循环body2
都在它们之间执行。据推测,使用compute(body1, body2)
会导致根据body2
值使用各种内存。
这个概念是,在body2
循环过程中,内存中的许多不同位置将被访问,与之关联的缓存块OUT[body1]
将从缓存中被逐出,因此,何时body1
递增到下一个值,但OUT[body1]
仍将在同一缓存块,该块不再在缓存中,必须再次加载。所以这是浪费。
将源代码更改为:
for (body2 = 0; body2 < NBODIES; body2 += BLOCK) {
for (body1=0; body1 < NBODIES; body1 ++) {
for (body22=0; body22 < BLOCK; body22 ++) {
OUT[body1] += compute(body1, body2 + body22);
}}
// Note: A closing "}" is missing in the original.
compute(body1, something)
通过在更改之前处理更少的实例来解决该问题body1
。如果BLOCK
设置得足够小,则与之关联的缓存块OUT[body1]
仍在缓存中,不需要从内存中重新加载。因此,在内部循环期间:
for (body1=0; body1 < NBODIES; body1 ++) {
for (body22=0; body22 < BLOCK; body22 ++) {
OUT[body1] += compute(body1, body2 + body22);
}}
每个缓存块OUT[body1]
只从内存中加载一次并写入内存一次。
当然,这些内循环是在一个新的外循环 onbody2
内,所以内循环会被执行NBODIES/BLOCK
多次(本文忽略了如果NOBODIES
不能被 整除的块碎片,BLOCK
我也会),所以缓存块OUT[body1]
仍然有被重新加载NBODIES/BLOCK
次数,但这比重新加载NBODIES
次数要好,这发生在原始代码中。
推荐阅读
- php - 如果产品属于特定类别,则按用户 ID 查询唯一的 WooCommerce 销售额
- haskell - 无法创建提供会话 cookie 的经过身份验证的仆人客户端
- python - 表达式 (0==0<1<2<3>2>1>0==0) 在 python 中的计算结果如何?
- kotlin - Junit - 如何以字符串形式获取测试结果?
- react-native - 反应原生视图转换器
- azure - 如何将海量产品连接到azure?
- r - 如何网页抓取文本字段/下拉菜单组合?
- binance - 在币安的python api中进行购买时出错,这个错误发生在testnet中
- node.js - 在 AWS 中部署后 Web 套接字连接失败
- python-3.x - 在 python 中的正则表达式匹配前添加分隔符