diff options
author | Ron Dreslinski <rdreslin@umich.edu> | 2006-06-28 11:02:14 -0400 |
---|---|---|
committer | Ron Dreslinski <rdreslin@umich.edu> | 2006-06-28 11:02:14 -0400 |
commit | ed8564a6b9f0702a40995d95cc4da54de3d35462 (patch) | |
tree | 156901f9e5a2e92ddfa44eea664103de5d210aa7 /src/mem/cache/tags | |
parent | ecab4b426c949dad797df0bde1c0c120b4b5fb00 (diff) | |
download | gem5-ed8564a6b9f0702a40995d95cc4da54de3d35462.tar.xz |
Was having difficulty with merging the cache, reverted to an early version and will add back in the patches to make it work soon.
src/mem/cache/prefetch/tagged_prefetcher_impl.hh:
Trying to merge
src/mem/cache/base_cache.cc:
src/mem/cache/base_cache.hh:
src/mem/cache/cache.cc:
src/mem/cache/cache.hh:
src/mem/cache/cache_blk.hh:
src/mem/cache/cache_builder.cc:
src/mem/cache/cache_impl.hh:
src/mem/cache/coherence/coherence_protocol.cc:
src/mem/cache/coherence/coherence_protocol.hh:
src/mem/cache/coherence/simple_coherence.hh:
src/mem/cache/coherence/uni_coherence.cc:
src/mem/cache/coherence/uni_coherence.hh:
src/mem/cache/miss/blocking_buffer.cc:
src/mem/cache/miss/blocking_buffer.hh:
src/mem/cache/miss/miss_queue.cc:
src/mem/cache/miss/miss_queue.hh:
src/mem/cache/miss/mshr.cc:
src/mem/cache/miss/mshr.hh:
src/mem/cache/miss/mshr_queue.cc:
src/mem/cache/miss/mshr_queue.hh:
src/mem/cache/prefetch/base_prefetcher.cc:
src/mem/cache/prefetch/base_prefetcher.hh:
src/mem/cache/prefetch/ghb_prefetcher.cc:
src/mem/cache/prefetch/ghb_prefetcher.hh:
src/mem/cache/prefetch/stride_prefetcher.cc:
src/mem/cache/prefetch/stride_prefetcher.hh:
src/mem/cache/prefetch/tagged_prefetcher.hh:
src/mem/cache/tags/base_tags.cc:
src/mem/cache/tags/base_tags.hh:
src/mem/cache/tags/fa_lru.cc:
src/mem/cache/tags/fa_lru.hh:
src/mem/cache/tags/iic.cc:
src/mem/cache/tags/iic.hh:
src/mem/cache/tags/lru.cc:
src/mem/cache/tags/lru.hh:
src/mem/cache/tags/repl/gen.cc:
src/mem/cache/tags/repl/gen.hh:
src/mem/cache/tags/repl/repl.cc:
src/mem/cache/tags/repl/repl.hh:
src/mem/cache/tags/split.cc:
src/mem/cache/tags/split.hh:
src/mem/cache/tags/split_blk.hh:
src/mem/cache/tags/split_lifo.cc:
src/mem/cache/tags/split_lifo.hh:
src/mem/cache/tags/split_lru.cc:
src/mem/cache/tags/split_lru.hh:
Pulling an early version of the cache into the tree due to merging issues. Will apply patches and push.
--HG--
extra : convert_revision : 3276e5fb9a6272681a1690babf2b586dd0e1f380
Diffstat (limited to 'src/mem/cache/tags')
-rw-r--r-- | src/mem/cache/tags/base_tags.cc | 91 | ||||
-rw-r--r-- | src/mem/cache/tags/base_tags.hh | 143 | ||||
-rw-r--r-- | src/mem/cache/tags/fa_lru.cc | 334 | ||||
-rw-r--r-- | src/mem/cache/tags/fa_lru.hh | 346 | ||||
-rw-r--r-- | src/mem/cache/tags/iic.cc | 869 | ||||
-rw-r--r-- | src/mem/cache/tags/iic.hh | 574 | ||||
-rw-r--r-- | src/mem/cache/tags/lru.cc | 310 | ||||
-rw-r--r-- | src/mem/cache/tags/lru.hh | 327 | ||||
-rw-r--r-- | src/mem/cache/tags/repl/gen.cc | 277 | ||||
-rw-r--r-- | src/mem/cache/tags/repl/gen.hh | 247 | ||||
-rw-r--r-- | src/mem/cache/tags/repl/repl.cc | 43 | ||||
-rw-r--r-- | src/mem/cache/tags/repl/repl.hh | 129 | ||||
-rw-r--r-- | src/mem/cache/tags/split.cc | 478 | ||||
-rw-r--r-- | src/mem/cache/tags/split.hh | 335 | ||||
-rw-r--r-- | src/mem/cache/tags/split_blk.hh | 68 | ||||
-rw-r--r-- | src/mem/cache/tags/split_lifo.cc | 405 | ||||
-rw-r--r-- | src/mem/cache/tags/split_lifo.hh | 350 | ||||
-rw-r--r-- | src/mem/cache/tags/split_lru.cc | 331 | ||||
-rw-r--r-- | src/mem/cache/tags/split_lru.hh | 333 |
19 files changed, 5990 insertions, 0 deletions
diff --git a/src/mem/cache/tags/base_tags.cc b/src/mem/cache/tags/base_tags.cc new file mode 100644 index 000000000..153737300 --- /dev/null +++ b/src/mem/cache/tags/base_tags.cc @@ -0,0 +1,91 @@ +/* + * Copyright (c) 2003-2005 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 + * Ron Dreslinski + */ + +/** + * @file + * Definitions of BaseTags. + */ + +#include "mem/cache/tags/base_tags.hh" + +#include "mem/cache/base_cache.hh" +#include "cpu/smt.hh" //maxThreadsPerCPU +#include "sim/sim_exit.hh" + +using namespace std; + +void +BaseTags::setCache(BaseCache *_cache) +{ + cache = _cache; + objName = cache->name(); +} + +void +BaseTags::regStats(const string &name) +{ + using namespace Stats; + replacements + .init(maxThreadsPerCPU) + .name(name + ".replacements") + .desc("number of replacements") + .flags(total) + ; + + tagsInUse + .name(name + ".tagsinuse") + .desc("Cycle average of tags in use") + ; + + totalRefs + .name(name + ".total_refs") + .desc("Total number of references to valid blocks.") + ; + + sampledRefs + .name(name + ".sampled_refs") + .desc("Sample count of references to valid blocks.") + ; + + avgRefs + .name(name + ".avg_refs") + .desc("Average number of references to valid blocks.") + ; + + avgRefs = totalRefs/sampledRefs; + + warmupCycle + .name(name + ".warmup_cycle") + .desc("Cycle when the warmup percentage was hit.") + ; + + registerExitCallback(new BaseTagsCallback(this)); +} diff --git a/src/mem/cache/tags/base_tags.hh b/src/mem/cache/tags/base_tags.hh new file mode 100644 index 000000000..b7b0c7ef0 --- /dev/null +++ b/src/mem/cache/tags/base_tags.hh @@ -0,0 +1,143 @@ +/* + * Copyright (c) 2003-2005 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 + * Ron Dreslinski + */ + +/** + * @file + * Declaration of a common base class for cache tagstore objects. + */ + +#ifndef __BASE_TAGS_HH__ +#define __BASE_TAGS_HH__ + +#include <string> +#include "base/statistics.hh" +#include "base/callback.hh" + +class BaseCache; + +/** + * A common base class of Cache tagstore objects. + */ +class BaseTags +{ + protected: + /** Pointer to the parent cache. */ + BaseCache *cache; + + /** Local copy of the parent cache name. Used for DPRINTF. */ + std::string objName; + + /** + * The number of tags that need to be touched to meet the warmup + * percentage. + */ + int warmupBound; + /** Marked true when the cache is warmed up. */ + bool warmedUp; + + // Statistics + /** + * @addtogroup CacheStatistics + * @{ + */ + + /** Number of replacements of valid blocks per thread. */ + Stats::Vector<> replacements; + /** Per cycle average of the number of tags that hold valid data. */ + Stats::Average<> tagsInUse; + + /** The total number of references to a block before it is replaced. */ + Stats::Scalar<> totalRefs; + + /** + * The number of reference counts sampled. This is different from + * replacements because we sample all the valid blocks when the simulator + * exits. + */ + Stats::Scalar<> sampledRefs; + + /** + * Average number of references to a block before is was replaced. + * @todo This should change to an average stat once we have them. + */ + Stats::Formula avgRefs; + + /** The cycle that the warmup percentage was hit. */ + Stats::Scalar<> warmupCycle; + /** + * @} + */ + + public: + + /** + * Destructor. + */ + virtual ~BaseTags() {} + + /** + * Set the parent cache back pointer. Also copies the cache name to + * objName. + * @param _cache Pointer to parent cache. + */ + void setCache(BaseCache *_cache); + + /** + * Return the parent cache name. + * @return the parent cache name. + */ + const std::string &name() const + { + return objName; + } + + /** + * Register local statistics. + * @param name The name to preceed each statistic name. + */ + void regStats(const std::string &name); + + /** + * Average in the reference count for valid blocks when the simulation + * exits. + */ + virtual void cleanupRefs() {} +}; + +class BaseTagsCallback : public Callback +{ + BaseTags *tags; + public: + BaseTagsCallback(BaseTags *t) : tags(t) {} + virtual void process() { tags->cleanupRefs(); }; +}; + +#endif //__BASE_TAGS_HH__ diff --git a/src/mem/cache/tags/fa_lru.cc b/src/mem/cache/tags/fa_lru.cc new file mode 100644 index 000000000..66d91b35b --- /dev/null +++ b/src/mem/cache/tags/fa_lru.cc @@ -0,0 +1,334 @@ +/* + * Copyright (c) 2003-2005 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 a fully associative LRU tagstore. + */ + +#include <sstream> + +#include <assert.h> + +#include "mem/cache/tags/fa_lru.hh" +#include "base/intmath.hh" + +using namespace std; + +FALRU::FALRU(int _blkSize, int _size, int hit_latency) + : blkSize(_blkSize), size(_size), + numBlks(size/blkSize), hitLatency(hit_latency) +{ + if (!isPowerOf2(blkSize)) + fatal("cache block size (in bytes) `%d' must be a power of two", + blkSize); + if (!(hitLatency > 0)) + fatal("Access latency in cycles must be at least one cycle"); + if (!isPowerOf2(size)) + fatal("Cache Size must be power of 2 for now"); + + // Track all cache sizes from 128K up by powers of 2 + numCaches = floorLog2(size) - 17; + if (numCaches >0){ + cacheBoundaries = new FALRUBlk *[numCaches]; + cacheMask = (1 << numCaches) - 1; + } else { + cacheMask = 0; + } + + warmedUp = false; + warmupBound = size/blkSize; + + blks = new FALRUBlk[numBlks]; + head = &(blks[0]); + tail = &(blks[numBlks-1]); + + head->prev = NULL; + head->next = &(blks[1]); + head->inCache = cacheMask; + + tail->prev = &(blks[numBlks-2]); + tail->next = NULL; + tail->inCache = 0; + + int index = (1 << 17) / blkSize; + int j = 0; + int flags = cacheMask; + for (int i = 1; i < numBlks-1; i++) { + blks[i].inCache = flags; + if (i == index - 1){ + cacheBoundaries[j] = &(blks[i]); + flags &= ~ (1<<j); + ++j; + index = index << 1; + } + blks[i].prev = &(blks[i-1]); + blks[i].next = &(blks[i+1]); + blks[i].isTouched = false; + } + assert(j == numCaches); + assert(index == numBlks); + //assert(check()); +} + +void +FALRU::regStats(const string &name) +{ + using namespace Stats; + BaseTags::regStats(name); + hits + .init(numCaches+1) + .name(name + ".falru_hits") + .desc("The number of hits in each cache size.") + ; + misses + .init(numCaches+1) + .name(name + ".falru_misses") + .desc("The number of misses in each cache size.") + ; + accesses + .name(name + ".falru_accesses") + .desc("The number of accesses to the FA LRU cache.") + ; + + for (int i = 0; i < numCaches+1; ++i) { + stringstream size_str; + if (i < 3){ + size_str << (1<<(i+7)) <<"K"; + } else { + size_str << (1<<(i-3)) <<"M"; + } + + hits.subname(i, size_str.str()); + hits.subdesc(i, "Hits in a " + size_str.str() +" cache"); + misses.subname(i, size_str.str()); + misses.subdesc(i, "Misses in a " + size_str.str() +" cache"); + } +} + +FALRUBlk * +FALRU::hashLookup(Addr addr) const +{ + tagIterator iter = tagHash.find(addr); + if (iter != tagHash.end()) { + return (*iter).second; + } + return NULL; +} + +bool +FALRU::probe(int asid, Addr addr) const +{ + Addr blkAddr = blkAlign(addr); + FALRUBlk* blk = hashLookup(blkAddr); + return blk && blk->tag == blkAddr && blk->isValid(); +} + +void +FALRU::invalidateBlk(int asid, Addr addr) +{ + Addr blkAddr = blkAlign(addr); + FALRUBlk* blk = (*tagHash.find(blkAddr)).second; + if (blk) { + assert(blk->tag == blkAddr); + blk->status = 0; + blk->isTouched = false; + tagsInUse--; + } +} + +FALRUBlk* +FALRU::findBlock(Addr addr, int asid, int &lat, int *inCache) +{ + accesses++; + int tmp_in_cache = 0; + Addr blkAddr = blkAlign(addr); + FALRUBlk* blk = hashLookup(blkAddr); + + if (blk && blk->isValid()) { + assert(blk->tag == blkAddr); + tmp_in_cache = blk->inCache; + for (int i = 0; i < numCaches; i++) { + if (1<<i & blk->inCache) { + hits[i]++; + } else { + misses[i]++; + } + } + hits[numCaches]++; + if (blk != head){ + moveToHead(blk); + } + } else { + blk = NULL; + for (int i = 0; i < numCaches+1; ++i) { + misses[i]++; + } + } + if (inCache) { + *inCache = tmp_in_cache; + } + + lat = hitLatency; + //assert(check()); + return blk; +} + +FALRUBlk* +FALRU::findBlock(Packet * &pkt, int &lat, int *inCache) +{ + Addr addr = pkt->paddr; + + accesses++; + int tmp_in_cache = 0; + Addr blkAddr = blkAlign(addr); + FALRUBlk* blk = hashLookup(blkAddr); + + if (blk && blk->isValid()) { + assert(blk->tag == blkAddr); + tmp_in_cache = blk->inCache; + for (int i = 0; i < numCaches; i++) { + if (1<<i & blk->inCache) { + hits[i]++; + } else { + misses[i]++; + } + } + hits[numCaches]++; + if (blk != head){ + moveToHead(blk); + } + } else { + blk = NULL; + for (int i = 0; i < numCaches+1; ++i) { + misses[i]++; + } + } + if (inCache) { + *inCache = tmp_in_cache; + } + + lat = hitLatency; + //assert(check()); + return blk; +} + +FALRUBlk* +FALRU::findBlock(Addr addr, int asid) const +{ + Addr blkAddr = blkAlign(addr); + FALRUBlk* blk = hashLookup(blkAddr); + + if (blk && blk->isValid()) { + assert(blk->tag == blkAddr); + } else { + blk = NULL; + } + return blk; +} + +FALRUBlk* +FALRU::findReplacement(Packet * &pkt, PacketList* &writebacks, + BlkList &compress_blocks) +{ + FALRUBlk * blk = tail; + assert(blk->inCache == 0); + moveToHead(blk); + tagHash.erase(blk->tag); + tagHash[blkAlign(pkt->paddr)] = blk; + if (blk->isValid()) { + int thread_num = (blk->xc) ? blk->xc->getThreadNum() : 0; + replacements[thread_num]++; + } else { + tagsInUse++; + blk->isTouched = true; + if (!warmedUp && tagsInUse.value() >= warmupBound) { + warmedUp = true; + warmupCycle = curTick; + } + } + //assert(check()); + return blk; +} + +void +FALRU::moveToHead(FALRUBlk *blk) +{ + int updateMask = blk->inCache ^ cacheMask; + for (int i = 0; i < numCaches; i++){ + if ((1<<i) & updateMask) { + cacheBoundaries[i]->inCache &= ~(1<<i); + cacheBoundaries[i] = cacheBoundaries[i]->prev; + } else if (cacheBoundaries[i] == blk) { + cacheBoundaries[i] = blk->prev; + } + } + blk->inCache = cacheMask; + if (blk != head) { + if (blk == tail){ + assert(blk->next == NULL); + tail = blk->prev; + tail->next = NULL; + } else { + blk->prev->next = blk->next; + blk->next->prev = blk->prev; + } + blk->next = head; + blk->prev = NULL; + head->prev = blk; + head = blk; + } +} + +bool +FALRU::check() +{ + FALRUBlk* blk = head; + int size = 0; + int boundary = 1<<17; + int j = 0; + int flags = cacheMask; + while (blk) { + size += blkSize; + if (blk->inCache != flags) { + return false; + } + if (size == boundary && blk != tail) { + if (cacheBoundaries[j] != blk) { + return false; + } + flags &=~(1 << j); + boundary = boundary<<1; + ++j; + } + blk = blk->next; + } + return true; +} diff --git a/src/mem/cache/tags/fa_lru.hh b/src/mem/cache/tags/fa_lru.hh new file mode 100644 index 000000000..7855f8455 --- /dev/null +++ b/src/mem/cache/tags/fa_lru.hh @@ -0,0 +1,346 @@ +/* + * Copyright (c) 2003-2005 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 fully associative LRU tag store. + */ + +#ifndef __FA_LRU_HH__ +#define __FA_LRU_HH__ + +#include <list> + +#include "mem/cache/cache_blk.hh" +#include "mem/packet.hh" +#include "base/hashmap.hh" +#include "mem/cache/tags/base_tags.hh" + +/** + * A fully associative cache block. + */ +class FALRUBlk : public CacheBlk +{ +public: + /** The previous block in LRU order. */ + FALRUBlk *prev; + /** The next block in LRU order. */ + FALRUBlk *next; + /** Has this block been touched? */ + bool isTouched; + + /** + * A bit mask of the sizes of cache that this block is resident in. + * Each bit represents a power of 2 in MB size cache. + * If bit 0 is set, this block is in a 1MB cache + * If bit 2 is set, this block is in a 4MB cache, etc. + * There is one bit for each cache smaller than the full size (default + * 16MB). + */ + int inCache; +}; + +/** + * A fully associative LRU cache. Keeps statistics for accesses to a number of + * cache sizes at once. + */ +class FALRU : public BaseTags +{ + public: + /** Typedef the block type used in this class. */ + typedef FALRUBlk BlkType; + /** Typedef a list of pointers to the local block type. */ + typedef std::list<FALRUBlk*> BlkList; + protected: + /** The block size of the cache. */ + const int blkSize; + /** The size of the cache. */ + const int size; + /** The number of blocks in the cache. */ + const int numBlks; // calculated internally + /** The hit latency of the cache. */ + const int hitLatency; + + /** Array of pointers to blocks at the cache size boundaries. */ + FALRUBlk **cacheBoundaries; + /** A mask for the FALRUBlk::inCache bits. */ + int cacheMask; + /** The number of different size caches being tracked. */ + int numCaches; + + /** The cache blocks. */ + FALRUBlk *blks; + + /** The MRU block. */ + FALRUBlk *head; + /** The LRU block. */ + FALRUBlk *tail; + + /** Hash table type mapping addresses to cache block pointers. */ + typedef m5::hash_map<Addr, FALRUBlk *, m5::hash<Addr> > hash_t; + /** Iterator into the address hash table. */ + typedef hash_t::const_iterator tagIterator; + + /** The address hash table. */ + hash_t tagHash; + + /** + * Find the cache block for the given address. + * @param addr The address to find. + * @return The cache block of the address, if any. + */ + FALRUBlk * hashLookup(Addr addr) const; + + /** + * Move a cache block to the MRU position. + * @param blk The block to promote. + */ + void moveToHead(FALRUBlk *blk); + + /** + * Check to make sure all the cache boundaries are still where they should + * be. Used for debugging. + * @return True if everything is correct. + */ + bool check(); + + /** + * @defgroup FALRUStats Fully Associative LRU specific statistics + * The FA lru stack lets us track multiple cache sizes at once. These + * statistics track the hits and misses for different cache sizes. + * @{ + */ + + /** Hits in each cache size >= 128K. */ + Stats::Vector<> hits; + /** Misses in each cache size >= 128K. */ + Stats::Vector<> misses; + /** Total number of accesses. */ + Stats::Scalar<> accesses; + + /** + * @} + */ + +public: + /** + * Construct and initialize this cache tagstore. + * @param blkSize The block size of the cache. + * @param size The size of the cache. + * @param hit_latency The hit latency of the cache. + */ + FALRU(int blkSize, int size, int hit_latency); + + /** + * Register the stats for this object. + * @param name The name to prepend to the stats name. + */ + void regStats(const std::string &name); + + /** + * Return true if the address is found in the cache. + * @param asid The address space ID. + * @param addr The address to look for. + * @return True if the address is in the cache. + */ + bool probe(int asid, Addr addr) const; + + /** + * Invalidate the cache block that contains the given addr. + * @param asid The address space ID. + * @param addr The address to invalidate. + */ + void invalidateBlk(int asid, Addr addr); + + /** + * Find the block in the cache and update the replacement data. Returns + * the access latency and the in cache flags as a side effect + * @param addr The address to look for. + * @param asid The address space ID. + * @param lat The latency of the access. + * @param inCache The FALRUBlk::inCache flags. + * @return Pointer to the cache block. + */ + FALRUBlk* findBlock(Addr addr, int asid, int &lat, int *inCache = 0); + + /** + * Find the block in the cache and update the replacement data. Returns + * the access latency and the in cache flags as a side effect + * @param req The req whose block to find + * @param lat The latency of the access. + * @param inCache The FALRUBlk::inCache flags. + * @return Pointer to the cache block. + */ + FALRUBlk* findBlock(Packet * &pkt, int &lat, int *inCache = 0); + + /** + * Find the block in the cache, do not update the replacement data. + * @param addr The address to look for. + * @param asid The address space ID. + * @return Pointer to the cache block. + */ + FALRUBlk* findBlock(Addr addr, int asid) const; + + /** + * Find a replacement block for the address provided. + * @param req The request to a find a replacement candidate for. + * @param writebacks List for any writebacks to be performed. + * @param compress_blocks List of blocks to compress, for adaptive comp. + * @return The block to place the replacement in. + */ + FALRUBlk* findReplacement(Packet * &pkt, PacketList* & writebacks, + BlkList &compress_blocks); + + /** + * Return the hit latency of this cache. + * @return The hit latency. + */ + int getHitLatency() const + { + return hitLatency; + } + + /** + * Return the block size of this cache. + * @return The block size. + */ + int getBlockSize() + { + return blkSize; + } + + /** + * Return the subblock size of this cache, always the block size. + * @return The block size. + */ + int getSubBlockSize() + { + return blkSize; + } + + /** + * Align an address to the block size. + * @param addr the address to align. + * @return The aligned address. + */ + Addr blkAlign(Addr addr) const + { + return (addr & ~(Addr)(blkSize-1)); + } + + /** + * Generate the tag from the addres. For fully associative this is just the + * block address. + * @param addr The address to get the tag from. + * @param blk ignored here + * @return The tag. + */ + Addr extractTag(Addr addr, FALRUBlk *blk) const + { + return blkAlign(addr); + } + + /** + * Return the set of an address. Only one set in a fully associative cache. + * @param addr The address to get the set from. + * @return 0. + */ + int extractSet(Addr addr) const + { + return 0; + } + + /** + * Calculate the block offset of an address. + * @param addr the address to get the offset of. + * @return the block offset. + */ + int extractBlkOffset(Addr addr) const + { + return (addr & (Addr)(blkSize-1)); + } + + /** + * Regenerate the block address from the tag and the set. + * @param tag The tag of the block. + * @param set The set the block belongs to. + * @return the block address. + */ + Addr regenerateBlkAddr(Addr tag, int set) const + { + return (tag); + } + + /** + * Read the data out of the internal storage of a cache block. FALRU + * currently doesn't support data storage. + * @param blk The cache block to read. + * @param data The buffer to read the data into. + * @return The data from the cache block. + */ + void readData(FALRUBlk *blk, uint8_t *data) + { + } + + /** + * Write data into the internal storage of a cache block. FALRU + * currently doesn't support data storage. + * @param blk The cache block to be written. + * @param data The data to write. + * @param size The number of bytes to write. + * @param writebacks A list for any writebacks to be performed. May be + * needed when writing to a compressed block. + */ + void writeData(FALRUBlk *blk, uint8_t *data, int size, + PacketList* &writebacks) + { + } + + /** + * Unimplemented. Perform a cache block copy from block aligned addresses. + * @param source The block aligned source address. + * @param dest The block aligned destination adddress. + * @param asid The address space ID. + * @param writebacks List for any generated writeback requests. + */ + void doCopy(Addr source, Addr dest, int asid, PacketList* &writebacks) + { + } + + /** + * Unimplemented. + */ + void fixCopy(Packet * &pkt, PacketList* &writebacks) + { + } + +}; + +#endif diff --git a/src/mem/cache/tags/iic.cc b/src/mem/cache/tags/iic.cc new file mode 100644 index 000000000..a574adaa3 --- /dev/null +++ b/src/mem/cache/tags/iic.cc @@ -0,0 +1,869 @@ +/* + * Copyright (c) 2002-2005 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 the Indirect Index Cache tagstore. + */ + +#include <algorithm> +#include <string> +#include <vector> + +#include <math.h> + +#include "mem/cache/base_cache.hh" +#include "mem/cache/tags/iic.hh" +#include "base/intmath.hh" +#include "sim/root.hh" // for curTick + +#include "base/trace.hh" // for DPRINTF + + +using namespace std; + +/** Track the number of accesses to each cache set. */ +#define PROFILE_IIC 1 + +IIC::IIC(IIC::Params ¶ms) : + hashSets(params.numSets), blkSize(params.blkSize), assoc(params.assoc), + hitLatency(params.hitLatency), subSize(params.subblockSize), + numSub(blkSize/subSize), + trivialSize((floorLog2(params.size/subSize)*numSub)/8), + tagShift(floorLog2(blkSize)), blkMask(blkSize - 1), + subShift(floorLog2(subSize)), subMask(numSub - 1), + hashDelay(params.hashDelay), + numBlocks(params.size/subSize), + numTags(hashSets * assoc + params.size/blkSize -1), + numSecondary(params.size/blkSize), + tagNull(numTags), + primaryBound(hashSets * assoc) +{ + int i; + + // Check parameters + if (blkSize < 4 || !isPowerOf2(blkSize)) { + fatal("Block size must be at least 4 and a power of 2"); + } + if (hashSets <= 0 || !isPowerOf2(hashSets)) { + fatal("# of hashsets 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"); + } + if (numSub*subSize != blkSize) { + fatal("blocksize must be evenly divisible by subblock size"); + } + + // debug stuff + freeSecond = numSecondary; + + warmedUp = false; + warmupBound = params.size/blkSize; + + // Replacement Policy Initialization + repl = params.rp; + repl->setIIC(this); + + //last_miss_time = 0 + + // allocate data reference counters + dataReferenceCount = new int[numBlocks]; + memset(dataReferenceCount, 0, numBlocks*sizeof(int)); + + // Allocate storage for both internal data and block fast access data. + // We allocate it as one large chunk to reduce overhead and to make + // deletion easier. + int data_index = 0; + dataStore = new uint8_t[(numBlocks + numTags) * blkSize]; + dataBlks = new uint8_t*[numBlocks]; + for (i = 0; i < numBlocks; ++i) { + dataBlks[i] = &dataStore[data_index]; + freeDataBlock(i); + data_index += subSize; + } + + assert(data_index == numBlocks * subSize); + + // allocate and init tag store + tagStore = new IICTag[numTags]; + + int blkIndex = 0; + // allocate and init sets + sets = new IICSet[hashSets]; + for (i = 0; i < hashSets; ++i) { + sets[i].assoc = assoc; + sets[i].tags = new IICTag*[assoc]; + sets[i].chain_ptr = tagNull; + + for (int j = 0; j < assoc; ++j) { + IICTag *tag = &tagStore[blkIndex++]; + tag->chain_ptr = tagNull; + tag->data_ptr.resize(numSub); + tag->size = blkSize; + tag->trivialData = new uint8_t[trivialSize]; + tag->numData = 0; + sets[i].tags[j] = tag; + tag->set = i; + tag->data = &dataStore[data_index]; + data_index += blkSize; + } + } + + assert(blkIndex == primaryBound); + + for (i = primaryBound; i < tagNull; i++) { + tagStore[i].chain_ptr = i+1; + //setup data ptrs to subblocks + tagStore[i].data_ptr.resize(numSub); + tagStore[i].size = blkSize; + tagStore[i].trivialData = new uint8_t[trivialSize]; + tagStore[i].numData = 0; + tagStore[i].set = 0; + tagStore[i].data = &dataStore[data_index]; + data_index += blkSize; + } + freelist = primaryBound; +} + +IIC::~IIC() +{ + delete [] dataReferenceCount; + delete [] dataStore; + delete [] tagStore; + delete [] sets; +} + +/* register cache stats */ +void +IIC::regStats(const string &name) +{ + using namespace Stats; + + BaseTags::regStats(name); + + hitHashDepth.init(0, 20, 1); + missHashDepth.init(0, 20, 1); + setAccess.init(0, hashSets, 1); + + /** IIC Statistics */ + hitHashDepth + .name(name + ".hit_hash_depth_dist") + .desc("Dist. of Hash lookup depths") + .flags(pdf) + ; + + missHashDepth + .name(name + ".miss_hash_depth_dist") + .desc("Dist. of Hash lookup depths") + .flags(pdf) + ; + + repl->regStats(name); + + if (PROFILE_IIC) + setAccess + .name(name + ".set_access_dist") + .desc("Dist. of Accesses across sets") + .flags(pdf) + ; + + missDepthTotal + .name(name + ".miss_depth_total") + .desc("Total of miss depths") + ; + + hashMiss + .name(name + ".hash_miss") + .desc("Total of misses in hash table") + ; + + hitDepthTotal + .name(name + ".hit_depth_total") + .desc("Total of hit depths") + ; + + hashHit + .name(name + ".hash_hit") + .desc("Total of hites in hash table") + ; +} + +// probe cache for presence of given block. +bool +IIC::probe(int asid, Addr addr) const +{ + return (findBlock(addr,asid) != NULL); +} + +IICTag* +IIC::findBlock(Addr addr, int asid, int &lat) +{ + Addr tag = extractTag(addr); + unsigned set = hash(addr); + int set_lat; + + unsigned long chain_ptr; + + if (PROFILE_IIC) + setAccess.sample(set); + + IICTag *tag_ptr = sets[set].findTag(asid, tag, chain_ptr); + set_lat = 1; + if (tag_ptr == NULL && chain_ptr != tagNull) { + int secondary_depth; + tag_ptr = secondaryChain(asid, tag, chain_ptr, &secondary_depth); + set_lat += secondary_depth; + // set depth for statistics fix this later!!! egh + sets[set].depth = set_lat; + + if (tag_ptr != NULL) { + /* need to move tag into primary table */ + // need to preserve chain: fix this egh + sets[set].tags[assoc-1]->chain_ptr = tag_ptr->chain_ptr; + tagSwap(tag_ptr - tagStore, sets[set].tags[assoc-1] - tagStore); + tag_ptr = sets[set].findTag(asid, tag, chain_ptr); + assert(tag_ptr!=NULL); + } + + } + set_lat = set_lat * hashDelay + hitLatency; + if (tag_ptr != NULL) { + // IIC replacement: if this is not the first element of + // list, reorder + sets[set].moveToHead(tag_ptr); + + hitHashDepth.sample(sets[set].depth); + hashHit++; + hitDepthTotal += sets[set].depth; + tag_ptr->status |= BlkReferenced; + lat = set_lat; + if (tag_ptr->whenReady > curTick && tag_ptr->whenReady - curTick > set_lat) { + lat = tag_ptr->whenReady - curTick; + } + + tag_ptr->refCount += 1; + } + else { + // fall through: cache block not found, not a hit... + missHashDepth.sample(sets[set].depth); + hashMiss++; + missDepthTotal += sets[set].depth; + lat = set_lat; + } + return tag_ptr; +} + +IICTag* +IIC::findBlock(Packet * &pkt, int &lat) +{ + Addr addr = pkt->paddr; + int asid = pkt->req->asid; + + Addr tag = extractTag(addr); + unsigned set = hash(addr); + int set_lat; + + unsigned long chain_ptr; + + if (PROFILE_IIC) + setAccess.sample(set); + + IICTag *tag_ptr = sets[set].findTag(asid, tag, chain_ptr); + set_lat = 1; + if (tag_ptr == NULL && chain_ptr != tagNull) { + int secondary_depth; + tag_ptr = secondaryChain(asid, tag, chain_ptr, &secondary_depth); + set_lat += secondary_depth; + // set depth for statistics fix this later!!! egh + sets[set].depth = set_lat; + + if (tag_ptr != NULL) { + /* need to move tag into primary table */ + // need to preserve chain: fix this egh + sets[set].tags[assoc-1]->chain_ptr = tag_ptr->chain_ptr; + tagSwap(tag_ptr - tagStore, sets[set].tags[assoc-1] - tagStore); + tag_ptr = sets[set].findTag(asid, tag, chain_ptr); + assert(tag_ptr!=NULL); + } + + } + set_lat = set_lat * hashDelay + hitLatency; + if (tag_ptr != NULL) { + // IIC replacement: if this is not the first element of + // list, reorder + sets[set].moveToHead(tag_ptr); + + hitHashDepth.sample(sets[set].depth); + hashHit++; + hitDepthTotal += sets[set].depth; + tag_ptr->status |= BlkReferenced; + lat = set_lat; + if (tag_ptr->whenReady > curTick && tag_ptr->whenReady - curTick > set_lat) { + lat = tag_ptr->whenReady - curTick; + } + + tag_ptr->refCount += 1; + } + else { + // fall through: cache block not found, not a hit... + missHashDepth.sample(sets[set].depth); + hashMiss++; + missDepthTotal += sets[set].depth; + lat = set_lat; + } + return tag_ptr; +} + +IICTag* +IIC::findBlock(Addr addr, int asid) const +{ + Addr tag = extractTag(addr); + unsigned set = hash(addr); + + unsigned long chain_ptr; + + IICTag *tag_ptr = sets[set].findTag(asid, tag, chain_ptr); + if (tag_ptr == NULL && chain_ptr != tagNull) { + int secondary_depth; + tag_ptr = secondaryChain(asid, tag, chain_ptr, &secondary_depth); + } + return tag_ptr; +} + + +IICTag* +IIC::findReplacement(Packet * &pkt, PacketList* &writebacks, + BlkList &compress_blocks) +{ + DPRINTF(IIC, "Finding Replacement for %x\n", pkt->paddr); + unsigned set = hash(pkt->paddr); + IICTag *tag_ptr; + unsigned long *tmp_data = new unsigned long[numSub]; + + // Get a enough subblocks for a full cache line + for (int i = 0; i < numSub; ++i){ + tmp_data[i] = getFreeDataBlock(writebacks); + assert(dataReferenceCount[tmp_data[i]]==0); + } + + tag_ptr = getFreeTag(set, writebacks); + + tag_ptr->set = set; + for (int i=0; i< numSub; ++i) { + tag_ptr->data_ptr[i] = tmp_data[i]; + dataReferenceCount[tag_ptr->data_ptr[i]]++; + } + tag_ptr->numData = numSub; + assert(tag_ptr - tagStore < primaryBound); // make sure it is in primary + tag_ptr->chain_ptr = tagNull; + sets[set].moveToHead(tag_ptr); + delete [] tmp_data; + + list<unsigned long> tag_indexes; + repl->doAdvance(tag_indexes); + while (!tag_indexes.empty()) { + if (!tagStore[tag_indexes.front()].isCompressed()) { + compress_blocks.push_back(&tagStore[tag_indexes.front()]); + } + tag_indexes.pop_front(); + } + + tag_ptr->re = (void*)repl->add(tag_ptr-tagStore); + + return tag_ptr; +} + +void +IIC::freeReplacementBlock(PacketList* & writebacks) +{ + IICTag *tag_ptr; + unsigned long data_ptr; + /* consult replacement policy */ + tag_ptr = &tagStore[repl->getRepl()]; + assert(tag_ptr->isValid()); + + DPRINTF(Cache, "Replacing %x in IIC: %s\n", + regenerateBlkAddr(tag_ptr->tag,0), + tag_ptr->isModified() ? "writeback" : "clean"); + /* write back replaced block data */ + if (tag_ptr && (tag_ptr->isValid())) { + int thread_num = (tag_ptr->xc) ? tag_ptr->xc->getThreadNum() : 0; + replacements[thread_num]++; + totalRefs += tag_ptr->refCount; + ++sampledRefs; + tag_ptr->refCount = 0; + + if (tag_ptr->isModified()) { + Packet * writeback = + buildWritebackReq(regenerateBlkAddr(tag_ptr->tag, 0), + tag_ptr->req->asid, tag_ptr->xc, blkSize, + (cache->doData())?tag_ptr->data:0, + tag_ptr->size); + writebacks.push_back(writeback); + } + } + + // free the data blocks + for (int i = 0; i < tag_ptr->numData; ++i) { + data_ptr = tag_ptr->data_ptr[i]; + assert(dataReferenceCount[data_ptr]>0); + if (--dataReferenceCount[data_ptr] == 0) { + freeDataBlock(data_ptr); + } + } + freeTag(tag_ptr); +} + +unsigned long +IIC::getFreeDataBlock(PacketList* & writebacks) +{ + struct IICTag *tag_ptr; + unsigned long data_ptr; + + tag_ptr = NULL; + /* find data block */ + while (blkFreelist.empty()) { + freeReplacementBlock(writebacks); + } + + data_ptr = blkFreelist.front(); + blkFreelist.pop_front(); + DPRINTF(IICMore,"Found free data at %d\n",data_ptr); + return data_ptr; +} + + + +IICTag* +IIC::getFreeTag(int set, PacketList* & writebacks) +{ + unsigned long tag_index; + IICTag *tag_ptr; + // Add new tag + tag_ptr = sets[set].findFree(); + // if no free in primary, and secondary exists + if (!tag_ptr && numSecondary) { + // need to spill a tag into secondary storage + while (freelist == tagNull) { + // get replacements until one is in secondary + freeReplacementBlock(writebacks); + } + + tag_index = freelist; + freelist = tagStore[freelist].chain_ptr; + freeSecond--; + + assert(tag_index != tagNull); + tagSwap(tag_index, sets[set].tags[assoc-1] - tagStore); + tagStore[tag_index].chain_ptr = sets[set].chain_ptr; + sets[set].chain_ptr = tag_index; + + tag_ptr = sets[set].tags[assoc-1]; + } + DPRINTF(IICMore,"Found free tag at %d\n",tag_ptr - tagStore); + tagsInUse++; + if (!warmedUp && tagsInUse.value() >= warmupBound) { + warmedUp = true; + warmupCycle = curTick; + } + + return tag_ptr; +} + +void +IIC::freeTag(IICTag *tag_ptr) +{ + unsigned long tag_index, tmp_index; + // Fix tag_ptr + if (tag_ptr) { + // we have a tag to clear + DPRINTF(IICMore,"Freeing Tag for %x\n", + regenerateBlkAddr(tag_ptr->tag,0)); + tagsInUse--; + tag_ptr->status = 0; + tag_ptr->numData = 0; + tag_ptr->re = NULL; + tag_index = tag_ptr - tagStore; + if (tag_index >= primaryBound) { + // tag_ptr points to secondary store + assert(tag_index < tagNull); // remove this?? egh + if (tag_ptr->chain_ptr == tagNull) { + // need to fix chain list + unsigned tmp_set = hash(tag_ptr->tag << tagShift); + if (sets[tmp_set].chain_ptr == tag_index) { + sets[tmp_set].chain_ptr = tagNull; + } else { + tmp_index = sets[tmp_set].chain_ptr; + while (tmp_index != tagNull + && tagStore[tmp_index].chain_ptr != tag_index) { + tmp_index = tagStore[tmp_index].chain_ptr; + } + assert(tmp_index != tagNull); + tagStore[tmp_index].chain_ptr = tagNull; + } + tag_ptr->chain_ptr = freelist; + freelist = tag_index; + freeSecond++; + } else { + // copy next chained entry to this tag location + tmp_index = tag_ptr->chain_ptr; + tagSwap(tmp_index, tag_index); + tagStore[tmp_index].chain_ptr = freelist; + freelist = tmp_index; + freeSecond++; + } + } else { + // tag_ptr in primary hash table + assert(tag_index < primaryBound); + tag_ptr->status = 0; + unsigned tmp_set = hash(tag_ptr->tag << tagShift); + if (sets[tmp_set].chain_ptr != tagNull) { // collapse chain + tmp_index = sets[tmp_set].chain_ptr; + tagSwap(tag_index, tmp_index); + tagStore[tmp_index].chain_ptr = freelist; + freelist = tmp_index; + freeSecond++; + sets[tmp_set].chain_ptr = tag_ptr->chain_ptr; + sets[tmp_set].moveToTail(tag_ptr); + } + } + } +} + +void +IIC::freeDataBlock(unsigned long data_ptr) +{ + assert(dataReferenceCount[data_ptr] == 0); + DPRINTF(IICMore, "Freeing data at %d\n", data_ptr); + blkFreelist.push_front(data_ptr); +} + +/** Use a simple modulo hash. */ +#define SIMPLE_HASH 0 + +unsigned +IIC::hash(Addr addr) const { +#if SIMPLE_HASH + return extractTag(addr) % iic_hash_size; +#else + Addr tag, mask, x, y; + tag = extractTag(addr); + mask = hashSets-1; /* assumes iic_hash_size is a power of 2 */ + x = tag & mask; + y = (tag >> (int)(::log(hashSets)/::log(2))) & mask; + assert (x < hashSets && y < hashSets); + return x ^ y; +#endif +} + + +void +IICSet::moveToHead(IICTag *tag) +{ + if (tags[0] == tag) + 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; + IICTag *next = tag; + + do { + assert(i < assoc); + // swap blks[i] and next + IICTag *tmp = tags[i]; + tags[i] = next; + next = tmp; + ++i; + } while (next != tag); +} + +void +IICSet::moveToTail(IICTag *tag) +{ + if (tags[assoc-1] == tag) + 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 = assoc - 1; + IICTag *next = tag; + + do { + assert(i >= 0); + // swap blks[i] and next + IICTag *tmp = tags[i]; + tags[i] = next; + next = tmp; + --i; + } while (next != tag); +} + +void +IIC::tagSwap(unsigned long index1, unsigned long index2) +{ + DPRINTF(IIC,"Swapping tag[%d]=%x for tag[%d]=%x\n",index1, + tagStore[index1].tag<<tagShift, index2, + tagStore[index2].tag<<tagShift); + IICTag tmp_tag; + tmp_tag = tagStore[index1]; + tagStore[index1] = tagStore[index2]; + tagStore[index2] = tmp_tag; + if (tagStore[index1].isValid()) + repl->fixTag(tagStore[index1].re, index2, index1); + if (tagStore[index2].isValid()) + repl->fixTag(tagStore[index2].re, index1, index2); +} + + +IICTag * +IIC::secondaryChain(int asid, Addr tag, unsigned long chain_ptr, + int *_depth) const +{ + int depth = 0; + while (chain_ptr != tagNull) { + DPRINTF(IIC,"Searching secondary at %d for %x\n", chain_ptr, + tag<<tagShift); + if (tagStore[chain_ptr].tag == tag && + tagStore[chain_ptr].asid == asid && + (tagStore[chain_ptr].isValid())) { + *_depth = depth; + return &tagStore[chain_ptr]; + } + depth++; + chain_ptr = tagStore[chain_ptr].chain_ptr; + } + *_depth = depth; + return NULL; +} + +void +IIC::decompressBlock(unsigned long index) +{ + IICTag *tag_ptr = &tagStore[index]; + if (tag_ptr->isCompressed()) { + // decompress the data here. + } +} + +void +IIC::compressBlock(unsigned long index) +{ + IICTag *tag_ptr = &tagStore[index]; + if (!tag_ptr->isCompressed()) { + // Compress the data here. + } +} + +void +IIC::invalidateBlk(int asid, Addr addr) +{ + IICTag* tag_ptr = findBlock(addr, asid); + if (tag_ptr) { + for (int i = 0; i < tag_ptr->numData; ++i) { + dataReferenceCount[tag_ptr->data_ptr[i]]--; + if (dataReferenceCount[tag_ptr->data_ptr[i]] == 0) { + freeDataBlock(tag_ptr->data_ptr[i]); + } + } + repl->removeEntry(tag_ptr->re); + freeTag(tag_ptr); + } +} + +void +IIC::readData(IICTag *blk, uint8_t *data){ + assert(cache->doData()); + assert(blk->size <= trivialSize || blk->numData > 0); + int data_size = blk->size; + if (data_size > trivialSize) { + for (int i = 0; i < blk->numData; ++i){ + memcpy(data+i*subSize, + &(dataBlks[blk->data_ptr[i]][0]), + (data_size>subSize)?subSize:data_size); + data_size -= subSize; + } + } else { + memcpy(data,blk->trivialData,data_size); + } +} + +void +IIC::writeData(IICTag *blk, uint8_t *write_data, int size, + PacketList* & writebacks){ + assert(cache->doData()); + assert(size < blkSize || !blk->isCompressed()); + DPRINTF(IIC, "Writing %d bytes to %x\n", size, + blk->tag<<tagShift); + // Find the number of subblocks needed, (round up) + int num_subs = (size + (subSize -1))/subSize; + if (size <= trivialSize) { + num_subs = 0; + } + assert(num_subs <= numSub); + if (num_subs > blk->numData) { + // need to allocate more data blocks + for (int i = blk->numData; i < num_subs; ++i){ + blk->data_ptr[i] = getFreeDataBlock(writebacks); + dataReferenceCount[blk->data_ptr[i]] += 1; + } + } else if (num_subs < blk->numData){ + // can free data blocks + for (int i=num_subs; i < blk->numData; ++i){ + // decrement reference count and compare to zero + /** + * @todo + * Make this work with copying. + */ + if (--dataReferenceCount[blk->data_ptr[i]] == 0) { + freeDataBlock(blk->data_ptr[i]); + } + } + } + + blk->numData = num_subs; + blk->size = size; + assert(size <= trivialSize || blk->numData > 0); + if (size > trivialSize){ + for (int i = 0; i < blk->numData; ++i){ + memcpy(&dataBlks[blk->data_ptr[i]][0], write_data + i*subSize, + (size>subSize)?subSize:size); + size -= subSize; + } + } else { + memcpy(blk->trivialData,write_data,size); + } +} + + +/** + * @todo This code can break if the src is evicted to get a tag for the dest. + */ +void +IIC::doCopy(Addr source, Addr dest, int asid, PacketList* &writebacks) +{ + IICTag *dest_tag = findBlock(dest, asid); + + if (dest_tag) { + for (int i = 0; i < dest_tag->numData; ++i) { + if (--dataReferenceCount[dest_tag->data_ptr[i]] == 0) { + freeDataBlock(dest_tag->data_ptr[i]); + } + } + // Reset replacement entry + } else { + dest_tag = getFreeTag(hash(dest), writebacks); + dest_tag->re = (void*) repl->add(dest_tag - tagStore); + dest_tag->set = hash(dest); + dest_tag->tag = extractTag(dest); + dest_tag->req->asid = asid; + dest_tag->status = BlkValid | BlkWritable; + } + // Find the source tag here since it might move if we need to find a + // tag for the destination. + IICTag *src_tag = findBlock(source, asid); + assert(src_tag); + assert(!cache->doData() || src_tag->size <= trivialSize + || src_tag->numData > 0); + // point dest to source data and inc counter + for (int i = 0; i < src_tag->numData; ++i) { + dest_tag->data_ptr[i] = src_tag->data_ptr[i]; + ++dataReferenceCount[dest_tag->data_ptr[i]]; + } + + // Maintain fast access data. + memcpy(dest_tag->data, src_tag->data, blkSize); + + dest_tag->xc = src_tag->xc; + dest_tag->size = src_tag->size; + dest_tag->numData = src_tag->numData; + if (src_tag->numData == 0) { + // Data is stored in the trivial data, just copy it. + memcpy(dest_tag->trivialData, src_tag->trivialData, src_tag->size); + } + + dest_tag->status |= BlkDirty; + if (dest_tag->size < blkSize) { + dest_tag->status |= BlkCompressed; + } else { + dest_tag->status &= ~BlkCompressed; + } +} + +void +IIC::fixCopy(Packet * &pkt, PacketList* &writebacks) +{ + // if reference counter is greater than 1, do copy + // else do write + Addr blk_addr = blkAlign(pkt->paddr); + IICTag* blk = findBlock(blk_addr, pkt->req->asid); + + if (blk->numData > 0 && dataReferenceCount[blk->data_ptr[0]] != 1) { + // copy the data + // Mark the block as referenced so it doesn't get replaced. + blk->status |= BlkReferenced; + for (int i = 0; i < blk->numData; ++i){ + unsigned long new_data = getFreeDataBlock(writebacks); + // Need to refresh pointer + /** + * @todo Remove this refetch once we change IIC to pointer based + */ + blk = findBlock(blk_addr, pkt->req->asid); + assert(blk); + if (cache->doData()) { + memcpy(&(dataBlks[new_data][0]), + &(dataBlks[blk->data_ptr[i]][0]), + subSize); + } + dataReferenceCount[blk->data_ptr[i]]--; + dataReferenceCount[new_data]++; + blk->data_ptr[i] = new_data; + } + } +} + +void +IIC::cleanupRefs() +{ + for (int i = 0; i < numTags; ++i) { + if (tagStore[i].isValid()) { + totalRefs += tagStore[i].refCount; + ++sampledRefs; + } + } +} diff --git a/src/mem/cache/tags/iic.hh b/src/mem/cache/tags/iic.hh new file mode 100644 index 000000000..ef3f03c53 --- /dev/null +++ b/src/mem/cache/tags/iic.hh @@ -0,0 +1,574 @@ +/* + * Copyright (c) 2002-2005 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 the Indirect Index Cache (IIC) tags store. + */ + +#ifndef __IIC_HH__ +#define __IIC_HH__ + +#include <list> +#include <vector> + +#include "mem/cache/cache_blk.hh" +#include "mem/cache/tags/repl/repl.hh" +#include "mem/packet.hh" +#include "base/statistics.hh" +#include "mem/cache/tags/base_tags.hh" + +class BaseCache; // Forward declaration + +/** + * IIC cache blk. + */ +class IICTag : public CacheBlk +{ + public: + /** + * Copy the contents of the given IICTag into this one. + * @param rhs The tag to copy. + * @return const reference to this tag. + */ + const IICTag& operator=(const IICTag& rhs) + { + CacheBlk::operator=(rhs); + chain_ptr = rhs.chain_ptr; + re = rhs.re; + set = rhs.set; + trivialData = rhs.trivialData; + numData = rhs.numData; + data_ptr.clear(); + for (int i = 0; i < rhs.numData; ++i) { + data_ptr.push_back(rhs.data_ptr[i]); + } + return *this; + } + + /** Hash chain pointer into secondary store. */ + unsigned long chain_ptr; + /** Data array pointers for each subblock. */ + std::vector<unsigned long> data_ptr; + /** Replacement Entry pointer. */ + void *re; + /** + * An array to store small compressed data. Conceputally the same size + * as the unsused data array pointers. + */ + uint8_t *trivialData; + /** + * The number of allocated subblocks. + */ + int numData; +}; + +/** + * A hash set for the IIC primary lookup table. + */ +class IICSet{ + public: + /** The associativity of the primary table. */ + int assoc; + + /** The number of hash chains followed when finding the last block. */ + int depth; + /** The current number of blocks on the chain. */ + int size; + + /** Tag pointer into the secondary tag storage. */ + unsigned long chain_ptr; + + /** The LRU list of the primary table. MRU is at 0 index. */ + IICTag ** tags; + + /** + * Find the addr in this set, return the chain pointer to the secondary if + * it isn't found. + * @param asid The address space ID. + * @param tag The address to find. + * @param chain_ptr The chain pointer to start the search of the secondary + * @return Pointer to the tag, NULL if not found. + */ + IICTag* findTag(int asid, Addr tag, unsigned long &chain_ptr) + { + depth = 1; + for (int i = 0; i < assoc; ++i) { + if (tags[i]->tag == tag && tags[i]->isValid()) { + return tags[i]; + } + } + chain_ptr = this->chain_ptr; + return 0; + } + + /** + * Find an usused tag in this set. + * @return Pointer to the unused tag, NULL if none are free. + */ + IICTag* findFree() + { + for (int i = 0; i < assoc; ++i) { + if (!tags[i]->isValid()) { + return tags[i]; + } + } + return 0; + } + + /** + * Move a tag to the head of the LRU list + * @param tag The tag to move. + */ + void moveToHead(IICTag *tag); + + /** + * Move a tag to the tail (LRU) of the LRU list + * @param tag The tag to move. + */ + void moveToTail(IICTag *tag); +}; + +/** + * The IIC tag store. This is a hardware-realizable, fully-associative tag + * store that uses software replacement, e.g. Gen. + */ +class IIC : public BaseTags +{ + public: + /** Typedef of the block type used in this class. */ + typedef IICTag BlkType; + /** Typedef for list of pointers to the local block type. */ + typedef std::list<IICTag*> BlkList; + protected: + /** The number of set in the primary table. */ + const int hashSets; + /** The block size in bytes. */ + const int blkSize; + /** The associativity of the primary table. */ + const int assoc; + /** The base hit latency. */ + const int hitLatency; + /** The subblock size, used for compression. */ + const int subSize; + + /** The number of subblocks */ + const int numSub; + /** The number of bytes used by data pointers */ + const int trivialSize; + + /** The amount to shift address to get the tag. */ + const int tagShift; + /** The mask to get block offset bits. */ + const unsigned blkMask; + + /** The amount to shift to get the subblock number. */ + const int subShift; + /** The mask to get the correct subblock number. */ + const unsigned subMask; + + /** The latency of a hash lookup. */ + const int hashDelay; + /** The number of data blocks. */ + const int numBlocks; + /** The total number of tags in primary and secondary. */ + const int numTags; + /** The number of tags in the secondary tag store. */ + const int numSecondary; + + /** The Null tag pointer. */ + const int tagNull; + /** The last tag in the primary table. */ + const int primaryBound; + + /** All of the tags */ + IICTag *tagStore; + /** + * Pointer to the head of the secondary freelist (maintained with chain + * pointers. + */ + unsigned long freelist; + /** + * The data block freelist. + */ + std::list<unsigned long> blkFreelist; + + /** The primary table. */ + IICSet *sets; + + /** The replacement policy. */ + Repl *repl; + + /** An array of data reference counters. */ + int *dataReferenceCount; + + /** The data blocks. */ + uint8_t *dataStore; + + /** Storage for the fast access data of each cache block. */ + uint8_t **dataBlks; + + /** + * Count of the current number of free secondary tags. + * Used for debugging. + */ + int freeSecond; + + // IIC Statistics + /** + * @addtogroup IICStatistics IIC Statistics + * @{ + */ + + /** Hash hit depth of cache hits. */ + Stats::Distribution<> hitHashDepth; + /** Hash depth for cache misses. */ + Stats::Distribution<> missHashDepth; + /** Count of accesses to each hash set. */ + Stats::Distribution<> setAccess; + + /** The total hash depth for every miss. */ + Stats::Scalar<> missDepthTotal; + /** The total hash depth for all hits. */ + Stats::Scalar<> hitDepthTotal; + /** The number of hash misses. */ + Stats::Scalar<> hashMiss; + /** The number of hash hits. */ + Stats::Scalar<> hashHit; + /** @} */ + + public: + /** + * Collection of parameters for the IIC. + */ + class Params { + public: + /** The size in bytes of the cache. */ + int size; + /** The number of sets in the primary table. */ + int numSets; + /** The block size in bytes. */ + int blkSize; + /** The associativity of the primary table. */ + int assoc; + /** The number of cycles for each hash lookup. */ + int hashDelay; + /** The number of cycles to read the data. */ + int hitLatency; + /** The replacement policy. */ + Repl *rp; + /** The subblock size in bytes. */ + int subblockSize; + }; + + /** + * Construct and initialize this tag store. + * @param params The IIC parameters. + * @todo + * Should make a way to have less tags in the primary than blks in the + * cache. Also should be able to specify number of secondary blks. + */ + IIC(Params ¶ms); + + /** + * Destructor. + */ + virtual ~IIC(); + + /** + * Register the statistics. + * @param name The name to prepend to the statistic descriptions. + */ + void regStats(const std::string &name); + + /** + * Regenerate the block address from the tag. + * @param tag The tag of the block. + * @param set Not needed for the iic. + * @return The block address. + */ + Addr regenerateBlkAddr(Addr tag, int set) { + return (((Addr)tag << tagShift)); + } + + /** + * Return the block size. + * @return The block size. + */ + int getBlockSize() + { + return blkSize; + } + + /** + * Return the subblock size. + * @return The subblock size. + */ + int getSubBlockSize() + { + return subSize; + } + + /** + * Return the hit latency. + * @return the hit latency. + */ + int getHitLatency() const + { + return hitLatency; + } + + /** + * Generate the tag from the address. + * @param addr The address to a get a tag for. + * @param blk Ignored here. + * @return the tag. + */ + Addr extractTag(Addr addr, IICTag *blk) const + { + return (addr >> tagShift); + } + + /** + * Generate the tag from the address. + * @param addr The address to a get a tag for. + * @return the tag. + */ + Addr extractTag(Addr addr) const + { + return (addr >> tagShift); + } + + /** + * Return the set, always 0 for IIC. + * @return 0. + */ + int extractSet(Addr addr) const + { + return 0; + } + + /** + * Get the block offset of an address. + * @param addr The address to get the offset of. + * @return the block offset of the address. + */ + 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); + } + + /** + * Check for the address in the tagstore. + * @param asid The address space ID. + * @param addr The address to find. + * @return true if it is found. + */ + bool probe(int asid, Addr addr) const; + + /** + * Swap the position of two tags. + * @param index1 The first tag location. + * @param index2 The second tag location. + */ + void tagSwap(unsigned long index1, unsigned long index2); + + /** + * Clear the reference bit of the tag and return its old value. + * @param index The pointer of the tag to manipulate. + * @return The previous state of the reference bit. + */ + bool clearRef(unsigned long index) + { + bool tmp = tagStore[index].isReferenced(); + tagStore[index].status &= ~BlkReferenced; + return tmp; + } + + /** + * Decompress a block if it is compressed. + * @param index The tag store index for the block to uncompress. + */ + void decompressBlock(unsigned long index); + + /** + * Try and compress a block if it is not already compressed. + * @param index The tag store index for the block to compress. + */ + void compressBlock(unsigned long index); + + /** + * Invalidate the block containing the address. + * @param asid The address space ID. + * @param addr The address to invalidate. + */ + void invalidateBlk(int asid, Addr addr); + + /** + * Find the block and update the replacement data. This call also returns + * the access latency as a side effect. + * @param addr The address to find. + * @param asid The address space ID. + * @param lat The access latency. + * @return A pointer to the block found, if any. + */ + IICTag* findBlock(Addr addr, int asid, int &lat); + + /** + * Find the block and update the replacement data. This call also returns + * the access latency as a side effect. + * @param req The req whose block to find + * @param lat The access latency. + * @return A pointer to the block found, if any. + */ + IICTag* findBlock(Packet * &pkt, int &lat); + + /** + * Find the block, do not update the replacement data. + * @param addr The address to find. + * @param asid The address space ID. + * @return A pointer to the block found, if any. + */ + IICTag* findBlock(Addr addr, int asid) const; + + /** + * Find a replacement block for the address provided. + * @param req The request to a find a replacement candidate for. + * @param writebacks List for any writebacks to be performed. + * @param compress_blocks List of blocks to compress, for adaptive comp. + * @return The block to place the replacement in. + */ + IICTag* findReplacement(Packet * &pkt, PacketList* &writebacks, + BlkList &compress_blocks); + + /** + * Read the data from the internal storage of the given cache block. + * @param blk The block to read the data from. + * @param data The buffer to read the data into. + * @return The cache block's data. + */ + void readData(IICTag *blk, uint8_t *data); + + /** + * Write the data into the internal storage of the given cache block. + * @param blk The block to write to. + * @param data The data to write. + * @param size The number of bytes to write. + * @param writebacks A list for any writebacks to be performed. May be + * needed when writing to a compressed block. + */ + void writeData(IICTag *blk, uint8_t *data, int size, + PacketList* & writebacks); + + /** + * Perform a block aligned copy from the source address to the destination. + * @param source The block-aligned source address. + * @param dest The block-aligned destination address. + * @param asid The address space DI. + * @param writebacks List for any generated writeback requests. + */ + void doCopy(Addr source, Addr dest, int asid, PacketList* &writebacks); + + /** + * If a block is currently marked copy on write, copy it before writing. + * @param req The write request. + * @param writebacks List for any generated writeback requests. + */ + void fixCopy(Packet * &pkt, PacketList* &writebacks); + + /** + * Called at end of simulation to complete average block reference stats. + */ + virtual void cleanupRefs(); +private: + /** + * Return the hash of the address. + * @param addr The address to hash. + * @return the hash of the address. + */ + unsigned hash(Addr addr) const; + + /** + * Search for a block in the secondary tag store. Returns the number of + * hash lookups as a side effect. + * @param asid The address space ID. + * @param tag The tag to match. + * @param chain_ptr The first entry to search. + * @param depth The number of hash lookups made while searching. + * @return A pointer to the block if found. + */ + IICTag *secondaryChain(int asid, Addr tag, unsigned long chain_ptr, + int *depth) const; + + /** + * Free the resources associated with the next replacement block. + * @param writebacks A list of any writebacks to perform. + */ + void freeReplacementBlock(PacketList* & writebacks); + + /** + * Return the pointer to a free data block. + * @param writebacks A list of any writebacks to perform. + * @return A pointer to a free data block. + */ + unsigned long getFreeDataBlock(PacketList* & writebacks); + + /** + * Get a free tag in the given hash set. + * @param set The hash set to search. + * @param writebacks A list of any writebacks to perform. + * @return a pointer to a free tag. + */ + IICTag* getFreeTag(int set, PacketList* & writebacks); + + /** + * Free the resources associated with the given tag. + * @param tag_ptr The tag to free. + */ + void freeTag(IICTag *tag_ptr); + + /** + * Mark the given data block as being available. + * @param data_ptr The data block to free. + */ + void freeDataBlock(unsigned long data_ptr); +}; +#endif // __IIC_HH__ + diff --git a/src/mem/cache/tags/lru.cc b/src/mem/cache/tags/lru.cc new file mode 100644 index 000000000..0fe88fd08 --- /dev/null +++ b/src/mem/cache/tags/lru.cc @@ -0,0 +1,310 @@ +/* + * Copyright (c) 2003-2005 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 LRU tag store. + */ + +#include <string> + +#include "mem/cache/base_cache.hh" +#include "base/intmath.hh" +#include "mem/cache/tags/lru.hh" +#include "sim/root.hh" + +using namespace std; + +LRUBlk* +CacheSet::findBlk(int asid, 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(int _numSets, int _blkSize, int _assoc, int _hit_latency) : + numSets(_numSets), blkSize(_blkSize), assoc(_assoc), hitLatency(_hit_latency) +{ + // 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"); + } + + LRUBlk *blk; + int i, j, blkIndex; + + 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 CacheSet[numSets]; + blks = new LRUBlk[numSets * assoc]; + // allocate data storage in one big chunk + dataBlks = new uint8_t[numSets*assoc*blkSize]; + + blkIndex = 0; // index into blks array + for (i = 0; i < numSets; ++i) { + sets[i].assoc = assoc; + + sets[i].blks = new LRUBlk*[assoc]; + + // link in the data blocks + for (j = 0; j < assoc; ++j) { + // locate next cache block + blk = &blks[blkIndex]; + blk->data = &dataBlks[blkSize*blkIndex]; + ++blkIndex; + + // invalidate new cache block + blk->status = 0; + + //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->req->asid = -1; + blk->isTouched = false; + blk->size = blkSize; + sets[i].blks[j]=blk; + blk->set = i; + } + } +} + +LRU::~LRU() +{ + delete [] dataBlks; + delete [] blks; + delete [] sets; +} + +// probe cache for presence of given block. +bool +LRU::probe(int asid, Addr addr) const +{ + // return(findBlock(Read, addr, asid) != 0); + Addr tag = extractTag(addr); + unsigned myset = extractSet(addr); + + LRUBlk *blk = sets[myset].findBlk(asid, tag); + + return (blk != NULL); // true if in cache +} + +LRUBlk* +LRU::findBlock(Addr addr, int asid, int &lat) +{ + Addr tag = extractTag(addr); + unsigned set = extractSet(addr); + LRUBlk *blk = sets[set].findBlk(asid, tag); + lat = hitLatency; + if (blk != NULL) { + // move this block to head of the MRU list + sets[set].moveToHead(blk); + if (blk->whenReady > curTick + && blk->whenReady - curTick > hitLatency) { + lat = blk->whenReady - curTick; + } + blk->refCount += 1; + } + + return blk; +} + +LRUBlk* +LRU::findBlock(Packet * &pkt, int &lat) +{ + Addr addr = pkt->paddr; + int asid = pkt->req->asid; + + Addr tag = extractTag(addr); + unsigned set = extractSet(addr); + LRUBlk *blk = sets[set].findBlk(asid, tag); + lat = hitLatency; + if (blk != NULL) { + // move this block to head of the MRU list + sets[set].moveToHead(blk); + if (blk->whenReady > curTick + && blk->whenReady - curTick > hitLatency) { + lat = blk->whenReady - curTick; + } + blk->refCount += 1; + } + + return blk; +} + +LRUBlk* +LRU::findBlock(Addr addr, int asid) const +{ + Addr tag = extractTag(addr); + unsigned set = extractSet(addr); + LRUBlk *blk = sets[set].findBlk(asid, tag); + return blk; +} + +LRUBlk* +LRU::findReplacement(Packet * &pkt, PacketList* &writebacks, + BlkList &compress_blocks) +{ + unsigned set = extractSet(pkt->paddr); + // grab a replacement candidate + LRUBlk *blk = sets[set].blks[assoc-1]; + sets[set].moveToHead(blk); + if (blk->isValid()) { + int thread_num = (blk->xc) ? blk->xc->getThreadNum() : 0; + replacements[thread_num]++; + totalRefs += blk->refCount; + ++sampledRefs; + blk->refCount = 0; + } else if (!blk->isTouched) { + tagsInUse++; + blk->isTouched = true; + if (!warmedUp && tagsInUse.value() >= warmupBound) { + warmedUp = true; + warmupCycle = curTick; + } + } + + return blk; +} + +void +LRU::invalidateBlk(int asid, Addr addr) +{ + LRUBlk *blk = findBlock(addr, asid); + if (blk) { + blk->status = 0; + blk->isTouched = false; + tagsInUse--; + } +} + +void +LRU::doCopy(Addr source, Addr dest, int asid, PacketList* &writebacks) +{ + assert(source == blkAlign(source)); + assert(dest == blkAlign(dest)); + LRUBlk *source_blk = findBlock(source, asid); + assert(source_blk); + LRUBlk *dest_blk = findBlock(dest, asid); + if (dest_blk == NULL) { + // Need to do a replacement + Packet * pkt = new Packet(); + pkt->paddr = dest; + BlkList dummy_list; + dest_blk = findReplacement(pkt, writebacks, dummy_list); + if (dest_blk->isValid() && dest_blk->isModified()) { + // Need to writeback data. + pkt = buildWritebackReq(regenerateBlkAddr(dest_blk->tag, + dest_blk->set), + dest_blk->req->asid, + dest_blk->xc, + blkSize, + (cache->doData())?dest_blk->data:0, + dest_blk->size); + writebacks.push_back(pkt); + } + dest_blk->tag = extractTag(dest); + dest_blk->req->asid = asid; + /** + * @todo Do we need to pass in the execution context, or can we + * assume its the same? + */ + assert(source_blk->xc); + dest_blk->xc = source_blk->xc; + } + /** + * @todo Can't assume the status once we have coherence on copies. + */ + + // Set this block as readable, writeable, and dirty. + dest_blk->status = 7; + if (cache->doData()) { + memcpy(dest_blk->data, source_blk->data, blkSize); + } +} + +void +LRU::cleanupRefs() +{ + for (int i = 0; i < numSets*assoc; ++i) { + if (blks[i].isValid()) { + totalRefs += blks[i].refCount; + ++sampledRefs; + } + } +} diff --git a/src/mem/cache/tags/lru.hh b/src/mem/cache/tags/lru.hh new file mode 100644 index 000000000..9b4a55777 --- /dev/null +++ b/src/mem/cache/tags/lru.hh @@ -0,0 +1,327 @@ +/* + * Copyright (c) 2003-2005 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 LRU tag store. + */ + +#ifndef __LRU_HH__ +#define __LRU_HH__ + +#include <list> + +#include "mem/cache/cache_blk.hh" // base class +#include "mem/packet.hh" // for inlined functions +#include <assert.h> +#include "mem/cache/tags/base_tags.hh" + +class BaseCache; + +/** + * 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(int asid, 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. + */ +class LRU : public BaseTags +{ + public: + /** Typedef the block type used in this tag store. */ + typedef LRUBlk BlkType; + /** Typedef for a list of pointers to the local block class. */ + typedef std::list<LRUBlk*> BlkList; + protected: + /** The number of sets in the cache. */ + const int numSets; + /** The number of bytes in a block. */ + const int blkSize; + /** The associativity of the cache. */ + const int assoc; + /** The hit latency. */ + const int hitLatency; + + /** The cache sets. */ + CacheSet *sets; + + /** The cache blocks. */ + LRUBlk *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: + /** + * Construct and initialize this tag store. + * @param _numSets The number of sets in the cache. + * @param _blkSize The number of bytes in a block. + * @param _assoc The associativity of the cache. + * @param _hit_latency The latency in cycles for a hit. + */ + LRU(int _numSets, int _blkSize, int _assoc, int _hit_latency); + + /** + * Destructor + */ + virtual ~LRU(); + + /** + * Return the block size. + * @return the block size. + */ + int getBlockSize() + { + return blkSize; + } + + /** + * Return the subblock size. In the case of LRU it is always the block + * size. + * @return The block size. + */ + int getSubBlockSize() + { + return blkSize; + } + + /** + * Search for the address in the cache. + * @param asid The address space ID. + * @param addr The address to find. + * @return True if the address is in the cache. + */ + bool probe(int asid, Addr addr) const; + + /** + * Invalidate the block containing the given address. + * @param asid The address space ID. + * @param addr The address to invalidate. + */ + void invalidateBlk(int asid, Addr addr); + + /** + * Finds the given address in the cache and update replacement data. + * Returns the access latency as a side effect. + * @param req The request whose block to find. + * @param lat The access latency. + * @return Pointer to the cache block if found. + */ + LRUBlk* findBlock(Packet * &pkt, int &lat); + + /** + * Finds the given address in the cache and update replacement data. + * Returns the access latency as a side effect. + * @param addr The address to find. + * @param asid The address space ID. + * @param lat The access latency. + * @return Pointer to the cache block if found. + */ + LRUBlk* findBlock(Addr addr, int asid, int &lat); + + /** + * Finds the given address in the cache, do not update replacement data. + * @param addr The address to find. + * @param asid The address space ID. + * @return Pointer to the cache block if found. + */ + LRUBlk* findBlock(Addr addr, int asid) const; + + /** + * Find a replacement block for the address provided. + * @param req The request to a find a replacement candidate for. + * @param writebacks List for any writebacks to be performed. + * @param compress_blocks List of blocks to compress, for adaptive comp. + * @return The block to place the replacement in. + */ + LRUBlk* findReplacement(Packet * &pkt, PacketList* &writebacks, + BlkList &compress_blocks); + + /** + * 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); + } + + /** + * Generate the tag from the given address. + * @param addr The address to get the tag from. + * @param blk Ignored. + * @return The tag of the address. + */ + Addr extractTag(Addr addr, LRUBlk *blk) 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. + */ + int getHitLatency() const + { + return hitLatency; + } + + /** + * Read the data out of the internal storage of the given cache block. + * @param blk The cache block to read. + * @param data The buffer to read the data into. + * @return The cache block's data. + */ + void readData(LRUBlk *blk, uint8_t *data) + { + memcpy(data, blk->data, blk->size); + } + + /** + * Write data into the internal storage of the given cache block. Since in + * LRU does not store data differently this just needs to update the size. + * @param blk The cache block to write. + * @param data The data to write. + * @param size The number of bytes to write. + * @param writebacks A list for any writebacks to be performed. May be + * needed when writing to a compressed block. + */ + void writeData(LRUBlk *blk, uint8_t *data, int size, + PacketList* & writebacks) + { + assert(size <= blkSize); + blk->size = size; + } + + /** + * Perform a block aligned copy from the source address to the destination. + * @param source The block-aligned source address. + * @param dest The block-aligned destination address. + * @param asid The address space DI. + * @param writebacks List for any generated writeback requests. + */ + void doCopy(Addr source, Addr dest, int asid, PacketList* &writebacks); + + /** + * No impl. + */ + void fixCopy(Packet * &pkt, PacketList* &writebacks) + { + } + + /** + * Called at end of simulation to complete average block reference stats. + */ + virtual void cleanupRefs(); +}; + +#endif diff --git a/src/mem/cache/tags/repl/gen.cc b/src/mem/cache/tags/repl/gen.cc new file mode 100644 index 000000000..ec1c2aaf3 --- /dev/null +++ b/src/mem/cache/tags/repl/gen.cc @@ -0,0 +1,277 @@ +/* + * Copyright (c) 2002-2005 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 + * Steve Reinhardt + */ + +/** + * @file + * Definitions of the Generational replacement policy. + */ + +#include <string> + +#include "base/misc.hh" +#include "mem/cache/tags/iic.hh" +#include "mem/cache/tags/repl/gen.hh" +#include "sim/builder.hh" +#include "sim/host.hh" + +using namespace std; + +GenRepl::GenRepl(const string &_name, + int _num_pools, + int _fresh_res, + int _pool_res) // fix this, should be set by cache + : Repl(_name) +{ + num_pools = _num_pools; + fresh_res = _fresh_res; + pool_res = _pool_res; + num_entries = 0; + num_pool_entries = 0; + misses = 0; + pools = new GenPool[num_pools+1]; +} + +GenRepl::~GenRepl() +{ + delete [] pools; +} + +unsigned long +GenRepl::getRepl() +{ + unsigned long tmp; + GenReplEntry *re; + int i; + int num_seen = 0; + if (!(num_pool_entries>0)) { + fatal("No blks available to replace"); + } + num_entries--; + num_pool_entries--; + for (i = 0; i < num_pools; i++) { + while ((re = pools[i].pop())) { + num_seen++; + // Remove invalidated entries + if (!re->valid) { + delete re; + continue; + } + if (iic->clearRef(re->tag_ptr)) { + pools[(((i+1)== num_pools)? i :i+1)].push(re, misses); + } + else { + tmp = re->tag_ptr; + delete re; + + repl_pool.sample(i); + + return tmp; + } + } + } + fatal("No replacement found"); + return 0xffffffff; +} + +unsigned long * +GenRepl::getNRepl(int n) +{ + unsigned long *tmp; + GenReplEntry *re; + int i; + if (!(num_pool_entries>(n-1))) { + fatal("Not enough blks available to replace"); + } + num_entries -= n; + num_pool_entries -= n; + tmp = new unsigned long[n]; /* array of cache_blk pointers */ + int blk_index = 0; + for (i = 0; i < num_pools && blk_index < n; i++) { + while (blk_index < n && (re = pools[i].pop())) { + // Remove invalidated entries + if (!re->valid) { + delete re; + continue; + } + if (iic->clearRef(re->tag_ptr)) { + pools[(((i+1)== num_pools)? i :i+1)].push(re, misses); + } + else { + tmp[blk_index] = re->tag_ptr; + blk_index++; + delete re; + repl_pool.sample(i); + } + } + } + if (blk_index >= n) + return tmp; + /* search the fresh pool */ + + fatal("No N replacements found"); + return NULL; +} + +void +GenRepl::doAdvance(std::list<unsigned long> &demoted) +{ + int i; + int num_seen = 0; + GenReplEntry *re; + misses++; + for (i=0; i<num_pools; i++) { + while (misses-pools[i].oldest > pool_res && (re = pools[i].pop())!=NULL) { + if (iic->clearRef(re->tag_ptr)) { + pools[(((i+1)== num_pools)? i :i+1)].push(re, misses); + /** @todo Not really demoted, but use it for now. */ + demoted.push_back(re->tag_ptr); + advance_pool.sample(i); + } + else { + pools[(((i-1)<0)?i:i-1)].push(re, misses); + demoted.push_back(re->tag_ptr); + demote_pool.sample(i); + } + } + num_seen += pools[i].size; + } + while (misses-pools[num_pools].oldest > fresh_res + && (re = pools[num_pools].pop())!=NULL) { + num_pool_entries++; + if (iic->clearRef(re->tag_ptr)) { + pools[num_pools/2].push(re, misses); + /** @todo Not really demoted, but use it for now. */ + demoted.push_back(re->tag_ptr); + advance_pool.sample(num_pools); + } + else { + pools[num_pools/2-1].push(re, misses); + demoted.push_back(re->tag_ptr); + demote_pool.sample(num_pools); + } + } +} + +void* +GenRepl::add(unsigned long tag_index) +{ + GenReplEntry *re = new GenReplEntry; + re->tag_ptr = tag_index; + re->valid = true; + pools[num_pools].push(re, misses); + num_entries++; + return (void*)re; +} + +void +GenRepl::regStats(const string name) +{ + using namespace Stats; + + /** GEN statistics */ + repl_pool + .init(0, 16, 1) + .name(name + ".repl_pool_dist") + .desc("Dist. of Repl. across pools") + .flags(pdf) + ; + + advance_pool + .init(0, 16, 1) + .name(name + ".advance_pool_dist") + .desc("Dist. of Repl. across pools") + .flags(pdf) + ; + + demote_pool + .init(0, 16, 1) + .name(name + ".demote_pool_dist") + .desc("Dist. of Repl. across pools") + .flags(pdf) + ; +} + +int +GenRepl::fixTag(void* _re, unsigned long old_index, unsigned long new_index) +{ + GenReplEntry *re = (GenReplEntry*)_re; + assert(re->valid); + if (re->tag_ptr == old_index) { + re->tag_ptr = new_index; + return 1; + } + fatal("Repl entry: tag ptrs do not match"); + return 0; +} + +bool +GenRepl::findTagPtr(unsigned long index) +{ + for (int i = 0; i < num_pools + 1; ++i) { + list<GenReplEntry*>::const_iterator iter = pools[i].entries.begin(); + list<GenReplEntry*>::const_iterator end = pools[i].entries.end(); + for (; iter != end; ++iter) { + if ((*iter)->valid && (*iter)->tag_ptr == index) { + return true; + } + } + } + return false; +} + +#ifndef DOXYGEN_SHOULD_SKIP_THIS + +BEGIN_DECLARE_SIM_OBJECT_PARAMS(GenRepl) + + Param<int> num_pools; + Param<int> fresh_res; + Param<int> pool_res; + +END_DECLARE_SIM_OBJECT_PARAMS(GenRepl) + + +BEGIN_INIT_SIM_OBJECT_PARAMS(GenRepl) + + INIT_PARAM(num_pools, "capacity in bytes"), + INIT_PARAM(fresh_res, "associativity"), + INIT_PARAM(pool_res, "block size in bytes") + +END_INIT_SIM_OBJECT_PARAMS(GenRepl) + + +CREATE_SIM_OBJECT(GenRepl) +{ + return new GenRepl(getInstanceName(), num_pools, fresh_res, pool_res); +} + +REGISTER_SIM_OBJECT("GenRepl", GenRepl) + +#endif // DOXYGEN_SHOULD_SKIP_THIS diff --git a/src/mem/cache/tags/repl/gen.hh b/src/mem/cache/tags/repl/gen.hh new file mode 100644 index 000000000..c1ceb3f4e --- /dev/null +++ b/src/mem/cache/tags/repl/gen.hh @@ -0,0 +1,247 @@ +/* + * Copyright (c) 2002-2005 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 + * Declarations of generational replacement policy + */ + +#ifndef ___GEN_HH__ +#define __GEN_HH__ + +#include <list> + +#include "base/statistics.hh" +#include "mem/cache/tags/repl/repl.hh" + +/** + * Generational Replacement entry. + */ +class GenReplEntry +{ + public: + /** Valid flag, used to quickly invalidate bogus entries. */ + bool valid; + /** The difference between this entry and the previous in the pool. */ + int delta; + /** Pointer to the corresponding tag in the IIC. */ + unsigned long tag_ptr; +}; + +/** + * Generational replacement pool + */ +class GenPool +{ + public: + /** The time the last entry was added. */ + Tick newest; + /** The time the oldest entry was added. */ + Tick oldest; + /** List of the replacement entries in this pool. */ + std::list<GenReplEntry*> entries; + + /** The number of entries in this pool. */ + int size; + + /** + * Simple constructor. + */ + GenPool() { + newest = 0; + oldest = 0; + size = 0; + } + + /** + * Add an entry to this pool. + * @param re The entry to add. + * @param now The current time. + */ + void push(GenReplEntry *re, Tick now) { + ++size; + if (!entries.empty()) { + re->delta = now - newest; + newest = now; + } else { + re->delta = 0; + newest = oldest = now; + } + entries.push_back(re); + } + + /** + * Remove an entry from the pool. + * @return The entry at the front of the list. + */ + GenReplEntry* pop() { + GenReplEntry *tmp = NULL; + if (!entries.empty()) { + --size; + tmp = entries.front(); + entries.pop_front(); + oldest += tmp->delta; + } + return tmp; + } + + /** + * Return the entry at the front of the list. + * @return the entry at the front of the list. + */ + GenReplEntry* top() { + return entries.front(); + } + + /** + * Destructor. + */ + ~GenPool() { + while (!entries.empty()) { + GenReplEntry *tmp = entries.front(); + entries.pop_front(); + delete tmp; + } + } +}; + +/** + * Generational replacement policy for use with the IIC. + * @todo update to use STL and for efficiency + */ +class GenRepl : public Repl +{ + public: + /** The array of pools. */ + GenPool *pools; + /** The number of pools. */ + int num_pools; + /** The amount of time to stay in the fresh pool. */ + int fresh_res; + /** The amount of time to stay in the normal pools. */ + int pool_res; + /** The maximum number of entries */ + int num_entries; + /** The number of entries currently in the pools. */ + int num_pool_entries; + /** The number of misses. Used as the internal time. */ + Tick misses; + + // Statistics + + /** + * @addtogroup CacheStatistics + * @{ + */ + /** The number of replacements from each pool. */ + Stats::Distribution<> repl_pool; + /** The number of advances out of each pool. */ + Stats::Distribution<> advance_pool; + /** The number of demotions from each pool. */ + Stats::Distribution<> demote_pool; + /** + * @} + */ + + /** + * Constructs and initializes this replacement policy. + * @param name The name of the policy. + * @param num_pools The number of pools to use. + * @param fresh_res The amount of time to wait in the fresh pool. + * @param pool_res The amount of time to wait in the normal pools. + */ + GenRepl(const std::string &name, int num_pools, + int fresh_res, int pool_res); + + /** + * Destructor. + */ + ~GenRepl(); + + /** + * Returns the tag pointer of the cache block to replace. + * @return The tag to replace. + */ + virtual unsigned long getRepl(); + + /** + * Return an array of N tag pointers to replace. + * @param n The number of tag pointer to return. + * @return An array of tag pointers to replace. + */ + virtual unsigned long *getNRepl(int n); + + /** + * Update replacement data + */ + virtual void doAdvance(std::list<unsigned long> &demoted); + + /** + * Add a tag to the replacement policy and return a pointer to the + * replacement entry. + * @param tag_index The tag to add. + * @return The replacement entry. + */ + virtual void* add(unsigned long tag_index); + + /** + * Register statistics. + * @param name The name to prepend to statistic descriptions. + */ + virtual void regStats(const std::string name); + + /** + * Update the tag pointer to when the tag moves. + * @param re The replacement entry of the tag. + * @param old_index The old tag pointer. + * @param new_index The new tag pointer. + * @return 1 if successful, 0 otherwise. + */ + virtual int fixTag(void *re, unsigned long old_index, + unsigned long new_index); + + /** + * Remove this entry from the replacement policy. + * @param re The replacement entry to remove + */ + virtual void removeEntry(void *re) + { + ((GenReplEntry*)re)->valid = false; + } + + protected: + /** + * Debug function to verify that there is only one repl entry per tag. + * @param index The tag index to check. + */ + bool findTagPtr(unsigned long index); +}; + +#endif /* __GEN_HH__ */ diff --git a/src/mem/cache/tags/repl/repl.cc b/src/mem/cache/tags/repl/repl.cc new file mode 100644 index 000000000..ce781eb9f --- /dev/null +++ b/src/mem/cache/tags/repl/repl.cc @@ -0,0 +1,43 @@ +/* + * Copyright (c) 2002-2005 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 + * Nathan Binkert + */ + +/** + * Definitions of the base replacement class. + */ + +#include "sim/param.hh" +#include "mem/cache/tags/repl/repl.hh" + +#ifndef DOXYGEN_SHOULD_SKIP_THIS + +DEFINE_SIM_OBJECT_CLASS_NAME("Repl", Repl) + +#endif //DOXYGEN_SHOULD_SKIP_THIS diff --git a/src/mem/cache/tags/repl/repl.hh b/src/mem/cache/tags/repl/repl.hh new file mode 100644 index 000000000..7c289a5c1 --- /dev/null +++ b/src/mem/cache/tags/repl/repl.hh @@ -0,0 +1,129 @@ +/* + * Copyright (c) 2002-2005 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 + * Steve Reinhardt + * Nathan Binkert + */ + +/** + * @file + * Declaration of a base replacement policy class. + */ + +#ifndef __REPL_HH__ +#define __REPL_HH__ + +#include <string> +#include <list> + +#include "cpu/smt.hh" +#include "sim/host.hh" +#include "sim/sim_object.hh" + + +class IIC; + +/** + * A pure virtual base class that defines the interface of a replacement + * policy. + */ +class Repl : public SimObject +{ + public: + /** Pointer to the IIC using this policy. */ + IIC *iic; + + /** + * Construct and initialize this polixy. + * @param name The instance name of this policy. + */ + Repl (const std::string &name) + : SimObject(name) + { + iic = NULL; + } + + /** + * Set the back pointer to the IIC. + * @param iic_ptr Pointer to the IIC. + */ + void setIIC(IIC *iic_ptr) + { + iic = iic_ptr; + } + + /** + * Returns the tag pointer of the cache block to replace. + * @return The tag to replace. + */ + virtual unsigned long getRepl() = 0; + + /** + * Return an array of N tag pointers to replace. + * @param n The number of tag pointer to return. + * @return An array of tag pointers to replace. + */ + virtual unsigned long *getNRepl(int n) = 0; + + /** + * Update replacement data + */ + virtual void doAdvance(std::list<unsigned long> &demoted) = 0; + + /** + * Add a tag to the replacement policy and return a pointer to the + * replacement entry. + * @param tag_index The tag to add. + * @return The replacement entry. + */ + virtual void* add(unsigned long tag_index) = 0; + + /** + * Register statistics. + * @param name The name to prepend to statistic descriptions. + */ + virtual void regStats(const std::string name) = 0; + + /** + * Update the tag pointer to when the tag moves. + * @param re The replacement entry of the tag. + * @param old_index The old tag pointer. + * @param new_index The new tag pointer. + * @return 1 if successful, 0 otherwise. + */ + virtual int fixTag(void *re, unsigned long old_index, + unsigned long new_index) = 0; + + /** + * Remove this entry from the replacement policy. + * @param re The replacement entry to remove + */ + virtual void removeEntry(void *re) = 0; +}; + +#endif /* SMT_REPL_HH */ diff --git a/src/mem/cache/tags/split.cc b/src/mem/cache/tags/split.cc new file mode 100644 index 000000000..9d9036abb --- /dev/null +++ b/src/mem/cache/tags/split.cc @@ -0,0 +1,478 @@ +/* + * Copyright (c) 2004-2005 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 + * Definitions of split cache tag store. + */ + +#include <string> +#include <iostream> +#include <fstream> + +#include "base/cprintf.hh" +#include "base/intmath.hh" +#include "base/output.hh" +#include "base/trace.hh" +#include "mem/cache/base_cache.hh" +#include "mem/cache/tags/split.hh" +#include "mem/cache/tags/split_lifo.hh" +#include "mem/cache/tags/split_lru.hh" + + +using namespace std; +using namespace TheISA; + +// create and initialize a partitioned cache structure +Split::Split(int _numSets, int _blkSize, int total_ways, int LRU1_assoc, + bool _lifo, bool _two_queue, int _hit_latency) : + numSets(_numSets), blkSize(_blkSize), lifo(_lifo), hitLatency(_hit_latency) +{ + DPRINTF(Split, "new split cache!!\n"); + + DPRINTF(Split, "lru has %d numSets, %d blkSize, %d assoc, and %d hit_latency\n", + numSets, blkSize, LRU1_assoc, hitLatency); + + lru = new SplitLRU(_numSets, _blkSize, LRU1_assoc, _hit_latency, 1); + + if (total_ways - LRU1_assoc == 0) { + lifo_net = NULL; + lru_net = NULL; + } else { + if (lifo) { + DPRINTF(Split, "Other partition is a LIFO with size %d in bytes. it gets %d ways\n", + (total_ways - LRU1_assoc)*_numSets*_blkSize, (total_ways - LRU1_assoc)); + lifo_net = new SplitLIFO(_blkSize, (total_ways - LRU1_assoc)*_numSets*_blkSize, + (total_ways - LRU1_assoc), _hit_latency, _two_queue, 2); + lru_net = NULL; + } + else { + DPRINTF(Split, "other LRU gets %d ways\n", total_ways - LRU1_assoc); + lru_net = new SplitLRU(_numSets, _blkSize, total_ways - LRU1_assoc, _hit_latency, 2); + lifo_net = NULL; + } + } + + blkMask = blkSize - 1; + + if (!isPowerOf2(total_ways)) + warn("total cache ways/columns %d should be power of 2", + total_ways); + + warmedUp = false; + /** @todo Make warmup percentage a parameter. */ + warmupBound = numSets * total_ways; + +} + +Split::~Split() +{ + delete lru; + if (lifo) + delete lifo_net; + else + delete lru_net; +} + +void +Split::regStats(const string &name) +{ + using namespace Stats; + + BaseTags::regStats(name); + + usedEvictDist.init(0,3000,40); + unusedEvictDist.init(0,3000,40); + useByCPUCycleDist.init(0,35,1); + + nic_repl + .name(name + ".nic_repl") + .desc("number of replacements in the nic partition") + .precision(0) + ; + + cpu_repl + .name(name + ".cpu_repl") + .desc("number of replacements in the cpu partition") + .precision(0) + ; + + lru->regStats(name + ".lru"); + + if (lifo && lifo_net) { + lifo_net->regStats(name + ".lifo_net"); + } else if (lru_net) { + lru_net->regStats(name + ".lru_net"); + } + + nicUsedWhenEvicted + .name(name + ".nicUsedWhenEvicted") + .desc("number of NIC blks that were used before evicted") + ; + + nicUsedTotLatency + .name(name + ".nicUsedTotLatency") + .desc("total cycles before eviction of used NIC blks") + ; + + nicUsedTotEvicted + .name(name + ".nicUsedTotEvicted") + .desc("total number of used NIC blks evicted") + ; + + nicUsedAvgLatency + .name(name + ".nicUsedAvgLatency") + .desc("avg number of cycles a used NIC blk is in cache") + .precision(0) + ; + nicUsedAvgLatency = nicUsedTotLatency / nicUsedTotEvicted; + + usedEvictDist + .name(name + ".usedEvictDist") + .desc("distribution of used NIC blk eviction times") + .flags(pdf | cdf) + ; + + nicUnusedWhenEvicted + .name(name + ".nicUnusedWhenEvicted") + .desc("number of NIC blks that were unused when evicted") + ; + + nicUnusedTotLatency + .name(name + ".nicUnusedTotLatency") + .desc("total cycles before eviction of unused NIC blks") + ; + + nicUnusedTotEvicted + .name(name + ".nicUnusedTotEvicted") + .desc("total number of unused NIC blks evicted") + ; + + nicUnusedAvgLatency + .name(name + ".nicUnusedAvgLatency") + .desc("avg number of cycles an unused NIC blk is in cache") + .precision(0) + ; + nicUnusedAvgLatency = nicUnusedTotLatency / nicUnusedTotEvicted; + + unusedEvictDist + .name(name + ".unusedEvictDist") + .desc("distribution of unused NIC blk eviction times") + .flags(pdf | cdf) + ; + + nicUseByCPUCycleTotal + .name(name + ".nicUseByCPUCycleTotal") + .desc("total latency of NIC blks til usage time") + ; + + nicBlksUsedByCPU + .name(name + ".nicBlksUsedByCPU") + .desc("total number of NIC blks used") + ; + + nicAvgUsageByCPULatency + .name(name + ".nicAvgUsageByCPULatency") + .desc("average number of cycles before a NIC blk that is used gets used") + .precision(0) + ; + nicAvgUsageByCPULatency = nicUseByCPUCycleTotal / nicBlksUsedByCPU; + + useByCPUCycleDist + .name(name + ".useByCPUCycleDist") + .desc("the distribution of cycle time in cache before NIC blk is used") + .flags(pdf | cdf) + ; + + cpuUsedBlks + .name(name + ".cpuUsedBlks") + .desc("number of cpu blks that were used before evicted") + ; + + cpuUnusedBlks + .name(name + ".cpuUnusedBlks") + .desc("number of cpu blks that were unused before evicted") + ; + + nicAvgLatency + .name(name + ".nicAvgLatency") + .desc("avg number of cycles a NIC blk is in cache before evicted") + .precision(0) + ; + nicAvgLatency = (nicUnusedTotLatency + nicUsedTotLatency) / + (nicUnusedTotEvicted + nicUsedTotEvicted); + + NR_CP_hits + .name(name + ".NR_CP_hits") + .desc("NIC requests hitting in CPU Partition") + ; + + NR_NP_hits + .name(name + ".NR_NP_hits") + .desc("NIC requests hitting in NIC Partition") + ; + + CR_CP_hits + .name(name + ".CR_CP_hits") + .desc("CPU requests hitting in CPU partition") + ; + + CR_NP_hits + .name(name + ".CR_NP_hits") + .desc("CPU requests hitting in NIC partition") + ; + +} + +// probe cache for presence of given block. +bool +Split::probe(int asid, Addr addr) const +{ + bool success = lru->probe(asid, addr); + if (!success) { + if (lifo && lifo_net) + success = lifo_net->probe(asid, addr); + else if (lru_net) + success = lru_net->probe(asid, addr); + } + + return success; +} + +SplitBlk* +Split::findBlock(Packet * &pkt, int &lat) +{ + + Addr aligned = blkAlign(pkt->paddr); + + if (memHash.count(aligned)) { + memHash[aligned]++; + } else if (pkt->nic_pkt) { + memHash[aligned] = 1; + } + + SplitBlk *blk = lru->findBlock(pkt->paddr, pkt->req->asid, lat); + if (blk) { + if (pkt->nic_pkt) { + NR_CP_hits++; + } else { + CR_CP_hits++; + } + } else { + if (lifo && lifo_net) { + blk = lifo_net->findBlock(pkt->paddr, pkt->req->asid, lat); + + } else if (lru_net) { + blk = lru_net->findBlock(pkt->paddr, pkt->req->asid, lat); + } + if (blk) { + if (pkt->nic_pkt) { + NR_NP_hits++; + } else { + CR_NP_hits++; + } + } + } + + if (blk) { + Tick latency = curTick - blk->ts; + if (blk->isNIC) { + if (!blk->isUsed && !pkt->nic_pkt) { + useByCPUCycleDist.sample(latency); + nicUseByCPUCycleTotal += latency; + nicBlksUsedByCPU++; + } + } + blk->isUsed = true; + + if (pkt->nic_pkt) { + DPRINTF(Split, "found block in partition %d\n", blk->part); + } + } + return blk; +} + +SplitBlk* +Split::findBlock(Addr addr, int asid, int &lat) +{ + SplitBlk *blk = lru->findBlock(addr, asid, lat); + if (!blk) { + if (lifo && lifo_net) { + blk = lifo_net->findBlock(addr, asid, lat); + } else if (lru_net) { + blk = lru_net->findBlock(addr, asid, lat); + } + } + + return blk; +} + +SplitBlk* +Split::findBlock(Addr addr, int asid) const +{ + SplitBlk *blk = lru->findBlock(addr, asid); + if (!blk) { + if (lifo && lifo_net) { + blk = lifo_net->findBlock(addr, asid); + } else if (lru_net) { + blk = lru_net->findBlock(addr, asid); + } + } + + return blk; +} + +SplitBlk* +Split::findReplacement(Packet * &pkt, PacketList* &writebacks, + BlkList &compress_blocks) +{ + SplitBlk *blk; + + if (pkt->nic_pkt) { + DPRINTF(Split, "finding a replacement for nic_req\n"); + nic_repl++; + if (lifo && lifo_net) + blk = lifo_net->findReplacement(pkt, writebacks, + compress_blocks); + else if (lru_net) + blk = lru_net->findReplacement(pkt, writebacks, + compress_blocks); + // in this case, this is an LRU only cache, it's non partitioned + else + blk = lru->findReplacement(pkt, writebacks, compress_blocks); + } else { + DPRINTF(Split, "finding replacement for cpu_req\n"); + blk = lru->findReplacement(pkt, writebacks, + compress_blocks); + cpu_repl++; + } + + Tick latency = curTick - blk->ts; + if (blk->isNIC) { + if (blk->isUsed) { + nicUsedWhenEvicted++; + usedEvictDist.sample(latency); + nicUsedTotLatency += latency; + nicUsedTotEvicted++; + } else { + nicUnusedWhenEvicted++; + unusedEvictDist.sample(latency); + nicUnusedTotLatency += latency; + nicUnusedTotEvicted++; + } + } else { + if (blk->isUsed) { + cpuUsedBlks++; + } else { + cpuUnusedBlks++; + } + } + + // blk attributes for the new blk coming IN + blk->ts = curTick; + blk->isNIC = (pkt->nic_pkt) ? true : false; + + return blk; +} + +void +Split::invalidateBlk(int asid, Addr addr) +{ + SplitBlk *blk = lru->findBlock(addr, asid); + if (!blk) { + if (lifo && lifo_net) + blk = lifo_net->findBlock(addr, asid); + else if (lru_net) + blk = lru_net->findBlock(addr, asid); + + if (!blk) + return; + } + + blk->status = 0; + blk->isTouched = false; + tagsInUse--; +} + +void +Split::doCopy(Addr source, Addr dest, int asid, PacketList* &writebacks) +{ + if (lru->probe(asid, source)) + lru->doCopy(source, dest, asid, writebacks); + else { + if (lifo && lifo_net) + lifo_net->doCopy(source, dest, asid, writebacks); + else if (lru_net) + lru_net->doCopy(source, dest, asid, writebacks); + } +} + +void +Split::cleanupRefs() +{ + lru->cleanupRefs(); + if (lifo && lifo_net) + lifo_net->cleanupRefs(); + else if (lru_net) + lru_net->cleanupRefs(); + + ofstream memPrint(simout.resolve("memory_footprint.txt").c_str(), + ios::trunc); + + // this shouldn't be here but it happens at the end, which is what i want + memIter end = memHash.end(); + for (memIter iter = memHash.begin(); iter != end; ++iter) { + ccprintf(memPrint, "%8x\t%d\n", (*iter).first, (*iter).second); + } +} + +Addr +Split::regenerateBlkAddr(Addr tag, int set) const +{ + if (lifo_net) + return lifo_net->regenerateBlkAddr(tag, set); + else + return lru->regenerateBlkAddr(tag, set); +} + +Addr +Split::extractTag(Addr addr, SplitBlk *blk) const +{ + if (blk->part == 2) { + if (lifo_net) + return lifo_net->extractTag(addr); + else if (lru_net) + return lru_net->extractTag(addr); + else + panic("this shouldn't happen"); + } else + return lru->extractTag(addr); +} + diff --git a/src/mem/cache/tags/split.hh b/src/mem/cache/tags/split.hh new file mode 100644 index 000000000..6f2441597 --- /dev/null +++ b/src/mem/cache/tags/split.hh @@ -0,0 +1,335 @@ +/* + * Copyright (c) 2004-2005 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 a split/partitioned tag store. + */ + +#ifndef __SPLIT_HH__ +#define __SPLIT_HH__ + +#include <list> + +#include "mem/cache/cache_blk.hh" // base class +#include "mem/cache/tags/split_blk.hh" +#include "mem/packet.hh" // for inlined functions +#include <assert.h> +#include "mem/cache/tags/base_tags.hh" +#include "base/hashmap.hh" + +class BaseCache; +class SplitLRU; +class SplitLIFO; + +/** + * A cache tag store. + */ +class Split : public BaseTags +{ + public: + /** Typedef the block type used in this tag store. */ + typedef SplitBlk BlkType; + /** Typedef for a list of pointers to the local block class. */ + typedef std::list<SplitBlk*> BlkList; + protected: + /** The number of sets in the cache. */ + const int numSets; + /** The number of bytes in a block. */ + const int blkSize; + /** Whether the 2nd partition (for the nic) is LIFO or not */ + const bool lifo; + /** The hit latency. */ + const int hitLatency; + + Addr blkMask; + + /** Number of NIC requests that hit in the NIC partition */ + Stats::Scalar<> NR_NP_hits; + /** Number of NIC requests that hit in the CPU partition */ + Stats::Scalar<> NR_CP_hits; + /** Number of CPU requests that hit in the NIC partition */ + Stats::Scalar<> CR_NP_hits; + /** Number of CPU requests that hit in the CPU partition */ + Stats::Scalar<> CR_CP_hits; + /** The number of nic replacements (i.e. misses) */ + Stats::Scalar<> nic_repl; + /** The number of cpu replacements (i.e. misses) */ + Stats::Scalar<> cpu_repl; + + //For latency studies + /** the number of NIC blks that were used before evicted */ + Stats::Scalar<> nicUsedWhenEvicted; + /** the total latency of used NIC blocks in the cache */ + Stats::Scalar<> nicUsedTotLatency; + /** the total number of used NIC blocks evicted */ + Stats::Scalar<> nicUsedTotEvicted; + /** the average number of cycles a used NIC blk is in the cache */ + Stats::Formula nicUsedAvgLatency; + /** the Distribution of used NIC blk eviction times */ + Stats::Distribution<> usedEvictDist; + + /** the number of NIC blks that were unused before evicted */ + Stats::Scalar<> nicUnusedWhenEvicted; + /** the total latency of unused NIC blks in the cache */ + Stats::Scalar<> nicUnusedTotLatency; + /** the total number of unused NIC blocks evicted */ + Stats::Scalar<> nicUnusedTotEvicted; + /** the average number of cycles an unused NIC blk is in the cache */ + Stats::Formula nicUnusedAvgLatency; + /** the Distribution of unused NIC blk eviction times */ + Stats::Distribution<> unusedEvictDist; + + /** The total latency of NIC blocks to 1st usage time by CPU */ + Stats::Scalar<> nicUseByCPUCycleTotal; + /** The total number of NIC blocks used */ + Stats::Scalar<> nicBlksUsedByCPU; + /** the average number of cycles before a NIC blk that is used gets used by CPU */ + Stats::Formula nicAvgUsageByCPULatency; + /** the Distribution of cycles time before a NIC blk is used by CPU*/ + Stats::Distribution<> useByCPUCycleDist; + + /** the number of CPU blks that were used before evicted */ + Stats::Scalar<> cpuUsedBlks; + /** the number of CPU blks that were unused before evicted */ + Stats::Scalar<> cpuUnusedBlks; + + /** the avg number of cycles before a NIC blk is evicted */ + Stats::Formula nicAvgLatency; + + typedef m5::hash_map<Addr, int, m5::hash<Addr> > hash_t; + typedef hash_t::const_iterator memIter; + hash_t memHash; + + + private: + SplitLRU *lru; + SplitLRU *lru_net; + SplitLIFO *lifo_net; + + public: + /** + * Construct and initialize this tag store. + * @param _numSets The number of sets in the cache. + * @param _blkSize The number of bytes in a block. + * @param _assoc The associativity of the cache. + * @param _hit_latency The latency in cycles for a hit. + */ + Split(int _numSets, int _blkSize, int total_ways, int LRU1_assoc, + bool _lifo, bool _two_queue, int _hit_latency); + + /** + * Destructor + */ + virtual ~Split(); + + /** + * Register the stats for this object + * @param name The name to prepend to the stats name. + */ + void regStats(const std::string &name); + + /** + * Return the block size. + * @return the block size. + */ + int getBlockSize() + { + return blkSize; + } + + /** + * Return the subblock size. In the case of Split it is always the block + * size. + * @return The block size. + */ + int getSubBlockSize() + { + return blkSize; + } + + /** + * Search for the address in the cache. + * @param asid The address space ID. + * @param addr The address to find. + * @return True if the address is in the cache. + */ + bool probe(int asid, Addr addr) const; + + /** + * Invalidate the block containing the given address. + * @param asid The address space ID. + * @param addr The address to invalidate. + */ + void invalidateBlk(int asid, Addr addr); + + /** + * Finds the given address in the cache and update replacement data. + * Returns the access latency as a side effect. + * @param addr The address to find. + * @param asid The address space ID. + * @param lat The access latency. + * @return Pointer to the cache block if found. + */ + SplitBlk* findBlock(Addr addr, int asid, int &lat); + + /** + * Finds the given address in the cache and update replacement data. + * Returns the access latency as a side effect. + * @param req The memory request whose block to find + * @param lat The access latency. + * @return Pointer to the cache block if found. + */ + SplitBlk* findBlock(Packet * &pkt, int &lat); + + /** + * Finds the given address in the cache, do not update replacement data. + * @param addr The address to find. + * @param asid The address space ID. + * @return Pointer to the cache block if found. + */ + SplitBlk* findBlock(Addr addr, int asid) const; + + /** + * Find a replacement block for the address provided. + * @param req The request to a find a replacement candidate for. + * @param writebacks List for any writebacks to be performed. + * @param compress_blocks List of blocks to compress, for adaptive comp. + * @return The block to place the replacement in. + */ + SplitBlk* findReplacement(Packet * &pkt, PacketList* &writebacks, + BlkList &compress_blocks); + + + /** + * Generate the tag from the given address. + * @param addr The address to get the tag from. + * @param blk The block to find the partition it's in + * @return The tag of the address. + */ + Addr extractTag(Addr addr, SplitBlk *blk) const; + + /** + * 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 + { + panic("should never call this!\n"); + } + + /** + * 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, int set) const; + + /** + * Return the hit latency. + * @return the hit latency. + */ + int getHitLatency() const + { + return hitLatency; + } + + /** + * Read the data out of the internal storage of the given cache block. + * @param blk The cache block to read. + * @param data The buffer to read the data into. + * @return The cache block's data. + */ + void readData(SplitBlk *blk, uint8_t *data) + { + memcpy(data, blk->data, blk->size); + } + + /** + * Write data into the internal storage of the given cache block. Since in + * Split does not store data differently this just needs to update the size. + * @param blk The cache block to write. + * @param data The data to write. + * @param size The number of bytes to write. + * @param writebacks A list for any writebacks to be performed. May be + * needed when writing to a compressed block. + */ + void writeData(SplitBlk *blk, uint8_t *data, int size, + PacketList* & writebacks) + { + assert(size <= blkSize); + blk->size = size; + } + + /** + * Perform a block aligned copy from the source address to the destination. + * @param source The block-aligned source address. + * @param dest The block-aligned destination address. + * @param asid The address space DI. + * @param writebacks List for any generated writeback requests. + */ + void doCopy(Addr source, Addr dest, int asid, PacketList* &writebacks); + + /** + * No impl. + */ + void fixCopy(Packet * &pkt, PacketList* &writebacks) + { + } + + /** + * Called at end of simulation to complete average block reference stats. + */ + virtual void cleanupRefs(); +}; + +#endif diff --git a/src/mem/cache/tags/split_blk.hh b/src/mem/cache/tags/split_blk.hh new file mode 100644 index 000000000..f38516180 --- /dev/null +++ b/src/mem/cache/tags/split_blk.hh @@ -0,0 +1,68 @@ +/* + * Copyright (c) 2004-2005 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 partitioned tag store cache block class. + */ + +#ifndef __SPLIT_BLK_HH__ +#define __SPLIT_BLK_HH__ + +#include "mem/cache/cache_blk.hh" // base class + +/** + * Split cache block. + */ +class SplitBlk : public CacheBlk { + public: + /** Has this block been touched? Used to aid calculation of warmup time. */ + bool isTouched; + /** Has this block been used after being brought in? (for LIFO partition) */ + bool isUsed; + /** is this blk a NIC block? (i.e. requested by the NIC) */ + bool isNIC; + /** timestamp of the arrival of this block into the cache */ + Tick ts; + /** the previous block in the LIFO partition (brought in before than me) */ + SplitBlk *prev; + /** the next block in the LIFO partition (brought in later than me) */ + SplitBlk *next; + /** which partition this block is in */ + int part; + + SplitBlk() + : isTouched(false), isUsed(false), isNIC(false), ts(0), prev(NULL), next(NULL), + part(0) + {} +}; + +#endif + diff --git a/src/mem/cache/tags/split_lifo.cc b/src/mem/cache/tags/split_lifo.cc new file mode 100644 index 000000000..f2c37c80d --- /dev/null +++ b/src/mem/cache/tags/split_lifo.cc @@ -0,0 +1,405 @@ +/* + * Copyright (c) 2004-2005 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 + * Definitions of LIFO tag store usable in a partitioned cache. + */ + +#include <string> + +#include "mem/cache/base_cache.hh" +#include "base/intmath.hh" +#include "mem/cache/tags/split_lifo.hh" +#include "sim/root.hh" +#include "base/trace.hh" + +using namespace std; + +SplitBlk* +LIFOSet::findBlk(int asid, Addr tag) const +{ + for (SplitBlk *blk = firstIn; blk != NULL; blk = blk->next) { + if (blk->tag == tag && blk->isValid()) { + return blk; + } + } + return NULL; +} + +void +LIFOSet::moveToLastIn(SplitBlk *blk) +{ + if (blk == lastIn) + return; + + if (blk == firstIn) { + blk->next->prev = NULL; + } else { + blk->prev->next = blk->next; + blk->next->prev = blk->prev; + } + blk->next = NULL; + blk->prev = lastIn; + lastIn->next = blk; + + lastIn = blk; +} + +void +LIFOSet::moveToFirstIn(SplitBlk *blk) +{ + if (blk == firstIn) + return; + + if (blk == lastIn) { + blk->prev->next = NULL; + } else { + blk->next->prev = blk->prev; + blk->prev->next = blk->next; + } + + blk->prev = NULL; + blk->next = firstIn; + firstIn->prev = blk; + + firstIn = blk; +} + +// create and initialize a LIFO cache structure +SplitLIFO::SplitLIFO(int _blkSize, int _size, int _ways, int _hit_latency, bool two_Queue, int _part) : + blkSize(_blkSize), size(_size), numBlks(_size/_blkSize), numSets((_size/_ways)/_blkSize), ways(_ways), + hitLatency(_hit_latency), twoQueue(two_Queue), part(_part) +{ + if (!isPowerOf2(blkSize)) + fatal("cache block size (in bytes) must be a power of 2"); + if (!(hitLatency > 0)) + fatal("access latency in cycles must be at least on cycle"); + if (_ways == 0) + fatal("if instantiating a splitLIFO, needs non-zero size!"); + + + SplitBlk *blk; + int i, j, blkIndex; + + setShift = floorLog2(blkSize); + blkMask = blkSize - 1; + setMask = numSets - 1; + tagShift = setShift + floorLog2(numSets); + + warmedUp = false; + /** @todo Make warmup percentage a parameter. */ + warmupBound = size/blkSize; + + // allocate data blocks + blks = new SplitBlk[numBlks]; + sets = new LIFOSet[numSets]; + dataBlks = new uint8_t[size]; + +/* + // these start off point to same blk + top = &(blks[0]); + head = top; +*/ + + blkIndex = 0; + for (i=0; i < numSets; ++i) { + sets[i].ways = ways; + sets[i].lastIn = &blks[blkIndex]; + sets[i].firstIn = &blks[blkIndex + ways - 1]; + + /* 3 cases: if there is 1 way, if there are 2 ways, or if there are 3+. + in the case of 1 way, last in and first out point to the same blocks, + and the next and prev pointers need to be assigned specially. and so on + */ + /* deal with the first way */ + blk = &blks[blkIndex]; + blk->prev = &blks[blkIndex + 1]; + blk->next = NULL; + blk->data = &dataBlks[blkSize*blkIndex]; + blk->size = blkSize; + blk->part = part; + blk->set = i; + ++blkIndex; + + /* if there are "middle" ways, do them here */ + if (ways > 2) { + for (j=1; j < ways-1; ++j) { + blk = &blks[blkIndex]; + blk->data = &dataBlks[blkSize*blkIndex]; + blk->prev = &blks[blkIndex+1]; + blk->next = &blks[blkIndex-1]; + blk->data = &(dataBlks[blkSize*blkIndex]); + blk->size = blkSize; + blk->part = part; + blk->set = i; + ++blkIndex; + } + } + + /* do the final way here, depending on whether the final way is the only + way or not + */ + if (ways > 1) { + blk = &blks[blkIndex]; + blk->prev = NULL; + blk->next = &blks[blkIndex - 1]; + blk->data = &dataBlks[blkSize*blkIndex]; + blk->size = blkSize; + blk->part = part; + blk->set = i; + ++blkIndex; + } else { + blk->prev = NULL; + } + } + assert(blkIndex == numBlks); +} + +SplitLIFO::~SplitLIFO() +{ + delete [] blks; + delete [] sets; + delete [] dataBlks; +} + +void +SplitLIFO::regStats(const std::string &name) +{ + BaseTags::regStats(name); + + hits + .name(name + ".hits") + .desc("number of hits on this partition") + .precision(0) + ; + + misses + .name(name + ".misses") + .desc("number of misses in this partition") + .precision(0) + ; + + invalidations + .name(name + ".invalidations") + .desc("number of invalidations in this partition") + .precision(0) + ; +} + +// probe cache for presence of given block. +bool +SplitLIFO::probe(int asid, Addr addr) const +{ + Addr tag = extractTag(addr); + unsigned myset = extractSet(addr); + + SplitBlk* blk = sets[myset].findBlk(asid, tag); + return (blk != NULL); +} + +SplitBlk* +SplitLIFO::findBlock(Addr addr, int asid, int &lat) +{ + Addr tag = extractTag(addr); + unsigned set = extractSet(addr); + SplitBlk *blk = sets[set].findBlk(asid, tag); + + lat = hitLatency; + + if (blk) { + DPRINTF(Split, "Found LIFO blk %#x in set %d, with tag %#x\n", + addr, set, tag); + hits++; + + if (blk->whenReady > curTick && blk->whenReady - curTick > hitLatency) + lat = blk->whenReady - curTick; + blk->refCount +=1; + + if (twoQueue) { + blk->isUsed = true; + sets[set].moveToFirstIn(blk); + } else { + sets[set].moveToLastIn(blk); + } + } + + return blk; +} + +SplitBlk* +SplitLIFO::findBlock(Packet * &pkt, int &lat) +{ + Addr addr = pkt->paddr; + int asid = pkt->req->asid; + + Addr tag = extractTag(addr); + unsigned set = extractSet(addr); + SplitBlk *blk = sets[set].findBlk(asid, tag); + + if (blk) { + DPRINTF(Split, "Found LIFO blk %#x in set %d, with tag %#x\n", + addr, set, tag); + hits++; + + if (twoQueue) { + blk->isUsed = true; + sets[set].moveToFirstIn(blk); + } else { + sets[set].moveToLastIn(blk); + } + } + lat = hitLatency; + + return blk; +} + +SplitBlk* +SplitLIFO::findBlock(Addr addr, int asid) const +{ + Addr tag = extractTag(addr); + unsigned set = extractSet(addr); + SplitBlk *blk = sets[set].findBlk(asid, tag); + + return blk; +} + +SplitBlk* +SplitLIFO::findReplacement(Packet * &pkt, PacketList* &writebacks, + BlkList &compress_blocks) +{ + unsigned set = extractSet(pkt->paddr); + + SplitBlk *firstIn = sets[set].firstIn; + SplitBlk *lastIn = sets[set].lastIn; + + SplitBlk *blk; + if (twoQueue && firstIn->isUsed) { + blk = firstIn; + blk->isUsed = false; + sets[set].moveToLastIn(blk); + } else { + int withValue = sets[set].withValue; + if (withValue == ways) { + blk = lastIn; + } else { + blk = &(sets[set].firstIn[ways - ++withValue]); + } + } + + DPRINTF(Split, "just assigned %#x addr into LIFO, replacing %#x status %#x\n", + pkt->paddr, regenerateBlkAddr(blk->tag, set), blk->status); + if (blk->isValid()) { + int thread_num = (blk->xc) ? blk->xc->getThreadNum() : 0; + replacements[thread_num]++; + totalRefs += blk->refCount; + ++sampledRefs; + blk->refCount = 0; + } else { + tagsInUse++; + blk->isTouched = true; + if (!warmedUp && tagsInUse.value() >= warmupBound) { + warmedUp = true; + warmupCycle = curTick; + } + } + + misses++; + + return blk; +} + +void +SplitLIFO::invalidateBlk(int asid, Addr addr) +{ + SplitBlk *blk = findBlock(addr, asid); + if (blk) { + blk->status = 0; + blk->isTouched = false; + tagsInUse--; + invalidations++; + } +} + +void +SplitLIFO::doCopy(Addr source, Addr dest, int asid, PacketList* &writebacks) +{ + assert(source == blkAlign(source)); + assert(dest == blkAlign(dest)); + SplitBlk *source_blk = findBlock(source, asid); + assert(source_blk); + SplitBlk *dest_blk = findBlock(dest, asid); + if (dest_blk == NULL) { + // Need to do a replacement + Packet * pkt = new Packet(); + pkt->paddr = dest; + BlkList dummy_list; + dest_blk = findReplacement(pkt, writebacks, dummy_list); + if (dest_blk->isValid() && dest_blk->isModified()) { + // Need to writeback data. + pkt = buildWritebackReq(regenerateBlkAddr(dest_blk->tag, + dest_blk->set), + dest_blk->req->asid, + dest_blk->xc, + blkSize, + (cache->doData())?dest_blk->data:0, + dest_blk->size); + writebacks.push_back(pkt); + } + dest_blk->tag = extractTag(dest); + dest_blk->req->asid = asid; + /** + * @todo Do we need to pass in the execution context, or can we + * assume its the same? + */ + assert(source_blk->xc); + dest_blk->xc = source_blk->xc; + } + /** + * @todo Can't assume the status once we have coherence on copies. + */ + + // Set this block as readable, writeable, and dirty. + dest_blk->status = 7; + if (cache->doData()) { + memcpy(dest_blk->data, source_blk->data, blkSize); + } +} + +void +SplitLIFO::cleanupRefs() +{ + for (int i = 0; i < numBlks; ++i) { + if (blks[i].isValid()) { + totalRefs += blks[i].refCount; + ++sampledRefs; + } + } +} diff --git a/src/mem/cache/tags/split_lifo.hh b/src/mem/cache/tags/split_lifo.hh new file mode 100644 index 000000000..c50eaa53d --- /dev/null +++ b/src/mem/cache/tags/split_lifo.hh @@ -0,0 +1,350 @@ +/* + * Copyright (c) 2004-2005 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 a LIFO tag store usable in a partitioned cache. + */ + +#ifndef __SPLIT_LIFO_HH__ +#define __SPLIT_LIFO_HH__ + +#include <list> + +#include "mem/cache/cache_blk.hh" // base class +#include "mem/cache/tags/split_blk.hh" +#include "mem/packet.hh" // for inlined functions +#include "base/hashmap.hh" +#include <assert.h> +#include "mem/cache/tags/base_tags.hh" + +class BaseCache; + +/** + * A LIFO set of cache blks + */ +class LIFOSet { + public: + /** the number of blocks in this set */ + int ways; + + /** Cache blocks in this set, maintained in LIFO order where + 0 = Last in (head) */ + SplitBlk *lastIn; + SplitBlk *firstIn; + + /** has the initial "filling" of this set finished? i.e., have you had + * 'ways' number of compulsory misses in this set yet? if withValue == ways, + * then yes. withValue is meant to be the number of blocks in the set that have + * gone through their first compulsory miss. + */ + int withValue; + + /** + * Find a block matching the tag in this set. + * @param asid The address space ID. + * @param tag the Tag you are looking for + * @return Pointer to the block, if found, NULL otherwise + */ + SplitBlk* findBlk(int asid, Addr tag) const; + + void moveToLastIn(SplitBlk *blk); + void moveToFirstIn(SplitBlk *blk); + + LIFOSet() + : ways(-1), lastIn(NULL), firstIn(NULL), withValue(0) + {} +}; + +/** + * A LIFO cache tag store. + */ +class SplitLIFO : public BaseTags +{ + public: + /** Typedef the block type used in this tag store. */ + typedef SplitBlk BlkType; + /** Typedef for a list of pointers to the local block class. */ + typedef std::list<SplitBlk*> BlkList; + protected: + /** The number of bytes in a block. */ + const int blkSize; + /** the size of the cache in bytes */ + const int size; + /** the number of blocks in the cache */ + const int numBlks; + /** the number of sets in the cache */ + const int numSets; + /** the number of ways in the cache */ + const int ways; + /** The hit latency. */ + const int hitLatency; + /** whether this is a "2 queue" replacement @sa moveToLastIn @sa moveToFirstIn */ + const bool twoQueue; + /** indicator for which partition this is */ + const int part; + + /** The cache blocks. */ + SplitBlk *blks; + /** The Cache sets */ + LIFOSet *sets; + /** 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; + + + /** the number of hit in this partition */ + Stats::Scalar<> hits; + /** the number of blocks brought into this partition (i.e. misses) */ + Stats::Scalar<> misses; + /** the number of invalidations in this partition */ + Stats::Scalar<> invalidations; + +public: + /** + * Construct and initialize this tag store. + * @param _numSets The number of sets in the cache. + * @param _blkSize The number of bytes in a block. + * @param _assoc The associativity of the cache. + * @param _hit_latency The latency in cycles for a hit. + */ + SplitLIFO(int _blkSize, int _size, int _ways, int _hit_latency, bool twoQueue, int _part); + + /** + * Destructor + */ + virtual ~SplitLIFO(); + + /** + * Register the statistics for this object + * @param name The name to precede the stat + */ + void regStats(const std::string &name); + + /** + * Return the block size. + * @return the block size. + */ + int getBlockSize() + { + return blkSize; + } + + /** + * Return the subblock size. In the case of LIFO it is always the block + * size. + * @return The block size. + */ + int getSubBlockSize() + { + return blkSize; + } + + /** + * Search for the address in the cache. + * @param asid The address space ID. + * @param addr The address to find. + * @return True if the address is in the cache. + */ + bool probe(int asid, Addr addr) const; + + /** + * Invalidate the block containing the given address. + * @param asid The address space ID. + * @param addr The address to invalidate. + */ + void invalidateBlk(int asid, Addr addr); + + /** + * Finds the given address in the cache and update replacement data. + * Returns the access latency as a side effect. + * @param addr The address to find. + * @param asid The address space ID. + * @param lat The access latency. + * @return Pointer to the cache block if found. + */ + SplitBlk* findBlock(Addr addr, int asid, int &lat); + + /** + * Finds the given address in the cache and update replacement data. + * Returns the access latency as a side effect. + * @param req The req whose block to find + * @param lat The access latency. + * @return Pointer to the cache block if found. + */ + SplitBlk* findBlock(Packet * &pkt, int &lat); + + /** + * Finds the given address in the cache, do not update replacement data. + * @param addr The address to find. + * @param asid The address space ID. + * @return Pointer to the cache block if found. + */ + SplitBlk* findBlock(Addr addr, int asid) const; + + /** + * Find a replacement block for the address provided. + * @param req The request to a find a replacement candidate for. + * @param writebacks List for any writebacks to be performed. + * @param compress_blocks List of blocks to compress, for adaptive comp. + * @return The block to place the replacement in. + */ + SplitBlk* findReplacement(Packet * &pkt, PacketList* &writebacks, + BlkList &compress_blocks); + + /** + * 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); + } + + /** + * Generate the tag from the given address. + * @param addr The address to get the tag from. + * @param blk Ignored + * @return The tag of the address. + */ + Addr extractTag(Addr addr, SplitBlk *blk) 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. + */ + int getHitLatency() const + { + return hitLatency; + } + + /** + * Read the data out of the internal storage of the given cache block. + * @param blk The cache block to read. + * @param data The buffer to read the data into. + * @return The cache block's data. + */ + void readData(SplitBlk *blk, uint8_t *data) + { + memcpy(data, blk->data, blk->size); + } + + /** + * Write data into the internal storage of the given cache block. Since in + * LIFO does not store data differently this just needs to update the size. + * @param blk The cache block to write. + * @param data The data to write. + * @param size The number of bytes to write. + * @param writebacks A list for any writebacks to be performed. May be + * needed when writing to a compressed block. + */ + void writeData(SplitBlk *blk, uint8_t *data, int size, + PacketList* & writebacks) + { + assert(size <= blkSize); + blk->size = size; + } + + /** + * Perform a block aligned copy from the source address to the destination. + * @param source The block-aligned source address. + * @param dest The block-aligned destination address. + * @param asid The address space DI. + * @param writebacks List for any generated writeback requests. + */ + void doCopy(Addr source, Addr dest, int asid, PacketList* &writebacks); + + /** + * No impl. + */ + void fixCopy(Packet * &pkt, PacketList* &writebacks) + { + } + + /** + * Called at end of simulation to complete average block reference stats. + */ + virtual void cleanupRefs(); +}; + +#endif diff --git a/src/mem/cache/tags/split_lru.cc b/src/mem/cache/tags/split_lru.cc new file mode 100644 index 000000000..ea5b92d6f --- /dev/null +++ b/src/mem/cache/tags/split_lru.cc @@ -0,0 +1,331 @@ +/* + * Copyright (c) 2004-2005 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 + * Definitions of LRU tag store for a partitioned cache. + */ + +#include <string> + +#include "mem/cache/base_cache.hh" +#include "base/intmath.hh" +#include "mem/cache/tags/split_lru.hh" +#include "sim/root.hh" + +using namespace std; + +SplitBlk* +SplitCacheSet::findBlk(int asid, Addr tag) const +{ + for (int i = 0; i < assoc; ++i) { + if (blks[i]->tag == tag && blks[i]->isValid()) { + return blks[i]; + } + } + return 0; +} + + +void +SplitCacheSet::moveToHead(SplitBlk *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; + SplitBlk *next = blk; + + do { + assert(i < assoc); + // swap blks[i] and next + SplitBlk *tmp = blks[i]; + blks[i] = next; + next = tmp; + ++i; + } while (next != blk); +} + + +// create and initialize a LRU/MRU cache structure +SplitLRU::SplitLRU(int _numSets, int _blkSize, int _assoc, int _hit_latency, int _part) : + numSets(_numSets), blkSize(_blkSize), assoc(_assoc), hitLatency(_hit_latency), part(_part) +{ + // 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"); + } + + SplitBlk *blk; + int i, j, blkIndex; + + 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 SplitCacheSet[numSets]; + blks = new SplitBlk[numSets * assoc]; + // allocate data storage in one big chunk + dataBlks = new uint8_t[numSets*assoc*blkSize]; + + blkIndex = 0; // index into blks array + for (i = 0; i < numSets; ++i) { + sets[i].assoc = assoc; + + sets[i].blks = new SplitBlk*[assoc]; + + // link in the data blocks + for (j = 0; j < assoc; ++j) { + // locate next cache block + blk = &blks[blkIndex]; + blk->data = &dataBlks[blkSize*blkIndex]; + ++blkIndex; + + // invalidate new cache block + blk->status = 0; + + //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->req->asid = -1; + blk->isTouched = false; + blk->size = blkSize; + sets[i].blks[j]=blk; + blk->set = i; + blk->part = part; + } + } +} + +SplitLRU::~SplitLRU() +{ + delete [] dataBlks; + delete [] blks; + delete [] sets; +} + +void +SplitLRU::regStats(const std::string &name) +{ + BaseTags::regStats(name); + + hits + .name(name + ".hits") + .desc("number of hits on this partition") + .precision(0) + ; + + misses + .name(name + ".misses") + .desc("number of misses in this partition") + .precision(0) + ; +} + +// probe cache for presence of given block. +bool +SplitLRU::probe(int asid, Addr addr) const +{ + // return(findBlock(Read, addr, asid) != 0); + Addr tag = extractTag(addr); + unsigned myset = extractSet(addr); + + SplitBlk *blk = sets[myset].findBlk(asid, tag); + + return (blk != NULL); // true if in cache +} + +SplitBlk* +SplitLRU::findBlock(Addr addr, int asid, int &lat) +{ + Addr tag = extractTag(addr); + unsigned set = extractSet(addr); + SplitBlk *blk = sets[set].findBlk(asid, tag); + lat = hitLatency; + if (blk != NULL) { + // move this block to head of the MRU list + sets[set].moveToHead(blk); + if (blk->whenReady > curTick && blk->whenReady - curTick > hitLatency){ + lat = blk->whenReady - curTick; + } + blk->refCount += 1; + hits++; + } + + return blk; +} + +SplitBlk* +SplitLRU::findBlock(Packet * &pkt, int &lat) +{ + Addr addr = pkt->paddr; + int asid = pkt->req->asid; + + Addr tag = extractTag(addr); + unsigned set = extractSet(addr); + SplitBlk *blk = sets[set].findBlk(asid, tag); + lat = hitLatency; + if (blk != NULL) { + // move this block to head of the MRU list + sets[set].moveToHead(blk); + if (blk->whenReady > curTick && blk->whenReady - curTick > hitLatency){ + lat = blk->whenReady - curTick; + } + blk->refCount += 1; + hits++; + } + + return blk; +} + +SplitBlk* +SplitLRU::findBlock(Addr addr, int asid) const +{ + Addr tag = extractTag(addr); + unsigned set = extractSet(addr); + SplitBlk *blk = sets[set].findBlk(asid, tag); + return blk; +} + +SplitBlk* +SplitLRU::findReplacement(Packet * &pkt, PacketList* &writebacks, + BlkList &compress_blocks) +{ + unsigned set = extractSet(pkt->paddr); + // grab a replacement candidate + SplitBlk *blk = sets[set].blks[assoc-1]; + sets[set].moveToHead(blk); + if (blk->isValid()) { + int thread_num = (blk->xc) ? blk->xc->getThreadNum() : 0; + replacements[thread_num]++; + totalRefs += blk->refCount; + ++sampledRefs; + blk->refCount = 0; + } else if (!blk->isTouched) { + tagsInUse++; + blk->isTouched = true; + if (!warmedUp && tagsInUse.value() >= warmupBound) { + warmedUp = true; + warmupCycle = curTick; + } + } + + misses++; + + return blk; +} + +void +SplitLRU::invalidateBlk(int asid, Addr addr) +{ + SplitBlk *blk = findBlock(addr, asid); + if (blk) { + blk->status = 0; + blk->isTouched = false; + tagsInUse--; + } +} + +void +SplitLRU::doCopy(Addr source, Addr dest, int asid, PacketList* &writebacks) +{ + assert(source == blkAlign(source)); + assert(dest == blkAlign(dest)); + SplitBlk *source_blk = findBlock(source, asid); + assert(source_blk); + SplitBlk *dest_blk = findBlock(dest, asid); + if (dest_blk == NULL) { + // Need to do a replacement + Packet * pkt = new Packet(); + pkt->paddr = dest; + BlkList dummy_list; + dest_blk = findReplacement(pkt, writebacks, dummy_list); + if (dest_blk->isValid() && dest_blk->isModified()) { + // Need to writeback data. + pkt = buildWritebackReq(regenerateBlkAddr(dest_blk->tag, + dest_blk->set), + dest_blk->req->asid, + dest_blk->xc, + blkSize, + (cache->doData())?dest_blk->data:0, + dest_blk->size); + writebacks.push_back(pkt); + } + dest_blk->tag = extractTag(dest); + dest_blk->req->asid = asid; + /** + * @todo Do we need to pass in the execution context, or can we + * assume its the same? + */ + assert(source_blk->xc); + dest_blk->xc = source_blk->xc; + } + /** + * @todo Can't assume the status once we have coherence on copies. + */ + + // Set this block as readable, writeable, and dirty. + dest_blk->status = 7; + if (cache->doData()) { + memcpy(dest_blk->data, source_blk->data, blkSize); + } +} + +void +SplitLRU::cleanupRefs() +{ + for (int i = 0; i < numSets*assoc; ++i) { + if (blks[i].isValid()) { + totalRefs += blks[i].refCount; + ++sampledRefs; + } + } +} diff --git a/src/mem/cache/tags/split_lru.hh b/src/mem/cache/tags/split_lru.hh new file mode 100644 index 000000000..1c0fc8600 --- /dev/null +++ b/src/mem/cache/tags/split_lru.hh @@ -0,0 +1,333 @@ +/* + * Copyright (c) 2004-2005 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 a LRU tag store for a partitioned cache. + */ + +#ifndef __SPLIT_LRU_HH__ +#define __SPLIT_LRU_HH__ + +#include <list> + +#include "mem/cache/cache_blk.hh" // base class +#include "mem/cache/tags/split_blk.hh" +#include "mem/packet.hh" // for inlined functions +#include <assert.h> +#include "mem/cache/tags/base_tags.hh" + +class BaseCache; + +/** + * An associative set of cache blocks. + */ + +class SplitCacheSet +{ + public: + /** The associativity of this set. */ + int assoc; + + /** Cache blocks in this set, maintained in LRU order 0 = MRU. */ + SplitBlk **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. + */ + SplitBlk* findBlk(int asid, Addr tag) const; + + /** + * Move the given block to the head of the list. + * @param blk The block to move. + */ + void moveToHead(SplitBlk *blk); +}; + +/** + * A LRU cache tag store. + */ +class SplitLRU : public BaseTags +{ + public: + /** Typedef the block type used in this tag store. */ + typedef SplitBlk BlkType; + /** Typedef for a list of pointers to the local block class. */ + typedef std::list<SplitBlk*> BlkList; + protected: + /** The number of sets in the cache. */ + const int numSets; + /** The number of bytes in a block. */ + const int blkSize; + /** The associativity of the cache. */ + const int assoc; + /** The hit latency. */ + const int hitLatency; + /** indicator for which partition this is */ + const int part; + + /** The cache sets. */ + SplitCacheSet *sets; + + /** The cache blocks. */ + SplitBlk *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; + + /** number of hits in this partition */ + Stats::Scalar<> hits; + /** number of blocks brought into this partition (i.e. misses) */ + Stats::Scalar<> misses; + +public: + /** + * Construct and initialize this tag store. + * @param _numSets The number of sets in the cache. + * @param _blkSize The number of bytes in a block. + * @param _assoc The associativity of the cache. + * @param _hit_latency The latency in cycles for a hit. + */ + SplitLRU(int _numSets, int _blkSize, int _assoc, int _hit_latency, int _part); + + /** + * Destructor + */ + virtual ~SplitLRU(); + + /** + * Register the statistics for this object + * @param name The name to precede the stat + */ + void regStats(const std::string &name); + + /** + * Return the block size. + * @return the block size. + */ + int getBlockSize() + { + return blkSize; + } + + /** + * Return the subblock size. In the case of LRU it is always the block + * size. + * @return The block size. + */ + int getSubBlockSize() + { + return blkSize; + } + + /** + * Search for the address in the cache. + * @param asid The address space ID. + * @param addr The address to find. + * @return True if the address is in the cache. + */ + bool probe(int asid, Addr addr) const; + + /** + * Invalidate the block containing the given address. + * @param asid The address space ID. + * @param addr The address to invalidate. + */ + void invalidateBlk(int asid, Addr addr); + + /** + * Finds the given address in the cache and update replacement data. + * Returns the access latency as a side effect. + * @param addr The address to find. + * @param asid The address space ID. + * @param lat The access latency. + * @return Pointer to the cache block if found. + */ + SplitBlk* findBlock(Addr addr, int asid, int &lat); + + /** + * Finds the given address in the cache and update replacement data. + * Returns the access latency as a side effect. + * @param req The req whose block to find. + * @param lat The access latency. + * @return Pointer to the cache block if found. + */ + SplitBlk* findBlock(Packet * &pkt, int &lat); + + /** + * Finds the given address in the cache, do not update replacement data. + * @param addr The address to find. + * @param asid The address space ID. + * @return Pointer to the cache block if found. + */ + SplitBlk* findBlock(Addr addr, int asid) const; + + /** + * Find a replacement block for the address provided. + * @param req The request to a find a replacement candidate for. + * @param writebacks List for any writebacks to be performed. + * @param compress_blocks List of blocks to compress, for adaptive comp. + * @return The block to place the replacement in. + */ + SplitBlk* findReplacement(Packet * &pkt, PacketList* &writebacks, + BlkList &compress_blocks); + + /** + * 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); + } + + /** + * Generate the tag from the given address. + * @param addr The address to get the tag from. + * @param blk Ignored. + * @return The tag of the address. + */ + Addr extractTag(Addr addr, SplitBlk *blk) 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. + */ + int getHitLatency() const + { + return hitLatency; + } + + /** + * Read the data out of the internal storage of the given cache block. + * @param blk The cache block to read. + * @param data The buffer to read the data into. + * @return The cache block's data. + */ + void readData(SplitBlk *blk, uint8_t *data) + { + memcpy(data, blk->data, blk->size); + } + + /** + * Write data into the internal storage of the given cache block. Since in + * LRU does not store data differently this just needs to update the size. + * @param blk The cache block to write. + * @param data The data to write. + * @param size The number of bytes to write. + * @param writebacks A list for any writebacks to be performed. May be + * needed when writing to a compressed block. + */ + void writeData(SplitBlk *blk, uint8_t *data, int size, + PacketList* & writebacks) + { + assert(size <= blkSize); + blk->size = size; + } + + /** + * Perform a block aligned copy from the source address to the destination. + * @param source The block-aligned source address. + * @param dest The block-aligned destination address. + * @param asid The address space DI. + * @param writebacks List for any generated writeback requests. + */ + void doCopy(Addr source, Addr dest, int asid, PacketList* &writebacks); + + /** + * No impl. + */ + void fixCopy(Packet * &pkt, PacketList* &writebacks) + { + } + + /** + * Called at end of simulation to complete average block reference stats. + */ + virtual void cleanupRefs(); +}; + +#endif |