spatio_temporal_memory_streaming.cc revision 13963:94555f0223ba 
1/**
2 * Copyright (c) 2019 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/spatio_temporal_memory_streaming.hh"
32
33#include "debug/HWPrefetch.hh"
34#include "mem/cache/prefetch/associative_set_impl.hh"
35#include "params/STeMSPrefetcher.hh"
36
37STeMSPrefetcher::STeMSPrefetcher(const STeMSPrefetcherParams *p)
38  : QueuedPrefetcher(p), spatialRegionSize(p->spatial_region_size),
39    spatialRegionSizeBits(floorLog2(p->spatial_region_size)),
40    reconstructionEntries(p->reconstruction_entries),
41    activeGenerationTable(p->active_generation_table_assoc,
42                          p->active_generation_table_entries,
43                          p->active_generation_table_indexing_policy,
44                          p->active_generation_table_replacement_policy,
45                          ActiveGenerationTableEntry(
46                              spatialRegionSize / blkSize)),
47    patternSequenceTable(p->pattern_sequence_table_assoc,
48                         p->pattern_sequence_table_entries,
49                         p->pattern_sequence_table_indexing_policy,
50                         p->pattern_sequence_table_replacement_policy,
51                         ActiveGenerationTableEntry(
52                             spatialRegionSize / blkSize)),
53    rmob(p->region_miss_order_buffer_entries), rmobHead(0)
54{
55    fatal_if(!isPowerOf2(spatialRegionSize),
56        "The spatial region size must be a power of 2.");
57}
58
59void
60STeMSPrefetcher::checkForActiveGenerationsEnd() {
61    // This prefetcher operates attached to the L1 and it observes all
62    // accesses, this guarantees that no evictions are missed
63
64    // Iterate over all entries, if any recorded cacheline has been evicted,
65    // the generation finishes, move the entry to the PST
66    for (auto &agt_entry : activeGenerationTable) {
67        if (agt_entry.isValid()) {
68            bool generation_ended = false;
69            bool sr_is_secure = agt_entry.isSecure();
70            for (auto &seq_entry : agt_entry.sequence) {
71                if (seq_entry.counter > 0) {
72                    Addr cache_addr =
73                        agt_entry.paddress + seq_entry.offset * blkSize;
74                    if (!inCache(cache_addr, sr_is_secure) &&
75                            !inMissQueue(cache_addr, sr_is_secure)) {
76                        generation_ended = true;
77                        break;
78                    }
79                }
80            }
81            if (generation_ended) {
82                // PST is indexed using the PC (secure bit is unused)
83                ActiveGenerationTableEntry *pst_entry =
84                    patternSequenceTable.findEntry(agt_entry.pc,
85                                                   false /*unused*/);
86                if (pst_entry == nullptr) {
87                    // Tipically an entry will not exist
88                    pst_entry = patternSequenceTable.findVictim(agt_entry.pc);
89                    assert(pst_entry != nullptr);
90                    patternSequenceTable.insertEntry(agt_entry.pc,
91                            false /*unused*/, pst_entry);
92                } else {
93                    patternSequenceTable.accessEntry(pst_entry);
94                }
95                // If the entry existed, this will update the values, if not,
96                // this also sets the values of the entry
97                pst_entry->update(agt_entry);
98                // Free the AGT entry
99                agt_entry.setInvalid();
100            }
101        }
102    }
103}
104
105void
106STeMSPrefetcher::addToRMOB(Addr sr_addr, Addr pst_addr, unsigned int delta)
107{
108    RegionMissOrderBufferEntry &rmob_entry = rmob[rmobHead];
109    rmobHead = (rmobHead + 1) % rmob.size();
110
111    rmob_entry.srAddress = sr_addr;
112    rmob_entry.pstAddress = pst_addr;
113    rmob_entry.delta = delta;
114    rmob_entry.valid = true;
115}
116
117void
118STeMSPrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
119                                   std::vector<AddrPriority> &addresses)
120{
121    if (!pfi.hasPC()) {
122        DPRINTF(HWPrefetch, "Ignoring request with no PC.\n");
123        return;
124    }
125
126    Addr pc = pfi.getPC();
127    bool is_secure = pfi.isSecure();
128    // Spatial region address
129    Addr sr_addr = pfi.getAddr() / spatialRegionSize;
130    Addr paddr = pfi.getPaddr();
131
132    // Offset in cachelines within the spatial region
133    Addr sr_offset = (pfi.getAddr() % spatialRegionSize) / blkSize;
134
135    // Check if any active generation has ended
136    checkForActiveGenerationsEnd();
137
138    ActiveGenerationTableEntry *agt_entry =
139        activeGenerationTable.findEntry(sr_addr, is_secure);
140    if (agt_entry != nullptr) {
141        // found an entry in the AGT, entry is currently being recorded,
142        // add the offset
143        activeGenerationTable.accessEntry(agt_entry);
144        agt_entry->addOffset(sr_offset);
145        lastTriggerCounter += 1;
146    } else {
147        // Not found, this is the first access (Trigger access)
148
149        // Add entry to RMOB
150        Addr pst_addr = (pc << spatialRegionSizeBits) + sr_offset;
151        addToRMOB(sr_addr, pst_addr, lastTriggerCounter);
152        // Reset last trigger counter
153        lastTriggerCounter = 0;
154
155        // allocate a new AGT entry
156        agt_entry = activeGenerationTable.findVictim(sr_addr);
157        assert(agt_entry != nullptr);
158        activeGenerationTable.insertEntry(sr_addr, is_secure, agt_entry);
159        agt_entry->pc = pc;
160        agt_entry->paddress = paddr;
161        agt_entry->addOffset(sr_offset);
162    }
163    // increase the seq Counter for other entries
164    for (auto &agt_e : activeGenerationTable) {
165        if (agt_e.isValid() && agt_entry != &agt_e) {
166            agt_e.seqCounter += 1;
167        }
168    }
169
170    // Prefetch generation: if this is a miss, search for the most recent
171    // entry in the RMOB, and reconstruct the registered access sequence
172    if (pfi.isCacheMiss()) {
173        for (unsigned int idx = (rmobHead - 1) % rmob.size();
174             idx != rmobHead && rmob[idx].valid;
175             idx = (idx - 1) % rmob.size())
176        {
177            if (rmob[idx].srAddress == sr_addr) {
178                // reconstruct the access sequence
179                reconstructSequence(idx, addresses);
180                break;
181            }
182        }
183    }
184}
185
186void
187STeMSPrefetcher::reconstructSequence(unsigned int rmob_idx,
188    std::vector<AddrPriority> &addresses)
189{
190    std::vector<Addr> reconstruction(reconstructionEntries, MaxAddr);
191    unsigned int idx = 0;
192    // process rmob entries from rmob_idx (most recent with
193    // address = sr_addr) to the last one (rmobHead)
194    for (int i = rmob_idx;
195         i != rmobHead && idx < reconstructionEntries;
196         i = (i + 1) % rmob.size())
197    {
198        reconstruction[idx] = rmob[i].srAddress * spatialRegionSize;
199        unsigned int next_i = (i + 1) % rmob.size();
200        idx += rmob[next_i].delta + 1;
201    }
202    // Now query the PST with the PC of each RMOB entry
203    idx = 0;
204    for (int i = rmob_idx;
205         i != rmobHead && idx < reconstructionEntries;
206         i = (i + 1) % rmob.size())
207    {
208        ActiveGenerationTableEntry *pst_entry =
209            patternSequenceTable.findEntry(rmob[i].pstAddress,
210                                           false /* unused */);
211        if (pst_entry != nullptr) {
212            patternSequenceTable.accessEntry(pst_entry);
213            for (auto &seq_entry : pst_entry->sequence) {
214                if (seq_entry.counter > 1) {
215                    // 2-bit counter: high enough confidence with a
216                    // value greater than 1
217                    Addr rec_addr = rmob[i].srAddress * spatialRegionSize +
218                        seq_entry.offset;
219                    unsigned ridx = idx + seq_entry.delta;
220                    // Try to use the corresponding position, if it has been
221                    // already used, look the surrounding positions
222                    if (ridx < reconstructionEntries &&
223                        reconstruction[ridx] == MaxAddr) {
224                        reconstruction[ridx] = rec_addr;
225                    } else if ((ridx + 1) < reconstructionEntries &&
226                        reconstruction[ridx + 1] == MaxAddr) {
227                        reconstruction[ridx + 1] = rec_addr;
228                    } else if ((ridx + 2) < reconstructionEntries &&
229                        reconstruction[ridx + 2] == MaxAddr) {
230                        reconstruction[ridx + 2] = rec_addr;
231                    } else if ((ridx > 0) &&
232                        ((ridx - 1) < reconstructionEntries) &&
233                        reconstruction[ridx - 1] == MaxAddr) {
234                        reconstruction[ridx - 1] = rec_addr;
235                    } else if ((ridx > 1) &&
236                        ((ridx - 2) < reconstructionEntries) &&
237                        reconstruction[ridx - 2] == MaxAddr) {
238                        reconstruction[ridx - 2] = rec_addr;
239                    }
240                }
241            }
242        }
243        unsigned int next_i = (i + 1) % rmob.size();
244        idx += rmob[next_i].delta + 1;
245    }
246    for (Addr pf_addr : reconstruction) {
247        if (pf_addr != MaxAddr) {
248            addresses.push_back(AddrPriority(pf_addr, 0));
249        }
250    }
251}
252
253STeMSPrefetcher *
254STeMSPrefetcherParams::create()
255{
256   return new STeMSPrefetcher(this);
257}
258