mem-cache: Create Skewed Assoc placement policy

Create a class that implements the skewed associative placement
policy. It uses the hash function and expansions of the skewing
functions described in "Skewed-Associative caches", by Seznec.

Only 8 skewing functions are implemented, and therefore if more
are needed a hash function will be recursively applied on top
of the output of one of these functions to generate different
values. This is not optimal, and if more functions are needed
it might be more effective to implement them.

Change-Id: Ibc77edffd8128114a8b200cec5d8deedfb5105cb
Reviewed-on: https://gem5-review.googlesource.com/8886
Reviewed-by: Nikos Nikoleris <nikos.nikoleris@arm.com>
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>

5 files changed, 413 insertions, 2 deletions

diff --git a/src/mem/cache/tags/SConscript b/src/mem/cache/tags/SConscript
index 136abac2c..1a3780ff1 100644
--- a/src/mem/cache/tags/SConscript
+++ b/src/mem/cache/tags/SConscript
@@ -36,3 +36,4 @@ Source('base.cc')
 Source('base_set_assoc.cc')
 Source('fa_lru.cc')
 Source('sector_tags.cc')
+Source('skewed_assoc.cc')
diff --git a/src/mem/cache/tags/Tags.py b/src/mem/cache/tags/Tags.py
index 8fdfdce61..781ac8e3f 100644
--- a/src/mem/cache/tags/Tags.py
+++ b/src/mem/cache/tags/Tags.py
@@ -96,3 +96,6 @@ class FALRU(BaseTags):
 
     min_tracked_cache_size = Param.MemorySize("128kB", "Minimum cache size for"
                                               " which we track statistics")
+class SkewedAssoc(BaseSetAssoc):
+    type = 'SkewedAssoc'
+    cxx_header = "mem/cache/tags/skewed_assoc.hh"
diff --git a/src/mem/cache/tags/base_set_assoc.hh b/src/mem/cache/tags/base_set_assoc.hh
index 61a16584f..8e4657fc1 100644
--- a/src/mem/cache/tags/base_set_assoc.hh
+++ b/src/mem/cache/tags/base_set_assoc.hh
@@ -183,9 +183,9 @@ class BaseSetAssoc : public BaseTags
     /**
      * 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.
      */
     CacheBlk* findBlock(Addr addr, bool is_secure) const override;
@@ -237,7 +237,7 @@ class BaseSetAssoc : public BaseTags
      * @param addr The addr to a find possible locations for.
      * @return The possible locations.
      */
-    const std::vector<CacheBlk*> getPossibleLocations(Addr addr) const
+    virtual const std::vector<CacheBlk*> getPossibleLocations(Addr addr) const
     {
         return sets[extractSet(addr)].blks;
     }
diff --git a/src/mem/cache/tags/skewed_assoc.cc b/src/mem/cache/tags/skewed_assoc.cc
new file mode 100644
index 000000000..044f8a3d7
--- /dev/null
+++ b/src/mem/cache/tags/skewed_assoc.cc
@@ -0,0 +1,241 @@
+/*
+ * 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 placement policy.
+ */
+
+#include "mem/cache/tags/skewed_assoc.hh"
+
+#include <vector>
+
+#include "base/logging.hh"
+
+SkewedAssoc::SkewedAssoc(const Params *p)
+    : BaseSetAssoc(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.");
+}
+
+Addr
+SkewedAssoc::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
+SkewedAssoc::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
+SkewedAssoc::skew(const Addr addr, const unsigned 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 (int i = 0; i < way/NUM_SKEWING_FUNCTIONS; i++) {
+        addr1 = hash(addr1);
+    }
+
+    return addr1;
+}
+
+Addr
+SkewedAssoc::deskew(const Addr addr, const unsigned 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 (int 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.");
+    }
+}
+
+unsigned
+SkewedAssoc::extractSet(Addr addr, unsigned way) const
+{
+    return skew(addr >> setShift, way) & setMask;
+}
+
+Addr
+SkewedAssoc::regenerateBlkAddr(const CacheBlk* blk) const
+{
+    const Addr addr = (blk->tag << (msbShift + 1)) | blk->set;
+    const Addr set = deskew(addr, blk->way) & setMask;
+    return (blk->tag << tagShift) | (set << setShift);
+}
+
+const std::vector<CacheBlk*>
+SkewedAssoc::getPossibleLocations(Addr addr) const
+{
+    std::vector<CacheBlk*> locations;
+
+    // Parse all ways
+    for (int way = 0; way < assoc; ++way) {
+        // Apply hash to get set, and get way entry in it
+        locations.push_back(sets[extractSet(addr, way)].blks[way]);
+    }
+
+    return locations;
+}
+
+CacheBlk*
+SkewedAssoc::findBlock(Addr addr, bool is_secure) const
+{
+    // Extract block tag
+    Addr tag = extractTag(addr);
+
+    // Find possible locations for the given address
+    std::vector<CacheBlk*> locations = getPossibleLocations(addr);
+
+    // Search for block
+    for (const auto& blk : locations) {
+        if ((blk->tag == tag) && blk->isValid() &&
+            (blk->isSecure() == is_secure)) {
+            return blk;
+        }
+    }
+
+    // Did not find block
+    return nullptr;
+}
+
+SkewedAssoc *
+SkewedAssocParams::create()
+{
+    return new SkewedAssoc(this);
+}
diff --git a/src/mem/cache/tags/skewed_assoc.hh b/src/mem/cache/tags/skewed_assoc.hh
new file mode 100644
index 000000000..7f5a75266
--- /dev/null
+++ b/src/mem/cache/tags/skewed_assoc.hh
@@ -0,0 +1,166 @@
+/*
+ * 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 tag store.
+ */
+
+#ifndef __MEM_CACHE_TAGS_SKEWED_ASSOC_HH__
+#define __MEM_CACHE_TAGS_SKEWED_ASSOC_HH__
+
+#include "mem/cache/blk.hh"
+#include "mem/cache/tags/base_set_assoc.hh"
+#include "params/SkewedAssoc.hh"
+
+/**
+ * A SkewedAssoc cache tag store.
+ * @sa \ref gem5MemorySystem "gem5 Memory System"
+ *
+ * The SkewedAssoc placement policy divides the cache into s sets of w
+ * cache lines (ways). A cache line has a different set mapping for each way,
+ * according to a skewing function.
+ *
+ * If provided with an associativity higher than the number of skewing
+ * functions, the skewing functions of the extra ways might be sub-optimal.
+ */
+class SkewedAssoc : public BaseSetAssoc
+{
+  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.
+     *
+     * @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 unsigned 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 unsigned 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.
+     */
+    unsigned extractSet(Addr addr, unsigned way) const;
+
+  public:
+    /** Convenience typedef. */
+     typedef SkewedAssocParams Params;
+
+    /**
+     * Construct and initialize this tag store.
+     */
+    SkewedAssoc(const Params *p);
+
+    /**
+     * Destructor
+     */
+    ~SkewedAssoc() {};
+
+    /**
+     * Find all possible block locations for insertion and replacement of
+     * an address. Should be called immediately before ReplacementPolicy's
+     * findVictim() not to break cache resizing.
+     * Returns blocks in all ways belonging to the set of the address.
+     *
+     * @param addr The addr to a find possible locations for.
+     * @return The possible locations.
+     */
+    const std::vector<CacheBlk*> getPossibleLocations(Addr addr) const
+                                                             override;
+
+    /**
+     * 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.
+     * @return Pointer to the cache block if found.
+     */
+    CacheBlk* findBlock(Addr addr, bool is_secure) const override;
+
+    /**
+     * Regenerate the block address from the tag, set and way. Uses the
+     * inverse of the skewing function.
+     *
+     * @param block The block.
+     * @return the block address.
+     */
+    Addr regenerateBlkAddr(const CacheBlk* blk) const override;
+};
+
+#endif //__MEM_CACHE_TAGS_SKEWED_ASSOC_HH__