The goal of this assignment is to provide you a better understanding of caches.
ID: 3822510 • Letter: T
Question
The goal of this assignment is to provide you a better understanding of caches. You are required to write a cache simulator using the C programming languages. The programs have to run on iLab machines and should be tested with the autograder. We are providing real program memory traces as input to your cache simulator. The format and structure of the memory traces are described below. Memory Access Traces The input to the cache simulator is a memory access trace, which we have generated by executing real programs. The trace contains memory addresses accessed during program execution. Your cache simulator will have to use these addresses to determine if the access is a hit, miss, and the actions to perform. The memory trace file consists of multiple lines. Each line of the trace file corresponds to a memory accesses performed by the program. Each line consists of multiple columns, which are space-separated. The first column reports the PC (program counter) when this particular memory access occurred. Second column lists whether the memory access is a read (R) or a write operation. And the last column reports the actual 48-bit memory address that has been accessed by the program. In this assignment, you only need to consider the second and the third columns (i.e. you don't really need to know the PCs). Cache Simulator You will implement a cache simulator to evaluate different configurations of caches. It should be able to run with different traces files. The followings are the requirements for your cache simulator: Simulate only one level cache: L1 The cache size, associativity, and block size are input parameters. Cache size and block size are specified in bytes. Replacement algorithm: First In First Out (FIFO) .When a block needs to be replaced, the cache evicts the block that was accessed first. It does not take into account whether the block is frequently or recently accessed.. It's a write through cache. You need to implement two types of caches as it will be explained later. Running your Cache Simulator You have to name your cache simulator first. Your program should support the following usage interface:/first where: A) is the total size of the cache in bytes. This number will be a power of 2. B) is one of: - direct - simulate a direct mapped cache. - assoc - simulate a fully associative cache. - assign - simulate an n - way associative cache, n will be a power of 2. C) is a power of 2 integer that specifies the size of the cache block in bytes. D) is the name of the trace file. In this assignment, you have to implement two types of caches (Type A and Type B). These caches differ in the bits of the address that they use to index into the cache. Type A: These cache use the indexing schemes discussed in class. We identify whether the access is a hit or a miss using the tag, index, and block bits from the address as shown below. Type B: Type B caches interprets the bits from the memory address differently. With Type B caches, the most significant bits of the 48-bit address constitute the index bits, which is followed by the tag bits and the block bits as shown below. Your program should print out the number of memory reads, memory writes, cache hits, and cache misses for each type of cache as shown below. You should follow the exact same format shown below, otherwise, the autograder can not grade your program properly. $./first 32 assoc:2 4 trace1.txt cache A Memory reads: 173 Memory writes: 334 Cache hits: 827 Cache misses: 173 cache B Memory reads: 667 Memory writes: 334 Cache hits: 333 Cache misses: 667 In this example above, we are simulating 2-way set associate cache of size 32 bytes. Each cache block is 4 bytes. The trace file name is "trace4.txt". As you can see, the simulator should simulate both catch types simultaneously (in the same run) and produce results (as shown above) for both cache types together. Simulation Details (a) When your program starts, there is nothing in the cache. So, all cache lines are empty, (b) you can assume that the memory size is 248. Therefore, memory addresses are 48 bit (zero extend the addresses in the trace file if they're less than 48-bit in length), (c) the number of bits in the tag, cache address, and byte address are determined by the cache size and the block size; (d) Your simulator should simulate the operation of a cache according to the given parameters for the given trace For a write-through cache, there is the question of what should happen in case of a write miss. In this assignment, the assumption is that the block is first read from memory (one read memory), and then followed by a memory write. You do not need to simulate the memory in this assignment. Because, the traces doesn't contain any information on 'data values" transferred between the memory and the caches. You have to compile your program with the following flags: -Wall -Werror -fsanitize=addressExplanation / Answer
Solution:-
The below given C program is a cache simulator and the program is commented on every line.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <ctype.h>
#include "sim.h"
/********************************
* 2. Structs *
********************************/
/* Block
*
* Holds an integer that states the validity of the bit (0 = invalid,
* 1 = valid), the tag being held, and another integer that states if
* the bit is dirty or not (0 = clean, 1 = dirty).
*/
struct Block_ {
int valid;
char* tag;
int dirty;
};
/* Cache
*
* Cache object that holds all the data about cache access as well as
* the write policy, sizes, and an array of blocks.
*
* @param hits # of cache accesses that hit valid data
* @param misses # of cache accesses that missed valid data
* @param reads # of reads from main memory
* @param writes # of writes from main memory
* @param cache_size Total size of the cache in bytes
* @param block_size How big each block of data should be
* @param numLines Total number of blocks
* @param blocks The actual array of blocks
*/
struct Cache_ {
int hits;
int misses;
int reads;
int writes;
int cache_size;
int block_size;
int numLines;
int write_policy;
Block* blocks;
};
/********************************
* 3. Utility Functions *
********************************/
/* Function List:
*
* 1) htoi
* 2) getBinary
* 3) formatBinary
* 4) btoi
* 5) parseMemoryAddress
*/
/* htoi
*
* Converts hexidecimal memory locations to unsigned integers.
* No real error checking is performed. This function will skip
* over any non recognized characters.
*/
unsigned int htoi(const char str[])
{
/* Local Variables */
unsigned int result;
int i;
i = 0;
result = 0;
if(str[i] == '0' && str[i+1] == 'x')
{
i = i + 2;
}
while(str[i] != '')
{
result = result * 16;
if(str[i] >= '0' && str[i] <= '9')
{
result = result + (str[i] - '0');
}
else if(tolower(str[i]) >= 'a' && tolower(str[i]) <= 'f')
{
result = result + (tolower(str[i]) - 'a') + 10;
}
i++;
}
return result;
}
/* getBinary
*
* Converts an unsigned integer into a string containing it's
* 32 bit long binary representation.
*
*
* @param num number to be converted
*
* @result char* binary string
*/
char *getBinary(unsigned int num)
{
char* bstring;
int i;
/* Calculate the Binary String */
bstring = (char*) malloc(sizeof(char) * 33);
assert(bstring != NULL);
bstring[32] = '';
for( i = 0; i < 32; i++ )
{
bstring[32 - 1 - i] = (num == ((1 << i) | num)) ? '1' : '0';
}
return bstring;
}
/* formatBinary
*
* Converts a 32 bit long binary string to a formatted version
* for easier parsing. The format is determined by the TAG, INDEX,
* and OFFSET variables.
*
* Ex. Format:
* -----------------------------------------------------
* | Tag: 18 bits | Index: 12 bits | Byte Select: 4 bits |
* -----------------------------------------------------
*
* Ex. Result:
* 000000000010001110 101111011111 00
*
* @param bstring binary string to be converted
*
* @result char* formated binary string
*/
char *formatBinary(char *bstring)
{
char *formatted;
int i;
/* Format for Output */
formatted = (char *) malloc(sizeof(char) * 35);
assert(formatted != NULL);
formatted[34] = '';
for(i = 0; i < TAG; i++)
{
formatted[i] = bstring[i];
}
formatted[TAG] = ' ';
for(i = TAG + 1; i < INDEX + TAG + 1; i++)
{
formatted[i] = bstring[i - 1];
}
formatted[INDEX + TAG + 1] = ' ';
for(i = INDEX + TAG + 2; i < OFFSET + INDEX + TAG + 2; i++)
{
formatted[i] = bstring[i - 2];
}
return formatted;
}
/* btoi
*
* Converts a binary string to an integer. Returns 0 on error.
*
* src: http://www.daniweb.com/software-development/c/code/216372
*
* @param bin binary string to convert
*
* @result int decimal representation of binary string
*/
int btoi(char *bin)
{
int b, k, m, n;
int len, sum;
sum = 0;
len = strlen(bin) - 1;
for(k = 0; k <= len; k++)
{
n = (bin[k] - '0');
if ((n > 1) || (n < 0))
{
return 0;
}
for(b = 1, m = len; m > k; m--)
{
b *= 2;
}
sum = sum + n * b;
}
return(sum);
}
/* parseMemoryAddress
*
* Helper function that takes in a hexidecimal address in
* the format of "0x00000000" and spits out the decimal,
* binary, and formatted binary equivilants. Also, it
* calculates the corresponding tag, index, and offset.
*
* @param address Hexidecimal memory address
*
* @return void
*/
void parseMemoryAddress(char *address)
{
unsigned int dec;
char *bstring, *bformatted, *tag, *index, *offset;
int i;
dec = htoi(address);
bstring = getBinary(dec);
bformatted = formatBinary(bstring);
if(DEBUG)
{
printf("Hex: %s ", address);
printf("Decimal: %u ", dec);
printf("Binary: %s ", bstring);
printf("Formatted: %s ", bformatted);
}
i = 0;
tag = (char *) malloc( sizeof(char) * (TAG + 1) );
assert(tag != NULL);
tag[TAG] = '';
for(i = 0; i < TAG; i++)
{
tag[i] = bformatted[i];
}
index = (char *) malloc( sizeof(char) * (INDEX + 1) );
assert(index != NULL);
index[INDEX] = '';
for(i = TAG + 1; i < INDEX + TAG + 1; i++)
{
index[i - TAG - 1] = bformatted[i];
}
offset = (char *) malloc( sizeof(char) * (OFFSET + 1) );
assert(offset != NULL);
offset[OFFSET] = '';
for(i = INDEX + TAG + 2; i < OFFSET + INDEX + TAG + 2; i++)
{
offset[i - INDEX - TAG - 2] = bformatted[i];
}
printf("Tag: %s (%i) ", tag, btoi(tag));
printf("Index: %s (%i) ", index, btoi(index));
printf("Offset: %s (%i) ", offset, btoi(offset));
}
/********************************
* 4. Main Function *
********************************/
/*
* Algorithm:
* 1. Validate inputs
* 2. Open the trace file for reading
* 3. Create a new cache object
* 4. Read a line from the file
* 5. Parse the line and read or write accordingly
* 6. If the line is "#eof" continue, otherwise go back to step 4
* 7. Print the results
* 8. Destroy the cache object
* 9. Close the file
*/
int main(int argc, char **argv)
{
/* Local Variables */
int write_policy, counter, i, j;
Cache cache;
FILE *file;
char mode, address[100];
/* Technically a line shouldn't be longer than 25 characters, but
allocate extra space in the buffer just in case */
char buffer[LINELENGTH];
/* Help Menu
*
* If the help flag is present or there are fewer than
* three arguments, print the usage menu and return.
*/
if(argc < 3 || strcmp(argv[1], "-h") == 0)
{
fprintf(stderr,
"Usage: ./sim [-h] <write policy> <trace file> <write policy> is one of: wt - simulate a write through cache. wb - simulate a write back cache <trace file> is the name of a file that contains a memory access trace. ");
return 0;
}
/* Write Policy */
if(strcmp(argv[1], "wt") == 0)
{
write_policy = 0;
if(DEBUG) printf("Write Policy: Write Through ");
}
else if(strcmp(argv[1], "wb") == 0)
{
write_policy = 1;
if(DEBUG) printf("Write Policy: Write Back ");
}
else
{
fprintf(stderr, "Invalid Write Policy. Usage: ./sim [-h] <write policy> <trace file> ");
return 0;
}
/* Open the file for reading. */
file = fopen( argv[2], "r" );
if( file == NULL )
{
fprintf(stderr, "Error: Could not open file. ");
return 0;
}
cache = createCache(CACHE_SIZE, BLOCK_SIZE, write_policy);
counter = 0;
while( fgets(buffer, LINELENGTH, file) != NULL )
{
if(buffer[0] != '#')
{
i = 0;
while(buffer[i] != ' ')
{
i++;
}
mode = buffer[i+1];
i = i+2;
j = 0;
while(buffer[i] != '')
{
address[j] = buffer[i];
i++;
j++;
}
address[j-1] = '';
if(DEBUG) printf("%i: %c %s ", counter, mode, address);
if(mode == 'R')
{
readFromCache(cache, address);
}
else if(mode == 'W')
{
writeToCache(cache, address);
}
else
{
printf("%i: ERROR!!!! ", counter);
fclose(file);
destroyCache(cache);
cache = NULL;
return 0;
}
counter++;
}
}
if(DEBUG) printf("Num Lines: %i ", counter);
printf("CACHE HITS: %i CACHE MISSES: %i MEMORY READS: %i MEMORY WRITES: %i ", cache->hits, cache->misses, cache->reads, cache->writes);
/* Close the file, destroy the cache. */
fclose(file);
destroyCache(cache);
cache = NULL;
return 1;
}
/********************************
* 5. Cache Functions *
********************************/
/* Function List:
*
* 1) createCache
* 2) destroyCache
* 3) readFromCache
* 4) writeToCache
* 5) printCache
*/
/* createCache
*
* Function to create a new cache struct. Returns the new struct on success
* and NULL on failure.
*
* @param cache_size size of cache in bytes
* @param block_size size of each block in bytes
* @param write_policy 0 = write through, 1 = write back
*
* @return success new Cache
* @return failure NULL
*/
Cache createCache(int cache_size, int block_size, int write_policy)
{
/* Local Variables */
Cache cache;
int i;
/* Validate Inputs */
if(cache_size <= 0)
{
fprintf(stderr, "Cache size must be greater than 0 bytes... ");
return NULL;
}
if(block_size <= 0)
{
fprintf(stderr, "Block size must be greater than 0 bytes... ");
return NULL;
}
if(write_policy != 0 && write_policy != 1)
{
fprintf(stderr, "Write policy must be either "Write Through" or "Write Back". ");
return NULL;
}
/* Lets make a cache! */
cache = (Cache) malloc( sizeof( struct Cache_ ) );
if(cache == NULL)
{
fprintf(stderr, "Could not allocate memory for cache. ");
return NULL;
}
cache->hits = 0;
cache->misses = 0;
cache->reads = 0;
cache->writes = 0;
cache->write_policy = write_policy;
cache->cache_size = CACHE_SIZE;
cache->block_size = BLOCK_SIZE;
/* Calculate numLines */
cache->numLines = (int)(CACHE_SIZE / BLOCK_SIZE);
cache->blocks = (Block*) malloc( sizeof(Block) * cache->numLines );
assert(cache->blocks != NULL);
/* By default insert blocks where valid = 0 */
for(i = 0; i < cache->numLines; i++)
{
cache->blocks[i] = (Block) malloc( sizeof( struct Block_ ) );
assert(cache->blocks[i] != NULL);
cache->blocks[i]->valid = 0;
cache->blocks[i]->dirty = 0;
cache->blocks[i]->tag = NULL;
}
return cache;
}
/* destroyCache
*
* Function that destroys a created cache. Frees all allocated memory. If
* you pass in NULL, nothing happens. So make sure to set your cache = NULL
* after you destroy it to prevent a double free.
*
* @param cache cache object to be destroyed
*
* @return void
*/
void destroyCache(Cache cache)
{
int i;
if(cache != NULL)
{
for( i = 0; i < cache->numLines; i++ )
{
if(cache->blocks[i]->tag != NULL)
{
free(cache->blocks[i]->tag);
}
free(cache->blocks[i]);
}
free(cache->blocks);
free(cache);
}
return;
}
/* readFromCache
*
* Function that reads data from a cache. Returns 0 on failure
* or 1 on success.
*
* @param cache target cache struct
* @param address hexidecimal address
*
* @return success 1
* @return failure 0
*/
int readFromCache(Cache cache, char* address)
{
unsigned int dec;
char *bstring, *bformatted, *tag, *index, *offset;
int i;
Block block;
/* Validate inputs */
if(cache == NULL)
{
fprintf(stderr, "Error: Must supply a valid cache to write to. ");
return 0;
}
if(address == NULL)
{
fprintf(stderr, "Error: Must supply a valid memory address. ");
return 0;
}
/* Convert and parse necessary values */
dec = htoi(address);
bstring = getBinary(dec);
bformatted = formatBinary(bstring);
if(DEBUG)
{
printf("Hex: %s ", address);
printf("Decimal: %u ", dec);
printf("Binary: %s ", bstring);
printf("Formatted: %s ", bformatted);
}
i = 0;
tag = (char *) malloc( sizeof(char) * (TAG + 1) );
assert(tag != NULL);
tag[TAG] = '';
for(i = 0; i < TAG; i++)
{
tag[i] = bformatted[i];
}
index = (char *) malloc( sizeof(char) * (INDEX + 1) );
assert(index != NULL);
index[INDEX] = '';
for(i = TAG + 1; i < INDEX + TAG + 1; i++)
{
index[i - TAG - 1] = bformatted[i];
}
offset = (char *) malloc( sizeof(char) * (OFFSET + 1) );
assert(offset != NULL);
offset[OFFSET] = '';
for(i = INDEX + TAG + 2; i < OFFSET + INDEX + TAG + 2; i++)
{
offset[i - INDEX - TAG - 2] = bformatted[i];
}
if(DEBUG)
{
printf("Tag: %s (%i) ", tag, btoi(tag));
printf("Index: %s (%i) ", index, btoi(index));
printf("Offset: %s (%i) ", offset, btoi(offset));
}
/* Get the block */
block = cache->blocks[btoi(index)];
if(DEBUG)
{
printf("Attempting to read data from cache slot %i. ", btoi(index));
}
if(block->valid == 1 && strcmp(block->tag, tag) == 0)
{
cache->hits++;
free(tag);
}
else
{
cache->misses++;
cache->reads++;
if(cache->write_policy == 1 && block->dirty == 1)
{
cache->writes++;
block->dirty = 0;
}
block->valid = 1;
if(block->tag != NULL)
{
free(block->tag);
}
block->tag = tag;
}
free(bstring);
free(bformatted);
free(offset);
free(index);
return 1;
}
/* writeToCache
*
* Function that writes data to the cache. Returns 0 on failure or
* 1 on success. Frees any old tags that already existed in the
* target slot.
*
* @param cache target cache struct
* @param address hexidecimal address
*
* @return success 1
* @return error 0
*/
int writeToCache(Cache cache, char* address)
{
unsigned int dec;
char *bstring, *bformatted, *tag, *index, *offset;
int i;
Block block;
/* Validate inputs */
if(cache == NULL)
{
fprintf(stderr, "Error: Must supply a valid cache to write to. ");
return 0;
}
if(address == NULL)
{
fprintf(stderr, "Error: Must supply a valid memory address. ");
return 0;
}
/* Convert and parse necessary values */
dec = htoi(address);
bstring = getBinary(dec);
bformatted = formatBinary(bstring);
if(DEBUG)
{
printf("Hex: %s ", address);
printf("Decimal: %u ", dec);
printf("Binary: %s ", bstring);
printf("Formatted: %s ", bformatted);
}
i = 0;
tag = (char *) malloc( sizeof(char) * (TAG + 1) );
assert(tag != NULL);
tag[TAG] = '';
for(i = 0; i < TAG; i++)
{
tag[i] = bformatted[i];
}
index = (char *) malloc( sizeof(char) * (INDEX + 1) );
assert(index != NULL);
index[INDEX] = '';
for(i = TAG + 1; i < INDEX + TAG + 1; i++)
{
index[i - TAG - 1] = bformatted[i];
}
offset = (char *) malloc( sizeof(char) * (OFFSET + 1) );
assert(offset != NULL);
offset[OFFSET] = '';
for(i = INDEX + TAG + 2; i < OFFSET + INDEX + TAG + 2; i++)
{
offset[i - INDEX - TAG - 2] = bformatted[i];
}
if(DEBUG)
{
printf("Tag: %s (%i) ", tag, btoi(tag));
printf("Index: %s (%i) ", index, btoi(index));
printf("Offset: %s (%i) ", offset, btoi(offset));
}
/* Get the block */
block = cache->blocks[btoi(index)];
if(DEBUG)
{
printf("Attempting to write data to cache slot %i. ", btoi(index));
}
if(block->valid == 1 && strcmp(block->tag, tag) == 0)
{
if(cache->write_policy == 0)
{
cache->writes++;
}
block->dirty = 1;
cache->hits++;
free(tag);
}
else
{
cache->misses++;
cache->reads++;
if(cache->write_policy == 0)
{
cache->writes++;
}
if(cache->write_policy == 1 && block->dirty == 1)
{
cache->writes++;
}
block->dirty = 1;
block->valid = 1;
if(block->tag != NULL)
{
free(block->tag);
}
block->tag = tag;
}
free(bstring);
free(bformatted);
free(offset);
free(index);
return 1;
}
/* printCache
*
* Prints out the values of each slot in the cache
* as well as the hit, miss, read, write, and size
* data.
*
* @param cache Cache struct
*
* @return void
*/
void printCache(Cache cache)
{
int i;
char* tag;
if(cache != NULL)
{
for(i = 0; i < cache->numLines; i++)
{
tag = "NULL";
if(cache->blocks[i]->tag != NULL)
{
tag = cache->blocks[i]->tag;
}
printf("[%i]: { valid: %i, tag: %s } ", i, cache->blocks[i]->valid, tag);
}
printf("Cache: CACHE HITS: %i CACHE MISSES: %i MEMORY READS: %i MEMORY WRITES: %i CACHE SIZE: %i Bytes BLOCK SIZE: %i Bytes NUM LINES: %i ", cache->hits, cache->misses, cache->reads, cache->writes, cache->cache_size, cache->block_size, cache->numLines);
}
}
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.