gem5  v22.0.0.2
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 
43 namespace gem5
44 {
45 
46 GEM5_DEPRECATED_NAMESPACE(ReplacementPolicy, replacement_policy);
47 namespace replacement_policy
48 {
49 
56 static uint64_t
57 parentIndex(const uint64_t index)
58 {
59  return std::floor((index-1)/2);
60 }
61 
68 static uint64_t
69 leftSubtreeIndex(const uint64_t index)
70 {
71  return 2*index + 1;
72 }
73 
80 static uint64_t
81 rightSubtreeIndex(const uint64_t index)
82 {
83  return 2*index + 2;
84 }
85 
93 static bool
94 isRightSubtree(const uint64_t index)
95 {
96  return index%2 == 0;
97 }
98 
100  const uint64_t index, std::shared_ptr<PLRUTree> tree)
101  : index(index), tree(tree)
102 {
103 }
104 
106  : Base(p), numLeaves(p.num_leaves), count(0), treeInstance(nullptr)
107 {
109  "Number of leaves must be non-zero and a power of 2");
110 }
111 
112 void
113 TreePLRU::invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
114 {
115  // Cast replacement data
116  std::shared_ptr<TreePLRUReplData> treePLRU_replacement_data =
117  std::static_pointer_cast<TreePLRUReplData>(replacement_data);
118  PLRUTree* tree = treePLRU_replacement_data->tree.get();
119 
120  // Index of the tree entry we are currently checking
121  // Make this entry the new LRU entry
122  uint64_t tree_index = treePLRU_replacement_data->index;
123 
124  // Parse and update tree to make it point to the new LRU
125  do {
126  // Store whether we are coming from a left or right node
127  const bool right = isRightSubtree(tree_index);
128 
129  // Go to the parent tree node
130  tree_index = parentIndex(tree_index);
131 
132  // Update parent node to make it point to the node we just came from
133  tree->at(tree_index) = right;
134  } while (tree_index != 0);
135 }
136 
137 void
138 TreePLRU::touch(const std::shared_ptr<ReplacementData>& replacement_data)
139 const
140 {
141  // Cast replacement data
142  std::shared_ptr<TreePLRUReplData> treePLRU_replacement_data =
143  std::static_pointer_cast<TreePLRUReplData>(replacement_data);
144  PLRUTree* tree = treePLRU_replacement_data->tree.get();
145 
146  // Index of the tree entry we are currently checking
147  // Make this entry the MRU entry
148  uint64_t tree_index = treePLRU_replacement_data->index;
149 
150  // Parse and update tree to make every bit point away from the new MRU
151  do {
152  // Store whether we are coming from a left or right node
153  const bool right = isRightSubtree(tree_index);
154 
155  // Go to the parent tree node
156  tree_index = parentIndex(tree_index);
157 
158  // Update node to not point to the touched leaf
159  tree->at(tree_index) = !right;
160  } while (tree_index != 0);
161 }
162 
163 void
164 TreePLRU::reset(const std::shared_ptr<ReplacementData>& replacement_data)
165 const
166 {
167  // A reset has the same functionality of a touch
168  touch(replacement_data);
169 }
170 
173 {
174  // There must be at least one replacement candidate
175  assert(candidates.size() > 0);
176 
177  // Get tree
178  const PLRUTree* tree = std::static_pointer_cast<TreePLRUReplData>(
179  candidates[0]->replacementData)->tree.get();
180 
181  // Index of the tree entry we are currently checking. Start with root.
182  uint64_t tree_index = 0;
183 
184  // Parse tree
185  while (tree_index < tree->size()) {
186  // Go to the next tree entry
187  if (tree->at(tree_index)) {
188  tree_index = rightSubtreeIndex(tree_index);
189  } else {
190  tree_index = leftSubtreeIndex(tree_index);
191  }
192  }
193 
194  // The tree index is currently at the leaf of the victim displaced by the
195  // number of non-leaf nodes
196  return candidates[tree_index - (numLeaves - 1)];
197 }
198 
199 std::shared_ptr<ReplacementData>
201 {
202  // Generate a tree instance every numLeaves created
203  if (count % numLeaves == 0) {
204  treeInstance = new PLRUTree(numLeaves - 1, false);
205  }
206 
207  // Create replacement data using current tree instance
208  TreePLRUReplData* treePLRUReplData = new TreePLRUReplData(
209  (count % numLeaves) + numLeaves - 1,
210  std::shared_ptr<PLRUTree>(treeInstance));
211 
212  // Update instance counter
213  count++;
214 
215  return std::shared_ptr<ReplacementData>(treePLRUReplData);
216 }
217 
218 } // namespace replacement_policy
219 } // namespace gem5
gem5::replacement_policy::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:94
gem5::replacement_policy::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:81
gem5::replacement_policy::TreePLRU::TreePLRU
TreePLRU(const Params &p)
Definition: tree_plru_rp.cc:105
gem5::replacement_policy::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:69
gem5::replacement_policy::TreePLRU::treeInstance
PLRUTree * treeInstance
Holds the latest temporary tree instance created by instantiateEntry().
Definition: tree_plru_rp.hh:126
gem5::MipsISA::index
Bitfield< 30, 0 > index
Definition: pra_constants.hh:47
gem5::replacement_policy::Base::Params
BaseReplacementPolicyParams Params
Definition: base.hh:58
gem5::replacement_policy::TreePLRU::numLeaves
const uint64_t numLeaves
Number of leaves that share a single replacement data.
Definition: tree_plru_rp.hh:114
gem5::replacement_policy::TreePLRU::invalidate
void invalidate(const std::shared_ptr< ReplacementData > &replacement_data) override
Invalidate replacement data to set it as the next probable victim.
Definition: tree_plru_rp.cc:113
gem5::replacement_policy::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:57
std::vector< bool >
gem5::replacement_policy::TreePLRU::TreePLRUReplData::TreePLRUReplData
TreePLRUReplData(const uint64_t index, std::shared_ptr< PLRUTree > tree)
Default constructor.
Definition: tree_plru_rp.cc:99
gem5::replacement_policy::TreePLRU::count
uint64_t count
Count of the number of sharers of a replacement data.
Definition: tree_plru_rp.hh:121
gem5::isPowerOf2
static constexpr bool isPowerOf2(const T &n)
Definition: intmath.hh:98
gem5::replacement_policy::TreePLRU::reset
void reset(const std::shared_ptr< ReplacementData > &replacement_data) const override
Reset replacement data.
Definition: tree_plru_rp.cc:164
gem5::replacement_policy::TreePLRU::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:138
tree_plru_rp.hh
Copyright (c) 2018-2020 Inria All rights reserved.
gem5::replacement_policy::TreePLRU::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:109
gem5::VegaISA::p
Bitfield< 54 > p
Definition: pagetable.hh:70
gem5::replacement_policy::TreePLRU::getVictim
ReplaceableEntry * getVictim(const ReplacementCandidates &candidates) const override
Find replacement victim using TreePLRU bits.
Definition: tree_plru_rp.cc:172
gem5::replacement_policy::TreePLRU::TreePLRUReplData
Tree-PLRU-specific implementation of replacement data.
Definition: tree_plru_rp.hh:133
gem5::replacement_policy::Base
A common base class of cache replacement policy objects.
Definition: base.hh:55
gem5::GEM5_DEPRECATED_NAMESPACE
GEM5_DEPRECATED_NAMESPACE(GuestABI, guest_abi)
gem5::replacement_policy::TreePLRU::instantiateEntry
std::shared_ptr< ReplacementData > instantiateEntry() override
Instantiate a replacement data entry.
Definition: tree_plru_rp.cc:200
gem5::ReplaceableEntry
A replaceable entry is a basic entry in a 2d table-like structure that needs to have replacement func...
Definition: replaceable_entry.hh:63
logging.hh
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:226
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: gpu_translation_state.hh:37

Generated on Thu Jul 28 2022 13:32:34 for gem5 by doxygen 1.8.17