summaryrefslogtreecommitdiff
path: root/src/mem/cache/tags/indexing_policies/skewed_associative.cc
diff options
context:
space:
mode:
Diffstat (limited to 'src/mem/cache/tags/indexing_policies/skewed_associative.cc')
-rw-r--r--src/mem/cache/tags/indexing_policies/skewed_associative.cc226
1 files changed, 226 insertions, 0 deletions
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);
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-16 03:36:35 +0000