src/mem/cache/tags/fa_lru.cc

   1 /*
   2  * Copyright (c) 2003-2005 The Regents of The University of Michigan
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  *
  28  * Authors: Erik Hallnor
  29  */
  30
  31 /**
  32  * @file
  33  * Definitions a fully associative LRU tagstore.
  34  */
  35
  36 #include <sstream>
  37
  38 #include <assert.h>
  39
  40 #include "mem/cache/tags/fa_lru.hh"
  41 #include "base/intmath.hh"
  42 #include "base/misc.hh"
  43
  44 using namespace std;
  45
  46 FALRU::FALRU(int _blkSize, int _size, int hit_latency)
  47     : blkSize(_blkSize), size(_size),
  48       numBlks(size/blkSize), hitLatency(hit_latency)
  49 {
  50     if (!isPowerOf2(blkSize))
  51         fatal("cache block size (in bytes) `%d' must be a power of two",
  52               blkSize);
  53     if (!(hitLatency > 0))
  54         fatal("Access latency in cycles must be at least one cycle");
  55     if (!isPowerOf2(size))
  56         fatal("Cache Size must be power of 2 for now");
  57
  58     // Track all cache sizes from 128K up by powers of 2
  59     numCaches = floorLog2(size) - 17;
  60     if (numCaches >0){
  61         cacheBoundaries = new FALRUBlk *[numCaches];
  62         cacheMask = (1 << numCaches) - 1;
  63     } else {
  64         cacheMask = 0;
  65     }
  66
  67     warmedUp = false;
  68     warmupBound = size/blkSize;
  69
  70     blks = new FALRUBlk[numBlks];
  71     head = &(blks[0]);
  72     tail = &(blks[numBlks-1]);
  73
  74     head->prev = NULL;
  75     head->next = &(blks[1]);
  76     head->inCache = cacheMask;
  77
  78     tail->prev = &(blks[numBlks-2]);
  79     tail->next = NULL;
  80     tail->inCache = 0;
  81
  82     int index = (1 << 17) / blkSize;
  83     int j = 0;
  84     int flags = cacheMask;
  85     for (int i = 1; i < numBlks-1; i++) {
  86         blks[i].inCache = flags;
  87         if (i == index - 1){
  88             cacheBoundaries[j] = &(blks[i]);
  89             flags &= ~ (1<<j);
  90             ++j;
  91             index = index << 1;
  92         }
  93         blks[i].prev = &(blks[i-1]);
  94         blks[i].next = &(blks[i+1]);
  95         blks[i].isTouched = false;
  96     }
  97     assert(j == numCaches);
  98     assert(index == numBlks);
  99     //assert(check());
 100 }
 101
 102 void
 103 FALRU::regStats(const string &name)
 104 {
 105     using namespace Stats;
 106     BaseTags::regStats(name);
 107     hits
 108         .init(numCaches+1)
 109         .name(name + ".falru_hits")
 110         .desc("The number of hits in each cache size.")
 111         ;
 112     misses
 113         .init(numCaches+1)
 114         .name(name + ".falru_misses")
 115         .desc("The number of misses in each cache size.")
 116         ;
 117     accesses
 118         .name(name + ".falru_accesses")
 119         .desc("The number of accesses to the FA LRU cache.")
 120         ;
 121
 122     for (int i = 0; i < numCaches+1; ++i) {
 123         stringstream size_str;
 124         if (i < 3){
 125             size_str << (1<<(i+7)) <<"K";
 126         } else {
 127             size_str << (1<<(i-3)) <<"M";
 128         }
 129
 130         hits.subname(i, size_str.str());
 131         hits.subdesc(i, "Hits in a " + size_str.str() +" cache");
 132         misses.subname(i, size_str.str());
 133         misses.subdesc(i, "Misses in a " + size_str.str() +" cache");
 134     }
 135 }
 136
 137 FALRUBlk *
 138 FALRU::hashLookup(Addr addr) const
 139 {
 140     tagIterator iter = tagHash.find(addr);
 141     if (iter != tagHash.end()) {
 142         return (*iter).second;
 143     }
 144     return NULL;
 145 }
 146
 147 bool
 148 FALRU::probe(Addr addr) const
 149 {
 150     Addr blkAddr = blkAlign(addr);
 151     FALRUBlk* blk = hashLookup(blkAddr);
 152     return blk && blk->tag == blkAddr && blk->isValid();
 153 }
 154
 155 void
 156 FALRU::invalidateBlk(FALRU::BlkType *blk)
 157 {
 158     if (blk) {
 159         blk->status = 0;
 160         blk->isTouched = false;
 161         tagsInUse--;
 162     }
 163 }
 164
 165 FALRUBlk*
 166 FALRU::findBlock(Addr addr, int &lat, int *inCache)
 167 {
 168     accesses++;
 169     int tmp_in_cache = 0;
 170     Addr blkAddr = blkAlign(addr);
 171     FALRUBlk* blk = hashLookup(blkAddr);
 172
 173     if (blk && blk->isValid()) {
 174         assert(blk->tag == blkAddr);
 175         tmp_in_cache = blk->inCache;
 176         for (int i = 0; i < numCaches; i++) {
 177             if (1<<i & blk->inCache) {
 178                 hits[i]++;
 179             } else {
 180                 misses[i]++;
 181             }
 182         }
 183         hits[numCaches]++;
 184         if (blk != head){
 185             moveToHead(blk);
 186         }
 187     } else {
 188         blk = NULL;
 189         for (int i = 0; i < numCaches+1; ++i) {
 190             misses[i]++;
 191         }
 192     }
 193     if (inCache) {
 194         *inCache = tmp_in_cache;
 195     }
 196
 197     lat = hitLatency;
 198     //assert(check());
 199     return blk;
 200 }
 201
 202
 203 FALRUBlk*
 204 FALRU::findBlock(Addr addr) const
 205 {
 206     Addr blkAddr = blkAlign(addr);
 207     FALRUBlk* blk = hashLookup(blkAddr);
 208
 209     if (blk && blk->isValid()) {
 210         assert(blk->tag == blkAddr);
 211     } else {
 212         blk = NULL;
 213     }
 214     return blk;
 215 }
 216
 217 FALRUBlk*
 218 FALRU::findReplacement(Addr addr, PacketList &writebacks)
 219 {
 220     FALRUBlk * blk = tail;
 221     assert(blk->inCache == 0);
 222     moveToHead(blk);
 223     tagHash.erase(blk->tag);
 224     tagHash[blkAlign(addr)] = blk;
 225     if (blk->isValid()) {
 226         replacements[0]++;
 227     } else {
 228         tagsInUse++;
 229         blk->isTouched = true;
 230         if (!warmedUp && tagsInUse.value() >= warmupBound) {
 231             warmedUp = true;
 232             warmupCycle = curTick;
 233         }
 234     }
 235     //assert(check());
 236     return blk;
 237 }
 238
 239 void
 240 FALRU::moveToHead(FALRUBlk *blk)
 241 {
 242     int updateMask = blk->inCache ^ cacheMask;
 243     for (int i = 0; i < numCaches; i++){
 244         if ((1<<i) & updateMask) {
 245             cacheBoundaries[i]->inCache &= ~(1<<i);
 246             cacheBoundaries[i] = cacheBoundaries[i]->prev;
 247         } else if (cacheBoundaries[i] == blk) {
 248             cacheBoundaries[i] = blk->prev;
 249         }
 250     }
 251     blk->inCache = cacheMask;
 252     if (blk != head) {
 253         if (blk == tail){
 254             assert(blk->next == NULL);
 255             tail = blk->prev;
 256             tail->next = NULL;
 257         } else {
 258             blk->prev->next = blk->next;
 259             blk->next->prev = blk->prev;
 260         }
 261         blk->next = head;
 262         blk->prev = NULL;
 263         head->prev = blk;
 264         head = blk;
 265     }
 266 }
 267
 268 bool
 269 FALRU::check()
 270 {
 271     FALRUBlk* blk = head;
 272     int size = 0;
 273     int boundary = 1<<17;
 274     int j = 0;
 275     int flags = cacheMask;
 276     while (blk) {
 277         size += blkSize;
 278         if (blk->inCache != flags) {
 279             return false;
 280         }
 281         if (size == boundary && blk != tail) {
 282             if (cacheBoundaries[j] != blk) {
 283                 return false;
 284             }
 285             flags &=~(1 << j);
 286             boundary = boundary<<1;
 287             ++j;
 288         }
 289         blk = blk->next;
 290     }
 291     return true;
 292 }