1/**
2 * Copyright (c) 2018 Metempsy Technology Consulting
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: Javier Bueno
29 */
30
31 #include "mem/cache/prefetch/indirect_memory.hh"
32
33 #include "mem/cache/base.hh"
34 #include "mem/cache/prefetch/associative_set_impl.hh"
35 #include "params/IndirectMemoryPrefetcher.hh"
36
37IndirectMemoryPrefetcher::IndirectMemoryPrefetcher(
38 const IndirectMemoryPrefetcherParams *p) : QueuedPrefetcher(p),
39 maxPrefetchDistance(p->max_prefetch_distance),
40 shiftValues(p->shift_values), prefetchThreshold(p->prefetch_threshold),
| 1/**
2 * Copyright (c) 2018 Metempsy Technology Consulting
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: Javier Bueno
29 */
30
31 #include "mem/cache/prefetch/indirect_memory.hh"
32
33 #include "mem/cache/base.hh"
34 #include "mem/cache/prefetch/associative_set_impl.hh"
35 #include "params/IndirectMemoryPrefetcher.hh"
36
37IndirectMemoryPrefetcher::IndirectMemoryPrefetcher(
38 const IndirectMemoryPrefetcherParams *p) : QueuedPrefetcher(p),
39 maxPrefetchDistance(p->max_prefetch_distance),
40 shiftValues(p->shift_values), prefetchThreshold(p->prefetch_threshold),
|
41 maxIndirectCounterValue(p->max_indirect_counter_value),
| |
42 streamCounterThreshold(p->stream_counter_threshold),
43 streamingDistance(p->streaming_distance),
44 prefetchTable(p->pt_table_assoc, p->pt_table_entries,
| 41 streamCounterThreshold(p->stream_counter_threshold),
42 streamingDistance(p->streaming_distance),
43 prefetchTable(p->pt_table_assoc, p->pt_table_entries,
|
45 p->pt_table_indexing_policy, p->pt_table_replacement_policy),
| 44 p->pt_table_indexing_policy, p->pt_table_replacement_policy,
45 PrefetchTableEntry(p->num_indirect_counter_bits)),
|
46 ipd(p->ipd_table_assoc, p->ipd_table_entries, p->ipd_table_indexing_policy,
47 p->ipd_table_replacement_policy,
48 IndirectPatternDetectorEntry(p->addr_array_len, shiftValues.size())),
49 ipdEntryTrackingMisses(nullptr),
50#if THE_ISA != NULL_ISA
51 byteOrder(TheISA::GuestByteOrder)
52#else
53 byteOrder((ByteOrder) -1)
54#endif
55{
56 fatal_if(byteOrder == static_cast<ByteOrder>(-1),
57 "This prefetcher requires a defined ISA\n");
58}
59
60void
61IndirectMemoryPrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
62 std::vector<AddrPriority> &addresses)
63{
64 // This prefetcher requires a PC
65 if (!pfi.hasPC()) {
66 return;
67 }
68
69 bool is_secure = pfi.isSecure();
70 Addr pc = pfi.getPC();
71 Addr addr = pfi.getAddr();
72 bool miss = pfi.isCacheMiss();
73
74 checkAccessMatchOnActiveEntries(addr);
75
76 // First check if this is a miss, if the prefetcher is tracking misses
77 if (ipdEntryTrackingMisses != nullptr && miss) {
78 // Check if the entry tracking misses has already set its second index
79 if (!ipdEntryTrackingMisses->secondIndexSet) {
80 trackMissIndex1(addr);
81 } else {
82 trackMissIndex2(addr);
83 }
84 } else {
85 // if misses are not being tracked, attempt to detect stream accesses
86 PrefetchTableEntry *pt_entry =
87 prefetchTable.findEntry(pc, false /* unused */);
88 if (pt_entry != nullptr) {
89 prefetchTable.accessEntry(pt_entry);
90
91 if (pt_entry->address != addr) {
92 // Streaming access found
93 pt_entry->streamCounter += 1;
94 if (pt_entry->streamCounter >= streamCounterThreshold) {
95 int64_t delta = addr - pt_entry->address;
96 for (unsigned int i = 1; i <= streamingDistance; i += 1) {
97 addresses.push_back(AddrPriority(addr + delta * i, 0));
98 }
99 }
100 pt_entry->address = addr;
101 pt_entry->secure = is_secure;
102
103
104 // if this is a read, read the data from the cache and assume
105 // it is an index (this is only possible if the data is already
106 // in the cache), also, only indexes up to 8 bytes are
107 // considered
108
109 if (!miss && !pfi.isWrite() && pfi.getSize() <= 8) {
110 int64_t index = 0;
111 bool read_index = true;
112 switch(pfi.getSize()) {
113 case sizeof(uint8_t):
114 index = pfi.get<uint8_t>(byteOrder);
115 break;
116 case sizeof(uint16_t):
117 index = pfi.get<uint16_t>(byteOrder);
118 break;
119 case sizeof(uint32_t):
120 index = pfi.get<uint32_t>(byteOrder);
121 break;
122 case sizeof(uint64_t):
123 index = pfi.get<uint64_t>(byteOrder);
124 break;
125 default:
126 // Ignore non-power-of-two sizes
127 read_index = false;
128 }
129 if (read_index && !pt_entry->enabled) {
130 // Not enabled (no pattern detected in this stream),
131 // add or update an entry in the pattern detector and
132 // start tracking misses
133 allocateOrUpdateIPDEntry(pt_entry, index);
134 } else if (read_index) {
135 // Enabled entry, update the index
136 pt_entry->index = index;
137 if (!pt_entry->increasedIndirectCounter) {
| 46 ipd(p->ipd_table_assoc, p->ipd_table_entries, p->ipd_table_indexing_policy,
47 p->ipd_table_replacement_policy,
48 IndirectPatternDetectorEntry(p->addr_array_len, shiftValues.size())),
49 ipdEntryTrackingMisses(nullptr),
50#if THE_ISA != NULL_ISA
51 byteOrder(TheISA::GuestByteOrder)
52#else
53 byteOrder((ByteOrder) -1)
54#endif
55{
56 fatal_if(byteOrder == static_cast<ByteOrder>(-1),
57 "This prefetcher requires a defined ISA\n");
58}
59
60void
61IndirectMemoryPrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
62 std::vector<AddrPriority> &addresses)
63{
64 // This prefetcher requires a PC
65 if (!pfi.hasPC()) {
66 return;
67 }
68
69 bool is_secure = pfi.isSecure();
70 Addr pc = pfi.getPC();
71 Addr addr = pfi.getAddr();
72 bool miss = pfi.isCacheMiss();
73
74 checkAccessMatchOnActiveEntries(addr);
75
76 // First check if this is a miss, if the prefetcher is tracking misses
77 if (ipdEntryTrackingMisses != nullptr && miss) {
78 // Check if the entry tracking misses has already set its second index
79 if (!ipdEntryTrackingMisses->secondIndexSet) {
80 trackMissIndex1(addr);
81 } else {
82 trackMissIndex2(addr);
83 }
84 } else {
85 // if misses are not being tracked, attempt to detect stream accesses
86 PrefetchTableEntry *pt_entry =
87 prefetchTable.findEntry(pc, false /* unused */);
88 if (pt_entry != nullptr) {
89 prefetchTable.accessEntry(pt_entry);
90
91 if (pt_entry->address != addr) {
92 // Streaming access found
93 pt_entry->streamCounter += 1;
94 if (pt_entry->streamCounter >= streamCounterThreshold) {
95 int64_t delta = addr - pt_entry->address;
96 for (unsigned int i = 1; i <= streamingDistance; i += 1) {
97 addresses.push_back(AddrPriority(addr + delta * i, 0));
98 }
99 }
100 pt_entry->address = addr;
101 pt_entry->secure = is_secure;
102
103
104 // if this is a read, read the data from the cache and assume
105 // it is an index (this is only possible if the data is already
106 // in the cache), also, only indexes up to 8 bytes are
107 // considered
108
109 if (!miss && !pfi.isWrite() && pfi.getSize() <= 8) {
110 int64_t index = 0;
111 bool read_index = true;
112 switch(pfi.getSize()) {
113 case sizeof(uint8_t):
114 index = pfi.get<uint8_t>(byteOrder);
115 break;
116 case sizeof(uint16_t):
117 index = pfi.get<uint16_t>(byteOrder);
118 break;
119 case sizeof(uint32_t):
120 index = pfi.get<uint32_t>(byteOrder);
121 break;
122 case sizeof(uint64_t):
123 index = pfi.get<uint64_t>(byteOrder);
124 break;
125 default:
126 // Ignore non-power-of-two sizes
127 read_index = false;
128 }
129 if (read_index && !pt_entry->enabled) {
130 // Not enabled (no pattern detected in this stream),
131 // add or update an entry in the pattern detector and
132 // start tracking misses
133 allocateOrUpdateIPDEntry(pt_entry, index);
134 } else if (read_index) {
135 // Enabled entry, update the index
136 pt_entry->index = index;
137 if (!pt_entry->increasedIndirectCounter) {
|
138 if (pt_entry->indirectCounter > 0) {
139 pt_entry->indirectCounter -= 1;
140 }
| 138 pt_entry->indirectCounter--;
|
141 } else {
142 // Set this to false, to see if the new index
143 // has any match
144 pt_entry->increasedIndirectCounter = false;
145 }
146
147 // If the counter is high enough, start prefetching
148 if (pt_entry->indirectCounter > prefetchThreshold) {
| 139 } else {
140 // Set this to false, to see if the new index
141 // has any match
142 pt_entry->increasedIndirectCounter = false;
143 }
144
145 // If the counter is high enough, start prefetching
146 if (pt_entry->indirectCounter > prefetchThreshold) {
|
149 unsigned distance = pt_entry->indirectCounter *
150 maxPrefetchDistance / maxIndirectCounterValue;
| 147 unsigned distance = maxPrefetchDistance *
148 pt_entry->indirectCounter.calcSaturation();
|
151 for (int delta = 1; delta < distance; delta += 1) {
152 Addr pf_addr = pt_entry->baseAddr +
153 (pt_entry->index << pt_entry->shift);
154 addresses.push_back(AddrPriority(pf_addr, 0));
155 }
156 }
157 }
158 }
159 }
160 } else {
161 pt_entry = prefetchTable.findVictim(pc);
162 assert(pt_entry != nullptr);
163 prefetchTable.insertEntry(pc, false /* unused */, pt_entry);
164 pt_entry->address = addr;
165 pt_entry->secure = is_secure;
166 }
167 }
168}
169
170void
171IndirectMemoryPrefetcher::allocateOrUpdateIPDEntry(
172 const PrefetchTableEntry *pt_entry, int64_t index)
173{
174 // The address of the pt_entry is used to index the IPD
175 Addr ipd_entry_addr = (Addr) pt_entry;
176 IndirectPatternDetectorEntry *ipd_entry = ipd.findEntry(ipd_entry_addr,
177 false/* unused */);
178 if (ipd_entry != nullptr) {
179 ipd.accessEntry(ipd_entry);
180 if (!ipd_entry->secondIndexSet) {
181 // Second time we see an index, fill idx2
182 ipd_entry->idx2 = index;
183 ipd_entry->secondIndexSet = true;
184 ipdEntryTrackingMisses = ipd_entry;
185 } else {
186 // Third access! no pattern has been found so far,
187 // release the IPD entry
188 ipd_entry->reset();
189 ipdEntryTrackingMisses = nullptr;
190 }
191 } else {
192 ipd_entry = ipd.findVictim(ipd_entry_addr);
193 assert(ipd_entry != nullptr);
194 ipd.insertEntry(ipd_entry_addr, false /* unused */, ipd_entry);
195 ipd_entry->idx1 = index;
196 ipdEntryTrackingMisses = ipd_entry;
197 }
198}
199
200void
201IndirectMemoryPrefetcher::trackMissIndex1(Addr miss_addr)
202{
203 IndirectPatternDetectorEntry *entry = ipdEntryTrackingMisses;
204 // If the second index is not set, we are just filling the baseAddr
205 // vector
206 assert(entry->numMisses < entry->baseAddr.size());
207 std::vector<Addr> &ba_array = entry->baseAddr[entry->numMisses];
208 int idx = 0;
209 for (int shift : shiftValues) {
210 ba_array[idx] = miss_addr - (entry->idx1 << shift);
211 idx += 1;
212 }
213 entry->numMisses += 1;
214 if (entry->numMisses == entry->baseAddr.size()) {
215 // stop tracking misses once we have tracked enough
216 ipdEntryTrackingMisses = nullptr;
217 }
218}
219void
220IndirectMemoryPrefetcher::trackMissIndex2(Addr miss_addr)
221{
222 IndirectPatternDetectorEntry *entry = ipdEntryTrackingMisses;
223 // Second index is filled, compare the addresses generated during
224 // the previous misses (using idx1) against newly generated values
225 // using idx2, if a match is found, fill the additional fields
226 // of the PT entry
227 for (int midx = 0; midx < entry->numMisses; midx += 1)
228 {
229 std::vector<Addr> &ba_array = entry->baseAddr[midx];
230 int idx = 0;
231 for (int shift : shiftValues) {
232 if (ba_array[idx] == (miss_addr - (entry->idx2 << shift))) {
233 // Match found!
234 // Fill the corresponding pt_entry
235 PrefetchTableEntry *pt_entry =
236 (PrefetchTableEntry *) entry->getTag();
237 pt_entry->baseAddr = ba_array[idx];
238 pt_entry->shift = shift;
239 pt_entry->enabled = true;
| 149 for (int delta = 1; delta < distance; delta += 1) {
150 Addr pf_addr = pt_entry->baseAddr +
151 (pt_entry->index << pt_entry->shift);
152 addresses.push_back(AddrPriority(pf_addr, 0));
153 }
154 }
155 }
156 }
157 }
158 } else {
159 pt_entry = prefetchTable.findVictim(pc);
160 assert(pt_entry != nullptr);
161 prefetchTable.insertEntry(pc, false /* unused */, pt_entry);
162 pt_entry->address = addr;
163 pt_entry->secure = is_secure;
164 }
165 }
166}
167
168void
169IndirectMemoryPrefetcher::allocateOrUpdateIPDEntry(
170 const PrefetchTableEntry *pt_entry, int64_t index)
171{
172 // The address of the pt_entry is used to index the IPD
173 Addr ipd_entry_addr = (Addr) pt_entry;
174 IndirectPatternDetectorEntry *ipd_entry = ipd.findEntry(ipd_entry_addr,
175 false/* unused */);
176 if (ipd_entry != nullptr) {
177 ipd.accessEntry(ipd_entry);
178 if (!ipd_entry->secondIndexSet) {
179 // Second time we see an index, fill idx2
180 ipd_entry->idx2 = index;
181 ipd_entry->secondIndexSet = true;
182 ipdEntryTrackingMisses = ipd_entry;
183 } else {
184 // Third access! no pattern has been found so far,
185 // release the IPD entry
186 ipd_entry->reset();
187 ipdEntryTrackingMisses = nullptr;
188 }
189 } else {
190 ipd_entry = ipd.findVictim(ipd_entry_addr);
191 assert(ipd_entry != nullptr);
192 ipd.insertEntry(ipd_entry_addr, false /* unused */, ipd_entry);
193 ipd_entry->idx1 = index;
194 ipdEntryTrackingMisses = ipd_entry;
195 }
196}
197
198void
199IndirectMemoryPrefetcher::trackMissIndex1(Addr miss_addr)
200{
201 IndirectPatternDetectorEntry *entry = ipdEntryTrackingMisses;
202 // If the second index is not set, we are just filling the baseAddr
203 // vector
204 assert(entry->numMisses < entry->baseAddr.size());
205 std::vector<Addr> &ba_array = entry->baseAddr[entry->numMisses];
206 int idx = 0;
207 for (int shift : shiftValues) {
208 ba_array[idx] = miss_addr - (entry->idx1 << shift);
209 idx += 1;
210 }
211 entry->numMisses += 1;
212 if (entry->numMisses == entry->baseAddr.size()) {
213 // stop tracking misses once we have tracked enough
214 ipdEntryTrackingMisses = nullptr;
215 }
216}
217void
218IndirectMemoryPrefetcher::trackMissIndex2(Addr miss_addr)
219{
220 IndirectPatternDetectorEntry *entry = ipdEntryTrackingMisses;
221 // Second index is filled, compare the addresses generated during
222 // the previous misses (using idx1) against newly generated values
223 // using idx2, if a match is found, fill the additional fields
224 // of the PT entry
225 for (int midx = 0; midx < entry->numMisses; midx += 1)
226 {
227 std::vector<Addr> &ba_array = entry->baseAddr[midx];
228 int idx = 0;
229 for (int shift : shiftValues) {
230 if (ba_array[idx] == (miss_addr - (entry->idx2 << shift))) {
231 // Match found!
232 // Fill the corresponding pt_entry
233 PrefetchTableEntry *pt_entry =
234 (PrefetchTableEntry *) entry->getTag();
235 pt_entry->baseAddr = ba_array[idx];
236 pt_entry->shift = shift;
237 pt_entry->enabled = true;
|
240 pt_entry->indirectCounter = 0;
| 238 pt_entry->indirectCounter.reset();
|
241 // Release the current IPD Entry
242 entry->reset();
243 // Do not track more misses
244 ipdEntryTrackingMisses = nullptr;
245 return;
246 }
247 idx += 1;
248 }
249 }
250}
251
252void
253IndirectMemoryPrefetcher::checkAccessMatchOnActiveEntries(Addr addr)
254{
255 for (auto &pt_entry : prefetchTable) {
256 if (pt_entry.enabled) {
257 if (addr == pt_entry.baseAddr +
258 (pt_entry.index << pt_entry.shift)) {
| 239 // Release the current IPD Entry
240 entry->reset();
241 // Do not track more misses
242 ipdEntryTrackingMisses = nullptr;
243 return;
244 }
245 idx += 1;
246 }
247 }
248}
249
250void
251IndirectMemoryPrefetcher::checkAccessMatchOnActiveEntries(Addr addr)
252{
253 for (auto &pt_entry : prefetchTable) {
254 if (pt_entry.enabled) {
255 if (addr == pt_entry.baseAddr +
256 (pt_entry.index << pt_entry.shift)) {
|
259 if (pt_entry.indirectCounter < maxIndirectCounterValue) {
260 pt_entry.indirectCounter += 1;
261 pt_entry.increasedIndirectCounter = true;
262 }
| 257 pt_entry.indirectCounter++;
258 pt_entry.increasedIndirectCounter = true;
|
263 }
264 }
265 }
266}
267
268IndirectMemoryPrefetcher*
269IndirectMemoryPrefetcherParams::create()
270{
271 return new IndirectMemoryPrefetcher(this);
272}
| 259 }
260 }
261 }
262}
263
264IndirectMemoryPrefetcher*
265IndirectMemoryPrefetcherParams::create()
266{
267 return new IndirectMemoryPrefetcher(this);
268}
|