#include #include #include #include #include // Just use 4 byte pointers // Not a bad assumption on 64 bit machines as pages won't exceed this, and for // simple tests, most of main memory is within a single data page. typedef unsigned int ptr_t; typedef unsigned int uint; inline uint ilog2(uint v) { return ((v & 0xAAAAAAAA) != 0) | ((v & 0xFFFF0000) != 0) << 4 | ((v & 0xFF00FF00) != 0) << 3 | ((v & 0xF0F0F0F0) != 0) << 2 | ((v & 0xCCCCCCCC) != 0) << 1; } inline bool ispow2(uint n) { return n && !(n & (n - 1)); } class cache { ptr_t* _tags; uint* _lastaccess; uint _blockshift; uint _tagshift; public: const uint blocksize; const uint size; const uint associativity; const uint wordsize; const uint blocks; const uint hittime; const uint misstime; int hits; int misses; int accesses; cache(uint blocksize_words, uint size_bytes, uint assoc, uint wordsize_bytes) : blocksize(blocksize_words) , size(size_bytes) , associativity(assoc) , wordsize(wordsize_bytes) , blocks(size_bytes / assoc / blocksize_words / wordsize_bytes) , hittime(assoc * 2 + 8) , misstime(blocksize_words * 10 + 100) // Looks like how dept. does it , hits(0), misses(0), accesses(0) { if (!ispow2(size) || !ispow2(blocks) || !ispow2(wordsize_bytes)) { throw std::invalid_argument("Size/blocks/words must be powers of 2."); } _tags = new ptr_t[blocks * associativity]; _lastaccess = new uint[blocks * associativity]; // Does new zero memory? for (int i = 0; i < blocks * associativity; i++) { _lastaccess[i] = 0; _tags[i] = 0; } _blockshift = ilog2(wordsize * blocksize); _tagshift = ilog2(wordsize * blocksize * blocks); } ~cache() { delete _tags; delete _lastaccess; }; // Simulate accessing an address bool access(ptr_t addr) { // set = block*associativity for tags array int set = ((addr >> _blockshift) % blocks) * associativity; ptr_t tag = addr >> _tagshift; accesses++; int a = 0; for (a; a < associativity; a++) { if (tag == _tags[set + a] && _lastaccess[set + a]) { // Cache hit hits++; _lastaccess[set + a] = accesses; return true; } } // Miss, add to cache misses++; int lru = 0x7FFFFFFF; int lrua = 0; // Check for empty sets for (a = 0; a < associativity; a++) { if (!_lastaccess[set + a]) { // Empty set _lastaccess[set + a] = accesses; _tags[set + a] = tag; return false; } if (_lastaccess[set + a] < lru) { lru = _lastaccess[set + a]; lrua = a; } } // No empty sets, remove lru. _lastaccess[set + lrua] = accesses; _tags[set + lrua] = tag; return false; } }; void runprogram(const char* program) { std::stringstream iss; iss << "\"" << program << ".exe\" > \"" << program << "_cachedata.bin\""; // std::cout << iss.str() << std::endl; // TODO: Doesn't work? // system(iss.str().c_str()); } std::vector readdata(const char* program) { std::stringstream iss; iss << program << "_cachedata.bin"; std::ifstream input(iss.str().c_str(), std::ios::binary ); if (!input) { std::cerr << "Error opening file." << std::endl; } std::vector buffer; ptr_t t; while (input) { input.read((char*)&t, sizeof(t)); buffer.push_back(t); } buffer.pop_back(); return buffer; } void cachesim(cache& c, std::vector& data) { for (ptr_t addr : data) { c.access(addr); } } struct TEST { int blocksize; int size; int assoc; }; void runtests(const char* program, TEST* tests, int testc, int wordsize) { runprogram(program); std::vector data = readdata(program); std::stringstream iss; iss << program << "_results.csv"; std::ofstream results(iss.str()); results << "Cache Size\tBlock Size\tAssociativity\tNumber of sets\t" "Number of blocks\tHit time\tMiss penalty time\t" "Accesses\tHits\tMisses\n"; for (int t = 0; t < testc; t++) { cache c(tests[t].blocksize, tests[t].size, tests[t].assoc, wordsize); cachesim(c, data); results << tests[t].size << "\t" << tests[t].blocksize << "\t" << tests[t].assoc << "\t" << tests[t].assoc*c.blocks << "\t" << c.blocks << "\t" << c.hittime << "\t" << c.misstime << "\t" << c.accesses << "\t" << c.hits << "\t" << c.misses << "\n"; } } int main(int argc, char const *argv[]) { int blocksize = 1; int size = 4096; int wordsize = 4; int assoc = 1; bool test = false; bool histogram_test = false; const char* program = ""; for (int i = 1; i < argc; i++) { if (*argv[i] == '-') { // Command line option switch (argv[i][1]) { case 'b': // Block size blocksize = atoi(&argv[i][2]); break; case 's': // cache size size = atoi(&argv[i][2]); break; case 'w': // word size wordsize = atoi(&argv[i][2]); break; case 'a': // assoc assoc = atoi(&argv[i][2]); break; case 't': // test test = true; break; case 'h': // test histogram_test = true; break; default: std::cout << "Unexpected commend line argument " << argv[i] << std::endl; break; } } else { // Program? if (*program == '\0') { // Set program program = argv[i]; } else { std::cout << "Unexpected command line argument " << argv[i] << std::endl; } } } if (program[0] == '\0') { std::cout << "Program required" << std::endl; return 1; } if (histogram_test) { TEST test[15] = { {1, 128, 1}, {2, 128, 1}, {4, 128, 1}, {8, 128, 1}, {16, 128, 1}, {32, 128, 1}, {1, 128, 2}, {2, 128, 2}, {4, 128, 2}, {8, 128, 2}, {16, 128, 2}, {1, 128, 4}, {2, 128, 4}, {4, 128, 4}, {8, 128, 4}, }; runtests(program, test, 15, wordsize); } else if (test) { TEST test[20] = { {1, 4 * 1024, assoc}, {2, 4 * 1024, assoc}, {4, 4 * 1024, assoc}, {8, 4 * 1024, assoc}, {1, 8 * 1024, assoc}, {2, 8 * 1024, assoc}, {4, 8 * 1024, assoc}, {8, 8 * 1024, assoc}, {1, 16 * 1024, assoc}, {2, 16 * 1024, assoc}, {4, 16 * 1024, assoc}, {8, 16 * 1024, assoc}, {1, 32 * 1024, assoc}, {2, 32 * 1024, assoc}, {4, 32 * 1024, assoc}, {8, 32 * 1024, assoc}, {1, 64 * 1024, assoc}, {2, 64 * 1024, assoc}, {4, 64 * 1024, assoc}, {8, 64 * 1024, assoc} }; runtests(program, test, 20, wordsize); } else { cache c(blocksize, size, assoc, wordsize); std::cout << "Block size: " << blocksize << "\nCache Size: " << size << "\nBlocks: " << c.blocks << "\nAssociativity: " << assoc << std::endl; runprogram(program); std::vector data = readdata(program); cachesim(c, data); std::cout << c.hits << " hits, " << c.misses << " misses, " << c.accesses << " accesses" << std::endl; } return 0; }