diff options
| -rw-r--r-- | src/mem/cache/base.cc | 3 | ||||
| -rw-r--r-- | src/mem/cache/cache.cc | 2 | ||||
| -rw-r--r-- | src/mem/cache/tags/SConscript | 4 | ||||
| -rw-r--r-- | src/mem/cache/tags/Tags.py | 18 | ||||
| -rw-r--r-- | src/mem/cache/tags/base_set_assoc.cc | 203 | ||||
| -rw-r--r-- | src/mem/cache/tags/base_set_assoc.hh | 396 | ||||
| -rw-r--r-- | src/mem/cache/tags/lru.cc | 258 | ||||
| -rw-r--r-- | src/mem/cache/tags/lru.hh | 226 | ||||
| -rw-r--r-- | src/mem/cache/tags/random_repl.cc | 89 | ||||
| -rw-r--r-- | src/mem/cache/tags/random_repl.hh | 68 |
10 files changed, 806 insertions, 461 deletions
diff --git a/src/mem/cache/base.cc b/src/mem/cache/base.cc index af324527f..dd1306270 100644 --- a/src/mem/cache/base.cc +++ b/src/mem/cache/base.cc @@ -49,6 +49,7 @@ #include "debug/Drain.hh" #include "mem/cache/tags/fa_lru.hh" #include "mem/cache/tags/lru.hh" +#include "mem/cache/tags/random_repl.hh" #include "mem/cache/base.hh" #include "mem/cache/cache.hh" #include "mem/cache/mshr.hh" @@ -783,6 +784,8 @@ BaseCacheParams::create() if (numSets == 1) warn("Consider using FALRU tags for a fully associative cache\n"); return new Cache<LRU>(this); + } else if (dynamic_cast<RandomRepl*>(tags)) { + return new Cache<RandomRepl>(this); } else { fatal("No suitable tags selected\n"); } diff --git a/src/mem/cache/cache.cc b/src/mem/cache/cache.cc index d59a0d44b..a5fa0e60d 100644 --- a/src/mem/cache/cache.cc +++ b/src/mem/cache/cache.cc @@ -38,6 +38,7 @@ #include "mem/cache/tags/fa_lru.hh" #include "mem/cache/tags/lru.hh" +#include "mem/cache/tags/random_repl.hh" #include "mem/cache/cache_impl.hh" // Template Instantiations @@ -45,5 +46,6 @@ template class Cache<FALRU>; template class Cache<LRU>; +template class Cache<RandomRepl>; #endif //DOXYGEN_SHOULD_SKIP_THIS diff --git a/src/mem/cache/tags/SConscript b/src/mem/cache/tags/SConscript index dca8d3bd8..1412286a7 100644 --- a/src/mem/cache/tags/SConscript +++ b/src/mem/cache/tags/SConscript @@ -33,5 +33,7 @@ Import('*') SimObject('Tags.py') Source('base.cc') -Source('fa_lru.cc') +Source('base_set_assoc.cc') Source('lru.cc') +Source('random_repl.cc') +Source('fa_lru.cc') diff --git a/src/mem/cache/tags/Tags.py b/src/mem/cache/tags/Tags.py index 7c0dded32..ab1282ac9 100644 --- a/src/mem/cache/tags/Tags.py +++ b/src/mem/cache/tags/Tags.py @@ -53,14 +53,24 @@ class BaseTags(ClockedObject): hit_latency = Param.Cycles(Parent.hit_latency, "The hit latency for this cache") -class LRU(BaseTags): - type = 'LRU' - cxx_class = 'LRU' - cxx_header = "mem/cache/tags/lru.hh" +class BaseSetAssoc(BaseTags): + type = 'BaseSetAssoc' + abstract = True + cxx_header = "mem/cache/tags/base_set_assoc.hh" assoc = Param.Int(Parent.assoc, "associativity") sequential_access = Param.Bool(Parent.sequential_access, "Whether to access tags and data sequentially") +class LRU(BaseSetAssoc): + type = 'LRU' + cxx_class = 'LRU' + cxx_header = "mem/cache/tags/lru.hh" + +class RandomRepl(BaseSetAssoc): + type = 'RandomRepl' + cxx_class = 'RandomRepl' + cxx_header = "mem/cache/tags/random_repl.hh" + class FALRU(BaseTags): type = 'FALRU' cxx_class = 'FALRU' diff --git a/src/mem/cache/tags/base_set_assoc.cc b/src/mem/cache/tags/base_set_assoc.cc new file mode 100644 index 000000000..637edd557 --- /dev/null +++ b/src/mem/cache/tags/base_set_assoc.cc @@ -0,0 +1,203 @@ +/* + * Copyright (c) 2012-2013 ARM Limited + * All rights reserved. + * + * The license below extends only to copyright in the software and shall + * not be construed as granting a license to any other intellectual + * property including but not limited to intellectual property relating + * to a hardware implementation of the functionality of the software + * licensed hereunder. You may use the software subject to the license + * terms below provided that you ensure that this notice is replicated + * unmodified and in its entirety in all distributions of the software, + * modified or unmodified, in source code or in binary form. + * + * Copyright (c) 2003-2005,2014 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: Erik Hallnor + */ + +/** + * @file + * Definitions of a base set associative tag store. + */ + +#include <string> + +#include "base/intmath.hh" +#include "mem/cache/tags/base_set_assoc.hh" +#include "sim/core.hh" + +using namespace std; + +BaseSetAssoc::BaseSetAssoc(const Params *p) + :BaseTags(p), assoc(p->assoc), + numSets(p->size / (p->block_size * p->assoc)), + sequentialAccess(p->sequential_access) +{ + // Check parameters + if (blkSize < 4 || !isPowerOf2(blkSize)) { + fatal("Block size must be at least 4 and a power of 2"); + } + if (numSets <= 0 || !isPowerOf2(numSets)) { + fatal("# of sets must be non-zero and a power of 2"); + } + if (assoc <= 0) { + fatal("associativity must be greater than zero"); + } + if (hitLatency <= 0) { + fatal("access latency must be greater than zero"); + } + + blkMask = blkSize - 1; + setShift = floorLog2(blkSize); + setMask = numSets - 1; + tagShift = setShift + floorLog2(numSets); + warmedUp = false; + /** @todo Make warmup percentage a parameter. */ + warmupBound = numSets * assoc; + + sets = new SetType[numSets]; + blks = new BlkType[numSets * assoc]; + // allocate data storage in one big chunk + numBlocks = numSets * assoc; + dataBlks = new uint8_t[numBlocks * blkSize]; + + unsigned blkIndex = 0; // index into blks array + for (unsigned i = 0; i < numSets; ++i) { + sets[i].assoc = assoc; + + sets[i].blks = new BlkType*[assoc]; + + // link in the data blocks + for (unsigned j = 0; j < assoc; ++j) { + // locate next cache block + BlkType *blk = &blks[blkIndex]; + blk->data = &dataBlks[blkSize*blkIndex]; + ++blkIndex; + + // invalidate new cache block + blk->invalidate(); + + //EGH Fix Me : do we need to initialize blk? + + // Setting the tag to j is just to prevent long chains in the hash + // table; won't matter because the block is invalid + blk->tag = j; + blk->whenReady = 0; + blk->isTouched = false; + blk->size = blkSize; + sets[i].blks[j]=blk; + blk->set = i; + } + } +} + +BaseSetAssoc::~BaseSetAssoc() +{ + delete [] dataBlks; + delete [] blks; + delete [] sets; +} + +BaseSetAssoc::BlkType* +BaseSetAssoc::findBlock(Addr addr, bool is_secure) const +{ + Addr tag = extractTag(addr); + unsigned set = extractSet(addr); + BlkType *blk = sets[set].findBlk(tag, is_secure); + return blk; +} + +void +BaseSetAssoc::clearLocks() +{ + for (int i = 0; i < numBlocks; i++){ + blks[i].clearLoadLocks(); + } +} + +std::string +BaseSetAssoc::print() const { + std::string cache_state; + for (unsigned i = 0; i < numSets; ++i) { + // link in the data blocks + for (unsigned j = 0; j < assoc; ++j) { + BlkType *blk = sets[i].blks[j]; + if (blk->isValid()) + cache_state += csprintf("\tset: %d block: %d %s\n", i, j, + blk->print()); + } + } + if (cache_state.empty()) + cache_state = "no valid tags\n"; + return cache_state; +} + +void +BaseSetAssoc::cleanupRefs() +{ + for (unsigned i = 0; i < numSets*assoc; ++i) { + if (blks[i].isValid()) { + totalRefs += blks[i].refCount; + ++sampledRefs; + } + } +} + +void +BaseSetAssoc::computeStats() +{ + for (unsigned i = 0; i < ContextSwitchTaskId::NumTaskId; ++i) { + occupanciesTaskId[i] = 0; + for (unsigned j = 0; j < 5; ++j) { + ageTaskId[i][j] = 0; + } + } + + for (unsigned i = 0; i < numSets * assoc; ++i) { + if (blks[i].isValid()) { + assert(blks[i].task_id < ContextSwitchTaskId::NumTaskId); + occupanciesTaskId[blks[i].task_id]++; + Tick age = curTick() - blks[i].tickInserted; + assert(age >= 0); + + int age_index; + if (age / SimClock::Int::us < 10) { // <10us + age_index = 0; + } else if (age / SimClock::Int::us < 100) { // <100us + age_index = 1; + } else if (age / SimClock::Int::ms < 1) { // <1ms + age_index = 2; + } else if (age / SimClock::Int::ms < 10) { // <10ms + age_index = 3; + } else + age_index = 4; // >10ms + + ageTaskId[blks[i].task_id][age_index]++; + } + } +} diff --git a/src/mem/cache/tags/base_set_assoc.hh b/src/mem/cache/tags/base_set_assoc.hh new file mode 100644 index 000000000..218d9cdd9 --- /dev/null +++ b/src/mem/cache/tags/base_set_assoc.hh @@ -0,0 +1,396 @@ +/* + * Copyright (c) 2012-2013 ARM Limited + * All rights reserved. + * + * The license below extends only to copyright in the software and shall + * not be construed as granting a license to any other intellectual + * property including but not limited to intellectual property relating + * to a hardware implementation of the functionality of the software + * licensed hereunder. You may use the software subject to the license + * terms below provided that you ensure that this notice is replicated + * unmodified and in its entirety in all distributions of the software, + * modified or unmodified, in source code or in binary form. + * + * Copyright (c) 2003-2005,2014 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: Erik Hallnor + */ + +/** + * @file + * Declaration of a base set associative tag store. + */ + +#ifndef __MEM_CACHE_TAGS_BASESETASSOC_HH__ +#define __MEM_CACHE_TAGS_BASESETASSOC_HH__ + +#include <cassert> +#include <cstring> +#include <list> + +#include "mem/cache/tags/base.hh" +#include "mem/cache/tags/cacheset.hh" +#include "mem/cache/base.hh" +#include "mem/cache/blk.hh" +#include "mem/packet.hh" +#include "params/BaseSetAssoc.hh" + +/** + * A BaseSetAssoc cache tag store. + * @sa \ref gem5MemorySystem "gem5 Memory System" + * + * The BaseSetAssoc tags provide a base, as well as the functionality + * common to any set associative tags. Any derived class must implement + * the methods related to the specifics of the actual replacment policy. + * These are: + * + * BlkType* accessBlock(); + * BlkType* findVictim(); + * void insertBlock(); + * void invalidate(); + */ +class BaseSetAssoc : public BaseTags +{ + public: + /** Typedef the block type used in this tag store. */ + typedef CacheBlk BlkType; + /** Typedef for a list of pointers to the local block class. */ + typedef std::list<BlkType*> BlkList; + /** Typedef the set type used in this tag store. */ + typedef CacheSet<CacheBlk> SetType; + + + protected: + /** The associativity of the cache. */ + const unsigned assoc; + /** The number of sets in the cache. */ + const unsigned numSets; + /** Whether tags and data are accessed sequentially. */ + const bool sequentialAccess; + + /** The cache sets. */ + SetType *sets; + + /** The cache blocks. */ + BlkType *blks; + /** The data blocks, 1 per cache block. */ + uint8_t *dataBlks; + + /** The amount to shift the address to get the set. */ + int setShift; + /** The amount to shift the address to get the tag. */ + int tagShift; + /** Mask out all bits that aren't part of the set index. */ + unsigned setMask; + /** Mask out all bits that aren't part of the block offset. */ + unsigned blkMask; + +public: + + /** Convenience typedef. */ + typedef BaseSetAssocParams Params; + + /** + * Construct and initialize this tag store. + */ + BaseSetAssoc(const Params *p); + + /** + * Destructor + */ + virtual ~BaseSetAssoc(); + + /** + * Return the block size. + * @return the block size. + */ + unsigned + getBlockSize() const + { + return blkSize; + } + + /** + * Return the subblock size. In the case of BaseSetAssoc it is always + * the block size. + * @return The block size. + */ + unsigned + getSubBlockSize() const + { + return blkSize; + } + + /** + * Invalidate the given block. + * @param blk The block to invalidate. + */ + void invalidate(BlkType *blk) + { + assert(blk); + assert(blk->isValid()); + tagsInUse--; + assert(blk->srcMasterId < cache->system->maxMasters()); + occupancies[blk->srcMasterId]--; + blk->srcMasterId = Request::invldMasterId; + blk->task_id = ContextSwitchTaskId::Unknown; + blk->tickInserted = curTick(); + } + + /** + * Access block and update replacement data. May not succeed, in which case + * NULL pointer is returned. This has all the implications of a cache + * access and should only be used as such. Returns the access latency as a + * side effect. + * @param addr The address to find. + * @param is_secure True if the target memory space is secure. + * @param asid The address space ID. + * @param lat The access latency. + * @return Pointer to the cache block if found. + */ + BlkType* accessBlock(Addr addr, bool is_secure, Cycles &lat, + int context_src) + { + Addr tag = extractTag(addr); + int set = extractSet(addr); + BlkType *blk = sets[set].findBlk(tag, is_secure); + lat = hitLatency; + + // Access all tags in parallel, hence one in each way. The data side + // either accesses all blocks in parallel, or one block sequentially on + // a hit. Sequential access with a miss doesn't access data. + tagAccesses += assoc; + if (sequentialAccess) { + if (blk != NULL) { + dataAccesses += 1; + } + } else { + dataAccesses += assoc; + } + + if (blk != NULL) { + if (blk->whenReady > curTick() + && cache->ticksToCycles(blk->whenReady - curTick()) + > hitLatency) { + lat = cache->ticksToCycles(blk->whenReady - curTick()); + } + blk->refCount += 1; + } + + return blk; + } + + /** + * Finds the given address in the cache, do not update replacement data. + * i.e. This is a no-side-effect find of a block. + * @param addr The address to find. + * @param is_secure True if the target memory space is secure. + * @param asid The address space ID. + * @return Pointer to the cache block if found. + */ + BlkType* findBlock(Addr addr, bool is_secure) const; + + /** + * Find an invalid block to evict for the address provided. + * If there are no invalid blocks, this will return the block + * in the least-recently-used position. + * @param addr The addr to a find a replacement candidate for. + * @return The candidate block. + */ + BlkType* findVictim(Addr addr) const + { + BlkType *blk = NULL; + int set = extractSet(addr); + + // prefer to evict an invalid block + for (int i = 0; i < assoc; ++i) { + blk = sets[set].blks[i]; + if (!blk->isValid()) { + break; + } + } + + return blk; + } + + /** + * Insert the new block into the cache. + * @param pkt Packet holding the address to update + * @param blk The block to update. + */ + void insertBlock(PacketPtr pkt, BlkType *blk) + { + Addr addr = pkt->getAddr(); + MasterID master_id = pkt->req->masterId(); + uint32_t task_id = pkt->req->taskId(); + bool is_secure = pkt->isSecure(); + if (!blk->isTouched) { + tagsInUse++; + blk->isTouched = true; + if (!warmedUp && tagsInUse.value() >= warmupBound) { + warmedUp = true; + warmupCycle = curTick(); + } + } + + // If we're replacing a block that was previously valid update + // stats for it. This can't be done in findBlock() because a + // found block might not actually be replaced there if the + // coherence protocol says it can't be. + if (blk->isValid()) { + replacements[0]++; + totalRefs += blk->refCount; + ++sampledRefs; + blk->refCount = 0; + + // deal with evicted block + assert(blk->srcMasterId < cache->system->maxMasters()); + occupancies[blk->srcMasterId]--; + + blk->invalidate(); + } + + blk->isTouched = true; + // Set tag for new block. Caller is responsible for setting status. + blk->tag = extractTag(addr); + if (is_secure) + blk->status |= BlkSecure; + + // deal with what we are bringing in + assert(master_id < cache->system->maxMasters()); + occupancies[master_id]++; + blk->srcMasterId = master_id; + blk->task_id = task_id; + blk->tickInserted = curTick(); + + // We only need to write into one tag and one data block. + tagAccesses += 1; + dataAccesses += 1; + } + + /** + * Generate the tag from the given address. + * @param addr The address to get the tag from. + * @return The tag of the address. + */ + Addr extractTag(Addr addr) const + { + return (addr >> tagShift); + } + + /** + * Calculate the set index from the address. + * @param addr The address to get the set from. + * @return The set index of the address. + */ + int extractSet(Addr addr) const + { + return ((addr >> setShift) & setMask); + } + + /** + * Get the block offset from an address. + * @param addr The address to get the offset of. + * @return The block offset. + */ + int extractBlkOffset(Addr addr) const + { + return (addr & blkMask); + } + + /** + * Align an address to the block size. + * @param addr the address to align. + * @return The block address. + */ + Addr blkAlign(Addr addr) const + { + return (addr & ~(Addr)blkMask); + } + + /** + * Regenerate the block address from the tag. + * @param tag The tag of the block. + * @param set The set of the block. + * @return The block address. + */ + Addr regenerateBlkAddr(Addr tag, unsigned set) const + { + return ((tag << tagShift) | ((Addr)set << setShift)); + } + + /** + * Return the hit latency. + * @return the hit latency. + */ + Cycles getHitLatency() const + { + return hitLatency; + } + /** + *iterated through all blocks and clear all locks + *Needed to clear all lock tracking at once + */ + virtual void clearLocks(); + + /** + * Called at end of simulation to complete average block reference stats. + */ + virtual void cleanupRefs(); + + /** + * Print all tags used + */ + virtual std::string print() const; + + /** + * Called prior to dumping stats to compute task occupancy + */ + virtual void computeStats(); + + /** + * Visit each block in the tag store and apply a visitor to the + * block. + * + * The visitor should be a function (or object that behaves like a + * function) that takes a cache block reference as its parameter + * and returns a bool. A visitor can request the traversal to be + * stopped by returning false, returning true causes it to be + * called for the next block in the tag store. + * + * \param visitor Visitor to call on each block. + */ + template <typename V> + void forEachBlk(V &visitor) { + for (unsigned i = 0; i < numSets * assoc; ++i) { + if (!visitor(blks[i])) + return; + } + } +}; + +#endif // __MEM_CACHE_TAGS_BASESETASSOC_HH__ diff --git a/src/mem/cache/tags/lru.cc b/src/mem/cache/tags/lru.cc index 744d7224a..290d1bdd0 100644 --- a/src/mem/cache/tags/lru.cc +++ b/src/mem/cache/tags/lru.cc @@ -11,7 +11,7 @@ * unmodified and in its entirety in all distributions of the software, * modified or unmodified, in source code or in binary form. * - * Copyright (c) 2003-2005 The Regents of The University of Michigan + * Copyright (c) 2003-2005,2014 The Regents of The University of Michigan * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -42,292 +42,70 @@ /** * @file - * Definitions of LRU tag store. + * Definitions of a LRU tag store. */ -#include <string> - -#include "base/intmath.hh" -#include "debug/Cache.hh" #include "debug/CacheRepl.hh" #include "mem/cache/tags/lru.hh" #include "mem/cache/base.hh" -#include "sim/core.hh" - -using namespace std; LRU::LRU(const Params *p) - :BaseTags(p), assoc(p->assoc), - numSets(p->size / (p->block_size * p->assoc)), - sequentialAccess(p->sequential_access) + : BaseSetAssoc(p) { - // Check parameters - if (blkSize < 4 || !isPowerOf2(blkSize)) { - fatal("Block size must be at least 4 and a power of 2"); - } - if (numSets <= 0 || !isPowerOf2(numSets)) { - fatal("# of sets must be non-zero and a power of 2"); - } - if (assoc <= 0) { - fatal("associativity must be greater than zero"); - } - if (hitLatency <= 0) { - fatal("access latency must be greater than zero"); - } - - blkMask = blkSize - 1; - setShift = floorLog2(blkSize); - setMask = numSets - 1; - tagShift = setShift + floorLog2(numSets); - warmedUp = false; - /** @todo Make warmup percentage a parameter. */ - warmupBound = numSets * assoc; - - sets = new SetType[numSets]; - blks = new BlkType[numSets * assoc]; - // allocate data storage in one big chunk - numBlocks = numSets * assoc; - dataBlks = new uint8_t[numBlocks * blkSize]; - - unsigned blkIndex = 0; // index into blks array - for (unsigned i = 0; i < numSets; ++i) { - sets[i].assoc = assoc; - - sets[i].blks = new BlkType*[assoc]; - - // link in the data blocks - for (unsigned j = 0; j < assoc; ++j) { - // locate next cache block - BlkType *blk = &blks[blkIndex]; - blk->data = &dataBlks[blkSize*blkIndex]; - ++blkIndex; - - // invalidate new cache block - blk->invalidate(); - - //EGH Fix Me : do we need to initialize blk? - - // Setting the tag to j is just to prevent long chains in the hash - // table; won't matter because the block is invalid - blk->tag = j; - blk->whenReady = 0; - blk->isTouched = false; - blk->size = blkSize; - sets[i].blks[j]=blk; - blk->set = i; - } - } } -LRU::~LRU() -{ - delete [] dataBlks; - delete [] blks; - delete [] sets; -} - -LRU::BlkType* +BaseSetAssoc::BlkType* LRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, int master_id) { - Addr tag = extractTag(addr); - unsigned set = extractSet(addr); - BlkType *blk = sets[set].findBlk(tag, is_secure); - lat = hitLatency; - - // Access all tags in parallel, hence one in each way. The data side - // either accesses all blocks in parallel, or one block sequentially on - // a hit. Sequential access with a miss doesn't access data. - tagAccesses += assoc; - if (sequentialAccess) { - if (blk != NULL) { - dataAccesses += 1; - } - } else { - dataAccesses += assoc; - } + BlkType *blk = BaseSetAssoc::accessBlock(addr, is_secure, lat, master_id); if (blk != NULL) { // move this block to head of the MRU list - sets[set].moveToHead(blk); + sets[blk->set].moveToHead(blk); DPRINTF(CacheRepl, "set %x: moving blk %x (%s) to MRU\n", - set, regenerateBlkAddr(tag, set), is_secure ? "s" : "ns"); - if (blk->whenReady > curTick() - && cache->ticksToCycles(blk->whenReady - curTick()) > hitLatency) { - lat = cache->ticksToCycles(blk->whenReady - curTick()); - } - blk->refCount += 1; + blk->set, regenerateBlkAddr(blk->tag, blk->set), + is_secure ? "s" : "ns"); } return blk; } - -LRU::BlkType* -LRU::findBlock(Addr addr, bool is_secure) const -{ - Addr tag = extractTag(addr); - unsigned set = extractSet(addr); - BlkType *blk = sets[set].findBlk(tag, is_secure); - return blk; -} - -LRU::BlkType* -LRU::findVictim(Addr addr) +BaseSetAssoc::BlkType* +LRU::findVictim(Addr addr) const { - unsigned set = extractSet(addr); + int set = extractSet(addr); // grab a replacement candidate - BlkType *blk = sets[set].blks[assoc-1]; + BlkType *blk = sets[set].blks[assoc - 1]; if (blk->isValid()) { DPRINTF(CacheRepl, "set %x: selecting blk %x for replacement\n", set, regenerateBlkAddr(blk->tag, set)); } + return blk; } void LRU::insertBlock(PacketPtr pkt, BlkType *blk) { - Addr addr = pkt->getAddr(); - MasterID master_id = pkt->req->masterId(); - uint32_t task_id = pkt->req->taskId(); - bool is_secure = pkt->isSecure(); - if (!blk->isTouched) { - tagsInUse++; - blk->isTouched = true; - if (!warmedUp && tagsInUse.value() >= warmupBound) { - warmedUp = true; - warmupCycle = curTick(); - } - } - - // If we're replacing a block that was previously valid update - // stats for it. This can't be done in findBlock() because a - // found block might not actually be replaced there if the - // coherence protocol says it can't be. - if (blk->isValid()) { - replacements[0]++; - totalRefs += blk->refCount; - ++sampledRefs; - blk->refCount = 0; + BaseSetAssoc::insertBlock(pkt, blk); - // deal with evicted block - assert(blk->srcMasterId < cache->system->maxMasters()); - occupancies[blk->srcMasterId]--; - - blk->invalidate(); - } - - blk->isTouched = true; - // Set tag for new block. Caller is responsible for setting status. - blk->tag = extractTag(addr); - if (is_secure) - blk->status |= BlkSecure; - - // deal with what we are bringing in - assert(master_id < cache->system->maxMasters()); - occupancies[master_id]++; - blk->srcMasterId = master_id; - blk->task_id = task_id; - blk->tickInserted = curTick(); - - unsigned set = extractSet(addr); + int set = extractSet(pkt->getAddr()); sets[set].moveToHead(blk); - - // We only need to write into one tag and one data block. - tagAccesses += 1; - dataAccesses += 1; } void LRU::invalidate(BlkType *blk) { - assert(blk); - assert(blk->isValid()); - tagsInUse--; - assert(blk->srcMasterId < cache->system->maxMasters()); - occupancies[blk->srcMasterId]--; - blk->srcMasterId = Request::invldMasterId; - blk->task_id = ContextSwitchTaskId::Unknown; - blk->tickInserted = curTick(); + BaseSetAssoc::invalidate(blk); // should be evicted before valid blocks - unsigned set = blk->set; + int set = blk->set; sets[set].moveToTail(blk); } -void -LRU::clearLocks() -{ - for (int i = 0; i < numBlocks; i++){ - blks[i].clearLoadLocks(); - } -} - -LRU * +LRU* LRUParams::create() { return new LRU(this); } -std::string -LRU::print() const { - std::string cache_state; - for (unsigned i = 0; i < numSets; ++i) { - // link in the data blocks - for (unsigned j = 0; j < assoc; ++j) { - BlkType *blk = sets[i].blks[j]; - if (blk->isValid()) - cache_state += csprintf("\tset: %d block: %d %s\n", i, j, - blk->print()); - } - } - if (cache_state.empty()) - cache_state = "no valid tags\n"; - return cache_state; -} - -void -LRU::cleanupRefs() -{ - for (unsigned i = 0; i < numSets*assoc; ++i) { - if (blks[i].isValid()) { - totalRefs += blks[i].refCount; - ++sampledRefs; - } - } -} - -void -LRU::computeStats() -{ - for (unsigned i = 0; i < ContextSwitchTaskId::NumTaskId; ++i) { - occupanciesTaskId[i] = 0; - for (unsigned j = 0; j < 5; ++j) { - ageTaskId[i][j] = 0; - } - } - - for (unsigned i = 0; i < numSets * assoc; ++i) { - if (blks[i].isValid()) { - assert(blks[i].task_id < ContextSwitchTaskId::NumTaskId); - occupanciesTaskId[blks[i].task_id]++; - Tick age = curTick() - blks[i].tickInserted; - assert(age >= 0); - - int age_index; - if (age / SimClock::Int::us < 10) { // <10us - age_index = 0; - } else if (age / SimClock::Int::us < 100) { // <100us - age_index = 1; - } else if (age / SimClock::Int::ms < 1) { // <1ms - age_index = 2; - } else if (age / SimClock::Int::ms < 10) { // <10ms - age_index = 3; - } else - age_index = 4; // >10ms - - ageTaskId[blks[i].task_id][age_index]++; - } - } -} - diff --git a/src/mem/cache/tags/lru.hh b/src/mem/cache/tags/lru.hh index 121bdb292..a034dd6ab 100644 --- a/src/mem/cache/tags/lru.hh +++ b/src/mem/cache/tags/lru.hh @@ -11,7 +11,7 @@ * unmodified and in its entirety in all distributions of the software, * modified or unmodified, in source code or in binary form. * - * Copyright (c) 2003-2005 The Regents of The University of Michigan + * Copyright (c) 2003-2005,2014 The Regents of The University of Michigan * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -43,68 +43,21 @@ /** * @file * Declaration of a LRU tag store. + * The LRU tags guarantee that the true least-recently-used way in + * a set will always be evicted. */ #ifndef __MEM_CACHE_TAGS_LRU_HH__ #define __MEM_CACHE_TAGS_LRU_HH__ -#include <cassert> -#include <cstring> -#include <list> - -#include "mem/cache/tags/base.hh" -#include "mem/cache/tags/cacheset.hh" -#include "mem/cache/blk.hh" -#include "mem/packet.hh" +#include "mem/cache/tags/base_set_assoc.hh" #include "params/LRU.hh" -class BaseCache; - - -/** - * A LRU cache tag store. - * @sa \ref gem5MemorySystem "gem5 Memory System" - */ -class LRU : public BaseTags +class LRU : public BaseSetAssoc { public: - /** Typedef the block type used in this tag store. */ - typedef CacheBlk BlkType; - /** Typedef for a list of pointers to the local block class. */ - typedef std::list<BlkType*> BlkList; - /** Typedef the set type used in this tag store. */ - typedef CacheSet<CacheBlk> SetType; - - - protected: - /** The associativity of the cache. */ - const unsigned assoc; - /** The number of sets in the cache. */ - const unsigned numSets; - /** Whether tags and data are accessed sequentially. */ - const bool sequentialAccess; - - /** The cache sets. */ - SetType *sets; - - /** The cache blocks. */ - BlkType *blks; - /** The data blocks, 1 per cache block. */ - uint8_t *dataBlks; - - /** The amount to shift the address to get the set. */ - int setShift; - /** The amount to shift the address to get the tag. */ - int tagShift; - /** Mask out all bits that aren't part of the set index. */ - unsigned setMask; - /** Mask out all bits that aren't part of the block offset. */ - unsigned blkMask; - -public: - /** Convenience typedef. */ - typedef LRUParams Params; + typedef LRUParams Params; /** * Construct and initialize this tag store. @@ -114,172 +67,13 @@ public: /** * Destructor */ - virtual ~LRU(); - - /** - * Return the block size. - * @return the block size. - */ - unsigned - getBlockSize() const - { - return blkSize; - } + ~LRU() {} - /** - * Return the subblock size. In the case of LRU it is always the block - * size. - * @return The block size. - */ - unsigned - getSubBlockSize() const - { - return blkSize; - } - - /** - * Invalidate the given block. - * @param blk The block to invalidate. - */ - void invalidate(BlkType *blk); - - /** - * Access block and update replacement data. May not succeed, in which case - * NULL pointer is returned. This has all the implications of a cache - * access and should only be used as such. Returns the access latency as a side effect. - * @param addr The address to find. - * @param is_secure True if the target memory space is secure. - * @param asid The address space ID. - * @param lat The access latency. - * @return Pointer to the cache block if found. - */ BlkType* accessBlock(Addr addr, bool is_secure, Cycles &lat, int context_src); - - /** - * Finds the given address in the cache, do not update replacement data. - * i.e. This is a no-side-effect find of a block. - * @param addr The address to find. - * @param is_secure True if the target memory space is secure. - * @param asid The address space ID. - * @return Pointer to the cache block if found. - */ - BlkType* findBlock(Addr addr, bool is_secure) const; - - /** - * Find a block to evict for the address provided. - * @param addr The addr to a find a replacement candidate for. - * @return The candidate block. - */ - BlkType* findVictim(Addr addr); - - /** - * Insert the new block into the cache. For LRU this means inserting into - * the MRU position of the set. - * @param pkt Packet holding the address to update - * @param blk The block to update. - */ - void insertBlock(PacketPtr pkt, BlkType *blk); - - /** - * Generate the tag from the given address. - * @param addr The address to get the tag from. - * @return The tag of the address. - */ - Addr extractTag(Addr addr) const - { - return (addr >> tagShift); - } - - /** - * Calculate the set index from the address. - * @param addr The address to get the set from. - * @return The set index of the address. - */ - int extractSet(Addr addr) const - { - return ((addr >> setShift) & setMask); - } - - /** - * Get the block offset from an address. - * @param addr The address to get the offset of. - * @return The block offset. - */ - int extractBlkOffset(Addr addr) const - { - return (addr & blkMask); - } - - /** - * Align an address to the block size. - * @param addr the address to align. - * @return The block address. - */ - Addr blkAlign(Addr addr) const - { - return (addr & ~(Addr)blkMask); - } - - /** - * Regenerate the block address from the tag. - * @param tag The tag of the block. - * @param set The set of the block. - * @return The block address. - */ - Addr regenerateBlkAddr(Addr tag, unsigned set) const - { - return ((tag << tagShift) | ((Addr)set << setShift)); - } - - /** - * Return the hit latency. - * @return the hit latency. - */ - Cycles getHitLatency() const - { - return hitLatency; - } - /** - *iterated through all blocks and clear all locks - *Needed to clear all lock tracking at once - */ - virtual void clearLocks(); - - /** - * Called at end of simulation to complete average block reference stats. - */ - virtual void cleanupRefs(); - - /** - * Print all tags used - */ - virtual std::string print() const; - - /** - * Called prior to dumping stats to compute task occupancy - */ - virtual void computeStats(); - - /** - * Visit each block in the tag store and apply a visitor to the - * block. - * - * The visitor should be a function (or object that behaves like a - * function) that takes a cache block reference as its parameter - * and returns a bool. A visitor can request the traversal to be - * stopped by returning false, returning true causes it to be - * called for the next block in the tag store. - * - * \param visitor Visitor to call on each block. - */ - template <typename V> - void forEachBlk(V &visitor) { - for (unsigned i = 0; i < numSets * assoc; ++i) { - if (!visitor(blks[i])) - return; - } - } + BlkType* findVictim(Addr addr) const; + void insertBlock(PacketPtr pkt, BlkType *blk); + void invalidate(BlkType *blk); }; #endif // __MEM_CACHE_TAGS_LRU_HH__ diff --git a/src/mem/cache/tags/random_repl.cc b/src/mem/cache/tags/random_repl.cc new file mode 100644 index 000000000..77b379135 --- /dev/null +++ b/src/mem/cache/tags/random_repl.cc @@ -0,0 +1,89 @@ +/* + * Copyright (c) 2014 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: Anthony Gutierrez + */ + +/** + * @file + * Definitions of a random replacement tag store. + */ + +#include "base/random.hh" +#include "debug/CacheRepl.hh" +#include "mem/cache/tags/random_repl.hh" +#include "mem/cache/base.hh" + +RandomRepl::RandomRepl(const Params *p) + : BaseSetAssoc(p) + +{ +} + +BaseSetAssoc::BlkType* +RandomRepl::accessBlock(Addr addr, bool is_secure, Cycles &lat, int master_id) +{ + return BaseSetAssoc::accessBlock(addr, is_secure, lat, master_id); +} + +BaseSetAssoc::BlkType* +RandomRepl::findVictim(Addr addr) const +{ + BlkType *blk = BaseSetAssoc::findVictim(addr); + + // if all blocks are valid, pick a replacement at random + if (blk->isValid()) { + // find a random index within the bounds of the set + int idx = random_mt.random<int>(0, assoc - 1); + assert(idx < assoc); + assert(idx >= 0); + blk = sets[extractSet(addr)].blks[idx]; + + DPRINTF(CacheRepl, "set %x: selecting blk %x for replacement\n", + blk->set, regenerateBlkAddr(blk->tag, blk->set)); + } + + return blk; +} + +void +RandomRepl::insertBlock(PacketPtr pkt, BlkType *blk) +{ + BaseSetAssoc::insertBlock(pkt, blk); +} + +void +RandomRepl::invalidate(BlkType *blk) +{ + BaseSetAssoc::invalidate(blk); +} + +RandomRepl* +RandomReplParams::create() +{ + return new RandomRepl(this); +} diff --git a/src/mem/cache/tags/random_repl.hh b/src/mem/cache/tags/random_repl.hh new file mode 100644 index 000000000..7f2795379 --- /dev/null +++ b/src/mem/cache/tags/random_repl.hh @@ -0,0 +1,68 @@ +/* + * Copyright (c) 2014 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: Anthony Gutierrez + */ + +/** + * @file + * Declaration of a random replacement tag store. + * The RandomRepl tags first try to evict an invalid + * block. If no invalid blocks are found, a candidate + * for eviction is found at random. + */ + +#ifndef __MEM_CACHE_TAGS_RANDOM_REPL_HH__ +#define __MEM_CACHE_TAGS_RANDOM_REPL_HH__ + +#include "mem/cache/tags/base_set_assoc.hh" +#include "params/RandomRepl.hh" + +class RandomRepl : public BaseSetAssoc +{ + public: + /** Convenience typedef. */ + typedef RandomReplParams Params; + + /** + * Construct and initiliaze this tag store. + */ + RandomRepl(const Params *p); + + /** + * Destructor + */ + ~RandomRepl() {} + + BlkType* accessBlock(Addr addr, bool is_secure, Cycles &lat, + int context_src); + BlkType* findVictim(Addr addr) const; + void insertBlock(PacketPtr pkt, BlkType *blk); + void invalidate(BlkType *blk); +}; + +#endif // __MEM_CACHE_TAGS_RANDOM_REPL_HH__ |