Question

C Programming Assignment 4

Cache Simulation

Objective:

To write a C program that simulates reading and writing to a custom-sized direct-mapped cache, involving a custom-sized main memory.

The program will read all values from the ZyLab as Test Bench inputs.

Main Menu Options:

The program simulates reading from and writing to a cache based on choosing from a menu of choices, where each choice calls the appropriate procedure, where the choices are:

1. Enter Configuration Parameters
2. Read from Cache
3. Write to Cache
4. Quit Program

Note that when you read from ZyLab, the input values are not displayed on the screen as they are in the sample run at the end of this document.

Inputs:

• Enter Parameters
  • The total size of accessible main memory (in words)
  • The total size of the cache (in words)
  • The block size (words/block)
• Read from Cache
  • The main memory address to read
• Write to Cache
  • The main memory address to write
  • The contents of the address for writing to the cache

Input Value Checks:

• All the parameter values must be powers of 2.
• The block size must never be larger than the size of accessible main memory.
• The total cache size must be some multiple of the block size.
• Your program should verify that all input variables are within limits as they are entered.

Output Messages:

All messages should be display EXACTLY as shown in the sample run; that is, prefixed by three asterisks, a space and hyphen and one more space. The message should be followed by a blank line.   

• Data Accepted Message is comprised of two sentences:

*** All Input Parameters Accepted.

     Starting to Process Write/Read Requests

• Error Messages are preceded by “*** Error –“. A list of possible errors is given below.

Note that one message has been deleted from previous versions of this Specification and three new ones have been added.

*** Error - Main Memory Size is not a Power of 2

*** Error - Block Size is not a Power of 2

*** Error - Cache Size is not a Power of 2

*** Error – Block size is larger than cache size

• Deleted Error Message

*** Error – Cache Size is not a multiple of Block Size

• Newly Added Error Messages

*** Error – Read Address Exceeds Memory Address Space

*** Error – Write Address Exceeds Memory Address Space (The write value following the invalid address value should be read and then discarded)

*** Error – Invalid Menu Option Selected (Until configuration data has been accepted, the only valid menu options that can be entered are “1” or “4.”)

Whenever any one of these errors occurs, the program should loop back to the Main Menu.

• Content Message resulting from reading/writing to the cache

*** Word WW of Cache Line LL with Tag TT contains Value VV

This message should appear after all successful reads or writes

WW is the word number in the cache line, LL is the line number in the cache, TT is the line’s tag value and VV is the content value in the cache.

All values are in decimal.

• Read Messages (two possible messages)

*** Read Miss - First Load Block from Memory (followed on the next line by the Content Message above)

*** Cache Hit (followed on the next line by the Content Message above)

• Write Messages

*** Write Miss - First Load Block from Memory (followed on the next line by the Content Message above)

*** Cache Hit (followed on the next line by the Content Message above)

• Quit Program Message

*** Memory Freed Up – Program Terminated Normally

When option 4 is entered, the memory should be freed up and the message “Memory Freed Up – Program Terminated Normally”, followed by a blank line, should be displayed before exiting the program.

Program Requirements:

• Use a structure (struct) to represent a cache line consisting of a tag (integer) and a block (integer pointer). Define the cache to be a pointer to the struct.
• Upon entering the parameters, the main memory and cache are to be dynamically allocated (use malloc) based on their respective total sizes.

Each word i of main memory is initialized with the value M–i, where M is the size of main memory in words. So, memory location 0 will contain the address of the last memory location and the last memory location will contain the address of the first memory location (i.e. 0).

• Reading/writing from/to a new block in the cache results in dynamically allocating a block for that instance, based on the previously entered block size.

Prologue & Comments:

At the very beginning of your source code (the very first lines), please include a prologue which looks like the following:

/*

Dr. George Lazik                      (use your full name not mine)

Programming Assignment 4: Cache Simulation

Comp 222 – Fall 2019

Meeting Time: 0800-0915       (your meeting time)

*/

• Include simple (brief) comments strategically throughout your program so that someone else can readily follow what you are doing, but don’t overdo it. Examples might look like these:

// Reading input values from ZyLab

// Determining the contents of memory

ZyLab Test Benches:

• You will be permitted unlimited submission attempts on ZyLab until the due date. Afterwards, the inputs will be changed, the point value of the assignment will be increased to 100 and only one submission will be permitted. This last submission will be on the day following the due date and should be the one with the highest score.

• Hardcopy printed listing of your program. Please place this on the Professor’s desk at the beginning of class on day the assignment is due. It should be properly C formatted listing and not one from programs such as Word.

Make sure your full name appears on each page of the listing and that all pages are stapled together in their correct order BEFORE you come to class.

Failure to provide this listing will result in no grade for the assignment.

Sample Test Run

The following is a sample run of one of the tests in Assignment 4’s Test Bench on ZyBooks. Note: Some recently added error conditions are not included in this run.

1

65536

512

1024

1

65536

1027

16

1

65536

1024

15

1

65537

1026

4096

1

65536

1024

18

1

65536

1024

16

3

65535

14

2

65535

3

65534

512

2

1023

4

Your output

Programming Assignment 4: Cache Simulation

Comp 222 - Fall 2019

Main Menu - Main Memory to Cache Memory Mapping

------------------------------------------------

1) Enter Configuration Parameters

2) Read from Cache

3) Write to Cache

4) Quit Program

Enter selection:

Enter main memory size (words):

Enter cache size (words):

Enter block size (words/block):

*** Error - Block Size is Larger than Cache Size

Main Menu - Main Memory to Cache Memory Mapping

------------------------------------------------

1) Enter Configuration Parameters

2) Read from Cache

3) Write to Cache

4) Quit Program

Enter selection:

Enter main memory size (words):

Enter cache size (words):

Enter block size (words/block):

*** Error - Cache Size is not a Power of 2

Main Menu - Main Memory to Cache Memory Mapping

------------------------------------------------

1) Enter Configuration Parameters

2) Read from Cache

3) Write to Cache

4) Quit Program

Enter selection:

Enter main memory size (words):

Enter cache size (words):

Enter block size (words/block):

*** Error - Block Size is not a Power of 2

Main Menu - Main Memory to Cache Memory Mapping

------------------------------------------------

1) Enter Configuration Parameters

2) Read from Cache

3) Write to Cache

4) Quit Program

Enter selection:

Enter main memory size (words):

Enter cache size (words):

Enter block size (words/block):

*** Error - Main Memory Size is not a Power of 2

Main Menu - Main Memory to Cache Memory Mapping

------------------------------------------------

1) Enter Configuration Parameters

2) Read from Cache

3) Write to Cache

4) Quit Program

Enter selection:

Enter main memory size (words):

Enter cache size (words):

Enter block size (words/block):

*** Error - Cache size is not a multiple of block size

Main Menu - Main Memory to Cache Memory Mapping

------------------------------------------------

1) Enter Configuration Parameters

2) Read from Cache

3) Write to Cache

4) Quit Program

Enter selection:

Enter main memory size (words):

Enter cache size (words):

Enter block size (words/block):

*** All Input Parameters Accepted. Starting to Process Write/Read Requests

Main Menu - Main Memory to Cache Memory Mapping

------------------------------------------------

1) Enter Configuration Parameters

2) Read from Cache

3) Write to Cache

4) Quit Program

Enter selection:

Enter Main Memory Address to Write:

Enter Value to Write:

*** Write Miss - First load block from memory

*** Word 15 of Cache Line 63 with Tag 63 contains the Value 14

Main Menu - Main Memory to Cache Memory Mapping

------------------------------------------------

1) Enter Configuration Parameters

2) Read from Cache

3) Write to Cache

4) Quit Program

Enter selection:

Enter Main Memory Address to Read:

*** Cache Hit

*** Word 15 of Cache Line 63 with Tag 63 contains the Value 14

Main Menu - Main Memory to Cache Memory Mapping

------------------------------------------------

1) Enter Configuration Parameters

2) Read from Cache

3) Write to Cache

4) Quit Program

Enter selection:

Enter Main Memory Address to Write:

Enter Value to Write:

*** Cache Hit

*** Word 14 of Cache Line 63 with Tag 63 contains the Value 512

Main Menu - Main Memory to Cache Memory Mapping

------------------------------------------------

1) Enter Configuration Parameters

2) Read from Cache

3) Write to Cache

4) Quit Program

Enter selection:

Enter Main Memory Address to Read:

Read Miss - First Load Block from Memory

*** Word 15 of Cache Line 63 with Tag 0 contains the Value 64513

Main Menu - Main Memory to Cache Memory Mapping

------------------------------------------------

1) Enter Configuration Parameters

2) Read from Cache

3) Write to Cache

4) Quit Program

Enter selection:

*** Memory Freed Up - Program Terminated Normally

Answer 1

Code Image:

Sample Output:

Code to copy:

#include <cstdio>

#include <cstdlib>

#include <string>

/*Declare a constant variable with value */

const int MEMORY_SIZE = 65536;

/*Declaration of structure cache */

struct userCache

{

//Declare myTag as type of integer

int myTag;

//Declare *useBlock as type of integer

int *useBlock;

};

typedef struct userCache usecache;

/*Declaration of setValues with parameters type as integer*/

void setValues(int*, int*, int*);

/*Declaration of program with no parameters*/

void program();

/*Declaration of display with no parameters*/

void display();

/*Declaration of getValue with parameter type as integer*/

int getValue(const char*);

/*Declaration of initMainMemory with parameter type as integer*/

int *initMainMemory(int);

/*Declaration of initializeCache with parameter type as integer*/

usecache *initializeCache(int);

/*Declaration of freefromCache with parameter type as usecache** and integer*/

void freefromCache(usecache**, int);

//Declaration of writetoCache with parameters type as integer and usecache*

void writetoCache(int*, usecache*, int, int, int);

//Declaration of readfromCache with parameter type as integer and usecache*

void readfromCache(int*, usecache*, int, int, int);

//Declaration of displayContent with parameter type as integer* and integer

void displayContent(int*, int);

/*Implementation Driver code*/

int main()

{

//Declare program amethod

program();

/*Exit from main */

return 0;

}

/*Implementation of setValues method */

void setValues(int *mainMemSize, int *cacheSize, int *blockSize)

{

//Get the value for main memory size

*mainMemSize = getValue("Enter the main memory size (words): ");

//Get the cache size

*cacheSize = getValue("Enter the cache size (words): ");

//Get the block size

*blockSize = getValue("Enter the block size (words/block): ");

//check blockSize is greater than the cacheSize or not

if (*blockSize > *cacheSize) {

//Display statement

printf("*** Error–Block size is larger than cache size\n");

}

//check (*cacheSize % *blockSize) is not equal to 0 or not

else if ((*cacheSize % *blockSize) != 0) {

//Display statement

printf("*** Error–Cache size is not a power of 2\n");

}

else if ((*blockSize % 2 == 0) && (*cacheSize % 2 == 0)) {

//Display statement

printf("*** *** Data Accepted \n");

}

}

/*Implementation of program method */

void program()

{

//Declare choice as type of integer

int choice = 0;

//Declare and initialize mainMemSize with 65536

int mainMemSize = 65536;

//Declare cacheSize,blockSize as integer type and assign values

int cacheSize = 1024, blockSize = 16;

int myTagsValue = mainMemSize / cacheSize;

//Declare *mainMemoryPtr as integer type and assign NULL

int *mainMemoryPtr = NULL;

//Declare *cachePtrVar as integer type and assign NULL

usecache *cachePtrVar = NULL;

/*Initialize memory and assign with values */

mainMemoryPtr = initMainMemory(mainMemSize);

cachePtrVar = initializeCache(cacheSize);

/*iterate the do while loop*/

do

{

/*call display method*/

display();

/*Get the input from user and store in choice*/

choice = getValue("\nEnter selection: ");

/*check choice through the switch loop*/

switch (choice)

{

//if 1 then

case 1:

       //call freefromCache method with parameters &cachePtrVar, myTagsValue

       freefromCache(&cachePtrVar, myTagsValue);

       //call free method with parameters mainMemoryPtr

       free(mainMemoryPtr);

       //call setValues method with parameters &mainMemSize, &cacheSize, &blockSize

       setValues(&mainMemSize, &cacheSize, &blockSize);

       /*Calculate the number of Tags and store in myTagsValue*/

       myTagsValue = mainMemSize / cacheSize;

       mainMemoryPtr = initMainMemory(mainMemSize);

       cachePtrVar = initializeCache(cacheSize);

       break;

//if 2 then

case 2:

       //call readfromCache method with parameters

       //mainMemoryPtr, cachePtrVar, mainMemSize, blockSize, cacheSize

       readfromCache(mainMemoryPtr, cachePtrVar, mainMemSize, blockSize, cacheSize);

       break;

//if 3 then

case 3:

       //call writetoCache method with parameter

       //mainMemoryPtr, cachePtrVar, mainMemSize, blockSize, cacheSize

       writetoCache(mainMemoryPtr, cachePtrVar, mainMemSize, blockSize, cacheSize);

       break;

//if 4 then

case 4:

       break;

default:

       //Display statement

       printf("Invalid selection!\n");

       break;

}

//check choice is not equal to 4

} while (choice != 4);

if (cachePtrVar != NULL)

{

//call freefromCache method with parameters

//&cachePtrVar, myTagsValue

freefromCache(&cachePtrVar, myTagsValue);

}

/*Condition check to whether memory is free or not*/

if (mainMemoryPtr != NULL)

{

//call free method

free(mainMemoryPtr);

}

}

/*Implementation of display mehod*/

void display()

{

//Display statement for menu

printf("\nMain memory to Cache memory mapping: \n");

printf("------------------------------------ \n");

//Display statement for Enter Configuration Parameters

printf("1) Enter Configuration Parameters\n");

//Display statement for Read from cache

printf("2) Read from cache\n");

//Display statement for Write to cache

printf("3) Write to cache\n");

//Display statement for End

printf("4) Quit Program\n");

}

/*Implementation of getValue mehod*/

int getValue(const char *userMsg)

{

//Declare v as type of integer

int v;

//Display statement

printf(userMsg);

scanf_s("%d", &v);

return v;

}

/*Implementation of initMainMemory mehod*/

int* initMainMemory(int size)

{

//Declare and initialize with 0 as integer type 0

int k = 0;

/*Initialize main memory with malloc */

int* ptr = (int*)malloc(size * sizeof(int));

/*Iterate the loop */

for (; k < size; ++k)

{

*(ptr + k) = size - k;

}

//return ptr

return ptr;

}

/* Implementation fo initializeCache method */

usecache* initializeCache(int myTagsValue)

{

//Declare k as type of integer

int k = 0;

usecache* ptr = (usecache*)malloc(myTagsValue * sizeof(usecache));

//Iterate the loop

for (; k < myTagsValue; ++k)

{

ptr[k].myTag = -1;

ptr[k].useBlock = NULL;

}

//return ptr

return ptr;

}

/* Implementation fo freefromCache method */

void freefromCache(usecache **ptr, int size)

{

//Declare k as type of integer

int k = 0;

//Iterate the loop

for (; k < size; ++k)

{

/*check block is not equal */

if ((*ptr)[k].useBlock != NULL)

{

       free((*ptr)[k].useBlock);

}

}

//call free method

free(*ptr);

}

/* Implementation fo writetoCache method */

void writetoCache(int* mainMemoryPtr, usecache* cachePtrVar, int mmSize, int blockSize, int cacheSize)

{

//Declare and initialize variables with type of integer

int address = 0;

//Declare value as type of integer and assign 0

int value = 0;

//Decalre myTag, useBlock, word,j, baseOffset as type of integer

int myTag, useBlock, word,j, baseOffset;

//Declare alreadyMissed as type of integer and assign 0

int alreadyMissed = 0;

/*Get the input from user about the main memory address */

address = getValue("Enter the main memory address to write to: ");

/*Get the input from user about the value to write */

value = getValue("Enter the value to write: ");

/*Calculate the baseOffset */

baseOffset = (address / blockSize) * blockSize;

/*Calculate the myTag */

myTag = address / cacheSize;

/*Calculate the word */

word = address % blockSize;

/*Calculate the useBlock */

useBlock = (address % cacheSize) / blockSize;

/*Assign new value to the mainMemoryPtr*/

mainMemoryPtr[address] = value;

/* if checks tag does not match */

if (cachePtrVar[useBlock].myTag != myTag)

{

//Display statement

printf("*** Write Miss - First Load block from memory\n");

//assign 1 to alreadyMissed

alreadyMissed = 1;

cachePtrVar[useBlock].myTag = myTag;

}

if (cachePtrVar[useBlock].useBlock == NULL)

{

//check alreadyMissed is equal to 0 or not

if (alreadyMissed == 0)

{

       //Display statement

       printf("*** Write Miss - First Load block from memory\n");

}

cachePtrVar[useBlock].useBlock = (int*)malloc(blockSize * sizeof(int));

}

/* Iterate the loop to transfer from the memory to the cache*/

for (j = 0; j < blockSize; ++j)

{

cachePtrVar[useBlock].useBlock[j] = mainMemoryPtr[baseOffset + j];

}

/*Display statement */

printf("*** Block in Cache\n");

/*Display statement */

printf("Word %d of block %d with tag %d have %d\n", word, useBlock, myTag, cachePtrVar[useBlock].useBlock[word]);

}

/*Implementation of readfromCache method */

void readfromCache(int* mainMemoryPtr, usecache* cachePtrVar, int mmSize, int blockSize, int cacheSize)

{

/* Declare and initialize variables with integer type */

int address = 0;

int value = 0;

//Declare useBlock, word,j,baseOffset, myTag ,k as type of integer

int useBlock, word,j,baseOffset, myTag,k;

int alreadyMissed = 0;

/*Ger the input from user */

address = getValue("Enter the main memory address to read from: ");

/*calculate baseOffset */

baseOffset = (address / blockSize) * blockSize;

/*calculate myTag */

myTag = address / cacheSize;

/*calculate word */

word = address % blockSize;

/*calculate useBlock */

useBlock = (address % cacheSize) / blockSize;

if (cachePtrVar[useBlock].myTag != myTag)

{

//Display statement

printf("Read miss- First load block from memory!\n");

alreadyMissed = 1;

cachePtrVar[useBlock].myTag = myTag;

}

if (cachePtrVar[useBlock].useBlock == NULL)

{

//check alreadyMissed is equal to 0 or not

if (alreadyMissed == 0)

{

       //Display statement

       printf("Read miss - First load block from memory!\n");

}

cachePtrVar[useBlock].useBlock = (int*)malloc(blockSize * sizeof(int));

}

/*Iterate the loop to get from the main memory */

for (k = 0; k < blockSize; ++k)

{

cachePtrVar[useBlock].useBlock[k] = mainMemoryPtr[baseOffset + k];

}

//Display satement

printf("Word %d of block %d with tag %d have %d\n", word, useBlock, myTag, cachePtrVar[useBlock].useBlock[word]);

}

/*Implementation of displayContent method */

void displayContent(int* ptr, int size)

{

//Declare j as type of integer

int k = 0;

//Iterate the loop

for (; k < size; ++k)

{

//Display statement

printf("%d, ", ptr[k]);

}

}