Daniel Carvalho has uploaded this change for review. (
https://gem5-review.googlesource.com/8366
Change subject: mem-cache: Remove FALRU class
......................................................................
mem-cache: Remove FALRU class
By definition, FALRU is a combination of a set associative (1 set and
N ways) cache with a LRU policy, thus instantiating the proper classes
should produce the same results.
Even if FALRU yields better performance, it is a limited approach, as
if other replacement policies are created, extensions of this class
would have to be created, and it hardens implementation of other cache
placement (indexing) policies (i.e., Skewed, Indirect, Decoupled), as
they would also need different implementations for each replacement
policy used.
Besides, FALRU currently only works for cache sizes >= 128K (if smaller,
the simulator crashes due to numCaches being unsigned), and does not have
comments, making it hard to maintain/understand.
Change-Id: Iebee8bf7f17ccc7fc7644267276046f34923f3d7
---
M src/mem/cache/base.cc
M src/mem/cache/tags/SConscript
M src/mem/cache/tags/Tags.py
D src/mem/cache/tags/fa_lru.cc
D src/mem/cache/tags/fa_lru.hh
5 files changed, 0 insertions(+), 623 deletions(-)
diff --git a/src/mem/cache/base.cc b/src/mem/cache/base.cc
index 6f25323..5cf9422 100644
--- a/src/mem/cache/base.cc
+++ b/src/mem/cache/base.cc
@@ -51,7 +51,6 @@
#include "debug/Drain.hh"
#include "mem/cache/cache.hh"
#include "mem/cache/mshr.hh"
-#include "mem/cache/tags/fa_lru.hh"
#include "mem/cache/tags/lru.hh"
#include "mem/cache/tags/random_repl.hh"
#include "sim/full_system.hh"
diff --git a/src/mem/cache/tags/SConscript b/src/mem/cache/tags/SConscript
index 1412286..5cc47c3 100644
--- a/src/mem/cache/tags/SConscript
+++ b/src/mem/cache/tags/SConscript
@@ -36,4 +36,3 @@
Source('base_set_assoc.cc')
Source('lru.cc')
Source('random_repl.cc')
-Source('fa_lru.cc')
diff --git a/src/mem/cache/tags/Tags.py b/src/mem/cache/tags/Tags.py
index b19010f..d58ce8f 100644
--- a/src/mem/cache/tags/Tags.py
+++ b/src/mem/cache/tags/Tags.py
@@ -79,8 +79,3 @@
type = 'RandomRepl'
cxx_class = 'RandomRepl'
cxx_header = "mem/cache/tags/random_repl.hh"
-
-class FALRU(BaseTags):
- type = 'FALRU'
- cxx_class = 'FALRU'
- cxx_header = "mem/cache/tags/fa_lru.hh"
diff --git a/src/mem/cache/tags/fa_lru.cc b/src/mem/cache/tags/fa_lru.cc
deleted file mode 100644
index dfd4c40..0000000
--- a/src/mem/cache/tags/fa_lru.cc
+++ /dev/null
@@ -1,335 +0,0 @@
-/*
- * Copyright (c) 2013,2016 ARM Limited
- * All rights reserved.
- *
- * The license below extends only to copyright in the software and shall
- * not be construed as granting a license to any other intellectual
- * property including but not limited to intellectual property relating
- * to a hardware implementation of the functionality of the software
- * licensed hereunder. You may use the software subject to the license
- * terms below provided that you ensure that this notice is replicated
- * unmodified and in its entirety in all distributions of the software,
- * modified or unmodified, in source code or in binary form.
- *
- * Copyright (c) 2003-2005 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 "mem/cache/tags/fa_lru.hh"
-
-#include <cassert>
-#include <sstream>
-
-#include "base/intmath.hh"
-#include "base/logging.hh"
-
-using namespace std;
-
-FALRU::FALRU(const Params *p)
- : BaseTags(p), cacheBoundaries(nullptr)
-{
- if (!isPowerOf2(blkSize))
- fatal("cache block size (in bytes) `%d' must be a power of two",
- blkSize);
- 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 = (ULL(1) << numCaches) - 1;
- } else {
- cacheMask = 0;
- }
-
- numBlocks = size/blkSize;
-
- blks = new FALRUBlk[numBlocks];
- head = &(blks[0]);
- tail = &(blks[numBlocks-1]);
-
- head->prev = nullptr;
- head->next = &(blks[1]);
- head->inCache = cacheMask;
-
- tail->prev = &(blks[numBlocks-2]);
- tail->next = nullptr;
- tail->inCache = 0;
-
- unsigned index = (1 << 17) / blkSize;
- unsigned j = 0;
- int flags = cacheMask;
- for (unsigned i = 1; i < numBlocks - 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;
- blks[i].set = 0;
- blks[i].way = i;
- }
- assert(j == numCaches);
- assert(index == numBlocks);
- //assert(check());
-}
-
-FALRU::~FALRU()
-{
- if (numCaches)
- delete[] cacheBoundaries;
-
- delete[] blks;
-}
-
-void
-FALRU::regStats()
-{
- using namespace Stats;
- BaseTags::regStats();
- 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 (unsigned i = 0; i <= numCaches; ++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 nullptr;
-}
-
-void
-FALRU::invalidate(CacheBlk *blk)
-{
- assert(blk);
- tagsInUse--;
-}
-
-CacheBlk*
-FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat)
-{
- return accessBlock(addr, is_secure, lat, 0);
-}
-
-CacheBlk*
-FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, int *inCache)
-{
- accesses++;
- int tmp_in_cache = 0;
- Addr blkAddr = blkAlign(addr);
- FALRUBlk* blk = hashLookup(blkAddr);
-
- if (blk && blk->isValid()) {
- // If a cache hit
- lat = accessLatency;
- // Check if the block to be accessed is available. If not,
- // apply the accessLatency on top of block->whenReady.
- if (blk->whenReady > curTick() &&
- cache->ticksToCycles(blk->whenReady - curTick()) >
- accessLatency) {
- lat = cache->ticksToCycles(blk->whenReady - curTick()) +
- accessLatency;
- }
- assert(blk->tag == blkAddr);
- tmp_in_cache = blk->inCache;
- for (unsigned i = 0; i < numCaches; i++) {
- if (1<<i & blk->inCache) {
- hits[i]++;
- } else {
- misses[i]++;
- }
- }
- hits[numCaches]++;
- if (blk != head){
- moveToHead(blk);
- }
- } else {
- // If a cache miss
- lat = lookupLatency;
- blk = nullptr;
- for (unsigned i = 0; i <= numCaches; ++i) {
- misses[i]++;
- }
- }
- if (inCache) {
- *inCache = tmp_in_cache;
- }
-
- //assert(check());
- return blk;
-}
-
-
-CacheBlk*
-FALRU::findBlock(Addr addr, bool is_secure) const
-{
- Addr blkAddr = blkAlign(addr);
- FALRUBlk* blk = hashLookup(blkAddr);
-
- if (blk && blk->isValid()) {
- assert(blk->tag == blkAddr);
- } else {
- blk = nullptr;
- }
- return blk;
-}
-
-CacheBlk*
-FALRU::findBlockBySetAndWay(int set, int way) const
-{
- assert(set == 0);
- return &blks[way];
-}
-
-CacheBlk*
-FALRU::findVictim(Addr addr)
-{
- FALRUBlk * blk = tail;
- assert(blk->inCache == 0);
- moveToHead(blk);
- tagHash.erase(blk->tag);
- tagHash[blkAlign(addr)] = blk;
- if (blk->isValid()) {
- replacements[0]++;
- } else {
- tagsInUse++;
- blk->isTouched = true;
- if (!warmedUp && tagsInUse.value() >= warmupBound) {
- warmedUp = true;
- warmupCycle = curTick();
- }
- }
- //assert(check());
- return blk;
-}
-
-void
-FALRU::insertBlock(PacketPtr pkt, CacheBlk *blk)
-{
-}
-
-void
-FALRU::moveToHead(FALRUBlk *blk)
-{
- int updateMask = blk->inCache ^ cacheMask;
- for (unsigned 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 == nullptr);
- tail = blk->prev;
- tail->next = nullptr;
- } else {
- blk->prev->next = blk->next;
- blk->next->prev = blk->prev;
- }
- blk->next = head;
- blk->prev = nullptr;
- head->prev = blk;
- head = blk;
- }
-}
-
-bool
-FALRU::check()
-{
- FALRUBlk* blk = head;
- int tot_size = 0;
- int boundary = 1<<17;
- int j = 0;
- int flags = cacheMask;
- while (blk) {
- tot_size += blkSize;
- if (blk->inCache != flags) {
- return false;
- }
- if (tot_size == boundary && blk != tail) {
- if (cacheBoundaries[j] != blk) {
- return false;
- }
- flags &=~(1 << j);
- boundary = boundary<<1;
- ++j;
- }
- blk = blk->next;
- }
- return true;
-}
-
-FALRU *
-FALRUParams::create()
-{
- return new FALRU(this);
-}
-
diff --git a/src/mem/cache/tags/fa_lru.hh b/src/mem/cache/tags/fa_lru.hh
deleted file mode 100644
index a266fb5..0000000
--- a/src/mem/cache/tags/fa_lru.hh
+++ /dev/null
@@ -1,281 +0,0 @@
-/*
- * Copyright (c) 2012-2013,2016 ARM Limited
- * All rights reserved.
- *
- * The license below extends only to copyright in the software and shall
- * not be construed as granting a license to any other intellectual
- * property including but not limited to intellectual property relating
- * to a hardware implementation of the functionality of the software
- * licensed hereunder. You may use the software subject to the license
- * terms below provided that you ensure that this notice is replicated
- * unmodified and in its entirety in all distributions of the software,
- * modified or unmodified, in source code or in binary form.
- *
- * Copyright (c) 2003-2005 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 __MEM_CACHE_TAGS_FA_LRU_HH__
-#define __MEM_CACHE_TAGS_FA_LRU_HH__
-
-#include <list>
-#include <unordered_map>
-
-#include "mem/cache/base.hh"
-#include "mem/cache/blk.hh"
-#include "mem/cache/tags/base.hh"
-#include "mem/packet.hh"
-#include "params/FALRU.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;
-
- protected:
- /** 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. */
- unsigned 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 std::unordered_map<Addr, FALRUBlk *, std::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:
-
- typedef FALRUParams Params;
-
- /**
- * Construct and initialize this cache tagstore.
- */
- FALRU(const Params *p);
- ~FALRU();
-
- /**
- * Register the stats for this object.
- * @param name The name to prepend to the stats name.
- */
- void regStats() override;
-
- /**
- * Invalidate a cache block.
- * @param blk The block to invalidate.
- */
- void invalidate(CacheBlk *blk) override;
-
- /**
- * Access block and update replacement data. May not succeed, in which
- * case nullptr pointer is returned. This has all the implications of
a
- * cache access and should only be used as such.
- * Returns the access latency and inCache flags as a side effect.
- * @param addr The address to look for.
- * @param is_secure True if the target memory space is secure.
- * @param lat The latency of the access.
- * @param inCache The FALRUBlk::inCache flags.
- * @return Pointer to the cache block.
- */
- CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat,
- int *inCache);
-
- /**
- * Just a wrapper of above function to conform with the base interface.
- */
- CacheBlk* accessBlock(Addr addr, bool is_secure, Cycles &lat) override;
-
- /**
- * Find the block in the cache, do not update the replacement data.
- * @param addr The address to look for.
- * @param is_secure True if the target memory space is secure.
- * @param asid The address space ID.
- * @return Pointer to the cache block.
- */
- CacheBlk* findBlock(Addr addr, bool is_secure) const override;
-
- /**
- * Find a replacement block for the address provided.
- * @param pkt The request to a find a replacement candidate for.
- * @return The block to place the replacement in.
- */
- CacheBlk* findVictim(Addr addr) override;
-
- void insertBlock(PacketPtr pkt, CacheBlk *blk) override;
-
- /**
- * Find the cache block given set and way
- * @param set The set of the block.
- * @param way The way of the block.
- * @return The cache block.
- */
- CacheBlk* findBlockBySetAndWay(int set, int way) const override;
-
- /**
- * Generate the tag from the addres. For fully associative this is
just the
- * block address.
- * @param addr The address to get the tag from.
- * @return The tag.
- */
- Addr extractTag(Addr addr) const override
- {
- 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 override
- {
- return 0;
- }
-
- /**
- * 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, unsigned set) const override
- {
- return (tag);
- }
-
- /**
- * @todo Implement as in lru. Currently not used
- */
- virtual std::string print() const override { return ""; }
-
- /**
- * Visit each block in the tag store and apply a visitor to the
- * block.
- *
- * The visitor should be a function (or object that behaves like a
- * function) that takes a cache block reference as its parameter
- * and returns a bool. A visitor can request the traversal to be
- * stopped by returning false, returning true causes it to be
- * called for the next block in the tag store.
- *
- * \param visitor Visitor to call on each block.
- */
- void forEachBlk(CacheBlkVisitor &visitor) override {
- for (int i = 0; i < numBlocks; i++) {
- if (!visitor(blks[i]))
- return;
- }
- }
-
-};
-
-#endif // __MEM_CACHE_TAGS_FA_LRU_HH__
--
To view, visit https://gem5-review.googlesource.com/8366
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings
Gerrit-Project: public/gem5
Gerrit-Branch: master
Gerrit-MessageType: newchange
Gerrit-Change-Id: Iebee8bf7f17ccc7fc7644267276046f34923f3d7
Gerrit-Change-Number: 8366
Gerrit-PatchSet: 1
Gerrit-Owner: Daniel Carvalho <[email protected]>
_______________________________________________
gem5-dev mailing list
[email protected]
http://m5sim.org/mailman/listinfo/gem5-dev
