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/irregular_stream_buffer.hh"
32
33#include "debug/HWPrefetch.hh"
34#include "mem/cache/prefetch/associative_set_impl.hh"
35#include "params/IrregularStreamBufferPrefetcher.hh"
36
37IrregularStreamBufferPrefetcher::IrregularStreamBufferPrefetcher(
38 const IrregularStreamBufferPrefetcherParams *p)
| 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/irregular_stream_buffer.hh"
32
33#include "debug/HWPrefetch.hh"
34#include "mem/cache/prefetch/associative_set_impl.hh"
35#include "params/IrregularStreamBufferPrefetcher.hh"
36
37IrregularStreamBufferPrefetcher::IrregularStreamBufferPrefetcher(
38 const IrregularStreamBufferPrefetcherParams *p)
|
39 : QueuedPrefetcher(p), maxCounterValue(p->max_counter_value),
| 39 : QueuedPrefetcher(p),
|
40 chunkSize(p->chunk_size),
41 prefetchCandidatesPerEntry(p->prefetch_candidates_per_entry),
42 degree(p->degree),
43 trainingUnit(p->training_unit_assoc, p->training_unit_entries,
44 p->training_unit_indexing_policy,
45 p->training_unit_replacement_policy),
46 psAddressMappingCache(p->address_map_cache_assoc,
47 p->address_map_cache_entries,
48 p->ps_address_map_cache_indexing_policy,
49 p->ps_address_map_cache_replacement_policy,
| 40 chunkSize(p->chunk_size),
41 prefetchCandidatesPerEntry(p->prefetch_candidates_per_entry),
42 degree(p->degree),
43 trainingUnit(p->training_unit_assoc, p->training_unit_entries,
44 p->training_unit_indexing_policy,
45 p->training_unit_replacement_policy),
46 psAddressMappingCache(p->address_map_cache_assoc,
47 p->address_map_cache_entries,
48 p->ps_address_map_cache_indexing_policy,
49 p->ps_address_map_cache_replacement_policy,
|
50 AddressMappingEntry(prefetchCandidatesPerEntry)),
| 50 AddressMappingEntry(prefetchCandidatesPerEntry,
51 p->num_counter_bits)),
|
51 spAddressMappingCache(p->address_map_cache_assoc,
52 p->address_map_cache_entries,
53 p->sp_address_map_cache_indexing_policy,
54 p->sp_address_map_cache_replacement_policy,
| 52 spAddressMappingCache(p->address_map_cache_assoc,
53 p->address_map_cache_entries,
54 p->sp_address_map_cache_indexing_policy,
55 p->sp_address_map_cache_replacement_policy,
|
55 AddressMappingEntry(prefetchCandidatesPerEntry)),
| 56 AddressMappingEntry(prefetchCandidatesPerEntry,
57 p->num_counter_bits)),
|
56 structuralAddressCounter(0)
57{
58 assert(isPowerOf2(prefetchCandidatesPerEntry));
59}
60
61void
62IrregularStreamBufferPrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
63 std::vector<AddrPriority> &addresses)
64{
65 // This prefetcher requires a PC
66 if (!pfi.hasPC()) {
67 return;
68 }
69 bool is_secure = pfi.isSecure();
70 Addr pc = pfi.getPC();
71 Addr addr = blockIndex(pfi.getAddr());
72
73 // Training, if the entry exists, then we found a correlation between
74 // the entry lastAddress (named as correlated_addr_A) and the address of
75 // the current access (named as correlated_addr_B)
76 TrainingUnitEntry *entry = trainingUnit.findEntry(pc, is_secure);
77 bool correlated_addr_found = false;
78 Addr correlated_addr_A = 0;
79 Addr correlated_addr_B = 0;
80 if (entry != nullptr && entry->lastAddressSecure == is_secure) {
81 trainingUnit.accessEntry(entry);
82 correlated_addr_found = true;
83 correlated_addr_A = entry->lastAddress;
84 correlated_addr_B = addr;
85 } else {
86 entry = trainingUnit.findVictim(pc);
87 assert(entry != nullptr);
88
89 trainingUnit.insertEntry(pc, is_secure, entry);
90 }
91 // Update the entry
92 entry->lastAddress = addr;
93 entry->lastAddressSecure = is_secure;
94
95 if (correlated_addr_found) {
96 // If a correlation was found, update the Physical-to-Structural
97 // table accordingly
98 AddressMapping &mapping_A = getPSMapping(correlated_addr_A, is_secure);
99 AddressMapping &mapping_B = getPSMapping(correlated_addr_B, is_secure);
100 if (mapping_A.counter > 0 && mapping_B.counter > 0) {
101 // Entry for A and B
102 if (mapping_B.address == (mapping_A.address + 1)) {
| 58 structuralAddressCounter(0)
59{
60 assert(isPowerOf2(prefetchCandidatesPerEntry));
61}
62
63void
64IrregularStreamBufferPrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
65 std::vector<AddrPriority> &addresses)
66{
67 // This prefetcher requires a PC
68 if (!pfi.hasPC()) {
69 return;
70 }
71 bool is_secure = pfi.isSecure();
72 Addr pc = pfi.getPC();
73 Addr addr = blockIndex(pfi.getAddr());
74
75 // Training, if the entry exists, then we found a correlation between
76 // the entry lastAddress (named as correlated_addr_A) and the address of
77 // the current access (named as correlated_addr_B)
78 TrainingUnitEntry *entry = trainingUnit.findEntry(pc, is_secure);
79 bool correlated_addr_found = false;
80 Addr correlated_addr_A = 0;
81 Addr correlated_addr_B = 0;
82 if (entry != nullptr && entry->lastAddressSecure == is_secure) {
83 trainingUnit.accessEntry(entry);
84 correlated_addr_found = true;
85 correlated_addr_A = entry->lastAddress;
86 correlated_addr_B = addr;
87 } else {
88 entry = trainingUnit.findVictim(pc);
89 assert(entry != nullptr);
90
91 trainingUnit.insertEntry(pc, is_secure, entry);
92 }
93 // Update the entry
94 entry->lastAddress = addr;
95 entry->lastAddressSecure = is_secure;
96
97 if (correlated_addr_found) {
98 // If a correlation was found, update the Physical-to-Structural
99 // table accordingly
100 AddressMapping &mapping_A = getPSMapping(correlated_addr_A, is_secure);
101 AddressMapping &mapping_B = getPSMapping(correlated_addr_B, is_secure);
102 if (mapping_A.counter > 0 && mapping_B.counter > 0) {
103 // Entry for A and B
104 if (mapping_B.address == (mapping_A.address + 1)) {
|
103 if (mapping_B.counter < maxCounterValue) {
104 mapping_B.counter += 1;
105 }
| 105 mapping_B.counter++;
|
106 } else {
107 if (mapping_B.counter == 1) {
| 106 } else {
107 if (mapping_B.counter == 1) {
|
108 // counter would hit 0, reassign address
109 mapping_B.counter = 1;
| 108 // Counter would hit 0, reassign address while keeping
109 // counter at 1
|
110 mapping_B.address = mapping_A.address + 1;
111 addStructuralToPhysicalEntry(mapping_B.address, is_secure,
112 correlated_addr_B);
113 } else {
| 110 mapping_B.address = mapping_A.address + 1;
111 addStructuralToPhysicalEntry(mapping_B.address, is_secure,
112 correlated_addr_B);
113 } else {
|
114 mapping_B.counter -= 1;
| 114 mapping_B.counter--;
|
115 }
116 }
117 } else {
118 if (mapping_A.counter == 0) {
119 // if A is not valid, generate a new structural address
| 115 }
116 }
117 } else {
118 if (mapping_A.counter == 0) {
119 // if A is not valid, generate a new structural address
|
120 mapping_A.counter = 1;
| 120 mapping_A.counter++;
|
121 mapping_A.address = structuralAddressCounter;
122 structuralAddressCounter += chunkSize;
123 addStructuralToPhysicalEntry(mapping_A.address,
124 is_secure, correlated_addr_A);
125 }
| 121 mapping_A.address = structuralAddressCounter;
122 structuralAddressCounter += chunkSize;
123 addStructuralToPhysicalEntry(mapping_A.address,
124 is_secure, correlated_addr_A);
125 }
|
126 mapping_B.counter = 1;
| 126 mapping_B.counter.reset();
127 mapping_B.counter++;
|
127 mapping_B.address = mapping_A.address + 1;
128 // update SP-AMC
129 addStructuralToPhysicalEntry(mapping_B.address, is_secure,
130 correlated_addr_B);
131 }
132 }
133
134 // Use the PS mapping to predict future accesses using the current address
135 // - Look for the structured address
136 // - if it exists, use it to generate prefetches for the subsequent
137 // addresses in ascending order, as many as indicated by the degree
138 // (given the structured address S, prefetch S+1, S+2, .. up to S+degree)
139 Addr amc_address = addr / prefetchCandidatesPerEntry;
140 Addr map_index = addr % prefetchCandidatesPerEntry;
141 AddressMappingEntry *ps_am = psAddressMappingCache.findEntry(amc_address,
142 is_secure);
143 if (ps_am != nullptr) {
144 AddressMapping &mapping = ps_am->mappings[map_index];
145 if (mapping.counter > 0) {
146 Addr sp_address = mapping.address / prefetchCandidatesPerEntry;
147 Addr sp_index = mapping.address % prefetchCandidatesPerEntry;
148 AddressMappingEntry *sp_am =
149 spAddressMappingCache.findEntry(sp_address, is_secure);
150 if (sp_am == nullptr) {
151 // The entry has been evicted, can not generate prefetches
152 return;
153 }
154 for (unsigned d = 1;
155 d <= degree && (sp_index + d) < prefetchCandidatesPerEntry;
156 d += 1)
157 {
158 AddressMapping &spm = sp_am->mappings[sp_index + d];
159 //generate prefetch
160 if (spm.counter > 0) {
161 Addr pf_addr = spm.address << lBlkSize;
162 addresses.push_back(AddrPriority(pf_addr, 0));
163 }
164 }
165 }
166 }
167}
168
169IrregularStreamBufferPrefetcher::AddressMapping&
170IrregularStreamBufferPrefetcher::getPSMapping(Addr paddr, bool is_secure)
171{
172 Addr amc_address = paddr / prefetchCandidatesPerEntry;
173 Addr map_index = paddr % prefetchCandidatesPerEntry;
174 AddressMappingEntry *ps_entry =
175 psAddressMappingCache.findEntry(amc_address, is_secure);
176 if (ps_entry != nullptr) {
177 // A PS-AMC line already exists
178 psAddressMappingCache.accessEntry(ps_entry);
179 } else {
180 ps_entry = psAddressMappingCache.findVictim(amc_address);
181 assert(ps_entry != nullptr);
182
183 psAddressMappingCache.insertEntry(amc_address, is_secure, ps_entry);
184 }
185 return ps_entry->mappings[map_index];
186}
187
188void
189IrregularStreamBufferPrefetcher::addStructuralToPhysicalEntry(
190 Addr structural_address, bool is_secure, Addr physical_address)
191{
192 Addr amc_address = structural_address / prefetchCandidatesPerEntry;
193 Addr map_index = structural_address % prefetchCandidatesPerEntry;
194 AddressMappingEntry *sp_entry =
195 spAddressMappingCache.findEntry(amc_address, is_secure);
196 if (sp_entry != nullptr) {
197 spAddressMappingCache.accessEntry(sp_entry);
198 } else {
199 sp_entry = spAddressMappingCache.findVictim(amc_address);
200 assert(sp_entry != nullptr);
201
202 spAddressMappingCache.insertEntry(amc_address, is_secure, sp_entry);
203 }
204 AddressMapping &mapping = sp_entry->mappings[map_index];
205 mapping.address = physical_address;
| 128 mapping_B.address = mapping_A.address + 1;
129 // update SP-AMC
130 addStructuralToPhysicalEntry(mapping_B.address, is_secure,
131 correlated_addr_B);
132 }
133 }
134
135 // Use the PS mapping to predict future accesses using the current address
136 // - Look for the structured address
137 // - if it exists, use it to generate prefetches for the subsequent
138 // addresses in ascending order, as many as indicated by the degree
139 // (given the structured address S, prefetch S+1, S+2, .. up to S+degree)
140 Addr amc_address = addr / prefetchCandidatesPerEntry;
141 Addr map_index = addr % prefetchCandidatesPerEntry;
142 AddressMappingEntry *ps_am = psAddressMappingCache.findEntry(amc_address,
143 is_secure);
144 if (ps_am != nullptr) {
145 AddressMapping &mapping = ps_am->mappings[map_index];
146 if (mapping.counter > 0) {
147 Addr sp_address = mapping.address / prefetchCandidatesPerEntry;
148 Addr sp_index = mapping.address % prefetchCandidatesPerEntry;
149 AddressMappingEntry *sp_am =
150 spAddressMappingCache.findEntry(sp_address, is_secure);
151 if (sp_am == nullptr) {
152 // The entry has been evicted, can not generate prefetches
153 return;
154 }
155 for (unsigned d = 1;
156 d <= degree && (sp_index + d) < prefetchCandidatesPerEntry;
157 d += 1)
158 {
159 AddressMapping &spm = sp_am->mappings[sp_index + d];
160 //generate prefetch
161 if (spm.counter > 0) {
162 Addr pf_addr = spm.address << lBlkSize;
163 addresses.push_back(AddrPriority(pf_addr, 0));
164 }
165 }
166 }
167 }
168}
169
170IrregularStreamBufferPrefetcher::AddressMapping&
171IrregularStreamBufferPrefetcher::getPSMapping(Addr paddr, bool is_secure)
172{
173 Addr amc_address = paddr / prefetchCandidatesPerEntry;
174 Addr map_index = paddr % prefetchCandidatesPerEntry;
175 AddressMappingEntry *ps_entry =
176 psAddressMappingCache.findEntry(amc_address, is_secure);
177 if (ps_entry != nullptr) {
178 // A PS-AMC line already exists
179 psAddressMappingCache.accessEntry(ps_entry);
180 } else {
181 ps_entry = psAddressMappingCache.findVictim(amc_address);
182 assert(ps_entry != nullptr);
183
184 psAddressMappingCache.insertEntry(amc_address, is_secure, ps_entry);
185 }
186 return ps_entry->mappings[map_index];
187}
188
189void
190IrregularStreamBufferPrefetcher::addStructuralToPhysicalEntry(
191 Addr structural_address, bool is_secure, Addr physical_address)
192{
193 Addr amc_address = structural_address / prefetchCandidatesPerEntry;
194 Addr map_index = structural_address % prefetchCandidatesPerEntry;
195 AddressMappingEntry *sp_entry =
196 spAddressMappingCache.findEntry(amc_address, is_secure);
197 if (sp_entry != nullptr) {
198 spAddressMappingCache.accessEntry(sp_entry);
199 } else {
200 sp_entry = spAddressMappingCache.findVictim(amc_address);
201 assert(sp_entry != nullptr);
202
203 spAddressMappingCache.insertEntry(amc_address, is_secure, sp_entry);
204 }
205 AddressMapping &mapping = sp_entry->mappings[map_index];
206 mapping.address = physical_address;
|
206 mapping.counter = 1;
| 207 mapping.counter.reset();
208 mapping.counter++;
|
207}
208
209IrregularStreamBufferPrefetcher*
210IrregularStreamBufferPrefetcherParams::create()
211{
212 return new IrregularStreamBufferPrefetcher(this);
213}
| 209}
210
211IrregularStreamBufferPrefetcher*
212IrregularStreamBufferPrefetcherParams::create()
213{
214 return new IrregularStreamBufferPrefetcher(this);
215}
|