Cache lab is more difficult than two labs I did before. You have to know what’s meaning of cache. And code some program to pass the examiner.
PART A
#include "cachelab.h"
#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include <limits.h>
#include <getopt.h>
#include <string.h>
int h,v,s,E,b,S; // global arguments
int hit_count ,
miss_count ,
eviction_count; // arguments from printSummary
char t[1000]; // store the cache file
typedef struct{
int valid_bits;
int tag;
int stamp;
}cache_line, *cache_asso, **cache; // cache structure。valid && tag && time stamp
cache _cache_ = NULL; // Define the 2 dimensional array
// print helper
void printUsage()
{
printf("Usage: ./csim-ref [-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> ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace\n"
" linux> ./csim-ref -v -s 8 -E 2 -b 4 -t traces/yi.trace\n");
}
// initialize the cache
void init_cache()
{
// We should allocate the memrory line by line in multi-dimensional array
_cache_ = (cache)malloc(sizeof(cache_asso) * S);
for(int i = 0; i < S; ++i)
{
_cache_[i] = (cache_asso)malloc(sizeof(cache_line) * E);
for(int j = 0; j < E; ++j)
{
_cache_[i][j].valid_bits = 0;
_cache_[i][j].tag = -1;
_cache_[i][j].stamp = -1;
}
}
}
void update(unsigned int address)
{
// set index && tag
int setindex_add = (address >> b) & ((-1U) >> (64 - s));
int tag_add = address >> (b + s);
int max_stamp = INT_MIN;
int max_stamp_index = -1;
for(int i = 0; i < E; ++i) //If the cache tag is the same as addr_tag, means to hit it.
{
if(_cache_[setindex_add][i].tag == tag_add)
{
_cache_[setindex_add][i].stamp = 0;
++hit_count;
return ;
}
}
for(int i = 0; i < E; ++i) // check whether exist the empty line
{
if(_cache_[setindex_add][i].valid_bits == 0)
{
_cache_[setindex_add][i].valid_bits = 1;
_cache_[setindex_add][i].tag = tag_add;
_cache_[setindex_add][i].stamp = 0;
++miss_count;
return ;
}
}
++eviction_count;
++miss_count;
for(int i = 0; i < E; ++i)
{
if(_cache_[setindex_add][i].stamp > max_stamp)
{
max_stamp = _cache_[setindex_add][i].stamp;
max_stamp_index = i;
}
}
_cache_[setindex_add][max_stamp_index].tag = tag_add;
_cache_[setindex_add][max_stamp_index].stamp = 0;
return ;
}
void update_stamp()
{
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;
}
void parse_trace()
{
FILE* fp = fopen(t, "r"); // read file
if(fp == NULL)
{
printf("open error");
exit(-1);
}
char operation;
unsigned int address;
int size;
while(fscanf(fp, " %c %xu,%d\n", &operation, &address, &size) > 0)
{
switch(operation)
{
// Pass the I instructions
case 'L':
update(address);
break;
case 'M':
update(address);
case 'S':
update(address);
}
update_stamp();
}
fclose(fp);
for(int i = 0; i < S; ++i)
free(_cache_[i]);
free(_cache_); // when we finished this part, we don't forget to free the cache
}
//===============================================================
int main(int argc, char* argv[])
{
h = 0;
v = 0;
hit_count = miss_count = eviction_count = 0;
int opt; // get the operation signal from function
while(-1 != (opt = (getopt(argc, argv, "hvs:E:b:t:"))))
{
switch(opt)
{
case 'h':
h = 1;
printUsage();
break;
case 'v':
v = 1;
printUsage();
break;
case 's':
s = atoi(optarg);
break;
case 'E':
E = atoi(optarg);
break;
case 'b':
b = atoi(optarg);
break;
case 't':
strcpy(t, optarg);
break;
default:
printUsage();
break;
}
}
if(s<=0 || E<=0 || b<=0 || t==NULL) // If we input invaid argument, we will exit.
return -1;
S = 1 << s; // S=2^s
FILE* fp = fopen(t, "r");
if(fp == NULL)
{
printf("open error");
exit(-1);
}
init_cache(); // init the cache
parse_trace(); // update the trace
printSummary(hit_count, miss_count, eviction_count);
return 0;
}PART B
void transpose_submit(int M, int N, int A[N][M], int B[M][N]) {
// S = 5, E = 1, B = 5
// at most 12 local int variables
if(M == 32 && N == 32)
{
for (int i = 0; i < N; i += 8) {
for (int j = 0; j < M; j += 8) {
for(int k = i; k < i + 8; k++)
{
int tmp1 = A[k][j];
int tmp2 = A[k][j+1];
int tmp3 = A[k][j+2];
int tmp4 = A[k][j+3];
int tmp5 = A[k][j+4];
int tmp6 = A[k][j+5];
int tmp7 = A[k][j+6];
int tmp8 = A[k][j+7];
B[j][k] = tmp1;
B[j+1][k] = tmp2;
B[j+2][k] = tmp3;
B[j+3][k] = tmp4;
B[j+4][k] = tmp5;
B[j+5][k] = tmp6;
B[j+6][k] = tmp7;
B[j+7][k] = tmp8;
}
}
}
}
else if(M == 64 && N == 64)
{
for (int i = 0; i < N; i += 4) {
for (int j = 0; j < M; j += 4) {
for(int k = i; k < i + 4; k += 2)
{
int tmp1 = A[k][j];
int tmp2 = A[k][j+1];
int tmp3 = A[k][j+2];
int tmp4 = A[k][j+3];
int tmp5 = A[k+1][j];
int tmp6 = A[k+1][j+1];
int tmp7 = A[k+1][j+2];
int tmp8 = A[k+1][j+3];
B[j][k] = tmp1;
B[j+1][k] = tmp2;
B[j+2][k] = tmp3;
B[j+3][k] = tmp4;
B[j][k+1] = tmp5;
B[j+1][k+1] = tmp6;
B[j+2][k+1] = tmp7;
B[j+3][k+1] = tmp8;
}
}
}
}
else if(M == 61 && N == 67)
{
for (int i = 0; i < N; i += 16) {
for (int j = 0; j < M; j += 16) {
for(int k = i; k < i + 16 && k < N; k ++)
for(int l = j; l < j + 16 && l < M; l++)
B[l][k] = A[k][l];
}
}
}
return;
}