本文主要是介绍CSAPP Cache 知识总结; Cache Lab Part A,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
CSAPP 高速缓存部分总结
1、程序的局部性
时间局部性:多次引用相同的内存位置
空间局部性:引用之前临近的内存位置
为什么cache能加速访问?——程序的局部性特征
3、缓存不命中种类:
(1)冷不命中:缓存为空时
(2)冲突不命中:访问的数据映射到同一个缓存块所导致
(3)容量不命中:缓存过小
Cache映射方式:
1、直接映射:
每个主存块映射到cache的固定行,优点是电路简单、缺点是可能冲突不命中,且cache空间没有充分利用。
(1)Cache结构:
n行,每行一个标记位,一个有效位(0 or 1)
标记位的作用是标记取自哪个块群(假设拿直接映射方式距离,0,4,8,12…会放到同一个cache行中,那么怎么区分?答案就是使用标记位)
(2)主存地址划分:
标记(和Cache对应行的标记做对比) + Cache行索引(Cache的哪一行) + 块内地址
(3)主存地址到cache的映射:
1、先根据行号找到对应的行
2、比较标记位,不符合的话从内存调
3、如果有效位为1,则命中
2、全相联映射:
有空就放
缺点:比较时间长,但空间利用率高
(1)Cache结构:
标记位 + 主存块
标记位的作用是标记主存块,因此位数多
3、组相联映射:
把Cache所有行分成几组(直接映射是整个Cache为一组),是直接映射和组相联的结合
(1)主存地址划分:
还是 标记 + Cache组索引 + 块内地址
但Cache行索引位数少了,标记位数多了,判断是否命中方式和直接映射一样。
几个概念:
(1)命中率/缺失率:
(2)关联度:主存块映射到cache时,可能存放的位置个数
几种映射方式的关联度:
直接映射:1
全相联:Cache行数
N路组相联:N
关联度越高,标记位数越多
Cache替换算法:
情景:组相联映射,第0组目前装入第0块和第8块,现在主存第16块需要装入Cache,是驱逐第0块还是第8块?
1、LRU最近最少用 : 特点是命中率随组的增大而提高
2、FIFO先进先出
3、LFU最不经常用
4、随机替换
LRU实现策略:
在cache的每行记录一个LRU位,如果命中,LRU位+1;
如果需要驱逐,则驱逐每组中LRU位最小的行
Cache一致性问题:
如果要写的单元在cache中存在,则有两种处理方法
(1)同时往cache和主存中写,需要加write buffer避免cpu等待内存
(2)write block,锁定内存,一次回写
Lab
lab分为两部分
(1)编写cache模拟程序
(2)优化矩阵转置
实验注意事项(来自实验指导书):
(1)对cache的操作有三种 L:加载数据 S:
1、编写cache模拟程序
(1)getopt函数解析命令行
因为要在命令行输入cache的组索引位数(s)、关联度(E)、块索引(b)、轨迹文件,格式为:
./csim -s 1 -E 1 -b 1 -t traces/yi2.trace
因此需要对命令行进行解析,使用getopt函数。
按照说明,因为 s,E等后面都有参数,因此需要加冒号,解析代码为:
while((c = getopt(argc,argv,"s:E:b:t:"))!= -1 ){switch(c){case 's':s = atoi(optarg);printf("%d\n",s);break;case 'E':E = atoi(optarg);printf("%d\n",E);break;case'b':b = atoi(optarg);printf("%d\n",b);break;case't':tracefile = optarg;printf("%s\n",tracefile);break;}}
(2)Cache组织结构
使用组相联方式组织cache,一个cache有多个组,每组有多个行。
每行有一个有效位,一个标记位,一块数据。
1、定义cache行结构:
typedef struct cache_line {char valid;mem_addr_t tag;unsigned long long int lru;
} cache_line_t;
2、使用指针定义组和cache,将每行的有效位,标记位,lru位都初始化为0
typedef Cache_line_t* cache_set_t; //用行定义组
cache_set_t* cache; //用组定义cache
(3)数据访问
1、获取标记和组索引:
//获取标记Address tag = addr >> (s+b);/*获取组索引, 地址共64位, 组索引位于中间,需要做按位与运算将标记位置置0set_index_mask = (mem_addr_t) (pow(2, s) - 1);*/Address set_index = (addr >> b) & (set_index_mask);
2、判断是否命中(有效位为1 && 标记位一致),如果命中返回
for(int i = 0; i < E; i++){if(cache_set[i].tag==tag&&cache_set[i].valid){//命中hit_count ++ ;cache_set[i].lru = lru_counter ++;return ;}}
3、如果没命中
(1)获得lru最小的一行
miss_count++;for(i=0; i<E; i++){//eviction_lru = ULONG_MAX,初始将eviction_lru置为最大值,以便比较if (cache_set[i].lru < eviction_lru){eviction_line = i;eviction_lru = cache_set[i].lru;}}
(2)根据有效位,决定是否驱逐
if( cache_set[eviction_line].valid ) eviction_count++;
(3)加载数据
cache_set[eviction_line].valid = 1;cache_set[eviction_line].tag = tag;cache_set[eviction_line].lru = lru_counter++;
这篇关于CSAPP Cache 知识总结; Cache Lab Part A的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!