cachelab - Katyusha's blog

cache lab#

Part A#

写在前面#

这部分要求你实现一个模拟缓存运行的C语言程序，支持读，写，修改内存三个操作，其与对于缓存模拟的行为给定的 $csim-ref$ 可执行文件一致，最后输出操作完成后的缓存命中，未命中，替换的次数。缓存的组数，行数，每一行的字节数在执行时以参数给出，替换策略使用 $LRU$ (least-recently used)，即每次替换块内离上一次引用时间最久的块

但是本部分不要求你输出访问时具体的值，你只需要统计这次操作是否命中，未命中，替换

在运行的时候，我们采用了一下的选项来传递参数

linux> ./csim-ref [-hv] -s <s> -E <E> -b <b>-t <tracefile>

其中-h -v两个选项可选可不选，且后面没有参数，分别表示打印使用方法，和运行时是否可见化地输出每次缓存访问的结果

-s -E -b 后接一个参数，分别表示组索引位数、每组行数、块偏移位数；因此组数 $S=2^s$ ，块大小 $B=2^b$

-t 后接字符串参数，表示读入文件的路径

读入部分#

怎么感觉是Part A 里面最难的部分（

首先为了从选项中读出参数，我们在linux系统下需要使用 $getopt$ 函数，该函数原型如下

int getopt(int argc, char * const argv[], const char *optstring)

其中 $argc$ ， $argv$ 为 $main$ 函数的参数，分别代表参数个数和参数列表

$optstring$ 为选项字符串，举例来说，getopt(argc, argv, "hvs:E:b:t:")就表示有-h -v -s -E -b -t 这几个选项，其中-s -E -b -t 若选择的话，后面必须带有参数

该函数返回值为选项的ASCII码，同时，包含该函数的 <unistd.h> 和 <getopt.h> 中有名为 $optarg$ 的指针变量，在每次使用 $getopt$ 时，若该选项有参数，就会被更新为该参数的字符串指针

由此不难写出读入函数

1
    int op;
2
    FILE *fp;
3

4
    while ((op = getopt(argc, argv, "hvs:E:b:t:")) != EOF) {
5
        if (op == 'h') {
6
            Help();
7
            return 0;
8
        }
9
        if (op == 'v') {
10
            v = 1;
11
            continue;
12
        }
13
        if (op == 's') {
14
            s = atoi(optarg);//atoi 在 stdlib.h中，传入一个字符串开头的指针，将其转换为整数
15
            S = (1 << s);
16
            continue;
17
        }
18
        if (op == 'E') {
19
            E = atoi(optarg);
20
            continue;
21
        }
22
        if (op == 'b') {
23
            b = atoi(optarg);
24
            B = (1 << b);
25
            continue;
26
        }
27
        if (op == 't') {
28
            fp = fopen(optarg, "r");//文件指针指向参数标明的文件
29
            continue;
30
        }
31
        Help();
32
        return 0;//其它异常参数符
33
    }

每次操作分为以下四类：

I address,size表示取address地址开始的size字节指令
L address,size 表示加载address地址开始的size字节数据
S address,size 表示向address地址开始的size字节写数据
M address,size 表示修改address地址开始的size字节数据

但是这部分只要我们用缓存处理数据信息，同时又不需要真正地对缓存进行读写，只是模拟是否命中和替换这个过程即可

所以 I操作完全没用， L 和S操作完全等价（无语

1
    char opt[5];
2
    size_t ad;
3
    int siz;
4
    while (fscanf(fp, "%s %lx,%d", opt, &ad, &siz) != EOF) {
5
        ++curtime;
6
        if (v) {
7
            printf("%c %lx,%d\n", opt[0], ad, siz);
8
        }
9
        if (opt[0] == 'I') continue;
10
        if (opt[0] == 'L') Load(ad);
11
        if (opt[0] == 'S') Store(ad);
12
        if (opt[0] == 'M') Modify(ad);
13
    }

缓存的相关结构#

由于本部分缓存大小未知，需要动态分配内存，这里实现上使用了指针加 malloc动态分配空间

1
struct row {
2
    int valid, flag, dfn;
3
    //有效位 标志位 上次更新的时间戳
4
};//一行
5

6
typedef struct row* set;//一组
7
typedef set* cache;//整个缓存
8
cache c;
9

10
void Cache_init() {
11
    c = (cache)malloc(sizeof(set) * S);//分配S个组的空间
12
    for (int i = 0; i < S; i++) {
13
        c[i] = (set)malloc(sizeof(struct row) * E);//每一组分配E行的空间
14
        for (int j = 0; j < E; j++) {
15
            c[i][j].valid = 0;
16
            c[i][j].flag = c[i][j].dfn = -1;
17
        }
18
    }
19
}

缓存的读写#

我们先对地址使用位运算得到该地址应该被分配到的组数，标识位和偏移量（偏移量好像没用）

为了维护某一组内是否有该地址对应的标志位，我们可以采用平衡树，但是E一般都比较小，没有这个必要（不是我懒得写了），直接E行依遍历比较就行

如果存在标识符相同且有效的，那么发生缓存命中，修改这一行的时间戳，直接返回即可

否则缓存未命中，我们优先找该组空的行，若存在，直接放入并更新时间戳，将其有效位设置为1，此时未命中，也未发生替换

如空的行不存在，我们就将该组中时间戳最小的行替换为需要访问的数据，同样更新时间戳即可，此时未命中并发生替换

1
void Load(int ad) {
2
    //m = t + s + b
3
    // int _b = ad & ((1 << b) - 1);
4
    int _s = (ad >> b) & ((1 << s) - 1);
5
    int _t = ad >> (s + b);
6

7
    struct row* r = c[_s];
8
    for (int i = 0; i < E; i++) {
9
        if ((r + i)->valid && (r + i)->flag == _t) {//缓存命中
10
            if (v) puts("hit");
11
            ++hit;
12
            (r + i)->dfn = curtime;
13
            return;
14
        }
15
    }
16

17

18
    struct row* evicp = r;
19
    for (int i = 1; i < E; i++) {
20
        if ((r + i)->dfn == -1 || (r + i)->dfn < evicp->dfn) {//优先使用空行
21
            evicp = r + i;
22
        }
23
    }
24

25
    miss++;
26
    printf("miss");
27
    if (evicp->dfn != -1) {
28
        evic++;
29
        if (v) printf(" eviction");
30
    }//发生了替换
31
    putchar('\n');
32
    evicp->dfn = curtime; evicp->valid = 1; evicp -> flag = _t;
33
    return;
34
}

写入和加载的缓存行为在本模拟器中完全一致。修改操作M等价于一次加载后紧跟一次存储：如果第一次访问未命中，则会统计一次未命中并把块载入缓存，随后第二次存储必然命中；如果第一次访问命中，则总共统计两次命中

1
void Store(int ad) {
2
    Load(ad);
3
}
4

5
void Modify(int ad) {
6
    //m = t + s + b
7
    // int _b = ad & ((1 << b) - 1);
8
    int _s = (ad >> b) & ((1 << s) - 1);
9
    int _t = ad >> (s + b);
10
    struct row *r = c[_s];
11
    for (int i = 0; i < E; i++) {
12
        if ((r + i)->valid && (r + i)->flag == _t) {
13
            if (v) puts("hit");
14
            hit += 2;
15
            (r + i)->dfn = curtime;
16
            return;
17
        }
18
    }
19

20
    struct row* evicp = r;
21
    for (int i = 1; i < E; i++) {
22
        if ((r + i)->dfn == -1 || (r + i)->dfn < evicp->dfn) {
23
            evicp = r + i;
24
        }
25
    }
26

27
    miss++;  hit++;
28
    if (v) puts("miss");
29
    if (evicp->dfn != -1) {
30
        evic++;
31
        if (v) printf(" eviction");
32
    }
33
    puts(" hit");
34
    evicp->dfn = curtime; evicp->valid = 1; evicp -> flag = _t;
35
    return;
36
}

代码#

主体已经完成了，再加上使用说明即可

1
#include "cachelab.h"
2
#include <unistd.h>
3
#include <stdio.h>
4
#include <stdlib.h>
5
#include <getopt.h>
6

7
int E, s, S, b, B, v, t;
8
const int m = 64;
9
int curtime;
10
int hit, miss, evic;
11

12
struct row {
13
    int valid, flag, dfn;
14
    //有效位 标志位 上次更新的时间戳
15
};//一行
16

17
typedef struct row* set;//一组
18
typedef set* cache;//整个缓存
19
cache c;
20

21
void Cache_init() {
22
    c = (cache)malloc(sizeof(set) * S);//分配S个组的空间
23
    for (int i = 0; i < S; i++) {
24
        c[i] = (set)malloc(sizeof(struct row) * E);//每一组分配E行的空间
25
        for (int j = 0; j < E; j++) {
26
            c[i][j].valid = 0;
27
            c[i][j].flag = c[i][j].dfn = -1;
28
        }
29
    }
30
}
31

32
/*
33
Usage: ./csim-ref [-hv] -s <num> -E <num> -b <num> -t <file>
34
Options:
35
  -h         Print this help message.
36
  -v         Optional verbose flag.
37
  -s <num>   Number of set index bits.
38
  -E <num>   Number of lines per set.
39
  -b <num>   Number of block offset bits.
40
  -t <file>  Trace file.
41

42
Examples:
43
  linux>  ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace
44
  linux>  ./csim-ref -v -s 8 -E 2 -b 4 -t traces/yi.trace
45
*/
46

47
void Help() {
48
    printf(
49
"Usage: ./csim-ref [-hv] -s <num> -E <num> -b <num> -t <file>\n"
50
"Options:\n"
51
"  -h         Print this help message.\n"
52
"  -v         Optional verbose flag.\n"
53
"  -s <num>   Number of set index bits.\n"
54
"  -E <num>   Number of lines per set.\n"
55
"  -b <num>   Number of block offset bits.\n"
56
"  -t <file>  Trace file.\n"
57

58
"Examples:\n"
59
"  linux>  ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace\n"
60
"  linux>  ./csim-ref -v -s 8 -E 2 -b 4 -t traces/yi.trace\n"
61
    );
62
}
63

64
void Load(int ad) {
65
    //m = t + s + b
66
    // int _b = ad & ((1 << b) - 1);
67
    int _s = (ad >> b) & ((1 << s) - 1);
68
    int _t = ad >> (s + b);
69

70
    struct row* r = c[_s];
71
    for (int i = 0; i < E; i++) {
72
        if ((r + i)->valid && (r + i)->flag == _t) {//缓存命中
73
            if (v) puts("hit");
74
            ++hit;
75
            (r + i)->dfn = curtime;
76
            return;
77
        }
78
    }
79

80

81
    struct row* evicp = r;
82
    for (int i = 1; i < E; i++) {
83
        if ((r + i)->dfn == -1 || (r + i)->dfn < evicp->dfn) {//优先使用空行
84
            evicp = r + i;
85
        }
86
    }
87

88
    miss++;
89
    printf("miss");
90
    if (evicp->dfn != -1) {
91
        evic++;
92
        if (v) printf(" eviction");
93
    }//发生了替换
94
    putchar('\n');
95
    evicp->dfn = curtime; evicp->valid = 1; evicp -> flag = _t;
96
    return;
97
}
98

99
void Store(int ad) {
100
    Load(ad);
101
}
102

103
void Modify(int ad) {
104
    //m = t + s + b
105
    // int _b = ad & ((1 << b) - 1);
106
    int _s = (ad >> b) & ((1 << s) - 1);
107
    int _t = ad >> (s + b);
108
    struct row *r = c[_s];
109
    for (int i = 0; i < E; i++) {
110
        if ((r + i)->valid && (r + i)->flag == _t) {
111
            if (v) puts("hit");
112
            hit += 2;
113
            (r + i)->dfn = curtime;
114
            return;
115
        }
116
    }
117

118
    struct row* evicp = r;
119
    for (int i = 1; i < E; i++) {
120
        if ((r + i)->dfn == -1 || (r + i)->dfn < evicp->dfn) {
121
            evicp = r + i;
122
        }
123
    }
124

125
    miss++;  hit++;
126
    if (v) puts("miss");
127
    if (evicp->dfn != -1) {
128
        evic++;
129
        if (v) printf(" eviction");
130
    }
131
    puts(" hit");
132
    evicp->dfn = curtime; evicp->valid = 1; evicp -> flag = _t;
133
    return;
134
}
135

136

137
int main(int argc, char *argv[]){
138
    int op;
139
    FILE *fp;
140

141
    while ((op = getopt(argc, argv, "hvs:E:b:t:")) != EOF) {
142
        if (op == 'h') {
143
            Help();
144
            return 0;
145
        }
146
        if (op == 'v') {
147
            v = 1;
148
            continue;
149
        }
150
        if (op == 's') {
151
            s = atoi(optarg);//atoi 在 stdlib.h中，传入一个字符串开头的指针，将其转换为整数
152
            S = (1 << s);
153
            continue;
154
        }
155
        if (op == 'E') {
156
            E = atoi(optarg);
157
            continue;
158
        }
159
        if (op == 'b') {
160
            b = atoi(optarg);
161
            B = (1 << b);
162
            continue;
163
        }
164
        if (op == 't') {
165
            fp = fopen(optarg, "r");//文件指针指向参数标明的文件
166
            continue;
167
        }
168
        Help();
169
        return 0;//其它异常参数符
170
    }
171

172
    Cache_init();//缓冲初始化，动态分配空间
173

174
    char opt[5];
175
    size_t ad;
176
    int siz;
177
    while (fscanf(fp, "%s %lx,%d", opt, &ad, &siz) != EOF) {
178
        ++curtime;
179
        if (v) {
180
            printf("%c %lx,%d\n", opt[0], ad, siz);
181
        }
182
        if (opt[0] == 'I') continue;
183
        if (opt[0] == 'L') Load(ad);
184
        if (opt[0] == 'S') Store(ad);
185
        if (opt[0] == 'M') Modify(ad);
186
    }
187

188
    printSummary(hit, miss, evic);
189
    return 0;
190
}

使用 make && ./test-csim得到以下结果

Part B#

写在前面#

有 $32 \times 32$ ， $64 \times 64$ ， $61 \times 67$ 三个矩阵 $A$ ，你需要使用C实现矩阵转置得到矩阵 $B$ ，要求使得参数为 $(s=5, E=1, b=5)$ 的缓存产生的不命中次数小于一个给定值，不能自己定义数组，最多使用12个局部变量

手算发现，该缓存有32个组，每组一行，块大小为32字节，即每块能存储8个int。方便起见，以下把一个缓存块称为一行，同时使用0-index

通过访问目录下的 $trace.f1$ (题目给出的不加优化的转置代码的缓存行为跟踪)发现， $A$ 的起始地址为 $0x0010d080$ ， $B$ 的起始地址为 $0x0014d080$ ，刚好相差 $2^{18}$ ，这说明在下标相同时， $A[i][j]$ 和 $B[i][j]$ 会被分配到相同的一行内，只是标志位不同；同时二者的起始地址都是32的倍数，说明 $A[i][8k+0]$ 到 $A[i][8k+7]$ 都在一行里面， $B$ 也同理

题目给出的最原始的转置函数如下

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

5
    for (i = 0; i < N; i++) {
6
        for (j = 0; j < M; j++) {
7
            tmp = A[i][j];
8
            B[j][i] = tmp;
9
        }
10
    }
11
}

注意先通过 sudo apt install valgrind 安装 valgrind

$32 \times 32$ #

本部分要求缓存未命中次数小于300次

先在目录下使用make && ./test-trans -M 32 -N 32对原始函数缓存访问效率进行测试，结果如下

发现该函数对于缓存访问相当不友好，我们先搞明白1183次不命中是怎么来的

每隔8个int就会产生一个行的偏移，先画出每个int会被放入缓存的哪一行（不会画图，图是偷的，勿喷）

1.对于 $A$ 是步长为1的访问，只有在第一次访问一个没有被访问过的组的时候才会不命中，所以会有128次不命中

2.对于 $B$ 是步长为32的访问，每一次都不会命中，所以有1024次不命中

3.对于 $i=j$ 即对角线上的情况，此时 $B[i][i]$ 和 $A[i][i]$ 所在的组一样，写入 $B[i][i]$ 的值的时候，刚好会将 $A$ 所在行替换掉，在下一次读取 $A$ 的值的时候，会将 $B$ 替换掉，这样的情况会发生31次，因为最后一次访问 $(31,31)$ 后不会再读取 $A$ 了

所以一共为128+1024+31=1183次

接下来考虑如何优化，可以使用分块，取块长为8，即每次将一个 $8\times8$ 的 $A$ 矩阵写入其在 $B$ 上对应的位置

这样优化后， $A$ 在块内以步长为1访问，而 $B$ 在块内按列顺序访问，每一块会在每一列第一次访问的时候不命中

优化后代码如下

1
    if (M == 32 && N == 32) {
2
        for (i = 0; i < N; i += 8) {
3
            for (j = 0; j < M; j += 8) {
4
                for (ii = i; ii < i + 8; ii++) {
5
                    for (jj = j; jj < j + 8; jj++) {
6
                        B[jj][ii] = A[ii][jj];
7
                    }
8
                }
9
            }
10
        }
11
    }

仍然需要进一步的优化，考虑对角线上的块，在转置的时候会发生对 $B$ 进行写入时，替换掉了这一行的 $A$ ，所以可以使用临时变量保存 $A$ 的值，然后放入 $B$ 中，这样减少了访问 $A$ 这一行后面的元素所需要的一次不命中

1
    if (M == 32 && N == 32) {
2
        for (i = 0; i < N; i += 8) {
3
            for (j = 0; j < M; j += 8) {
4
                for (ii = i; ii < i + 8; ii++) {
5
                    a = A[ii][j];
6
                    b = A[ii][j + 1];
7
                    c = A[ii][j + 2];
8
                    d = A[ii][j + 3];
9
                    e = A[ii][j + 4];
10
                    f = A[ii][j + 5];
11
                    g = A[ii][j + 6];
12
                    h = A[ii][j + 7];
13
                    B[j ][ii] = a;
14
                    B[j + 1][ii] = b;
15
                    B[j + 2][ii] = c;
16
                    B[j + 3][ii] = d;
17
                    B[j + 4][ii] = e;
18
                    B[j + 5][ii] = f;
19
                    B[j + 6][ii] = g;
20
                    B[j + 7][ii] = h;
21
                }
22
            }
23
        }
24
    }

结果如下，成功通过此题

$64\times64$ #

本部分要求缓存未命中次数小于1300

再次偷图（这是左上角 $16 \times 16$ 的矩阵

如果我们仍然采用 $8\times8$ 分块处理的话，块内会存在严重的抖动，比如 $B$ 内部对组0，组8，组16，组24都有两次访问，都会产生一次替换，这导致缓存命中率相当糟糕，实际测试中不命中次数为4611，与未优化的原始代码次数4723几乎没有差别

为了减少 $B$ 的抖动，我们尝试使用 $4\times4$ 分块

1
    if (M == 64 && N == 64) {
2
        for (i = 0; i < N; i += 4) {
3
            for (j = 0; j < M; j += 4) {
4
                for (ii = i; ii < i + 4; ii++) {
5
                    a = A[ii][j];
6
                    b = A[ii][j + 1];
7
                    c = A[ii][j + 2];
8
                    d = A[ii][j + 3];
9
                    B[j ][ii] = a;
10
                    B[j + 1][ii] = b;
11
                    B[j + 2][ii] = c;
12
                    B[j + 3][ii] = d;
13
                }
14
            }
15
        }
16
    }

结果如下

有所优化但是还未达到本题要求，采用 $4\times4$ 分块的时候，虽然 $B$ 的抖动减少了，但是对 $A$ 中原本连续8个数的访问变成了两次对4个数的访问，这增加了 $A$ 的抖动

到这里就不会了，去看别人博客了（

我们考虑以下的策略

1.先读取 $A$ 矩阵 $8\times8$ 分块的前4行，将黄色部分和绿色部分分别转置后，直接顺序不变拷贝到 $B$ 中，此时未发生缓存替换，只有 $A$ 和 $B$ 的各4次载入

2.使用寄存器暂存未放置正确的绿色部分的一行，然后将粉色部分的一列放置到绿色部分的这一行，接着从寄存器中取值将绿色部分这一行放到正确的位置。绿色部分已经存放在了缓存中，可以直接读取，粉色第一列的时候会发生4次载入，热身缓存，正确放置绿色部分每一行的时候都会产生一次对原本存放 $A$ 的组的替换，故一共发生8次缓存不命中

3.最后将紫色部分直接转置到正确位置即可，紫色部分每一行和放置的 $B$ 每一列都在缓存中，全部命中

所以对于 $8\times8$ 的块，发生了16次不命中，对 $64 \times 64$ 的块，理论会有1024次不命中

1
    if (M == 64 && N == 64) {
2
        int i, j, ii;
3
        int a, b, c, d, e, f, g, h;
4

5
        for (i = 0; i < N; i += 8) {
6
            for (j = 0; j < M; j += 8) {
7
                for (ii = i; ii < i + 4; ii++) {
8
                    a = A[ii][j];
9
                    b = A[ii][j + 1];
10
                    c = A[ii][j + 2];
11
                    d = A[ii][j + 3];
12

13
                    e = A[ii][j + 4];
14
                    f = A[ii][j + 5];
15
                    g = A[ii][j + 6];
16
                    h = A[ii][j + 7];
17

18
                    B[j][ii] = a;
19
                    B[j + 1][ii] = b;
20
                    B[j + 2][ii] = c;
21
                    B[j + 3][ii] = d;
22

23
                    B[j][ii + 4] = e;
24
                    B[j + 1][ii + 4] = f;
25
                    B[j + 2][ii + 4] = g;
26
                    B[j + 3][ii + 4] = h;
27
                }
28

29
                for (ii = 0; ii < 4; ii++) {
30
                    a = B[j + ii][i + 4];
31
                    b = B[j + ii][i + 5];
32
                    c = B[j + ii][i + 6];
33
                    d = B[j + ii][i + 7];
34

35
                    e = A[i + 4][j + ii];
36
                    f = A[i + 5][j + ii];
37
                    g = A[i + 6][j + ii];
38
                    h = A[i + 7][j + ii];
39

40
                    B[j + ii][i + 4] = e;
41
                    B[j + ii][i + 5] = f;
42
                    B[j + ii][i + 6] = g;
43
                    B[j + ii][i + 7] = h;
44

45
                    B[j + 4 + ii][i] = a;
46
                    B[j + 4 + ii][i + 1] = b;
47
                    B[j + 4 + ii][i + 2] = c;
48
                    B[j + 4 + ii][i + 3] = d;
49
                }
50

51

52
                for (ii = i + 4; ii < i + 8; ii++) {
53
                    a = A[ii][j + 4];
54
                    b = A[ii][j + 5];
55
                    c = A[ii][j + 6];
56
                    d = A[ii][j + 7];
57

58
                    B[j + 4][ii] = a;
59
                    B[j + 5][ii] = b;
60
                    B[j + 6][ii] = c;
61
                    B[j + 7][ii] = d;
62
                }
63
            }
64
        }
65
        return;
66
    }

运行结果如下，达到了本题的要求

$67 \times 61$ #

本题要求缓存不命中次数小于2000

我们调整参数，发现使用 $16 \times 16$ 分块可以通过此题

1
    if (M == 67 && N == 61) {
2
        int i, j, ii,jj;
3
        for (i = 0; i < 61; i += 16) {
4
            for (j = 0; j < 67; j += 16) {
5
                for (ii = i; ii < i + 16 && ii < 61; ii++) {
6
                    for (jj = j; jj < j + 16 && jj < 67; jj++) {
7
                        B[jj][ii] = A[ii][jj];
8
                    }
9
                }
10
            }
11
        }
12
    }

结果如下

代码#

1
/*
2
 * trans.c - Matrix transpose B = A^T
3
 *
4
 * Each transpose function must have a prototype of the form:
5
 * void trans(int M, int N, int A[N][M], int B[M][N]);
6
 *
7
 * A transpose function is evaluated by counting the number of misses
8
 * on a 1KB direct mapped cache with a block size of 32 bytes.
9
 */
10
#include <stdio.h>
11
#include "cachelab.h"
12

13
int is_transpose(int M, int N, int A[N][M], int B[M][N]);
14

15
/*
16
 * transpose_submit - This is the solution transpose function that you
17
 *     will be graded on for Part B of the assignment. Do not change
18
 *     the description string "Transpose submission", as the driver
19
 *     searches for that string to identify the transpose function to
20
 *     be graded.
21
 */
22
char transpose_submit_desc[] = "Transpose submission";
23
void transpose_submit(int M, int N, int A[N][M], int B[M][N])
24
{
25

26
    if (M == 32 && N == 32) {
27
        int i, j, ii;
28
        int a, b, c, d, e, f, g, h;
29
        for (i = 0; i < N; i += 8) {
30
            for (j = 0; j < M; j += 8) {
31
                for (ii = i; ii < i + 8; ii++) {
32
                    a = A[ii][j];
33
                    b = A[ii][j + 1];
34
                    c = A[ii][j + 2];
35
                    d = A[ii][j + 3];
36
                    e = A[ii][j + 4];
37
                    f = A[ii][j + 5];
38
                    g = A[ii][j + 6];
39
                    h = A[ii][j + 7];
40
                    B[j ][ii] = a;
41
                    B[j + 1][ii] = b;
42
                    B[j + 2][ii] = c;
43
                    B[j + 3][ii] = d;
44
                    B[j + 4][ii] = e;
45
                    B[j + 5][ii] = f;
46
                    B[j + 6][ii] = g;
47
                    B[j + 7][ii] = h;
48
                }
49
            }
50
        }
51
        return;
52
    }
53

54
    if (M == 64 && N == 64) {
55
        int i, j, ii;
56
        int a, b, c, d, e, f, g, h;
57

58
        for (i = 0; i < N; i += 8) {
59
            for (j = 0; j < M; j += 8) {
60
                for (ii = i; ii < i + 4; ii++) {
61
                    a = A[ii][j];
62
                    b = A[ii][j + 1];
63
                    c = A[ii][j + 2];
64
                    d = A[ii][j + 3];
65

66
                    e = A[ii][j + 4];
67
                    f = A[ii][j + 5];
68
                    g = A[ii][j + 6];
69
                    h = A[ii][j + 7];
70

71
                    B[j][ii] = a;
72
                    B[j + 1][ii] = b;
73
                    B[j + 2][ii] = c;
74
                    B[j + 3][ii] = d;
75

76
                    B[j][ii + 4] = e;
77
                    B[j + 1][ii + 4] = f;
78
                    B[j + 2][ii + 4] = g;
79
                    B[j + 3][ii + 4] = h;
80
                }
81

82
                for (ii = 0; ii < 4; ii++) {
83
                    a = B[j + ii][i + 4];
84
                    b = B[j + ii][i + 5];
85
                    c = B[j + ii][i + 6];
86
                    d = B[j + ii][i + 7];
87

88
                    e = A[i + 4][j + ii];
89
                    f = A[i + 5][j + ii];
90
                    g = A[i + 6][j + ii];
91
                    h = A[i + 7][j + ii];
92

93
                    B[j + ii][i + 4] = e;
94
                    B[j + ii][i + 5] = f;
95
                    B[j + ii][i + 6] = g;
96
                    B[j + ii][i + 7] = h;
97

98
                    B[j + 4 + ii][i] = a;
99
                    B[j + 4 + ii][i + 1] = b;
100
                    B[j + 4 + ii][i + 2] = c;
101
                    B[j + 4 + ii][i + 3] = d;
102
                }
103

104

105
                for (ii = i + 4; ii < i + 8; ii++) {
106
                    a = A[ii][j + 4];
107
                    b = A[ii][j + 5];
108
                    c = A[ii][j + 6];
109
                    d = A[ii][j + 7];
110

111
                    B[j + 4][ii] = a;
112
                    B[j + 5][ii] = b;
113
                    B[j + 6][ii] = c;
114
                    B[j + 7][ii] = d;
115
                }
116
            }
117
        }
118
        return;
119
    }
120

121
    if (M == 61 && N == 67) {
122
        int i, j, ii,jj, tmp;
123
        for (i = 0; i < N; i += 16) {
124
            for (j = 0; j < M; j += 16) {
125
                for (ii = i; ii < i + 16 && ii < N; ii++) {
126
                    for (jj = j; jj < j + 16 && jj < M; jj++) {
127
                        tmp = A[ii][jj];
128
                        B[jj][ii] = tmp;
129
                    }
130
                }
131
            }
132
        }
133
    }
134
}
135

136
/*
137
 * You can define additional transpose functions below. We've defined
138
 * a simple one below to help you get started.
139
 */
140

141
/*
142
 * trans - A simple baseline transpose function, not optimized for the cache.
143
 */
144
char trans_desc[] = "Simple row-wise scan transpose";
145
void trans(int M, int N, int A[N][M], int B[M][N])
146
{
147
    int i, j, tmp;
148

149
    for (i = 0; i < N; i++) {
150
        for (j = 0; j < M; j++) {
151
            tmp = A[i][j];
152
            B[j][i] = tmp;
153
        }
154
    }
155
}
156

157
/*
158
 * registerFunctions - This function registers your transpose
159
 *     functions with the driver.  At runtime, the driver will
160
 *     evaluate each of the registered functions and summarize their
161
 *     performance. This is a handy way to experiment with different
162
 *     transpose strategies.
163
 */
164
void registerFunctions()
165
{
166
    /* Register your solution function */
167
    registerTransFunction(transpose_submit, transpose_submit_desc);
168

169
    /* Register any additional transpose functions */
170
    registerTransFunction(trans, trans_desc);
171

172
}
173

174
/*
175
 * is_transpose - This helper function checks if B is the transpose of
176
 *     A. You can check the correctness of your transpose by calling
177
 *     it before returning from the transpose function.
178
 */
179
int is_transpose(int M, int N, int A[N][M], int B[M][N])
180
{
181
    int i, j;
182

183
    for (i = 0; i < N; i++) {
184
        for (j = 0; j < M; ++j) {
185
            if (A[i][j] != B[j][i]) {
186
                return 0;
187
            }
188
        }
189
    }
190
    return 1;
191
}

Katyusha's blog

cache lab#

Part A#

写在前面#

读入部分#

缓存的相关结构#

缓存的读写#

代码#

Part B#

写在前面#

32×3232 \times 3232×32#

64×6464\times6464×64#

67×6167 \times 6167×61#

代码#

目录

$32 \times 32$ #

$64\times64$ #

$67 \times 61$ #