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;

--- 16 unchanged lines hidden (view full) ---

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}