signature_path.cc (13553:047def1fa787) signature_path.cc (13624:3d8220c2d41d)
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;

--- 39 unchanged lines hidden (view full) ---

48 signatureTable(p->signature_table_assoc, p->signature_table_entries,
49 p->signature_table_indexing_policy,
50 p->signature_table_replacement_policy),
51 patternTable(p->pattern_table_assoc, p->pattern_table_entries,
52 p->pattern_table_indexing_policy,
53 p->pattern_table_replacement_policy,
54 PatternEntry(stridesPerPatternEntry))
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;

--- 39 unchanged lines hidden (view full) ---

48 signatureTable(p->signature_table_assoc, p->signature_table_entries,
49 p->signature_table_indexing_policy,
50 p->signature_table_replacement_policy),
51 patternTable(p->pattern_table_assoc, p->pattern_table_entries,
52 p->pattern_table_indexing_policy,
53 p->pattern_table_replacement_policy,
54 PatternEntry(stridesPerPatternEntry))
55{
56 fatal_if(prefetchConfidenceThreshold < 0,
57 "The prefetch confidence threshold must be greater than 0\n");
58 fatal_if(prefetchConfidenceThreshold > 1,
59 "The prefetch confidence threshold must be less than 1\n");
60 fatal_if(lookaheadConfidenceThreshold < 0,
61 "The lookahead confidence threshold must be greater than 0\n");
62 fatal_if(lookaheadConfidenceThreshold > 1,
63 "The lookahead confidence threshold must be less than 1\n");
56}
57
58SignaturePathPrefetcher::PatternStrideEntry &
59SignaturePathPrefetcher::PatternEntry::getStrideEntry(stride_t stride,
60 uint8_t max_counter_value)
61{
62 PatternStrideEntry *pstride_entry = findStride(stride);
63 if (pstride_entry == nullptr) {

--- 17 unchanged lines hidden (view full) ---

81 pstride_entry = victim_pstride_entry;
82 pstride_entry->counter = 0;
83 pstride_entry->stride = stride;
84 }
85 return *pstride_entry;
86}
87
88void
64}
65
66SignaturePathPrefetcher::PatternStrideEntry &
67SignaturePathPrefetcher::PatternEntry::getStrideEntry(stride_t stride,
68 uint8_t max_counter_value)
69{
70 PatternStrideEntry *pstride_entry = findStride(stride);
71 if (pstride_entry == nullptr) {

--- 17 unchanged lines hidden (view full) ---

89 pstride_entry = victim_pstride_entry;
90 pstride_entry->counter = 0;
91 pstride_entry->stride = stride;
92 }
93 return *pstride_entry;
94}
95
96void
89SignaturePathPrefetcher::addPrefetch(Addr ppn, stride_t block,
97SignaturePathPrefetcher::addPrefetch(Addr ppn, stride_t last_block,
98 stride_t delta, double path_confidence, signature_t signature,
90 bool is_secure, std::vector<AddrPriority> &addresses)
91{
99 bool is_secure, std::vector<AddrPriority> &addresses)
100{
92 /**
93 * block is relative to the provided ppn. Assuming a page size of 4kB and
94 * a block size of 64B, the range of the stride of this prefetcher is
95 * -63,63 (pageBytes/blkSize) as the last accessed block also ranges from
96 * 0,63, the block value is expected to be between -63 and 126
97 * Negative block means that we are accessing the lower contiguous page,
98 * 64 or greater point to the next contiguous.
99 */
100 assert(block > -((stride_t)(pageBytes/blkSize)));
101 assert(block < 2*((stride_t)(pageBytes/blkSize)));
101 stride_t block = last_block + delta;
102
103 Addr pf_ppn;
104 stride_t pf_block;
105 if (block < 0) {
102
103 Addr pf_ppn;
104 stride_t pf_block;
105 if (block < 0) {
106 pf_ppn = ppn - 1;
107 pf_block = block + (pageBytes/blkSize);
106 stride_t num_cross_pages = 1 + (-block) / (pageBytes/blkSize);
107 if (num_cross_pages > ppn) {
108 // target address smaller than page 0, ignore this request;
109 return;
110 }
111 pf_ppn = ppn - num_cross_pages;
112 pf_block = block + (pageBytes/blkSize) * num_cross_pages;
113 handlePageCrossingLookahead(signature, last_block, delta,
114 path_confidence);
108 } else if (block >= (pageBytes/blkSize)) {
115 } else if (block >= (pageBytes/blkSize)) {
109 pf_ppn = ppn + 1;
110 pf_block = block - (pageBytes/blkSize);
116 stride_t num_cross_pages = block / (pageBytes/blkSize);
117 if (MaxAddr/pageBytes < (ppn + num_cross_pages)) {
118 // target address goes beyond MaxAddr, ignore this request;
119 return;
120 }
121 pf_ppn = ppn + num_cross_pages;
122 pf_block = block - (pageBytes/blkSize) * num_cross_pages;
123 handlePageCrossingLookahead(signature, last_block, delta,
124 path_confidence);
111 } else {
112 pf_ppn = ppn;
113 pf_block = block;
114 }
115
116 Addr new_addr = pf_ppn * pageBytes;
117 new_addr += pf_block * (Addr)blkSize;
118
119 DPRINTF(HWPrefetch, "Queuing prefetch to %#x.\n", new_addr);
120 addresses.push_back(AddrPriority(new_addr, 0));
121}
122
123void
125 } else {
126 pf_ppn = ppn;
127 pf_block = block;
128 }
129
130 Addr new_addr = pf_ppn * pageBytes;
131 new_addr += pf_block * (Addr)blkSize;
132
133 DPRINTF(HWPrefetch, "Queuing prefetch to %#x.\n", new_addr);
134 addresses.push_back(AddrPriority(new_addr, 0));
135}
136
137void
138SignaturePathPrefetcher::handleSignatureTableMiss(stride_t current_block,
139 signature_t &new_signature, double &new_conf, stride_t &new_stride)
140{
141 new_signature = current_block;
142 new_conf = 1.0;
143 new_stride = current_block;
144}
145
146void
147SignaturePathPrefetcher::increasePatternEntryCounter(
148 PatternEntry &pattern_entry, PatternStrideEntry &pstride_entry)
149{
150 if (pstride_entry.counter < maxCounterValue) {
151 pstride_entry.counter += 1;
152 }
153}
154
155void
124SignaturePathPrefetcher::updatePatternTable(Addr signature, stride_t stride)
125{
126 assert(stride != 0);
127 // The pattern table is indexed by signatures
128 PatternEntry &p_entry = getPatternEntry(signature);
129 PatternStrideEntry &ps_entry = p_entry.getStrideEntry(stride,
130 maxCounterValue);
156SignaturePathPrefetcher::updatePatternTable(Addr signature, stride_t stride)
157{
158 assert(stride != 0);
159 // The pattern table is indexed by signatures
160 PatternEntry &p_entry = getPatternEntry(signature);
161 PatternStrideEntry &ps_entry = p_entry.getStrideEntry(stride,
162 maxCounterValue);
131 if (ps_entry.counter < maxCounterValue) {
132 ps_entry.counter += 1;
133 }
163 increasePatternEntryCounter(p_entry, ps_entry);
134}
135
136SignaturePathPrefetcher::SignatureEntry &
137SignaturePathPrefetcher::getSignatureEntry(Addr ppn, bool is_secure,
164}
165
166SignaturePathPrefetcher::SignatureEntry &
167SignaturePathPrefetcher::getSignatureEntry(Addr ppn, bool is_secure,
138 stride_t block, bool &miss)
168 stride_t block, bool &miss, stride_t &stride,
169 double &initial_confidence)
139{
140 SignatureEntry* signature_entry = signatureTable.findEntry(ppn, is_secure);
141 if (signature_entry != nullptr) {
142 signatureTable.accessEntry(signature_entry);
143 miss = false;
170{
171 SignatureEntry* signature_entry = signatureTable.findEntry(ppn, is_secure);
172 if (signature_entry != nullptr) {
173 signatureTable.accessEntry(signature_entry);
174 miss = false;
175 stride = block - signature_entry->lastBlock;
144 } else {
145 signature_entry = signatureTable.findVictim(ppn);
146 assert(signature_entry != nullptr);
147
176 } else {
177 signature_entry = signatureTable.findVictim(ppn);
178 assert(signature_entry != nullptr);
179
180 // Sets signature_entry->signature, initial_confidence, and stride
181 handleSignatureTableMiss(block, signature_entry->signature,
182 initial_confidence, stride);
183
148 signatureTable.insertEntry(ppn, is_secure, signature_entry);
184 signatureTable.insertEntry(ppn, is_secure, signature_entry);
149 signature_entry->signature = block;
150 signature_entry->lastBlock = block;
151 miss = true;
152 }
185 miss = true;
186 }
187 signature_entry->lastBlock = block;
153 return *signature_entry;
154}
155
156SignaturePathPrefetcher::PatternEntry &
157SignaturePathPrefetcher::getPatternEntry(Addr signature)
158{
159 PatternEntry* pattern_entry = patternTable.findEntry(signature, false);
160 if (pattern_entry != nullptr) {

--- 4 unchanged lines hidden (view full) ---

165 pattern_entry = patternTable.findVictim(signature);
166 assert(pattern_entry != nullptr);
167
168 patternTable.insertEntry(signature, false, pattern_entry);
169 }
170 return *pattern_entry;
171}
172
188 return *signature_entry;
189}
190
191SignaturePathPrefetcher::PatternEntry &
192SignaturePathPrefetcher::getPatternEntry(Addr signature)
193{
194 PatternEntry* pattern_entry = patternTable.findEntry(signature, false);
195 if (pattern_entry != nullptr) {

--- 4 unchanged lines hidden (view full) ---

200 pattern_entry = patternTable.findVictim(signature);
201 assert(pattern_entry != nullptr);
202
203 patternTable.insertEntry(signature, false, pattern_entry);
204 }
205 return *pattern_entry;
206}
207
208double
209SignaturePathPrefetcher::calculatePrefetchConfidence(PatternEntry const &sig,
210 PatternStrideEntry const &entry) const
211{
212 return ((double) entry.counter) / maxCounterValue;
213}
214
215double
216SignaturePathPrefetcher::calculateLookaheadConfidence(PatternEntry const &sig,
217 PatternStrideEntry const &lookahead) const
218{
219 double lookahead_confidence;
220 if (lookahead.counter == maxCounterValue) {
221 /**
222 * maximum confidence is 0.95, guaranteeing that
223 * current confidence will eventually fall beyond
224 * the threshold
225 */
226 lookahead_confidence = 0.95;
227 } else {
228 lookahead_confidence = ((double) lookahead.counter / maxCounterValue);
229 }
230 return lookahead_confidence;
231}
232
173void
174SignaturePathPrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
175 std::vector<AddrPriority> &addresses)
176{
177 Addr request_addr = pfi.getAddr();
178 Addr ppn = request_addr / pageBytes;
179 stride_t current_block = (request_addr % pageBytes) / blkSize;
180 stride_t stride;
181 bool is_secure = pfi.isSecure();
233void
234SignaturePathPrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
235 std::vector<AddrPriority> &addresses)
236{
237 Addr request_addr = pfi.getAddr();
238 Addr ppn = request_addr / pageBytes;
239 stride_t current_block = (request_addr % pageBytes) / blkSize;
240 stride_t stride;
241 bool is_secure = pfi.isSecure();
242 double initial_confidence = 1.0;
182
183 // Get the SignatureEntry of this page to:
184 // - compute the current stride
185 // - obtain the current signature of accesses
186 bool miss;
187 SignatureEntry &signature_entry = getSignatureEntry(ppn, is_secure,
243
244 // Get the SignatureEntry of this page to:
245 // - compute the current stride
246 // - obtain the current signature of accesses
247 bool miss;
248 SignatureEntry &signature_entry = getSignatureEntry(ppn, is_secure,
188 current_block, miss);
249 current_block, miss, stride, initial_confidence);
250
189 if (miss) {
190 // No history for this page, can't continue
191 return;
192 }
193
251 if (miss) {
252 // No history for this page, can't continue
253 return;
254 }
255
194 stride = current_block - signature_entry.lastBlock;
195 if (stride == 0) {
196 // Can't continue with a stride 0
197 return;
198 }
199
200 // Update the confidence of the current signature
201 updatePatternTable(signature_entry.signature, stride);
202
256 if (stride == 0) {
257 // Can't continue with a stride 0
258 return;
259 }
260
261 // Update the confidence of the current signature
262 updatePatternTable(signature_entry.signature, stride);
263
203 // Update the current SignatureEntry signature and lastBlock
264 // Update the current SignatureEntry signature
204 signature_entry.signature =
205 updateSignature(signature_entry.signature, stride);
265 signature_entry.signature =
266 updateSignature(signature_entry.signature, stride);
206 signature_entry.lastBlock = current_block;
207
208 signature_t current_signature = signature_entry.signature;
267
268 signature_t current_signature = signature_entry.signature;
209 double current_confidence = 1.0;
269 double current_confidence = initial_confidence;
210 stride_t current_stride = signature_entry.lastBlock;
211
270 stride_t current_stride = signature_entry.lastBlock;
271
212 do {
272 // Look for prefetch candidates while the current path confidence is
273 // high enough
274 while (current_confidence > lookaheadConfidenceThreshold) {
213 // With the updated signature, attempt to generate prefetches
214 // - search the PatternTable and select all entries with enough
215 // confidence, these are prefetch candidates
216 // - select the entry with the highest counter as the "lookahead"
217 PatternEntry *current_pattern_entry =
218 patternTable.findEntry(current_signature, false);
219 PatternStrideEntry const *lookahead = nullptr;
220 if (current_pattern_entry != nullptr) {
221 uint8_t max_counter = 0;
222 for (auto const &entry : current_pattern_entry->strideEntries) {
223 //select the entry with the maximum counter value as lookahead
224 if (max_counter < entry.counter) {
225 max_counter = entry.counter;
226 lookahead = &entry;
227 }
228 double prefetch_confidence =
275 // With the updated signature, attempt to generate prefetches
276 // - search the PatternTable and select all entries with enough
277 // confidence, these are prefetch candidates
278 // - select the entry with the highest counter as the "lookahead"
279 PatternEntry *current_pattern_entry =
280 patternTable.findEntry(current_signature, false);
281 PatternStrideEntry const *lookahead = nullptr;
282 if (current_pattern_entry != nullptr) {
283 uint8_t max_counter = 0;
284 for (auto const &entry : current_pattern_entry->strideEntries) {
285 //select the entry with the maximum counter value as lookahead
286 if (max_counter < entry.counter) {
287 max_counter = entry.counter;
288 lookahead = &entry;
289 }
290 double prefetch_confidence =
229 (double) entry.counter / maxCounterValue;
291 calculatePrefetchConfidence(*current_pattern_entry, entry);
230
231 if (prefetch_confidence >= prefetchConfidenceThreshold) {
232 assert(entry.stride != 0);
233 //prefetch candidate
292
293 if (prefetch_confidence >= prefetchConfidenceThreshold) {
294 assert(entry.stride != 0);
295 //prefetch candidate
234 addPrefetch(ppn, current_stride + entry.stride,
235 is_secure, addresses);
296 addPrefetch(ppn, current_stride, entry.stride,
297 current_confidence, current_signature,
298 is_secure, addresses);
236 }
237 }
238 }
299 }
300 }
301 }
302
239 if (lookahead != nullptr) {
303 if (lookahead != nullptr) {
240 // If a lookahead was selected, compute its confidence using
241 // the counter of its entry and the accumulated confidence
242 // if the confidence is high enough, generate a new signature
243 double lookahead_confidence;
244 if (lookahead->counter == maxCounterValue) {
245 // maximum confidence is 0.95, guaranteeing that
246 // current confidence will eventually fall beyond
247 // the threshold
248 lookahead_confidence = 0.95;
249 } else {
250 lookahead_confidence =
251 ((double) lookahead->counter / maxCounterValue);
252 }
253 current_confidence *= lookahead_confidence;
304 current_confidence *= calculateLookaheadConfidence(
305 *current_pattern_entry, *lookahead);
254 current_signature =
255 updateSignature(current_signature, lookahead->stride);
256 current_stride += lookahead->stride;
257 } else {
258 current_confidence = 0.0;
259 }
306 current_signature =
307 updateSignature(current_signature, lookahead->stride);
308 current_stride += lookahead->stride;
309 } else {
310 current_confidence = 0.0;
311 }
260 // If the accumulated confidence is high enough, keep repeating
261 // this process with the updated signature
262 }
312 }
263 while (current_confidence > lookaheadConfidenceThreshold);
264
313
314 auxiliaryPrefetcher(ppn, current_block, is_secure, addresses);
315}
316
317void
318SignaturePathPrefetcher::auxiliaryPrefetcher(Addr ppn, stride_t current_block,
319 bool is_secure, std::vector<AddrPriority> &addresses)
320{
265 if (addresses.empty()) {
266 // Enable the next line prefetcher if no prefetch candidates are found
321 if (addresses.empty()) {
322 // Enable the next line prefetcher if no prefetch candidates are found
267 addPrefetch(ppn, current_block + 1, is_secure, addresses);
323 addPrefetch(ppn, current_block, 1, 0.0 /* unused*/, 0 /* unused */,
324 is_secure, addresses);
268 }
269}
270
271SignaturePathPrefetcher*
272SignaturePathPrefetcherParams::create()
273{
274 return new SignaturePathPrefetcher(this);
275}
325 }
326}
327
328SignaturePathPrefetcher*
329SignaturePathPrefetcherParams::create()
330{
331 return new SignaturePathPrefetcher(this);
332}