如何编程模拟计算机中的高速缓存
如何编程模拟计算机中的高速缓存
- 1. 实验要求
- 2. 编程
- 2.1 读取文件
- 2.2 高速缓存定义结构体
- 2.3 初始化Cache
- 2.4 解析输入的指令
- 2.5 LRU策略
- 2.6 更新高速缓存Cache
- 2.7 完整代码
- 3. 测试结果
1. 实验要求
1.编程模拟Cahce的命中，不命中，替换等行为。
2.编写的程序必须对任意s，E和b正确工作。
3.本实验不涉及真实的数据读写，不需要考虑block的细节，每行只有一个block。
4.编写的程序要能读取指定文件内的指令，根据不同的指令完成不同的动作，下面为指令内容示例。
I 0400d7d4,8 #
M 0421c7f0,4 # 修改access cache， 即读写access cache两次，0421c7f0：修改的地址，8：修改的长度
L 04f6b868,8 # 读access cache，04f6b868：读取的地址，8：读取长度
S 7ff0005c8,8 # 写access cache，0421c7f0：写的地址，8：写的长度
2. 编程
考虑模拟一个Cache的行为需要用到哪些变量？
计算机中的高速缓存模型
Cache有组数S、一组包含的行数E，存储块的字节大小B，Cache的容量C=S×E×B。
地址的构成：标识位t、组索引s、块偏移b（前面说了，不需要管块偏移）。
关于缓存和内存数据交换的详细介绍可以看下这个24张图7000字详解计算机中的高速缓存。
下面我们开始编写代码。
2.1 读取文件
getopt()该函数能够帮助程序分析C语言命令行程序输入的参数。
int getopt(int argc,char * const argv[ ],const char * optstring);
重点说下getopt()函数。前两个形参是main函数传入的参数，即我们输入的命令行，第三个形参是 optstring“选项字符串”，即标识哪些字母表示了操作。
如"a:b:cd::e"，字母后带一个冒号（例中的a、b）表明这个操作带参数，字母后的内容需要读取，存放到它内部变量 extern char * optarg中。
字母不带冒号（例中的c、e）表明该操作不带参数，后面输入的内容仍看作操作符处理。字母后带两个冒号（例中的d）表明该操作后参数是可选的，但是要求如果带参数时参数与操作符不能有空格，如-d123是对的，而-d 123会报错。当读取了全部的输入的命令后 getopt（）返回-1。
while((opt = getopt(argc,argv,"s:E:b:t:")) !=-1){ //解析命令行参数
switch(opt){
case 's':
s=atoi(optarg);
break;
case 'E':
E=atoi(optarg);
break;
case 'b':
b=atoi(optarg);
break;
case 't':
filepath = optarg;
break;
}
}
fscanf函数，该函数能够帮助用户处理文本文件中输入的格式化数据。
int fscanf(FILE *stream, char *format[,argument...]);
stream-这是指向 FILE 对象的指针，该 FILE 对象标识了流。
format-这是 C 字符串，包含了以下各项中的一个或多个：空格字符、非空格字符和format 说明符。
2.2 高速缓存定义结构体
实验要求中说明了，不需要处理b，只需认为每行中有一个block。因此cache_line结构体中包括有效位，标记位，时间戳三个变量就够了。stamp记录的是block 的使用时间，每被使用一次，block++。因此，stamp越大表明该block越是最近被使用。具体代码如下。
typedef struct{
int valid_bits;
unsigned tag;
int stamp;
}cache_line;
2.3 初始化Cache
定义一个Cache[S] [E]大小的二维数组。这样Cache就模拟好了。
void init(){
cache = (cache_line**)malloc(sizeof(cache_line*)*S); //malloc开辟空间
for(int i=0;i<S;i++)
*(cache+i) = (cache_line*)malloc(sizeof(cache_line)*E);
for(int i=0;i<S;i++){
for(int j=0;j<E;j++){
cache[i][j].valid_bits = 0; // 初始化有效位为0
cache[i][j].tag = 0xffffffff; //初始化标记位
cache[i][j].stamp = 0; //这个时间戳模拟LRU的时候会用到
}
}
}
2.4 解析输入的指令
先分析每个输入的指令应该被如何操作。如果是I，则不是数据操作，直接忽略。如果是L或者S，则需要进行一次hit-miss-eviction检测，如果是M，则相当于先L再S，需要进行两次hit-miss-eviction检测。然后考虑hit-miss- eviction检测细节。
while(fscanf(file," %c %x,%d",&operation,&address,&size)>0){
switch(operation){
case 'L':
update(address);
break;
case 'M':
update(address);
case 'S':
update(address);
break;
}
time();
}
首先需要对读取的地进有分析，低b位表示 block偏移，本实验中不需要计算block偏移。中间s位是 set index位，表示对那个行操作。其余t位是tag位。用于标明对应的line是否有效。我们需要对得到的地址进行如下操作，解析出t和s。
unsigned s_address =(address>>b) & ((0xffffffff)>>(32-s)); //索引位
unsigned t_address = address>>(s+b); //标记位
2.5 LRU策略
替换策略使用的是LRU的缓存替换策略。如果该set存满了，我每次要找到stamp最小的替换。为了方便，我把stamp初始化为0，之后每个操作+1. 当stamp= 0的时候就代表不valid。
void time(){
for(int i=0;i<S;i++){
for(int j=0;j<E;j++){
if(cache[i][j].valid_bits == 1)
cache[i][j].stamp++;
}
}
}
for(int i=0;i<E;i++){
if(cache[s_address][i].stamp > max_stamp){
max_stamp = cache[s_address][i].stamp;
max_i = i;
}
}
2.6 更新高速缓存Cache
Cache的容量有限，当满的时候需要替换行，先遍历当前组，判断它满了没有，如何判断是否满，可以遍历所有的行，只要有一个有效位为0，（有效位的作用是说明该行是否存储了数据，通俗的理解就是是否为空）则该组未满。
for(int i=0;i<E;i++){
if(cache[s_address][i].valid_bits == 0){
cache[s_address][i].tag = t_address;
cache[s_address][i].valid_bits = 1;
cache[s_address][i].stamp = 0;
miss++;
return;
}
}
2.7 完整代码
/*
* @Description: 编程模拟Cache
* @Version: V1.0
* @Autor: 嵌入式与Linux那些事
* @Date: 2021-1-1 20:40:12
* @LastEditors: 嵌入式与Linux那些事
* @LastEditTime: 2021-1-1 22:11:58
*/
#include "cachelab.h"
#include <getopt.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include <stddef.h>
typedef struct{
int valid_bits;
unsigned tag;
int stamp;
}cache_line;
char* filepath = NULL;
int s,E,b,S; // s 表示组 ,E表示行,每一行有 2^b位 ,S = 2^s 组
int hit=0,miss=0,eviction=0;
cache_line** cache = NULL;
void init(){
cache = (cache_line**)malloc(sizeof(cache_line*)*S); //malloc开辟空间
for(int i=0;i<S;i++)
*(cache+i) = (cache_line*)malloc(sizeof(cache_line)*E);
for(int i=0;i<S;i++){
for(int j=0;j<E;j++){
cache[i][j].valid_bits = 0; // 初始化有效位为0
cache[i][j].tag = 0xffffffff; //初始化标记位
cache[i][j].stamp = 0; //这个时间戳模拟LRU的时候会用到
}
}
}
void update(unsigned address){
unsigned s_address =(address>>b) & ((0xffffffff)>>(32-s)); //从地址分解出索引位
unsigned t_address = address>>(s+b); //从地址分解出标记位
//判断tag为是否相等，是否命中
for(int i=0;i<E;i++){
if((*(cache+s_address)+i)->tag ==t_address){
cache[s_address][i].stamp = 0; //被使用了
hit++;
return;
}
}
//更新高速缓存cache
for(int i=0;i<E;i++){
if(cache[s_address][i].valid_bits == 0){
cache[s_address][i].tag = t_address;
cache[s_address][i].valid_bits = 1;
cache[s_address][i].stamp = 0; //now ,this is load
miss++;
return;
}
}
//暴力实现LRU
int max_stamp=0;
int max_i;
for(int i=0;i<E;i++){
if(cache[s_address][i].stamp > max_stamp){
max_stamp = cache[s_address][i].stamp;
max_i = i;
}
}
eviction++;
miss++;
cache[s_address][max_i].tag = t_address;
cache[s_address][max_i].stamp = 0;
}
//更新stamp
void time(){
for(int i=0;i<S;i++){
for(int j=0;j<E;j++){
if(cache[i][j].valid_bits == 1)
cache[i][j].stamp++;
}
}
}
int main(int argc,char *argv[])
{
int opt;
while((opt = getopt(argc,argv,"s:E:b:t:")) !=-1){ //解析命令行参数
switch(opt){
case 's':
s=atoi(optarg);
break;
case 'E':
E=atoi(optarg);
break;
case 'b':
b=atoi(optarg);
break;
case 't':
filepath = optarg;
break;
}
}
S = 1<<s;
init();
FILE* file=fopen(filepath,"r");
if(file == NULL){ // 读取文件错误
printf("Open file wrong");
exit(-1);
}
char operation;
unsigned address;
int size;
while(fscanf(file," %c %x,%d",&operation,&address,&size)>0){
switch(operation){
case 'L':
update(address);
break;
case 'M':
update(address);
case 'S':
update(address);
break;
}
time();
}
for(int i=0;i<S;i++) //释放 cache[S][E]
free(*(cache+i));
free(cache);
fclose(file); //关闭文件
printSummary(hit,miss,eviction); //本次实验使用的是HNU的自动评分系统，它会读取这条语句进行评分。
return 0;
}
3. 测试结果
HNU的自动评分系统会测试我们编写的代码是否可以通过所有的测试用例，和Reference simulator的对比表明，结果完全相同。测试通过！
本文分享自 嵌入式与Linux那些事 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
腾讯云开发者
