我试图通过阻止循环来提高缓存性能来加速矩阵乘法算法,但无论矩阵大小、块大小如何,非阻塞版本仍然明显更快(我已经尝试了 2 到 200 之间的许多值,效力) 2 及其他)和优化级别。
非阻塞版本:
for(size_t i = 0; i < n; ++i)
{
for(size_t k = 0; k < n; ++k)
{
int r = a[i][k];
for(size_t j = 0; j < n; ++j)
{
c[i][j] += r * b[k][j];
}
}
}
被屏蔽的版本:
for(size_t kk = 0; kk < n; kk += BLOCK)
{
for(size_t jj = 0; jj < n; jj += BLOCK)
{
for(size_t i = 0; i < n; ++i)
{
for(size_t k = kk; k < kk + BLOCK; ++k)
{
int r = a[i][k];
for(size_t j = jj; j < jj + BLOCK; ++j)
{
c[i][j] += r * b[k][j];
}
}
}
}
}
我还有一个 bijk 版本和一个 6 循环 bikj 版本,但它们的性能都优于非阻塞版本,我不明白为什么会发生这种情况。我遇到的每一篇论文和教程似乎都表明受阻止的版本应该明显更快。如果重要的话,我在 Core i5 上运行它。
尝试仅在一维上进行阻塞,而不是在两个维度上进行阻塞。
矩阵乘法详尽地处理两个矩阵中的元素。左侧矩阵上的每个行向量都会被重复处理,并放入右侧矩阵的连续列中。
如果矩阵不能同时装入缓存,则某些数据最终将不可避免地被多次加载。
我们能做的就是分解操作,以便我们一次处理大约缓存大小的数据量。我们希望缓存左操作数中的行向量,因为它会重复应用于多个列。但是我们应该(一次)只获取足够的列以保持在缓存的限制内。例如,如果我们只能获取 25% 的列,则意味着我们必须传递行向量四次。我们最终从内存中加载左矩阵四次,而右矩阵仅加载一次。
(如果要多次加载任何内容,则应该是左侧的行向量,因为它们在内存中是平坦的,这受益于突发加载。许多缓存架构可以比从内存更快地执行从内存到相邻缓存行的突发加载随机访问加载。如果正确的矩阵以列优先顺序存储,那就更好了:然后我们在平面数组之间进行叉积,它可以很好地预取到内存中。)
我们也不要忘记输出矩阵。输出矩阵也占用缓存中的空间。
我怀疑 2D 分块方法的一个缺陷是输出矩阵的每个元素都依赖于两个输入:左侧矩阵中的整个行和右侧矩阵中的整个列。如果矩阵被分块访问,则意味着每个目标元素被访问多次以累积部分结果。
如果我们做一个完整的行列点积,我们就不必访问c[i][j]
不止一次;一旦我们采取专栏j
进入行i
,我们就完成了c[i][j]
.
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)