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 Indirect Memory Prefetcher
33 *
34 * References:
35 * IMP: Indirect memory prefetcher.
36 * Yu, X., Hughes, C. J., Satish, N., & Devadas, S. (2015, December).
37 * In Proceedings of the 48th International Symposium on Microarchitecture
38 * (pp. 178-190). ACM.
39 */
40
41#ifndef __MEM_CACHE_PREFETCH_INDIRECT_MEMORY_HH__
42#define __MEM_CACHE_PREFETCH_INDIRECT_MEMORY_HH__
43
44#include <vector>
45
| 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 Indirect Memory Prefetcher
33 *
34 * References:
35 * IMP: Indirect memory prefetcher.
36 * Yu, X., Hughes, C. J., Satish, N., & Devadas, S. (2015, December).
37 * In Proceedings of the 48th International Symposium on Microarchitecture
38 * (pp. 178-190). ACM.
39 */
40
41#ifndef __MEM_CACHE_PREFETCH_INDIRECT_MEMORY_HH__
42#define __MEM_CACHE_PREFETCH_INDIRECT_MEMORY_HH__
43
44#include <vector>
45
|
| 46#include "base/sat_counter.hh"
|
46#include "mem/cache/prefetch/associative_set.hh"
47#include "mem/cache/prefetch/queued.hh"
48
49struct IndirectMemoryPrefetcherParams;
50
51class IndirectMemoryPrefetcher : public QueuedPrefetcher
52{
53 /** Maximum number of prefetches generated per event */
54 const unsigned int maxPrefetchDistance;
55 /** Shift values considered */
56 const std::vector<int> shiftValues;
57 /** Counter threshold to start prefetching */
58 const unsigned int prefetchThreshold;
| 47#include "mem/cache/prefetch/associative_set.hh"
48#include "mem/cache/prefetch/queued.hh"
49
50struct IndirectMemoryPrefetcherParams;
51
52class IndirectMemoryPrefetcher : public QueuedPrefetcher
53{
54 /** Maximum number of prefetches generated per event */
55 const unsigned int maxPrefetchDistance;
56 /** Shift values considered */
57 const std::vector<int> shiftValues;
58 /** Counter threshold to start prefetching */
59 const unsigned int prefetchThreshold;
|
59 /** Maximum value of the confidence indirectCounter */
60 const unsigned int maxIndirectCounterValue;
| |
61 /** streamCounter value to trigger the streaming prefetcher */
62 const int streamCounterThreshold;
63 /** Number of prefetches generated when using the streaming prefetcher */
64 const int streamingDistance;
65
66 /** Prefetch Table Entry */
67 struct PrefetchTableEntry : public TaggedEntry
68 {
69 /* Stream table fields */
70
71 /** Accessed address */
72 Addr address;
73 /** Whether this address is in the secure region */
74 bool secure;
75 /** Confidence counter of the stream */
76 unsigned int streamCounter;
77
78 /* Indirect table fields */
79
80 /** Enable bit of the indirect fields */
81 bool enabled;
82 /** Current index value */
83 int64_t index;
84 /** BaseAddr detected */
85 Addr baseAddr;
86 /** Shift detected */
87 int shift;
88 /** Confidence counter of the indirect fields */
| 60 /** streamCounter value to trigger the streaming prefetcher */
61 const int streamCounterThreshold;
62 /** Number of prefetches generated when using the streaming prefetcher */
63 const int streamingDistance;
64
65 /** Prefetch Table Entry */
66 struct PrefetchTableEntry : public TaggedEntry
67 {
68 /* Stream table fields */
69
70 /** Accessed address */
71 Addr address;
72 /** Whether this address is in the secure region */
73 bool secure;
74 /** Confidence counter of the stream */
75 unsigned int streamCounter;
76
77 /* Indirect table fields */
78
79 /** Enable bit of the indirect fields */
80 bool enabled;
81 /** Current index value */
82 int64_t index;
83 /** BaseAddr detected */
84 Addr baseAddr;
85 /** Shift detected */
86 int shift;
87 /** Confidence counter of the indirect fields */
|
89 int indirectCounter;
| 88 SatCounter indirectCounter;
|
90 /**
91 * This variable is set to indicate that there has been at least one
92 * match with the current index value. This information is later used
93 * when a new index is updated. If there were no increases in the
94 * indirectCounter, the counter is decremented.
95 */
96 bool increasedIndirectCounter;
97
| 89 /**
90 * This variable is set to indicate that there has been at least one
91 * match with the current index value. This information is later used
92 * when a new index is updated. If there were no increases in the
93 * indirectCounter, the counter is decremented.
94 */
95 bool increasedIndirectCounter;
96
|
98 PrefetchTableEntry() : TaggedEntry(), address(0), secure(false),
99 streamCounter(0), enabled(false), index(0), baseAddr(0), shift(0),
100 indirectCounter(0), increasedIndirectCounter(false)
| 97 PrefetchTableEntry(unsigned indirect_counter_bits)
98 : TaggedEntry(), address(0), secure(false), streamCounter(0),
99 enabled(false), index(0), baseAddr(0), shift(0),
100 indirectCounter(indirect_counter_bits),
101 increasedIndirectCounter(false)
|
101 {}
102
103 void reset() override {
104 address = 0;
105 secure = false;
106 streamCounter = 0;
107 enabled = false;
108 index = 0;
109 baseAddr = 0;
110 shift = 0;
| 102 {}
103
104 void reset() override {
105 address = 0;
106 secure = false;
107 streamCounter = 0;
108 enabled = false;
109 index = 0;
110 baseAddr = 0;
111 shift = 0;
|
111 indirectCounter = 0;
| 112 indirectCounter.reset();
|
112 increasedIndirectCounter = false;
113 }
114 };
115 /** Prefetch table */
116 AssociativeSet<PrefetchTableEntry> prefetchTable;
117
118 /** Indirect Pattern Detector entrt */
119 struct IndirectPatternDetectorEntry : public TaggedEntry
120 {
121 /** First index */
122 int64_t idx1;
123 /** Second index */
124 int64_t idx2;
125 /** Valid bit for the second index */
126 bool secondIndexSet;
127 /** Number of misses currently recorded */
128 int numMisses;
129 /**
130 * Potential BaseAddr candidates for each recorded miss.
131 * The number of candidates per miss is determined by the number of
132 * elements in the shiftValues array.
133 */
134 std::vector<std::vector<Addr>> baseAddr;
135
136 IndirectPatternDetectorEntry(unsigned int num_addresses,
137 unsigned int num_shifts)
138 : idx1(0), idx2(0), secondIndexSet(false), numMisses(0),
139 baseAddr(num_addresses, std::vector<Addr>(num_shifts))
140 {}
141
142 void reset() override {
143 idx1 = 0;
144 idx2 = 0;
145 secondIndexSet = false;
146 numMisses = 0;
147 setInvalid();
148 }
149 };
150 /** Indirect Pattern Detector (IPD) table */
151 AssociativeSet<IndirectPatternDetectorEntry> ipd;
152
153 /** Entry currently tracking misses */
154 IndirectPatternDetectorEntry *ipdEntryTrackingMisses;
155
156 /** Byte order used to access the cache */
157 const ByteOrder byteOrder;
158
159 /**
160 * Allocate or update an entry in the IPD
161 * @param pt_entry Pointer to the associated page table entry
162 * @param index Detected first index value
163 */
164 void allocateOrUpdateIPDEntry(const PrefetchTableEntry *pt_entry,
165 int64_t index);
166 /**
167 * Update an IPD entry with a detected miss address, when the first index
168 * is being tracked
169 * @param miss_addr The address that caused the miss
170 */
171 void trackMissIndex1(Addr miss_addr);
172
173 /**
174 * Update an IPD entry with a detected miss address, when the second index
175 * is being tracked
176 * @param miss_addr The address that caused the miss
177 */
178 void trackMissIndex2(Addr miss_addr);
179
180 /**
181 * Checks if an access to the cache matches any active PT entry, if so,
182 * the indirect confidence counter is incremented
183 * @param addr address of the access
184 */
185 void checkAccessMatchOnActiveEntries(Addr addr);
186
187 public:
188 IndirectMemoryPrefetcher(const IndirectMemoryPrefetcherParams *p);
189 ~IndirectMemoryPrefetcher() {}
190
191 void calculatePrefetch(const PrefetchInfo &pfi,
192 std::vector<AddrPriority> &addresses) override;
193};
194#endif//__MEM_CACHE_PREFETCH_INDIRECT_MEMORY_HH__
| 113 increasedIndirectCounter = false;
114 }
115 };
116 /** Prefetch table */
117 AssociativeSet<PrefetchTableEntry> prefetchTable;
118
119 /** Indirect Pattern Detector entrt */
120 struct IndirectPatternDetectorEntry : public TaggedEntry
121 {
122 /** First index */
123 int64_t idx1;
124 /** Second index */
125 int64_t idx2;
126 /** Valid bit for the second index */
127 bool secondIndexSet;
128 /** Number of misses currently recorded */
129 int numMisses;
130 /**
131 * Potential BaseAddr candidates for each recorded miss.
132 * The number of candidates per miss is determined by the number of
133 * elements in the shiftValues array.
134 */
135 std::vector<std::vector<Addr>> baseAddr;
136
137 IndirectPatternDetectorEntry(unsigned int num_addresses,
138 unsigned int num_shifts)
139 : idx1(0), idx2(0), secondIndexSet(false), numMisses(0),
140 baseAddr(num_addresses, std::vector<Addr>(num_shifts))
141 {}
142
143 void reset() override {
144 idx1 = 0;
145 idx2 = 0;
146 secondIndexSet = false;
147 numMisses = 0;
148 setInvalid();
149 }
150 };
151 /** Indirect Pattern Detector (IPD) table */
152 AssociativeSet<IndirectPatternDetectorEntry> ipd;
153
154 /** Entry currently tracking misses */
155 IndirectPatternDetectorEntry *ipdEntryTrackingMisses;
156
157 /** Byte order used to access the cache */
158 const ByteOrder byteOrder;
159
160 /**
161 * Allocate or update an entry in the IPD
162 * @param pt_entry Pointer to the associated page table entry
163 * @param index Detected first index value
164 */
165 void allocateOrUpdateIPDEntry(const PrefetchTableEntry *pt_entry,
166 int64_t index);
167 /**
168 * Update an IPD entry with a detected miss address, when the first index
169 * is being tracked
170 * @param miss_addr The address that caused the miss
171 */
172 void trackMissIndex1(Addr miss_addr);
173
174 /**
175 * Update an IPD entry with a detected miss address, when the second index
176 * is being tracked
177 * @param miss_addr The address that caused the miss
178 */
179 void trackMissIndex2(Addr miss_addr);
180
181 /**
182 * Checks if an access to the cache matches any active PT entry, if so,
183 * the indirect confidence counter is incremented
184 * @param addr address of the access
185 */
186 void checkAccessMatchOnActiveEntries(Addr addr);
187
188 public:
189 IndirectMemoryPrefetcher(const IndirectMemoryPrefetcherParams *p);
190 ~IndirectMemoryPrefetcher() {}
191
192 void calculatePrefetch(const PrefetchInfo &pfi,
193 std::vector<AddrPriority> &addresses) override;
194};
195#endif//__MEM_CACHE_PREFETCH_INDIRECT_MEMORY_HH__
|