brrip_rp.cc revision 12727
112953Sgabeblack@google.com/** 212953Sgabeblack@google.com * Copyright (c) 2018 Inria 312953Sgabeblack@google.com * All rights reserved. 412953Sgabeblack@google.com * 512953Sgabeblack@google.com * Redistribution and use in source and binary forms, with or without 612953Sgabeblack@google.com * modification, are permitted provided that the following conditions are 712953Sgabeblack@google.com * met: redistributions of source code must retain the above copyright 812953Sgabeblack@google.com * notice, this list of conditions and the following disclaimer; 912953Sgabeblack@google.com * redistributions in binary form must reproduce the above copyright 1012953Sgabeblack@google.com * notice, this list of conditions and the following disclaimer in the 1112953Sgabeblack@google.com * documentation and/or other materials provided with the distribution; 1212953Sgabeblack@google.com * neither the name of the copyright holders nor the names of its 1312953Sgabeblack@google.com * contributors may be used to endorse or promote products derived from 1412953Sgabeblack@google.com * this software without specific prior written permission. 1512953Sgabeblack@google.com * 1612953Sgabeblack@google.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1712953Sgabeblack@google.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1812953Sgabeblack@google.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1912953Sgabeblack@google.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2012953Sgabeblack@google.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2112953Sgabeblack@google.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2212953Sgabeblack@google.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2312953Sgabeblack@google.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2412953Sgabeblack@google.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2512953Sgabeblack@google.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2612953Sgabeblack@google.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2712953Sgabeblack@google.com * 2812953Sgabeblack@google.com * Authors: Daniel Carvalho 2912953Sgabeblack@google.com */ 3012953Sgabeblack@google.com 3112953Sgabeblack@google.com#include "mem/cache/replacement_policies/brrip_rp.hh" 3212953Sgabeblack@google.com 3312954Sgabeblack@google.com#include <cassert> 3412954Sgabeblack@google.com#include <memory> 3512982Sgabeblack@google.com 3612982Sgabeblack@google.com#include "base/logging.hh" // For fatal_if 3713182Sgabeblack@google.com#include "base/random.hh" 3813182Sgabeblack@google.com#include "params/BRRIPRP.hh" 3913245Sgabeblack@google.com 4012953Sgabeblack@google.comBRRIPRP::BRRIPRP(const Params *p) 4112953Sgabeblack@google.com : BaseReplacementPolicy(p), 4212953Sgabeblack@google.com maxRRPV(p->max_RRPV), hitPriority(p->hit_priority), btp(p->btp) 4312953Sgabeblack@google.com{ 4412954Sgabeblack@google.com fatal_if(maxRRPV <= 0, "max_RRPV should be greater than zero.\n"); 4512962Sgabeblack@google.com} 4612961Sgabeblack@google.com 4712961Sgabeblack@google.comvoid 4813182Sgabeblack@google.comBRRIPRP::invalidate(const std::shared_ptr<ReplacementData>& replacement_data) 4912987Sgabeblack@google.comconst 5013203Sgabeblack@google.com{ 5113203Sgabeblack@google.com std::shared_ptr<BRRIPReplData> casted_replacement_data = 5213245Sgabeblack@google.com std::static_pointer_cast<BRRIPReplData>(replacement_data); 5313245Sgabeblack@google.com 5412954Sgabeblack@google.com // Set RRPV to an invalid distance 5512953Sgabeblack@google.com casted_replacement_data->rrpv = maxRRPV + 1; 5613072Sgabeblack@google.com} 5713072Sgabeblack@google.com 5813072Sgabeblack@google.comvoid 5913072Sgabeblack@google.comBRRIPRP::touch(const std::shared_ptr<ReplacementData>& replacement_data) const 6013076Sgabeblack@google.com{ 6113076Sgabeblack@google.com std::shared_ptr<BRRIPReplData> casted_replacement_data = 6213072Sgabeblack@google.com std::static_pointer_cast<BRRIPReplData>(replacement_data); 6313076Sgabeblack@google.com 6413076Sgabeblack@google.com // Update RRPV if not 0 yet 6513076Sgabeblack@google.com // Every hit in HP mode makes the entry the last to be evicted, while 6613072Sgabeblack@google.com // in FP mode a hit makes the entry less likely to be evicted 6713144Sgabeblack@google.com if (hitPriority) { 6813144Sgabeblack@google.com casted_replacement_data->rrpv = 0; 6913072Sgabeblack@google.com } else if (casted_replacement_data->rrpv > 0) { 7013072Sgabeblack@google.com casted_replacement_data->rrpv--; 7113076Sgabeblack@google.com } 7213076Sgabeblack@google.com} 7313144Sgabeblack@google.com 7413144Sgabeblack@google.comvoid 7513088Sgabeblack@google.comBRRIPRP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const 7613072Sgabeblack@google.com{ 7713076Sgabeblack@google.com std::shared_ptr<BRRIPReplData> casted_replacement_data = 7813072Sgabeblack@google.com std::static_pointer_cast<BRRIPReplData>(replacement_data); 7913072Sgabeblack@google.com 8013072Sgabeblack@google.com // Reset RRPV 8113088Sgabeblack@google.com // Replacement data is inserted as "long re-reference" if lower than btp, 8213072Sgabeblack@google.com // "distant re-reference" otherwise 8313088Sgabeblack@google.com if (random_mt.random<unsigned>(1, 100) <= btp) { 8413072Sgabeblack@google.com casted_replacement_data->rrpv = maxRRPV-1; 8513088Sgabeblack@google.com } else { 8613072Sgabeblack@google.com casted_replacement_data->rrpv = maxRRPV; 8713088Sgabeblack@google.com } 8813072Sgabeblack@google.com} 8913088Sgabeblack@google.com 9013245Sgabeblack@google.comReplaceableEntry* 9113245Sgabeblack@google.comBRRIPRP::getVictim(const ReplacementCandidates& candidates) const 9213072Sgabeblack@google.com{ 9313072Sgabeblack@google.com // There must be at least one replacement candidate 9413072Sgabeblack@google.com assert(candidates.size() > 0); 9513072Sgabeblack@google.com 9613176Sgabeblack@google.com // Use first candidate as dummy victim 9713176Sgabeblack@google.com ReplaceableEntry* victim = candidates[0]; 9813176Sgabeblack@google.com 9913072Sgabeblack@google.com // Store victim->rrpv in a variable to improve code readability 10013072Sgabeblack@google.com int victim_RRPV = std::static_pointer_cast<BRRIPReplData>( 10113072Sgabeblack@google.com victim->replacementData)->rrpv; 10213072Sgabeblack@google.com 10313072Sgabeblack@google.com // Visit all candidates to find victim 10413072Sgabeblack@google.com for (const auto& candidate : candidates) { 10513072Sgabeblack@google.com // Get candidate's rrpv 10612953Sgabeblack@google.com int candidate_RRPV = std::static_pointer_cast<BRRIPReplData>( 10713067Sgabeblack@google.com candidate->replacementData)->rrpv; 10812953Sgabeblack@google.com 10913194Sgabeblack@google.com // Stop searching for victims if an invalid entry is found 11012957Sgabeblack@google.com if (candidate_RRPV == maxRRPV + 1) { 11113180Sgabeblack@google.com return candidate; 11213194Sgabeblack@google.com // Update victim entry if necessary 11313194Sgabeblack@google.com } else if (candidate_RRPV > victim_RRPV) { 11413194Sgabeblack@google.com victim = candidate; 11513194Sgabeblack@google.com victim_RRPV = candidate_RRPV; 11613194Sgabeblack@google.com } 11713194Sgabeblack@google.com } 11813194Sgabeblack@google.com 11913194Sgabeblack@google.com // Get difference of victim's RRPV to the highest possible RRPV in 12013194Sgabeblack@google.com // order to update the RRPV of all the other entries accordingly 12113180Sgabeblack@google.com int diff = maxRRPV - victim_RRPV; 12212957Sgabeblack@google.com 12312957Sgabeblack@google.com // No need to update RRPV if there is no difference 12413186Sgabeblack@google.com if (diff > 0){ 12513186Sgabeblack@google.com // Update RRPV of all candidates 12613067Sgabeblack@google.com for (const auto& candidate : candidates) { 12712985Sgabeblack@google.com std::static_pointer_cast<BRRIPReplData>( 12812985Sgabeblack@google.com candidate->replacementData)->rrpv += diff; 12912985Sgabeblack@google.com } 13012985Sgabeblack@google.com } 13113068Sgabeblack@google.com 13213096Sgabeblack@google.com return victim; 13313068Sgabeblack@google.com} 13413069Sgabeblack@google.com 13513068Sgabeblack@google.comstd::shared_ptr<ReplacementData> 13612961Sgabeblack@google.comBRRIPRP::instantiateEntry() 13713067Sgabeblack@google.com{ 13813186Sgabeblack@google.com return std::shared_ptr<ReplacementData>(new BRRIPReplData(maxRRPV)); 13913186Sgabeblack@google.com} 14013245Sgabeblack@google.com 14113245Sgabeblack@google.comBRRIPRP* 14212957Sgabeblack@google.comBRRIPRPParams::create() 14312957Sgabeblack@google.com{ 14412957Sgabeblack@google.com return new BRRIPRP(this); 14512957Sgabeblack@google.com} 14612957Sgabeblack@google.com