fa_lru.cc revision 3349:fec4a86fa212
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 147bool 148FALRU::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 155void 156FALRU::invalidateBlk(Addr addr) 157{ 158 Addr blkAddr = blkAlign(addr); 159 FALRUBlk* blk = (*tagHash.find(blkAddr)).second; 160 if (blk) { 161 assert(blk->tag == blkAddr); 162 blk->status = 0; 163 blk->isTouched = false; 164 tagsInUse--; 165 } 166} 167 168FALRUBlk* 169FALRU::findBlock(Addr addr, int &lat, int *inCache) 170{ 171 accesses++; 172 int tmp_in_cache = 0; 173 Addr blkAddr = blkAlign(addr); 174 FALRUBlk* blk = hashLookup(blkAddr); 175 176 if (blk && blk->isValid()) { 177 assert(blk->tag == blkAddr); 178 tmp_in_cache = blk->inCache; 179 for (int i = 0; i < numCaches; i++) { 180 if (1<<i & blk->inCache) { 181 hits[i]++; 182 } else { 183 misses[i]++; 184 } 185 } 186 hits[numCaches]++; 187 if (blk != head){ 188 moveToHead(blk); 189 } 190 } else { 191 blk = NULL; 192 for (int i = 0; i < numCaches+1; ++i) { 193 misses[i]++; 194 } 195 } 196 if (inCache) { 197 *inCache = tmp_in_cache; 198 } 199 200 lat = hitLatency; 201 //assert(check()); 202 return blk; 203} 204 205FALRUBlk* 206FALRU::findBlock(PacketPtr &pkt, int &lat, int *inCache) 207{ 208 Addr addr = pkt->getAddr(); 209 210 accesses++; 211 int tmp_in_cache = 0; 212 Addr blkAddr = blkAlign(addr); 213 FALRUBlk* blk = hashLookup(blkAddr); 214 215 if (blk && blk->isValid()) { 216 assert(blk->tag == blkAddr); 217 tmp_in_cache = blk->inCache; 218 for (int i = 0; i < numCaches; i++) { 219 if (1<<i & blk->inCache) { 220 hits[i]++; 221 } else { 222 misses[i]++; 223 } 224 } 225 hits[numCaches]++; 226 if (blk != head){ 227 moveToHead(blk); 228 } 229 } else { 230 blk = NULL; 231 for (int i = 0; i < numCaches+1; ++i) { 232 misses[i]++; 233 } 234 } 235 if (inCache) { 236 *inCache = tmp_in_cache; 237 } 238 239 lat = hitLatency; 240 //assert(check()); 241 return blk; 242} 243 244FALRUBlk* 245FALRU::findBlock(Addr addr) const 246{ 247 Addr blkAddr = blkAlign(addr); 248 FALRUBlk* blk = hashLookup(blkAddr); 249 250 if (blk && blk->isValid()) { 251 assert(blk->tag == blkAddr); 252 } else { 253 blk = NULL; 254 } 255 return blk; 256} 257 258FALRUBlk* 259FALRU::findReplacement(PacketPtr &pkt, PacketList &writebacks, 260 BlkList &compress_blocks) 261{ 262 FALRUBlk * blk = tail; 263 assert(blk->inCache == 0); 264 moveToHead(blk); 265 tagHash.erase(blk->tag); 266 tagHash[blkAlign(pkt->getAddr())] = blk; 267 if (blk->isValid()) { 268 replacements[0]++; 269 } else { 270 tagsInUse++; 271 blk->isTouched = true; 272 if (!warmedUp && tagsInUse.value() >= warmupBound) { 273 warmedUp = true; 274 warmupCycle = curTick; 275 } 276 } 277 //assert(check()); 278 return blk; 279} 280 281void 282FALRU::moveToHead(FALRUBlk *blk) 283{ 284 int updateMask = blk->inCache ^ cacheMask; 285 for (int i = 0; i < numCaches; i++){ 286 if ((1<<i) & updateMask) { 287 cacheBoundaries[i]->inCache &= ~(1<<i); 288 cacheBoundaries[i] = cacheBoundaries[i]->prev; 289 } else if (cacheBoundaries[i] == blk) { 290 cacheBoundaries[i] = blk->prev; 291 } 292 } 293 blk->inCache = cacheMask; 294 if (blk != head) { 295 if (blk == tail){ 296 assert(blk->next == NULL); 297 tail = blk->prev; 298 tail->next = NULL; 299 } else { 300 blk->prev->next = blk->next; 301 blk->next->prev = blk->prev; 302 } 303 blk->next = head; 304 blk->prev = NULL; 305 head->prev = blk; 306 head = blk; 307 } 308} 309 310bool 311FALRU::check() 312{ 313 FALRUBlk* blk = head; 314 int size = 0; 315 int boundary = 1<<17; 316 int j = 0; 317 int flags = cacheMask; 318 while (blk) { 319 size += blkSize; 320 if (blk->inCache != flags) { 321 return false; 322 } 323 if (size == boundary && blk != tail) { 324 if (cacheBoundaries[j] != blk) { 325 return false; 326 } 327 flags &=~(1 << j); 328 boundary = boundary<<1; 329 ++j; 330 } 331 blk = blk->next; 332 } 333 return true; 334} 335