diff options
Diffstat (limited to 'src/mem/cache/tags/indexing_policies')
| -rw-r--r-- | src/mem/cache/tags/indexing_policies/IndexingPolicies.py | 55 | ||||
| -rw-r--r-- | src/mem/cache/tags/indexing_policies/SConscript | 36 | ||||
| -rw-r--r-- | src/mem/cache/tags/indexing_policies/base.cc | 102 | ||||
| -rw-r--r-- | src/mem/cache/tags/indexing_policies/base.hh | 163 | ||||
| -rw-r--r-- | src/mem/cache/tags/indexing_policies/set_associative.cc | 82 | ||||
| -rw-r--r-- | src/mem/cache/tags/indexing_policies/set_associative.hh | 132 | ||||
| -rw-r--r-- | src/mem/cache/tags/indexing_policies/skewed_associative.cc | 226 | ||||
| -rw-r--r-- | src/mem/cache/tags/indexing_policies/skewed_associative.hh | 177 |
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__ |