brrip_rp.cc revision 12626:e161d7725d4b
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#include "mem/cache/replacement_policies/brrip_rp.hh" 32 33#include "base/random.hh" 34#include "debug/CacheRepl.hh" 35 36BRRIPRP::BRRIPRP(const Params *p) 37 : BaseReplacementPolicy(p), 38 maxRRPV(p->max_RRPV), hitPriority(p->hit_priority), btp(p->btp) 39{ 40 if (maxRRPV == 0){ 41 fatal("max_RRPV should be greater than zero.\n"); 42 } 43} 44 45void 46BRRIPRP::touch(CacheBlk *blk) 47{ 48 BaseReplacementPolicy::touch(blk); 49 50 // Update RRPV if not 0 yet 51 // Every hit in HP mode makes the block the last to be evicted, while 52 // in FP mode a hit makes the block less likely to be evicted 53 if (hitPriority) { 54 blk->rrpv = 0; 55 } else if (blk->rrpv > 0) { 56 blk->rrpv--; 57 } 58} 59 60void 61BRRIPRP::reset(CacheBlk *blk) 62{ 63 BaseReplacementPolicy::reset(blk); 64 65 // Reset RRPV 66 // Blocks are inserted as "long re-reference" if lower than btp, 67 // "distant re-reference" otherwise 68 if (random_mt.random<unsigned>(1, 100) <= btp) { 69 blk->rrpv = maxRRPV-1; 70 } else { 71 blk->rrpv = maxRRPV; 72 } 73} 74 75CacheBlk* 76BRRIPRP::getVictim(const ReplacementCandidates& candidates) 77{ 78 // There must be at least one replacement candidate 79 assert(candidates.size() > 0); 80 81 // Use visitor to search for the victim 82 CacheBlk* blk = candidates[0]; 83 for (const auto& candidate : candidates) { 84 // Stop iteration if found an invalid block 85 if (!candidate->isValid()) { 86 blk = candidate; 87 blk->rrpv = maxRRPV; 88 break; 89 // Update victim block if necessary 90 } else if (candidate->rrpv > blk->rrpv) { 91 blk = candidate; 92 } 93 } 94 95 // Make sure we don't have an invalid rrpv 96 assert(blk->rrpv <= maxRRPV); 97 98 // Get difference of block's RRPV to the highest possible RRPV in 99 // order to update the RRPV of all the other blocks accordingly 100 unsigned diff = maxRRPV - blk->rrpv; 101 102 // No need to update RRPV if there is no difference 103 if (diff > 0){ 104 // Update RRPV of all candidates 105 for (const auto& candidate : candidates) { 106 // Update the block's RPPV with the new value 107 candidate->rrpv += diff; 108 } 109 } 110 111 DPRINTF(CacheRepl, "set %x, way %x: selecting blk for replacement\n", 112 blk->set, blk->way); 113 114 return blk; 115} 116 117BRRIPRP* 118BRRIPRPParams::create() 119{ 120 return new BRRIPRP(this); 121} 122