1/* 2 * Copyright (c) 2018 Inria 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer; 9 * redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution; 12 * neither the name of the copyright holders nor the names of its 13 * contributors may be used to endorse or promote products derived from 14 * this software without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 * 28 * Authors: Daniel Carvalho 29 */ 30 31/** 32 * @file 33 * Definitions of a skewed associative indexing policy. 34 */ 35 36#include "mem/cache/tags/indexing_policies/skewed_associative.hh" 37 38#include "base/bitfield.hh" 39#include "base/intmath.hh" 40#include "base/logging.hh" 41#include "mem/cache/replacement_policies/replaceable_entry.hh" 42 43SkewedAssociative::SkewedAssociative(const Params *p) 44 : BaseIndexingPolicy(p), msbShift(floorLog2(numSets) - 1) 45{ 46 if (assoc > NUM_SKEWING_FUNCTIONS) { 47 warn_once("Associativity higher than number of skewing functions. " \ 48 "Expect sub-optimal skewing.\n"); 49 } 50 51 // Check if set is too big to do skewing. If using big sets, rewrite 52 // skewing functions accordingly to make good use of the hashing function 53 panic_if(setShift + 2 * (msbShift + 1) > 64, "Unsuported number of bits " \ 54 "for the skewing functions."); 55 56 // We must have more than two sets, otherwise the MSB and LSB are the same 57 // bit, and the xor of them will always be 0 58 fatal_if(numSets <= 2, "The number of sets must be greater than 2"); 59} 60 61Addr 62SkewedAssociative::hash(const Addr addr) const 63{ 64 // Get relevant bits 65 const uint8_t lsb = bits<Addr>(addr, 0); 66 const uint8_t msb = bits<Addr>(addr, msbShift); 67 const uint8_t xor_bit = msb ^ lsb; 68 69 // Shift-off LSB and set new MSB as xor of old LSB and MSB 70 return insertBits<Addr, uint8_t>(addr >> 1, msbShift, xor_bit); 71} 72 73Addr 74SkewedAssociative::dehash(const Addr addr) const 75{ 76 // Get relevant bits. The original MSB is one bit away on the current MSB 77 // (which is the XOR bit). The original LSB can be retrieved from inverting 78 // the xor that generated the XOR bit. 79 const uint8_t msb = bits<Addr>(addr, msbShift - 1); 80 const uint8_t xor_bit = bits<Addr>(addr, msbShift); 81 const uint8_t lsb = msb ^ xor_bit; 82 83 // Remove current MSB (XOR bit), shift left and add LSB back 84 const Addr addr_no_msb = mbits<Addr>(addr, msbShift - 1, 0); 85 return insertBits<Addr, uint8_t>(addr_no_msb << 1, 0, lsb); 86} 87 88Addr 89SkewedAssociative::skew(const Addr addr, const uint32_t way) const 90{ 91 // Assume an address of size A bits can be decomposed into 92 // {addr3, addr2, addr1, addr0}, where: 93 // addr0 (M bits) = Block offset; 94 // addr1 (N bits) = Set bits in conventional cache; 95 // addr3 (A - M - 2*N bits), addr2 (N bits) = Tag bits. 96 // We use addr1 and addr2, as proposed in the original paper 97 Addr addr1 = bits<Addr>(addr, msbShift, 0); 98 const Addr addr2 = bits<Addr>(addr, 2 * (msbShift + 1) - 1, msbShift + 1); 99 100 // Select and apply skewing function for given way 101 switch (way % NUM_SKEWING_FUNCTIONS) { 102 case 0: 103 addr1 = hash(addr1) ^ hash(addr2) ^ addr2; 104 break; 105 case 1: 106 addr1 = hash(addr1) ^ hash(addr2) ^ addr1; 107 break; 108 case 2: 109 addr1 = hash(addr1) ^ dehash(addr2) ^ addr2; 110 break; 111 case 3: 112 addr1 = hash(addr1) ^ dehash(addr2) ^ addr1; 113 break; 114 case 4: 115 addr1 = dehash(addr1) ^ hash(addr2) ^ addr2; 116 break; 117 case 5: 118 addr1 = dehash(addr1) ^ hash(addr2) ^ addr1; 119 break; 120 case 6: 121 addr1 = dehash(addr1) ^ dehash(addr2) ^ addr2; 122 break; 123 case 7: 124 addr1 = dehash(addr1) ^ dehash(addr2) ^ addr1; 125 break; 126 default: 127 panic("A skewing function has not been implemented for this way."); 128 } 129 130 // If we have more than 8 ways, just pile them up on hashes. This is not 131 // the optimal solution, and can be improved by adding more skewing 132 // functions to the previous selector 133 for (uint32_t i = 0; i < way/NUM_SKEWING_FUNCTIONS; i++) { 134 addr1 = hash(addr1); 135 } 136 137 return addr1; 138} 139 140Addr 141SkewedAssociative::deskew(const Addr addr, const uint32_t way) const 142{ 143 // Get relevant bits of the addr 144 Addr addr1 = bits<Addr>(addr, msbShift, 0); 145 const Addr addr2 = bits<Addr>(addr, 2 * (msbShift + 1) - 1, msbShift + 1); 146 147 // If we have more than NUM_SKEWING_FUNCTIONS ways, unpile the hashes 148 if (way >= NUM_SKEWING_FUNCTIONS) { 149 for (uint32_t i = 0; i < way/NUM_SKEWING_FUNCTIONS; i++) { 150 addr1 = dehash(addr1); 151 } 152 } 153 154 // Select and apply skewing function for given way 155 switch (way % 8) { 156 case 0: 157 return dehash(addr1 ^ hash(addr2) ^ addr2); 158 case 1: 159 addr1 = addr1 ^ hash(addr2); 160 for (int i = 0; i < msbShift; i++) { 161 addr1 = hash(addr1); 162 } 163 return addr1; 164 case 2: 165 return dehash(addr1 ^ dehash(addr2) ^ addr2); 166 case 3: 167 addr1 = addr1 ^ dehash(addr2); 168 for (int i = 0; i < msbShift; i++) { 169 addr1 = hash(addr1); 170 } 171 return addr1; 172 case 4: 173 return hash(addr1 ^ hash(addr2) ^ addr2); 174 case 5: 175 addr1 = addr1 ^ hash(addr2); 176 for (int i = 0; i <= msbShift; i++) { 177 addr1 = hash(addr1); 178 } 179 return addr1; 180 case 6: 181 return hash(addr1 ^ dehash(addr2) ^ addr2); 182 case 7: 183 addr1 = addr1 ^ dehash(addr2); 184 for (int i = 0; i <= msbShift; i++) { 185 addr1 = hash(addr1); 186 } 187 return addr1; 188 default: 189 panic("A skewing function has not been implemented for this way."); 190 } 191} 192 193uint32_t 194SkewedAssociative::extractSet(const Addr addr, const uint32_t way) const 195{ 196 return skew(addr >> setShift, way) & setMask; 197} 198 199Addr 200SkewedAssociative::regenerateAddr(const Addr tag, 201 const ReplaceableEntry* entry) const 202{ 203 const Addr addr_set = (tag << (msbShift + 1)) | entry->getSet(); 204 return (tag << tagShift) | 205 ((deskew(addr_set, entry->getWay()) & setMask) << setShift); 206} 207 208std::vector<ReplaceableEntry*> 209SkewedAssociative::getPossibleEntries(const Addr addr) const 210{ 211 std::vector<ReplaceableEntry*> entries; 212 213 // Parse all ways 214 for (uint32_t way = 0; way < assoc; ++way) { 215 // Apply hash to get set, and get way entry in it 216 entries.push_back(sets[extractSet(addr, way)][way]); 217 } 218 219 return entries; 220} 221 222SkewedAssociative * 223SkewedAssociativeParams::create() 224{ 225 return new SkewedAssociative(this); 226} 227