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;
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.
15 *
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.
27 *
28 * Authors: Daniel Carvalho
29 */
30
31/**
32 * @file
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.
35 */
36
37#include "mem/cache/replacement_policies/tree_plru_rp.hh"
38
| 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;
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.
15 *
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.
27 *
28 * Authors: Daniel Carvalho
29 */
30
31/**
32 * @file
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.
35 */
36
37#include "mem/cache/replacement_policies/tree_plru_rp.hh"
38
|
42#include "params/TreePLRURP.hh"
43
44/**
45 * Get the index of the parent of the given indexed subtree.
46 *
47 * @param Index of the queried tree.
48 * @return The index of the parent tree.
49 */
50static uint64_t
51parentIndex(const uint64_t index)
52{
53 return std::floor((index-1)/2);
54}
55
56/**
57 * Get index of the subtree on the left of the given indexed tree.
58 *
59 * @param index The index of the queried tree.
60 * @return The index of the subtree to the left of the queried tree.
61 */
62static uint64_t
63leftSubtreeIndex(const uint64_t index)
64{
65 return 2*index + 1;
66}
67
68/**
69 * Get index of the subtree on the right of the given indexed tree.
70 *
71 * @param index The index of the queried tree.
72 * @return The index of the subtree to the right of the queried tree.
73 */
74static uint64_t
75rightSubtreeIndex(const uint64_t index)
76{
77 return 2*index + 2;
78}
79
80/**
81 * Find out if the subtree at index corresponds to the right or left subtree
82 * of its parent tree.
83 *
84 * @param index The index of the subtree.
85 * @return True if it is a right subtree, false otherwise.
86 */
87static bool
88isRightSubtree(const uint64_t index)
89{
90 return index%2 == 0;
91}
92
93TreePLRURP::TreePLRUReplData::TreePLRUReplData(
94 const uint64_t index, std::shared_ptr<PLRUTree> tree)
95 : index(index), tree(tree)
96{
97}
98
99TreePLRURP::TreePLRURP(const Params *p)
100 : BaseReplacementPolicy(p), numLeaves(p->num_leaves), count(0),
101 treeInstance(nullptr)
102{
103 fatal_if(!isPowerOf2(numLeaves),
104 "Number of leaves must be non-zero and a power of 2");
105}
106
107void
108TreePLRURP::invalidate(
109 const std::shared_ptr<ReplacementData>& replacement_data) const
110{
111 // Cast replacement data
112 std::shared_ptr<TreePLRUReplData> treePLRU_replacement_data =
113 std::static_pointer_cast<TreePLRUReplData>(replacement_data);
114 PLRUTree* tree = treePLRU_replacement_data->tree.get();
115
116 // Index of the tree entry we are currently checking
117 // Make this entry the new LRU entry
118 uint64_t tree_index = treePLRU_replacement_data->index;
119
120 // Parse and update tree to make it point to the new LRU
121 do {
122 // Store whether we are coming from a left or right node
123 const bool right = isRightSubtree(tree_index);
124
125 // Go to the parent tree node
126 tree_index = parentIndex(tree_index);
127
128 // Update parent node to make it point to the node we just came from
129 tree->at(tree_index) = right;
130 } while (tree_index != 0);
131}
132
133void
134TreePLRURP::touch(const std::shared_ptr<ReplacementData>& replacement_data)
135const
136{
137 // Cast replacement data
138 std::shared_ptr<TreePLRUReplData> treePLRU_replacement_data =
139 std::static_pointer_cast<TreePLRUReplData>(replacement_data);
140 PLRUTree* tree = treePLRU_replacement_data->tree.get();
141
142 // Index of the tree entry we are currently checking
143 // Make this entry the MRU entry
144 uint64_t tree_index = treePLRU_replacement_data->index;
145
146 // Parse and update tree to make every bit point away from the new MRU
147 do {
148 // Store whether we are coming from a left or right node
149 const bool right = isRightSubtree(tree_index);
150
151 // Go to the parent tree node
152 tree_index = parentIndex(tree_index);
153
154 // Update node to not point to the touched leaf
155 tree->at(tree_index) = !right;
156 } while (tree_index != 0);
157}
158
159void
160TreePLRURP::reset(const std::shared_ptr<ReplacementData>& replacement_data)
161const
162{
163 // A reset has the same functionality of a touch
164 touch(replacement_data);
165}
166
167ReplaceableEntry*
168TreePLRURP::getVictim(const ReplacementCandidates& candidates) const
169{
170 // There must be at least one replacement candidate
171 assert(candidates.size() > 0);
172
173 // Get tree
174 const PLRUTree* tree = std::static_pointer_cast<TreePLRUReplData>(
175 candidates[0]->replacementData)->tree.get();
176
177 // Index of the tree entry we are currently checking. Start with root.
178 uint64_t tree_index = 0;
179
180 // Parse tree
181 while (tree_index < tree->size()) {
182 // Go to the next tree entry
183 if (tree->at(tree_index)) {
184 tree_index = rightSubtreeIndex(tree_index);
185 } else {
186 tree_index = leftSubtreeIndex(tree_index);
187 }
188 }
189
190 // The tree index is currently at the leaf of the victim displaced by the
191 // number of non-leaf nodes
192 return candidates[tree_index - (numLeaves - 1)];
193}
194
195std::shared_ptr<ReplacementData>
196TreePLRURP::instantiateEntry()
197{
198 // Generate a tree instance every numLeaves created
199 if (count % numLeaves == 0) {
200 treeInstance = new PLRUTree(numLeaves - 1, false);
201 }
202
203 // Create replacement data using current tree instance
204 TreePLRUReplData* treePLRUReplData = new TreePLRUReplData(
205 (count % numLeaves) + numLeaves - 1,
206 std::shared_ptr<PLRUTree>(treeInstance));
207
208 // Update instance counter
209 count++;
210
211 return std::shared_ptr<ReplacementData>(treePLRUReplData);
212}
213
214TreePLRURP*
215TreePLRURPParams::create()
216{
217 return new TreePLRURP(this);
218}
| 43#include "params/TreePLRURP.hh"
44
45/**
46 * Get the index of the parent of the given indexed subtree.
47 *
48 * @param Index of the queried tree.
49 * @return The index of the parent tree.
50 */
51static uint64_t
52parentIndex(const uint64_t index)
53{
54 return std::floor((index-1)/2);
55}
56
57/**
58 * Get index of the subtree on the left of the given indexed tree.
59 *
60 * @param index The index of the queried tree.
61 * @return The index of the subtree to the left of the queried tree.
62 */
63static uint64_t
64leftSubtreeIndex(const uint64_t index)
65{
66 return 2*index + 1;
67}
68
69/**
70 * Get index of the subtree on the right of the given indexed tree.
71 *
72 * @param index The index of the queried tree.
73 * @return The index of the subtree to the right of the queried tree.
74 */
75static uint64_t
76rightSubtreeIndex(const uint64_t index)
77{
78 return 2*index + 2;
79}
80
81/**
82 * Find out if the subtree at index corresponds to the right or left subtree
83 * of its parent tree.
84 *
85 * @param index The index of the subtree.
86 * @return True if it is a right subtree, false otherwise.
87 */
88static bool
89isRightSubtree(const uint64_t index)
90{
91 return index%2 == 0;
92}
93
94TreePLRURP::TreePLRUReplData::TreePLRUReplData(
95 const uint64_t index, std::shared_ptr<PLRUTree> tree)
96 : index(index), tree(tree)
97{
98}
99
100TreePLRURP::TreePLRURP(const Params *p)
101 : BaseReplacementPolicy(p), numLeaves(p->num_leaves), count(0),
102 treeInstance(nullptr)
103{
104 fatal_if(!isPowerOf2(numLeaves),
105 "Number of leaves must be non-zero and a power of 2");
106}
107
108void
109TreePLRURP::invalidate(
110 const std::shared_ptr<ReplacementData>& replacement_data) const
111{
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();
116
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;
120
121 // Parse and update tree to make it point to the new LRU
122 do {
123 // Store whether we are coming from a left or right node
124 const bool right = isRightSubtree(tree_index);
125
126 // Go to the parent tree node
127 tree_index = parentIndex(tree_index);
128
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);
132}
133
134void
135TreePLRURP::touch(const std::shared_ptr<ReplacementData>& replacement_data)
136const
137{
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();
142
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;
146
147 // Parse and update tree to make every bit point away from the new MRU
148 do {
149 // Store whether we are coming from a left or right node
150 const bool right = isRightSubtree(tree_index);
151
152 // Go to the parent tree node
153 tree_index = parentIndex(tree_index);
154
155 // Update node to not point to the touched leaf
156 tree->at(tree_index) = !right;
157 } while (tree_index != 0);
158}
159
160void
161TreePLRURP::reset(const std::shared_ptr<ReplacementData>& replacement_data)
162const
163{
164 // A reset has the same functionality of a touch
165 touch(replacement_data);
166}
167
168ReplaceableEntry*
169TreePLRURP::getVictim(const ReplacementCandidates& candidates) const
170{
171 // There must be at least one replacement candidate
172 assert(candidates.size() > 0);
173
174 // Get tree
175 const PLRUTree* tree = std::static_pointer_cast<TreePLRUReplData>(
176 candidates[0]->replacementData)->tree.get();
177
178 // Index of the tree entry we are currently checking. Start with root.
179 uint64_t tree_index = 0;
180
181 // Parse tree
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);
186 } else {
187 tree_index = leftSubtreeIndex(tree_index);
188 }
189 }
190
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)];
194}
195
196std::shared_ptr<ReplacementData>
197TreePLRURP::instantiateEntry()
198{
199 // Generate a tree instance every numLeaves created
200 if (count % numLeaves == 0) {
201 treeInstance = new PLRUTree(numLeaves - 1, false);
202 }
203
204 // Create replacement data using current tree instance
205 TreePLRUReplData* treePLRUReplData = new TreePLRUReplData(
206 (count % numLeaves) + numLeaves - 1,
207 std::shared_ptr<PLRUTree>(treeInstance));
208
209 // Update instance counter
210 count++;
211
212 return std::shared_ptr<ReplacementData>(treePLRUReplData);
213}
214
215TreePLRURP*
216TreePLRURPParams::create()
217{
218 return new TreePLRURP(this);
219}
|