-
Notifications
You must be signed in to change notification settings - Fork 0
/
DirectMappedCache.c
316 lines (269 loc) · 12.3 KB
/
DirectMappedCache.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#define CACHESIZE 16
#define INDEX 4
struct cache{
unsigned int address;
char state;
unsigned int timer;
};
struct cache myCache[CACHESIZE];
enum values { VALID = 0, INVALID, EMPTY};
/**********************************************************************/
/* Name: getAddr */
/* */
/* Description: This function will read the input file and return a */
/* decimal number. It will skip over comments, which */
/* begin the line with a # */
/* */
/* Inputs: The name of the input file */
/* */
/* Outputs: The address that will be presented to the cache */
/**********************************************************************/
unsigned int getAddr(FILE *fp){
char c; /* Character read */
unsigned int address;
do {
c = getc(fp); /* Get next character */
if(c == '#') /* Skip the comment */
do {
c = getc(fp);
} while(c != '\n');
} while(!isxdigit(c) && !feof(fp));
ungetc(c, fp); /* Return the character to the file */
fscanf(fp, "%x\n", &address);
return (address);
}
/**********************************************************************/
/* Name: decimalToBinary */
/* */
/* Description: This function will transform an address or a number */
/* in decimal format into binary format */
/* */
/* Inputs: An array; An address or number in decimal format */
/* */
/* Outputs: A number in binary format */
/**********************************************************************/
void decimalToBinary(int binaryIndex[], int address){
int i = INDEX - 1;
while(i >= 0){
binaryIndex[i] = address % 2;
i--;
address = address/2;
}
}
/**********************************************************************/
/* Name: cacheAccess */
/* */
/* Description: This function will simulate a direct mapped cache */
/* */
/* Inputs: An address in decimal format */
/* */
/* Outputs: The number of hits */
/**********************************************************************/
int cacheAccess(unsigned int address){
static unsigned int hit = 0;
static unsigned int timer = 0;
/* Declare an array with the last 4 binary digits of the address*/
int binaryIndex[INDEX];
/* Call decimalToBinary() to initialise binaryIndex[]; pass array name, itself a pointer and
the self address in order to get the last 4 binary digits*/
decimalToBinary(binaryIndex, address);
/* Get the index of the cache where the address it is going to be allocated */
int i = -1;
int found = -1;
while((i < CACHESIZE)&&(found != 0)){
i++;
/* Declare a temporal array*/
int temp[INDEX];
/* Create a temporal array with the number of the entry*/
decimalToBinary(temp, i);
/* Compare the last 4 binary digits of the address with the cache entrys */
found = memcmp(temp, binaryIndex, sizeof(temp));
}
/* Check the state of the cache entry; if the entry is not valid, change the state
and store the address of the entry */
if(myCache[i].state == INVALID){
myCache[i].state = VALID;
myCache[i].address = address;
}
else{
/* If the contents pairs, increase the number of hits*/
if(myCache[i].address == address)
hit++;
else
myCache[i].address = address; /* If the content does not
pair, replace the old address with the new one*/
}
/* Timer Assignation; increase it over timer*/
myCache[i].timer = timer;
timer++;
return hit;
}
/**********************************************************************/
/* Name: decimalToHex */
/* */
/* Description: This function will transform an address or a number */
/* in decimal format into hexadecimal format */
/* */
/* Inputs: An array; An address in decimal format */
/* */
/* Outputs: An address in hexadecimal format */
/**********************************************************************/
void decimalToHex(int hexAddress[], int address){
int i = INDEX;
/* The last digit is ignored, instead a zero is placed at the begining of the
number, due to the fact that the entry in which is contained, already
gives the information that we need from the last digit*/
hexAddress[0] = 0;
while(i > 0){
hexAddress[i] = address % 16;
i--;
address = address/16;
}
}
/**********************************************************************/
/* Name: entries */
/* */
/* Description: This function will print the first column of the */
/* cache, which basically is the entry number */
/* */
/* Inputs: An integer counter */
/* */
/* Outputs: NONE */
/**********************************************************************/
void entries(int i){
/* Declare a temporal array*/
int temp[INDEX];
/* Create an array with only 0's*/
for(int j = 0; j < INDEX; j++)
temp[j] = 0;
/* Print over the same line as the 0's array depending on the length of the entry number*/
for(int j = 0; j < INDEX; j++)
printf("%d", temp[j]);
if(i < 10)
printf("\b%d", i);
else if(i < 100)
printf("\b\b%d", i);
else if(i < 1000)
printf("\b\b\b%d", i);
else if(i < 10000)
printf("\b\b\b\b%d", i);
}
/**********************************************************************/
/* Name: header */
/* */
/* Description: This function will print the header structure of the */
/* table which presents the information of the cache */
/* */
/* Inputs: NONE */
/* */
/* Outputs: NONE */
/**********************************************************************/
void header(){
printf("-----------------------------------------\n| DIRECT MAPPED CACHE |\n| |\n-----------------------------------------\n");
printf("| ENTRY | ADDRESS | STATUS | LAST USED |\n");
printf("-----------------------------------------\n");
}
/**********************************************************************/
/* Name: cacheStatistics */
/* */
/* Description: This function will print the number hits, misses and */
/* and the hit rate */
/* */
/* Inputs: The number of hits, misses, and the hit rate */
/* */
/* Outputs: NONE */
/**********************************************************************/
void cacheStatistics(int hits, int events, float hitRate){
printf("-----------------------------------------\n");
printf("| HITS | MISSES | HIT RATE |\n");
printf("-----------------------------------------\n");
printf("| %2d | %2d | p = %.6f |\n", hits, events-hits, hitRate);
printf("-----------------------------------------\n\n");
}
/**********************************************************************/
/* Name: printCache */
/* */
/* Description: This function will build and print all the */
/* information about the cache */
/* */
/* Inputs: NONE */
/* */
/* Outputs: NONE */
/**********************************************************************/
void printCache(){
header(); /* Print the basic header of the table*/
for(int i = 0; i < CACHESIZE; i++){
printf("| ");
entries(i); /* Print the entry (first) column*/
printf(" | ");
/* Load the address of the entry*/
int address = myCache[i].address;
/* Declare an array that will contain the address in hex format */
int hexAddress[INDEX];
/* Call decimalToHex() to initialise hexAddress[]; pass array name, itself a pointer and
the self address in decimal format*/
decimalToHex(hexAddress, address);
/* Print the address (second) column*/
for(int j = 0; j < INDEX; j++){
switch(hexAddress[j]){
case 10:
printf("A");
break;
case 11:
printf("B");
break;
case 12:
printf("C");
break;
case 13:
printf("D");
break;
case 14:
printf("E");
break;
case 15:
printf("F");
break;
default :
printf("%d", hexAddress[j]);
}
}
/* Print the state (third) column*/
if(myCache[i].state == VALID)
printf(" | VALID |");
else
printf(" | INVALID |");
/* Print the "last used" (fourth) column*/
printf(" %8d |\n", myCache[i].timer);
}
/* Print the last border of the table*/
printf("-----------------------------------------\n\n");
}
int main(){
unsigned int events = 0;
static unsigned int hit = 0;
FILE *fp; /* Pointer to the input file */
unsigned int ref;
/* Initialize the cache */
for (int i = 0; i < CACHESIZE; i++){
myCache[i].state = INVALID;
myCache[i].address = EMPTY;
}
fp = fopen("trace.txt", "r"); /* Open file for read operation */
while(!feof(fp)){
ref = getAddr(fp);
hit = cacheAccess(ref);
events++;
}
/* Print the cache final state & information*/
system("cls");
printCache();
float hitRate = (hit/(float)events);
/* Print the cache statistics*/
cacheStatistics(hit, events, hitRate);
system("pause");
}