2 * Copyright (c) 2018 Metempsy Technology Consulting
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.
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.
28 * Authors: Javier Bueno
31 #include "mem/cache/prefetch/irregular_stream_buffer.hh"
33 #include "debug/HWPrefetch.hh"
34 #include "mem/cache/prefetch/associative_set_impl.hh"
35 #include "params/IrregularStreamBufferPrefetcher.hh"
37 IrregularStreamBufferPrefetcher::IrregularStreamBufferPrefetcher(
38 const IrregularStreamBufferPrefetcherParams
*p
)
39 : QueuedPrefetcher(p
),
40 chunkSize(p
->chunk_size
),
41 prefetchCandidatesPerEntry(p
->prefetch_candidates_per_entry
),
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
,
51 p
->num_counter_bits
)),
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
,
56 AddressMappingEntry(prefetchCandidatesPerEntry
,
57 p
->num_counter_bits
)),
58 structuralAddressCounter(0)
60 assert(isPowerOf2(prefetchCandidatesPerEntry
));
64 IrregularStreamBufferPrefetcher::calculatePrefetch(const PrefetchInfo
&pfi
,
65 std::vector
<AddrPriority
> &addresses
)
67 // This prefetcher requires a PC
71 bool is_secure
= pfi
.isSecure();
72 Addr pc
= pfi
.getPC();
73 Addr addr
= blockIndex(pfi
.getAddr());
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
;
88 entry
= trainingUnit
.findVictim(pc
);
89 assert(entry
!= nullptr);
91 trainingUnit
.insertEntry(pc
, is_secure
, entry
);
94 entry
->lastAddress
= addr
;
95 entry
->lastAddressSecure
= is_secure
;
97 if (correlated_addr_found
) {
98 // If a correlation was found, update the Physical-to-Structural
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) {
104 if (mapping_B
.address
== (mapping_A
.address
+ 1)) {
107 if (mapping_B
.counter
== 1) {
108 // Counter would hit 0, reassign address while keeping
110 mapping_B
.address
= mapping_A
.address
+ 1;
111 addStructuralToPhysicalEntry(mapping_B
.address
, is_secure
,
118 if (mapping_A
.counter
== 0) {
119 // if A is not valid, generate a new structural address
121 mapping_A
.address
= structuralAddressCounter
;
122 structuralAddressCounter
+= chunkSize
;
123 addStructuralToPhysicalEntry(mapping_A
.address
,
124 is_secure
, correlated_addr_A
);
126 mapping_B
.counter
.reset();
128 mapping_B
.address
= mapping_A
.address
+ 1;
130 addStructuralToPhysicalEntry(mapping_B
.address
, is_secure
,
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
,
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
156 d
<= degree
&& (sp_index
+ d
) < prefetchCandidatesPerEntry
;
159 AddressMapping
&spm
= sp_am
->mappings
[sp_index
+ d
];
161 if (spm
.counter
> 0) {
162 Addr pf_addr
= spm
.address
<< lBlkSize
;
163 addresses
.push_back(AddrPriority(pf_addr
, 0));
170 IrregularStreamBufferPrefetcher::AddressMapping
&
171 IrregularStreamBufferPrefetcher::getPSMapping(Addr paddr
, bool is_secure
)
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
);
181 ps_entry
= psAddressMappingCache
.findVictim(amc_address
);
182 assert(ps_entry
!= nullptr);
184 psAddressMappingCache
.insertEntry(amc_address
, is_secure
, ps_entry
);
186 return ps_entry
->mappings
[map_index
];
190 IrregularStreamBufferPrefetcher::addStructuralToPhysicalEntry(
191 Addr structural_address
, bool is_secure
, Addr physical_address
)
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
);
200 sp_entry
= spAddressMappingCache
.findVictim(amc_address
);
201 assert(sp_entry
!= nullptr);
203 spAddressMappingCache
.insertEntry(amc_address
, is_secure
, sp_entry
);
205 AddressMapping
&mapping
= sp_entry
->mappings
[map_index
];
206 mapping
.address
= physical_address
;
207 mapping
.counter
.reset();
211 IrregularStreamBufferPrefetcher
*
212 IrregularStreamBufferPrefetcherParams::create()
214 return new IrregularStreamBufferPrefetcher(this);