fa_lru.cc revision 3862:ec47e4243107
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(FALRU::BlkType *blk) 157{ 158 if (blk) { 159 blk->status = 0; 160 blk->isTouched = false; 161 tagsInUse--; 162 } 163} 164 165FALRUBlk* 166FALRU::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 203FALRUBlk* 204FALRU::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 217FALRUBlk* 218FALRU::findReplacement(PacketPtr &pkt, PacketList &writebacks, 219 BlkList &compress_blocks) 220{ 221 FALRUBlk * blk = tail; 222 assert(blk->inCache == 0); 223 moveToHead(blk); 224 tagHash.erase(blk->tag); 225 tagHash[blkAlign(pkt->getAddr())] = blk; 226 if (blk->isValid()) { 227 replacements[0]++; 228 } else { 229 tagsInUse++; 230 blk->isTouched = true; 231 if (!warmedUp && tagsInUse.value() >= warmupBound) { 232 warmedUp = true; 233 warmupCycle = curTick; 234 } 235 } 236 //assert(check()); 237 return blk; 238} 239 240void 241FALRU::moveToHead(FALRUBlk *blk) 242{ 243 int updateMask = blk->inCache ^ cacheMask; 244 for (int i = 0; i < numCaches; i++){ 245 if ((1<<i) & updateMask) { 246 cacheBoundaries[i]->inCache &= ~(1<<i); 247 cacheBoundaries[i] = cacheBoundaries[i]->prev; 248 } else if (cacheBoundaries[i] == blk) { 249 cacheBoundaries[i] = blk->prev; 250 } 251 } 252 blk->inCache = cacheMask; 253 if (blk != head) { 254 if (blk == tail){ 255 assert(blk->next == NULL); 256 tail = blk->prev; 257 tail->next = NULL; 258 } else { 259 blk->prev->next = blk->next; 260 blk->next->prev = blk->prev; 261 } 262 blk->next = head; 263 blk->prev = NULL; 264 head->prev = blk; 265 head = blk; 266 } 267} 268 269bool 270FALRU::check() 271{ 272 FALRUBlk* blk = head; 273 int size = 0; 274 int boundary = 1<<17; 275 int j = 0; 276 int flags = cacheMask; 277 while (blk) { 278 size += blkSize; 279 if (blk->inCache != flags) { 280 return false; 281 } 282 if (size == boundary && blk != tail) { 283 if (cacheBoundaries[j] != blk) { 284 return false; 285 } 286 flags &=~(1 << j); 287 boundary = boundary<<1; 288 ++j; 289 } 290 blk = blk->next; 291 } 292 return true; 293} 294