diff options
Diffstat (limited to 'src/mem/cache')
-rw-r--r-- | src/mem/cache/tags/fa_lru.cc | 86 | ||||
-rw-r--r-- | src/mem/cache/tags/fa_lru.hh | 8 |
2 files changed, 82 insertions, 12 deletions
diff --git a/src/mem/cache/tags/fa_lru.cc b/src/mem/cache/tags/fa_lru.cc index f02b55a8d..b75497ea2 100644 --- a/src/mem/cache/tags/fa_lru.cc +++ b/src/mem/cache/tags/fa_lru.cc @@ -64,7 +64,7 @@ FALRU::FALRU(const Params *p) // Track all cache sizes from 128K up by powers of 2 numCaches = floorLog2(size) - 17; - if (numCaches >0){ + if (numCaches > 0){ cacheBoundaries = new FALRUBlk *[numCaches]; cacheMask = (ULL(1) << numCaches) - 1; } else { @@ -164,9 +164,11 @@ FALRU::hashLookup(Addr addr) const void FALRU::invalidate(CacheBlk *blk) { - // TODO: We need to move the block to the tail to make it the next victim BaseTags::invalidate(blk); + // Move the block to the tail to make it the next victim + moveToTail((FALRUBlk*)blk); + // Erase block entry in the hash table tagHash.erase(blk->tag); } @@ -276,25 +278,41 @@ FALRU::insertBlock(PacketPtr pkt, CacheBlk *blk) void FALRU::moveToHead(FALRUBlk *blk) { - int updateMask = blk->inCache ^ cacheMask; - for (unsigned i = 0; i < numCaches; i++){ - if ((1<<i) & updateMask) { - cacheBoundaries[i]->inCache &= ~(1<<i); - cacheBoundaries[i] = cacheBoundaries[i]->prev; - } else if (cacheBoundaries[i] == blk) { - cacheBoundaries[i] = blk->prev; - } - } - blk->inCache = cacheMask; + // If block is not already head, do the moving if (blk != head) { + // Get all caches that this block does not reside in + int updateMask = blk->inCache ^ cacheMask; + + // Update boundaries for all cache sizes + for (unsigned i = 0; i < numCaches; i++){ + // If block has been moved to a place before this boundary, + // all blocks in it will be pushed towards the LRU position, + // making one leave the boundary + if ((1U<<i) & updateMask) { + cacheBoundaries[i]->inCache &= ~(1U<<i); + cacheBoundaries[i] = cacheBoundaries[i]->prev; + // If the block resides exactly at this boundary, the previous + // block is pushed to its position + } else if (cacheBoundaries[i] == blk) { + cacheBoundaries[i] = blk->prev; + } + } + + // Make block reside in all caches + blk->inCache = cacheMask; + + // If block is tail, set previous block as new tail if (blk == tail){ assert(blk->next == nullptr); tail = blk->prev; tail->next = nullptr; + // Inform block's surrounding blocks that it has been moved } else { blk->prev->next = blk->next; blk->next->prev = blk->prev; } + + // Swap pointers blk->next = head; blk->prev = nullptr; head->prev = blk; @@ -302,6 +320,50 @@ FALRU::moveToHead(FALRUBlk *blk) } } +void +FALRU::moveToTail(FALRUBlk *blk) +{ + // If block is not already tail, do the moving + if (blk != tail) { + // Update boundaries for all cache sizes + for (unsigned i = 0; i < numCaches; i++){ + // If block has been moved to a place after this boundary, + // all blocks in it will be pushed towards the MRU position, + // making one enter the boundary + if ((1U<<i) & blk->inCache) { + // If the first block after the boundary is the block, + // get its successor + if (cacheBoundaries[i]->next == blk){ + cacheBoundaries[i] = cacheBoundaries[i]->next->next; + } else { + cacheBoundaries[i] = cacheBoundaries[i]->next; + } + cacheBoundaries[i]->inCache |= (1U<<i); + } + } + + // Make block reside in the last cache only + blk->inCache = 0; + + // If block is head, set next block as new head + if (blk == head){ + assert(blk->prev == nullptr); + head = blk->next; + head->prev = nullptr; + // Inform block's surrounding blocks that it has been moved + } else { + blk->prev->next = blk->next; + blk->next->prev = blk->prev; + } + + // Swap pointers + blk->prev = tail; + blk->next = nullptr; + tail->next = blk; + tail = blk; + } +} + bool FALRU::check() { diff --git a/src/mem/cache/tags/fa_lru.hh b/src/mem/cache/tags/fa_lru.hh index 129af9f37..73d66604f 100644 --- a/src/mem/cache/tags/fa_lru.hh +++ b/src/mem/cache/tags/fa_lru.hh @@ -122,11 +122,19 @@ class FALRU : public BaseTags /** * Move a cache block to the MRU position. + * * @param blk The block to promote. */ void moveToHead(FALRUBlk *blk); /** + * Move a cache block to the LRU position. + * + * @param blk The block to demote. + */ + void moveToTail(FALRUBlk *blk); + + /** * Check to make sure all the cache boundaries are still where they should * be. Used for debugging. * @return True if everything is correct. |