块矩阵的矩阵乘法最好块大小值

Question

我想要做的块矩阵的矩阵乘法用下面的C code.In这种方法，大小BLOCK_SIZE的块被加载到高速缓存最快，以减少计算期间存储器的流量。

void bMMikj(double **A , double **B , double ** C , int m, int n , int p , int BLOCK_SIZE){

   int i, j , jj, k , kk ;
   register double jjTempMin = 0.0 , kkTempMin = 0.0;

   for (jj=0; jj<n; jj+= BLOCK_SIZE) {
       jjTempMin = min(jj+ BLOCK_SIZE,n); 
       for (kk=0; kk<n; kk+= BLOCK_SIZE) {
           kkTempMin = min(kk+ BLOCK_SIZE,n); 
           for (i=0; i<n; i++) {
               for (k = kk ; k < kkTempMin ; k++) {
                   for (j=jj; j < jjTempMin; j++) {
                      C[i][j]  +=  A[i][k] * B[k][j];
                   }
               }
           }
      }
   }
}

我搜索关于BLOCK_SIZE的最合适的值，我发现BLOCK_SIZE <= sqrt( M_fast / 3 )这里M_fast是L1缓存。

在我的电脑，我有两个L1缓存与here工具中显示lstopo。 下面，我使用启发式像BLOCK_SIZE的4开始和8为1000次数的增加值，以矩阵大小的不同值。

跳频以获得最佳的MFLOPS（或最少的时间为乘法）值和相应的BLOCK_SIZE值将是最好的合适的值。

这对于测试的代码：

int BLOCK_SIZE = 4;
int m , n , p;
m = n = p = 1024; /* This value is also changed
                     and all the matrices are square, for simplicity
                     */
for(int i=0;i< 1000; i++ , BLOCK_SIZE += 8) {
    # aClock.start();
    test_bMMikj(A , B ,  C , loc_n , loc_n , loc_n ,BLOCK_SIZE);
    # aClock.stop();
}

测试给了我不同的值，每个矩阵大小并且不与formula.The计算机模型同意是“英特尔®酷睿™i5-3320M CPU @ 2.60GHz×4” 3.8GiB这里是Intel specification

另一个问题 ： 如果我有两个L1高速缓存，就像我在here，应该我认为BLOCK_SIZE相对于他们中的一个或两个的总和？

Answer 1

1.分块矩阵乘法：我们的想法是通过重用当前存储在缓存中的数据块，以最大限度地利用时间和空间局部性的。您的相同的代码是不正确，因为它仅含有5环;块应该有6，是这样的：

for(int ii=0; ii<N; ii+=stride)
{
    for(int jj=0; jj<N; jj+=stride)
    {
        for(int kk=0; kk<N; kk+=stride)
        {
            for(int i=ii; i<ii+stride; ++i)
            {
                for(int j=jj; j<jj+stride; ++j)
                {
                    for(int k=kk; k<kk+stride; ++k) C[i][j] += A[i][k]*B[k][j];
                }
            }               
        }
    }
}

起初保持N和步幅为简单的2权力。该IJK模式不是最优的，你要么去KIJ或ikj，对here细节。不同的访问模式有不同的表现，你应该尝试IJK的所有排列。

2.座/步幅大小：人们一般说，你最快的高速缓存（L1）应该能够容纳3块（步幅*步幅）在矩阵乘法的情况下，最佳的性能数据，但它总是好的实验，发现它为自己。 8增大步幅可能不是一个好主意，尽量保持它，因为大多数块大小以这种方式增加的大小2的幂。而你只能看数据缓存（L1D），而你的情况是32KB。