brrip_rp.cc (12626:e161d7725d4b) brrip_rp.cc (12684:44ebd2bc020f)
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
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 <memory>
34
35#include "base/logging.hh" // For fatal_if
33#include "base/random.hh"
36#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{
37
38BRRIPRP::BRRIPRP(const Params *p)
39 : BaseReplacementPolicy(p),
40 maxRRPV(p->max_RRPV), hitPriority(p->hit_priority), btp(p->btp)
41{
40 if (maxRRPV == 0){
41 fatal("max_RRPV should be greater than zero.\n");
42 }
42 fatal_if(maxRRPV <= 0, "max_RRPV should be greater than zero.\n");
43}
44
45void
43}
44
45void
46BRRIPRP::touch(CacheBlk *blk)
46BRRIPRP::invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
47const
47{
48{
48 BaseReplacementPolicy::touch(blk);
49 std::shared_ptr<BRRIPReplData> casted_replacement_data =
50 std::static_pointer_cast<BRRIPReplData>(replacement_data);
49
51
52 // Set RRPV to an invalid distance
53 casted_replacement_data->rrpv = maxRRPV + 1;
54}
55
56void
57BRRIPRP::touch(const std::shared_ptr<ReplacementData>& replacement_data) const
58{
59 std::shared_ptr<BRRIPReplData> casted_replacement_data =
60 std::static_pointer_cast<BRRIPReplData>(replacement_data);
61
50 // Update RRPV if not 0 yet
62 // 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
63 // Every hit in HP mode makes the entry the last to be evicted, while
64 // in FP mode a hit makes the entry less likely to be evicted
53 if (hitPriority) {
65 if (hitPriority) {
54 blk->rrpv = 0;
55 } else if (blk->rrpv > 0) {
56 blk->rrpv--;
66 casted_replacement_data->rrpv = 0;
67 } else if (casted_replacement_data->rrpv > 0) {
68 casted_replacement_data->rrpv--;
57 }
58}
59
60void
69 }
70}
71
72void
61BRRIPRP::reset(CacheBlk *blk)
73BRRIPRP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const
62{
74{
63 BaseReplacementPolicy::reset(blk);
75 std::shared_ptr<BRRIPReplData> casted_replacement_data =
76 std::static_pointer_cast<BRRIPReplData>(replacement_data);
64
65 // Reset RRPV
77
78 // Reset RRPV
66 // Blocks are inserted as "long re-reference" if lower than btp,
79 // Replacement data is inserted as "long re-reference" if lower than btp,
67 // "distant re-reference" otherwise
68 if (random_mt.random<unsigned>(1, 100) <= btp) {
80 // "distant re-reference" otherwise
81 if (random_mt.random<unsigned>(1, 100) <= btp) {
69 blk->rrpv = maxRRPV-1;
82 casted_replacement_data->rrpv = maxRRPV-1;
70 } else {
83 } else {
71 blk->rrpv = maxRRPV;
84 casted_replacement_data->rrpv = maxRRPV;
72 }
73}
74
85 }
86}
87
75CacheBlk*
76BRRIPRP::getVictim(const ReplacementCandidates& candidates)
88ReplaceableEntry*
89BRRIPRP::getVictim(const ReplacementCandidates& candidates) const
77{
78 // There must be at least one replacement candidate
79 assert(candidates.size() > 0);
80
90{
91 // There must be at least one replacement candidate
92 assert(candidates.size() > 0);
93
81 // Use visitor to search for the victim
82 CacheBlk* blk = candidates[0];
94 // Use first candidate as dummy victim
95 ReplaceableEntry* victim = candidates[0];
96
97 // Store victim->rrpv in a variable to improve code readability
98 int victim_RRPV = std::static_pointer_cast<BRRIPReplData>(
99 victim->replacementData)->rrpv;
100
101 // Visit all candidates to find victim
83 for (const auto& candidate : candidates) {
102 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;
103 // Get candidate's rrpv
104 int candidate_RRPV = std::static_pointer_cast<BRRIPReplData>(
105 candidate->replacementData)->rrpv;
106
107 // Stop searching for victims if an invalid entry is found
108 if (candidate_RRPV == maxRRPV + 1) {
109 return candidate;
110 // Update victim entry if necessary
111 } else if (candidate_RRPV > victim_RRPV) {
112 victim = candidate;
113 victim_RRPV = candidate_RRPV;
92 }
93 }
94
114 }
115 }
116
95 // Make sure we don't have an invalid rrpv
96 assert(blk->rrpv <= maxRRPV);
117 // Get difference of victim's RRPV to the highest possible RRPV in
118 // order to update the RRPV of all the other entries accordingly
119 int diff = maxRRPV - victim_RRPV;
97
120
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) {
121 // No need to update RRPV if there is no difference
122 if (diff > 0){
123 // Update RRPV of all candidates
124 for (const auto& candidate : candidates) {
106 // Update the block's RPPV with the new value
107 candidate->rrpv += diff;
125 std::static_pointer_cast<BRRIPReplData>(
126 candidate->replacementData)->rrpv += diff;
108 }
109 }
110
127 }
128 }
129
111 DPRINTF(CacheRepl, "set %x, way %x: selecting blk for replacement\n",
112 blk->set, blk->way);
130 return victim;
131}
113
132
114 return blk;
133std::shared_ptr<ReplacementData>
134BRRIPRP::instantiateEntry()
135{
136 return std::shared_ptr<ReplacementData>(new BRRIPReplData(maxRRPV));
115}
116
117BRRIPRP*
118BRRIPRPParams::create()
119{
120 return new BRRIPRP(this);
121}
137}
138
139BRRIPRP*
140BRRIPRPParams::create()
141{
142 return new BRRIPRP(this);
143}