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