skewed_associative.cc revision 13225
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 * Definitions of a skewed associative indexing policy. 3413219Sodanrc@yahoo.com.br */ 3513219Sodanrc@yahoo.com.br 3613219Sodanrc@yahoo.com.br#include "mem/cache/tags/indexing_policies/skewed_associative.hh" 3713219Sodanrc@yahoo.com.br 3813219Sodanrc@yahoo.com.br#include "base/bitfield.hh" 3913219Sodanrc@yahoo.com.br#include "base/intmath.hh" 4013219Sodanrc@yahoo.com.br#include "base/logging.hh" 4113225Sodanrc@yahoo.com.br#include "mem/cache/replacement_policies/replaceable_entry.hh" 4213219Sodanrc@yahoo.com.br 4313219Sodanrc@yahoo.com.brSkewedAssociative::SkewedAssociative(const Params *p) 4413219Sodanrc@yahoo.com.br : BaseIndexingPolicy(p), msbShift(floorLog2(numSets) - 1) 4513219Sodanrc@yahoo.com.br{ 4613219Sodanrc@yahoo.com.br if (assoc > NUM_SKEWING_FUNCTIONS) { 4713219Sodanrc@yahoo.com.br warn_once("Associativity higher than number of skewing functions. " \ 4813219Sodanrc@yahoo.com.br "Expect sub-optimal skewing.\n"); 4913219Sodanrc@yahoo.com.br } 5013219Sodanrc@yahoo.com.br 5113219Sodanrc@yahoo.com.br // Check if set is too big to do skewing. If using big sets, rewrite 5213219Sodanrc@yahoo.com.br // skewing functions accordingly to make good use of the hashing function 5313219Sodanrc@yahoo.com.br panic_if(setShift + 2 * (msbShift + 1) > 64, "Unsuported number of bits " \ 5413219Sodanrc@yahoo.com.br "for the skewing functions."); 5513219Sodanrc@yahoo.com.br 5613219Sodanrc@yahoo.com.br // We must have more than two sets, otherwise the MSB and LSB are the same 5713219Sodanrc@yahoo.com.br // bit, and the xor of them will always be 0 5813219Sodanrc@yahoo.com.br fatal_if(numSets <= 2, "The number of sets must be greater than 2"); 5913219Sodanrc@yahoo.com.br} 6013219Sodanrc@yahoo.com.br 6113219Sodanrc@yahoo.com.brAddr 6213219Sodanrc@yahoo.com.brSkewedAssociative::hash(const Addr addr) const 6313219Sodanrc@yahoo.com.br{ 6413219Sodanrc@yahoo.com.br // Get relevant bits 6513219Sodanrc@yahoo.com.br const uint8_t lsb = bits<Addr>(addr, 0); 6613219Sodanrc@yahoo.com.br const uint8_t msb = bits<Addr>(addr, msbShift); 6713219Sodanrc@yahoo.com.br const uint8_t xor_bit = msb ^ lsb; 6813219Sodanrc@yahoo.com.br 6913219Sodanrc@yahoo.com.br // Shift-off LSB and set new MSB as xor of old LSB and MSB 7013219Sodanrc@yahoo.com.br return insertBits<Addr, uint8_t>(addr >> 1, msbShift, xor_bit); 7113219Sodanrc@yahoo.com.br} 7213219Sodanrc@yahoo.com.br 7313219Sodanrc@yahoo.com.brAddr 7413219Sodanrc@yahoo.com.brSkewedAssociative::dehash(const Addr addr) const 7513219Sodanrc@yahoo.com.br{ 7613219Sodanrc@yahoo.com.br // Get relevant bits. The original MSB is one bit away on the current MSB 7713219Sodanrc@yahoo.com.br // (which is the XOR bit). The original LSB can be retrieved from inverting 7813219Sodanrc@yahoo.com.br // the xor that generated the XOR bit. 7913219Sodanrc@yahoo.com.br const uint8_t msb = bits<Addr>(addr, msbShift - 1); 8013219Sodanrc@yahoo.com.br const uint8_t xor_bit = bits<Addr>(addr, msbShift); 8113219Sodanrc@yahoo.com.br const uint8_t lsb = msb ^ xor_bit; 8213219Sodanrc@yahoo.com.br 8313219Sodanrc@yahoo.com.br // Remove current MSB (XOR bit), shift left and add LSB back 8413219Sodanrc@yahoo.com.br const Addr addr_no_msb = mbits<Addr>(addr, msbShift - 1, 0); 8513219Sodanrc@yahoo.com.br return insertBits<Addr, uint8_t>(addr_no_msb << 1, 0, lsb); 8613219Sodanrc@yahoo.com.br} 8713219Sodanrc@yahoo.com.br 8813219Sodanrc@yahoo.com.brAddr 8913219Sodanrc@yahoo.com.brSkewedAssociative::skew(const Addr addr, const uint32_t way) const 9013219Sodanrc@yahoo.com.br{ 9113219Sodanrc@yahoo.com.br // Assume an address of size A bits can be decomposed into 9213219Sodanrc@yahoo.com.br // {addr3, addr2, addr1, addr0}, where: 9313219Sodanrc@yahoo.com.br // addr0 (M bits) = Block offset; 9413219Sodanrc@yahoo.com.br // addr1 (N bits) = Set bits in conventional cache; 9513219Sodanrc@yahoo.com.br // addr3 (A - M - 2*N bits), addr2 (N bits) = Tag bits. 9613219Sodanrc@yahoo.com.br // We use addr1 and addr2, as proposed in the original paper 9713219Sodanrc@yahoo.com.br Addr addr1 = bits<Addr>(addr, msbShift, 0); 9813219Sodanrc@yahoo.com.br const Addr addr2 = bits<Addr>(addr, 2 * (msbShift + 1) - 1, msbShift + 1); 9913219Sodanrc@yahoo.com.br 10013219Sodanrc@yahoo.com.br // Select and apply skewing function for given way 10113219Sodanrc@yahoo.com.br switch (way % NUM_SKEWING_FUNCTIONS) { 10213219Sodanrc@yahoo.com.br case 0: 10313219Sodanrc@yahoo.com.br addr1 = hash(addr1) ^ hash(addr2) ^ addr2; 10413219Sodanrc@yahoo.com.br break; 10513219Sodanrc@yahoo.com.br case 1: 10613219Sodanrc@yahoo.com.br addr1 = hash(addr1) ^ hash(addr2) ^ addr1; 10713219Sodanrc@yahoo.com.br break; 10813219Sodanrc@yahoo.com.br case 2: 10913219Sodanrc@yahoo.com.br addr1 = hash(addr1) ^ dehash(addr2) ^ addr2; 11013219Sodanrc@yahoo.com.br break; 11113219Sodanrc@yahoo.com.br case 3: 11213219Sodanrc@yahoo.com.br addr1 = hash(addr1) ^ dehash(addr2) ^ addr1; 11313219Sodanrc@yahoo.com.br break; 11413219Sodanrc@yahoo.com.br case 4: 11513219Sodanrc@yahoo.com.br addr1 = dehash(addr1) ^ hash(addr2) ^ addr2; 11613219Sodanrc@yahoo.com.br break; 11713219Sodanrc@yahoo.com.br case 5: 11813219Sodanrc@yahoo.com.br addr1 = dehash(addr1) ^ hash(addr2) ^ addr1; 11913219Sodanrc@yahoo.com.br break; 12013219Sodanrc@yahoo.com.br case 6: 12113219Sodanrc@yahoo.com.br addr1 = dehash(addr1) ^ dehash(addr2) ^ addr2; 12213219Sodanrc@yahoo.com.br break; 12313219Sodanrc@yahoo.com.br case 7: 12413219Sodanrc@yahoo.com.br addr1 = dehash(addr1) ^ dehash(addr2) ^ addr1; 12513219Sodanrc@yahoo.com.br break; 12613219Sodanrc@yahoo.com.br default: 12713219Sodanrc@yahoo.com.br panic("A skewing function has not been implemented for this way."); 12813219Sodanrc@yahoo.com.br } 12913219Sodanrc@yahoo.com.br 13013219Sodanrc@yahoo.com.br // If we have more than 8 ways, just pile them up on hashes. This is not 13113219Sodanrc@yahoo.com.br // the optimal solution, and can be improved by adding more skewing 13213219Sodanrc@yahoo.com.br // functions to the previous selector 13313219Sodanrc@yahoo.com.br for (uint32_t i = 0; i < way/NUM_SKEWING_FUNCTIONS; i++) { 13413219Sodanrc@yahoo.com.br addr1 = hash(addr1); 13513219Sodanrc@yahoo.com.br } 13613219Sodanrc@yahoo.com.br 13713219Sodanrc@yahoo.com.br return addr1; 13813219Sodanrc@yahoo.com.br} 13913219Sodanrc@yahoo.com.br 14013219Sodanrc@yahoo.com.brAddr 14113219Sodanrc@yahoo.com.brSkewedAssociative::deskew(const Addr addr, const uint32_t way) const 14213219Sodanrc@yahoo.com.br{ 14313219Sodanrc@yahoo.com.br // Get relevant bits of the addr 14413219Sodanrc@yahoo.com.br Addr addr1 = bits<Addr>(addr, msbShift, 0); 14513219Sodanrc@yahoo.com.br const Addr addr2 = bits<Addr>(addr, 2 * (msbShift + 1) - 1, msbShift + 1); 14613219Sodanrc@yahoo.com.br 14713219Sodanrc@yahoo.com.br // If we have more than NUM_SKEWING_FUNCTIONS ways, unpile the hashes 14813219Sodanrc@yahoo.com.br if (way >= NUM_SKEWING_FUNCTIONS) { 14913219Sodanrc@yahoo.com.br for (uint32_t i = 0; i < way/NUM_SKEWING_FUNCTIONS; i++) { 15013219Sodanrc@yahoo.com.br addr1 = dehash(addr1); 15113219Sodanrc@yahoo.com.br } 15213219Sodanrc@yahoo.com.br } 15313219Sodanrc@yahoo.com.br 15413219Sodanrc@yahoo.com.br // Select and apply skewing function for given way 15513219Sodanrc@yahoo.com.br switch (way % 8) { 15613219Sodanrc@yahoo.com.br case 0: 15713219Sodanrc@yahoo.com.br return dehash(addr1 ^ hash(addr2) ^ addr2); 15813219Sodanrc@yahoo.com.br case 1: 15913219Sodanrc@yahoo.com.br addr1 = addr1 ^ hash(addr2); 16013219Sodanrc@yahoo.com.br for (int i = 0; i < msbShift; i++) { 16113219Sodanrc@yahoo.com.br addr1 = hash(addr1); 16213219Sodanrc@yahoo.com.br } 16313219Sodanrc@yahoo.com.br return addr1; 16413219Sodanrc@yahoo.com.br case 2: 16513219Sodanrc@yahoo.com.br return dehash(addr1 ^ dehash(addr2) ^ addr2); 16613219Sodanrc@yahoo.com.br case 3: 16713219Sodanrc@yahoo.com.br addr1 = addr1 ^ dehash(addr2); 16813219Sodanrc@yahoo.com.br for (int i = 0; i < msbShift; i++) { 16913219Sodanrc@yahoo.com.br addr1 = hash(addr1); 17013219Sodanrc@yahoo.com.br } 17113219Sodanrc@yahoo.com.br return addr1; 17213219Sodanrc@yahoo.com.br case 4: 17313219Sodanrc@yahoo.com.br return hash(addr1 ^ hash(addr2) ^ addr2); 17413219Sodanrc@yahoo.com.br case 5: 17513219Sodanrc@yahoo.com.br addr1 = addr1 ^ hash(addr2); 17613219Sodanrc@yahoo.com.br for (int i = 0; i <= msbShift; i++) { 17713219Sodanrc@yahoo.com.br addr1 = hash(addr1); 17813219Sodanrc@yahoo.com.br } 17913219Sodanrc@yahoo.com.br return addr1; 18013219Sodanrc@yahoo.com.br case 6: 18113219Sodanrc@yahoo.com.br return hash(addr1 ^ dehash(addr2) ^ addr2); 18213219Sodanrc@yahoo.com.br case 7: 18313219Sodanrc@yahoo.com.br addr1 = addr1 ^ dehash(addr2); 18413219Sodanrc@yahoo.com.br for (int i = 0; i <= msbShift; i++) { 18513219Sodanrc@yahoo.com.br addr1 = hash(addr1); 18613219Sodanrc@yahoo.com.br } 18713219Sodanrc@yahoo.com.br return addr1; 18813219Sodanrc@yahoo.com.br default: 18913219Sodanrc@yahoo.com.br panic("A skewing function has not been implemented for this way."); 19013219Sodanrc@yahoo.com.br } 19113219Sodanrc@yahoo.com.br} 19213219Sodanrc@yahoo.com.br 19313219Sodanrc@yahoo.com.bruint32_t 19413219Sodanrc@yahoo.com.brSkewedAssociative::extractSet(const Addr addr, const uint32_t way) const 19513219Sodanrc@yahoo.com.br{ 19613219Sodanrc@yahoo.com.br return skew(addr >> setShift, way) & setMask; 19713219Sodanrc@yahoo.com.br} 19813219Sodanrc@yahoo.com.br 19913219Sodanrc@yahoo.com.brAddr 20013219Sodanrc@yahoo.com.brSkewedAssociative::regenerateAddr(const Addr tag, 20113219Sodanrc@yahoo.com.br const ReplaceableEntry* entry) const 20213219Sodanrc@yahoo.com.br{ 20313219Sodanrc@yahoo.com.br const Addr addr_set = (tag << (msbShift + 1)) | entry->getSet(); 20413219Sodanrc@yahoo.com.br return (tag << tagShift) | 20513219Sodanrc@yahoo.com.br ((deskew(addr_set, entry->getWay()) & setMask) << setShift); 20613219Sodanrc@yahoo.com.br} 20713219Sodanrc@yahoo.com.br 20813219Sodanrc@yahoo.com.brstd::vector<ReplaceableEntry*> 20913219Sodanrc@yahoo.com.brSkewedAssociative::getPossibleEntries(const Addr addr) const 21013219Sodanrc@yahoo.com.br{ 21113219Sodanrc@yahoo.com.br std::vector<ReplaceableEntry*> entries; 21213219Sodanrc@yahoo.com.br 21313219Sodanrc@yahoo.com.br // Parse all ways 21413219Sodanrc@yahoo.com.br for (uint32_t way = 0; way < assoc; ++way) { 21513219Sodanrc@yahoo.com.br // Apply hash to get set, and get way entry in it 21613219Sodanrc@yahoo.com.br entries.push_back(sets[extractSet(addr, way)][way]); 21713219Sodanrc@yahoo.com.br } 21813219Sodanrc@yahoo.com.br 21913219Sodanrc@yahoo.com.br return entries; 22013219Sodanrc@yahoo.com.br} 22113219Sodanrc@yahoo.com.br 22213219Sodanrc@yahoo.com.brSkewedAssociative * 22313219Sodanrc@yahoo.com.brSkewedAssociativeParams::create() 22413219Sodanrc@yahoo.com.br{ 22513219Sodanrc@yahoo.com.br return new SkewedAssociative(this); 22613219Sodanrc@yahoo.com.br} 227