mem-cache: Split Tags for indexing policies

Split indexing functionality from tags, so that code duplication
is reduced when adding new classes that use different indexing
policies, such as set associative, skewed associative or other
hash-based policies.

An indexing policy defines the mapping between an address' set
and its physical location. For example, a conventional set assoc
cache maps an address to all ways in a set using an immutable
function, that is, a set x is always mapped to set x. However,
skewed assoc caches map an address to a different set for each way,
using a skewing function.

FALRU has been left unmodified as it is a specialization with its
own complexity.

Change-Id: I0838b41663f21eba0aeab7aeb7839e3703ca3324
Reviewed-on: https://gem5-review.googlesource.com/c/8885
Reviewed-by: Jason Lowe-Power <jason@lowepower.com>
Maintainer: Jason Lowe-Power <jason@lowepower.com>

8 files changed, 973 insertions, 0 deletions

diff --git a/src/mem/cache/tags/indexing_policies/IndexingPolicies.py b/src/mem/cache/tags/indexing_policies/IndexingPolicies.py
new file mode 100644
index 000000000..c33a1d7df
--- /dev/null
+++ b/src/mem/cache/tags/indexing_policies/IndexingPolicies.py
@@ -0,0 +1,55 @@
+# Copyright (c) 2018 Inria
+# 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: Daniel Carvalho
+
+from m5.params import *
+from m5.proxy import *
+from m5.SimObject import SimObject
+
+class BaseIndexingPolicy(SimObject):
+    type = 'BaseIndexingPolicy'
+    abstract = True
+    cxx_header = "mem/cache/tags/indexing_policies/base.hh"
+
+    # Get the size from the parent (cache)
+    size = Param.MemorySize(Parent.size, "capacity in bytes")
+
+    # Get the entry size from the parent (tags)
+    entry_size = Param.Int(Parent.entry_size, "entry size in bytes")
+
+    # Get the associativity
+    assoc = Param.Int(Parent.assoc, "associativity")
+
+class SetAssociative(BaseIndexingPolicy):
+    type = 'SetAssociative'
+    cxx_class = 'SetAssociative'
+    cxx_header = "mem/cache/tags/indexing_policies/set_associative.hh"
+
+class SkewedAssociative(BaseIndexingPolicy):
+    type = 'SkewedAssociative'
+    cxx_class = 'SkewedAssociative'
+    cxx_header = "mem/cache/tags/indexing_policies/skewed_associative.hh"
diff --git a/src/mem/cache/tags/indexing_policies/SConscript b/src/mem/cache/tags/indexing_policies/SConscript
new file mode 100644
index 000000000..9f57bd641
--- /dev/null
+++ b/src/mem/cache/tags/indexing_policies/SConscript
@@ -0,0 +1,36 @@
+# -*- mode:python -*-
+
+# Copyright (c) 2018 Inria.
+#
+# 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: Daniel Carvalho
+
+Import('*')
+
+SimObject('IndexingPolicies.py')
+
+Source('base.cc')
+Source('set_associative.cc')
+Source('skewed_associative.cc')
diff --git a/src/mem/cache/tags/indexing_policies/base.cc b/src/mem/cache/tags/indexing_policies/base.cc
new file mode 100644
index 000000000..f27bedd4a
--- /dev/null
+++ b/src/mem/cache/tags/indexing_policies/base.cc
@@ -0,0 +1,102 @@
+/*
+ * Copyright (c) 2018 Inria
+ * Copyright (c) 2012-2014,2017 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: Daniel Carvalho
+ *          Erik Hallnor
+ */
+
+/**
+ * @file
+ * Definitions of a common framework for indexing policies.
+ */
+
+#include "mem/cache/tags/indexing_policies/base.hh"
+
+#include <cstdlib>
+
+#include "base/intmath.hh"
+#include "base/logging.hh"
+#include "mem/cache/replacement_policies/base.hh"
+
+BaseIndexingPolicy::BaseIndexingPolicy(const Params *p)
+    : SimObject(p), assoc(p->assoc),
+      numSets(p->size / (p->entry_size * assoc)),
+      setShift(floorLog2(p->entry_size)), setMask(numSets - 1), sets(numSets),
+      tagShift(setShift + floorLog2(numSets))
+{
+    fatal_if(!isPowerOf2(numSets), "# of sets must be non-zero and a power " \
+             "of 2");
+    fatal_if(assoc <= 0, "associativity must be greater than zero");
+
+    // Make space for the entries
+    for (uint32_t i = 0; i < numSets; ++i) {
+        sets[i].resize(assoc);
+    }
+}
+
+ReplaceableEntry*
+BaseIndexingPolicy::getEntry(const uint32_t set, const uint32_t way) const
+{
+    return sets[set][way];
+}
+
+void
+BaseIndexingPolicy::setEntry(ReplaceableEntry* entry, const uint64_t index)
+{
+    // Calculate set and way from entry index
+    const std::lldiv_t div_result = std::div((long long)index, assoc);
+    const uint32_t set = div_result.quot;
+    const uint32_t way = div_result.rem;
+
+    // Sanity check
+    assert(set < numSets);
+
+    // Assign a free pointer
+    sets[set][way] = entry;
+
+    // Inform the entry its position
+    entry->setPosition(set, way);
+}
+
+Addr
+BaseIndexingPolicy::extractTag(const Addr addr) const
+{
+    return (addr >> tagShift);
+}
diff --git a/src/mem/cache/tags/indexing_policies/base.hh b/src/mem/cache/tags/indexing_policies/base.hh
new file mode 100644
index 000000000..02c175d1a
--- /dev/null
+++ b/src/mem/cache/tags/indexing_policies/base.hh
@@ -0,0 +1,163 @@
+/*
+ * Copyright (c) 2018 Inria
+ * Copyright (c) 2012-2014,2017 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: Daniel Carvalho
+ *          Erik Hallnor
+ */
+
+/**
+ * @file
+ * Declaration of a common framework for indexing policies.
+ */
+
+#ifndef __MEM_CACHE_INDEXING_POLICIES_BASE_HH__
+#define __MEM_CACHE_INDEXING_POLICIES_BASE_HH__
+
+#include <vector>
+
+#include "params/BaseIndexingPolicy.hh"
+#include "sim/sim_object.hh"
+
+class ReplaceableEntry;
+
+/**
+ * A common base class for indexing table locations. Classes that inherit
+ * from it determine hash functions that should be applied based on the set
+ * and way. These functions are then applied to re-map the original values.
+ * @sa  \ref gem5MemorySystem "gem5 Memory System"
+ */
+class BaseIndexingPolicy : public SimObject
+{
+  protected:
+    /**
+     * The associativity.
+     */
+    const unsigned assoc;
+
+    /**
+     * The number of sets in the cache.
+     */
+    const uint32_t numSets;
+
+    /**
+     * The amount to shift the address to get the set.
+     */
+    const int setShift;
+
+    /**
+     * Mask out all bits that aren't part of the set index.
+     */
+    const unsigned setMask;
+
+    /**
+     * The cache sets.
+     */
+    std::vector<std::vector<ReplaceableEntry*>> sets;
+
+    /**
+     * The amount to shift the address to get the tag.
+     */
+    const int tagShift;
+
+  public:
+    /**
+     * Convenience typedef.
+     */
+    typedef BaseIndexingPolicyParams Params;
+
+    /**
+     * Construct and initialize this policy.
+     */
+    BaseIndexingPolicy(const Params *p);
+
+    /**
+     * Destructor.
+     */
+    ~BaseIndexingPolicy() {};
+
+    /**
+     * Associate a pointer to an entry to its physical counterpart.
+     *
+     * @param entry The entry pointer.
+     * @param index An unique index for the entry.
+     */
+    void setEntry(ReplaceableEntry* entry, const uint64_t index);
+
+    /**
+     * Get an entry based on its set and way. All entries must have been set
+     * already before calling this function.
+     *
+     * @param set The set of the desired entry.
+     * @param way The way of the desired entry.
+     * @return entry The entry pointer.
+     */
+    ReplaceableEntry* getEntry(const uint32_t set, const uint32_t way) const;
+
+    /**
+     * Generate the tag from the given address.
+     *
+     * @param addr The address to get the tag from.
+     * @return The tag of the address.
+     */
+    Addr extractTag(const Addr addr) const;
+
+    /**
+     * Find all possible entries for insertion and replacement of an address.
+     * Should be called immediately before ReplacementPolicy's findVictim()
+     * not to break cache resizing.
+     *
+     * @param addr The addr to a find possible entries for.
+     * @return The possible entries.
+     */
+    virtual std::vector<ReplaceableEntry*> getPossibleEntries(const Addr addr)
+                                                                    const = 0;
+
+    /**
+     * Regenerate an entry's address from its tag and assigned indexing bits.
+     *
+     * @param tag The tag bits.
+     * @param entry The entry.
+     * @return the entry's original address.
+     */
+    virtual Addr regenerateAddr(const Addr tag, const ReplaceableEntry* entry)
+                                                                    const = 0;
+};
+
+#endif //__MEM_CACHE_INDEXING_POLICIES_BASE_HH__
diff --git a/src/mem/cache/tags/indexing_policies/set_associative.cc b/src/mem/cache/tags/indexing_policies/set_associative.cc
new file mode 100644
index 000000000..d5fe8ffd0
--- /dev/null
+++ b/src/mem/cache/tags/indexing_policies/set_associative.cc
@@ -0,0 +1,82 @@
+/*
+ * Copyright (c) 2018 Inria
+ * Copyright (c) 2012-2014,2017 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: Daniel Carvalho
+ *          Erik Hallnor
+ */
+
+/**
+ * @file
+ * Definitions of a set associative indexing policy.
+ */
+
+#include "mem/cache/tags/indexing_policies/set_associative.hh"
+
+#include "mem/cache/replacement_policies/base.hh"
+
+SetAssociative::SetAssociative(const Params *p)
+    : BaseIndexingPolicy(p)
+{
+}
+
+uint32_t
+SetAssociative::extractSet(const Addr addr) const
+{
+    return (addr >> setShift) & setMask;
+}
+
+Addr
+SetAssociative::regenerateAddr(const Addr tag, const ReplaceableEntry* entry)
+                                                                        const
+{
+    return (tag << tagShift) | (entry->getSet() << setShift);
+}
+
+std::vector<ReplaceableEntry*>
+SetAssociative::getPossibleEntries(const Addr addr) const
+{
+    return sets[extractSet(addr)];
+}
+
+SetAssociative*
+SetAssociativeParams::create()
+{
+    return new SetAssociative(this);
+}
diff --git a/src/mem/cache/tags/indexing_policies/set_associative.hh b/src/mem/cache/tags/indexing_policies/set_associative.hh
new file mode 100644
index 000000000..216172395
--- /dev/null
+++ b/src/mem/cache/tags/indexing_policies/set_associative.hh
@@ -0,0 +1,132 @@
+/*
+ * Copyright (c) 2018 Inria
+ * Copyright (c) 2012-2014,2017 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: Daniel Carvalho
+ *          Erik Hallnor
+ */
+
+/**
+ * @file
+ * Declaration of a set associative indexing policy.
+ */
+
+#ifndef __MEM_CACHE_INDEXING_POLICIES_SET_ASSOCIATIVE_HH__
+#define __MEM_CACHE_INDEXING_POLICIES_SET_ASSOCIATIVE_HH__
+
+#include <vector>
+
+#include "mem/cache/tags/indexing_policies/base.hh"
+#include "params/SetAssociative.hh"
+
+class ReplaceableEntry;
+
+/**
+ * A set associative indexing policy.
+ * @sa  \ref gem5MemorySystem "gem5 Memory System"
+ *
+ * The set associative indexing policy has an immutable/identity mapping, so a
+ * value x is always mapped to set x, independent of the way, that is,
+ * Hash(A, 0) = Hash(A, 1) = Hash(A, N-1), where N is the number of ways.
+ *
+ * For example, let's assume address A maps to set 3 on way 0. This policy
+ * makes so that A is also mappable to set 3 on every other way. Visually, the
+ * possible locations of A are, for a table with 4 ways and 8 sets:
+ *    Way 0   1   2   3
+ *  Set   _   _   _   _
+ *    0  |_| |_| |_| |_|
+ *    1  |_| |_| |_| |_|
+ *    2  |_| |_| |_| |_|
+ *    3  |X| |X| |X| |X|
+ *    4  |_| |_| |_| |_|
+ *    5  |_| |_| |_| |_|
+ *    6  |_| |_| |_| |_|
+ *    7  |_| |_| |_| |_|
+ */
+class SetAssociative : public BaseIndexingPolicy
+{
+  private:
+    /**
+     * Apply a hash function to calculate address set.
+     *
+     * @param addr The address to calculate the set for.
+     * @return The set index for given combination of address and way.
+     */
+    uint32_t extractSet(const Addr addr) const;
+
+  public:
+    /**
+     * Convenience typedef.
+     */
+    typedef SetAssociativeParams Params;
+
+    /**
+     * Construct and initialize this policy.
+     */
+    SetAssociative(const Params *p);
+
+    /**
+     * Destructor.
+     */
+    ~SetAssociative() {};
+
+    /**
+     * Find all possible entries for insertion and replacement of an address.
+     * Should be called immediately before ReplacementPolicy's findVictim()
+     * not to break cache resizing.
+     * Returns entries in all ways belonging to the set of the address.
+     *
+     * @param addr The addr to a find possible entries for.
+     * @return The possible entries.
+     */
+    std::vector<ReplaceableEntry*> getPossibleEntries(const Addr addr) const
+                                                                     override;
+
+    /**
+     * Regenerate an entry's address from its tag and assigned set and way.
+     *
+     * @param tag The tag bits.
+     * @param entry The entry.
+     * @return the entry's original addr value.
+     */
+    Addr regenerateAddr(const Addr tag, const ReplaceableEntry* entry) const
+                                                                   override;
+};
+
+#endif //__MEM_CACHE_INDEXING_POLICIES_SET_ASSOCIATIVE_HH__
diff --git a/src/mem/cache/tags/indexing_policies/skewed_associative.cc b/src/mem/cache/tags/indexing_policies/skewed_associative.cc
new file mode 100644
index 000000000..d1765e5d6
--- /dev/null
+++ b/src/mem/cache/tags/indexing_policies/skewed_associative.cc
@@ -0,0 +1,226 @@
+/*
+ * Copyright (c) 2018 Inria
+ * 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: Daniel Carvalho
+ */
+
+/**
+ * @file
+ * Definitions of a skewed associative indexing policy.
+ */
+
+#include "mem/cache/tags/indexing_policies/skewed_associative.hh"
+
+#include "base/bitfield.hh"
+#include "base/intmath.hh"
+#include "base/logging.hh"
+#include "mem/cache/replacement_policies/base.hh"
+
+SkewedAssociative::SkewedAssociative(const Params *p)
+    : BaseIndexingPolicy(p), msbShift(floorLog2(numSets) - 1)
+{
+    if (assoc > NUM_SKEWING_FUNCTIONS) {
+        warn_once("Associativity higher than number of skewing functions. " \
+                  "Expect sub-optimal skewing.\n");
+    }
+
+    // Check if set is too big to do skewing. If using big sets, rewrite
+    // skewing functions accordingly to make good use of the hashing function
+    panic_if(setShift + 2 * (msbShift + 1) > 64, "Unsuported number of bits " \
+             "for the skewing functions.");
+
+    // We must have more than two sets, otherwise the MSB and LSB are the same
+    // bit, and the xor of them will always be 0
+    fatal_if(numSets <= 2, "The number of sets must be greater than 2");
+}
+
+Addr
+SkewedAssociative::hash(const Addr addr) const
+{
+    // Get relevant bits
+    const uint8_t lsb = bits<Addr>(addr, 0);
+    const uint8_t msb = bits<Addr>(addr, msbShift);
+    const uint8_t xor_bit = msb ^ lsb;
+
+    // Shift-off LSB and set new MSB as xor of old LSB and MSB
+    return insertBits<Addr, uint8_t>(addr >> 1, msbShift, xor_bit);
+}
+
+Addr
+SkewedAssociative::dehash(const Addr addr) const
+{
+    // Get relevant bits. The original MSB is one bit away on the current MSB
+    // (which is the XOR bit). The original LSB can be retrieved from inverting
+    // the xor that generated the XOR bit.
+    const uint8_t msb = bits<Addr>(addr, msbShift - 1);
+    const uint8_t xor_bit = bits<Addr>(addr, msbShift);
+    const uint8_t lsb = msb ^ xor_bit;
+
+    // Remove current MSB (XOR bit), shift left and add LSB back
+    const Addr addr_no_msb = mbits<Addr>(addr, msbShift - 1, 0);
+    return insertBits<Addr, uint8_t>(addr_no_msb << 1, 0, lsb);
+}
+
+Addr
+SkewedAssociative::skew(const Addr addr, const uint32_t way) const
+{
+    // Assume an address of size A bits can be decomposed into
+    // {addr3, addr2, addr1, addr0}, where:
+    //   addr0 (M bits) = Block offset;
+    //   addr1 (N bits) = Set bits in conventional cache;
+    //   addr3 (A - M - 2*N bits), addr2 (N bits) = Tag bits.
+    // We use addr1 and addr2, as proposed in the original paper
+    Addr addr1 = bits<Addr>(addr, msbShift, 0);
+    const Addr addr2 = bits<Addr>(addr, 2 * (msbShift + 1) - 1, msbShift + 1);
+
+    // Select and apply skewing function for given way
+    switch (way % NUM_SKEWING_FUNCTIONS) {
+      case 0:
+        addr1 = hash(addr1) ^ hash(addr2) ^ addr2;
+        break;
+      case 1:
+        addr1 = hash(addr1) ^ hash(addr2) ^ addr1;
+        break;
+      case 2:
+        addr1 = hash(addr1) ^ dehash(addr2) ^ addr2;
+        break;
+      case 3:
+        addr1 = hash(addr1) ^ dehash(addr2) ^ addr1;
+        break;
+      case 4:
+        addr1 = dehash(addr1) ^ hash(addr2) ^ addr2;
+        break;
+      case 5:
+        addr1 = dehash(addr1) ^ hash(addr2) ^ addr1;
+        break;
+      case 6:
+        addr1 = dehash(addr1) ^ dehash(addr2) ^ addr2;
+        break;
+      case 7:
+        addr1 = dehash(addr1) ^ dehash(addr2) ^ addr1;
+        break;
+      default:
+        panic("A skewing function has not been implemented for this way.");
+    }
+
+    // If we have more than 8 ways, just pile them up on hashes. This is not
+    // the optimal solution, and can be improved by adding more skewing
+    // functions to the previous selector
+    for (uint32_t i = 0; i < way/NUM_SKEWING_FUNCTIONS; i++) {
+        addr1 = hash(addr1);
+    }
+
+    return addr1;
+}
+
+Addr
+SkewedAssociative::deskew(const Addr addr, const uint32_t way) const
+{
+    // Get relevant bits of the addr
+    Addr addr1 = bits<Addr>(addr, msbShift, 0);
+    const Addr addr2 = bits<Addr>(addr, 2 * (msbShift + 1) - 1, msbShift + 1);
+
+    // If we have more than NUM_SKEWING_FUNCTIONS ways, unpile the hashes
+    if (way >= NUM_SKEWING_FUNCTIONS) {
+        for (uint32_t i = 0; i < way/NUM_SKEWING_FUNCTIONS; i++) {
+            addr1 = dehash(addr1);
+        }
+    }
+
+    // Select and apply skewing function for given way
+    switch (way % 8) {
+      case 0:
+        return dehash(addr1 ^ hash(addr2) ^ addr2);
+      case 1:
+        addr1 = addr1 ^ hash(addr2);
+        for (int i = 0; i < msbShift; i++) {
+            addr1 = hash(addr1);
+        }
+        return addr1;
+      case 2:
+        return dehash(addr1 ^ dehash(addr2) ^ addr2);
+      case 3:
+        addr1 = addr1 ^ dehash(addr2);
+        for (int i = 0; i < msbShift; i++) {
+            addr1 = hash(addr1);
+        }
+        return addr1;
+      case 4:
+        return hash(addr1 ^ hash(addr2) ^ addr2);
+      case 5:
+        addr1 = addr1 ^ hash(addr2);
+        for (int i = 0; i <= msbShift; i++) {
+            addr1 = hash(addr1);
+        }
+        return addr1;
+      case 6:
+        return hash(addr1 ^ dehash(addr2) ^ addr2);
+      case 7:
+        addr1 = addr1 ^ dehash(addr2);
+        for (int i = 0; i <= msbShift; i++) {
+            addr1 = hash(addr1);
+        }
+        return addr1;
+      default:
+        panic("A skewing function has not been implemented for this way.");
+    }
+}
+
+uint32_t
+SkewedAssociative::extractSet(const Addr addr, const uint32_t way) const
+{
+    return skew(addr >> setShift, way) & setMask;
+}
+
+Addr
+SkewedAssociative::regenerateAddr(const Addr tag,
+                                  const ReplaceableEntry* entry) const
+{
+    const Addr addr_set = (tag << (msbShift + 1)) | entry->getSet();
+    return (tag << tagShift) |
+           ((deskew(addr_set, entry->getWay()) & setMask) << setShift);
+}
+
+std::vector<ReplaceableEntry*>
+SkewedAssociative::getPossibleEntries(const Addr addr) const
+{
+    std::vector<ReplaceableEntry*> entries;
+
+    // Parse all ways
+    for (uint32_t way = 0; way < assoc; ++way) {
+        // Apply hash to get set, and get way entry in it
+        entries.push_back(sets[extractSet(addr, way)][way]);
+    }
+
+    return entries;
+}
+
+SkewedAssociative *
+SkewedAssociativeParams::create()
+{
+    return new SkewedAssociative(this);
+}
diff --git a/src/mem/cache/tags/indexing_policies/skewed_associative.hh b/src/mem/cache/tags/indexing_policies/skewed_associative.hh
new file mode 100644
index 000000000..de3e57963
--- /dev/null
+++ b/src/mem/cache/tags/indexing_policies/skewed_associative.hh
@@ -0,0 +1,177 @@
+/*
+ * Copyright (c) 2018 Inria
+ * 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: Daniel Carvalho
+ */
+
+/**
+ * @file
+ * Declaration of a skewed associative indexing policy.
+ */
+
+#ifndef __MEM_CACHE_INDEXING_POLICIES_SKEWED_ASSOCIATIVE_HH__
+#define __MEM_CACHE_INDEXING_POLICIES_SKEWED_ASSOCIATIVE_HH__
+
+#include <vector>
+
+#include "mem/cache/tags/indexing_policies/base.hh"
+#include "params/SkewedAssociative.hh"
+
+class ReplaceableEntry;
+
+/**
+ * A skewed associative indexing policy.
+ * @sa  \ref gem5MemorySystem "gem5 Memory System"
+ *
+ * The skewed indexing policy has a variable mapping based on a hash function,
+ * so a value x can be mapped to different sets, based on the way being used.
+ *
+ * For example, let's assume address A maps to set 3 on way 0. It will likely
+ * have a different set for every other way. Visually, the possible locations
+ * of A are, for a table with 4 ways and 8 sets (arbitrarily chosen sets; these
+ * locations depend on A and the hashing function used):
+ *    Way 0   1   2   3
+ *  Set   _   _   _   _
+ *    0  |_| |_| |X| |_|
+ *    1  |_| |_| |_| |X|
+ *    2  |_| |_| |_| |_|
+ *    3  |X| |_| |_| |_|
+ *    4  |_| |_| |_| |_|
+ *    5  |_| |X| |_| |_|
+ *    6  |_| |_| |_| |_|
+ *    7  |_| |_| |_| |_|
+ *
+ * If provided with an associativity higher than the number of skewing
+ * functions, the skewing functions of the extra ways might be sub-optimal.
+ */
+class SkewedAssociative : public BaseIndexingPolicy
+{
+  private:
+    /**
+     * The number of skewing functions implemented. Should be updated if more
+     * functions are added. If more than this number of skewing functions are
+     * needed (i.e., assoc > this value), we programatically generate new ones,
+     * which may be sub-optimal.
+     */
+    const int NUM_SKEWING_FUNCTIONS = 8;
+
+    /**
+     * The amount to shift a set index to get its MSB.
+     */
+    const int msbShift;
+
+    /**
+     * The hash function itself. Uses the hash function H, as described in
+     * "Skewed-Associative Caches", from Seznec et al. (section 3.3): It
+     * applies an XOR to the MSB and LSB, shifts all bits one bit to the right,
+     * and set the result of the XOR as the new MSB.
+     *
+     * This function is not bijective if the address has only 1 bit, as the MSB
+     * and LSB will be the same, and therefore the xor will always be 0.
+     *
+     * @param addr The address to be hashed.
+     * @param The hashed address.
+     */
+    Addr hash(const Addr addr) const;
+
+    /**
+     * Inverse of the hash function.
+     * @sa hash().
+     *
+     * @param addr The address to be dehashed.
+     * @param The dehashed address.
+     */
+    Addr dehash(const Addr addr) const;
+
+    /**
+     * Address skewing function selection. It selects and applies one of the
+     * skewing functions functions based on the way provided.
+     *
+     * @param addr Address to be skewed. Should contain the set and tag bits.
+     * @param way The cache way, used to select a hash function.
+     * @return The skewed address.
+     */
+    Addr skew(const Addr addr, const uint32_t way) const;
+
+    /**
+     * Address deskewing function (inverse of the skew function) of the given
+     * way.
+     * @sa skew()
+     *
+     * @param addr Address to be deskewed. Should contain the set and tag bits.
+     * @param way The cache way, used to select a hash function.
+     * @return The deskewed address.
+     */
+    Addr deskew(const Addr addr, const uint32_t way) const;
+
+    /**
+     * Apply a skewing function to calculate address' set given a way.
+     *
+     * @param addr The address to calculate the set for.
+     * @param way The way to get the set from.
+     * @return The set index for given combination of address and way.
+     */
+    uint32_t extractSet(const Addr addr, const uint32_t way) const;
+
+  public:
+    /** Convenience typedef. */
+     typedef SkewedAssociativeParams Params;
+
+    /**
+     * Construct and initialize this policy.
+     */
+    SkewedAssociative(const Params *p);
+
+    /**
+     * Destructor.
+     */
+    ~SkewedAssociative() {};
+
+    /**
+     * Find all possible entries for insertion and replacement of an address.
+     * Should be called immediately before ReplacementPolicy's findVictim()
+     * not to break cache resizing.
+     *
+     * @param addr The addr to a find possible entries for.
+     * @return The possible entries.
+     */
+    std::vector<ReplaceableEntry*> getPossibleEntries(const Addr addr) const
+                                                                   override;
+
+    /**
+     * Regenerate an entry's address from its tag and assigned set and way.
+     * Uses the inverse of the skewing function.
+     *
+     * @param tag The tag bits.
+     * @param entry The entry.
+     * @return the entry's address.
+     */
+    Addr regenerateAddr(const Addr tag, const ReplaceableEntry* entry) const
+                                                                   override;
+};
+
+#endif //__MEM_CACHE_INDEXING_POLICIES_SKEWED_ASSOCIATIVE_HH__