TDT4258/ex2/cache_sim.c

302 lines
8.2 KiB
C
Raw Permalink Normal View History

2022-12-19 18:06:38 +01:00
#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <stdbool.h>
#define RED_START "\033[31m"
#define COLOR_END "\033[0m"
#define DEBUG
typedef enum { dm, fa } cache_map_t;
typedef enum { uc, sc } cache_org_t;
typedef enum { instruction, data } access_t;
typedef struct {
uint32_t address;
access_t accesstype;
} mem_access_t;
typedef struct {
uint64_t accesses;
uint64_t hits;
// You can declare additional statistics if
// you like, however you are now allowed to
// remove the accesses or hits
} cache_stat_t;
// DECLARE CACHES AND COUNTERS FOR THE STATS HERE
typedef struct {
bool is_initialized;
int content;
} cache_block_t;
cache_block_t* cache;
uint32_t cache_size;
uint32_t block_size = 64;
cache_map_t cache_mapping;
cache_org_t cache_org;
// Misc
// USE THIS FOR YOUR CACHE STATISTICS
cache_stat_t cache_statistics;
/* Reads a memory access from the trace file and returns
* 1) access type (instruction or data access
* 2) memory address
*/
mem_access_t read_transaction(FILE* ptr_file) {
char buf[1000];
char* token;
char* string = buf;
mem_access_t access;
if (fgets(buf, 1000, ptr_file) != NULL) {
/* Get the access type */
token = strsep(&string, " \n");
if (strcmp(token, "I") == 0) {
access.accesstype = instruction;
} else if (strcmp(token, "D") == 0) {
access.accesstype = data;
} else {
printf(
"Could not parse access type:\n"
"%s%s%s %s\n",
RED_START, token, COLOR_END, strsep(&string, " \n"));
exit(0);
}
/* Get the access type */
token = strsep(&string, " \n");
access.address = (uint32_t)strtol(token, NULL, 16);
return access;
}
/* If there are no more entries in the file,
* return an address 0 that will terminate the infinite loop in main
*/
access.address = 0;
return access;
}
static int cache_access(mem_access_t access) {
}
const char* usage =
"Usage:\n"
"cache_sim size mapping organization [file]\n"
"\tsize: 128-4096\n"
"\tmapping: dm | fa \n"
"\torganization: uc | sc\n"
"\tfile: path\n";
/* Read command-line parameters and initialize:
* cache_size, cache_mapping and cache_org variables
*/
static void handle_arguments(int argc, char** argv) {
if (argc < 4) perror(usage);
/* argv[0] is program name, parameters start with argv[1] */
/* Set cache size */
cache_size = atoi(argv[1]);
// if (128 < cache_size || cache_size < 4096) error(
// "Cache size needs to be be between 128 and 4096\n"
// "Please check the input: %s%s%s",
// RED_START, argv[1], COLOR_END
// );
/* Set Cache Mapping */
if (strcmp(argv[2], "dm") == 0) {
cache_mapping = dm;
} else if (strcmp(argv[2], "fa") == 0) {
cache_mapping = fa;
} else {
printf("Unknown cache mapping\n");
exit(1);
}
/* Set Cache Organization */
if (strcmp(argv[3], "uc") == 0) {
cache_org = uc;
} else if (strcmp(argv[3], "sc") == 0) {
cache_org = sc;
} else {
printf("Unknown cache organization\n");
exit(1);
}
}
static bool access_cache_dm(int index, int tag) {
bool foundMatch = cache[index].is_initialized
&& cache[index].content == tag;
if (foundMatch) return true;
cache[index].is_initialized = true;
cache[index].content = tag;
#ifdef DEBUG
// printf("Overwriting tag at cache[%d] = %x\n", index, cache + index);
#endif
return false;
}
static bool access_cache_fa(int tag, cache_block_t* local_cache, int* counter, int number_of_blocks) {
for (int i = 0; i < number_of_blocks; i++)
if (local_cache[i].is_initialized && local_cache[i].content == tag)
return true;
(*counter)++;
// if (*counter == number_of_blocks) *counter = 0;
(*counter) %= number_of_blocks;
local_cache[*counter].is_initialized = true;
local_cache[*counter].content = tag;
#ifdef DEBUG
// printf("Overwriting tag at cache[%d] = %x\n", *counter, local_cache + *counter);
#endif
return false;
}
int main(int argc, char** argv) {
// Reset statistics:
memset(&cache_statistics, 0, sizeof(cache_stat_t));
handle_arguments(argc, argv);
// Will truncate 0, but that should not matter if args are handled correctly.
int number_of_blocks = cache_size / block_size;
int bits_for_offset = 0;
int bs = block_size;
while (bs % 2 == 0) {
bits_for_offset++;
bs = bs >> 1;
}
int bits_for_index = 0;
if (cache_mapping == dm) {
int nob = number_of_blocks;
while (nob % 2 == 0) {
bits_for_index++;
nob = nob >> 1;
}
// If the cache is half the size (split), we will need 1 less bit for the index.
if (cache_org == sc) bits_for_index --;
}
int bits_for_tag = 32 - bits_for_index - bits_for_offset;
int offset_mask = (1 << bits_for_offset) - 1;
int index_mask = ((1 << bits_for_index) - 1) << bits_for_offset;
int tag_mask = ((1 << bits_for_tag) - 1) << (bits_for_index + bits_for_index);
#ifdef DEBUG
printf("Block offset mask: %08x\n", offset_mask);
printf("Index mask: %08x\n", index_mask);
printf("Tag mask: %08x\n", tag_mask);
#endif
int fa_counter1 = 0;
int fa_counter2 = 0;
int* fa_counter1_p = &fa_counter1;
int* fa_counter2_p = &fa_counter2;
#ifdef DEBUG
printf("Number of blocks: %d\n", number_of_blocks);
printf("Bits for offset: %d\n", bits_for_offset);
printf("Bits for index: %d\n", bits_for_index);
printf("Bits for tag: %d\n", bits_for_tag);
printf("Size of cache_block: %d\n", sizeof(cache_block_t));
printf("Cache size: %d\n", number_of_blocks * sizeof(cache_block_t));
printf("Half cache size: %d\n", number_of_blocks * sizeof(cache_block_t) / 2);
#endif
cache = (cache_block_t*) malloc(number_of_blocks * sizeof(cache_block_t));
// Pointer arithmetic black magic compiler voodoo will ensure that this is correct
// (I spent waaaay to long figuring out that '+' doesn't literally mean integer addition when working
// with pointers types...)
cache_block_t* upper_half_cache = cache + (number_of_blocks / 2);
#ifdef DEBUG
printf("Cache location: %d\n", cache);
printf("Upper half cache location: %d\n\n", upper_half_cache);
#endif
// exit(1);
// The global cache memory and global args values should now have been set.
/* Open the file mem_trace.txt to read memory accesses */
FILE* ptr_file;
ptr_file = fopen("mem_trace.txt", "r");
if (!ptr_file) {
printf("Unable to open the trace file\n");
exit(1);
}
#ifdef DEBUG
int line = 0;
#endif
/* Loop until whole trace file has been read */
mem_access_t access;
while (1) {
access = read_transaction(ptr_file);
// If no transactions left, break out of loop
if (access.address == 0) break;
/* Do a cache access */
cache_statistics.accesses++;
int tag = (access.address & tag_mask) >> bits_for_offset + bits_for_index;
int index = (access.address & index_mask) >> bits_for_offset;
bool is_data = access.accesstype == data;
#ifdef DEBUG
// printf("Line: %u\n", line++);
// printf("%c %08x\n", access.accesstype == instruction ? 'I' : 'D', access.address);
// printf("Tag: %x\n", tag);
// printf("Index: %x\n", index);
#endif
if ( (cache_mapping == fa && cache_org == uc && access_cache_fa(tag, cache, fa_counter1_p, number_of_blocks))
|| (cache_mapping == fa && cache_org == sc && (!is_data
? access_cache_fa(tag, cache, fa_counter1_p, number_of_blocks / 2)
: access_cache_fa(tag, upper_half_cache, fa_counter2_p, number_of_blocks / 2)))
|| (cache_mapping == dm && cache_org == uc && access_cache_dm(index, tag))
|| (cache_mapping == dm && cache_org == sc && access_cache_dm(index + (number_of_blocks / 2) * is_data, tag))
) {
#ifdef DEBUG
// printf("Hit!\n");
#endif
cache_statistics.hits++;
}
#ifdef DEBUG
// printf("\n");
#endif
}
printf("\nCache Statistics\n");
printf("-----------------\n\n");
printf("Accesses: %ld\n", cache_statistics.accesses);
printf("Hits: %ld\n", cache_statistics.hits);
printf("Hit Rate: %.4f\n",
(double)cache_statistics.hits / cache_statistics.accesses);
fclose(ptr_file);
return 0;
}