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/signature_path.hh"
32
33#include <cassert>
34#include <climits>
35
36#include "debug/HWPrefetch.hh"
37#include "mem/cache/prefetch/associative_set_impl.hh"
38#include "params/SignaturePathPrefetcher.hh"
39
40SignaturePathPrefetcher::SignaturePathPrefetcher(
41    const SignaturePathPrefetcherParams *p)
42    : QueuedPrefetcher(p),
43      stridesPerPatternEntry(p->strides_per_pattern_entry),
44      signatureShift(p->signature_shift),
45      signatureBits(p->signature_bits),
46      prefetchConfidenceThreshold(p->prefetch_confidence_threshold),
47      lookaheadConfidenceThreshold(p->lookahead_confidence_threshold),
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, p->num_counter_bits))
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");
64}
65
66SignaturePathPrefetcher::PatternStrideEntry &
67SignaturePathPrefetcher::PatternEntry::getStrideEntry(stride_t stride)
68{
69    PatternStrideEntry *pstride_entry = findStride(stride);
70    if (pstride_entry == nullptr) {
71        // Specific replacement algorithm for this table,
72        // pick the entry with the lowest counter value,
73        // then decrease the counter of all entries
74
75        // If all counters have the max value, this will be the pick
76        PatternStrideEntry *victim_pstride_entry = &(strideEntries[0]);
77
78        unsigned long current_counter = ULONG_MAX;
79        for (auto &entry : strideEntries) {
80            if (entry.counter < current_counter) {
81                victim_pstride_entry = &entry;
82                current_counter = entry.counter;
83            }
84            entry.counter--;
85        }
86        pstride_entry = victim_pstride_entry;
87        pstride_entry->counter.reset();
88        pstride_entry->stride = stride;
89    }
90    return *pstride_entry;
91}
92
93void
94SignaturePathPrefetcher::addPrefetch(Addr ppn, stride_t last_block,
95    stride_t delta, double path_confidence, signature_t signature,
96    bool is_secure, std::vector<AddrPriority> &addresses)
97{
98    stride_t block = last_block + delta;
99
100    Addr pf_ppn;
101    stride_t pf_block;
102    if (block < 0) {
103        stride_t num_cross_pages = 1 + (-block) / (pageBytes/blkSize);
104        if (num_cross_pages > ppn) {
105            // target address smaller than page 0, ignore this request;
106            return;
107        }
108        pf_ppn = ppn - num_cross_pages;
109        pf_block = block + (pageBytes/blkSize) * num_cross_pages;
110        handlePageCrossingLookahead(signature, last_block, delta,
111                                    path_confidence);
112    } else if (block >= (pageBytes/blkSize)) {
113        stride_t num_cross_pages = block / (pageBytes/blkSize);
114        if (MaxAddr/pageBytes < (ppn + num_cross_pages)) {
115            // target address goes beyond MaxAddr, ignore this request;
116            return;
117        }
118        pf_ppn = ppn + num_cross_pages;
119        pf_block = block - (pageBytes/blkSize) * num_cross_pages;
120        handlePageCrossingLookahead(signature, last_block, delta,
121                                    path_confidence);
122    } else {
123        pf_ppn = ppn;
124        pf_block = block;
125    }
126
127    Addr new_addr = pf_ppn * pageBytes;
128    new_addr += pf_block * (Addr)blkSize;
129
130    DPRINTF(HWPrefetch, "Queuing prefetch to %#x.\n", new_addr);
131    addresses.push_back(AddrPriority(new_addr, 0));
132}
133
134void
135SignaturePathPrefetcher::handleSignatureTableMiss(stride_t current_block,
136    signature_t &new_signature, double &new_conf, stride_t &new_stride)
137{
138    new_signature = current_block;
139    new_conf = 1.0;
140    new_stride = current_block;
141}
142
143void
144SignaturePathPrefetcher::increasePatternEntryCounter(
145        PatternEntry &pattern_entry, PatternStrideEntry &pstride_entry)
146{
147    pstride_entry.counter++;
148}
149
150void
151SignaturePathPrefetcher::updatePatternTable(Addr signature, stride_t stride)
152{
153    assert(stride != 0);
154    // The pattern table is indexed by signatures
155    PatternEntry &p_entry = getPatternEntry(signature);
156    PatternStrideEntry &ps_entry = p_entry.getStrideEntry(stride);
157    increasePatternEntryCounter(p_entry, ps_entry);
158}
159
160SignaturePathPrefetcher::SignatureEntry &
161SignaturePathPrefetcher::getSignatureEntry(Addr ppn, bool is_secure,
162        stride_t block, bool &miss, stride_t &stride,
163        double &initial_confidence)
164{
165    SignatureEntry* signature_entry = signatureTable.findEntry(ppn, is_secure);
166    if (signature_entry != nullptr) {
167        signatureTable.accessEntry(signature_entry);
168        miss = false;
169        stride = block - signature_entry->lastBlock;
170    } else {
171        signature_entry = signatureTable.findVictim(ppn);
172        assert(signature_entry != nullptr);
173
174        // Sets signature_entry->signature, initial_confidence, and stride
175        handleSignatureTableMiss(block, signature_entry->signature,
176            initial_confidence, stride);
177
178        signatureTable.insertEntry(ppn, is_secure, signature_entry);
179        miss = true;
180    }
181    signature_entry->lastBlock = block;
182    return *signature_entry;
183}
184
185SignaturePathPrefetcher::PatternEntry &
186SignaturePathPrefetcher::getPatternEntry(Addr signature)
187{
188    PatternEntry* pattern_entry = patternTable.findEntry(signature, false);
189    if (pattern_entry != nullptr) {
190        // Signature found
191        patternTable.accessEntry(pattern_entry);
192    } else {
193        // Signature not found
194        pattern_entry = patternTable.findVictim(signature);
195        assert(pattern_entry != nullptr);
196
197        patternTable.insertEntry(signature, false, pattern_entry);
198    }
199    return *pattern_entry;
200}
201
202double
203SignaturePathPrefetcher::calculatePrefetchConfidence(PatternEntry const &sig,
204        PatternStrideEntry const &entry) const
205{
206    return entry.counter.calcSaturation();
207}
208
209double
210SignaturePathPrefetcher::calculateLookaheadConfidence(PatternEntry const &sig,
211        PatternStrideEntry const &lookahead) const
212{
213    double lookahead_confidence = lookahead.counter.calcSaturation();
214    if (lookahead_confidence > 0.95) {
215        /**
216         * maximum confidence is 0.95, guaranteeing that
217         * current confidence will eventually fall beyond
218         * the threshold
219         */
220        lookahead_confidence = 0.95;
221    }
222    return lookahead_confidence;
223}
224
225void
226SignaturePathPrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
227                                 std::vector<AddrPriority> &addresses)
228{
229    Addr request_addr = pfi.getAddr();
230    Addr ppn = request_addr / pageBytes;
231    stride_t current_block = (request_addr % pageBytes) / blkSize;
232    stride_t stride;
233    bool is_secure = pfi.isSecure();
234    double initial_confidence = 1.0;
235
236    // Get the SignatureEntry of this page to:
237    // - compute the current stride
238    // - obtain the current signature of accesses
239    bool miss;
240    SignatureEntry &signature_entry = getSignatureEntry(ppn, is_secure,
241            current_block, miss, stride, initial_confidence);
242
243    if (miss) {
244        // No history for this page, can't continue
245        return;
246    }
247
248    if (stride == 0) {
249        // Can't continue with a stride 0
250        return;
251    }
252
253    // Update the confidence of the current signature
254    updatePatternTable(signature_entry.signature, stride);
255
256    // Update the current SignatureEntry signature
257    signature_entry.signature =
258        updateSignature(signature_entry.signature, stride);
259
260    signature_t current_signature = signature_entry.signature;
261    double current_confidence = initial_confidence;
262    stride_t current_stride = signature_entry.lastBlock;
263
264    // Look for prefetch candidates while the current path confidence is
265    // high enough
266    while (current_confidence > lookaheadConfidenceThreshold) {
267        // With the updated signature, attempt to generate prefetches
268        // - search the PatternTable and select all entries with enough
269        //   confidence, these are prefetch candidates
270        // - select the entry with the highest counter as the "lookahead"
271        PatternEntry *current_pattern_entry =
272            patternTable.findEntry(current_signature, false);
273        PatternStrideEntry const *lookahead = nullptr;
274        if (current_pattern_entry != nullptr) {
275            unsigned long max_counter = 0;
276            for (auto const &entry : current_pattern_entry->strideEntries) {
277                //select the entry with the maximum counter value as lookahead
278                if (max_counter < entry.counter) {
279                    max_counter = entry.counter;
280                    lookahead = &entry;
281                }
282                double prefetch_confidence =
283                    calculatePrefetchConfidence(*current_pattern_entry, entry);
284
285                if (prefetch_confidence >= prefetchConfidenceThreshold) {
286                    assert(entry.stride != 0);
287                    //prefetch candidate
288                    addPrefetch(ppn, current_stride, entry.stride,
289                                current_confidence, current_signature,
290                                is_secure, addresses);
291                }
292            }
293        }
294
295        if (lookahead != nullptr) {
296            current_confidence *= calculateLookaheadConfidence(
297                    *current_pattern_entry, *lookahead);
298            current_signature =
299                updateSignature(current_signature, lookahead->stride);
300            current_stride += lookahead->stride;
301        } else {
302            current_confidence = 0.0;
303        }
304    }
305
306    auxiliaryPrefetcher(ppn, current_block, is_secure, addresses);
307}
308
309void
310SignaturePathPrefetcher::auxiliaryPrefetcher(Addr ppn, stride_t current_block,
311        bool is_secure, std::vector<AddrPriority> &addresses)
312{
313    if (addresses.empty()) {
314        // Enable the next line prefetcher if no prefetch candidates are found
315        addPrefetch(ppn, current_block, 1, 0.0 /* unused*/, 0 /* unused */,
316                    is_secure, addresses);
317    }
318}
319
320SignaturePathPrefetcher*
321SignaturePathPrefetcherParams::create()
322{
323    return new SignaturePathPrefetcher(this);
324}
325