From 3c9fe9d5f3ecb82d10c0e1dc59fba509cdfc20e7 Mon Sep 17 00:00:00 2001 From: bd Date: Mon, 28 Apr 2025 21:37:40 -0400 Subject: Fixed bugs introduced with cache ways, small cleanups --- inc/cache.h | 29 +++++++++-------------------- inc/definitions.h | 5 ----- src/cache.cc | 49 +++++++++++++++++++++++++------------------------ 3 files changed, 34 insertions(+), 49 deletions(-) diff --git a/inc/cache.h b/inc/cache.h index b55b30c..0eee833 100644 --- a/inc/cache.h +++ b/inc/cache.h @@ -75,29 +75,14 @@ nn * Constructor. */ int priming_address(int address); /** - * Walks the ways in this set of ways. If none of the tags match, returns -1. Otherwise, returns - * the index the matching data is located. + * Searches the set of ways in cache belonging to `index' for `tag'. If a match is found, + * returns the true index into the table. If a match is not found, returns a address suitable to + * replace, dictated by the LRU replacement policy.. * @param an index aligned to the set of ways in `this->data' * @param the tag to be matched - * @return -1 if the tag is not present in this set of ways (not in cache), or the true index if - * the tag is present. + * @return the true index if the tag is present, or the index to be replaced if not. */ - int is_address_missing(int true_index, int tag); - /** - * Converts an index into a set of ways into an index into `this->data', which is a - * 1D array. The next `this->ways' entries after the returned index represent the ways in the - * set for this index. - * @param an index to a set of ways - * @param an index aligned to the set of ways in `this->data' - */ - int get_true_index(int index); - /** - * Selects an index into the `data' and `meta' tables for write back using a random replacement - * policy. - * @param an index aligned to the set of ways in `this->data' - * @return an index aligned to the data line selected for eviction - */ - int get_replacement_index(int index); + int search_ways_for(int true_index, int tag); /** * The number of bits required to specify a line in this level of cache. */ @@ -107,6 +92,10 @@ nn * Constructor. * certain address index. */ unsigned int ways; + /** + * The current access number. Used to assign usage data for the LRU replacement policy. + */ + unsigned int access_num; /** * An array of metadata about elements in `data`. * If the first value of an element is negative, the corresponding diff --git a/inc/definitions.h b/inc/definitions.h index f0946b8..737656d 100644 --- a/inc/definitions.h +++ b/inc/definitions.h @@ -42,11 +42,6 @@ #define MEM_WORDS static_cast(pow(2, MEM_WORD_SPEC)) #define MEM_LINES static_cast(pow(2, MEM_LINE_SPEC)) -/** - * The total number of cycles a memory access takes - */ -#define MEM_DELAY 3 - /** * Return the N least-significant bits from integer K using a bit mask * @param the integer to be parsed diff --git a/src/cache.cc b/src/cache.cc index c8879b5..95ddf4a 100644 --- a/src/cache.cc +++ b/src/cache.cc @@ -20,6 +20,7 @@ #include #include #include +#include Cache::Cache(Storage *lower, unsigned int size, unsigned int ways, int delay) : Storage(delay) { @@ -33,6 +34,7 @@ Cache::Cache(Storage *lower, unsigned int size, unsigned int ways, int delay) : this->size = size; // store the number of bits which are moved into the tag field this->ways = ways; + this->access_num = 0; } Cache::~Cache() @@ -87,9 +89,15 @@ Cache::process(void *id, int address, std::function return 0; int tag, index, offset; + std::array *meta; + GET_FIELDS(address, &tag, &index, &offset); - index = this->get_true_index(index); + index = this->search_ways_for(index, tag); request_handler(index, offset); + // set usage status + meta = &this->meta.at(index); + meta->at(2) = (this->access_num % INT_MAX); + ++this->access_num; return 1; } @@ -97,26 +105,25 @@ Cache::process(void *id, int address, std::function int Cache::priming_address(int address) { - int tag, index, offset; + int tag, index, offset, t_index; int r1, r2; std::array *evict; std::array *meta; r1 = 0; GET_FIELDS(address, &tag, &index, &offset); - index = this->get_true_index(index); + t_index = this->search_ways_for(index, tag); + meta = &this->meta.at(t_index); - if (this->is_address_missing(index, tag)) { + if (meta->at(0) != tag) { r1 = 1; - index = this->get_replacement_index(index); - meta = &this->meta.at(index); - evict = &this->data->at(index); + evict = &this->data->at(t_index); // handle eviction of dirty cache lines if (meta->at(1) >= 0) { r2 = this->lower->write_line( - this, *evict, ((index << LINE_SPEC) + (meta->at(0) << (this->size + LINE_SPEC)))); + this, *evict, ((index << LINE_SPEC) + (meta->at(0) << (this->size - this->ways + LINE_SPEC)))); if (r2) meta->at(1) = -1; } else { @@ -131,24 +138,18 @@ Cache::priming_address(int address) } int -Cache::is_address_missing(int index, int tag) +Cache::search_ways_for(int index, int tag) { - int i; + int i, r; + + index = index * (1 << this->ways); + r = INT_MAX; for (i = 0; i < (1 << this->ways); ++i) if (this->meta.at(index + i).at(0) == tag) - return i; - return -1; -} - -int -Cache::get_true_index(int index) -{ - return index * (1 << this->ways); -} - -int -Cache::get_replacement_index(int index) -{ - return index + (rand() % (1 << this->ways)); + return i + index; + for (i = 0; i < (1 << this->ways); ++i) + if (this->meta.at(index + i).at(2) < r) + r = i; + return r + index; } -- cgit v1.2.3