irregular_stream_buffer.cc revision 13963:94555f0223ba 
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),
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,
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)
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)) {
105                mapping_B.counter++;
106            } else {
107                if (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 {
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
120                mapping_A.counter++;
121                mapping_A.address = structuralAddressCounter;
122                structuralAddressCounter += chunkSize;
123                addStructuralToPhysicalEntry(mapping_A.address,
124                        is_secure, correlated_addr_A);
125            }
126            mapping_B.counter.reset();
127            mapping_B.counter++;
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;
207    mapping.counter.reset();
208    mapping.counter++;
209}
210
211IrregularStreamBufferPrefetcher*
212IrregularStreamBufferPrefetcherParams::create()
213{
214    return new IrregularStreamBufferPrefetcher(this);
215}
216