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 /**
32 * Implementation of the Signature Path Prefetcher
33 *
34 * References:
35 * Lookahead prefetching with signature path
36 * J Kim, PV Gratz, ALN Reddy
37 * The 2nd Data Prefetching Championship (DPC2)
38 * The filter feature described in the paper is not implemented, as it
39 * redundant prefetches are dropped by the cache.
40 */
41
42#ifndef __MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__
43#define __MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__
44
45#include "mem/cache/prefetch/associative_set.hh"
46#include "mem/cache/prefetch/queued.hh"
47#include "mem/packet.hh"
48
49struct SignaturePathPrefetcherParams;
50
51class SignaturePathPrefetcher : public QueuedPrefetcher
52{
53 /** Signature type */
54 typedef uint16_t signature_t;
55 /** Stride type */
56 typedef int16_t stride_t;
57
58 /** Number of strides stored in each pattern entry */
59 const unsigned stridesPerPatternEntry;
60 /** Number of bits to shift when generating a new signature */
61 const uint8_t signatureShift;
62 /** Size of the signature, in bits */
63 const signature_t signatureBits;
64 /** Maximum pattern entries counter value */
65 const uint8_t maxCounterValue;
66 /** Minimum confidence to issue a prefetch */
67 const double prefetchConfidenceThreshold;
68 /** Minimum confidence to keep navigating lookahead entries */
69 const double lookaheadConfidenceThreshold;
70
71 /** Signature entry data type */
72 struct SignatureEntry : public TaggedEntry
73 {
74 /** Path signature */
75 signature_t signature;
76 /** Last accessed block within a page */
77 stride_t lastBlock;
78 SignatureEntry() : signature(0), lastBlock(0)
79 {}
80 };
81 /** Signature table */
82 AssociativeSet<SignatureEntry> signatureTable;
83
84 /** A stride entry with its counter */
85 struct PatternStrideEntry
86 {
87 /** stride in a page in blkSize increments */
88 stride_t stride;
89 /** counter value (max value defined by maxCounterValue) */
90 uint8_t counter;
91 PatternStrideEntry() : stride(0), counter(0)
92 {}
93 };
94 /** Pattern entry data type, a set of stride and counter entries */
95 struct PatternEntry : public TaggedEntry
96 {
97 /** group of stides */
98 std::vector<PatternStrideEntry> strideEntries;
99 PatternEntry(size_t num_strides) : strideEntries(num_strides)
100 {}
101
102 /** Reset the entries to their initial values */
103 void reset() override
104 {
105 for (auto &entry : strideEntries) {
106 entry.counter = 0;
107 entry.stride = 0;
108 }
109 }
110
111 /**
112 * Returns the entry with the desired stride
113 * @param stride the stride to find
114 * @result a pointer to the entry, if the stride was found, or nullptr,
115 * if the stride was not found
116 */
117 PatternStrideEntry *findStride(stride_t stride)
118 {
119 PatternStrideEntry *found_entry = nullptr;
120 for (auto &entry : strideEntries) {
121 if (entry.stride == stride) {
122 found_entry = &entry;
123 break;
124 }
125 }
126 return found_entry;
127 }
128
129 /**
130 * Gets the entry with the provided stride, if there is no entry with
131 * the associated stride, it replaces one of them.
132 * @param stride the stride to find
133 * @param max_counter_value maximum value of the confidence counters,
134 * it is used when no strides are found and an entry needs to be
135 * replaced
136 * @result reference to the selected entry
137 */
138 PatternStrideEntry &getStrideEntry(stride_t stride,
139 uint8_t max_counter_value);
140 };
141 /** Pattern table */
142 AssociativeSet<PatternEntry> patternTable;
143
144 /**
145 * Generates a new signature from an existing one and a new stride
146 * @param sig current signature
147 * @param str stride to add to the new signature
148 * @result the new signature
149 */
150 inline signature_t updateSignature(signature_t sig, stride_t str) const {
151 sig <<= signatureShift;
152 sig ^= str;
153 sig &= mask(signatureBits);
154 return sig;
155 }
156
157 /**
158 * Generates an address to be prefetched.
159 * @param ppn page number to prefetch from
160 * @param block block number within the page, this value can be negative,
161 * which means that the block refered is actualy in the previous
162 * page (ppn-1), if the value is greater than (pageBytes/blkSize-1)
163 * then the block refers to a block within the next page (ppn+1)
164 * @param is_secure whether this page is inside the secure memory area
165 * @param addresses if allowed, the address will be added to this vector
166 */
167 void addPrefetch(Addr ppn, stride_t block, bool is_secure,
168 std::vector<AddrPriority> &addresses);
169
170 /**
171 * Obtains the SignatureEntry of the given page, if the page is not found,
172 * it allocates a new one, replacing an existing entry if needed
173 * @param ppn physical page number of the page
174 * @param is_secure whether this page is inside the secure memory area
175 * @param block accessed block within the page
176 * @param miss output, if the entry is not found, this will be set to true
177 * @result a reference to the SignatureEntry
178 */
179 SignatureEntry & getSignatureEntry(Addr ppn, bool is_secure,
180 stride_t block, bool &miss);
181 /**
182 * Obtains the PatternEntry of the given signature, if the signature is
183 * not found, it allocates a new one, replacing an existing entry if needed
184 * @param signature the signature of the desired entry
185 * @result a reference to the PatternEntry
186 */
187 PatternEntry & getPatternEntry(Addr signature);
188
189 /**
190 * Updates the pattern table with the provided signature and stride
191 * @param signature the signature to use to index the pattern table
192 * @param stride the stride to use to index the set of strides of the
193 * pattern table entry
194 */
195 void updatePatternTable(Addr signature, stride_t stride);
196
197 public:
198 SignaturePathPrefetcher(const SignaturePathPrefetcherParams* p);
199 ~SignaturePathPrefetcher() {}
200 void calculatePrefetch(const PrefetchInfo &pfi,
201 std::vector<AddrPriority> &addresses) override;
202};
203
204#endif//__MEM_CACHE_PREFETCH_SIGNATURE_PATH_HH__