gem5  v20.1.0.0
tree_plru_rp.cc
Go to the documentation of this file.
1 
36 
37 #include <cmath>
38 
39 #include "base/intmath.hh"
40 #include "base/logging.hh"
41 #include "params/TreePLRURP.hh"
42 
49 static uint64_t
50 parentIndex(const uint64_t index)
51 {
52  return std::floor((index-1)/2);
53 }
54 
61 static uint64_t
62 leftSubtreeIndex(const uint64_t index)
63 {
64  return 2*index + 1;
65 }
66 
73 static uint64_t
74 rightSubtreeIndex(const uint64_t index)
75 {
76  return 2*index + 2;
77 }
78 
86 static bool
87 isRightSubtree(const uint64_t index)
88 {
89  return index%2 == 0;
90 }
91 
93  const uint64_t index, std::shared_ptr<PLRUTree> tree)
94  : index(index), tree(tree)
95 {
96 }
97 
99  : BaseReplacementPolicy(p), numLeaves(p->num_leaves), count(0),
100  treeInstance(nullptr)
101 {
103  "Number of leaves must be non-zero and a power of 2");
104 }
105 
106 void
108  const std::shared_ptr<ReplacementData>& replacement_data) const
109 {
110  // Cast replacement data
111  std::shared_ptr<TreePLRUReplData> treePLRU_replacement_data =
112  std::static_pointer_cast<TreePLRUReplData>(replacement_data);
113  PLRUTree* tree = treePLRU_replacement_data->tree.get();
114 
115  // Index of the tree entry we are currently checking
116  // Make this entry the new LRU entry
117  uint64_t tree_index = treePLRU_replacement_data->index;
118 
119  // Parse and update tree to make it point to the new LRU
120  do {
121  // Store whether we are coming from a left or right node
122  const bool right = isRightSubtree(tree_index);
123 
124  // Go to the parent tree node
125  tree_index = parentIndex(tree_index);
126 
127  // Update parent node to make it point to the node we just came from
128  tree->at(tree_index) = right;
129  } while (tree_index != 0);
130 }
131 
132 void
133 TreePLRURP::touch(const std::shared_ptr<ReplacementData>& replacement_data)
134 const
135 {
136  // Cast replacement data
137  std::shared_ptr<TreePLRUReplData> treePLRU_replacement_data =
138  std::static_pointer_cast<TreePLRUReplData>(replacement_data);
139  PLRUTree* tree = treePLRU_replacement_data->tree.get();
140 
141  // Index of the tree entry we are currently checking
142  // Make this entry the MRU entry
143  uint64_t tree_index = treePLRU_replacement_data->index;
144 
145  // Parse and update tree to make every bit point away from the new MRU
146  do {
147  // Store whether we are coming from a left or right node
148  const bool right = isRightSubtree(tree_index);
149 
150  // Go to the parent tree node
151  tree_index = parentIndex(tree_index);
152 
153  // Update node to not point to the touched leaf
154  tree->at(tree_index) = !right;
155  } while (tree_index != 0);
156 }
157 
158 void
159 TreePLRURP::reset(const std::shared_ptr<ReplacementData>& replacement_data)
160 const
161 {
162  // A reset has the same functionality of a touch
163  touch(replacement_data);
164 }
165 
168 {
169  // There must be at least one replacement candidate
170  assert(candidates.size() > 0);
171 
172  // Get tree
173  const PLRUTree* tree = std::static_pointer_cast<TreePLRUReplData>(
174  candidates[0]->replacementData)->tree.get();
175 
176  // Index of the tree entry we are currently checking. Start with root.
177  uint64_t tree_index = 0;
178 
179  // Parse tree
180  while (tree_index < tree->size()) {
181  // Go to the next tree entry
182  if (tree->at(tree_index)) {
183  tree_index = rightSubtreeIndex(tree_index);
184  } else {
185  tree_index = leftSubtreeIndex(tree_index);
186  }
187  }
188 
189  // The tree index is currently at the leaf of the victim displaced by the
190  // number of non-leaf nodes
191  return candidates[tree_index - (numLeaves - 1)];
192 }
193 
194 std::shared_ptr<ReplacementData>
196 {
197  // Generate a tree instance every numLeaves created
198  if (count % numLeaves == 0) {
199  treeInstance = new PLRUTree(numLeaves - 1, false);
200  }
201 
202  // Create replacement data using current tree instance
203  TreePLRUReplData* treePLRUReplData = new TreePLRUReplData(
204  (count % numLeaves) + numLeaves - 1,
205  std::shared_ptr<PLRUTree>(treeInstance));
206 
207  // Update instance counter
208  count++;
209 
210  return std::shared_ptr<ReplacementData>(treePLRUReplData);
211 }
212 
213 TreePLRURP*
214 TreePLRURPParams::create()
215 {
216  return new TreePLRURP(this);
217 }
ReplaceableEntry
A replaceable entry is a basic entry in a 2d table-like structure that needs to have replacement func...
Definition: replaceable_entry.hh:53
TreePLRURP::PLRUTree
std::vector< bool > PLRUTree
Instead of implementing the tree itself with pointers, it is implemented as an array of bits.
Definition: tree_plru_rp.hh:102
BaseReplacementPolicy::Params
BaseReplacementPolicyParams Params
Convenience typedef.
Definition: base.hh:52
MipsISA::index
Bitfield< 30, 0 > index
Definition: pra_constants.hh:44
TreePLRURP::TreePLRUReplData
Tree-PLRU-specific implementation of replacement data.
Definition: tree_plru_rp.hh:126
TreePLRURP::getVictim
ReplaceableEntry * getVictim(const ReplacementCandidates &candidates) const override
Find replacement victim using TreePLRU bits.
Definition: tree_plru_rp.cc:167
std::vector< bool >
TreePLRURP::touch
void touch(const std::shared_ptr< ReplacementData > &replacement_data) const override
Touch an entry to update its replacement data.
Definition: tree_plru_rp.cc:133
leftSubtreeIndex
static uint64_t leftSubtreeIndex(const uint64_t index)
Get index of the subtree on the left of the given indexed tree.
Definition: tree_plru_rp.cc:62
tree_plru_rp.hh
Copyright (c) 2018 Inria All rights reserved.
TreePLRURP::TreePLRUReplData::TreePLRUReplData
TreePLRUReplData(const uint64_t index, std::shared_ptr< PLRUTree > tree)
Default constructor.
Definition: tree_plru_rp.cc:92
BaseReplacementPolicy
A common base class of cache replacement policy objects.
Definition: base.hh:46
TreePLRURP
Definition: tree_plru_rp.hh:80
parentIndex
static uint64_t parentIndex(const uint64_t index)
Get the index of the parent of the given indexed subtree.
Definition: tree_plru_rp.cc:50
TreePLRURP::reset
void reset(const std::shared_ptr< ReplacementData > &replacement_data) const override
Reset replacement data.
Definition: tree_plru_rp.cc:159
TreePLRURP::instantiateEntry
std::shared_ptr< ReplacementData > instantiateEntry() override
Instantiate a replacement data entry.
Definition: tree_plru_rp.cc:195
TreePLRURP::invalidate
void invalidate(const std::shared_ptr< ReplacementData > &replacement_data) const override
Invalidate replacement data to set it as the next probable victim.
Definition: tree_plru_rp.cc:107
TreePLRURP::numLeaves
const uint64_t numLeaves
Number of leaves that share a single replacement data.
Definition: tree_plru_rp.hh:107
TreePLRURP::count
uint64_t count
Count of the number of sharers of a replacement data.
Definition: tree_plru_rp.hh:114
logging.hh
rightSubtreeIndex
static uint64_t rightSubtreeIndex(const uint64_t index)
Get index of the subtree on the right of the given indexed tree.
Definition: tree_plru_rp.cc:74
isRightSubtree
static bool isRightSubtree(const uint64_t index)
Find out if the subtree at index corresponds to the right or left subtree of its parent tree.
Definition: tree_plru_rp.cc:87
MipsISA::p
Bitfield< 0 > p
Definition: pra_constants.hh:323
intmath.hh
fatal_if
#define fatal_if(cond,...)
Conditional fatal macro that checks the supplied condition and only causes a fatal error if the condi...
Definition: logging.hh:219
TreePLRURP::treeInstance
PLRUTree * treeInstance
Holds the latest temporary tree instance created by instantiateEntry().
Definition: tree_plru_rp.hh:119
TreePLRURP::TreePLRURP
TreePLRURP(const Params *p)
Construct and initiliaze this replacement policy.
Definition: tree_plru_rp.cc:98
isPowerOf2
bool isPowerOf2(const T &n)
Definition: intmath.hh:102

Generated on Wed Sep 30 2020 14:02:12 for gem5 by doxygen 1.8.17