113219Sodanrc@yahoo.com.br/* 213219Sodanrc@yahoo.com.br * Copyright (c) 2018 Inria 313219Sodanrc@yahoo.com.br * All rights reserved. 413219Sodanrc@yahoo.com.br * 513219Sodanrc@yahoo.com.br * Redistribution and use in source and binary forms, with or without 613219Sodanrc@yahoo.com.br * modification, are permitted provided that the following conditions are 713219Sodanrc@yahoo.com.br * met: redistributions of source code must retain the above copyright 813219Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer; 913219Sodanrc@yahoo.com.br * redistributions in binary form must reproduce the above copyright 1013219Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer in the 1113219Sodanrc@yahoo.com.br * documentation and/or other materials provided with the distribution; 1213219Sodanrc@yahoo.com.br * neither the name of the copyright holders nor the names of its 1313219Sodanrc@yahoo.com.br * contributors may be used to endorse or promote products derived from 1413219Sodanrc@yahoo.com.br * this software without specific prior written permission. 1513219Sodanrc@yahoo.com.br * 1613219Sodanrc@yahoo.com.br * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1713219Sodanrc@yahoo.com.br * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1813219Sodanrc@yahoo.com.br * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1913219Sodanrc@yahoo.com.br * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2013219Sodanrc@yahoo.com.br * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2113219Sodanrc@yahoo.com.br * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2213219Sodanrc@yahoo.com.br * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2313219Sodanrc@yahoo.com.br * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2413219Sodanrc@yahoo.com.br * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2513219Sodanrc@yahoo.com.br * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2613219Sodanrc@yahoo.com.br * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2713219Sodanrc@yahoo.com.br * 2813219Sodanrc@yahoo.com.br * Authors: Daniel Carvalho 2913219Sodanrc@yahoo.com.br */ 3013219Sodanrc@yahoo.com.br 3113219Sodanrc@yahoo.com.br/** 3213219Sodanrc@yahoo.com.br * @file 3313219Sodanrc@yahoo.com.br * Declaration of a skewed associative indexing policy. 3413219Sodanrc@yahoo.com.br */ 3513219Sodanrc@yahoo.com.br 3613219Sodanrc@yahoo.com.br#ifndef __MEM_CACHE_INDEXING_POLICIES_SKEWED_ASSOCIATIVE_HH__ 3713219Sodanrc@yahoo.com.br#define __MEM_CACHE_INDEXING_POLICIES_SKEWED_ASSOCIATIVE_HH__ 3813219Sodanrc@yahoo.com.br 3913219Sodanrc@yahoo.com.br#include <vector> 4013219Sodanrc@yahoo.com.br 4113219Sodanrc@yahoo.com.br#include "mem/cache/tags/indexing_policies/base.hh" 4213219Sodanrc@yahoo.com.br#include "params/SkewedAssociative.hh" 4313219Sodanrc@yahoo.com.br 4413219Sodanrc@yahoo.com.brclass ReplaceableEntry; 4513219Sodanrc@yahoo.com.br 4613219Sodanrc@yahoo.com.br/** 4713219Sodanrc@yahoo.com.br * A skewed associative indexing policy. 4813219Sodanrc@yahoo.com.br * @sa \ref gem5MemorySystem "gem5 Memory System" 4913219Sodanrc@yahoo.com.br * 5013219Sodanrc@yahoo.com.br * The skewed indexing policy has a variable mapping based on a hash function, 5113219Sodanrc@yahoo.com.br * so a value x can be mapped to different sets, based on the way being used. 5213219Sodanrc@yahoo.com.br * 5313219Sodanrc@yahoo.com.br * For example, let's assume address A maps to set 3 on way 0. It will likely 5413219Sodanrc@yahoo.com.br * have a different set for every other way. Visually, the possible locations 5513219Sodanrc@yahoo.com.br * of A are, for a table with 4 ways and 8 sets (arbitrarily chosen sets; these 5613219Sodanrc@yahoo.com.br * locations depend on A and the hashing function used): 5713219Sodanrc@yahoo.com.br * Way 0 1 2 3 5813219Sodanrc@yahoo.com.br * Set _ _ _ _ 5913219Sodanrc@yahoo.com.br * 0 |_| |_| |X| |_| 6013219Sodanrc@yahoo.com.br * 1 |_| |_| |_| |X| 6113219Sodanrc@yahoo.com.br * 2 |_| |_| |_| |_| 6213219Sodanrc@yahoo.com.br * 3 |X| |_| |_| |_| 6313219Sodanrc@yahoo.com.br * 4 |_| |_| |_| |_| 6413219Sodanrc@yahoo.com.br * 5 |_| |X| |_| |_| 6513219Sodanrc@yahoo.com.br * 6 |_| |_| |_| |_| 6613219Sodanrc@yahoo.com.br * 7 |_| |_| |_| |_| 6713219Sodanrc@yahoo.com.br * 6813219Sodanrc@yahoo.com.br * If provided with an associativity higher than the number of skewing 6913219Sodanrc@yahoo.com.br * functions, the skewing functions of the extra ways might be sub-optimal. 7013219Sodanrc@yahoo.com.br */ 7113219Sodanrc@yahoo.com.brclass SkewedAssociative : public BaseIndexingPolicy 7213219Sodanrc@yahoo.com.br{ 7313219Sodanrc@yahoo.com.br private: 7413219Sodanrc@yahoo.com.br /** 7513219Sodanrc@yahoo.com.br * The number of skewing functions implemented. Should be updated if more 7613219Sodanrc@yahoo.com.br * functions are added. If more than this number of skewing functions are 7713219Sodanrc@yahoo.com.br * needed (i.e., assoc > this value), we programatically generate new ones, 7813219Sodanrc@yahoo.com.br * which may be sub-optimal. 7913219Sodanrc@yahoo.com.br */ 8013219Sodanrc@yahoo.com.br const int NUM_SKEWING_FUNCTIONS = 8; 8113219Sodanrc@yahoo.com.br 8213219Sodanrc@yahoo.com.br /** 8313219Sodanrc@yahoo.com.br * The amount to shift a set index to get its MSB. 8413219Sodanrc@yahoo.com.br */ 8513219Sodanrc@yahoo.com.br const int msbShift; 8613219Sodanrc@yahoo.com.br 8713219Sodanrc@yahoo.com.br /** 8813219Sodanrc@yahoo.com.br * The hash function itself. Uses the hash function H, as described in 8913219Sodanrc@yahoo.com.br * "Skewed-Associative Caches", from Seznec et al. (section 3.3): It 9013219Sodanrc@yahoo.com.br * applies an XOR to the MSB and LSB, shifts all bits one bit to the right, 9113219Sodanrc@yahoo.com.br * and set the result of the XOR as the new MSB. 9213219Sodanrc@yahoo.com.br * 9313219Sodanrc@yahoo.com.br * This function is not bijective if the address has only 1 bit, as the MSB 9413219Sodanrc@yahoo.com.br * and LSB will be the same, and therefore the xor will always be 0. 9513219Sodanrc@yahoo.com.br * 9613219Sodanrc@yahoo.com.br * @param addr The address to be hashed. 9713219Sodanrc@yahoo.com.br * @param The hashed address. 9813219Sodanrc@yahoo.com.br */ 9913219Sodanrc@yahoo.com.br Addr hash(const Addr addr) const; 10013219Sodanrc@yahoo.com.br 10113219Sodanrc@yahoo.com.br /** 10213219Sodanrc@yahoo.com.br * Inverse of the hash function. 10313219Sodanrc@yahoo.com.br * @sa hash(). 10413219Sodanrc@yahoo.com.br * 10513219Sodanrc@yahoo.com.br * @param addr The address to be dehashed. 10613219Sodanrc@yahoo.com.br * @param The dehashed address. 10713219Sodanrc@yahoo.com.br */ 10813219Sodanrc@yahoo.com.br Addr dehash(const Addr addr) const; 10913219Sodanrc@yahoo.com.br 11013219Sodanrc@yahoo.com.br /** 11113219Sodanrc@yahoo.com.br * Address skewing function selection. It selects and applies one of the 11213219Sodanrc@yahoo.com.br * skewing functions functions based on the way provided. 11313219Sodanrc@yahoo.com.br * 11413219Sodanrc@yahoo.com.br * @param addr Address to be skewed. Should contain the set and tag bits. 11513219Sodanrc@yahoo.com.br * @param way The cache way, used to select a hash function. 11613219Sodanrc@yahoo.com.br * @return The skewed address. 11713219Sodanrc@yahoo.com.br */ 11813219Sodanrc@yahoo.com.br Addr skew(const Addr addr, const uint32_t way) const; 11913219Sodanrc@yahoo.com.br 12013219Sodanrc@yahoo.com.br /** 12113219Sodanrc@yahoo.com.br * Address deskewing function (inverse of the skew function) of the given 12213219Sodanrc@yahoo.com.br * way. 12313219Sodanrc@yahoo.com.br * @sa skew() 12413219Sodanrc@yahoo.com.br * 12513219Sodanrc@yahoo.com.br * @param addr Address to be deskewed. Should contain the set and tag bits. 12613219Sodanrc@yahoo.com.br * @param way The cache way, used to select a hash function. 12713219Sodanrc@yahoo.com.br * @return The deskewed address. 12813219Sodanrc@yahoo.com.br */ 12913219Sodanrc@yahoo.com.br Addr deskew(const Addr addr, const uint32_t way) const; 13013219Sodanrc@yahoo.com.br 13113219Sodanrc@yahoo.com.br /** 13213219Sodanrc@yahoo.com.br * Apply a skewing function to calculate address' set given a way. 13313219Sodanrc@yahoo.com.br * 13413219Sodanrc@yahoo.com.br * @param addr The address to calculate the set for. 13513219Sodanrc@yahoo.com.br * @param way The way to get the set from. 13613219Sodanrc@yahoo.com.br * @return The set index for given combination of address and way. 13713219Sodanrc@yahoo.com.br */ 13813219Sodanrc@yahoo.com.br uint32_t extractSet(const Addr addr, const uint32_t way) const; 13913219Sodanrc@yahoo.com.br 14013219Sodanrc@yahoo.com.br public: 14113219Sodanrc@yahoo.com.br /** Convenience typedef. */ 14213219Sodanrc@yahoo.com.br typedef SkewedAssociativeParams Params; 14313219Sodanrc@yahoo.com.br 14413219Sodanrc@yahoo.com.br /** 14513219Sodanrc@yahoo.com.br * Construct and initialize this policy. 14613219Sodanrc@yahoo.com.br */ 14713219Sodanrc@yahoo.com.br SkewedAssociative(const Params *p); 14813219Sodanrc@yahoo.com.br 14913219Sodanrc@yahoo.com.br /** 15013219Sodanrc@yahoo.com.br * Destructor. 15113219Sodanrc@yahoo.com.br */ 15213219Sodanrc@yahoo.com.br ~SkewedAssociative() {}; 15313219Sodanrc@yahoo.com.br 15413219Sodanrc@yahoo.com.br /** 15513219Sodanrc@yahoo.com.br * Find all possible entries for insertion and replacement of an address. 15613219Sodanrc@yahoo.com.br * Should be called immediately before ReplacementPolicy's findVictim() 15713219Sodanrc@yahoo.com.br * not to break cache resizing. 15813219Sodanrc@yahoo.com.br * 15913219Sodanrc@yahoo.com.br * @param addr The addr to a find possible entries for. 16013219Sodanrc@yahoo.com.br * @return The possible entries. 16113219Sodanrc@yahoo.com.br */ 16213219Sodanrc@yahoo.com.br std::vector<ReplaceableEntry*> getPossibleEntries(const Addr addr) const 16313219Sodanrc@yahoo.com.br override; 16413219Sodanrc@yahoo.com.br 16513219Sodanrc@yahoo.com.br /** 16613219Sodanrc@yahoo.com.br * Regenerate an entry's address from its tag and assigned set and way. 16713219Sodanrc@yahoo.com.br * Uses the inverse of the skewing function. 16813219Sodanrc@yahoo.com.br * 16913219Sodanrc@yahoo.com.br * @param tag The tag bits. 17013219Sodanrc@yahoo.com.br * @param entry The entry. 17113219Sodanrc@yahoo.com.br * @return the entry's address. 17213219Sodanrc@yahoo.com.br */ 17313219Sodanrc@yahoo.com.br Addr regenerateAddr(const Addr tag, const ReplaceableEntry* entry) const 17413219Sodanrc@yahoo.com.br override; 17513219Sodanrc@yahoo.com.br}; 17613219Sodanrc@yahoo.com.br 17713219Sodanrc@yahoo.com.br#endif //__MEM_CACHE_INDEXING_POLICIES_SKEWED_ASSOCIATIVE_HH__ 178