Cache-Simulator
Schreibe ich einen cache-simulator. Die Idee ist, gegeben eine Eingabe-Datei mit den Befehlen, verfolgen Sie die Ergebnisse der input-Simulation von cache-Funktionen, so dass wir den überblick behalten können cache-hits und-misses. Ich habe geschrieben das folgenden code, aber scheint zu sein, Schwierigkeiten haben, den richtigen Ausgang. Ich bin Entsendung meine ganze code, weil ich will nicht mit Vermutungen, wo das problem liegen kann. Kann mir jemand sagen, wo ich bin, einen Fehler zu machen?
#include <stdlib.h>
#include <stdio.h>
#include <getopt.h>
#include <strings.h>
#include "cachelab.h"
/* Always use a 64-bit variable to hold memory addresses*/
typedef unsigned long long int mem_addr_t;
/* a struct that groups cache parameters together */
typedef struct {
int s; /* 2**s cache sets */
int b; /* cacheline block size 2**b bytes */
int E; /* number of cachelines per set */
int S; /* number of sets, derived from S = 2**s */
int B; /* cacheline block size (bytes), derived from B = 2**b */
} cache_param_t;
int verbosity;
/*
* printUsage - Print usage info
*/
void printUsage(char* argv[])
{
printf("Usage: %s [-hv] -s <num> -E <num> -b <num> -t <file>\n", argv[0]);
printf("Options:\n");
printf(" -h Print this help message.\n");
printf(" -v Optional verbose flag.\n");
printf(" -s <num> Number of set index bits.\n");
printf(" -E <num> Number of lines per set.\n");
printf(" -b <num> Number of block offset bits.\n");
printf(" -t <file> Trace file.\n");
printf("\nExamples:\n");
printf(" %s -s 4 -E 1 -b 4 -t traces/yi.trace\n", argv[0]);
printf(" %s -v -s 8 -E 2 -b 4 -t traces/yi.trace\n", argv[0]);
exit(0);
}
int main(int argc, char **argv)
{
cache_param_t par;
bzero(&par, sizeof(par));
char *trace_file;
char c;
while( (c=getopt(argc,argv,"s:E:b:t:vh")) != -1){
switch(c){
case 's':
par.s = atoi(optarg);
break;
case 'E':
par.E = atoi(optarg);
break;
case 'b':
par.b = atoi(optarg);
break;
case 't':
trace_file = optarg;
break;
case 'v':
verbosity = 1;
break;
case 'h':
printUsage(argv);
exit(0);
default:
printUsage(argv);
exit(1);
}
}
if (par.s == 0 || par.E == 0 || par.b == 0 || trace_file == NULL) {
printf("%s: Missing required command line argument\n", argv[0]);
printUsage(argv);
exit(1);
}
/* TODO: Compute S and B based on information passed in */
//Compute S and B, 2^s and 2^b respectively
par.S = (1 << par.s);
par.B = (1 << par.b);
/* TODO: Initialize a cache */
//Structure for a line
typedef struct {
int valid;
mem_addr_t tag;
int timestamp;
} line_st;
//Structure for a set; a pointer to an array of lines
typedef struct {
line_st *lines;
} cache_set;
//Structure for a cache; a pointer to an array of sets
typedef struct {
cache_set *sets;
} cache_t;
//allocate space for sets and for lines
cache_t cache;
cache.sets = malloc(par.S * sizeof(cache_set));
for (int i = 0; i < par.S; i++) {
cache.sets[i].lines = malloc(sizeof(line_st) * par.E);
}
//counters
int hit_count = 0;
int miss_count = 0;
int eviction_count = 0;
/* TODO: Run the trace simulation */
char act; //L,S,M
int size; //size read in from file
int TSTAMP = 0; //value for LRU
int empty = -1; //index of empty space
int H = 0; //is there a hit
int E = 0; //is there an eviction
int toEvict = 0; //keeps track of what to evict
mem_addr_t addr;
//open the file and read it in
FILE * traceFile = fopen(trace_file, "r");
if (traceFile != NULL) {
//keep going while we have additional lines
//while(feof(traceFile) == 0) {
while(fscanf(traceFile, " %c %llx,%d", &act, &addr, &size) == 3){
if (act != 'I') {
//read the next line and look for string formated as " %c %llx,%d"
//sscanf(traceFile, " %c %llx,%d", &act, &addr, &size);
//fscanf(traceFile, " %c %llx,%d", &act, &addr, &size);
//calculate address tag and set index
mem_addr_t addr_tag = addr >> (par.s + par.b);
int tag_size = (64 - (par.s + par.b));
unsigned long long temp = addr << (tag_size);
unsigned long long setid = temp >> (tag_size + par.b);
//unsigned long long setid = ((addr >> par.b) & (par.S - 1));
cache_set set = cache.sets[setid];
int low = par.E + 1;
for(int e = 0; e < par.E; e++) {
if (set.lines[e].valid == 0) {
empty = e;
}
else if (set.lines[e].valid == 1){
if (TSTAMP < low) {
low = TSTAMP;
toEvict = e;
}
if (set.lines[e].tag == addr_tag) {
hit_count++;
H = 1;
set.lines[e].timestamp = TSTAMP;
TSTAMP++;
}
}
}
//if we have a miss
if (H != 1){
miss_count++;
//if we have an empty line
if (empty > -1) {
set.lines[empty].valid = 1;
set.lines[empty].tag = addr_tag;
set.lines[empty].timestamp = TSTAMP;
TSTAMP++;
}
//if the set is full we need to evict
else if (empty < 0) {
E = 1;
set.lines[toEvict].tag = addr_tag;
set.lines[toEvict].timestamp = TSTAMP;
eviction_count++;
}
}
//if the instruction is M, we will always get a hit
if (act == 'M') {
hit_count++;
}
//if the -v flag is set print out all debug information
if (verbosity == 1) {
printf("%c ", act);
//printf("%llx,%d ", addr_tag, setid);
printf("%llx,%d ", addr, size);
if (H == 1) {
printf("Hit ");
}
else if (H != 1) {
printf("Miss ");
}
if (E == 1) {
printf("Eviction ");
}
if (act == 'M') {
printf("Hit ");
}
printf("\n");
}
empty = -1;
H = 0;
E = 0;
}
}
}
/* TODO: Clean up cache resources */
/* TODO: Print out real results */
printSummary(hit_count, miss_count, eviction_count);
return 0;
}
Ich bin mit meinem code, mit dem folgenden Beispiel für die Eingabe:
S 00600aa0,1
S 7ff000384,4
L 7ff000384,4
L 7ff000384,4
L 00600a20,4
L 7ff000384,4
Mein code erzeugt das folgende Ergebnis:
./ -v -s 2 -E 2 -b 3 -t traces/test.trace
S 600aa0,1 Miss
S 7ff000384,4 Miss
L 7ff000384,4 Hit
L 7ff000384,4 Hit
L 600a20,4 Miss Eviction
L 7ff000384,4 Miss Eviction
hits:2 misses:4 evictions:2
aber das ist, was er produzieren sollte:
./ -v -s 2 -E 2 -b 3 -t traces/test.trace
S 600aa0,1 miss
S 7ff000384,4 miss
L 7ff000384,4 hit
L 7ff000384,4 hit
L 600a20,4 miss eviction
L 7ff000384,4 hit
hits:3 misses:3 evictions:1
Kann mir jemand sagen, was ich falsch mache?
EDIT:
Zweiten test-Datei:
S 00600aa0,1
I 004005b6,5
I 004005bb,5
I 004005c0,5
S 7ff000398,8
I 0040051e,1
S 7ff000390,8
I 0040051f,3
I 00400522,4
S 7ff000378,8
I 00400526,4
S 7ff000370,8
I 0040052a,7
S 7ff000384,4
I 00400531,2
I 00400581,4
L 7ff000384,4
I 00400585,2
I 00400533,7
S 7ff000388,4
I 0040053a,2
I 00400577,4
L 7ff000388,4
I 0040057b,2
I 0040053c,3
L 7ff000384,4
I 0040053f,2
I 00400541,4
I 00400545,3
I 00400548,4
L 7ff000378,8
I 0040054c,3
L 7ff000388,4
I 0040054f,2
I 00400551,3
L 00600a20,4
I 00400554,3
S 7ff00038c,4
I 00400557,3
L 7ff000388,4
I 0040055a,2
I 0040055c,4
I 00400560,3
I 00400563,4
L 7ff000370,8
I 00400567,3
L 7ff000384,4
I 0040056a,3
I 0040056d,3
L 7ff00038c,4
I 00400570,3
S 00600a60,4
I 00400573,4
M 7ff000388,4
I 00400577,4
L 7ff000388,4
I 0040057b,2
I 0040053c,3
L 7ff000384,4
I 0040053f,2
I 00400541,4
I 00400545,3
I 00400548,4
L 7ff000378,8
I 0040054c,3
L 7ff000388,4
I 0040054f,2
I 00400551,3
L 00600a24,4
I 00400554,3
S 7ff00038c,4
I 00400557,3
L 7ff000388,4
I 0040055a,2
I 0040055c,4
I 00400560,3
I 00400563,4
L 7ff000370,8
I 00400567,3
L 7ff000384,4
I 0040056a,3
I 0040056d,3
L 7ff00038c,4
I 00400570,3
S 00600a70,4
I 00400573,4
M 7ff000388,4
I 00400577,4
L 7ff000388,4
I 0040057b,2
I 0040053c,3
L 7ff000384,4
I 0040053f,2
I 00400541,4
I 00400545,3
I 00400548,4
L 7ff000378,8
I 0040054c,3
L 7ff000388,4
I 0040054f,2
I 00400551,3
L 00600a28,4
I 00400554,3
S 7ff00038c,4
I 00400557,3
L 7ff000388,4
I 0040055a,2
I 0040055c,4
I 00400560,3
I 00400563,4
L 7ff000370,8
I 00400567,3
L 7ff000384,4
I 0040056a,3
I 0040056d,3
L 7ff00038c,4
I 00400570,3
S 00600a80,4
I 00400573,4
M 7ff000388,4
I 00400577,4
L 7ff000388,4
I 0040057b,2
I 0040053c,3
L 7ff000384,4
I 0040053f,2
I 00400541,4
I 00400545,3
I 00400548,4
L 7ff000378,8
I 0040054c,3
L 7ff000388,4
I 0040054f,2
I 00400551,3
L 00600a2c,4
I 00400554,3
S 7ff00038c,4
I 00400557,3
L 7ff000388,4
I 0040055a,2
I 0040055c,4
I 00400560,3
I 00400563,4
L 7ff000370,8
I 00400567,3
L 7ff000384,4
I 0040056a,3
I 0040056d,3
L 7ff00038c,4
I 00400570,3
S 00600a90,4
I 00400573,4
M 7ff000388,4
I 00400577,4
L 7ff000388,4
I 0040057b,2
I 0040057d,4
M 7ff000384,4
I 00400581,4
L 7ff000384,4
I 00400585,2
I 00400533,7
S 7ff000388,4
I 0040053a,2
I 00400577,4
L 7ff000388,4
I 0040057b,2
I 0040053c,3
L 7ff000384,4
I 0040053f,2
I 00400541,4
I 00400545,3
I 00400548,4
L 7ff000378,8
I 0040054c,3
L 7ff000388,4
I 0040054f,2
I 00400551,3
L 00600a30,4
I 00400554,3
S 7ff00038c,4
I 00400557,3
L 7ff000388,4
I 0040055a,2
I 0040055c,4
I 00400560,3
I 00400563,4
L 7ff000370,8
I 00400567,3
L 7ff000384,4
I 0040056a,3
I 0040056d,3
L 7ff00038c,4
I 00400570,3
S 00600a64,4
I 00400573,4
M 7ff000388,4
I 00400577,4
L 7ff000388,4
I 0040057b,2
I 0040053c,3
L 7ff000384,4
I 0040053f,2
I 00400541,4
I 00400545,3
I 00400548,4
L 7ff000378,8
I 0040054c,3
L 7ff000388,4
I 0040054f,2
I 00400551,3
L 00600a34,4
I 00400554,3
S 7ff00038c,4
I 00400557,3
L 7ff000388,4
I 0040055a,2
I 0040055c,4
I 00400560,3
I 00400563,4
L 7ff000370,8
I 00400567,3
L 7ff000384,4
I 0040056a,3
I 0040056d,3
L 7ff00038c,4
I 00400570,3
S 00600a74,4
I 00400573,4
M 7ff000388,4
I 00400577,4
L 7ff000388,4
I 0040057b,2
I 0040053c,3
L 7ff000384,4
I 0040053f,2
I 00400541,4
I 00400545,3
I 00400548,4
L 7ff000378,8
I 0040054c,3
L 7ff000388,4
I 0040054f,2
I 00400551,3
L 00600a38,4
I 00400554,3
S 7ff00038c,4
I 00400557,3
L 7ff000388,4
I 0040055a,2
I 0040055c,4
I 00400560,3
I 00400563,4
L 7ff000370,8
I 00400567,3
L 7ff000384,4
I 0040056a,3
I 0040056d,3
L 7ff00038c,4
I 00400570,3
S 00600a84,4
I 00400573,4
M 7ff000388,4
I 00400577,4
L 7ff000388,4
I 0040057b,2
I 0040053c,3
L 7ff000384,4
I 0040053f,2
I 00400541,4
I 00400545,3
I 00400548,4
L 7ff000378,8
I 0040054c,3
L 7ff000388,4
I 0040054f,2
I 00400551,3
L 00600a3c,4
I 00400554,3
S 7ff00038c,4
I 00400557,3
L 7ff000388,4
I 0040055a,2
I 0040055c,4
I 00400560,3
I 00400563,4
L 7ff000370,8
I 00400567,3
L 7ff000384,4
I 0040056a,3
I 0040056d,3
L 7ff00038c,4
I 00400570,3
S 00600a94,4
I 00400573,4
M 7ff000388,4
I 00400577,4
L 7ff000388,4
I 0040057b,2
I 0040057d,4
M 7ff000384,4
I 00400581,4
L 7ff000384,4
I 00400585,2
I 00400533,7
S 7ff000388,4
I 0040053a,2
I 00400577,4
L 7ff000388,4
I 0040057b,2
I 0040053c,3
L 7ff000384,4
I 0040053f,2
I 00400541,4
I 00400545,3
I 00400548,4
L 7ff000378,8
I 0040054c,3
L 7ff000388,4
I 0040054f,2
I 00400551,3
L 00600a40,4
I 00400554,3
S 7ff00038c,4
I 00400557,3
L 7ff000388,4
I 0040055a,2
I 0040055c,4
I 00400560,3
I 00400563,4
L 7ff000370,8
I 00400567,3
L 7ff000384,4
I 0040056a,3
I 0040056d,3
L 7ff00038c,4
I 00400570,3
S 00600a68,4
I 00400573,4
M 7ff000388,4
I 00400577,4
L 7ff000388,4
I 0040057b,2
I 0040053c,3
L 7ff000384,4
I 0040053f,2
I 00400541,4
I 00400545,3
I 00400548,4
L 7ff000378,8
I 0040054c,3
L 7ff000388,4
I 0040054f,2
I 00400551,3
L 00600a44,4
I 00400554,3
S 7ff00038c,4
I 00400557,3
L 7ff000388,4
I 0040055a,2
I 0040055c,4
I 00400560,3
I 00400563,4
L 7ff000370,8
I 00400567,3
L 7ff000384,4
I 0040056a,3
I 0040056d,3
L 7ff00038c,4
I 00400570,3
S 00600a78,4
I 00400573,4
M 7ff000388,4
I 00400577,4
L 7ff000388,4
I 0040057b,2
I 0040053c,3
L 7ff000384,4
I 0040053f,2
I 00400541,4
I 00400545,3
I 00400548,4
L 7ff000378,8
I 0040054c,3
L 7ff000388,4
I 0040054f,2
I 00400551,3
L 00600a48,4
I 00400554,3
S 7ff00038c,4
I 00400557,3
L 7ff000388,4
I 0040055a,2
I 0040055c,4
I 00400560,3
I 00400563,4
L 7ff000370,8
I 00400567,3
L 7ff000384,4
I 0040056a,3
I 0040056d,3
L 7ff00038c,4
I 00400570,3
S 00600a88,4
I 00400573,4
M 7ff000388,4
I 00400577,4
L 7ff000388,4
I 0040057b,2
I 0040053c,3
L 7ff000384,4
I 0040053f,2
I 00400541,4
I 00400545,3
I 00400548,4
L 7ff000378,8
I 0040054c,3
L 7ff000388,4
I 0040054f,2
I 00400551,3
L 00600a4c,4
I 00400554,3
S 7ff00038c,4
I 00400557,3
L 7ff000388,4
I 0040055a,2
I 0040055c,4
I 00400560,3
I 00400563,4
L 7ff000370,8
I 00400567,3
L 7ff000384,4
I 0040056a,3
I 0040056d,3
L 7ff00038c,4
I 00400570,3
S 00600a98,4
I 00400573,4
M 7ff000388,4
I 00400577,4
L 7ff000388,4
I 0040057b,2
I 0040057d,4
M 7ff000384,4
I 00400581,4
L 7ff000384,4
I 00400585,2
I 00400533,7
S 7ff000388,4
I 0040053a,2
I 00400577,4
L 7ff000388,4
I 0040057b,2
I 0040053c,3
L 7ff000384,4
I 0040053f,2
I 00400541,4
I 00400545,3
I 00400548,4
L 7ff000378,8
I 0040054c,3
L 7ff000388,4
I 0040054f,2
I 00400551,3
L 00600a50,4
I 00400554,3
S 7ff00038c,4
I 00400557,3
L 7ff000388,4
I 0040055a,2
I 0040055c,4
I 00400560,3
I 00400563,4
L 7ff000370,8
I 00400567,3
L 7ff000384,4
I 0040056a,3
I 0040056d,3
L 7ff00038c,4
I 00400570,3
S 00600a6c,4
I 00400573,4
M 7ff000388,4
I 00400577,4
L 7ff000388,4
I 0040057b,2
I 0040053c,3
L 7ff000384,4
I 0040053f,2
I 00400541,4
I 00400545,3
I 00400548,4
L 7ff000378,8
I 0040054c,3
L 7ff000388,4
I 0040054f,2
I 00400551,3
L 00600a54,4
I 00400554,3
S 7ff00038c,4
I 00400557,3
L 7ff000388,4
I 0040055a,2
I 0040055c,4
I 00400560,3
I 00400563,4
L 7ff000370,8
I 00400567,3
L 7ff000384,4
I 0040056a,3
I 0040056d,3
L 7ff00038c,4
I 00400570,3
S 00600a7c,4
I 00400573,4
M 7ff000388,4
I 00400577,4
L 7ff000388,4
I 0040057b,2
I 0040053c,3
L 7ff000384,4
I 0040053f,2
I 00400541,4
I 00400545,3
I 00400548,4
L 7ff000378,8
I 0040054c,3
L 7ff000388,4
I 0040054f,2
I 00400551,3
L 00600a58,4
I 00400554,3
S 7ff00038c,4
I 00400557,3
L 7ff000388,4
I 0040055a,2
I 0040055c,4
I 00400560,3
I 00400563,4
L 7ff000370,8
I 00400567,3
L 7ff000384,4
I 0040056a,3
I 0040056d,3
L 7ff00038c,4
I 00400570,3
S 00600a8c,4
I 00400573,4
M 7ff000388,4
I 00400577,4
L 7ff000388,4
I 0040057b,2
I 0040053c,3
L 7ff000384,4
I 0040053f,2
I 00400541,4
I 00400545,3
I 00400548,4
L 7ff000378,8
I 0040054c,3
L 7ff000388,4
I 0040054f,2
I 00400551,3
L 00600a5c,4
I 00400554,3
S 7ff00038c,4
I 00400557,3
L 7ff000388,4
I 0040055a,2
I 0040055c,4
I 00400560,3
I 00400563,4
L 7ff000370,8
I 00400567,3
L 7ff000384,4
I 0040056a,3
I 0040056d,3
L 7ff00038c,4
I 00400570,3
S 00600a9c,4
I 00400573,4
M 7ff000388,4
I 00400577,4
L 7ff000388,4
I 0040057b,2
I 0040057d,4
M 7ff000384,4
I 00400581,4
L 7ff000384,4
I 00400585,2
I 00400587,1
L 7ff000390,8
I 00400588,1
L 7ff000398,8
I 004005c5,7
L 00600aa0,1
Erwartete Werte:
My simulator Reference simulator
(s,E,b) Hits Misses Evicts Hits Misses Evicts
(2,2,3) 196 42 34 201 37 29
(2,4,3) 208 30 14 212 26 10
InformationsquelleAutor Lesha | 2014-04-15
Du musst angemeldet sein, um einen Kommentar abzugeben.
Knifflige Fehler gibt. Ich habe die for-Schleife in der Mitte, um nur gesetzt
empty
wenn es bereits -1, so wird die erste leere Stelle gefunden wird, dann wird es nicht wieder ändern, sobald es gefunden hat, eine leere Stelle. Ich auch geändert-Initialisierunglow
werden INT_MAX und sucht das echte zuletzt benutzt, indem Sie die relevantenelse
Bedingungen. Ich auch neu bestellt, der code für ein Spiel VOR der Suche nach der Räumung Kandidaten, da die Suche nach einem match erfrischt die cache-timestamp. Sie hatte auch vergessen zu erhöhen TSTAMP im Falle eines Miss Räumung.Meine Ergebnisse:
Seltsam genug, selbst wenn Sie Ihre gesamte Datei bin ich immer das alte Ergebnis und nicht das, was erwartet wird. Ist es möglich, dass einige Umwelt-Differenz ist dieses problem verursacht?
Ich änderte die Reihenfolge der letzten beiden Zeilen in der Eingabe und das problem verschwand. Ich denke, die erste "Miss Vertreibung" irgendwie bewirkt, dass eine zweite. Jede Idee, was könnte die Ursache sein?
Ich habe die änderungen gemacht, wie Sie empfohlen. Es funktioniert für dieses Beispiel Eingang aber einmal ausführen, mit verschiedenen sample-input reports falsch zählt. Die Daten zu schreiben, manchmal schreibt "Miss Räumung Treffer", das ist nicht möglich und ich nehme an, der den Fehler verursacht. Irgendeine Idee, wie man dieses Problem lösen?
Ich aktualisiert meine version des Codes, ein paar bug-fixes. Bitte Lesen Sie nochmals meinen Kommentar, bevor Sie den code, und suchen Sie nach dem tag "VERÄNDERT" in den code für die Bereiche geändert.
InformationsquelleAutor JohnH