mem: refactor LRU cache tags and add random replacement tags

this patch implements a new tags class that uses a random replacement policy.
these tags prefer to evict invalid blocks first, if none are available a
replacement candidate is chosen at random.

this patch factors out the common code in the LRU class and creates a new
abstract class: the BaseSetAssoc class. any set associative tag class must
implement the functionality related to the actual replacement policy in the
following methods:

accessBlock()
findVictim()
insertBlock()
invalidate()

10 files changed, 806 insertions, 461 deletions

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