signature_path.cc revision 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;
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    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                                                     uint8_t max_counter_value)
69{
70    PatternStrideEntry *pstride_entry = findStride(stride);
71    if (pstride_entry == nullptr) {
72        // Specific replacement algorithm for this table,
73        // pick the entry with the lowest counter value,
74        // then decrease the counter of all entries
75
76        // If all counters have the max value, this will be the pick
77        PatternStrideEntry *victim_pstride_entry = &(strideEntries[0]);
78
79        uint8_t current_counter = max_counter_value;
80        for (auto &entry : strideEntries) {
81            if (entry.counter < current_counter) {
82                victim_pstride_entry = &entry;
83                current_counter = entry.counter;
84            }
85            if (entry.counter > 0) {
86                entry.counter -= 1;
87            }
88        }
89        pstride_entry = victim_pstride_entry;
90        pstride_entry->counter = 0;
91        pstride_entry->stride = stride;
92    }
93    return *pstride_entry;
94}
95
96void
97SignaturePathPrefetcher::addPrefetch(Addr ppn, stride_t last_block,
98    stride_t delta, double path_confidence, signature_t signature,
99    bool is_secure, std::vector<AddrPriority> &addresses)
100{
101    stride_t block = last_block + delta;
102
103    Addr pf_ppn;
104    stride_t pf_block;
105    if (block < 0) {
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);
115    } else if (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);
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
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);
163    increasePatternEntryCounter(p_entry, ps_entry);
164}
165
166SignaturePathPrefetcher::SignatureEntry &
167SignaturePathPrefetcher::getSignatureEntry(Addr ppn, bool is_secure,
168        stride_t block, bool &miss, stride_t &stride,
169        double &initial_confidence)
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;
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
184        signatureTable.insertEntry(ppn, is_secure, signature_entry);
185        miss = true;
186    }
187    signature_entry->lastBlock = block;
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) {
196        // Signature found
197        patternTable.accessEntry(pattern_entry);
198    } else {
199        // Signature not found
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
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;
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,
249            current_block, miss, stride, initial_confidence);
250
251    if (miss) {
252        // No history for this page, can't continue
253        return;
254    }
255
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
264    // Update the current SignatureEntry signature
265    signature_entry.signature =
266        updateSignature(signature_entry.signature, stride);
267
268    signature_t current_signature = signature_entry.signature;
269    double current_confidence = initial_confidence;
270    stride_t current_stride = signature_entry.lastBlock;
271
272    // Look for prefetch candidates while the current path confidence is
273    // high enough
274    while (current_confidence > lookaheadConfidenceThreshold) {
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 =
291                    calculatePrefetchConfidence(*current_pattern_entry, entry);
292
293                if (prefetch_confidence >= prefetchConfidenceThreshold) {
294                    assert(entry.stride != 0);
295                    //prefetch candidate
296                    addPrefetch(ppn, current_stride, entry.stride,
297                                current_confidence, current_signature,
298                                is_secure, addresses);
299                }
300            }
301        }
302
303        if (lookahead != nullptr) {
304            current_confidence *= calculateLookaheadConfidence(
305                    *current_pattern_entry, *lookahead);
306            current_signature =
307                updateSignature(current_signature, lookahead->stride);
308            current_stride += lookahead->stride;
309        } else {
310            current_confidence = 0.0;
311        }
312    }
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{
321    if (addresses.empty()) {
322        // Enable the next line prefetcher if no prefetch candidates are found
323        addPrefetch(ppn, current_block, 1, 0.0 /* unused*/, 0 /* unused */,
324                    is_secure, addresses);
325    }
326}
327
328SignaturePathPrefetcher*
329SignaturePathPrefetcherParams::create()
330{
331    return new SignaturePathPrefetcher(this);
332}
333