CacheLab - Optimizing Matrix Transpose

Optimizing Matrix Transpose

Matrix Transpose 还算一个常见的问题. cache lab handout 也写出了最常见和 easy 的解法，但这并不是最memory friendly的。

先来读懂文档：

Matrices are stored in memory in a row major order.

If the entire matrix can’t fit in the cache, then after the cache is full with all the elements it can load. The next elements will evict the existing elements of the cache.

Example:- 4x4 Matrix of integers and a 32 byte cache.

The third row will evict the first row!

前两个row 4 * 2 * 4 = 32 byte， int 4 byte，所以满了自然就会挤出去。

The first row of Matrix A evicts the first row of Matrix B

Caches are memory aligned.

Matrix A and B are stored in memory at addresses such that both the first elements align to the same place in cache!

Diagonal elements evict each other.

这看起来很难的样子，同时也解答了为什么在给的例子中，我们这样来做计算：

void trans(int M, int N, int A[N][M], int B[M][N])
{
    int i, j, tmp;

    for (i = 0; i < N; i++) {
        for (j = 0; j < M; j++) {
            tmp = A[i][j];
            B[j][i] = tmp;
        }
    }    

}

就是引入一个temp。 A 是B 么？对于 M = N 的（此处存疑）因为说他们在内存中相同的位置？

再看 cache 的规格：

E = 1, S = 32, B = 32, total = 1 kilobyte

然后针对于 M = 32, N = 32, 一开始 load 的状况是：

A[0][0] ... A[0][7]
A[0][8] ... A[0][15]
A[0][16]... A[0][23]
A[0][24]... A[0][31]
.
.
A[7][24] ... A[7][31]

然后比如我们加载进 B 的哪一行之后，它会 evict 其中一行。

然后再看提示：

最多12个int variable
array A 我们虽然不能改变，但是 array B 我们可以随意

然我们从最简单的实验开始吧，先就按照写的例子来填 trans_submit，结果：

Function 0 (2 total)
Step 1: Validating and generating memory traces
Step 2: Evaluating performance (s=5, E=1, b=5)
func 0 (Transpose submission): hits:870, misses:1183, evictions:1151

Function 1 (2 total)
Step 1: Validating and generating memory traces
Step 2: Evaluating performance (s=5, E=1, b=5)
func 1 (Simple row-wise scan transpose): hits:870, misses:1183, evictions:1151

Summary for official submission (func 0): correctness=1 misses=1183

TEST_TRANS_RESULTS=1:1183

先来测试次简单的：既然我们允许12个local variable，每个block可以存8个int，那么我们每次把8个记住，然后来填B， 🤣，然而这样写出来的代码为什么misses比之前更多了呢？？？

思路二：

    t0 = A[0][0];
    t1 = A[0][1];
    t2 = A[0][2];
    t3 = A[0][3];
    t4 = A[1][1];
    t5 = A[1][2];
    t6 = A[1][3];
    t7 = A[2][2];
    t8 = A[2][3];
    t9 = A[3][3];

    B[0][0] = t0;
    for(j = 1; j < 8; j++)
      B[0][j] = A[j][0];
    B[1][0] = t1;
    B[1][1] = t4;
    for(j = 2; j < 8; j++)
      B[1][j] = A[j][1];

    B[2][0] = t2;
    B[2][1] = t5;
    B[2][2] = t7;
    for(j = 3; j < 8; j++)
      B[2][j] = A[j][2];

    B[3][0] = t3;
    B[3][1] = t6;
    B[3][2] = t8;
    B[3][3] = t9;
    for(j = 4; j < 8; j++)
      B[3][j] = A[j][3];

这样操作下来之后明显会减少一些miss。我们 A[0~3] 被替换为 B[0~3], 剩余 A[4~7]，注意A[7]就一部分在cache里面,这里还有疑问，就是 local variable 也是在cache里面么？知道它一定在stack上，但它也是占据了cache的空间么？（存疑

这个时候如果我们再来加载 A[8]，是否我们会将B evict，然后我们可以用类似的方法来处理B[0][8]~B[0][15], B[1][8]~B[1][15], B[2][8]~B[2][15]...

不过即使这样做，A[4] ~ A[7]的填也麻烦，按照这样的思路拼凑出来的代码可以做到 misses 700 some what，但是这个完全达不到要求，而且很僵化，我只考虑了 32 * 32

所以来读一读关于matrix transpose的 Q & A.

首先，发现有这个：

A Cache Efficient Matrix Transpose Program?

在 wikipedia 的这篇 Cache-oblivious algorithm 也提到了 matrix transpose的例子，甚至还画了示意图。

先看问题中的代码：

 for( int i = 0; i < n; i++ )

    for( int j = 0; j < n; j++ )

      destination[j+i*n] = source[i+j*n];

这里假设 n = 4, 那么我们依次：

i = 0
- dst[0] = src[0]
- dst[1] = src[4]
- dst[2] = src[8]
- dst[3] = src[12]
i = 1
- dst[4] = src[1]
- dst[5] = src[5]
- dst[6] = src[9]
- dst[7] = src[13]

无需继续验证，如果 dst 和 src 都被装入了 cache 中，那么这将是非常cache 友好的。

如果不是方形矩阵，维度是 M * N ,我们也可以写出类似代码：

for (int i = 0 ; i < N; i++)
  for (int j = 0; j < M; j++)
    dst[j + i * N] = src[i + j * M]

然后来尝试明白这个top voted answer给的算法。所以其实还是要先回到课上给的matrix 相乘的例子。

for (int i = 0; i < n; i += blocksize) {
    for (int j = 0; j < n; j += blocksize) {
        // transpose the block beginning at [i,j]
        for (int k = i; k < i + blocksize; ++k) {
            for (int l = j; l < j + blocksize; ++l) {
                dst[k + l*n] = src[l + k*n];
            }
        }
    }
}

根据**改写的代码：

void transpose_submit(int M, int N, int A[N][M], int B[M][N]){

    int blocksize = 8;
    int k, l;
    int i, j; 

    for (i = 0; i < M; i += blocksize)
    {
        for (j = 0; j < N; j += blocksize)
        {
            for (k = i; k < i + blocksize && k < M; ++k)
            {
                for (l = j; l < j + blocksize && l < N; ++l)
                {
                    B[k][l] = A[l][k];
                }
            }
        }
    }
}

结果：

Function 0 (2 total)
Step 1: Validating and generating memory traces
Step 2: Evaluating performance (s=5, E=1, b=5)
func 0 (Transpose submission): hits:1710, misses:343, evictions:311

Function 1 (2 total)
Step 1: Validating and generating memory traces
Step 2: Evaluating performance (s=5, E=1, b=5)
func 1 (Simple row-wise scan transpose): hits:870, misses:1183, evictions:1151

Summary for official submission (func 0): correctness=1 misses=343

TEST_TRANS_RESULTS=1:343

比 1183 好很多了。但是没有达到 doc 的要求，同时，发现 blocksize = 8 对于 M = 64, N = 64 的时候完全没有改善

32×32: 8 points if m<300,0 points if m>600
64×64:8 points if m<1,300,0 points if m>2,000
61×67: 10 points if m<2,000,0 points if m>3,000

blocksize = 4 32* 32 ：misses:487

blocksize = 4 64 * 64 ：misses:1891

blocksize = 4 61 * 67 ： misses:2425

当然这里还有一些trick，如果是硬朝着减少miss方向努力的话，针对不同的 M 和 N 调整blocksize，然后如果是对角线我们就不用去改变它。

可以参考cachelab

实际上看这段代码，情况会更清楚，突然，一页slides make sense了：

假设 block size 是 8 byte

Matrix A

[1] [2] 3 4
 5  6   7 8
 9 10   11 12
 13 14 15 16
 
 此时 matrix B :
 
 [1]
 [2]

接下来处理 5 和 6 更好，因为 1/2 旁边已经加载进去，如果处理 3/4的话我们都要重新加载，更多 miss，这也是我们为什么用block来处理的原因吧。

实际上我们看别人的代码，也更清晰，它的两层 loop 针对 A 是先走第一列的 block，然后走第二列的block：

1 5 . .
2 6 . .
3 7 . .
4 8 . .

对于block 1 的内部，就是先横着走啦，因为这个block已经被加载入了。。。

按照github 上的代码，32 x 32 和 61 x 67 能达到要求，即使已经对 64 x 64 有了这么多改善，也还是 misses:1635。

这可真不容易啊

CacheLab - Optimizing Matrix Transpose

Optimizing Matrix Transpose

推荐阅读更多精彩内容