该文章只讲述了cache lab的第一部分,第二部分由于技巧性过于强,所以没做..
基础知识
由于cpu寄存器与内存的速度差异越来越大,产生了在寄存器与内存之间的l1/l2/..等缓存,在执行命令时,涉及内存操作的首先会去缓存中查找相应的数据是否存在,如果存在,则直接从缓存中读写数据,否则,才会去内存进行读写操作。
缓存需要解决的一个问题是,对于任意一个内存地址,要如何判断其是否在缓存中,如果在,如何获取对应地址的数据。
缓存的结构如下图所示,cache包含S个set,每个set中,包含E个lines,而每个lines中,包含一位的valid bit、t位的tag bits和 B = 2^b bytes的数据块。刨除valid bit和tag bits,该cache中可以存储 S * E * B bytes的数据。
在缓存的设计中,由b图可以看到,m位的地址被分为t bits的tag、s bits的set index以及b bits的block内偏移。具体来说,就是对于任意一个m位的地址,首先先取中间的s位,计算出set的index S=2^s,来确认该地址的数据会被存储在哪一个set中,再去查找该set中有哪个line的tag是和该地址的tag一致,如果找到了某个line,其tag与地址的tag一致,且该line的valid bit为true,则该地址所存储的数据在该line中,找到该line后,通过地址的最低b位的数据,找到所要获取数据在该line的offset,之后读取该数据即可。
当s=0时,可以看到该m位的地址被分为t位的tag段和b位的block offset段,并且缓存中仅有一个set,这种情况被称为Fully Associative Caches。该方式也更为直观:以m=8,t=4举例,对于地址0xa1来说,tag=0xa,存储了2^4 = 16 bytes的数据,也就是说,地址0xa0-0xaf的数据都被存储在tag=0xa的line中,如果下次需要从0xa4地址中,取4个bytes的数据,则直接可以在tag=0xa的line中,从offset=4往后取4个bytes即可。
当s不为0时,区别仅仅在于在查询tag之前,先用中间的s位去确认数据应该在第几个set,然后再通过tag来进行查询。
这里有个问题是,为什么最高几位表征tag,而中间几位是表征set index呢?如果反过来,高几位为set index,中间位是tag会有什么结果?考虑连续访问数组的情况,如果用最高位作为set index,在顺序遍历数组时,最高位往往保持不变,也就意味着数组中的元素都会被缓存到同一个set的不同line中,这也就造成了当set中的line的数量较小(也就是E比较小时),会造成频繁的cache逐出的情况,使得cache miss的情况增多;而如果使用中间几位作为set index,顺序遍历数组时,不同的数组块就会被映射到不同的set中,也就意味着能缓存的数组数据量变大了。
cache lab
cache lab的地址:http://csapp.cs.cmu.edu/2e/cachelab.pdf
第一部分就是实现一个脚本,输入是s/E/b的大小以及一个内存操作文件,输出为在给定的cache规格的条件下,该内存操作命中/miss/逐出了多少次缓存操作。内存操作文件每行的格式为operation address,size
,operation指代操作类型,有M(modify)、L(load)、S(save)三种,address为内存的地址,size为需要操作的操作数长度。
整体的实现较为简单,首先对于输入的s和t创建相应大小的数据结构,数据结构如下图所示,整体的cache由sets[]
组成,每个元素包含set的序号和对应的line的数组,每个line用setvalue
来表示,其中,validbits代表是否有效,ts类似时间戳,用来做逐出用。
struct setvalue {
int validbits;
int tag;
int ts;
};
struct sets {
int setno;
struct setvalue *values;
};
在读取内存操作文件中的数据时,对于每个地址,先计算出来该地址对应的缓存的set序号以及tag,计算逻辑如下:通过位运算计算出对应的smask和tmask,与地址做&
操作后进行移位,即可获得set的序号和tag的大小。
const int bmask = (1<<b) - 1;
const int smask = (1<<(s+b)) - bmask - 1;
const unsigned long tmask = ~0 - smask - bmask;
soffset = (address & smask) >> b;
tnum = (address & tmask) >> (b+s);
计算出后,去sets数组中找到对应的set,再遍历line中是否有tag与计算出来的tag相等,如果相等且validbits为1,则证明cache中包含该地址存储的值,否则,进行load的操作。
整体代码如下:
#include "cachelab.h"
#include <getopt.h>
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <string.h>
const int hitResultMask1 = 0x1;
const int hitResultMask2 = 0x10;
const int missResultMask = 0x100;
const int evictResultMask = 0x1000;
struct setvalue {
int validbits;
int tag;
int ts;
};
struct sets {
int setno;
struct setvalue *values;
};
int getaddr(char *);
int process(char itype, struct sets *ss, int e, int soffset, int tnum, int* tscounter) {
struct sets theset = ss[soffset];
int i;
int cacheresult = 0;
for (i = 0; i < e; i++) {
if (theset.values[i].validbits == 1 && theset.values[i].tag == tnum) {
theset.values[i].ts = *tscounter;
*tscounter += 1;
cacheresult |= hitResultMask1;
if (itype == 'M') {
cacheresult |= hitResultMask2;
}
return cacheresult;
}
}
int evictIndex = 0;
for (i = 0; i < e; i++) {
if (theset.values[i].validbits != 1) {
evictIndex = i;
break;
} else if (theset.values[i].ts < theset.values[evictIndex].ts) {
evictIndex = i;
}
}
cacheresult |= missResultMask;
if (theset.values[evictIndex].validbits == 1) {
cacheresult |= evictResultMask;
}
theset.values[evictIndex].validbits = 1;
theset.values[evictIndex].tag = tnum;
theset.values[evictIndex].ts = *tscounter;
*tscounter += 1;
if (itype == 'M') {
cacheresult |= hitResultMask2;
}
return cacheresult;
}
int main(int argc, char *argv[])
{
int isverbose = 0;
int opt = 0;
int s = 0, e = 0, b = 0;
int tscounter= 0;
char *tpath;
// parse arguments
while ((opt = getopt(argc, argv, "hvs:E:b:t:")) != -1) {
switch (opt) {
case 'h':
break;
case 'v':
isverbose = 1;
break;
case 's':
s = atoi(optarg);
break;
case 'E':
e = atoi(optarg);
break;
case 'b':
b = atoi(optarg);
break;
case 't':
tpath = optarg;
break;
}
}
printf("%d %d %d %d %s\n", isverbose, s, e, b, tpath);
// init sets
int setsize = 1 << s;
struct sets *ss = malloc(setsize * sizeof(struct sets));
int i, j;
for (i = 0; i < setsize; i++) {
ss[i].setno = i;
ss[i].values = malloc(e * sizeof(struct setvalue));
for (j = 0; j < e; j++) {
ss[i].values[j].validbits = 0;
ss[i].values[j].tag = 0;
ss[i].values[j].ts = 0;
}
}
FILE *fp;
fp = fopen(tpath, "r");
if (fp == NULL) {
exit(EXIT_FAILURE);
}
int hitsresult = 0, missresult = 0, evictresult = 0;
const size_t line_size = 300;
char* line = malloc(line_size);
// int boffset = 0;
int soffset = 0, tnum = 0;
const int bmask = (1<<b) - 1;
const int smask = (1<<(s+b)) - bmask - 1;
const unsigned long tmask = ~0 - smask - bmask;
while (fgets(line, line_size, fp) != NULL) {
int size = strlen(line);
if (size > 1 && line[0] == ' ') {
char itype = line[1];
int address = getaddr(line);
soffset = (address & smask) >> b;
tnum = (address & tmask) >> (b+s);
int result = process(itype, ss, e, soffset, tnum, &tscounter);
// parse result
if (isverbose == 1) {
line[size-1] = '\0';
char* lr = line + 1;
printf(lr);
}
if ((result & missResultMask) != 0) {
missresult += 1;
if (isverbose == 1) {
printf(" miss");
}
}
if ((result & evictResultMask) != 0) {
evictresult += 1;
if (isverbose == 1) {
printf(" eviction");
}
}
if ((result & hitResultMask1) != 0) {
hitsresult += 1;
if (isverbose == 1) {
printf(" hit");
}
}
if ((result & hitResultMask2) != 0) {
hitsresult += 1;
if (isverbose == 1) {
printf(" hit");
}
}
if (isverbose == 1) {
printf("\n");
}
}
}
fclose(fp);
if (line) {
free(line);
}
for (i = 0; i < setsize; i++) {
free(ss[i].values);
}
free(ss);
printSummary(hitsresult, missresult, evictresult);
return 0;
}
int getaddr(char *line) {
int i;
char *r = malloc(strlen(line) + 1);
char *tmp = r;
for (i = 3; i < strlen(line); i++) {
if (line[i] == ',') {
break;
}
*tmp = line[i];
tmp++;
}
*tmp = '\0';
return (int)strtol(r, NULL, 16);
}
Comments | NOTHING