Daniel Carvalho has submitted this change and it was merged. (
https://gem5-review.googlesource.com/9541 )
Change subject: mem-cache: Add MoveToTail to FALRU
......................................................................
mem-cache: Add MoveToTail to FALRU
FALRU was missing MoveToTail functionality within its invalidate
function, and MoveToHead was doing unnecessary passes when the
moved block was the head already.
Besides, added some comments to make the code understandable.
Change-Id: I2430d82b5d53c88b102a62610ea38b46d6e03a55
Reviewed-on: https://gem5-review.googlesource.com/9541
Reviewed-by: Nikos Nikoleris <[email protected]>
Maintainer: Nikos Nikoleris <[email protected]>
---
M src/mem/cache/tags/fa_lru.cc
M src/mem/cache/tags/fa_lru.hh
2 files changed, 82 insertions(+), 12 deletions(-)
Approvals:
Nikos Nikoleris: Looks good to me, approved; Looks good to me, approved
diff --git a/src/mem/cache/tags/fa_lru.cc b/src/mem/cache/tags/fa_lru.cc
index f02b55a..b75497e 100644
--- a/src/mem/cache/tags/fa_lru.cc
+++ b/src/mem/cache/tags/fa_lru.cc
@@ -64,7 +64,7 @@
// 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 @@
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 @@
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 @@
}
}
+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 129af9f..73d6660 100644
--- a/src/mem/cache/tags/fa_lru.hh
+++ b/src/mem/cache/tags/fa_lru.hh
@@ -122,11 +122,19 @@
/**
* 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.
--
To view, visit https://gem5-review.googlesource.com/9541
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings
Gerrit-Project: public/gem5
Gerrit-Branch: master
Gerrit-Change-Id: I2430d82b5d53c88b102a62610ea38b46d6e03a55
Gerrit-Change-Number: 9541
Gerrit-PatchSet: 4
Gerrit-Owner: Daniel Carvalho <[email protected]>
Gerrit-Reviewer: Daniel Carvalho <[email protected]>
Gerrit-Reviewer: Jason Lowe-Power <[email protected]>
Gerrit-Reviewer: Nikos Nikoleris <[email protected]>
Gerrit-MessageType: merged
_______________________________________________
gem5-dev mailing list
[email protected]
http://m5sim.org/mailman/listinfo/gem5-dev
