algorithm - 阻塞的矩阵乘法运算可以优化地减少到缓存上的 2*N^3/B^3+N^2/B^2 读取吗？

Question

根据这篇论文https://suif.stanford.edu/papers/lam-asplos91.pdf，在最坏的情况（例如 3 个寄存器）。这可以通过下面的伪代码来说明：

for i to N:
    for k to N: // X[i][k] is accessed N*N times and is loaded to register 1
        r = X[i][k] 
        for j to N: // Z[i][j] & Y[k][j] are accessed N*N*N times and are loaded to register 2 and 3 respectively
            Z[i][j] += r * Y[k][j] 
        

在论文中，它提到如果我们有一个缓存大小来保存 Y 的 BxB 子矩阵加上一个 B 大小的缓存来保存 Z[i][0:B] 的结果（为简单起见，我们假设 N = 0（mod B))，数据访问次数减少到 2*N^3/B+N^2，因为每次对 Y 和 Z 的数据访问在下一次访问之前被重用 B 次：

for i to N:
for kk to N with stride of B:
for k to kk:
    r = X[i][k] // still N*N times of access to store value to register 1
    for jj to N with stride of B: // cache loads row Z[i][jj:jj+B] and submatrix Y[kk:kk+B][jj:jj+B]; equivalent to N^3/B times of access for both Z & Y
        Z[i][jj:jj+B] += r * Y[kk:kk+B][jj:jj+B]
        

那么，如果我们有 3 个 BxB 子矩阵的空间，那么数据访问的数量最好减少到 2*N^3/B^3+N^2/B^2？

for ii to N with stride of B:
for kk to N with stride of B: // cache loads submatrix X[ii:ii+B][kk:kk+B]; equivalent to (N/B)^2 times of access
    r = X[ii:ii+B][kk:kk+B] 
    for jj to N with stride of B: // cache loads submatrices Z[ii:ii+B][jj:jj+B] and Y[kk:kk+B][jj:jj+B]; equivalent to (N/B)^3 times of access for both Z & Y
        Z[ii:ii+B][jj:jj+B] += r * Y[kk:kk+B][jj:jj+B]
        

当然，这会使用更多的缓存空间，但实际上，这是否比以前的解决方案在功耗/执行时间方面更优化？

标签： algorithmcachingoptimization