signature_path.cc revision 13553:047def1fa787 
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
35#include "debug/HWPrefetch.hh"
36#include "mem/cache/prefetch/associative_set_impl.hh"
37#include "params/SignaturePathPrefetcher.hh"
38
39SignaturePathPrefetcher::SignaturePathPrefetcher(
40    const SignaturePathPrefetcherParams *p)
41    : QueuedPrefetcher(p),
42      stridesPerPatternEntry(p->strides_per_pattern_entry),
43      signatureShift(p->signature_shift),
44      signatureBits(p->signature_bits),
45      maxCounterValue(p->max_counter_value),
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))
55{
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) {
64        // Specific replacement algorithm for this table,
65        // pick the entry with the lowest counter value,
66        // then decrease the counter of all entries
67
68        // If all counters have the max value, this will be the pick
69        PatternStrideEntry *victim_pstride_entry = &(strideEntries[0]);
70
71        uint8_t current_counter = max_counter_value;
72        for (auto &entry : strideEntries) {
73            if (entry.counter < current_counter) {
74                victim_pstride_entry = &entry;
75                current_counter = entry.counter;
76            }
77            if (entry.counter > 0) {
78                entry.counter -= 1;
79            }
80        }
81        pstride_entry = victim_pstride_entry;
82        pstride_entry->counter = 0;
83        pstride_entry->stride = stride;
84    }
85    return *pstride_entry;
86}
87
88void
89SignaturePathPrefetcher::addPrefetch(Addr ppn, stride_t block,
90    bool is_secure, std::vector<AddrPriority> &addresses)
91{
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)));
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);
108    } else if (block >= (pageBytes/blkSize)) {
109        pf_ppn = ppn + 1;
110        pf_block = block - (pageBytes/blkSize);
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
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);
131    if (ps_entry.counter < maxCounterValue) {
132        ps_entry.counter += 1;
133    }
134}
135
136SignaturePathPrefetcher::SignatureEntry &
137SignaturePathPrefetcher::getSignatureEntry(Addr ppn, bool is_secure,
138                                           stride_t block, bool &miss)
139{
140    SignatureEntry* signature_entry = signatureTable.findEntry(ppn, is_secure);
141    if (signature_entry != nullptr) {
142        signatureTable.accessEntry(signature_entry);
143        miss = false;
144    } else {
145        signature_entry = signatureTable.findVictim(ppn);
146        assert(signature_entry != nullptr);
147
148        signatureTable.insertEntry(ppn, is_secure, signature_entry);
149        signature_entry->signature = block;
150        signature_entry->lastBlock = block;
151        miss = true;
152    }
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) {
161        // Signature found
162        patternTable.accessEntry(pattern_entry);
163    } else {
164        // Signature not found
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
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();
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,
188                                                        current_block, miss);
189    if (miss) {
190        // No history for this page, can't continue
191        return;
192    }
193
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
203    // Update the current SignatureEntry signature and lastBlock
204    signature_entry.signature =
205        updateSignature(signature_entry.signature, stride);
206    signature_entry.lastBlock = current_block;
207
208    signature_t current_signature = signature_entry.signature;
209    double current_confidence = 1.0;
210    stride_t current_stride = signature_entry.lastBlock;
211
212    do {
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 =
229                    (double) entry.counter / maxCounterValue;
230
231                if (prefetch_confidence >= prefetchConfidenceThreshold) {
232                    assert(entry.stride != 0);
233                    //prefetch candidate
234                    addPrefetch(ppn, current_stride + entry.stride,
235                                         is_secure, addresses);
236                }
237            }
238        }
239        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;
254            current_signature =
255                updateSignature(current_signature, lookahead->stride);
256            current_stride += lookahead->stride;
257        } else {
258            current_confidence = 0.0;
259        }
260        // If the accumulated confidence is high enough, keep repeating
261        // this process with the updated signature
262    }
263    while (current_confidence > lookaheadConfidenceThreshold);
264
265    if (addresses.empty()) {
266        // Enable the next line prefetcher if no prefetch candidates are found
267        addPrefetch(ppn, current_block + 1, is_secure, addresses);
268    }
269}
270
271SignaturePathPrefetcher*
272SignaturePathPrefetcherParams::create()
273{
274    return new SignaturePathPrefetcher(this);
275}
276