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 Access Map Pattern Matching Prefetcher
33 *
34 * References:
35 * Access map pattern matching for high performance data cache prefetch.
36 * Ishii, Y., Inaba, M., & Hiraki, K. (2011).
37 * Journal of Instruction-Level Parallelism, 13, 1-24.
38 */
39
40#ifndef __MEM_CACHE_PREFETCH_ACCESS_MAP_PATTERN_MATCHING_HH__
41#define __MEM_CACHE_PREFETCH_ACCESS_MAP_PATTERN_MATCHING_HH__
42
43#include "mem/cache/base.hh"
44#include "mem/cache/prefetch/associative_set.hh"
45#include "mem/cache/prefetch/queued.hh"
46#include "mem/packet.hh"
|
| 47#include "sim/clocked_object.hh" |
48
|
48struct AccessMapPatternMatchingPrefetcherParams;
|
| 49struct AccessMapPatternMatchingParams; |
50
|
50class AccessMapPatternMatchingPrefetcher : public QueuedPrefetcher
|
| 51class AccessMapPatternMatching : public ClockedObject |
52{
|
53 /** Cacheline size used by the prefetcher using this object */
54 const unsigned blkSize;
55 /** Limit the stride checking to -limitStride/+limitStride */
56 const unsigned limitStride; |
57 /** Maximum number of prefetch generated */
58 const unsigned startDegree;
59 /** Amount of memory covered by a hot zone */
60 const uint64_t hotZoneSize;
61 /** A prefetch coverage factor bigger than this is considered high */
62 const double highCoverageThreshold;
63 /** A prefetch coverage factor smaller than this is considered low */
64 const double lowCoverageThreshold;
65 /** A prefetch accuracy factor bigger than this is considered high */
66 const double highAccuracyThreshold;
67 /** A prefetch accuracy factor smaller than this is considered low */
68 const double lowAccuracyThreshold;
69 /** A cache hit ratio bigger than this is considered high */
70 const double highCacheHitThreshold;
71 /** A cache hit ratio smaller than this is considered low */
72 const double lowCacheHitThreshold;
73 /** Cycles in an epoch period */
74 const Cycles epochCycles;
75 /** Off chip memory latency to use for the epoch bandwidth calculation */
76 const Tick offChipMemoryLatency;
77
78 /** Data type representing the state of a cacheline in the access map */
79 enum AccessMapState
80 {
81 AM_INIT,
82 AM_PREFETCH,
83 AM_ACCESS,
84 AM_INVALID
85 };
86
87 /** AccessMapEntry data type */
88 struct AccessMapEntry : public TaggedEntry
89 {
90 /** vector containing the state of the cachelines in this zone */
91 std::vector<AccessMapState> states;
92
93 AccessMapEntry(size_t num_entries) : states(num_entries, AM_INIT)
94 {}
95
96 /** Reset the entries to their initial values */
97 void reset() override
98 {
99 for (auto &entry : states) {
100 entry = AM_INIT;
101 }
102 }
103 };
104 /** Access map table */
105 AssociativeSet<AccessMapEntry> accessMapTable;
106
107 /**
108 * Number of good prefetches
109 * - State transitions from PREFETCH to ACCESS
110 */
111 uint64_t numGoodPrefetches;
112 /**
113 * Number of prefetches issued
114 * - State transitions from INIT to PREFETCH
115 */
116 uint64_t numTotalPrefetches;
117 /**
118 * Number of raw cache misses
119 * - State transitions from INIT or PREFETCH to ACCESS
120 */
121 uint64_t numRawCacheMisses;
122 /**
123 * Number of raw cache hits
124 * - State transitions from ACCESS to ACCESS
125 */
126 uint64_t numRawCacheHits;
127 /** Current degree */
128 unsigned degree;
129 /** Current useful degree */
130 unsigned usefulDegree;
131
132 /**
133 * Given a target cacheline, this function checks if the cachelines
134 * that follow the provided stride have been accessed. If so, the line
135 * is considered a good candidate.
136 * @param states vector containing the states of three contiguous hot zones
137 * @param current target block (cacheline)
138 * @param stride access stride to obtain the reference cachelines
139 * @return true if current is a prefetch candidate
140 */
141 inline bool checkCandidate(std::vector<AccessMapState> const &states,
142 Addr current, int stride) const
143 {
144 enum AccessMapState tgt = states[current - stride];
145 enum AccessMapState s = states[current + stride];
146 enum AccessMapState s2 = states[current + 2 * stride];
147 enum AccessMapState s2_p1 = states[current + 2 * stride + 1];
148 return (tgt != AM_INVALID &&
149 ((s == AM_ACCESS && s2 == AM_ACCESS) ||
150 (s == AM_ACCESS && s2_p1 == AM_ACCESS)));
151 }
152
153 /**
154 * Obtain an AccessMapEntry from the AccessMapTable, if the entry is not
155 * found a new one is initialized and inserted.
156 * @param am_addr address of the hot zone
157 * @param is_secure whether the address belongs to the secure memory area
158 * @return the corresponding entry
159 */
160 AccessMapEntry *getAccessMapEntry(Addr am_addr, bool is_secure);
161
162 /**
163 * Updates the state of a block within an AccessMapEntry, also updates
164 * the prefetcher metrics.
165 * @param entry AccessMapEntry to update
166 * @param block cacheline within the hot zone
167 * @param state new state
168 */
169 void setEntryState(AccessMapEntry &entry, Addr block,
170 enum AccessMapState state);
171
172 /**
173 * This event constitues the epoch of the statistics that keep track of
174 * the prefetcher accuracy, when this event triggers, the prefetcher degree
175 * is adjusted and the statistics counters are reset.
176 */
177 void processEpochEvent();
178 EventFunctionWrapper epochEvent;
179
180 public:
|
176 AccessMapPatternMatchingPrefetcher(
177 const AccessMapPatternMatchingPrefetcherParams* p);
178 ~AccessMapPatternMatchingPrefetcher() {}
|
181 AccessMapPatternMatching(const AccessMapPatternMatchingParams* p);
182 ~AccessMapPatternMatching()
183 {}
184 void calculatePrefetch(const BasePrefetcher::PrefetchInfo &pfi,
185 std::vector<QueuedPrefetcher::AddrPriority> &addresses);
186};
187
188struct AMPMPrefetcherParams;
189
190class AMPMPrefetcher : public QueuedPrefetcher
191{
192 AccessMapPatternMatching &m;
193 public:
194 AMPMPrefetcher(const AMPMPrefetcherParams* p);
195 ~AMPMPrefetcher()
196 {} |
197 void calculatePrefetch(const PrefetchInfo &pfi,
198 std::vector<AddrPriority> &addresses) override;
199};
200#endif//__MEM_CACHE_PREFETCH_ACCESS_MAP_PATTERN_MATCHING_HH__
|