brrip_rp.cc revision 12626
112626Sodanrc@yahoo.com.br/** 212626Sodanrc@yahoo.com.br * Copyright (c) 2018 Inria 312626Sodanrc@yahoo.com.br * All rights reserved. 412626Sodanrc@yahoo.com.br * 512626Sodanrc@yahoo.com.br * Redistribution and use in source and binary forms, with or without 612626Sodanrc@yahoo.com.br * modification, are permitted provided that the following conditions are 712626Sodanrc@yahoo.com.br * met: redistributions of source code must retain the above copyright 812626Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer; 912626Sodanrc@yahoo.com.br * redistributions in binary form must reproduce the above copyright 1012626Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer in the 1112626Sodanrc@yahoo.com.br * documentation and/or other materials provided with the distribution; 1212626Sodanrc@yahoo.com.br * neither the name of the copyright holders nor the names of its 1312626Sodanrc@yahoo.com.br * contributors may be used to endorse or promote products derived from 1412626Sodanrc@yahoo.com.br * this software without specific prior written permission. 1512626Sodanrc@yahoo.com.br * 1612626Sodanrc@yahoo.com.br * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1712626Sodanrc@yahoo.com.br * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1812626Sodanrc@yahoo.com.br * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1912626Sodanrc@yahoo.com.br * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2012626Sodanrc@yahoo.com.br * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2112626Sodanrc@yahoo.com.br * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2212626Sodanrc@yahoo.com.br * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2312626Sodanrc@yahoo.com.br * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2412626Sodanrc@yahoo.com.br * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2512626Sodanrc@yahoo.com.br * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2612626Sodanrc@yahoo.com.br * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2712626Sodanrc@yahoo.com.br * 2812626Sodanrc@yahoo.com.br * Authors: Daniel Carvalho 2912626Sodanrc@yahoo.com.br */ 3012626Sodanrc@yahoo.com.br 3112626Sodanrc@yahoo.com.br#include "mem/cache/replacement_policies/brrip_rp.hh" 3212626Sodanrc@yahoo.com.br 3312626Sodanrc@yahoo.com.br#include "base/random.hh" 3412626Sodanrc@yahoo.com.br#include "debug/CacheRepl.hh" 3512626Sodanrc@yahoo.com.br 3612626Sodanrc@yahoo.com.brBRRIPRP::BRRIPRP(const Params *p) 3712626Sodanrc@yahoo.com.br : BaseReplacementPolicy(p), 3812626Sodanrc@yahoo.com.br maxRRPV(p->max_RRPV), hitPriority(p->hit_priority), btp(p->btp) 3912626Sodanrc@yahoo.com.br{ 4012626Sodanrc@yahoo.com.br if (maxRRPV == 0){ 4112626Sodanrc@yahoo.com.br fatal("max_RRPV should be greater than zero.\n"); 4212626Sodanrc@yahoo.com.br } 4312626Sodanrc@yahoo.com.br} 4412626Sodanrc@yahoo.com.br 4512626Sodanrc@yahoo.com.brvoid 4612626Sodanrc@yahoo.com.brBRRIPRP::touch(CacheBlk *blk) 4712626Sodanrc@yahoo.com.br{ 4812626Sodanrc@yahoo.com.br BaseReplacementPolicy::touch(blk); 4912626Sodanrc@yahoo.com.br 5012626Sodanrc@yahoo.com.br // Update RRPV if not 0 yet 5112626Sodanrc@yahoo.com.br // Every hit in HP mode makes the block the last to be evicted, while 5212626Sodanrc@yahoo.com.br // in FP mode a hit makes the block less likely to be evicted 5312626Sodanrc@yahoo.com.br if (hitPriority) { 5412626Sodanrc@yahoo.com.br blk->rrpv = 0; 5512626Sodanrc@yahoo.com.br } else if (blk->rrpv > 0) { 5612626Sodanrc@yahoo.com.br blk->rrpv--; 5712626Sodanrc@yahoo.com.br } 5812626Sodanrc@yahoo.com.br} 5912626Sodanrc@yahoo.com.br 6012626Sodanrc@yahoo.com.brvoid 6112626Sodanrc@yahoo.com.brBRRIPRP::reset(CacheBlk *blk) 6212626Sodanrc@yahoo.com.br{ 6312626Sodanrc@yahoo.com.br BaseReplacementPolicy::reset(blk); 6412626Sodanrc@yahoo.com.br 6512626Sodanrc@yahoo.com.br // Reset RRPV 6612626Sodanrc@yahoo.com.br // Blocks are inserted as "long re-reference" if lower than btp, 6712626Sodanrc@yahoo.com.br // "distant re-reference" otherwise 6812626Sodanrc@yahoo.com.br if (random_mt.random<unsigned>(1, 100) <= btp) { 6912626Sodanrc@yahoo.com.br blk->rrpv = maxRRPV-1; 7012626Sodanrc@yahoo.com.br } else { 7112626Sodanrc@yahoo.com.br blk->rrpv = maxRRPV; 7212626Sodanrc@yahoo.com.br } 7312626Sodanrc@yahoo.com.br} 7412626Sodanrc@yahoo.com.br 7512626Sodanrc@yahoo.com.brCacheBlk* 7612626Sodanrc@yahoo.com.brBRRIPRP::getVictim(const ReplacementCandidates& candidates) 7712626Sodanrc@yahoo.com.br{ 7812626Sodanrc@yahoo.com.br // There must be at least one replacement candidate 7912626Sodanrc@yahoo.com.br assert(candidates.size() > 0); 8012626Sodanrc@yahoo.com.br 8112626Sodanrc@yahoo.com.br // Use visitor to search for the victim 8212626Sodanrc@yahoo.com.br CacheBlk* blk = candidates[0]; 8312626Sodanrc@yahoo.com.br for (const auto& candidate : candidates) { 8412626Sodanrc@yahoo.com.br // Stop iteration if found an invalid block 8512626Sodanrc@yahoo.com.br if (!candidate->isValid()) { 8612626Sodanrc@yahoo.com.br blk = candidate; 8712626Sodanrc@yahoo.com.br blk->rrpv = maxRRPV; 8812626Sodanrc@yahoo.com.br break; 8912626Sodanrc@yahoo.com.br // Update victim block if necessary 9012626Sodanrc@yahoo.com.br } else if (candidate->rrpv > blk->rrpv) { 9112626Sodanrc@yahoo.com.br blk = candidate; 9212626Sodanrc@yahoo.com.br } 9312626Sodanrc@yahoo.com.br } 9412626Sodanrc@yahoo.com.br 9512626Sodanrc@yahoo.com.br // Make sure we don't have an invalid rrpv 9612626Sodanrc@yahoo.com.br assert(blk->rrpv <= maxRRPV); 9712626Sodanrc@yahoo.com.br 9812626Sodanrc@yahoo.com.br // Get difference of block's RRPV to the highest possible RRPV in 9912626Sodanrc@yahoo.com.br // order to update the RRPV of all the other blocks accordingly 10012626Sodanrc@yahoo.com.br unsigned diff = maxRRPV - blk->rrpv; 10112626Sodanrc@yahoo.com.br 10212626Sodanrc@yahoo.com.br // No need to update RRPV if there is no difference 10312626Sodanrc@yahoo.com.br if (diff > 0){ 10412626Sodanrc@yahoo.com.br // Update RRPV of all candidates 10512626Sodanrc@yahoo.com.br for (const auto& candidate : candidates) { 10612626Sodanrc@yahoo.com.br // Update the block's RPPV with the new value 10712626Sodanrc@yahoo.com.br candidate->rrpv += diff; 10812626Sodanrc@yahoo.com.br } 10912626Sodanrc@yahoo.com.br } 11012626Sodanrc@yahoo.com.br 11112626Sodanrc@yahoo.com.br DPRINTF(CacheRepl, "set %x, way %x: selecting blk for replacement\n", 11212626Sodanrc@yahoo.com.br blk->set, blk->way); 11312626Sodanrc@yahoo.com.br 11412626Sodanrc@yahoo.com.br return blk; 11512626Sodanrc@yahoo.com.br} 11612626Sodanrc@yahoo.com.br 11712626Sodanrc@yahoo.com.brBRRIPRP* 11812626Sodanrc@yahoo.com.brBRRIPRPParams::create() 11912626Sodanrc@yahoo.com.br{ 12012626Sodanrc@yahoo.com.br return new BRRIPRP(this); 12112626Sodanrc@yahoo.com.br} 122