前言
《深入理解计算机系统》实验五Cache Lab下载和官方文档机翻请看:
https://blog.csdn.net/weixin_43362650/article/details/121989400
我觉得这个文档对整个实验很有帮助。
对于我来说实验五Cache Lab中的B部分64*64是实验一~实验五中最难的,我还是打开了百度,害。这矩阵还是看的懵懵懂懂,所以个人认为该篇播客只有A部分有看头。B部分建议看这篇。
深入理解计算机系统-cachelab
A部分
题目请看文档。
基本架构-接收命令行参数
首先应该先实现基本的架构,即可以接收到在linux命令行中输入的-v、-h、-s等参数。
文档有提到建议使用getopt函数来解析命令行参数。需要三个头文件
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
详细可见(以下只提用上的)
linux> man 3 getopt
int getopt(int argc, char * const argv[], const char *optstring);
extern char *optarg;
extern int optind, opterr, optopt;
有个例子
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
int
main(int argc, char *argv[])
{
int flags, opt;
int nsecs, tfnd;
nsecs = 0;
tfnd = 0;
flags = 0;
while ((opt = getopt(argc, argv, "nt:")) != -1) {
switch (opt) {
case 'n':
flags = 1;
break;
case 't':
nsecs = atoi(optarg);
tfnd = 1;
break;
default: /* '?' */
fprintf(stderr, "Usage: %s [-t nsecs] [-n] name\n",
argv[0]);
exit(EXIT_FAILURE);
}
}
printf("flags=%d; tfnd=%d; nsecs=%d; optind=%d\n",
flags, tfnd, nsecs, optind);
if (optind >= argc) {
fprintf(stderr, "Expected argument after options\n");
exit(EXIT_FAILURE);
}
printf("name argument = %s\n", argv[optind]);
/* Other code omitted */
exit(EXIT_SUCCESS);
}
int getopt(int argc, char * const argv[], const char *optstring);
参数:
- argc和argv与main函数的两个参数一致
- optstring:表示我们短选项的字符串
如:“sEbt:hv”。表示程序支持的命令行参数有-s、-E、-b、-t、-h和-v。
冒号的含义表示:
- 只有一个字符,不带冒号:表示选项,如-h和-v。
- 一个字符,后面接一个冒号:表示选项后面带一个参数,如-s、-E、-b和-t
extern char *optarg;
extern int optind, opterr, optopt;
4个全局变量
- optarg:当前选项对应的参数值。
- optind:argv中要处理的下一个元素的索引。
- opterr:默认情况下,opterr有一个非零值,opterr设置为零,那么getopt()不会打印错误消息。
- optopt:表示错误选项字符。
据此编写出基本的框架
#include "cachelab.h"
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
extern char *optarg;
extern int optind, opterr, optopt;
int
main(int argc, char *argv[])
{
int hit_count=0,miss_count=0,eviction_count=0; //命中,未命中,驱逐
int opt;
int s=0; //高速缓存组S=2^s
int E=0; //高速缓存行
int b=0; //数据块B=2^b
int tag_v=0; //是否查看过程信息,tag_v==1查看 tag_v==0查看
char *file_name;
FILE *file;
//提示(帮助)的信息
char help[]="Usage: %s [-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> %s -s 4 -E 1 -b 4 -t traces/yi.trace\n"
"linux> %s -v -s 8 -E 2 -b 4 -t traces/yi.trace\n";
//"sEbt:hv":-s、-E、-b、-t 可接收字符,-h和-v不x接受
while ((opt = getopt(argc, argv, "sEbt:hv")) != -1) {
switch (opt) {
case 'h':
fprintf(stderr, help,argv[0],argv[0],argv[0]); //argv[0]是命令行参数的第一个值,即运行的可执行文件名
break;
case 'v':
tag_v = 1;
break;
case 's':
s=atoi(argv[optind]); //atoi字符转十进制
break;
case 'E':
E=atoi(argv[optind]);
break;
case 'b':
b=atoi(argv[optind]);
break;
case 't':
file_name=argv[optind-1]; //获取文件名
file = fopen(file_name,"r"); //打开文件
if(file == NULL){
perror(file_name);
exit(EXIT_FAILURE);
}
break;
default:
fprintf(stderr, help,argv[0],argv[0],argv[0]);
exit(EXIT_FAILURE);
}
}
/* Other code omitted */
printSummary(hit_count,miss_count,eviction_count);
return 0;
}
用-h命令运行如下(gcc编译要带上cachelab.c):
![在这里插入图片描述](https://img-blog.csdnimg.cn/4462d8c4dbd747f9afc42dc7c39ed4a2.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQWRkeXo=,size_20,color_FFFFFF,t_70,g_se,x_16)
(有一些细节没处理好,不过这部分不是主要的)
模拟高速缓存结构
我们要设计一个数据结构,使它能模仿高速缓存结构的行为
![在这里插入图片描述](https://img-blog.csdnimg.cn/aa65ec90ee964e8a8eebdae7f21c1327.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQWRkeXo=,size_20,color_FFFFFF,t_70,g_se,x_16)
《CS:APP3e》图6-25 高速缓存(S,E,B,m)的通用组织。a)高速缓存是一个高速缓存组。每个组包括一个行或多个行,每个行包含一个有效位,一些标记位,以及一个数据块
可以看出这是一个“组”里面有“行”,行里面有有效位,标记位,以及一个数据块。
可以把有效位,标记位,以及一个数据块定义成一个结构体,然后创建该结构体的二维数组就可以模拟高速缓存组。
如下所示:
struct ROW{
int validBit; //有效位
int tagBit; //标记位
char *block; //数据块
};
/**
* 设置模拟缓存。初始化
* S=2^s组,即1<<s。
* B=2^b字节,即1<<b。 //数据块的大小
**/
int S=1<<s;
int block_size=1<<b;
struct ROW cacheLine[S][E];
for(int i = 0;i < S;i++){
for(int j = 0;j < E;j++){
cacheLine[i][j].validBit=0;
cacheLine[i][j].tagBit=-1;
cacheLine[i][j].block = malloc(block_size);
}
}
解析地址
我们要用程序来解析地址。
![在这里插入图片描述](https://img-blog.csdnimg.cn/1725cdc897204654a796aa203e7dc571.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQWRkeXo=,size_20,color_FFFFFF,t_70,g_se,x_16)
《CS:APP3e》图6-25 b)高速缓存结构将m个地址位划分成了t个标记位、s个组索引位和b个块偏移位
要创建两个掩码来取到块偏移位和组索引位
- 创建一个b位全是1其他位全是0的掩码。
- 创建一个s位全是1其他为全是0的掩码。
这里
- 一个b位全是1其他位全是0的掩码:(2b)-1
- 一个s位全是1其他为全是0的掩码:((2s)-1)<<b
#include <math.h>
int mask_b = (int)pow(2,b)-1; //创建块偏移b位的掩码
int mask_s = ((int)pow(2,s)-1)<<b; //创建组索引s位的掩码
比如说有个地址addres,这样就可以计算组索引和标记位
int cacheLine_index = (addres & mask_s)>>b; //组索引
int tag = addres>>s>>b; //标记位
解析文件
实验给的.trace是这样子的
每行表示一个或两个内存访问。每一行的格式为
[space] operation address,size
operation字段表示内存访问的类型:“I” 表示指令加载,“L” 表示数据加载,“S” 表示数据存储,“M” 表示数据修改(即,数据加载后跟着一个数据存储)。在每个 “I” 之前从来没有空格。每个 “M”、“L” 和 “S” 前面总是有一个空格。address字段指定一个64位的十六进制内存地址。size字段指定操作访问的字节数。
L 0,1
L 1,1
L 2,1
L 3,1
S 4,1
L 5,1
S 6,1
L 7,1
S 8,1
L 9,1
S a,1
L b,1
S c,1
L d,1
S e,1
M f,1
有"I"就是这样子的
S 00600aa0,1
I 004005b6,5
I 004005bb,5
I 004005c0,5
用char *fgets(char *str, int n, FILE *stream);一行一行读取并进行处理。
用char *strtok(char *str, const char *delim);分割字符串。
要处理address,因为它是字符的表示形式要转成整数才可以对它的位进行处理。
写个htoi方法:十六进制字符转成十进制整数。
int mask_b = (int)pow(2,b)-1; //创建块偏移b位的掩码
int mask_s = ((int)pow(2,s)-1)<<b; //创建组索引s位的掩码
char ch[16]; //刚好可以容纳一行数据的大小
const char Separator[3]=" ,"; //分隔符
char *token; //子串
while(fgets(ch,16,file)!=NULL){
token = strtok(ch,Separator);
char *instruction = token; //内存访问的类型
if (*instruction == 'I') //I类型不用处理
{
continue;
}
token = strtok(NULL,Separator);
char *addres_char = token; //地址的字符表示
long addres = htoi(addres_char); //地址的十进制表示
token = strtok(NULL,Separator);
int size = atoi(token);
int cacheLine_index = (addres & mask_s)>>b; //组索引
int tag = addres>>s>>b; //标记位
if(tag_v) printf("%s %s,%d \n",instruction,addres_char,size);
}
/**
* 十六进制字符转成十进制整数
**/
long htoi(char *s){
long n = 0;
for(int i = 0;(s[i] >= '0' && s[i] <= '9') || (s[i]>= 'a' && s[i] <= 'f');i++)
{
if(s[i] > '9')
{
n = 16 * n +(10 + s[i] - 'a');
}
else
{
n = 16 * n + (s[i] - '0');
}
}
return n;
}
运行结果(用到了math.h中声明的库函数pow,gcc编译要加"-lm"):
![在这里插入图片描述](https://img-blog.csdnimg.cn/2f6531e281ba48bda807190eac2d7865.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQWRkeXo=,size_20,color_FFFFFF,t_70,g_se,x_16)
模拟缓存行为(当E=1时,没替换策略的简易版)
先解决当E=1时。
这个就简单了,只要获取地址中的组索引
按以下步骤,只要其中一个步骤完成即可
- 遍历行是否有效,在判断标记位是否相同,标记位相同就命中。
- 1没有命中。遍历行是否有无效(空)的缓存区,有就写入。
- 2也没有。驱逐一个缓存区,写入
- "I"表示指令加载:不用处理。
- "L"表示数据加载和"S"表示数据存储:一样处理
- "M"数据修改(即,数据加载后跟着一个数据存储):“L"然后"S”
int tag_M = *instruction == 'M' ? 2:1; //'M' 循环两遍,'S''I'一遍
do{
//1.遍历行是否有效,在判断标记位是否相同,标记位相同就命中。
for(int i = 0;i < E;i++){ //遍历一组中的所有行
struct ROW *one_row = &cacheLine[cacheLine_index][i]; //获取一行
if(one_row->validBit && one_row->tagBit == tag){ //有效且标记相同则命中
hit_count++; //命中
if(tag_v) printf("hit ");
goto end;
}
}
//2.遍历行是否有无效(空)的缓存区,有就写入。
for(int i =0;i < E;i++){ //无效:未命中,要写入无效的缓存区
struct ROW *one_row = &cacheLine[cacheLine_index][i];
if(!one_row->validBit){
miss_count++;
one_row->validBit = 1;
one_row->tagBit = tag;
if(tag_v)printf("miss ");
goto end;
}
}
//3.驱逐一个缓存区,写入
//驱逐使用LRU(最近使用最少的)替换策略,现在还没写,因为E=1的情况用不用都一样
for (int i = 0; i < E; i++){ //缓存区满了,要驱逐
struct ROW *one_row = &cacheLine[cacheLine_index][i];
miss_count++; //未命中
eviction_count++; //驱逐
one_row->validBit = 1;
one_row->tagBit = tag;
if(tag_v)printf("miss ");
goto end;
}
end:
if (tag_v && !(tag_M-1)){printf("\n");} //不是'M'就要换行
tag_M--;
}while(tag_M);
代码
截止目前为止的代码合起来为
#include "cachelab.h"
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
extern char *optarg;
extern int optind, opterr, optopt;
long htoi(char *s); //十六进制字符转成十进制整数
struct ROW{
int validBit; //有效位
int tagBit; //标记位
char *block; //数据块
};
int
main(int argc, char *argv[])
{
int hit_count=0,miss_count=0,eviction_count=0; //命中,未命中,驱逐
int opt;
int s=0; //高速缓存组S=2^s
int E=0; //高速缓存行
int b=0; //数据块B=2^b
int tag_v=0; //是否查看过程信息,tag_v==1查看 tag_v==0查看
char *file_name;
FILE *file;
//提示(帮助)的信息
char help[]="Usage: %s [-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> %s -s 4 -E 1 -b 4 -t traces/yi.trace\n"
"linux> %s -v -s 8 -E 2 -b 4 -t traces/yi.trace\n";
//"sEbt:hv":-s、-E、-b、-t 可接收字符,-h和-v不接收
while ((opt = getopt(argc, argv, "sEbt:hv")) != -1) {
switch (opt) {
case 'h':
fprintf(stderr, help,argv[0],argv[0],argv[0]); //argv[0]是命令行参数的第一个值,即运行的可执行文件名
break;
case 'v':
tag_v = 1;
break;
case 's':
s=atoi(argv[optind]); //atoi字符转十进制
break;
case 'E':
E=atoi(argv[optind]);
break;
case 'b':
b=atoi(argv[optind]);
break;
case 't':
file_name=argv[optind-1]; //获取文件名
file = fopen(file_name,"r"); //打开文件
if(file == NULL){
perror(file_name);
exit(EXIT_FAILURE);
}
break;
default:
fprintf(stderr, help,argv[0],argv[0],argv[0]);
exit(EXIT_FAILURE);
}
}
/**
* 设置模拟缓存。初始化
* S=2^s组,即1<<s。
* B=2^b字节,即1<<b。
**/
int S=1<<s;
int block_size=1<<b; //数据块的大小
struct ROW cacheLine[S][E];
for(int i = 0;i < S;i++){
for(int j = 0;j < E;j++){
cacheLine[i][j].validBit=0;
cacheLine[i][j].tagBit=-1;
cacheLine[i][j].block = malloc(block_size);
}
}
int mask_b = (int)pow(2,b)-1; //创建块偏移b位的掩码
int mask_s = ((int)pow(2,s)-1)<<b; //创建组索引s位的掩码
char ch[16]; //刚好可以容纳一行数据的大小
const char Separator[3]=" ,"; //分隔符
char *token; //子串
while(fgets(ch,16,file)!=NULL){
token = strtok(ch,Separator);
char *instruction = token; //内存访问的类型
if (*instruction == 'I') //I类型不用处理
{
continue;
}
token = strtok(NULL,Separator);
char *addres_char = token; //地址的字符表示
long addres = htoi(addres_char); //地址的十进制表示
token = strtok(NULL,Separator);
int size = atoi(token);
int cacheLine_index = (addres & mask_s)>>b; //组索引
int tag = addres>>s>>b; //标记位
if(tag_v) printf("%s %s,%d ",instruction,addres_char,size);
int tag_M = *instruction == 'M' ? 2:1; //'M' 循环两遍,'S''I'一遍
do{
//1.遍历行是否有效,在判断标记位是否相同,标记位相同就命中。
for(int i = 0;i < E;i++){ //遍历一组中的所有行
struct ROW *one_row = &cacheLine[cacheLine_index][i]; //获取一行
if(one_row->validBit && one_row->tagBit == tag){ //有效且标记相同则命中
hit_count++; //命中
if(tag_v) printf("hit ");
goto end;
}
}
//2.遍历行是否有无效(空)的缓存区,有就写入。
for(int i =0;i < E;i++){ //无效:未命中,要写入无效的缓存区
struct ROW *one_row = &cacheLine[cacheLine_index][i];
if(!one_row->validBit){
miss_count++;
one_row->validBit = 1;
one_row->tagBit = tag;
if(tag_v)printf("miss ");
goto end;
}
}
//3.驱逐一个缓存区,写入
//驱逐使用LRU(最近使用最少的)替换策略,现在还没写,因为E=1的情况用不用都一样
for (int i = 0; i < E; i++){ //缓存区满了,要驱逐
struct ROW *one_row = &cacheLine[cacheLine_index][i];
miss_count++; //未命中
eviction_count++; //驱逐
one_row->validBit = 1;
one_row->tagBit = tag;
if(tag_v)printf("miss ");
goto end;
}
end:
if (tag_v && !(tag_M-1)){printf("\n");} //不是'M'就要换行
tag_M--;
}while(tag_M);
}
//释放分配的空间
for(int i = 0;i < S;i++){
for(int j = 0;j < E;j++){
free(cacheLine[i][j].block);
}
}
printSummary(hit_count,miss_count,eviction_count);
return 0;
}
/**
* 十六进制字符转成十进制整数
**/
long htoi(char *s){
long n = 0;
for(int i = 0;(s[i] >= '0' && s[i] <= '9') || (s[i]>= 'a' && s[i] <= 'f');i++)
{
if(s[i] > '9')
{
n = 16 * n +(10 + s[i] - 'a');
}
else
{
n = 16 * n + (s[i] - '0');
}
}
return n;
}
这段代码只能解决E=1时。
根据文档用测试程序来打分。
linux> make
在目录下make会发现报错了,挺奇怪的,官方文档中建议用getopt,编译的环境又有问题。
![在这里插入图片描述](https://img-blog.csdnimg.cn/905b87f146094dd7a1b69ee8de969c68.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQWRkeXo=,size_20,color_FFFFFF,t_70,g_se,x_16)
找到目录下的Makefile文件打开注释掉这段话![在这里插入图片描述](https://img-blog.csdnimg.cn/09ba72a0333b4a87be29fac72db5ea6e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQWRkeXo=,size_20,color_FFFFFF,t_70,g_se,x_16)
重新make就可以了
![在这里插入图片描述](https://img-blog.csdnimg.cn/77d422a26f6d40288ce26de3c0fe171a.png)
运行评分系统,会发现所有E=1的都正确了(yi.trace的E=2也正确了,是碰巧)。
![在这里插入图片描述](https://img-blog.csdnimg.cn/63375ec278a049ddbf134e823e88200e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQWRkeXo=,size_20,color_FFFFFF,t_70,g_se,x_16)
现在已经21分了,还差6分。还剩下两个不正确,要实现LRU(最近使用最少的)替换策略。
设计模拟LRU高速缓存结构
可以用一个双链表来实现LRU替换策略。
链头是最近访问的Cache。
链尾是最后访问的缓存区。
当一个位置被命中之后,通过调整链表的指向,将该位置调整到链表头的位置,新加入的Cache直接加到链表头中。
这样,在多次进行Cache操作后,最近被命中的,就会被向链表头方向移动,而没有命中的,会向链表后面移动,链表尾则表示最近最少使用的Cache。
发现在上面的
struct ROW{
int validBit; //有效位
int tagBit; //标记位
char *block; //数据块
};
中的char *block是用不上的,只要标记位命中就可以了。
重新设计一个数据结构,每一组加多一个双链表。
![请添加图片描述](https://img-blog.csdnimg.cn/14fa8ee658434e058386b4e1afca8ff9.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQWRkeXo=,size_20,color_FFFFFF,t_70,g_se,x_16)
数据结构如下:
struct ROW{
int validBit; //有效位
int tagBit; //标记位
};
struct LRU_ROW{
struct line *head; //链表头
struct ROW *E_ROW; //组
};
struct line{
struct line *prior; //指向直接前趋
struct line *next; //指向直接后继
int tagBit; //标记
};
/**
* 设置模拟缓存。初始化
* S=2^s组,即1<<s。
* B=2^b字节,即1<<b。
**/
int S=1<<s;
int block_size=1<<b; //数据块的大小
struct LRU_ROW cacheLine[S];
for(int i = 0;i < S;i++){
cacheLine[i].head=(struct line*)malloc(sizeof(struct line));
cacheLine[i].head->tagBit=-1;
cacheLine[i].E_ROW=malloc(sizeof(struct ROW)*E);
for(int j = 0;j < E;j++){
cacheLine[i].E_ROW[j].validBit=0;
cacheLine[i].E_ROW[j].tagBit=-1;
}
}
剩下的模拟操作就是对链表进行操作,要注意一些特殊情况,如头和尾。
int tag_M = *instruction == 'M' ? 2:1; //'M' 循环两遍,'S''I'一遍
do{
struct LRU_ROW *cache_lru_row = &cacheLine[cacheLine_index]; //获取该组
struct line *body = cache_lru_row->head; //获取该组的双链表头
for(int i = 0;i < E;i++){ //遍历一组中的所有行
struct ROW *one_row = &cache_lru_row->E_ROW[i]; //获取一行
if(one_row->validBit && one_row->tagBit == tag){ //有效且标记相同则命中
//找到双链表中命中的缓存,准备放到链表头
while(body!=NULL){
if(body->tagBit == tag){
break;
}
body=body->next;
}
//放到链表头,要判断,是不是本身就是头,是头就跳过
if (body!=cache_lru_row->head)
{
body->prior->next = body->next;
//判断是不是链表尾,是尾就跳过
if(body->next != NULL){
body->next->prior = body->prior;
}
body->prior == NULL;
body->next = cache_lru_row->head;
cache_lru_row->head->prior=body;
cache_lru_row->head = body;
}
hit_count++; //命中
if(tag_v) printf("hit ");
goto end;
}
}
for(int i = 0;i < E;i++){ //无效:未命中,要写入无效的缓存区
struct ROW *one_row = &cache_lru_row->E_ROW[i]; //获取一行
if(!(one_row->validBit)){
//准备放入链表的新结点
struct line * temp=(struct line*)malloc(sizeof(struct line));
temp->prior=NULL;
temp->next=NULL;
temp->tagBit = tag;
//判断是不是链表中的第一个结点,是就跳过
if(body->tagBit!=-1){
temp->next = body;
body->prior = temp;
}
//设置尾头结点
cache_lru_row->head = temp;
miss_count++;
one_row->validBit = 1;
one_row->tagBit = tag;
if(tag_v)printf("miss ");
goto end;
}
}
/**
* 又没命中,又没有多余的缓存区,则驱逐
*
* 驱逐的是双链表的最后一个
* 驱逐就是把双链表最后一个移到开头并重新设置tag
**/
while(body->next!=NULL){
body = body->next;
}
//判断链表中是不是只有一个结点
if (body!=cache_lru_row->head)
{
body->prior->next=NULL;
body->next=cache_lru_row->head;
cache_lru_row->head->prior=body;
}
cache_lru_row->head=body;
//找到在缓存中对应与双链表最后一个的缓存,移除,写入新的缓存。
struct ROW *one_row;
for(int j = 0;j < E;j++){
one_row=&cacheLine[cacheLine_index].E_ROW[j];
if(body->tagBit == (one_row->tagBit)){
break;
}
}
body->tagBit=tag;
one_row->validBit=1;
one_row->tagBit=tag;
if(tag_v)printf("miss eviction");
miss_count++; //未命中
eviction_count++; //驱逐
end:
if (tag_v && !(tag_M-1)){printf("\n");} //不是'M'就要换行
tag_M--;
}while(tag_M);
代码(满分)
完整代码如下
#include "cachelab.h"
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
extern char *optarg;
extern int optind, opterr, optopt;
long htoi(char *s); //十六进制字符转成十进制整数
struct ROW{
int validBit; //有效位
int tagBit; //标记位
};
struct LRU_ROW{
struct line *head; //链表头
struct ROW *E_ROW; //组
};
struct line{
struct line *prior; //指向直接前趋
struct line *next; //指向直接后继
int tagBit; //标记
};
int
main(int argc, char *argv[])
{
int hit_count=0,miss_count=0,eviction_count=0; //命中,未命中,驱逐
int opt;
int s=0; //高速缓存组S=2^s
int E=0; //高速缓存行
int b=0; //数据块B=2^b
int tag_v=0; //是否查看过程信息
char *file_name;
FILE *file;
//提示(帮助)的信息
char help[]="Usage: %s [-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> %s -s 4 -E 1 -b 4 -t traces/yi.trace\n"
"linux> %s -v -s 8 -E 2 -b 4 -t traces/yi.trace\n";
//"sEbt:hv":-s、-E、-b、-t 可接收字符,-h和-v不接收
while ((opt = getopt(argc, argv, "sEbt:hv")) != -1) {
switch (opt) {
case 'h':
fprintf(stderr, help,argv[0],argv[0],argv[0]); //argv[0]是命令行参数的第一个值,即运行的可执行文件名
break;
case 'v':
tag_v = 1;
break;
case 's':
s=atoi(argv[optind]); //atoi字符转十进制
break;
case 'E':
E=atoi(argv[optind]);
break;
case 'b':
b=atoi(argv[optind]);
break;
case 't':
file_name=argv[optind-1]; //获取文件名
file = fopen(file_name,"r"); //打开文件
if(file == NULL){
perror(file_name);
exit(EXIT_FAILURE);
}
break;
default:
fprintf(stderr, help,argv[0],argv[0],argv[0]);
exit(EXIT_FAILURE);
}
}
/**
* 设置模拟缓存。初始化
* S=2^s组,即1<<s。
* B=2^b字节,即1<<b。
**/
int S=1<<s;
int block_size=1<<b; //数据块的大小
struct LRU_ROW cacheLine[S];
for(int i = 0;i < S;i++){
cacheLine[i].head=(struct line*)malloc(sizeof(struct line));
cacheLine[i].head->tagBit=-1;
cacheLine[i].E_ROW=malloc(sizeof(struct ROW)*E);
for(int j = 0;j < E;j++){
cacheLine[i].E_ROW[j].validBit=0;
cacheLine[i].E_ROW[j].tagBit=-1;
}
}
int mask_b = (int)pow(2,b)-1; //创建块偏移b位的掩码
int mask_s = ((int)pow(2,s)-1)<<b; //创建组索引s位的掩码
char ch[16]; //刚好可以容纳一行数据的大小
const char Separator[3]=" ,"; //分隔符
char *token; //子串
while(fgets(ch,16,file)!=NULL){
token = strtok(ch,Separator);
char *instruction = token; //内存访问的类型
if (*instruction == 'I') //I类型不用处理
{
continue;
}
token = strtok(NULL,Separator);
char *addres_char = token; //地址的字符表示
long addres = htoi(addres_char); //地址的十进制表示
token = strtok(NULL,Separator);
int size = atoi(token);
int cacheLine_index = (addres & mask_s)>>b; //组索引
int tag = addres>>s>>b; //标记位
if(tag_v) printf("%s %s,%d ",instruction,addres_char,size);
int tag_M = *instruction == 'M' ? 2:1; //'M' 循环两遍,'S''I'一遍
do{
struct LRU_ROW *cache_lru_row = &cacheLine[cacheLine_index]; //获取该组
struct line *body = cache_lru_row->head; //获取该组的双链表头
for(int i = 0;i < E;i++){ //遍历一组中的所有行
struct ROW *one_row = &cache_lru_row->E_ROW[i]; //获取一行
if(one_row->validBit && one_row->tagBit == tag){ //有效且标记相同则命中
//找到双链表中命中的缓存,准备放到链表头
while(body!=NULL){
if(body->tagBit == tag){
break;
}
body=body->next;
}
//放到链表头,要判断,是不是本身就是头,是头就跳过
if (body!=cache_lru_row->head)
{
body->prior->next = body->next;
//判断是不是链表尾,是尾就跳过
if(body->next != NULL){
body->next->prior = body->prior;
}
body->prior == NULL;
body->next = cache_lru_row->head;
cache_lru_row->head->prior=body;
cache_lru_row->head = body;
}
hit_count++; //命中
if(tag_v) printf("hit ");
goto end;
}
}
for(int i = 0;i < E;i++){ //无效:未命中,要写入无效的缓存区
struct ROW *one_row = &cache_lru_row->E_ROW[i]; //获取一行
if(!(one_row->validBit)){
//准备放入链表的新结点
struct line * temp=(struct line*)malloc(sizeof(struct line));
temp->prior=NULL;
temp->next=NULL;
temp->tagBit = tag;
//判断是不是链表中的第一个结点,是就跳过
if(body->tagBit!=-1){
temp->next = body;
body->prior = temp;
}
//设置尾头结点
cache_lru_row->head = temp;
miss_count++;
one_row->validBit = 1;
one_row->tagBit = tag;
if(tag_v)printf("miss ");
goto end;
}
}
/**
* 又没命中,又没有多余的缓存区,则驱逐
*
* 驱逐的是双链表的最后一个
* 驱逐就是把双链表最后一个移到开头并重新设置tag
**/
while(body->next!=NULL){
body = body->next;
}
//判断链表中是不是只有一个结点,是就跳过
if (body!=cache_lru_row->head)
{
body->prior->next=NULL;
body->next=cache_lru_row->head;
cache_lru_row->head->prior=body;
}
cache_lru_row->head=body;
//找到在缓存中对应与双链表最后一个的缓存,移除,写入新的缓存。
struct ROW *one_row;
for(int j = 0;j < E;j++){
one_row=&cacheLine[cacheLine_index].E_ROW[j];
if(body->tagBit == (one_row->tagBit)){
break;
}
}
body->tagBit=tag;
one_row->validBit=1;
one_row->tagBit=tag;
if(tag_v)printf("miss eviction");
miss_count++; //未命中
eviction_count++; //驱逐
end:
if (tag_v && !(tag_M-1)){printf("\n");} //不是'M'就要换行
tag_M--;
}while(tag_M);
}
//释放分配的空间
for (int i = 0; i < S; i++)
{
free(cacheLine[i].head);
free(cacheLine[i].E_ROW);
}
printSummary(hit_count,miss_count,eviction_count);
return 0;
}
/**
* 十六进制字符转成十进制整数
**/
long htoi(char *s){
long n = 0;
for(int i = 0;(s[i] >= '0' && s[i] <= '9') || (s[i]>= 'a' && s[i] <= 'f');i++)
{
if(s[i] > '9')
{
n = 16 * n +(10 + s[i] - 'a');
}
else
{
n = 16 * n + (s[i] - '0');
}
}
return n;
}
测试一下
可以看到拿到了27分满分。
![在这里插入图片描述](https://img-blog.csdnimg.cn/6d3c7fc3dd6b47c5be6a1f2f46f395c3.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQWRkeXo=,size_20,color_FFFFFF,t_70,g_se,x_16)
B部分
运行一下熟悉环境
![在这里插入图片描述](https://img-blog.csdnimg.cn/c210f6e3b3fb49c4acd779cdb5abc9b7.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQWRkeXo=,size_20,color_FFFFFF,t_70,g_se,x_16)
结果运行异常,说是找不到valgrind
需要安装valgrind
linux> sudo apt-get install valgrind
然后在运行就可以了(把trans中的代码复制了一份到transpose_submit)
![在这里插入图片描述](https://img-blog.csdnimg.cn/fa48e4e8a23d448f92ca128302fd940b.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQWRkeXo=,size_20,color_FFFFFF,t_70,g_se,x_16)
32*32
给了一个最简单的版本
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;
}
}
}
这很明显,啥都没用上。
s=5,E=1,b=5。S=25=32,每组一行,B=25=32。
cache有32组,每组一行,每行可以储存32字节的数据,int类型为4字节,所以每个缓存中的每个数据块可以保存8个int元素。
可以用循环展开,一次循环复制8个。
A矩阵中,这8个,第1个未命中,然后放8个进缓存区,剩下7个都能命中。
而B矩阵呢?它的步长为N,所以在第一次把A矩阵复制到B矩阵时,B是全部未命中,然后缓存中就多了
B[0][0]~B[0][7]
B[1][0]~B[1][7]
B[2][0]~B[2][7]
B[3][0]~B[3][7]
B[4][0]~B[4][7]
…
这样下8次都可以命中(外循环间隔是8),而每一次都只有因为A数组而被逐出造成的一个未命中。
所以把它分为8*8的块。
代码如下
char transpose_submit_desc[] = "Transpose submission";
void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
int i, j, temp0,temp1,temp2,temp3,temp4,temp5,temp6,temp7;
if(M==32){
for (j = 0; j < 32; j=j+8) {
for (i = 0; i < 32;i++) {
temp0 = A[i][j];
temp1 = A[i][j+1];
temp2 = A[i][j+2];
temp3 = A[i][j+3];
temp4 = A[i][j+4];
temp5 = A[i][j+5];
temp6 = A[i][j+6];
temp7 = A[i][j+7];
B[j][i] = temp0;
B[j+1][i]=temp1;
B[j+2][i]=temp2;
B[j+3][i]=temp3;
B[j+4][i]=temp4;
B[j+5][i]=temp5;
B[j+6][i]=temp6;
B[j+7][i]=temp7;
}
}
}
}
make然后运行
![在这里插入图片描述](https://img-blog.csdnimg.cn/93d63e22ce9a4ad4b532f7d16cf701c6.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQWRkeXo=,size_20,color_FFFFFF,t_70,g_se,x_16)
<300。8分。
![在这里插入图片描述](https://img-blog.csdnimg.cn/668c389645b84ddbadcb10d6e78f1f4e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQWRkeXo=,size_20,color_FFFFFF,t_70,g_se,x_16)
根据trace.f0给的起始地址,
A是30b080
B是34b080
![在这里插入图片描述](https://img-blog.csdnimg.cn/e5b16d24edcb4afc9513309ac7f26617.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQWRkeXo=,size_20,color_FFFFFF,t_70,g_se,x_16)
写了个程序看了一下A和B的组数
![在这里插入图片描述](https://img-blog.csdnimg.cn/0ed50b811b394dd2acee217fb74145d7.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQWRkeXo=,size_20,color_FFFFFF,t_70,g_se,x_16)
如下所示
A/B[][0]~A/B[][7] |
A/B[0][8]~A/B[][15] |
A/B[][16]~A/B[][23] |
A/B[][24]~A/B[31] |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
0 |
1 |
2 |
3 |
A数组中的元素命中情况
"M"未命中,"H"命中。
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
B数组中的元素命中情况
"M"未命中,"H"命中。
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
M |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
M |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
M |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
M |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
M |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
M |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
M |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
M |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
M |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
M |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
M |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
M |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
M |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
M |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
M |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
M |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
M |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
M |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
M |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
M |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
M |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
M |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
M |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
M |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
M |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
M |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
M |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
M |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
H |
M |
H |
H |
H |
H |
H |
H |
M |
64*64
if(M==64 && N==64){
for (j = 0; j < 64; j=j+8) {
for (i = 0; i < 64;i=i+8) {
for(x = j;x < j + 4;x++){
temp0 = A[x][i];temp1 = A[x][i+1];temp2 = A[x][i+2];temp3 = A[x][i+3];
temp4 = A[x][i+4];temp5 = A[x][i+5];temp6 = A[x][i+6];temp7 = A[x][i+7];
B[i][x] = temp0;B[i+1][x] = temp1;B[i+2][x] = temp2;B[i+3][x] = temp3;
B[i][x+4] = temp4;B[i+1][x+4] = temp5;B[i+2][x+4] = temp6;B[i+3][x+4] = temp7;
}
for(y = i;y < i + 4;y++){
temp0 = A[j+4][y];temp1 = A[j+5][y];temp2 = A[j+6][y];temp3 = A[j+7][y];
temp4 = B[y][j+4];temp5 = B[y][j+5];temp6 = B[y][j+6];temp7 = B[y][j+7];
B[y][j+4] = temp0;B[y][j+5] = temp1;B[y][j+6] = temp2;B[y][j+7]=temp3;
B[y+4][j] = temp4;B[y+4][j+1] = temp5;B[y+4][j+2] = temp6;B[y+4][j+3]=temp7;
}
for(x = j + 4;x < j + 8;x++){
temp0 = A[x][i+4];temp1 = A[x][i+5];temp2 = A[x][i+6];temp3 = A[x][i+7];
B[i+4][x] = temp0;B[i+5][x] = temp1;B[i+6][x] = temp2;B[i+7][x] = temp3;
}
}
}
}
结果
![在这里插入图片描述](https://img-blog.csdnimg.cn/95886978dc394073811e85044e2323d1.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQWRkeXo=,size_20,color_FFFFFF,t_70,g_se,x_16)
61*67
用16*16分块
if(M==61 && N==67){
for(i = 0;i < N;i+=16){
for(j = 0;j < M;j+=16){
for(x = i;x < N && x < i+16;x++){
for(y=j;y < M && y < j+16;y++){
B[y][x]=A[x][y];
}
}
}
}
}
结果
![在这里插入图片描述](https://img-blog.csdnimg.cn/6860c7e1646a422aa23efd46c1584a48.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQWRkeXo=,size_20,color_FFFFFF,t_70,g_se,x_16)
总测
![在这里插入图片描述](https://img-blog.csdnimg.cn/814608520d4e4fdea147fa83a396aa24.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAQWRkeXo=,size_20,color_FFFFFF,t_70,g_se,x_16)