summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorDaniel R. Carvalho <odanrc@yahoo.com.br>2018-03-28 12:23:19 +0200
committerDaniel Carvalho <odanrc@yahoo.com.br>2018-04-13 09:27:52 +0000
commitf119531fc123d33bef34a6ee28cad22717c63927 (patch)
tree5fc1e3794a351b7ce269a5e7dfedd8e6a2e4c195 /src
parente6ab75cc6cc89436904905f92dfec8a964de3108 (diff)
downloadgem5-f119531fc123d33bef34a6ee28cad22717c63927.tar.xz
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 <nikos.nikoleris@arm.com> Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>
Diffstat (limited to 'src')
-rw-r--r--src/mem/cache/tags/fa_lru.cc86
-rw-r--r--src/mem/cache/tags/fa_lru.hh8
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.