用个人的信息备案网站吗,高校校园网站建设项目的要求,2022年网络热点事件舆情案例,百度怎么优化排名文章目录 Part APart B32 * 3264 * 6461 * 67 实验全程参考大佬的博客CS:APP3e 深入理解计算机系统_3e CacheLab实验 #xff0c;感觉大佬在矩阵转置那块介绍的还是有些简略#xff0c;我自己又做了点动图加以补充理解。膜拜大佬#xff01; Part A
先解决解析命令行参数的… 文章目录 Part APart B32 * 3264 * 6461 * 67 实验全程参考大佬的博客CS:APP3e 深入理解计算机系统_3e CacheLab实验 感觉大佬在矩阵转置那块介绍的还是有些简略我自己又做了点动图加以补充理解。膜拜大佬 Part A
先解决解析命令行参数的问题文档推荐使用getopt()函数进行解析
#include unistd.h
#include stdlib.h
#include getopt.h
int getopt(int argc, char *const argv[], const char *optstring);着重关注第三个参数——选项字符串如ab:c:de::就是一个选项字符串。对应到命令行就是-a ,-b ,-c ,-d, -e。冒号表示参数一个冒号就表示这个选项后面必须带有参数但是这个参数可以和选项连在一起写也可以用空格隔开比如-b123和-b 123。两个冒号的就表示这个选项的参数是可选的即可以有参数也可以没有参数有参数时参数与选项之间不能有空格。如果后面不带冒号则说明没有选项参数。
其返回值就是对应选项字符的ascii码值有选项参数则参数字符串保存在extern char* optarg中。如果选项读完了就返回-1。更具体的信息可以使用man手册查看man 3 getopt。
我们要实现的例子中命令行参数有[-hv] -s s -E E -b b -t tracefile所以对应的选项字符串就是hvs:E:b:t:。
首先需要定义缓存数据结构cache的结构如下
由于题目只关注hit/miss/eviction的次数不需要实际存取数据为了简便就不实现缓存块block了如果实现的话就是添加一个指针分配缓存空间的时候需要malloc分配2b个字节的空间。所以只需要valid和tag即可。
题目要求替换算法采用LRU也就是eviction时替换最近没有被使用的line所以需要添加一个记录最后访问时间的成员每次访问的时候就更新一下。这里直接采用最简单粗暴的方式用一个时间戳从0开始计数每访问一次就1最小的则是访问时间最为久远的进行替换。
由此可以定义数据类型
typedef struct
{bool valid;unsigned long tag;unsigned long time;
}line_;这就是line的类型2e个行构成了一个组(set)为了方便再定义一个组类型
typedef line_* set_;组其实就是一个line数组数组名是指针类型后续方便malloc动态分配2e * sizeof(line_)的空间。
然后2s个组就构成了整个缓存结构所以3为了方便再定义一个类型
typedef set_* cache_;和上面一样这就是一个set数组后续分配2s * sizeof(set_)的空间。
需要定义三个全局变量记录最终结果
int hit;
int miss;
int eviction;此外还需要定义几个全局变量分别是-h选项对应的help信息这个直接照抄示例程序的就行
const char *help_message
Usage: ./csim-ref [-hv] -s num -E num -b num -t file\n\
Options:\n\-h Print this help message.\n\-v Optional verbose flag.\n\-s num Number of set index bits.\n\-E num Number of lines per set.\n\-b num Number of block offset bits.\n\-t file Trace file.\n\n\
Examples:\n\linux ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace\n\linux ./csim-ref -v -s 8 -E 2 -b 4 -t traces/yi.trace;选项字符串
const char *command_options hvs:E:b:t:;要追踪的文件名
FILE* tracefile NULL;缓存对象
cache_ cache NULL;是否输入-v选项也就是是否显示跟踪信息的可选详细标志默认为false当命令行参数检测到v后置为true即可
bool verbose false;还有几个记录缓存大小相关的数据
unsigned long s 0;
unsigned long b 0;
unsigned long S 0;
unsigned long E 0;其中2s是sets的数量2b是每行中缓存块的数量这里不关注S就是块的数量数值等于2sE是每个set中的line数。
数据类型定义完成开始逐步处理。首先是解析命令行参数代码如下
int checkCommand(int argc, char* argv[])
{char ch;while ((ch getopt(argc, argv, command_options)) ! -1){switch(ch){case h:printf(%s\n, help_message);exit(0);case v:verbose true;break;case s:s atol(optarg);S 1 s;if (s 0){printf(%s\n, help_message);exit(-1);}break;case E:E atol(optarg);if (E 0){printf(%s\n, help_message);exit(-1);}break;case b:b atol(optarg);if (b 0){printf(%s\n, help_message);exit(-1);}break;case t:if ((tracefile fopen(optarg, r)) NULL){printf(%s\n, Failed to open tracefile);exit(-1);}break;default:printf(%s\n, help_message);exit(-1);}}if (s 0 || b 0 || E 0 || tracefile NULL){printf(%s\n, Command line arguments are missing);printf(%s\n, help_message);exit(-1);}
}while嵌套switch结构仅仅能判断输入的命令行参数中输入的值合法但不能判断缺少命令行参数的情况。所以还需要加个if判断确保命令行参数输入齐全。
接下来该给缓存对象分配空间了一共需要开辟S个set每个块中开辟E个line每个line中就不需要开辟block了。我们此前定义的缓存对象为cache_ cache NULL其中cache_是set_*类型所以cache是一个set数组指针每一个成员是一个set一共有S个成员所以需要给它分配S * sizeof(set_)个字节的空间并且需要初始化为0。对于它的每一个成员又是一个line数组每个成员都有E个line所以需要循环遍历给每个成员开辟E * sizeof(line_)个字节的空间
void initCache()
{cache calloc(S, sizeof(set_));if (cache NULL){printf(Failed to calloc set\n);exit(-1);}for (unsigned long i 0; i S; i){cache[i] calloc(E, sizeof(line_));if (cache[i] NULL){printf(Failed to calloc line\n);exit(-1);}}
}同时把free函数也写出来开辟时从上至下开辟释放时就要从下至上释放
void freeCache()
{for (unsigned long i 0; i S; i)free(cache[i]);free(cache);
}接下来就是程序的核心部分测试hit/miss/eviction的次数。
文件中I表示指令加载我们要统计的是数据加载所以遇到I开头的指令直接忽略其余指令开头都有一个空格以此区分。
如果命令是L(a data load)或S(a data store)则需要判断一次是否命中或替换。如果命令是M(a data modify, a data load followed by a data store)则相当于一个L和一个M需要进行两次判断。
判断用一个函数实现那这个函数需要哪些参数呢这就需要了解缓存读取规则了。
首先进行组选择也就是在哪个set中进行查找通过提取addr对应图中的s bits位可以得到(addr b) ((1 s) - 1)。 首先addr b得到低s位为目标值(1 s) - 1得到低s位为全1二者按位与即为目标值。 然后进行行匹配这一步需要提取tagaddr (s b)。
所以测试函数就可以写出来
void test()
{char op;unsigned long addr;int size;while (fscanf(tracefile, %c %lx,%d, op, addr, size) ! EOF){if (op I)continue;if (verbose)printf(%c %lx , op, addr);unsigned long set_index (addr b) ((1 s) - 1);unsigned long tag addr (b s);if (op L || op S)judge(set_index, tag);else if (op M){judge(set_index, tag);judge(set_index, tag);}}
}接下来需要完善judge判断函数判断每次访问是hit还是miss或是eviction。
现在拿到了要查找的set的下标只需要遍历set匹配tag即可。如果匹配上了并且valid是true就是hit更新时间戳judge结束直接返回即可。如果miss了则需要找出上次访问时间最为久远的line如果没数据则填充进去(因为没有实现block所以直接将valid置为true即可)然后更新tag和时间戳如果有数据则发生冲突eviction。time值最小的line那个自然就是要替换的然后更新time也要注意这里有两种策略一种是在遍历的同时把最大的time记录下来1就是要更新的值或者设置一个全局变量计数。这里采用前者策略。
所以judge函数也就写出来了
void judge(unsigned long set_index, unsigned long tag)
{for (unsigned long i 0; i E; i){if (cache[set_index][i].tag tag cache[set_index][i].valid){if (verbose)printf(hit\n);hit;cache[set_index][i].time;return;}}if (verbose)printf(miss\n);miss;// 找出时间戳最小的一个并记录下标同时记录最大的时间戳unsigned long max 0, min -1, line_index 0;for (unsigned long i 0; i E; i){if (cache[set_index][i].time min){min cache[set_index][i].time;line_index i;}if (cache[set_index][i].time max)max cache[set_index][i].time;}cache[set_index][line_index].time max 1;cache[set_index][line_index].tag tag;if (cache[set_index][line_index].valid){if (verbose)printf( and eviction\n);eviction;}else{if (verbose)printf(\n);cache[set_index][line_index].valid true;}
}拼凑一下就凑出了main函数
int main(int argc, char* argv[])
{checkCommand(argc, argv);initCache();test();freeCache();printSummary(hit, miss, eviction);return 0;
}测试一下可以通过
Part B
以下均假设数组第一个元素映射到set[0][0] 为前提。
文档给了缓存的大小参数s 5, E 1, b 5其实就是下面这样
一共有25 32个set每个set有1个line每个line中有25 32byte大小的block可以存放32 / 4 8个int类型的数据。所以cache最多存放32 * 8 256个int类型的数据。那么当(int1 - int2) / 4 256 * k时两个数据就会映射到同一个位置也就是会发生冲突。
以32*32的矩阵进行举例一行32个int需要占用4个set所以缓存一次性最多存8行也就是两个元素正好差八行的整数倍就会发生冲突比如A[7][0] A[0][0]二者会映射到同一个位置会发生冲突。
不过这种冲突情况是不会发生的因为A转置到B的两个元素并不会正好相差8*k行。
还有一个很隐藏的点在文件tracegen.c文件中可以看到A、B数组原型为A[256][256]俩都是256 * 256的数组A[0][0]和B[0][0]正好差了256 * 256个数据会映射到同一个位置这个是很重要的所以如果进行B[7][0] A[0][0]这样的赋值也会发生冲突。因为B[7][0]和A[7][0]映射到了一个位置。并且在转置过程中对角线上的元素是不变的也就是B[i][i] A[i][i]如果直接赋值也必然会发生冲突需要单独考虑。
32 * 32
下面尝试8 * 8进行矩阵分块理解一下分块是如何减少不命中和冲突的下图中每一个色块覆盖8*8的区域
缓存映射情况如下
以绿色色块为例
左侧对应A数组右侧对应B数组。赋值语句为B[j][i] A[i][j]。对应数据可以全部加载进缓存不冲突
这样虽然只同时利用了16个set但是只会在加载分块进缓存的时候产生冲突而如果使用更大的分块在加载分块的时候必然会加载两个正好相差8行的元素产生更多冲突。如果采用更小的分块虽然没有增加冲突但是缓存的利用率更低了。所以权衡一下8*8就是最优分块。
就用这种分块策略进行测试
for (int i 0; i N; i 8)for (int j 0; j M; j 8)for (int m i; m i 8; m)for (int n j; n j 8; n)B[n][m] A[m][n];结果如下
与300次的要求还有差距这就需要解决一下对角线上的元素冲突问题。以第一个白色块为例
A的第一行要赋值到B的第一列首先读A[0][0]第一次肯定不命中加载进来set[0]存A[0]然后读B[0][0]还是不在加载进来set[0]存B[0]然后读A[0][1]不命中加载进来set[0]又存A[0]直到A的第一行全部读完。再读下一行首先读A[1][0]不命中加载进来set[4]存A[1]再读B[0][1]不命中加载进来set[0]存B[0]再读A[1][1]不命中加载进来set[4]存A[1]再读B[1][1]不命中加载进来set[4]存B[1]再读A[1][2]不命中加载进来set[4]存A[1]直到A的第二行全部读完缓存都会命中。
以此类推后面每一行相比第一行都多了2次不命中一个对角块有8行一块就会多14次不命中一共有4块总共就会多56次不命中。如果把这些解决了理论上就能控制在300以内。
解决方法也很粗暴直接定义8个局部变量局部变量可以存放在寄存器中。依次把A的一行全部读出来依次给B对应的一列赋值这样可以避免中间多余的两次不命中
for (int i 0; i N; i 8)for (int j 0; j M; j 8)for (int k i; k i 8; k){int t0 A[k][j];int t1 A[k][j1];int t2 A[k][j2];int t3 A[k][j3];int t4 A[k][j4];int t5 A[k][j5];int t6 A[k][j6];int t7 A[k][j7];B[j][k] t0;B[j1][k] t1;B[j2][k] t2;B[j3][k] t3;B[j4][k] t4;B[j5][k] t5;B[j6][k] t6;B[j7][k] t7;}测试如下
结果正好比预想的少56次。也达到了题目要求。
再看一下优化对角线后的读取情况加深理解
64 * 64
做完动图突然发现不合适的地方右边为要转置到B中的某个分块分块初始应该是白色的没有数据的就当白色看吧。
此时数据一行有64个元素8个set才能存满一行cache存满最多能存4行。也就是两个元素中间差4行的整数倍就会发生冲突比如A[0][0]和A[4][0]都会映射到cache[0][0]位置。
如果仍使用8 * 8分块那么每个分块内部读取的时候都会发生冲突比如A[0][0]和A[4][0]都在一个分块内。如果使用4 * 4分块那cache利用率就减半结果肯定也不理想。
还是考虑8 * 8分块把每一个块分成4部分
本来是要把黄色部分转置到黄色部分灰色部分本应转置到绿色部分但是绿色部分和黄色部分映射到同一块缓存会发生冲突先把灰色部分转置到灰色部分。下图颜色加深代表要访问某个元素左边是A矩阵右边是B矩阵
为了避免对角线分块上会多miss的问题还是采用先把A的一行全部读出来的策略。这样就以较少的miss把B矩阵初步填满此时填满之后效果如下
再交换灰色块和绿色块就完成了整个分块的转置。可惜的是这样优化仍拿不到满分。
进一步优化在转换灰色块时逆序转换
过程如下
整个过程并没有因为逆序存放发生多余的miss。
然后读绿色块和蓝色块时按列来读从内到外
从下向上按行转换B中的灰色块到绿色块
此时可以发现正好可以把用临时变量存放的A中的绿色块和蓝色块赋到B中
并且这个过程不会发生miss复原灰色块的同时把绿色块和蓝色块也转置了。
继续后面的过程
此时转置情况如下
剩下的就不列举了都是一样的过程代码如下
for (int i 0; i N; i 8)
{for (int j 0; j M; j 8){for (int k i; k i 4; k){// 读取A中的黄色块和灰色块int t0 A[k][j];int t1 A[k][j1];int t2 A[k][j2];int t3 A[k][j3];int t4 A[k][j4];int t5 A[k][j5];int t6 A[k][j6];int t7 A[k][j7];// 黄色块在B中正常转置B[j][k] t0;B[j1][k] t1;B[j2][k] t2;B[j3][k] t3;// 灰色块在B中灰色块位置逆序放置B[j][k4] t7;B[j1][k4] t6;B[j2][k4] t5;B[j3][k4] t4;}for (int l 0; l 4; l){// 由内到外按列读取A中绿色块和蓝色块int t0 A[i4][j3-l];int t1 A[i5][j3-l];int t2 A[i6][j3-l];int t3 A[i7][j3-l];int t4 A[i4][j4l];int t5 A[i5][j4l];int t6 A[i6][j4l];int t7 A[i7][j4l];// 从下至上按行转换B中的灰色块到绿色块B[j4l][i] B[j3-l][i4];B[j4l][i1] B[j3-l][i5];B[j4l][i2] B[j3-l][i6];B[j4l][i3] B[j3-l][i7];// 将临时变量中存放的A中的绿色块和蓝色块B中的灰色块和蓝色块完成转置B[j3-l][i4] t0;B[j3-l][i5] t1;B[j3-l][i6] t2;B[j3-l][i7] t3;B[j4l][i4] t4;B[j4l][i5] t5;B[j4l][i6] t6;B[j4l][i7] t7;} }
}测试通过
61 * 67
此时矩阵不是32或64的方阵不会像之前一样隔4行或8行就映射到同一个缓存快所以可以尝试一下依次利用更大的缓存大胆一点全部用上进行16 * 16分块不过Aii和Bii还是会映射到同一个缓存快还需要单独处理用临时变量存放代码如下
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){int temp_position -1;int temp_value 0;int l;for (l j; l j 16 l M; l){// 横坐标等于纵坐标局部变量暂存整个block读完再处理if (l k){temp_position k;temp_value A[k][k];}elseB[l][k] A[k][l];}// 遇到了冲突元素if (temp_position ! -1)B[temp_position][temp_position] temp_value;}}
}测试通过正好卡在了2000线边缘
