irregular_stream_buffer.cc revision 13669:24ef552b4d6d 
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),
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        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,
55                              AddressMappingEntry(prefetchCandidatesPerEntry)),
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)) {
103                if (mapping_B.counter < maxCounterValue) {
104                    mapping_B.counter += 1;
105                }
106            } else {
107                if (mapping_B.counter == 1) {
108                    // counter would hit 0, reassign address
109                    mapping_B.counter = 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 -= 1;
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;
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;
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            assert(sp_am != nullptr);
151            for (unsigned d = 1;
152                    d <= degree && (sp_index + d) < prefetchCandidatesPerEntry;
153                    d += 1)
154            {
155                AddressMapping &spm = sp_am->mappings[sp_index + d];
156                //generate prefetch
157                if (spm.counter > 0) {
158                    Addr pf_addr = spm.address << lBlkSize;
159                    addresses.push_back(AddrPriority(pf_addr, 0));
160                }
161            }
162        }
163    }
164}
165
166IrregularStreamBufferPrefetcher::AddressMapping&
167IrregularStreamBufferPrefetcher::getPSMapping(Addr paddr, bool is_secure)
168{
169    Addr amc_address = paddr / prefetchCandidatesPerEntry;
170    Addr map_index   = paddr % prefetchCandidatesPerEntry;
171    AddressMappingEntry *ps_entry =
172        psAddressMappingCache.findEntry(amc_address, is_secure);
173    if (ps_entry != nullptr) {
174        // A PS-AMC line already exists
175        psAddressMappingCache.accessEntry(ps_entry);
176    } else {
177        ps_entry = psAddressMappingCache.findVictim(amc_address);
178        assert(ps_entry != nullptr);
179
180        psAddressMappingCache.insertEntry(amc_address, is_secure, ps_entry);
181    }
182    return ps_entry->mappings[map_index];
183}
184
185void
186IrregularStreamBufferPrefetcher::addStructuralToPhysicalEntry(
187    Addr structural_address, bool is_secure, Addr physical_address)
188{
189    Addr amc_address = structural_address / prefetchCandidatesPerEntry;
190    Addr map_index   = structural_address % prefetchCandidatesPerEntry;
191    AddressMappingEntry *sp_entry =
192        spAddressMappingCache.findEntry(amc_address, is_secure);
193    if (sp_entry != nullptr) {
194        spAddressMappingCache.accessEntry(sp_entry);
195    } else {
196        sp_entry = spAddressMappingCache.findVictim(amc_address);
197        assert(sp_entry != nullptr);
198
199        spAddressMappingCache.insertEntry(amc_address, is_secure, sp_entry);
200    }
201    AddressMapping &mapping = sp_entry->mappings[map_index];
202    mapping.address = physical_address;
203    mapping.counter = 1;
204}
205
206IrregularStreamBufferPrefetcher*
207IrregularStreamBufferPrefetcherParams::create()
208{
209    return new IrregularStreamBufferPrefetcher(this);
210}
211