#include #include inline int ilog2(unsigned int v) { static const unsigned int b[] = {0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0, 0xFF00FF00, 0xFFFF0000 }; unsigned int r = (v & b[0]) != 0; for (int i = 4; i > 0; i--) { r |= ((v & b[i]) != 0) << i; } return r; } inline bool ispow2(unsigned int n) { return n && !(n & (n - 1)); } class cache { int _blocksize; int _blocks; int _size; int _assoc; int _wordsize; int _blocks_log2; unsigned int* _tags; int* _lastaccess; public: int hits; int misses; int accesses; cache(int blocksize, int size, int associativity, int wordsize) : _blocksize(blocksize), _blocks(size / blocksize), _size(size), _assoc(associativity), _wordsize(wordsize), hits(0), misses(0), accesses(0) { if (!ispow2(size) || !ispow2(_blocks)) { // throw std::argument_exception("Size/blocks must be power of 2."); std::cout << "Size/blocks must be power of 2." << std::endl; } _blocks_log2 = ilog2(_blocks); _tags = new unsigned int[_blocks * _assoc]; _lastaccess = new int[_blocks * _assoc]; for (int i = 0; i < _blocks * _assoc; i++) { _lastaccess[i] = 0; } } ~cache() { }; bool access(unsigned int addr) { int block = (addr >> (_wordsize - 1)) % _blocks; unsigned int t = addr >> (_wordsize - 1 + _blocks_log2); accesses++; int a = 0; for (a; a < _assoc; a++) { if (t == _tags[block + _blocks * a] && _lastaccess[block + _blocks * a]) { hits++; _lastaccess[block + _blocks * a] = accesses; return true; } } // Miss, add to cache misses++; int lru = 0xFFFF; int lrua = 0; for (a = 0; a < _assoc; a++) { if (_lastaccess[block + _blocks * a] < lru) { lru = _lastaccess[block + _blocks * a]; lrua = a; } if (!_lastaccess[block + _blocks * a]) { // Empty set _lastaccess[block + _blocks * a] = accesses; _tags[block + _blocks * a] = t; return false; } } // No empty sets, remove lru. _lastaccess[block + _blocks * lrua] = accesses; _tags[block + _blocks * lrua] = t; return false; } }; int main(int argc, char const *argv[]) { cache c(1, 8, 1, 1); std::cout << c.access(22) << std::endl; std::cout << c.access(26) << std::endl; std::cout << c.access(22) << std::endl; std::cout << c.access(26) << std::endl; std::cout << c.access(16) << std::endl; std::cout << c.access(3) << std::endl; std::cout << c.access(16) << std::endl; std::cout << c.access(19) << std::endl; std::cout << c.access(16) << std::endl; std::cout << c.access(3) << std::endl; std::cout << c.hits << " hits, " << c.misses << " misses, " << c.accesses << " accesses" << std::endl; return 0; }