diff options
| -rw-r--r-- | src/mem/cache/tags/SConscript | 1 | ||||
| -rw-r--r-- | src/mem/cache/tags/Tags.py | 3 | ||||
| -rw-r--r-- | src/mem/cache/tags/base_set_assoc.hh | 4 | ||||
| -rw-r--r-- | src/mem/cache/tags/skewed_assoc.cc | 241 | ||||
| -rw-r--r-- | src/mem/cache/tags/skewed_assoc.hh | 166 |
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__ |