fa_lru.cc revision 5706:2cc2387049bc
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 44using namespace std; 45 46FALRU::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 102void 103FALRU::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 137FALRUBlk * 138FALRU::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 147void 148FALRU::invalidateBlk(FALRU::BlkType *blk) 149{ 150 if (blk) { 151 blk->status = 0; 152 blk->isTouched = false; 153 tagsInUse--; 154 } 155} 156 157FALRUBlk* 158FALRU::findBlock(Addr addr, int &lat, int *inCache) 159{ 160 accesses++; 161 int tmp_in_cache = 0; 162 Addr blkAddr = blkAlign(addr); 163 FALRUBlk* blk = hashLookup(blkAddr); 164 165 if (blk && blk->isValid()) { 166 assert(blk->tag == blkAddr); 167 tmp_in_cache = blk->inCache; 168 for (int i = 0; i < numCaches; i++) { 169 if (1<<i & blk->inCache) { 170 hits[i]++; 171 } else { 172 misses[i]++; 173 } 174 } 175 hits[numCaches]++; 176 if (blk != head){ 177 moveToHead(blk); 178 } 179 } else { 180 blk = NULL; 181 for (int i = 0; i < numCaches+1; ++i) { 182 misses[i]++; 183 } 184 } 185 if (inCache) { 186 *inCache = tmp_in_cache; 187 } 188 189 lat = hitLatency; 190 //assert(check()); 191 return blk; 192} 193 194 195FALRUBlk* 196FALRU::findBlock(Addr addr) const 197{ 198 Addr blkAddr = blkAlign(addr); 199 FALRUBlk* blk = hashLookup(blkAddr); 200 201 if (blk && blk->isValid()) { 202 assert(blk->tag == blkAddr); 203 } else { 204 blk = NULL; 205 } 206 return blk; 207} 208 209FALRUBlk* 210FALRU::findReplacement(Addr addr, PacketList &writebacks) 211{ 212 FALRUBlk * blk = tail; 213 assert(blk->inCache == 0); 214 moveToHead(blk); 215 tagHash.erase(blk->tag); 216 tagHash[blkAlign(addr)] = blk; 217 if (blk->isValid()) { 218 replacements[0]++; 219 } else { 220 tagsInUse++; 221 blk->isTouched = true; 222 if (!warmedUp && tagsInUse.value() >= warmupBound) { 223 warmedUp = true; 224 warmupCycle = curTick; 225 } 226 } 227 //assert(check()); 228 return blk; 229} 230 231void 232FALRU::moveToHead(FALRUBlk *blk) 233{ 234 int updateMask = blk->inCache ^ cacheMask; 235 for (int i = 0; i < numCaches; i++){ 236 if ((1<<i) & updateMask) { 237 cacheBoundaries[i]->inCache &= ~(1<<i); 238 cacheBoundaries[i] = cacheBoundaries[i]->prev; 239 } else if (cacheBoundaries[i] == blk) { 240 cacheBoundaries[i] = blk->prev; 241 } 242 } 243 blk->inCache = cacheMask; 244 if (blk != head) { 245 if (blk == tail){ 246 assert(blk->next == NULL); 247 tail = blk->prev; 248 tail->next = NULL; 249 } else { 250 blk->prev->next = blk->next; 251 blk->next->prev = blk->prev; 252 } 253 blk->next = head; 254 blk->prev = NULL; 255 head->prev = blk; 256 head = blk; 257 } 258} 259 260bool 261FALRU::check() 262{ 263 FALRUBlk* blk = head; 264 int size = 0; 265 int boundary = 1<<17; 266 int j = 0; 267 int flags = cacheMask; 268 while (blk) { 269 size += blkSize; 270 if (blk->inCache != flags) { 271 return false; 272 } 273 if (size == boundary && blk != tail) { 274 if (cacheBoundaries[j] != blk) { 275 return false; 276 } 277 flags &=~(1 << j); 278 boundary = boundary<<1; 279 ++j; 280 } 281 blk = blk->next; 282 } 283 return true; 284} 285