From 2ad386f104cf84bd8bcb50eef50f04cdbcf9ebf7 Mon Sep 17 00:00:00 2001 From: Lisa Hsu Date: Tue, 23 Feb 2010 09:33:09 -0800 Subject: [PATCH] cache: pull CacheSet out of LRU so that other tags can use associative sets. --- src/mem/cache/blk.hh | 5 ++- src/mem/cache/tags/SConscript | 1 + src/mem/cache/tags/cacheset.cc | 68 ++++++++++++++++++++++++++++++++ src/mem/cache/tags/cacheset.hh | 71 ++++++++++++++++++++++++++++++++++ src/mem/cache/tags/lru.cc | 60 ++++++---------------------- src/mem/cache/tags/lru.hh | 48 ++++------------------- 6 files changed, 163 insertions(+), 90 deletions(-) create mode 100644 src/mem/cache/tags/cacheset.cc create mode 100644 src/mem/cache/tags/cacheset.hh diff --git a/src/mem/cache/blk.hh b/src/mem/cache/blk.hh index 369de6d11..4f023e848 100644 --- a/src/mem/cache/blk.hh +++ b/src/mem/cache/blk.hh @@ -98,6 +98,9 @@ class CacheBlk */ int set; + /** whether this block has been touched */ + bool isTouched; + /** Number of references to this block since it was brought in. */ int refCount; @@ -130,7 +133,7 @@ class CacheBlk CacheBlk() : asid(-1), tag(0), data(0) ,size(0), status(0), whenReady(0), - set(-1), refCount(0) + set(-1), isTouched(false), refCount(0) {} /** diff --git a/src/mem/cache/tags/SConscript b/src/mem/cache/tags/SConscript index 7255e0b7e..37ed5dc85 100644 --- a/src/mem/cache/tags/SConscript +++ b/src/mem/cache/tags/SConscript @@ -34,6 +34,7 @@ Source('base.cc') Source('fa_lru.cc') Source('iic.cc') Source('lru.cc') +Source('cacheset.cc') SimObject('iic_repl/Repl.py') Source('iic_repl/gen.cc') diff --git a/src/mem/cache/tags/cacheset.cc b/src/mem/cache/tags/cacheset.cc new file mode 100644 index 000000000..dea1a6b45 --- /dev/null +++ b/src/mem/cache/tags/cacheset.cc @@ -0,0 +1,68 @@ +/* + * Copyright (c) 2009 The Regents of The University of Michigan + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer; + * redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution; + * neither the name of the copyright holders nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * Authors: Lisa Hsu + */ + + +#include "mem/cache/tags/cacheset.hh" + +CacheBlk* +CacheSet::findBlk(Addr tag) const +{ + for (int i = 0; i < assoc; ++i) { + if (blks[i]->tag == tag && blks[i]->isValid()) { + return blks[i]; + } + } + return 0; +} + +void +CacheSet::moveToHead(CacheBlk *blk) +{ + // nothing to do if blk is already head + if (blks[0] == blk) + return; + + // write 'next' block into blks[i], moving up from MRU toward LRU + // until we overwrite the block we moved to head. + + // start by setting up to write 'blk' into blks[0] + int i = 0; + CacheBlk *next = blk; + + do { + assert(i < assoc); + // swap blks[i] and next + CacheBlk *tmp = blks[i]; + blks[i] = next; + next = tmp; + ++i; + } while (next != blk); +} + diff --git a/src/mem/cache/tags/cacheset.hh b/src/mem/cache/tags/cacheset.hh new file mode 100644 index 000000000..135e993aa --- /dev/null +++ b/src/mem/cache/tags/cacheset.hh @@ -0,0 +1,71 @@ +/* + * Copyright (c) 2009 The Regents of The University of Michigan + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer; + * redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution; + * neither the name of the copyright holders nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * Authors: Lisa Hsu + */ + +/** + * @file + * Declaration of an associative set + */ + +#ifndef __CACHESET_HH__ +#define __CACHESET_HH__ + +#include "mem/cache/blk.hh" // base class +#include + + +/** + * An associative set of cache blocks. + */ +class CacheSet +{ + public: + /** The associativity of this set. */ + int assoc; + + /** Cache blocks in this set, maintained in LRU order 0 = MRU. */ + CacheBlk **blks; + + /** + * Find a block matching the tag in this set. + * @param asid The address space ID. + * @param tag The Tag to find. + * @return Pointer to the block if found. + */ + CacheBlk* findBlk(Addr tag) const; + + /** + * Move the given block to the head of the list. + * @param blk The block to move. + */ + void moveToHead(CacheBlk *blk); + +}; + +#endif diff --git a/src/mem/cache/tags/lru.cc b/src/mem/cache/tags/lru.cc index 81d82c231..81d44b0c0 100644 --- a/src/mem/cache/tags/lru.cc +++ b/src/mem/cache/tags/lru.cc @@ -39,46 +39,10 @@ #include "base/intmath.hh" #include "mem/cache/tags/lru.hh" #include "sim/core.hh" +#include "cacheset.hh" using namespace std; -LRUBlk* -CacheSet::findBlk(Addr tag) const -{ - for (int i = 0; i < assoc; ++i) { - if (blks[i]->tag == tag && blks[i]->isValid()) { - return blks[i]; - } - } - return 0; -} - - -void -CacheSet::moveToHead(LRUBlk *blk) -{ - // nothing to do if blk is already head - if (blks[0] == blk) - return; - - // write 'next' block into blks[i], moving up from MRU toward LRU - // until we overwrite the block we moved to head. - - // start by setting up to write 'blk' into blks[0] - int i = 0; - LRUBlk *next = blk; - - do { - assert(i < assoc); - // swap blks[i] and next - LRUBlk *tmp = blks[i]; - blks[i] = next; - next = tmp; - ++i; - } while (next != blk); -} - - // create and initialize a LRU/MRU cache structure LRU::LRU(unsigned _numSets, unsigned _blkSize, unsigned _assoc, unsigned _hit_latency) @@ -108,7 +72,7 @@ LRU::LRU(unsigned _numSets, unsigned _blkSize, unsigned _assoc, warmupBound = numSets * assoc; sets = new CacheSet[numSets]; - blks = new LRUBlk[numSets * assoc]; + blks = new BlkType[numSets * assoc]; // allocate data storage in one big chunk dataBlks = new uint8_t[numSets*assoc*blkSize]; @@ -116,12 +80,12 @@ LRU::LRU(unsigned _numSets, unsigned _blkSize, unsigned _assoc, for (unsigned i = 0; i < numSets; ++i) { sets[i].assoc = assoc; - sets[i].blks = new LRUBlk*[assoc]; + sets[i].blks = new BlkType*[assoc]; // link in the data blocks for (unsigned j = 0; j < assoc; ++j) { // locate next cache block - LRUBlk *blk = &blks[blkIndex]; + BlkType *blk = &blks[blkIndex]; blk->data = &dataBlks[blkSize*blkIndex]; ++blkIndex; @@ -149,12 +113,12 @@ LRU::~LRU() delete [] sets; } -LRUBlk* +LRU::BlkType* LRU::accessBlock(Addr addr, int &lat, int context_src) { Addr tag = extractTag(addr); unsigned set = extractSet(addr); - LRUBlk *blk = sets[set].findBlk(tag); + BlkType *blk = sets[set].findBlk(tag); lat = hitLatency; if (blk != NULL) { // move this block to head of the MRU list @@ -172,21 +136,21 @@ LRU::accessBlock(Addr addr, int &lat, int context_src) } -LRUBlk* +LRU::BlkType* LRU::findBlock(Addr addr) const { Addr tag = extractTag(addr); unsigned set = extractSet(addr); - LRUBlk *blk = sets[set].findBlk(tag); + BlkType *blk = sets[set].findBlk(tag); return blk; } -LRUBlk* +LRU::BlkType* LRU::findVictim(Addr addr, PacketList &writebacks) { unsigned set = extractSet(addr); // grab a replacement candidate - LRUBlk *blk = sets[set].blks[assoc-1]; + BlkType *blk = sets[set].blks[assoc-1]; if (blk->isValid()) { replacements[0]++; totalRefs += blk->refCount; @@ -200,7 +164,7 @@ LRU::findVictim(Addr addr, PacketList &writebacks) } void -LRU::insertBlock(Addr addr, LRU::BlkType *blk, int context_src) +LRU::insertBlock(Addr addr, BlkType *blk, int context_src) { if (!blk->isTouched) { tagsInUse++; @@ -219,7 +183,7 @@ LRU::insertBlock(Addr addr, LRU::BlkType *blk, int context_src) } void -LRU::invalidateBlk(LRU::BlkType *blk) +LRU::invalidateBlk(BlkType *blk) { if (blk) { blk->status = 0; diff --git a/src/mem/cache/tags/lru.hh b/src/mem/cache/tags/lru.hh index ecd6e861f..be8d75b5a 100644 --- a/src/mem/cache/tags/lru.hh +++ b/src/mem/cache/tags/lru.hh @@ -45,42 +45,8 @@ #include "mem/packet.hh" class BaseCache; +class CacheSet; -/** - * LRU cache block. - */ -class LRUBlk : public CacheBlk { - public: - /** Has this block been touched? Used to aid calculation of warmup time. */ - bool isTouched; -}; - -/** - * An associative set of cache blocks. - */ -class CacheSet -{ - public: - /** The associativity of this set. */ - int assoc; - - /** Cache blocks in this set, maintained in LRU order 0 = MRU. */ - LRUBlk **blks; - - /** - * Find a block matching the tag in this set. - * @param asid The address space ID. - * @param tag The Tag to find. - * @return Pointer to the block if found. - */ - LRUBlk* findBlk(Addr tag) const; - - /** - * Move the given block to the head of the list. - * @param blk The block to move. - */ - void moveToHead(LRUBlk *blk); -}; /** * A LRU cache tag store. @@ -89,9 +55,9 @@ class LRU : public BaseTags { public: /** Typedef the block type used in this tag store. */ - typedef LRUBlk BlkType; + typedef CacheBlk BlkType; /** Typedef for a list of pointers to the local block class. */ - typedef std::list BlkList; + typedef std::list BlkList; protected: /** The number of sets in the cache. */ @@ -107,7 +73,7 @@ class LRU : public BaseTags CacheSet *sets; /** The cache blocks. */ - LRUBlk *blks; + BlkType *blks; /** The data blocks, 1 per cache block. */ uint8_t *dataBlks; @@ -172,7 +138,7 @@ public: * @param lat The access latency. * @return Pointer to the cache block if found. */ - LRUBlk* accessBlock(Addr addr, int &lat, int context_src); + BlkType* accessBlock(Addr addr, int &lat, int context_src); /** * Finds the given address in the cache, do not update replacement data. @@ -181,7 +147,7 @@ public: * @param asid The address space ID. * @return Pointer to the cache block if found. */ - LRUBlk* findBlock(Addr addr) const; + BlkType* findBlock(Addr addr) const; /** * Find a block to evict for the address provided. @@ -189,7 +155,7 @@ public: * @param writebacks List for any writebacks to be performed. * @return The candidate block. */ - LRUBlk* findVictim(Addr addr, PacketList &writebacks); + BlkType* findVictim(Addr addr, PacketList &writebacks); /** * Insert the new block into the cache. For LRU this means inserting into -- 2.30.2