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_v2.hh"
32
33#include <cassert>
34
35#include "debug/HWPrefetch.hh"
36#include "mem/cache/prefetch/associative_set_impl.hh"
37#include "params/SignaturePathPrefetcherV2.hh"
38
39SignaturePathPrefetcherV2::SignaturePathPrefetcherV2(
40    const SignaturePathPrefetcherV2Params *p)
41    : SignaturePathPrefetcher(p),
42      globalHistoryRegister(p->global_history_register_entries,
43                            p->global_history_register_entries,
44                            p->global_history_register_indexing_policy,
45                            p->global_history_register_replacement_policy,
46                            GlobalHistoryEntry())
47{
48}
49
50void
51SignaturePathPrefetcherV2::handleSignatureTableMiss(stride_t current_block,
52    signature_t &new_signature, double &new_conf, stride_t &new_stride)
53{
54    bool found = false;
55
56    // This should return all entries of the GHR, since it is a fully
57    // associative table
58    std::vector<GlobalHistoryEntry *> all_ghr_entries =
59             globalHistoryRegister.getPossibleEntries(0 /* any value works */);
60
61    for (auto gh_entry : all_ghr_entries) {
62        if (gh_entry->lastBlock + gh_entry->delta == current_block) {
63            new_signature = gh_entry->signature;
64            new_conf = gh_entry->confidence;
65            new_stride = gh_entry->delta;
66            found = true;
67            globalHistoryRegister.accessEntry(gh_entry);
68            break;
69        }
70    }
71    if (!found) {
72        new_signature = current_block;
73        new_conf = 1.0;
74        new_stride = current_block;
75    }
76}
77
78double
79SignaturePathPrefetcherV2::calculateLookaheadConfidence(
80        PatternEntry const &sig, PatternStrideEntry const &lookahead) const
81{
82    if (sig.counter == 0) return 0.0;
83    return (((double) usefulPrefetches) / issuedPrefetches) *
84            (((double) lookahead.counter) / sig.counter);
85}
86
87double
88SignaturePathPrefetcherV2::calculatePrefetchConfidence(PatternEntry const &sig,
89        PatternStrideEntry const &entry) const
90{
91    if (sig.counter == 0) return 0.0;
92    return ((double) entry.counter) / sig.counter;
93}
94
95void
96SignaturePathPrefetcherV2::increasePatternEntryCounter(
97        PatternEntry &pattern_entry, PatternStrideEntry &pstride_entry)
98{
99    if (pattern_entry.counter.isSaturated()) {
100        pattern_entry.counter >>= 1;
101        for (auto &entry : pattern_entry.strideEntries) {
102            entry.counter >>= 1;
103        }
104    }
105    if (pstride_entry.counter.isSaturated()) {
106        pattern_entry.counter >>= 1;
107        for (auto &entry : pattern_entry.strideEntries) {
108            entry.counter >>= 1;
109        }
110    }
111    pattern_entry.counter++;
112    pstride_entry.counter++;
113}
114
115void
116SignaturePathPrefetcherV2::handlePageCrossingLookahead(signature_t signature,
117            stride_t last_offset, stride_t delta, double path_confidence)
118{
119    // Always use the replacement policy to assign new entries, as all
120    // of them are unique, there are never "hits" in the GHR
121    GlobalHistoryEntry *gh_entry = globalHistoryRegister.findVictim(0);
122    assert(gh_entry != nullptr);
123    // Any address value works, as it is never used
124    globalHistoryRegister.insertEntry(0, false, gh_entry);
125
126    gh_entry->signature = signature;
127    gh_entry->lastBlock = last_offset;
128    gh_entry->delta = delta;
129    gh_entry->confidence = path_confidence;
130}
131
132SignaturePathPrefetcherV2*
133SignaturePathPrefetcherV2Params::create()
134{
135    return new SignaturePathPrefetcherV2(this);
136}
137