CSAPP Cache Lab 笔记

发表于 2025-08-19 分类于组成原理阅读次数：

现代计算机通过每一层都是下一层的缓存的抽象构建出存储器的层次结构, 依据程序的局部性原理巧妙解决了存取信息的速度远小于 CPU 处理速度的问题.

前置知识可看: CSAPP3e第六章(存储器层次结构) | Amiriox’s Storage

Cache lab 分为两个部分:

第一部分写一个模拟程序, 模拟缓存的行为; 如果对缓存的原理和行为理解透了难度不高, ~~主要难点是必须用 C 写~~
第二部分是优化一个矩阵转置的函数, 转置有着鲜明的”两个数组访问模式相反”的特点, 导致必然有一个数组的访问模式缓存不友好. 要理解分块技术和缓存冲突不命中的常见情况及调整措施. 这个 lab 要求比较极端, 给定的缓存组关联度是 $1$, 也就是说只要是同一组的就会冲突不命中抢夺缓存行.

这是我做起来体感最痛苦的一个, 很多人也有相同的感受. 不过 lab 本身是没什么问题的, ~~CMU 是一款我的问题~~

Part A

首先要组织出缓存的数据结构: 缓存由几组缓存组构成, 每组缓存组有一行或多行缓存行构成, 每行缓存行有标记, 有效位, 实际记录信息的块.

构造缓存行和时间戳

首先构造缓存行, 注意要求的冲突替换策略是 LRU, 所以每一行还需要维护一个时间戳判断哪一行需要被踢出

真的写 UNIX 时间戳又有些麻烦, 我直接维护了一个全局的 tick, 每次插入新行时新行的时间戳就是 ++tick. 这样冲突需要 evict 一行的时候在对应组里找时间戳最小的.

static int tick;

typedef struct {
    unsigned long long tag;
    int valid;
    int timestamp;   // hit 和 push 时更新
    uint8_t *blocks; // 实际上不需要
} Line;

Line create_line(size_t b, unsigned long long tag) {
    Line ret;
    ret.tag = tag;
    ret.valid = 0;
    ret.timestamp = -1;
    ret.blocks = (uint8_t *)malloc(sizeof(uint8_t) * b);
    memset(ret.blocks, 0, sizeof(uint8_t) * b);
    return ret;
}

void destory_line(Line *line) {
    if (!line || !line->blocks)
        return;
    free(line->blocks);
    line->blocks = NULL;
}

构造缓存组

缓存组需要维护一个大小, 判断何时缓存组满了, 还需要插入一个缓存行 ( push_line 的实现后面提及 )

typedef struct {
    size_t line_count;
    Line *lines;
    // Find line by iterating lines with O(n)
    // CPU 高速缓存上一般有硬件优化, 这里只写了个很朴素的 O(n) 查找
} Set;

Set *create_set(size_t e, size_t b) {
    Set *ret = (Set *)malloc(sizeof(Set));
    if (ret) {
        ret->line_count = 0; // e;
        ret->lines = (Line *)malloc(sizeof(Line) * e);
        if (ret->lines) {
            memset(ret->lines, 0, sizeof(Line) * e);
            for (size_t i = 0; i < e; i++) {
                ret->lines[i] = create_line(b, 0);
            }
            return ret;
        }
    }
    exit(139 + 1);
}

void push_line(Set *set, unsigned long long tag, int e);

void destory_set(Set *set) {
    if (!set || !set->lines)
        return;
    // 这里实际上应该对组里每一行都 destory_line
    // 带 RRID 的语言写习惯了就会对这个不太敏感(并不
    free(set->lines);
    set->lines = NULL;
    free(set);
}

初始化缓存

紧接着, 一个缓存包含很多缓存组

初始化时按照命令行传参进来的 s 计算组数 $S = 2^s$, 直接开好每一组, 每一组也开好行, 组大小和有效位都置 $0$

更健壮更 C 的写法, create_set 应该在失败是返回 NULL, 这里内层 for 循环如果检查到某个组未能成功初始化还需要回滚之前的元素. 这就是由于不同语言的语言特性所造成的不同的写法和思维方式. ~~但是我并不像在一个模拟程序上浪费太多时间~~ ~~尽管写这两句话的时间完全足够我把这个修了~~

typedef struct {
    size_t set_count;
    Set **sets;
} Cache;

Cache *init_cache(size_t S, size_t e, size_t b) {
    Cache *ret = (Cache *)malloc(sizeof(Cache));
    if (ret) {
        ret->set_count = S;
        ret->sets = (Set **)malloc(sizeof(Set *) * S);
        if (ret->sets) {
            for (size_t i = 0; i < S; i++) {
                ret->sets[i] = create_set(e, b);
            }
            return ret;
        }
    }
    exit(139 + 1);
}

void destory_cache(Cache *cache) {
    if (!cache || !cache->sets)
        return;
    for (size_t i = 0; i < cache->set_count; i++) {
        destory_set(cache->sets[i]);
        cache->sets[i] = NULL;
    }
    free(cache);
}

查找缓存

查找某一个地址的缓存, 需要把地址拆解为标记位, 组索引和偏移量

如果在对应组找到带有对应标记为的行, 且有效位为 1 则是一次 hit, 更新这一行的时间戳

否则就是一次 miss, 这个 lab 采用写分配策略, 无论读不命中还是写不命中都需要加载进缓存, 进行 push_line 操作来完成这一点.

关于获取标记和组索引: 这里最好直接通过位移拆出这三段, 如果手写十六进制转十进制可能很痛苦, 因为 s, e, b 都是二进制的位数, 还需要手动对齐一下 (lab 没要求真的返回缓存的值, 所以块偏移可以不实现. 到 Part B 的时候可以看到这个程序的作用)

// 标记 | 组索引 | 块偏移
// Set, E-associativity, Block
// ttt sss bbb
unsigned long long get_addr_s(unsigned long long wrap, int len, int s, int e, int b) {
    unsigned long long mask = ((1LL << s) - 1);
    wrap = (wrap >> b) & mask;
    return wrap;
}
unsigned long long get_addr_t(unsigned long long wrap, int len, int s, int e, int b) {
    wrap = wrap >> (s + b);
    return wrap;
}

void find_cache(Cache *cache, char *addr, int len, int s, int e, int b) {
    unsigned long long wrap = 0;
    sscanf(addr, "%llx", &wrap);
    unsigned long long set_id = get_addr_s(wrap, len, s, e, b);
    unsigned long long tag = get_addr_t(wrap, len, s, e, b);
    Set *set = cache->sets[set_id];
    for (int i = 0; i < e; i++) {
        Line *li = &set->lines[i];
        if (li->valid && li->tag == tag) {
            hit++;
            li->timestamp = ++tick;
            return;
        }
    }
    // should not be executed if hit
    miss++;
    push_line(set, tag, e);
}

插入缓存行与替换策略

push_line 是可能出现冲突不命中和驱逐的情况, 按照 LRU 替换缓存行

void push_line(Set *set, unsigned long long tag, int e) {
    // WARN: eviction occurs
    if (set->line_count == e) {
        evic++;
        // TODO: LRU
        int lru = 0x7fffffff;
        Line *arg = NULL;
        for (int i = 0; i < e; i++) {
            Line *li = &set->lines[i];
            assert(li->valid);
            if (lru > li->timestamp) {
                /*
                 * < : max(|tick - timestamp|)
                 * timestamp 越大越新, 找最旧也就是最小的
                 * */
                lru = li->timestamp;
                arg = li;
            }
        }
        if (arg) {
            arg->tag = tag;
            arg->timestamp = ++tick;
        }
    } else {
        // TODO: bad impl
        for (int i = 0; i < e; i++) {
            Line *li = &set->lines[i];
            if (!li->valid) {
                li->valid = 1;
                li->tag = tag;
                li->timestamp = ++tick;
                set->line_count++;
                return;
            }
        }
    }
}

处理命令行参数

最后再写个处理命令行参数的. Part A 比较简单, 没有什么好说的.

int opt;
// int verbose = 0;
int s = 0, E = 0, b = 0;
FILE *trace_file = NULL;

while ((opt = getopt(argc, argv, "vs:E:b:t:")) != -1) {
    switch (opt) {
    case 'v':
        // verbose = 1;
        break;
    case 's':
        s = atoi(optarg);
        break;
    case 'E':
        E = atoi(optarg);
        break;
    case 'b':
        b = atoi(optarg);
        break;
    case 't':
        trace_file = fopen(optarg, "r");
        break;
    default:
        return 1;
    }
}

Cache *cache = init_cache((1 << s), E, b);
// TODO: parse $trace_file
if (!trace_file)
    exit(139 + 1);
char trace[256];

char ins;
char addr[256];
int blksz;
while (fgets(trace, sizeof(trace), trace_file)) {
    sscanf(trace, " %c %s,%d", &ins, addr, &blksz);
    int len = strlen(addr);
    switch (ins) {
    case 'I':
        // find_cache(cache, addr, len, s, E, b);
        // 指令加载的缓存在 I-Cache, 我们只需要模拟 D-Cache
        break;
    case 'S':
        find_cache(cache, addr, len, s, E, b);
        break;
    case 'L':
        find_cache(cache, addr, len, s, E, b);
        break;
    case 'M':
        find_cache(cache, addr, len, s, E, b);
        find_cache(cache, addr, len, s, E, b);
        break;
    }
}

printSummary(hit, miss, evic);

Part B

在 trans.c 中编写缓存友好的转置函数. “缓存友好”的具体要求是对缓存不明中的次数 $m$ 满足以下条件:

$32 \times 32: \text{8 points if }m \lt 300, \text{ 0 points if } m \gt 600$
$64 \times 64: \text{8 points if }m \lt 1,300, \text{ 0 points if } m \gt 2,000$
$61 \times 67: \text{10 points if }m \lt 2,000, \text{ 0 points if } m \gt 3,000$

我一开始没看这个要求, 试图直接写通用的转置函数, 在计算缓存访问冲突模式时试图将 $4n$ 从十进制转换为二进制

首先观察常规写法的矩阵转置:

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;
        }
    }
}

分析访问模式:

内循环对于 A 数组元素的读访问是步长为 $1$ 的连续访问, 空间局部性良好, 在一次 miss 并加载缓存行之后可以连续访问这一缓存行的所有元素直到再次 miss. 这是缓存友好的.
内循环对于 B 数组元素的写访问是步长为 N 的跨行访问 (B[j][i] 的下一次访问是 B[j + 1][i], 中间差一行的元素数量), 这导致每次访问 miss 后加载的缓存行都不会被再次利用到从而导致每次访问都会 miss, 空间局部性很差, 缓存不友好.

然而, 我们意识到矩阵转置的行列是必然相反的, A 和 B 必然呈现相反的访问模式, 肯定会有一个数组的访问模式很差

根据 lab 提供的 pdf 的提示, 考虑分块策略.

缓存友好的分块策略, 是指将一个需要处理的矩阵分为特定 $b \times b$ 的小块, 在每个小块中进行需要的操作.

为什么这样能够使得缓存友好呢? 重点就在于 $b$ 块大小的选择, 选择合适的块大小使得缓存可以装下 A 和 B 的一个分块(子矩阵), 这样即使 B 的访问模式依然空间局部性差, 但是时间局部性友好: 缓存足够装下这一小块的多行元素, B 的每次访问都能在缓存中 hit.

32x32 与 61x67: 分块策略与循环展开

于是我们可以开始计算如何设计块大小. lab 给定的缓存是 $s = 5, E = 1, b = 5$. 每个地址有 $5$ 位的块偏移, 意味着一个缓存行大小为 $2^5 = 32$ 字节, 也就是 $8$ 个 $4$ 字节整型——这暗示我们分块的每一行设置为 $8$ 个整型来适配缓存行大小. 同时, 每个地址有 $5$ 位组索引, 一共 $2^5 = 32$ 组, 一组一行即缓存一共有 $32$ 个这样的缓存行, 足以装下四个分块了.

#define BSIZE 8
for (int kk = 0; kk < N; kk += BSIZE) {
    for (int jj = 0; jj < M; jj += BSIZE) {
        for (int i = jj; i < min(jj + BSIZE, M); i++) {
            for (int j = kk; j < min(kk + BSIZE, N); j++) {
                B[i][j] = A[j][i];
            }
        }
    }
}

然而事情并没这么简单, 这段代码的表现还是比较差. 这是比较反直觉的: 既然现在所有元素都在缓存内, 只有少数冷启动的 miss, 剩下都是 hit, 那理应是最优了吧? 所以只有一种可能, 并不是所有元素都在缓存内!

这时通过缓存模拟器, 以 valgrind 生成的 trace.f0 为输入模拟缓存, 发现许多 eviction, 这才想起来可能有两个元素的地址被映射到同一组内, 由于这个严厉的 $E = 1$ 也就是直接映射高速缓存限制, 可能会出现很多冲突.

1	$ ./csim-ref -v -s 5 -E 1 -b 5 -t trace.f0

但我实在是懒得把十六进制地址转二进制再提取组索引找规律了, 所以还是先想一些可能出现的情况:

回顾文章开头的博客, 我记得我曾经写过这样一段话:

这里块偏移是要求连续所以是最后几位很好理解, 但为什么组索引不设置为头部的位而是分配在中间呢?

这是因为如果是分配在头部, 连续的几个地址就回分配在同一组(比如设置为前两位的话, 0x1000, 0x1001, 0x1010, 0x1011这连续四个就分配在同一组了), 而缓存每次不命中都会加载一整块相邻的地址, 我们希望相邻的地址分散到不同的组, 来让缓存加载整个地址空间上尽可能多的地址, 增加缓存效率

缓存的核心就是局部性, 所以块偏移必须连续, 所以必须放在最后几位; 而组索引的要求是相邻的最好不放在同一组以减少冲突, 所以也放在尽可能靠后的位 (块偏移位前). 但是这也可能不够, 如果”相邻”的要求扩大, 比如我们需要在一个分块内都尽可能不分在同一组, 就可能不太满足了.

考虑一下 A 的两次访问之间的地址差值: A[j] 到 A[j + 1] 是跨行访问, 地址差距是 $4 \times M$, 即元素大小乘以行元素数量. 对于 $32\times32$ 的矩阵, 地址差距是 $4 \times 32 = 128$.

对每次访问的偏移计算组索引 $(128)_{10} = (10000000)_2$, 组索引位是 100 也就是每次 $+4$. 相邻两次访问 A 数组元素地址, 组索引的变化为 $4, 8, 12, 16, 20, 24, 28, 32$, 在 $8$ 次内是不会从组索引位溢出导致冲突到 $4 ,8, ...$ 的 (如果再 $+4$ 相当于模 $32$, 因为进位超出了组索引的位到了标记位).

由于我们的分块每一行长度是 $8$, $8$ 次访问后已经无需再维持这一行的缓存了, 即使冲突了直接丢弃也没关系.
虽然对当前研究的问题没有帮助, 但是通过同样的方法计算 $64\times64$ 的矩阵, 发现会出现数组内部冲突的情况, 每四次访问就会冲突, 这给了我们一些警示.

tips: 如果懒得换算可以直接把 gdb 当进制转换器用. /t, /d, /x 分别是以二进制, 十进制, 十六进制形式输出, Bomb lab 时的小技巧

1 2	(gdb) p /t 128 $1 = 10000000

既然 A 自己内部不会有冲突, 那会不会是 A 和 B 的某些元素地址映射到了同一行? 这里 lab 的 pdf 其实给了一些提示 (好像是阅读资料里给的): 对角线上可能会出现大量冲突

我研究了一会其实没弄明白, 查阅资料后发现在分块的方法中, 如果这个分块位于整体矩阵的对角线上 ($kk = jj$ 时), 就会产生读 $A[x][x]$ 写 $B[x][x]$ 的情况, 这两者的元素地址是极大概率映射到同一组的.

所以就需要尽可能延长读 $A[x][x]$ 和写 B[x][x] 这两个操作的距离, 使得 A 全部读进(缓存被充分使用, 可以被驱逐丢弃了)后, 再进行写 B 的操作, 此时即使冲突, B 也可以放心驱逐 A 的缓存行, 因为未来不会再用到了, 不会出现以后读 A 还映射到这一缓存行导致 A 和 B 交替抢夺这一缓存行的情况. 采用局部变量和循环展开分离读写操作:

#define BSIZE 8
int a, b, c, d, e, f, g, h;
for (int kk = 0; kk < N; kk += BSIZE) {
    for (int jj = 0; jj < M; jj += BSIZE) {
        // a chunk with left-top corner (kk, jj)
        for (int i = jj; i < min(jj + BSIZE, M); i++) {
            // 写 A
            if (kk + 0 < N)
                a = A[kk][i];
            if (kk + 1 < N)
                b = A[kk + 1][i];
            if (kk + 2 < N)
                c = A[kk + 2][i];
            if (kk + 3 < N)
                d = A[kk + 3][i];
            if (kk + 4 < N)
                e = A[kk + 4][i];
            if (kk + 5 < N)
                f = A[kk + 5][i];
            if (kk + 6 < N)
                g = A[kk + 6][i];
            if (kk + 7 < N)
                h = A[kk + 7][i];

            // 写 B
            if (kk + 0 < N)
                B[i][kk] = a;
            if (kk + 1 < N)
                B[i][kk + 1] = b;
            if (kk + 2 < N)
                B[i][kk + 2] = c;
            if (kk + 3 < N)
                B[i][kk + 3] = d;
            if (kk + 4 < N)
                B[i][kk + 4] = e;
            if (kk + 5 < N)
                B[i][kk + 5] = f;
            if (kk + 6 < N)
                B[i][kk + 6] = g;
            if (kk + 7 < N)
                B[i][kk + 7] = h;
        }
    }
}
#undef BSIZE

模拟一下, $kk == jj$ 时, 对于内循环第一次迭代 $i = jj$

上面读 A 的一列的第一个 if 就会变成 a = A[kk][jj] 也就是对角线上的的 A[x][x]
上面写 B 的一行的第一个 if 就会变成 B[jj][kk] = a 同上
A[x][x] 和 B[x][x] 的地址大概率映射在同一组上, 而对于 $E = 1$ 的直接映射缓存, 只有一个缓存行, 所以 A 的第 $x$ 行会和 B 的第 $x$ 行冲突在统一缓存行, B 会因为冲突残忍地把 A 这一整行踢出缓存行
内循环第二次迭代 i = jj + 1 时, A[kk] 这一整行的缓存就没有了, 但是得益于循环展开带来的读写分离, A 这一行的缓存每次大循环只会 miss 一次. 如果不循环展开, 写完整的循环, 小循环每次迭代, A 和 B 都会反复争抢一个缓存行
非对角线块不会出现这个情况, 因为读写的缓存行没有交集, 不会冲突

于是 $32 \times 32$ 的情况顺利过了(实际上我走了很多弯路, 在错误的思路上浪费了很多时间), 顺便还过了个 $61\times67$ 的, 这个应该主要考察分块遇到不规整的情况是否能满足, 由于我们写的是 < min(jj + BSIZE, M), 所以可以正常处理边角上的元素, 也不会越界.

64x64: 防止冲突的访问顺序

然而真正的难点才刚开始, $64\times 64$ 的矩阵有一些问题需要解决. 虽然上述代码也能取得一些分数, 但是看 miss 远不能拿到满分

首先是上述说的 A 的访问冲突模式, 对于 $64\times64$, 矩阵行元素增多一倍, 使得冲突频率也增多一倍: 每 $4$ 次相邻访问 A (A[i] 和 A[i+4]) 就会造成冲突.

最直观的想法肯定是把 BSIZE 改为 $4$, 然后修改一下循环展开的地方删掉读 A 和写 B 的后四行. 可惜这样并不能拿到满分, 甚至分数还低了一些. 动脑子想一下, 一个缓存行能容纳 $8$ 个元素, 如果分块的一行只有 $4$ 个元素, 那每个缓存行的有效利用率只有一半, 所以还是要考虑 $\text{BSIZE} = 8$ 的方案

呃, 我实际上没考虑出来. 折腾了很久后最后失去心气, 在耻辱地参阅了他人的做法后大概逆向出了这种做法的逻辑:

$8 \times 8$ 的结论是对的, 但是到第五行时还是 A[0] 会和 A[4] 冲突, 所以需要一种方案能够在 $8\times 8$ 的分块内以能够充分利用缓存的方式再分部分处理.

对于前 $4$ 行(分块的上半部分), 我们需要在充分利用这 $4$ 行缓存后再去碰下半部分, 只有在已经用不到上半部分缓存之后才能访问下半部分, 加载下半部分缓存, 否则就会出现冲突不命中.

首先转置并复制 A 的这前 $4$ 行到 B 的前 $4$ 行, 此时 A 和 B 的上半部分都在缓存中, 且A 的上半部分缓存已经没什么用了可以放心踢出

但实际上在前四行中, A 右上角的 $2 \times 2$ 块应当被转置到 B 的左下角, 所以目前 B 右上角的位置是错误的, 需要把这 $4$ 个数试图放到 B 的正确位置(左下角); 假设我们真的这么做了, 下一步就应该是把 A 的左下角复制到 B 的右上角, 我们审视一下这个操作的缓存友好性:

A 的上半部分缓存没有用了, 可以放心踢出, 所以访问 A 的下半部分是合理的.
之前修正 B 右上角到左下角时踢出了上半部分的缓存, 导致我们现在再写入 B 的右上角时需要重新加载缓存, 而后面再写 B 的右下角有需要加载上半部分缓存, 总结来说就是: 加载上半部分->踢上半部分并加载下半部分->踢下半部分并加载上半部分->踢下半部分并加载上半部分, 出现缓存抖动.

所以那 $4$ 个错误的数需要先用局部变量存起来, 尽可能等上半部分利用完毕再执行修正

先把 A 的左下角复制到 B 的右上角, 再从局部变量恢复 B 的左下角, 此时 B 的上半部分没用了, B 的下半部分才初次进入缓存.

最后只需要把 A 的右下角转置到 B 的右下角收尾即可.

需要注意的是 A 的 $(kk, jj)$ 块要转置到 B 的 $(jj, kk)$ 块

#define BSIZE 8
int a, b, c, d, e, f, g, h;
for (int kk = 0; kk < N; kk += BSIZE) {
    for (int jj = 0; jj < M; jj += BSIZE) {
        // 还是 8 * 8, 但是要对每一分块再分块
        // 先复制前四行, 因为第五行会出现 A[0] 和 A[4] 冲突
        for (int i = 0; i < 4; i++) {
            a = A[kk + i][jj + 0];
            b = A[kk + i][jj + 1];
            c = A[kk + i][jj + 2];
            d = A[kk + i][jj + 3];
            e = A[kk + i][jj + 4];
            f = A[kk + i][jj + 5];
            g = A[kk + i][jj + 6];
            h = A[kk + i][jj + 7];

            B[jj + 0][kk + i] = a;
            B[jj + 1][kk + i] = b;
            B[jj + 2][kk + i] = c;
            B[jj + 3][kk + i] = d;
            B[jj + 0][kk + 4 + i] = e;
            B[jj + 1][kk + 4 + i] = f;
            B[jj + 2][kk + 4 + i] = g;
            B[jj + 3][kk + 4 + i] = h;
        }
        // A 的前四行, B 的前四行都在缓存里
        // A 的前四行已经没用了, 可以直接踢出
        for (int i = 0; i < 4; i++) {
            // 缓冲 B 的右上角(此时位置错误)
            // hit B 第 i 行一行后半的缓存
            a = B[jj + i][kk + 4 + 0];
            b = B[jj + i][kk + 4 + 1];
            c = B[jj + i][kk + 4 + 2];
            d = B[jj + i][kk + 4 + 3];

            // A 的左下角转置并正确放置到 B 的右上角
            // evict A 前四行的缓存, 加载/hit 后四行
            // hit B 第 i 行一行后半的缓存
            e = A[kk + 4 + 0][jj + i];
            f = A[kk + 4 + 1][jj + i];
            g = A[kk + 4 + 2][jj + i];
            h = A[kk + 4 + 3][jj + i];
            B[jj + i][kk + 4] = e;
            B[jj + i][kk + 4 + 1] = f;
            B[jj + i][kk + 4 + 2] = g;
            B[jj + i][kk + 4 + 3] = h;
            
            // 此时 B 的第 i 行缓存已经没用了, 可以直接踢出
            // 恢复 B 的右上角到正确的位置(左下)
            // evict B 第 i 行的缓存, 加载第 i + 4 行
            B[jj + i + 4][kk + 0] = a;
            B[jj + i + 4][kk + 1] = b;
            B[jj + i + 4][kk + 2] = c;
            B[jj + i + 4][kk + 3] = d;
        }

        // 还剩 B 的右下角
        for (int i = 0; i < 4; i++) {
            // A 的下半部分第 i 行
            a = A[kk + 4 + i][jj + 4 + 0];
            b = A[kk + 4 + i][jj + 4 + 1];
            c = A[kk + 4 + i][jj + 4 + 2];
            d = A[kk + 4 + i][jj + 4 + 3];
            // B 的下半部分 4 行
            B[jj + 4 + 0][kk + 4 + i] = a;
            B[jj + 4 + 1][kk + 4 + i] = b;
            B[jj + 4 + 2][kk + 4 + i] = c;
            B[jj + 4 + 3][kk + 4 + i] = d;
        }
        // 妈的终于过了, 我快写死了
    }
}
#undef BSIZE