fa_lru.cc revision 7823:dac01f14f20f
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 <cassert> 37#include <sstream> 38 39#include "base/intmath.hh" 40#include "base/misc.hh" 41#include "mem/cache/tags/fa_lru.hh" 42 43using namespace std; 44 45FALRU::FALRU(unsigned _blkSize, unsigned _size, unsigned hit_latency) 46 : blkSize(_blkSize), size(_size), hitLatency(hit_latency) 47{ 48 if (!isPowerOf2(blkSize)) 49 fatal("cache block size (in bytes) `%d' must be a power of two", 50 blkSize); 51 if (!(hitLatency > 0)) 52 fatal("Access latency in cycles must be at least one cycle"); 53 if (!isPowerOf2(size)) 54 fatal("Cache Size must be power of 2 for now"); 55 56 // Track all cache sizes from 128K up by powers of 2 57 numCaches = floorLog2(size) - 17; 58 if (numCaches >0){ 59 cacheBoundaries = new FALRUBlk *[numCaches]; 60 cacheMask = (1 << numCaches) - 1; 61 } else { 62 cacheMask = 0; 63 } 64 65 warmedUp = false; 66 warmupBound = size/blkSize; 67 numBlocks = size/blkSize; 68 69 blks = new FALRUBlk[numBlocks]; 70 head = &(blks[0]); 71 tail = &(blks[numBlocks-1]); 72 73 head->prev = NULL; 74 head->next = &(blks[1]); 75 head->inCache = cacheMask; 76 77 tail->prev = &(blks[numBlocks-2]); 78 tail->next = NULL; 79 tail->inCache = 0; 80 81 unsigned index = (1 << 17) / blkSize; 82 unsigned j = 0; 83 int flags = cacheMask; 84 for (unsigned i = 1; i < numBlocks - 1; i++) { 85 blks[i].inCache = flags; 86 if (i == index - 1){ 87 cacheBoundaries[j] = &(blks[i]); 88 flags &= ~ (1<<j); 89 ++j; 90 index = index << 1; 91 } 92 blks[i].prev = &(blks[i-1]); 93 blks[i].next = &(blks[i+1]); 94 blks[i].isTouched = false; 95 } 96 assert(j == numCaches); 97 assert(index == numBlocks); 98 //assert(check()); 99} 100 101void 102FALRU::regStats(const string &name) 103{ 104 using namespace Stats; 105 BaseTags::regStats(name); 106 hits 107 .init(numCaches+1) 108 .name(name + ".falru_hits") 109 .desc("The number of hits in each cache size.") 110 ; 111 misses 112 .init(numCaches+1) 113 .name(name + ".falru_misses") 114 .desc("The number of misses in each cache size.") 115 ; 116 accesses 117 .name(name + ".falru_accesses") 118 .desc("The number of accesses to the FA LRU cache.") 119 ; 120 121 for (unsigned i = 0; i <= numCaches; ++i) { 122 stringstream size_str; 123 if (i < 3){ 124 size_str << (1<<(i+7)) <<"K"; 125 } else { 126 size_str << (1<<(i-3)) <<"M"; 127 } 128 129 hits.subname(i, size_str.str()); 130 hits.subdesc(i, "Hits in a " + size_str.str() +" cache"); 131 misses.subname(i, size_str.str()); 132 misses.subdesc(i, "Misses in a " + size_str.str() +" cache"); 133 } 134} 135 136FALRUBlk * 137FALRU::hashLookup(Addr addr) const 138{ 139 tagIterator iter = tagHash.find(addr); 140 if (iter != tagHash.end()) { 141 return (*iter).second; 142 } 143 return NULL; 144} 145 146void 147FALRU::invalidateBlk(FALRU::BlkType *blk) 148{ 149 if (blk) { 150 blk->status = 0; 151 blk->isTouched = false; 152 tagsInUse--; 153 } 154} 155 156FALRUBlk* 157FALRU::accessBlock(Addr addr, int &lat, int context_src, int *inCache) 158{ 159 accesses++; 160 int tmp_in_cache = 0; 161 Addr blkAddr = blkAlign(addr); 162 FALRUBlk* blk = hashLookup(blkAddr); 163 164 if (blk && blk->isValid()) { 165 assert(blk->tag == blkAddr); 166 tmp_in_cache = blk->inCache; 167 for (unsigned i = 0; i < numCaches; i++) { 168 if (1<<i & blk->inCache) { 169 hits[i]++; 170 } else { 171 misses[i]++; 172 } 173 } 174 hits[numCaches]++; 175 if (blk != head){ 176 moveToHead(blk); 177 } 178 } else { 179 blk = NULL; 180 for (unsigned i = 0; i <= numCaches; ++i) { 181 misses[i]++; 182 } 183 } 184 if (inCache) { 185 *inCache = tmp_in_cache; 186 } 187 188 lat = hitLatency; 189 //assert(check()); 190 return blk; 191} 192 193 194FALRUBlk* 195FALRU::findBlock(Addr addr) const 196{ 197 Addr blkAddr = blkAlign(addr); 198 FALRUBlk* blk = hashLookup(blkAddr); 199 200 if (blk && blk->isValid()) { 201 assert(blk->tag == blkAddr); 202 } else { 203 blk = NULL; 204 } 205 return blk; 206} 207 208FALRUBlk* 209FALRU::findVictim(Addr addr, PacketList &writebacks) 210{ 211 FALRUBlk * blk = tail; 212 assert(blk->inCache == 0); 213 moveToHead(blk); 214 tagHash.erase(blk->tag); 215 tagHash[blkAlign(addr)] = blk; 216 if (blk->isValid()) { 217 replacements[0]++; 218 } else { 219 tagsInUse++; 220 blk->isTouched = true; 221 if (!warmedUp && tagsInUse.value() >= warmupBound) { 222 warmedUp = true; 223 warmupCycle = curTick(); 224 } 225 } 226 //assert(check()); 227 return blk; 228} 229 230void 231FALRU::insertBlock(Addr addr, FALRU::BlkType *blk, int context_src) 232{ 233} 234 235void 236FALRU::moveToHead(FALRUBlk *blk) 237{ 238 int updateMask = blk->inCache ^ cacheMask; 239 for (unsigned i = 0; i < numCaches; i++){ 240 if ((1<<i) & updateMask) { 241 cacheBoundaries[i]->inCache &= ~(1<<i); 242 cacheBoundaries[i] = cacheBoundaries[i]->prev; 243 } else if (cacheBoundaries[i] == blk) { 244 cacheBoundaries[i] = blk->prev; 245 } 246 } 247 blk->inCache = cacheMask; 248 if (blk != head) { 249 if (blk == tail){ 250 assert(blk->next == NULL); 251 tail = blk->prev; 252 tail->next = NULL; 253 } else { 254 blk->prev->next = blk->next; 255 blk->next->prev = blk->prev; 256 } 257 blk->next = head; 258 blk->prev = NULL; 259 head->prev = blk; 260 head = blk; 261 } 262} 263 264bool 265FALRU::check() 266{ 267 FALRUBlk* blk = head; 268 int size = 0; 269 int boundary = 1<<17; 270 int j = 0; 271 int flags = cacheMask; 272 while (blk) { 273 size += blkSize; 274 if (blk->inCache != flags) { 275 return false; 276 } 277 if (size == boundary && blk != tail) { 278 if (cacheBoundaries[j] != blk) { 279 return false; 280 } 281 flags &=~(1 << j); 282 boundary = boundary<<1; 283 ++j; 284 } 285 blk = blk->next; 286 } 287 return true; 288} 289 290void 291FALRU::clearLocks() 292{ 293 for (int i = 0; i < numBlocks; i++){ 294 blks[i].clearLoadLocks(); 295 } 296} 297