2 * Copyright (c) 2018 Inria
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;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
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.
28 * Authors: Daniel Carvalho
33 * Definitions of a Tree-PLRU replacement policy, along with some helper
34 * tree indexing functions, which map an index to the tree 2D-array.
37 #include "mem/cache/replacement_policies/tree_plru_rp.hh"
41 #include "base/intmath.hh"
42 #include "base/logging.hh"
43 #include "params/TreePLRURP.hh"
46 * Get the index of the parent of the given indexed subtree.
48 * @param Index of the queried tree.
49 * @return The index of the parent tree.
52 parentIndex(const uint64_t index
)
54 return std::floor((index
-1)/2);
58 * Get index of the subtree on the left of the given indexed tree.
60 * @param index The index of the queried tree.
61 * @return The index of the subtree to the left of the queried tree.
64 leftSubtreeIndex(const uint64_t index
)
70 * Get index of the subtree on the right of the given indexed tree.
72 * @param index The index of the queried tree.
73 * @return The index of the subtree to the right of the queried tree.
76 rightSubtreeIndex(const uint64_t index
)
82 * Find out if the subtree at index corresponds to the right or left subtree
85 * @param index The index of the subtree.
86 * @return True if it is a right subtree, false otherwise.
89 isRightSubtree(const uint64_t index
)
94 TreePLRURP::TreePLRUReplData::TreePLRUReplData(
95 const uint64_t index
, std::shared_ptr
<PLRUTree
> tree
)
96 : index(index
), tree(tree
)
100 TreePLRURP::TreePLRURP(const Params
*p
)
101 : BaseReplacementPolicy(p
), numLeaves(p
->num_leaves
), count(0),
102 treeInstance(nullptr)
104 fatal_if(!isPowerOf2(numLeaves
),
105 "Number of leaves must be non-zero and a power of 2");
109 TreePLRURP::invalidate(
110 const std::shared_ptr
<ReplacementData
>& replacement_data
) const
112 // Cast replacement data
113 std::shared_ptr
<TreePLRUReplData
> treePLRU_replacement_data
=
114 std::static_pointer_cast
<TreePLRUReplData
>(replacement_data
);
115 PLRUTree
* tree
= treePLRU_replacement_data
->tree
.get();
117 // Index of the tree entry we are currently checking
118 // Make this entry the new LRU entry
119 uint64_t tree_index
= treePLRU_replacement_data
->index
;
121 // Parse and update tree to make it point to the new LRU
123 // Store whether we are coming from a left or right node
124 const bool right
= isRightSubtree(tree_index
);
126 // Go to the parent tree node
127 tree_index
= parentIndex(tree_index
);
129 // Update parent node to make it point to the node we just came from
130 tree
->at(tree_index
) = right
;
131 } while (tree_index
!= 0);
135 TreePLRURP::touch(const std::shared_ptr
<ReplacementData
>& replacement_data
)
138 // Cast replacement data
139 std::shared_ptr
<TreePLRUReplData
> treePLRU_replacement_data
=
140 std::static_pointer_cast
<TreePLRUReplData
>(replacement_data
);
141 PLRUTree
* tree
= treePLRU_replacement_data
->tree
.get();
143 // Index of the tree entry we are currently checking
144 // Make this entry the MRU entry
145 uint64_t tree_index
= treePLRU_replacement_data
->index
;
147 // Parse and update tree to make every bit point away from the new MRU
149 // Store whether we are coming from a left or right node
150 const bool right
= isRightSubtree(tree_index
);
152 // Go to the parent tree node
153 tree_index
= parentIndex(tree_index
);
155 // Update node to not point to the touched leaf
156 tree
->at(tree_index
) = !right
;
157 } while (tree_index
!= 0);
161 TreePLRURP::reset(const std::shared_ptr
<ReplacementData
>& replacement_data
)
164 // A reset has the same functionality of a touch
165 touch(replacement_data
);
169 TreePLRURP::getVictim(const ReplacementCandidates
& candidates
) const
171 // There must be at least one replacement candidate
172 assert(candidates
.size() > 0);
175 const PLRUTree
* tree
= std::static_pointer_cast
<TreePLRUReplData
>(
176 candidates
[0]->replacementData
)->tree
.get();
178 // Index of the tree entry we are currently checking. Start with root.
179 uint64_t tree_index
= 0;
182 while (tree_index
< tree
->size()) {
183 // Go to the next tree entry
184 if (tree
->at(tree_index
)) {
185 tree_index
= rightSubtreeIndex(tree_index
);
187 tree_index
= leftSubtreeIndex(tree_index
);
191 // The tree index is currently at the leaf of the victim displaced by the
192 // number of non-leaf nodes
193 return candidates
[tree_index
- (numLeaves
- 1)];
196 std::shared_ptr
<ReplacementData
>
197 TreePLRURP::instantiateEntry()
199 // Generate a tree instance every numLeaves created
200 if (count
% numLeaves
== 0) {
201 treeInstance
= new PLRUTree(numLeaves
- 1, false);
204 // Create replacement data using current tree instance
205 TreePLRUReplData
* treePLRUReplData
= new TreePLRUReplData(
206 (count
% numLeaves
) + numLeaves
- 1,
207 std::shared_ptr
<PLRUTree
>(treeInstance
));
209 // Update instance counter
212 return std::shared_ptr
<ReplacementData
>(treePLRUReplData
);
216 TreePLRURPParams::create()
218 return new TreePLRURP(this);