浮沉浪似人潮
哪会没有思念
你我伤心到
讲不出再见
——讲不出再见
完整代码见：CSAPP/cachelab-handout at main · SnowLegend-star/CSAPP (github.com)
Part A: Cache Simulator
这个lab描述背大锅，开始我是真有点没看懂题目的描述。特别是“M 20,1”“L 10,1”，这种描述二义性也太强了，搞得我开始一直以为这是十进制数字，于是把这些数字从十进制转化成二进制进行处理。然后自然是在歪路上越走越远，开始不断自欺欺人来强行往题目的要求上靠，md！耽误了好久才发现地址全是十六进制，之前在瞎忙活。
还有一点，尽量看一章书就做完相应的lab。我之前lab的进度一直落后于看书的进度，就导致完成lab时总是这忘一块那忘一块。这次也是，开始我还纳闷怎么lab说明没提到“cache simulator”是用直接映射、组相连映射还是全相联映射，知道重新把书看了一遍才知道是什么映射完全取决于“E”。
好了，两个与正文无关的坑点就到此为止，下面开始言归正传。
最初我下意识地觉得这lab的“E”都是1,设想是直接把“cache simulator”看成是一个二维数组，然后每行就是一组，这样我还可以额外给每行开辟个存储数据的空间，属于是超出题目要求了，win！
后来真正看懂lab要求的时候惊觉自己才是自作聪明的那个——如果不是直接映射，那每一组
就会有好几行，再加上我打算每行都开辟存储数据的空间，即“cache simulator”每一行存储的是一个二维的数组，那它自己岂不是成三维的了，苦也……索性我是写完“init_Cache”就发现了这个bug，颇有悬崖勒马的感觉。
最后得到的“cache simulator”模式如下：cache看成一个二维数组，组Si
里面的每一行因为不考虑数据位就可以看成是一个结构体元素，有几行就可以看成有几个结构体元素，相当于做了降维处理。写到题解的后半部分的时候，我才发现其实把cache也声明成一个结构体(S,E都是它的成员)才是一个最好的选择。不过也没有精力再去修改了，遂作罢。
把题解的大体框架完成后，我正式迎来了第一个棘手的问题，如下：
由于不会调试，只能嗯看代码。看了好久也没发现哪里有不妥，后来一想按理说“Reference simulator”应该会输出正常的值啊，它也这样只能说明是数据读入的时候出问题了，于是我抱着试一试的心态改掉了main函数的读入命令行部分，果然这时候“Reference simulator”输出就正常了。找到了问题所在，我就开始对比我写的和标准题解之间的异同。
事实证明，良好的视力是一个优秀coder所必备的。由于老眼昏花，导致我一度以为是自己定义的全局变量“E”坏了大事，开始无限懊悔自己当初怎么没把cache定义成一个结构体，这样也就不用被可恶的全局变量折 磨了。头疼了半天，我觉得给所有调用“E”的函数传入“E”这个参数，而不是用该死的全局变量“E”。然而！还是无济于事。tmd！又是竹篮打水。只能傻傻地把代码改回来了……
经过了一个小时的找不同，我终于发现问题出在这个位置。这里应该是“while”，用了“if”就只会读文件一次了，而且读到的是那个不用的“I address，size”，所以才会有上面的错误。至此，我才发现是我错怪了“E”。
修改了main函数之后里答案进了一步，很明显地可以看到是hit相关的函数出现了问题。
仔细排查一番，发现是这个位置写岔了。
修改完之后离正确答案又近了一步，欢呼！
不过接下来的改错又开始恶心了起来，我的大体框架没问题，那肯定又是每个细节坏我大事了。我找了个“yi2.trace”运行了下，发现居然有“Segmentation fault”，这让我似乎抓住了一丝曙光——很有可能是某个变量没被初始化，一番调查下来之后，果然，就是那个我早就怀疑的“index”。改了这个地方，终于是完美通关part A。
相关代码如下：
引入的头文件和相关定义如下：
#include "cachelab.h"
#include<unistd.h>
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include <getopt.h>
typedef struct Cache_Line {
int valid;
int tag;
int time_tamp;
//int* line;
}cache_Line;
int hit_count = 0, miss_count = 0, eviction_count = 0; // 记录冲突不命中、缓存不命中
int verbose = 0; //是否打印详细信息
char t[1000];
cache_Line** Cache;
int S,E;//E的值不会变，而且没有二义性这里对cache的操作抽象出几个函数比较好，不然全堆在一个函数里面严重影响了代码可读性。对cache的相关操作如下：
void print_help() {
printf("Usage: ./csim-ref [-hv] -s <num> -E <num> -b <num> -t <file>\n");
printf("Options:\n");
printf("-h Print this help message.\n");
printf("-v Optional verbose flag.\n");
printf("-s <num> Number of set index bits.\n");
printf("-E <num> Number of lines per set.\n");
printf("-b <num> Number of block offset bits.\n");
printf("-t <file> Trace file.\n\n\n");
printf("Examples:\n");
printf("linux> ./csim -s 4 -E 1 -b 4 -t traces/yi.trace\n");
printf("linux> ./csim -v -s 8 -E 2 -b 4 -t traces/yi.trace\n");
exit(0);
}
void init_Cache(int s, int E, int b) {//直接映射型的cache可以看成是一个大二维数组，开始把它初始化
int i, j;
S = 1 << s;
//int B = 1 << b;
Cache = (cache_Line**)malloc(sizeof(cache_Line*) * S);
for (i = 0; i < S; i++) {
Cache[i] = (cache_Line*)malloc(sizeof(cache_Line)*E);
//Cache[i]->line = (int*)malloc(sizeof(int) * B);
for (j = 0; j < E; j++) {
Cache[i][j].valid = 0;
Cache[i][j].tag = -1;
Cache[i][j].time_tamp = 0;
//Cache[i]->line[j] = 0;
}
}
}
int is_Full(int opt_s) {//判断这一组的行是不是都缓存满了
int j;
for (j = 0; j < E; j++) {
if (Cache[opt_s][j].valid == 0)
return j;//如果没满，就把第一个没满的行返回去
}
return -1;//满了就返回-1
}
int is_Hit(int opt_tag, int opt_s) {//判断是否命中
int i;
for (i = 0; i < E; i++) {//开始遍历相应的组是否有这个缓存
if (Cache[opt_s][i].valid && Cache[opt_s][i].tag == opt_tag) {//缓存命中
return i;
}
}
// printf("In is_Hit:E=%d",E);
return -1;
}
int replace_Line(int opt_s) {//找出最久时间没被访问的那行
int max_tamp=0, i;
int index=0; //就因为这里index没有初始化导致一直有三个地方过不了
for (i = 0; i < E; i++) {
if (Cache[opt_s][i].time_tamp > max_tamp) {//
max_tamp = Cache[opt_s][i].time_tamp;
index = i;
}
}
return index;
}
void update_Line(int line_replaced, int opt_s, int opt_tag) {//更新每一行的时间tamp
int j=0;
Cache[opt_s][line_replaced].valid = 1;
Cache[opt_s][line_replaced].tag = opt_tag;
for (j = 0; j < E; j++) {//这组所有行的时间都加1，不用考虑这行的valid是否为1
Cache[opt_s][j].time_tamp++;
}
Cache[opt_s][line_replaced].time_tamp = 0;
}
void update_Cache(int opt_tag, int opt_s) {
int flag = is_Hit(opt_tag, opt_s);
int line_replaced = -1;
if (flag == -1) {
miss_count++;
if (verbose)
printf("miss \n");
line_replaced = is_Full(opt_s);
if (line_replaced==-1) {//如果是冲突不命中(改组的缓存行满了)
eviction_count++;
printf("1111");//怎么不打印啊。。。
if (verbose)
printf("eviction \n");
//如果index没有初始化，打印完eviction直接就报错了，有些奇怪。难道不是得执行完replace_Line后再报错吗？
line_replaced = replace_Line(opt_s);
}
update_Line(line_replaced, opt_s, opt_tag);
}
else {
hit_count++;
if (verbose)
printf("hit \n");
update_Line(flag, opt_s, opt_tag);//命中了也得更新行信息
}
}
void get_Trace(int s, int E, int b) {
FILE* pFile;
pFile = fopen(t, "r");
int mask_s = ((1 << s)-1) << b; //索引位s的掩码
if (pFile == NULL) {
exit(1);
}
char option;
unsigned address;
int size;
while (fscanf(pFile, "%c %x,%d", &option, &address, &size) > 0) {
int opt_tag = address >> (s + b);
// int opt_s = (address >> b) & ((unsigned)(-1) >> (8 * sizeof(unsigned) - s));//进行逻辑右移
int opt_s=(unsigned)(address&mask_s)>>b;//这样其实也可以的，可恶
switch (option)
{
case 'M'://可以分解为一次L和一次S
update_Cache(opt_tag, opt_s);
update_Cache(opt_tag, opt_s);
break;
case 'L':
update_Cache(opt_tag, opt_s);
break;
case 'S':
update_Cache(opt_tag, opt_s);
break;
default:
break;
}
}
fclose(pFile);
}
void free_Cache(){
int i;
for(i=0;i<S;i++)
free(Cache[i]);
free(Cache);
}
main函数如下：
int main(int argc,char *argv[]) {
char opt;
int s,b;
while ((opt = getopt(argc, argv, "hvs:E:b:t:"))!=-1) {//这里t后面没：怎么不报错啊 这里是while而不是if
switch (opt) {
case 'h':
print_help();
break;
case 'v':
verbose = 1;
break;
case 's':
s = atoi(optarg);
break;
case 'E':
E = atoi(optarg);
// E=e;
break;
case 'b':
b = atoi(optarg);
break;
case 't':
strcpy(t, optarg);
break;
default:
printf("Something wrong with your command,try './csim-ref -h' for help.");
exit(0);
}
}
init_Cache(s, E, b);
get_Trace(s, E, b);
printSummary(hit_count, miss_count, eviction_count);
free_Cache();
return 0;
}
Part B: Optimizing Matrix Transpose
这个lab是目前我觉得最上强度的一个，搞得我头昏脑涨，思路乱成一团，几欲放弃。好在nerd精神发挥了作用，到底还是坚持了下来。没想到一个简单的矩阵转置还有如此巧妙的地方，完成这个lab也算是给我带来了不菲的收获。
32×32型
其实这三个lab本质是差不多的，就是要彻底理解cache的miss、hit、eviction这三部分，而且part B更侧重miss的计算。Tmd，最恶心的就是算miss数量。我算了几天没算明白，还是下午上英语课的时候拿草稿纸出来算才真正算明白了，下面细说怎么算32×32型矩阵的miss数量。
首先，我们根据实验说明的“(s = 5, E = 1, b = 5)”可以知道cache是直接映射的，它有32组，每行(组)有32byte可以拿来存数据，也就是每行可以存8个int类型的数据。对于A、B两个数组都是32×32的整形二维数组来说，A的一行在cache里面会被映射到4组即4行。
我们先用说明文档给的“./csim-ref -v -s 5 -E 1 -b 5 -t trace.f0”这句命令来查看下二维数组A、B的首地址。可以看到A的首地址应该就是0x10d080，B的首地址是0x1ad080，而他俩的地址之差是0x14d080-0x10d080=0x4 0000。根据地址的格式，0-4位是块内偏移，5-9位是组号，可以发现A[i][j]和B[i][j]会被映射到cache的同一个位置。
我们把分块的大小定义为size×size，那这个块内最好不存在有两个A的元素被映射到cache的同一个位置。举个例子，假设把块定义为9×9，且A[0][0]~A[0][7]映射到cache的第0组，A[0][8]~A[0][15]映射到cache的第1组……以此类推。那到了A[8][0]~A[8][7]的时候，这八个元素又会被映射到第0组。
在赋值给B[0][8]的时候，就要用到A[8][0]了，此时第0组的元素从A[0][0]~A[0][7]被替换为A[8][0]~A[8][7]。当继续给B[1][0]赋值的时候，会访问A[0][1]。但此时A[0][1]已经被逐出cache了，系统又得重新把A[0][0]~A[0][7]的内容调入第0组，最后导致miss和eviction的情况暴增。但是size太小虽然数组不会在分块内有元素映射冲突，但是利用到的cache组数又会变少，浪费了cache的存储能力。
故比较好的size大小应该是8×8，此时块内元素不存在访问冲突，而且元素的跨度恰好等于cache的大小。得到了分块的大小，我们开始着手计算不同方案的miss数量。最容易想到的方案是把实例那个加上分块策略。
分块直接赋值法
理论上它的miss数应该是(8+8)*16=256，但结果却是343，和我们预计的相差甚远。
遂从第一块开始分析。
块内第0行的赋值情况如下(S代表组的序号)：
| A元素映射情况 | 命中情况 | Cache的映射情况 | B元素映射情况 | 命中情况 | Cache的映射情况 |
| A[0][0]->S0 | miss | S0:A[0][0]~A[0][7] | B[0][0] ->S0 | evict miss | S0: B[0][0]~B[0][7] |
| A[0][1]->S0 | evict miss | S0:A[0][0]~A[0][7] | B[1][0]~B[1][7]->S4 | miss | S4: B[1][0]~B[1][7] |
| A[0][2]->S0 | hit | S0:A[0][0]~A[0][7] | B[2][0]~B[2][7]->S8 | miss | S8: B[2][0]~B[2][7] |
| … | hit | S0:A[0][0]~A[0][7] | … | miss | S(4*i):B[i][0]~B[i][7] |
| A[0][7]->S0 | hit | S0:A[0][0]~A[0][7] | B[7][0]~B[0][7]->S28 | miss | S28: B[7][0]~B[7][7] |
| miss次数 | A：2次 | B：8次 | 共计10次 |
此时S0被A占据，B则占据了S4、S8、S12、S16、S20、S24、S28
块内第1行的赋值情况如下：
| A元素映射情况 | B元素映射情况 | ||||
| A[1][0]->S4 | evict miss | S4:A[1][0]~A[1][7] | B[0][1]->S0 | evict miss | S0: B[0][0]~B[0][7] |
| A[1][1]->S4 | hit | S4:A[1][0]~A[1][7] | B[1][1]->S4 | evict miss | S4: B[1][1]~B[1][7] |
| A[1][2]->S4 | evict miss | S4:A[1][0]~A[1][7] | B[2][1]->S8 | hit | S8: B[2][0]~B[2][7] |
| … | hit | S4:A[1][0]~A[1][7] | … | hit | S(4*i):B[i][0]~B[i][7] |
| A[1][7]->S4 | hit | S4:A[1][0]~A[1][7] | B[7][1]->S28 | hit | S28: B[7][0]~B[7][7] |
| miss次数 | A：2次 | B：2次 | 共计4次 |
此时A占据S4，B占据S0、S8、S12、S16、S20、S24、S28
块内第2行的赋值情况如下：
| A元素映射情况 | B元素映射情况 | ||||
| A[2][0]->S8 | evict miss | S8:A[2][0]~A[2][7] | B[0][2]->S0 | hit | S0: B[0][0]~B[0][7] |
| A[2][1]->S8 | hit | S8:A[2][0]~A[2][7] | B[1][2]->S4 | evict miss | S4: B[1][1]~B[1][7] |
| A[2][2]->S8 | hit | S8:A[2][0]~A[2][7] | B[2][2]->S8 | evict miss | S8: B[2][0]~B[2][7] |
| A[2][3]->S8 | evict miss | S8:A[2][0]~A[2][7] | B[3][2]->S12 | hit | S12:B[3][0]~B[3][77] |
| … | hit | S8:A[2][0]~A[2][7] | … | hit | S(4*i):B[i][0]~B[i][7] |
| A[2][7]->S8 | hit | S8:A[2][0]~A[2][7] | B[7][1]->S28 | hit | S28: B[7][0]~B[7][7] |
| miss次数 | A：2次 | B：2次 | 共计4次 |
此时A占据S8，B占据S0、S4、S12、S16、S20、S24、S28
块内第7行的赋值情况如下：
| A元素映射情况 | B元素映射情况 | ||||
| A[7][0]->S28 | evict miss | S28:A[7][0]~A[7][6] | B[0][2]->S0 | hit | S0: B[0][0]~B[0][7] |
| A[7][1]->S28 | hit | S28:A[7][0]~A[7][6] | B[1][2]->S4 | hit | S4: B[1][1]~B[1][7] |
| A[7][2]->S28 | hit | S28:A[7][0]~A[7][6] | B[2][2]->S8 | hit | S8: B[2][0]~B[2][7] |
| … | hit | S28:A[7][0]~A[7][6] | … | hit | S(4*i):B[i][0]~B[i][7] |
| A[7][6]->S28 | hit | S28:A[7][0]~A[7][6] | B[6][7]->S24 | evict miss | S24:B[6][0]~B[6]][7] |
| A[7][7]->S28 | hit | S28:A[7][0]~A[7][6] | B[7][1]->S28 | evict miss | S28: B[7][0]~B[7][7] |
| miss次数 | A：1次 | B：2次 | 共计3次 |
此时A占据S28，B占据S0、S4、S8、S12、S16、S20、S24、S28
我们可以发现一个规律，当处理第i(1<=i<=6)行时，A会占据S(4*i)这组，导致两次miss和eviction；B由于S(4*i)块被A占据会m/e一次，同时由于S(i*(i-1))也被A占据又会m/e一次。第7行由于A不会再访问一次S(4*i)，所以就会少一次m/e。
对于那些不在对角线上的块，我们很容易就可以发现因为不存在A[i][j] (i=j)、B[i][j](i=j)这种元素，就不会存在A的元素和B的元素映射到cache的同一个位置。只会存在每行在第一次访问A[i][0]有miss，第一次访问B[i][0]有一个miss。所以每个块一共有8+8个miss。
综上，分块直接赋值法miss次数是(8+8)*12+(10+4*6+3)*4=340，和实际跑出来的结果343有个3的误差。其实通过后面的定量计算，可以发现计算的和跑出来的结果一直有这个误差，可能是程序在访问A、B数组之前也进行了别的操作导致3次miss。
分块循环展开法
通过上面的直接赋值法，我们发现因为交叉访问A数组的元素和B数组的元素导致m/e问题，那是不是可以考虑一下子提取块内第i行的A[i][0]~A[i][7]并把它们放在临变量中，再用8个临时变量给B对应的列赋值呢？这个思想就是第五章的循环展开，我们计算一下miss看是否可行。
块内第0行的赋值情况如下
| A元素映射情况 | 命中情况 | Cache的映射情况 | B元素映射情况 | 命中情况 | Cache的映射情况 |
| A[0][0]->S0 | miss | S0:A[0][0]~A[0][7] | B[0][0] ->S0 | evict miss | S0: B[0][0]~B[0][7] |
| A[0][1]->S0 | hit | S0:A[0][0]~A[0][7] | B[1][0]~B[1][7]->S4 | miss | S4: B[1][0]~B[1][7] |
| A[0][2]->S0 | hit | S0:A[0][0]~A[0][7] | B[2][0]~B[2][7]->S8 | miss | S8: B[2][0]~B[2][7] |
| … | hit | S0:A[0][0]~A[0][7] | … | miss | S(4*i):B[i][0]~B[i][7] |
| A[0][7]->S0 | hit | S0:A[0][0]~A[0][7] | B[7][0]~B[0][7]->S28 | miss | S28: B[7][0]~B[7][7] |
| miss次数 | A：1次 | B：8次 | 共计9次 |
此时A原本占据的S0也被B窃取了，B则占据了S0、S4、S8、S12、S16、S20、S24、S28八组
块内第1行的赋值情况如下：
| A元素映射情况 | B元素映射情况 | ||||
| A[1][0]->S4 | evict miss | S4:A[1][0]~A[1][7] | B[0][1]->S0 | hit | S0: B[0][0]~B[0][7] |
| A[1][1]->S4 | hit | S4:A[1][0]~A[1][7] | B[1][1]->S4 | evict miss | S4: B[1][1]~B[1][7] |
| A[1][2]->S4 | hit | S4:A[1][0]~A[1][7] | B[2][1]->S8 | hit | S8: B[2][0]~B[2][7] |
| … | hit | S4:A[1][0]~A[1][7] | … | hit | S(4*i):B[i][0]~B[i][7] |
| A[1][7]->S4 | hit | S4:A[1][0]~A[1][7] | B[7][1]->S28 | hit | S28: B[7][0]~B[7][7] |
| miss次数 | A：1次 | B：1次 | 共计2次 |
此时A访问结束后还是一组也没占据，B占据S0、S4、S8、S12、S16、S20、S24、S28
块内第2行的赋值情况如下：
| A元素映射情况 | B元素映射情况 | ||||
| A[2][0]->S8 | evict miss | S8:A[2][0]~A[2][7] | B[0][2]->S0 | hit | S0: B[0][0]~B[0][7] |
| A[2][1]->S8 | hit | S8:A[2][0]~A[2][7] | B[1][2]->S4 | hit | S4: B[1][1]~B[1][7] |
| A[2][2]->S8 | hit | S8:A[2][0]~A[2][7] | B[2][2]->S8 | evict miss | S8: B[2][0]~B[2][7] |
| A[2][3]->S8 | hit | S8:A[2][0]~A[2][7] | B[3][2]->S12 | hit | S12:B[3][0]~B[3][77] |
| … | hit | S8:A[2][0]~A[2][7] | … | hit | S(4*i):B[i][0]~B[i][7] |
| A[2][7]->S8 | hit | S8:A[2][0]~A[2][7] | B[7][1]->S28 | hit | S28: B[7][0]~B[7][7] |
| miss次数 | A：1次 | B：2次 | 共计3次 |
A访问结束后仍然一无所有，B占据S0、S4、S8、、S12、S16、S20、S24、S28
块内第7行的赋值情况如下：
| A元素映射情况 | B元素映射情况 | ||||
| A[7][0]->S28 | evict miss | S28:A[7][0]~A[7][6] | B[0][2]->S0 | hit | S0: B[0][0]~B[0][7] |
| A[7][1]->S28 | hit | S28:A[7][0]~A[7][6] | B[1][2]->S4 | hit | S4: B[1][1]~B[1][7] |
| A[7][2]->S28 | hit | S28:A[7][0]~A[7][6] | B[2][2]->S8 | hit | S8: B[2][0]~B[2][7] |
| … | hit | S28:A[7][0]~A[7][6] | … | hit | S(4*i):B[i][0]~B[i][7] |
| A[7][6]->S28 | hit | S28:A[7][0]~A[7][6] | B[6][7]->S24 | hit | S24:B[6][0]~B[6]][7] |
| A[7][7]->S28 | hit | S28:A[7][0]~A[7][6] | B[7][1]->S28 | evict miss | S28: B[7][0]~B[7][7] |
| miss次数 | A：1次 | B：1次 | 共计1次 |
此时A一如既往啥也没有，B占据S0、S4、S8、S12、S16、S20、S24、S28
我们发现，通过循环展开法，当i∈[0,6]
访问A时减少了一次m/e，当i∈[1,7]
访问B时减少了一次m/e。总的来说相较直接赋值法减少了14次m/e。对于未处在对角线上的块，访问的miss数依然是8+8。
综上，分块循环展开法的miss数是(8+8)*12+(9+2*7)*4=284，和输出结果287也是差了3。
分块循环展开plus
其实上面两个方法有个共同的问题，就是每次访问B[i][j](i=j)时就会导致m/e。这是因为对于A我们总是按行加载，对于B总是按列加载，这样势必导致在B[k][k]处有m/e冲突。如果我们把A按行赋值给B，那岂不是可以消除在B[k][k]处的m/e冲突呢?最后单独给B进行转置，而对B自己进行转置的时候是没有miss的。
写这个函数的时候有个地方疏忽了，导致数组访问一直有越界的问题，但是这种涉及矩阵的问题数据元素又特别多，调试起来十分麻烦。忙活了一个小时没找到代码内部结构的问题。后来猛然发现原来是最初的大循环条件就写错了，记得当时在平板上手动模拟的时候大循环的条件也写错过，这下属于是在同一个地方跌倒两次了。汗流浃背。
这个方法分析起来比较简单，对角线上的块的miss数也是(8+8)，所以结果跑出来应该是16*16+3=259。
实现代码如下：
void trans_32x32_Mtx(int M, int N, int A[N][M], int B[M][N]){
int i,j,k,s;
for(i=0;i<32;i+=8)//汗流浃背了，把i+=8写成了i++；j也是这样
for(j=0;j<32;j+=8){
for(k=0;k<8;k++){
int a0=A[i+k][j+0];
int a1=A[i+k][j+1];
int a2=A[i+k][j+2];
int a3=A[i+k][j+3];
int a4=A[i+k][j+4];
int a5=A[i+k][j+5];
int a6=A[i+k][j+6];
int a7=A[i+k][j+7];
B[j+k][i+0]=a0;
B[j+k][i+1]=a1;
B[j+k][i+2]=a2;
B[j+k][i+3]=a3;
B[j+k][i+4]=a4;
B[j+k][i+5]=a5;
B[j+k][i+6]=a6;
B[j+k][i+7]=a7;
}
for(k=0;k<8;k++)
for(s=k+1;s<8;s++){
int tmp=B[j+k][i+s];
B[j+k][i+s]=B[j+s][i+k];
B[j+s][i+k]=tmp;
}
}
// for (int i = 0; i < N; i += 8)
// for (int j = 0; j < M; j += 8)
// for (int k = 0; k < 8; k++)
// for (int s = 0; s < 8; s++)
// B[j + s][i + k] = A[i + k][j + s];
}
64×64型
这个我也没悟透，用上面的分块思路把块的大小设置为4×4硬写。满昏8分我就得了3.4，属于是黔驴技穷了……
实现代码如下：
void trans_64x64_Mtx(int M, int N, int A[N][M], int B[M][N]){
int i,j,k;
for(i=0;i<64;i+=4)
for(j=0;j<64;j+=4){
for(k=0;k<4;k++){
int a0=A[i+k][j+0];
int a1=A[i+k][j+1];
int a2=A[i+k][j+2];
int a3=A[i+k][j+3];
// int a4=A[i+k][j+4];
// int a5=A[i+k][j+5];
// int a6=A[i+k][j+6];
// int a7=A[i+k][j+7];
B[j+0][i+k]=a0;
B[j+1][i+k]=a1;
B[j+2][i+k]=a2;
B[j+3][i+k]=a3;
// B[j+4][i+k]=a4;
// B[j+5][i+k]=a5;
// B[j+6][i+k]=a6;
// B[j+7][i+k]=a7;
}
}
}
67×61型
我看这个矩阵都不是方阵，好像没有特别好的分块方法，拿4×4、8×8、16×16硬套，最后发现块的大小设置为16×16可以擦边满分过。小win！
对了,“./driver.py”文件是cmu的老师用python2写的，假如自己系统装的是python3，得适当改写下。我是直接搬大佬的dirver.py。
实现代码如下：
void trans_61x67_Mtx(int M,int N,int A[N][M],int B[M][N]){
for (int i = 0; i < N; i += 16)
for (int j = 0; j < M; j += 16)
for (int k = i; k < i + 16 && k < N; k++)
for (int s = j; s < j + 16 && s < M; s++)
B[s][k] = A[k][s];
}driver.py如下
#!/usr//bin/python3
#
# driver.py - The driver tests the correctness of the student's cache
# simulator and the correctness and performance of their transpose
# function. It uses ./test-csim to check the correctness of the
# simulator and it runs ./test-trans on three different sized
# matrices (32x32, 64x64, and 61x67) to test the correctness and
# performance of the transpose function.
#
import subprocess;
import re;
import os;
import sys;
import optparse;
#
# computeMissScore - compute the score depending on the number of
# cache misses
#
def computeMissScore(miss, lower, upper, full_score):
if miss <= lower:
return full_score
if miss >= upper:
return 0
score = (miss - lower) * 1.0
range = (upper- lower) * 1.0
return round((1 - score / range) * full_score, 1)
#
# main - Main function
#
def main():
# Configure maxscores here
maxscore= {};
maxscore['csim'] = 27
maxscore['transc'] = 1
maxscore['trans32'] = 8
maxscore['trans64'] = 8
maxscore['trans61'] = 10
# Parse the command line arguments
p = optparse.OptionParser()
p.add_option("-A", action="store_true", dest="autograde",
help="emit autoresult string for Autolab");
opts, args = p.parse_args()
autograde = opts.autograde
# Check the correctness of the cache simulator
print ("Part A: Testing cache simulator")
print ("Running ./test-csim")
p = subprocess.Popen("./test-csim",
shell=True, stdout=subprocess.PIPE)
stdout_data = p.communicate()[0]
# Emit the output from test-csim
stdout_data = re.split("\n", str(stdout_data, 'utf-8'))
for line in stdout_data:
if re.match("TEST_CSIM_RESULTS", line):
resultsim = re.findall(r'(\d+)', line)
else:
print ("%s" % (line))
# Check the correctness and performance of the transpose function
# 32x32 transpose
print ("Part B: Testing transpose function")
print ("Running ./test-trans -M 32 -N 32")
p = subprocess.Popen("./test-trans -M 32 -N 32 | grep TEST_TRANS_RESULTS",
shell=True, stdout=subprocess.PIPE)
stdout_data = p.communicate()[0]
result32 = re.findall(r'(\d+)', str(stdout_data, 'utf-8'))
# 64x64 transpose
print ("Running ./test-trans -M 64 -N 64")
p = subprocess.Popen("./test-trans -M 64 -N 64 | grep TEST_TRANS_RESULTS",
shell=True, stdout=subprocess.PIPE)
stdout_data = p.communicate()[0]
result64 = re.findall(r'(\d+)', str(stdout_data, 'utf-8'))
# 61x67 transpose
print ("Running ./test-trans -M 61 -N 67")
p = subprocess.Popen("./test-trans -M 61 -N 67 | grep TEST_TRANS_RESULTS",
shell=True, stdout=subprocess.PIPE)
stdout_data = p.communicate()[0]
result61 = re.findall(r'(\d+)', str(stdout_data, 'utf-8'))
# Compute the scores for each step
csim_cscore = list(map(int, resultsim[0:1]))
trans_cscore = int(result32[0]) * int(result64[0]) * int(result61[0]);
miss32 = int(result32[1])
miss64 = int(result64[1])
miss61 = int(result61[1])
trans32_score = computeMissScore(miss32, 300, 600, maxscore['trans32']) * int(result32[0])
trans64_score = computeMissScore(miss64, 1300, 2000, maxscore['trans64']) * int(result64[0])
trans61_score = computeMissScore(miss61, 2000, 3000, maxscore['trans61']) * int(result61[0])
total_score = csim_cscore[0] + trans32_score + trans64_score + trans61_score
# Summarize the results
print ("\nCache Lab summary:")
print ("%-22s%8s%10s%12s" % ("", "Points", "Max pts", "Misses"))
print ("%-22s%8.1f%10d" % ("Csim correctness", csim_cscore[0],
maxscore['csim']))
misses = str(miss32)
if miss32 == 2**31-1 :
misses = "invalid"
print ("%-22s%8.1f%10d%12s" % ("Trans perf 32x32", trans32_score,
maxscore['trans32'], misses))
misses = str(miss64)
if miss64 == 2**31-1 :
misses = "invalid"
print ("%-22s%8.1f%10d%12s" % ("Trans perf 64x64", trans64_score,
maxscore['trans64'], misses))
misses = str(miss61)
if miss61 == 2**31-1 :
misses = "invalid"
print ("%-22s%8.1f%10d%12s" % ("Trans perf 61x67", trans61_score,
maxscore['trans61'], misses))
print ("%22s%8.1f%10d" % ("Total points", total_score,
maxscore['csim'] +
maxscore['trans32'] +
maxscore['trans64'] +
maxscore['trans61']))
# Emit autoresult string for Autolab if called with -A option
if autograde:
autoresult="%.1f:%d:%d:%d" % (total_score, miss32, miss64, miss61)
print ("\nAUTORESULT_STRING=%s" % autoresult)
# execute main only if called as a script
if __name__ == "__main__":
main()