fa_lru.cc revision 2991
12810Srdreslin@umich.edu/* 22810Srdreslin@umich.edu * Copyright (c) 2003-2005 The Regents of The University of Michigan 32810Srdreslin@umich.edu * All rights reserved. 42810Srdreslin@umich.edu * 52810Srdreslin@umich.edu * Redistribution and use in source and binary forms, with or without 62810Srdreslin@umich.edu * modification, are permitted provided that the following conditions are 72810Srdreslin@umich.edu * met: redistributions of source code must retain the above copyright 82810Srdreslin@umich.edu * notice, this list of conditions and the following disclaimer; 92810Srdreslin@umich.edu * redistributions in binary form must reproduce the above copyright 102810Srdreslin@umich.edu * notice, this list of conditions and the following disclaimer in the 112810Srdreslin@umich.edu * documentation and/or other materials provided with the distribution; 122810Srdreslin@umich.edu * neither the name of the copyright holders nor the names of its 132810Srdreslin@umich.edu * contributors may be used to endorse or promote products derived from 142810Srdreslin@umich.edu * this software without specific prior written permission. 152810Srdreslin@umich.edu * 162810Srdreslin@umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 172810Srdreslin@umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 182810Srdreslin@umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 192810Srdreslin@umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 202810Srdreslin@umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 212810Srdreslin@umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 222810Srdreslin@umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 232810Srdreslin@umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 242810Srdreslin@umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 252810Srdreslin@umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 262810Srdreslin@umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272810Srdreslin@umich.edu * 282810Srdreslin@umich.edu * Authors: Erik Hallnor 292810Srdreslin@umich.edu */ 302810Srdreslin@umich.edu 312810Srdreslin@umich.edu/** 322810Srdreslin@umich.edu * @file 332810Srdreslin@umich.edu * Definitions a fully associative LRU tagstore. 342810Srdreslin@umich.edu */ 352810Srdreslin@umich.edu 362810Srdreslin@umich.edu#include <sstream> 372810Srdreslin@umich.edu 382810Srdreslin@umich.edu#include <assert.h> 392810Srdreslin@umich.edu 402810Srdreslin@umich.edu#include "mem/cache/tags/fa_lru.hh" 412810Srdreslin@umich.edu#include "base/intmath.hh" 422814Srdreslin@umich.edu#include "base/misc.hh" 432810Srdreslin@umich.edu 442810Srdreslin@umich.eduusing namespace std; 452810Srdreslin@umich.edu 462810Srdreslin@umich.eduFALRU::FALRU(int _blkSize, int _size, int hit_latency) 472810Srdreslin@umich.edu : blkSize(_blkSize), size(_size), 482810Srdreslin@umich.edu numBlks(size/blkSize), hitLatency(hit_latency) 492810Srdreslin@umich.edu{ 502810Srdreslin@umich.edu if (!isPowerOf2(blkSize)) 512810Srdreslin@umich.edu fatal("cache block size (in bytes) `%d' must be a power of two", 522810Srdreslin@umich.edu blkSize); 532810Srdreslin@umich.edu if (!(hitLatency > 0)) 542810Srdreslin@umich.edu fatal("Access latency in cycles must be at least one cycle"); 552810Srdreslin@umich.edu if (!isPowerOf2(size)) 562810Srdreslin@umich.edu fatal("Cache Size must be power of 2 for now"); 572810Srdreslin@umich.edu 582810Srdreslin@umich.edu // Track all cache sizes from 128K up by powers of 2 592810Srdreslin@umich.edu numCaches = floorLog2(size) - 17; 602810Srdreslin@umich.edu if (numCaches >0){ 612810Srdreslin@umich.edu cacheBoundaries = new FALRUBlk *[numCaches]; 622810Srdreslin@umich.edu cacheMask = (1 << numCaches) - 1; 632810Srdreslin@umich.edu } else { 642810Srdreslin@umich.edu cacheMask = 0; 652810Srdreslin@umich.edu } 662810Srdreslin@umich.edu 672810Srdreslin@umich.edu warmedUp = false; 682810Srdreslin@umich.edu warmupBound = size/blkSize; 692810Srdreslin@umich.edu 702810Srdreslin@umich.edu blks = new FALRUBlk[numBlks]; 712810Srdreslin@umich.edu head = &(blks[0]); 722810Srdreslin@umich.edu tail = &(blks[numBlks-1]); 732810Srdreslin@umich.edu 742810Srdreslin@umich.edu head->prev = NULL; 752810Srdreslin@umich.edu head->next = &(blks[1]); 762810Srdreslin@umich.edu head->inCache = cacheMask; 772810Srdreslin@umich.edu 782810Srdreslin@umich.edu tail->prev = &(blks[numBlks-2]); 792810Srdreslin@umich.edu tail->next = NULL; 802810Srdreslin@umich.edu tail->inCache = 0; 812810Srdreslin@umich.edu 822810Srdreslin@umich.edu int index = (1 << 17) / blkSize; 832810Srdreslin@umich.edu int j = 0; 842810Srdreslin@umich.edu int flags = cacheMask; 852810Srdreslin@umich.edu for (int i = 1; i < numBlks-1; i++) { 862810Srdreslin@umich.edu blks[i].inCache = flags; 872810Srdreslin@umich.edu if (i == index - 1){ 882810Srdreslin@umich.edu cacheBoundaries[j] = &(blks[i]); 892810Srdreslin@umich.edu flags &= ~ (1<<j); 902810Srdreslin@umich.edu ++j; 912810Srdreslin@umich.edu index = index << 1; 922810Srdreslin@umich.edu } 932810Srdreslin@umich.edu blks[i].prev = &(blks[i-1]); 942810Srdreslin@umich.edu blks[i].next = &(blks[i+1]); 952810Srdreslin@umich.edu blks[i].isTouched = false; 962810Srdreslin@umich.edu } 972810Srdreslin@umich.edu assert(j == numCaches); 982810Srdreslin@umich.edu assert(index == numBlks); 992810Srdreslin@umich.edu //assert(check()); 1002810Srdreslin@umich.edu} 1012810Srdreslin@umich.edu 1022810Srdreslin@umich.eduvoid 1032810Srdreslin@umich.eduFALRU::regStats(const string &name) 1042810Srdreslin@umich.edu{ 1052810Srdreslin@umich.edu using namespace Stats; 1062810Srdreslin@umich.edu BaseTags::regStats(name); 1072810Srdreslin@umich.edu hits 1082810Srdreslin@umich.edu .init(numCaches+1) 1092810Srdreslin@umich.edu .name(name + ".falru_hits") 1102810Srdreslin@umich.edu .desc("The number of hits in each cache size.") 1112810Srdreslin@umich.edu ; 1122810Srdreslin@umich.edu misses 1132810Srdreslin@umich.edu .init(numCaches+1) 1142810Srdreslin@umich.edu .name(name + ".falru_misses") 1152810Srdreslin@umich.edu .desc("The number of misses in each cache size.") 1162810Srdreslin@umich.edu ; 1172810Srdreslin@umich.edu accesses 1182810Srdreslin@umich.edu .name(name + ".falru_accesses") 1192810Srdreslin@umich.edu .desc("The number of accesses to the FA LRU cache.") 1202810Srdreslin@umich.edu ; 1212810Srdreslin@umich.edu 1222810Srdreslin@umich.edu for (int i = 0; i < numCaches+1; ++i) { 1232810Srdreslin@umich.edu stringstream size_str; 1242810Srdreslin@umich.edu if (i < 3){ 1252810Srdreslin@umich.edu size_str << (1<<(i+7)) <<"K"; 1262810Srdreslin@umich.edu } else { 1272810Srdreslin@umich.edu size_str << (1<<(i-3)) <<"M"; 1282810Srdreslin@umich.edu } 1292810Srdreslin@umich.edu 1302810Srdreslin@umich.edu hits.subname(i, size_str.str()); 1312810Srdreslin@umich.edu hits.subdesc(i, "Hits in a " + size_str.str() +" cache"); 1322810Srdreslin@umich.edu misses.subname(i, size_str.str()); 1332810Srdreslin@umich.edu misses.subdesc(i, "Misses in a " + size_str.str() +" cache"); 1342810Srdreslin@umich.edu } 1352810Srdreslin@umich.edu} 1362810Srdreslin@umich.edu 1372810Srdreslin@umich.eduFALRUBlk * 1382810Srdreslin@umich.eduFALRU::hashLookup(Addr addr) const 1392810Srdreslin@umich.edu{ 1402810Srdreslin@umich.edu tagIterator iter = tagHash.find(addr); 1412810Srdreslin@umich.edu if (iter != tagHash.end()) { 1422810Srdreslin@umich.edu return (*iter).second; 1432810Srdreslin@umich.edu } 1442810Srdreslin@umich.edu return NULL; 1452810Srdreslin@umich.edu} 1462810Srdreslin@umich.edu 1472810Srdreslin@umich.edubool 1482991Srdreslin@umich.eduFALRU::probe(Addr addr) const 1492810Srdreslin@umich.edu{ 1502810Srdreslin@umich.edu Addr blkAddr = blkAlign(addr); 1512810Srdreslin@umich.edu FALRUBlk* blk = hashLookup(blkAddr); 1522810Srdreslin@umich.edu return blk && blk->tag == blkAddr && blk->isValid(); 1532810Srdreslin@umich.edu} 1542810Srdreslin@umich.edu 1552810Srdreslin@umich.eduvoid 1562991Srdreslin@umich.eduFALRU::invalidateBlk(Addr addr) 1572810Srdreslin@umich.edu{ 1582810Srdreslin@umich.edu Addr blkAddr = blkAlign(addr); 1592810Srdreslin@umich.edu FALRUBlk* blk = (*tagHash.find(blkAddr)).second; 1602810Srdreslin@umich.edu if (blk) { 1612810Srdreslin@umich.edu assert(blk->tag == blkAddr); 1622810Srdreslin@umich.edu blk->status = 0; 1632810Srdreslin@umich.edu blk->isTouched = false; 1642810Srdreslin@umich.edu tagsInUse--; 1652810Srdreslin@umich.edu } 1662810Srdreslin@umich.edu} 1672810Srdreslin@umich.edu 1682810Srdreslin@umich.eduFALRUBlk* 1692991Srdreslin@umich.eduFALRU::findBlock(Addr addr, int &lat, int *inCache) 1702810Srdreslin@umich.edu{ 1712810Srdreslin@umich.edu accesses++; 1722810Srdreslin@umich.edu int tmp_in_cache = 0; 1732810Srdreslin@umich.edu Addr blkAddr = blkAlign(addr); 1742810Srdreslin@umich.edu FALRUBlk* blk = hashLookup(blkAddr); 1752810Srdreslin@umich.edu 1762810Srdreslin@umich.edu if (blk && blk->isValid()) { 1772810Srdreslin@umich.edu assert(blk->tag == blkAddr); 1782810Srdreslin@umich.edu tmp_in_cache = blk->inCache; 1792810Srdreslin@umich.edu for (int i = 0; i < numCaches; i++) { 1802810Srdreslin@umich.edu if (1<<i & blk->inCache) { 1812810Srdreslin@umich.edu hits[i]++; 1822810Srdreslin@umich.edu } else { 1832810Srdreslin@umich.edu misses[i]++; 1842810Srdreslin@umich.edu } 1852810Srdreslin@umich.edu } 1862810Srdreslin@umich.edu hits[numCaches]++; 1872810Srdreslin@umich.edu if (blk != head){ 1882810Srdreslin@umich.edu moveToHead(blk); 1892810Srdreslin@umich.edu } 1902810Srdreslin@umich.edu } else { 1912810Srdreslin@umich.edu blk = NULL; 1922810Srdreslin@umich.edu for (int i = 0; i < numCaches+1; ++i) { 1932810Srdreslin@umich.edu misses[i]++; 1942810Srdreslin@umich.edu } 1952810Srdreslin@umich.edu } 1962810Srdreslin@umich.edu if (inCache) { 1972810Srdreslin@umich.edu *inCache = tmp_in_cache; 1982810Srdreslin@umich.edu } 1992810Srdreslin@umich.edu 2002810Srdreslin@umich.edu lat = hitLatency; 2012810Srdreslin@umich.edu //assert(check()); 2022810Srdreslin@umich.edu return blk; 2032810Srdreslin@umich.edu} 2042810Srdreslin@umich.edu 2052810Srdreslin@umich.eduFALRUBlk* 2062810Srdreslin@umich.eduFALRU::findBlock(Packet * &pkt, int &lat, int *inCache) 2072810Srdreslin@umich.edu{ 2082814Srdreslin@umich.edu Addr addr = pkt->getAddr(); 2092810Srdreslin@umich.edu 2102810Srdreslin@umich.edu accesses++; 2112810Srdreslin@umich.edu int tmp_in_cache = 0; 2122810Srdreslin@umich.edu Addr blkAddr = blkAlign(addr); 2132810Srdreslin@umich.edu FALRUBlk* blk = hashLookup(blkAddr); 2142810Srdreslin@umich.edu 2152810Srdreslin@umich.edu if (blk && blk->isValid()) { 2162810Srdreslin@umich.edu assert(blk->tag == blkAddr); 2172810Srdreslin@umich.edu tmp_in_cache = blk->inCache; 2182810Srdreslin@umich.edu for (int i = 0; i < numCaches; i++) { 2192810Srdreslin@umich.edu if (1<<i & blk->inCache) { 2202810Srdreslin@umich.edu hits[i]++; 2212810Srdreslin@umich.edu } else { 2222810Srdreslin@umich.edu misses[i]++; 2232810Srdreslin@umich.edu } 2242810Srdreslin@umich.edu } 2252810Srdreslin@umich.edu hits[numCaches]++; 2262810Srdreslin@umich.edu if (blk != head){ 2272810Srdreslin@umich.edu moveToHead(blk); 2282810Srdreslin@umich.edu } 2292810Srdreslin@umich.edu } else { 2302810Srdreslin@umich.edu blk = NULL; 2312810Srdreslin@umich.edu for (int i = 0; i < numCaches+1; ++i) { 2322810Srdreslin@umich.edu misses[i]++; 2332810Srdreslin@umich.edu } 2342810Srdreslin@umich.edu } 2352810Srdreslin@umich.edu if (inCache) { 2362810Srdreslin@umich.edu *inCache = tmp_in_cache; 2372810Srdreslin@umich.edu } 2382810Srdreslin@umich.edu 2392810Srdreslin@umich.edu lat = hitLatency; 2402810Srdreslin@umich.edu //assert(check()); 2412810Srdreslin@umich.edu return blk; 2422810Srdreslin@umich.edu} 2432810Srdreslin@umich.edu 2442810Srdreslin@umich.eduFALRUBlk* 2452991Srdreslin@umich.eduFALRU::findBlock(Addr addr) const 2462810Srdreslin@umich.edu{ 2472810Srdreslin@umich.edu Addr blkAddr = blkAlign(addr); 2482810Srdreslin@umich.edu FALRUBlk* blk = hashLookup(blkAddr); 2492810Srdreslin@umich.edu 2502810Srdreslin@umich.edu if (blk && blk->isValid()) { 2512810Srdreslin@umich.edu assert(blk->tag == blkAddr); 2522810Srdreslin@umich.edu } else { 2532810Srdreslin@umich.edu blk = NULL; 2542810Srdreslin@umich.edu } 2552810Srdreslin@umich.edu return blk; 2562810Srdreslin@umich.edu} 2572810Srdreslin@umich.edu 2582810Srdreslin@umich.eduFALRUBlk* 2592814Srdreslin@umich.eduFALRU::findReplacement(Packet * &pkt, PacketList &writebacks, 2602810Srdreslin@umich.edu BlkList &compress_blocks) 2612810Srdreslin@umich.edu{ 2622810Srdreslin@umich.edu FALRUBlk * blk = tail; 2632810Srdreslin@umich.edu assert(blk->inCache == 0); 2642810Srdreslin@umich.edu moveToHead(blk); 2652810Srdreslin@umich.edu tagHash.erase(blk->tag); 2662814Srdreslin@umich.edu tagHash[blkAlign(pkt->getAddr())] = blk; 2672810Srdreslin@umich.edu if (blk->isValid()) { 2682814Srdreslin@umich.edu replacements[0]++; 2692810Srdreslin@umich.edu } else { 2702810Srdreslin@umich.edu tagsInUse++; 2712810Srdreslin@umich.edu blk->isTouched = true; 2722810Srdreslin@umich.edu if (!warmedUp && tagsInUse.value() >= warmupBound) { 2732810Srdreslin@umich.edu warmedUp = true; 2742810Srdreslin@umich.edu warmupCycle = curTick; 2752810Srdreslin@umich.edu } 2762810Srdreslin@umich.edu } 2772810Srdreslin@umich.edu //assert(check()); 2782810Srdreslin@umich.edu return blk; 2792810Srdreslin@umich.edu} 2802810Srdreslin@umich.edu 2812810Srdreslin@umich.eduvoid 2822810Srdreslin@umich.eduFALRU::moveToHead(FALRUBlk *blk) 2832810Srdreslin@umich.edu{ 2842810Srdreslin@umich.edu int updateMask = blk->inCache ^ cacheMask; 2852810Srdreslin@umich.edu for (int i = 0; i < numCaches; i++){ 2862810Srdreslin@umich.edu if ((1<<i) & updateMask) { 2872810Srdreslin@umich.edu cacheBoundaries[i]->inCache &= ~(1<<i); 2882810Srdreslin@umich.edu cacheBoundaries[i] = cacheBoundaries[i]->prev; 2892810Srdreslin@umich.edu } else if (cacheBoundaries[i] == blk) { 2902810Srdreslin@umich.edu cacheBoundaries[i] = blk->prev; 2912810Srdreslin@umich.edu } 2922810Srdreslin@umich.edu } 2932810Srdreslin@umich.edu blk->inCache = cacheMask; 2942810Srdreslin@umich.edu if (blk != head) { 2952810Srdreslin@umich.edu if (blk == tail){ 2962810Srdreslin@umich.edu assert(blk->next == NULL); 2972810Srdreslin@umich.edu tail = blk->prev; 2982810Srdreslin@umich.edu tail->next = NULL; 2992810Srdreslin@umich.edu } else { 3002810Srdreslin@umich.edu blk->prev->next = blk->next; 3012810Srdreslin@umich.edu blk->next->prev = blk->prev; 3022810Srdreslin@umich.edu } 3032810Srdreslin@umich.edu blk->next = head; 3042810Srdreslin@umich.edu blk->prev = NULL; 3052810Srdreslin@umich.edu head->prev = blk; 3062810Srdreslin@umich.edu head = blk; 3072810Srdreslin@umich.edu } 3082810Srdreslin@umich.edu} 3092810Srdreslin@umich.edu 3102810Srdreslin@umich.edubool 3112810Srdreslin@umich.eduFALRU::check() 3122810Srdreslin@umich.edu{ 3132810Srdreslin@umich.edu FALRUBlk* blk = head; 3142810Srdreslin@umich.edu int size = 0; 3152810Srdreslin@umich.edu int boundary = 1<<17; 3162810Srdreslin@umich.edu int j = 0; 3172810Srdreslin@umich.edu int flags = cacheMask; 3182810Srdreslin@umich.edu while (blk) { 3192810Srdreslin@umich.edu size += blkSize; 3202810Srdreslin@umich.edu if (blk->inCache != flags) { 3212810Srdreslin@umich.edu return false; 3222810Srdreslin@umich.edu } 3232810Srdreslin@umich.edu if (size == boundary && blk != tail) { 3242810Srdreslin@umich.edu if (cacheBoundaries[j] != blk) { 3252810Srdreslin@umich.edu return false; 3262810Srdreslin@umich.edu } 3272810Srdreslin@umich.edu flags &=~(1 << j); 3282810Srdreslin@umich.edu boundary = boundary<<1; 3292810Srdreslin@umich.edu ++j; 3302810Srdreslin@umich.edu } 3312810Srdreslin@umich.edu blk = blk->next; 3322810Srdreslin@umich.edu } 3332810Srdreslin@umich.edu return true; 3342810Srdreslin@umich.edu} 335