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