cachelab是csapp的配套实验之一,该实验分为A、B两个部分,A部分要求实现一个cache模拟器,B部分是实现一个针对cache优化的矩阵转置函数
Part A
Part A部分我们需要完成csim.c源文件,参考csim-ref程序接收相同的命令行参数并产生相同的输出。csim-ref是一个参考可执行程序,它能够模拟cache并处理valgrind生成的trace文件,它遵循LRU(最近使用)替换策略。我们的main函数要依次做如下几件事情:
- 使用getopt库处理参数,保存cache的几个基本参数如s、E、b,并根据基本参数计算其它参数如S、B、t等。
- 根据这些参数初始化cache,这步需要使用malloc动态申请内存。
- 读取trace文件并逐行处理每一个operation,其中I操作可以忽略,L和S操作访问cache一次,M操作访问cache两次,这是最关键的一步。
- 关闭文件流并释放cache的内存。
- 使用printSummary函数输出结果。
代码如下,关键部分已有注释:
#include <stdlib.h>
#include <stdio.h>
#include <getopt.h>
#include <stdbool.h>
#include <string.h>
#include "cachelab.h"
#define m (sizeof(void*)*8)
//块结构(不带数据)
struct block{
bool valid;
int tag;
int timestamp;
};
int hits = 0;
int misses = 0;
int evictions = 0;
int timestamp = 0; //时间戳,每读取一个操作+1
bool verbose = false;
int s, E, b;
int S, B, t;
int C;
FILE *fp;
struct block ***cache;
char operationStr[256];
void printHelp(){
printf("Help...\n");
}
//解析参数
void getOptions(int argc, char* argv[]){
int opt;
while((opt=getopt(argc, argv, "hvs:E:b:t:"))!=-1){
switch (opt)
{
case 'h':
printHelp();
exit(0);
case 'v':
verbose = true;
break;
case 's':
s = atoi(optarg);
S = 1<<s;
break;
case 'E':
E = atoi(optarg);
break;
case 'b':
b = atoi(optarg);
B = 1<<b;
break;
case 't':
fp = fopen(optarg, "r");
if(fp == NULL){
fprintf(stderr, "Open file failed");
exit(-1);
}
break;
default:
break;
}
}
t = m - (s+b);
C = B*E*S;
}
//根据参数初始化cache
void initCache(){
cache = malloc(sizeof(void*)*S);
for(int i = 0; i<S; i++){
cache[i] = malloc(sizeof(void*)*E);
for(int j = 0; j<E; j++){
struct block *pBlock = malloc(sizeof(struct block));
pBlock->valid = false;
pBlock->tag = 0;
pBlock->timestamp = 0;
cache[i][j] = pBlock;
}
}
}
//释放cache
void freeCache(){
for(int i = 0; i<S; i++){
for(int j = 0; j<E; j++){
free(cache[i][j]);
}
free(cache[i]);
}
free(cache);
}
void callCache(unsigned long long address){
int setAddress = address<<t>>(t+b);
int tagAddress = address>>(s+b);
struct block **pSet = cache[setAddress];
struct block *pHitBlock = NULL;//命中的Block
struct block *pEmptyBlock = NULL;//set中首个空的block
struct block *pLRUBlock = NULL;//LRU策略下准备替换的block
for(int i = 0; i<E; i++){
struct block *pBlock = pSet[i];
//找到对应tag的block即为命中缓存
if(pHitBlock == NULL && pBlock->valid && pBlock->tag == tagAddress){
pHitBlock = pBlock;
}
//遍历到的第一个空的block作为miss后使用的block
if(pEmptyBlock == NULL && !pBlock->valid){
pEmptyBlock = pBlock;
}
//timestamp最小的block即为最长时间没有访问的block
if(pBlock->valid && (pLRUBlock == NULL || pLRUBlock->timestamp > pBlock->timestamp)){
pLRUBlock = pBlock;
}
}
if(pHitBlock!=NULL){
hits++;
if(verbose){
printf(" hit");
}
pHitBlock->timestamp = timestamp;
}
else{
misses++;
if(verbose){
printf(" miss");
}
if(pEmptyBlock!=NULL){
pEmptyBlock->valid = true;
pEmptyBlock->tag = tagAddress;
pEmptyBlock->timestamp = timestamp;
}
else{
//此时pLRUBlock必不为空
if(pLRUBlock == NULL){
printf("LRU Error\n");
exit(-1);
}
evictions++;
if(verbose){
printf(" eviction");
}
pLRUBlock->tag = tagAddress;
pLRUBlock->timestamp = timestamp;
}
}
}
//处理操作
void handleOpertaion(){
timestamp++;
char opType;
unsigned long long address;
int size;
int count = sscanf(operationStr, " %c %llx,%d", &opType, &address, &size);
//不匹配的行是I操作,忽略即可
if(count==0){
return;
}
if(verbose){
printf("%s", operationStr);
}
switch (opType)
{
case 'L':
callCache(address);
break;
case 'S':
callCache(address);
break;
case 'M': //M需要访问两次
callCache(address);
callCache(address);
break;
default:
break;
}
if(verbose){
printf("\n");
}
}
void handleInput(){
while(fgets(operationStr, 256, fp)){
if(operationStr[strlen(operationStr)-1]=='\n'){
operationStr[strlen(operationStr)-1]='\0';
}
handleOpertaion();
}
}
int main(int argc, char* argv[])
{
getOptions(argc, argv);
initCache();
handleInput();
fclose(fp);
freeCache();
printSummary(hits, misses, evictions);
return 0;
}
根据ReadMe中的指示,Make
命令编译后,再运行测试程序test-csim,运行结果如下:
得到27分即完成Part A。
Part B
Part B部分我们需要完成trans.c源文件,实现矩阵的转置同时要尽可能的减少cache miss。
首先如下指令安装valgrind
sudo apt install valgrind
注意在进行后续步骤前,要将当前实验目录移动到linux其它目录而非docker的共享文件夹中,否则会出现Program timed out,并且运行driver.py脚本需要python2.7环境。所谓cache friendly如何做到呢,现在脑子里有几个概念:
- 程序要有良好的
空间局部性
和时间局部性
。时间局部性是多次访问同一个地址尽可能在同一小时间段内(后面访问时该地址大概率在cache里);空间局部性是在一小段时间内访问的地址尽可能靠近(这样两个地址更可能在同一个block内)。大部分业务层的代码做到这两点基本就够了 - 对于性能要求苛刻的场景(大循环和重计算),核心开销代码不得不考虑进行更深层次的cache优化。每个函数都可以视为自身 独占 完整的cache资源(就算刚执行时cache中都是其它数据,在函数执行一定时间后cache的大量block也会被替换为该函数访问的地址),此时考虑cache的平均hit率,一个有效的策略是对于循环访问的数组进行
分块
。
32×32
首先计算cache的大小,在test-trans.c中使用的cache是(s=5,E=1,b=5)规格,每个block 2^5=32个字节,能存储8个int值;每一组只有一个块,一共有2^5=32组,所以cache能同时保存32*8=256个int值,也就是可以同时缓存256*4=1024字节=1M连续地址空间的内容。
分析给出的示例代码,单次循环要分别访问A[i][j]和B[j][i]一次,cache在执行该函数时被A和B数组共用。函数对A数组的是沿行遍历访问,效率尚可,对A的访问一共会产生32*4=128次左右miss。但是由于需要对数组转置,对B数组的遍历访问是沿列遍历访问,空间局部性很差,几乎每次访问都是miss,一共会产生1024次左右miss。我们的目标就清晰了,改进遍历方式,优化B数组访问的空间局部性,同时不对A的空间局部性产生影响。根据ppt的提示,我们可以使用分块
的方式,也就是将A、B数组分成数个大小一致的正方块,只要保证访问每个块的空间局部性是较优的,那么让数组按块遍历的空间局部性也是较优的。由于cache至多可以存放32×32数组中连续8行的地址空间,所以我们选用8x8
作为遍历的基本单位,A、B数组分别被分为16个块,平均每个块产生8次miss,理论上一共产生16*8*2=256次miss。
void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
if(M == 32){
int i, j, tmp;
int k1, k2;
for(k1 = 0; k1<32; k1+=8){
for(k2=0; k2<32; k2+=8){
for(i=0; i<8; i++){
for(j=0; j<8; j++){
tmp = A[k1+i][k2+j];
B[k2+j][k1+i] = tmp;
}
}
}
}
}
}
使用如上代码测试转置32×32的矩阵一共产生了343次miss,原因是A、B数组共用一个cache,所以某些块会出现A某行(对应B某列)使用cache的同一个block的情况,此时A、B不再能视为各自独立访问。简化计算可以假设A[0][0]和B[0][0]都使用cache的第0组,位于左对角线上的元素会额外产生一次miss,位于对角线上的块会多产生8次miss,每个数组的访问会多产生32次miss,这样理论上一共产生(16*8+32)*2=320次miss。此时就要考虑 时间局部性 的优化,由于题目限制不能在栈上定义超过12个局部变量,我们可以定义8个中间值tmp0~tmp7,将A数组块中一行的数据一次性取出分别赋给8个局部变量,然后在逐个赋给B数组块中一列的数据,这样对角线上的元素仅在访问B时才会产生一次额外miss,理论上一共产生16*8*2+32=288次。
void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
if(M == 32){
int i, tmp0,tmp1,tmp2,tmp3,tmp4,tmp5,tmp6,tmp7;
int k1, k2;
for(k1 = 0; k1<M; k1+=8){
for(k2=0; k2<M; k2+=8){
for(i=0; i<8; i++){
tmp0 = A[k1+i][k2];
tmp1 = A[k1+i][k2+1];
tmp2 = A[k1+i][k2+2];
tmp3 = A[k1+i][k2+3];
tmp4 = A[k1+i][k2+4];
tmp5 = A[k1+i][k2+5];
tmp6 = A[k1+i][k2+6];
tmp7 = A[k1+i][k2+7];
B[k2][k1+i] = tmp0;
B[k2+1][k1+i] = tmp1;
B[k2+2][k1+i] = tmp2;
B[k2+3][k1+i] = tmp3;
B[k2+4][k1+i] = tmp4;
B[k2+5][k1+i] = tmp5;
B[k2+6][k1+i] = tmp6;
B[k2+7][k1+i] = tmp7;
}
}
}
}
}
使用如上代码测试转置32×32的矩阵一共产生了287次miss符合预期,低于300次即可拿到满分。
64×64
对于64×64的矩阵,明显不能单纯使用8×8的分块策略,因为每行从32个值增加为64个值,此时cache至多可以存放64×64数组中连续4行的地址空间。按照之前的思路我们选用 4x4
的分块策略,数组将被分为256个块,那么理论上共会产生256*4*256*2+64=1600次miss,实际测试时发现产生了1699次miss,没达到满分1300次以内的要求,只得到了3.4分,原因是在4×4分块时cache的利用率较低。看了下网上的解决方案都比较复杂,这种针对特定场景的高级别的优化基本可以看作是纯粹的脑力训练,这里我就不求甚解了,代码如下
void transpose_submit(int M, int N, int A[N][M], int B[M][N]){
if(M == 64){
int i, tmp0,tmp1,tmp2,tmp3;
int k1, k2;
for(k1 = 0; k1<M; k1+=4){
for(k2=0; k2<N; k2+=4){
for(i=0;i<4;i++){
tmp0 = A[k1+i][k2];
tmp1 = A[k1+i][k2+1];
tmp2 = A[k1+i][k2+2];
tmp3 = A[k1+i][k2+3];
B[k2][k1+i] = tmp0;
B[k2+1][k1+i] = tmp1;
B[k2+2][k1+i] = tmp2;
B[k2+3][k1+i] = tmp3;
}
}
}
}
}
61×67
对于不规则61×67的矩阵,可以先对60×60的矩阵使用4×4的分块策略,剩下的部分直接用最原始的赋值即可。代码如下:
void transpose_submit(int M, int N, int A[N][M], int B[M][N]){
if(M == 61){
int i, tmp0,tmp1,tmp2,tmp3;
int k1, k2;
int k1_max = M/4*4;
int k2_max = N/4*4;
for(k1 = 0; k1<k1_max; k1+=4){
for(k2=0; k2<k2_max; k2+=4){
for(i=0;i<4;i++){
tmp0 = A[k1+i][k2];
tmp1 = A[k1+i][k2+1];
tmp2 = A[k1+i][k2+2];
tmp3 = A[k1+i][k2+3];
B[k2][k1+i] = tmp0;
B[k2+1][k1+i] = tmp1;
B[k2+2][k1+i] = tmp2;
B[k2+3][k1+i] = tmp3;
}
}
}
for(k1=k1_max; k1<M; k1++){
for(k2=0; k2<k2_max; k2++){
tmp0 = A[k1][k2];
B[k2][k1] = tmp0;
}
}
for(k1=0; k1<k1_max; k1++){
for(k2=k2_max; k2<N; k2++){
tmp0 = A[k1][k2];
B[k2][k1] = tmp0;
}
}
for(k1=k1_max; k1<M; k1++){
for(k2=k2_max; k2<N; k2++){
tmp0 = A[k1][k2];
B[k2][k1] = tmp0;
}
}
}
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/38135.html