spatio_temporal_memory_streaming.cc revision 13963:94555f0223ba
16691Stjones1@inf.ed.ac.uk/**
26691Stjones1@inf.ed.ac.uk * Copyright (c) 2019 Metempsy Technology Consulting
36691Stjones1@inf.ed.ac.uk * All rights reserved.
46691Stjones1@inf.ed.ac.uk *
56691Stjones1@inf.ed.ac.uk * Redistribution and use in source and binary forms, with or without
66691Stjones1@inf.ed.ac.uk * modification, are permitted provided that the following conditions are
76691Stjones1@inf.ed.ac.uk * met: redistributions of source code must retain the above copyright
86691Stjones1@inf.ed.ac.uk * notice, this list of conditions and the following disclaimer;
96691Stjones1@inf.ed.ac.uk * redistributions in binary form must reproduce the above copyright
106691Stjones1@inf.ed.ac.uk * notice, this list of conditions and the following disclaimer in the
116691Stjones1@inf.ed.ac.uk * documentation and/or other materials provided with the distribution;
126691Stjones1@inf.ed.ac.uk * neither the name of the copyright holders nor the names of its
136691Stjones1@inf.ed.ac.uk * contributors may be used to endorse or promote products derived from
146691Stjones1@inf.ed.ac.uk * this software without specific prior written permission.
156691Stjones1@inf.ed.ac.uk *
166691Stjones1@inf.ed.ac.uk * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
176691Stjones1@inf.ed.ac.uk * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
186691Stjones1@inf.ed.ac.uk * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
196691Stjones1@inf.ed.ac.uk * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
206691Stjones1@inf.ed.ac.uk * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
216691Stjones1@inf.ed.ac.uk * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
226691Stjones1@inf.ed.ac.uk * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
236691Stjones1@inf.ed.ac.uk * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
246691Stjones1@inf.ed.ac.uk * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
256691Stjones1@inf.ed.ac.uk * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
266691Stjones1@inf.ed.ac.uk * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
276691Stjones1@inf.ed.ac.uk *
286691Stjones1@inf.ed.ac.uk * Authors: Javier Bueno
296691Stjones1@inf.ed.ac.uk */
306691Stjones1@inf.ed.ac.uk
316691Stjones1@inf.ed.ac.uk#include "mem/cache/prefetch/spatio_temporal_memory_streaming.hh"
326691Stjones1@inf.ed.ac.uk
336691Stjones1@inf.ed.ac.uk#include "debug/HWPrefetch.hh"
346691Stjones1@inf.ed.ac.uk#include "mem/cache/prefetch/associative_set_impl.hh"
356691Stjones1@inf.ed.ac.uk#include "params/STeMSPrefetcher.hh"
366691Stjones1@inf.ed.ac.uk
376691Stjones1@inf.ed.ac.ukSTeMSPrefetcher::STeMSPrefetcher(const STeMSPrefetcherParams *p)
386691Stjones1@inf.ed.ac.uk  : QueuedPrefetcher(p), spatialRegionSize(p->spatial_region_size),
396691Stjones1@inf.ed.ac.uk    spatialRegionSizeBits(floorLog2(p->spatial_region_size)),
406691Stjones1@inf.ed.ac.uk    reconstructionEntries(p->reconstruction_entries),
416691Stjones1@inf.ed.ac.uk    activeGenerationTable(p->active_generation_table_assoc,
426691Stjones1@inf.ed.ac.uk                          p->active_generation_table_entries,
436691Stjones1@inf.ed.ac.uk                          p->active_generation_table_indexing_policy,
446691Stjones1@inf.ed.ac.uk                          p->active_generation_table_replacement_policy,
456691Stjones1@inf.ed.ac.uk                          ActiveGenerationTableEntry(
466691Stjones1@inf.ed.ac.uk                              spatialRegionSize / blkSize)),
476691Stjones1@inf.ed.ac.uk    patternSequenceTable(p->pattern_sequence_table_assoc,
486691Stjones1@inf.ed.ac.uk                         p->pattern_sequence_table_entries,
496691Stjones1@inf.ed.ac.uk                         p->pattern_sequence_table_indexing_policy,
506691Stjones1@inf.ed.ac.uk                         p->pattern_sequence_table_replacement_policy,
516691Stjones1@inf.ed.ac.uk                         ActiveGenerationTableEntry(
526691Stjones1@inf.ed.ac.uk                             spatialRegionSize / blkSize)),
536691Stjones1@inf.ed.ac.uk    rmob(p->region_miss_order_buffer_entries), rmobHead(0)
546691Stjones1@inf.ed.ac.uk{
556691Stjones1@inf.ed.ac.uk    fatal_if(!isPowerOf2(spatialRegionSize),
566691Stjones1@inf.ed.ac.uk        "The spatial region size must be a power of 2.");
576691Stjones1@inf.ed.ac.uk}
586691Stjones1@inf.ed.ac.uk
596691Stjones1@inf.ed.ac.ukvoid
606691Stjones1@inf.ed.ac.ukSTeMSPrefetcher::checkForActiveGenerationsEnd() {
616691Stjones1@inf.ed.ac.uk    // This prefetcher operates attached to the L1 and it observes all
6212104Snathanael.premillieu@arm.com    // accesses, this guarantees that no evictions are missed
636691Stjones1@inf.ed.ac.uk
646691Stjones1@inf.ed.ac.uk    // Iterate over all entries, if any recorded cacheline has been evicted,
656691Stjones1@inf.ed.ac.uk    // the generation finishes, move the entry to the PST
667720Sgblack@eecs.umich.edu    for (auto &agt_entry : activeGenerationTable) {
677720Sgblack@eecs.umich.edu        if (agt_entry.isValid()) {
687720Sgblack@eecs.umich.edu            bool generation_ended = false;
697720Sgblack@eecs.umich.edu            bool sr_is_secure = agt_entry.isSecure();
707720Sgblack@eecs.umich.edu            for (auto &seq_entry : agt_entry.sequence) {
717720Sgblack@eecs.umich.edu                if (seq_entry.counter > 0) {
7212614Sgabeblack@google.com                    Addr cache_addr =
7312614Sgabeblack@google.com                        agt_entry.paddress + seq_entry.offset * blkSize;
7412614Sgabeblack@google.com                    if (!inCache(cache_addr, sr_is_secure) &&
7512614Sgabeblack@google.com                            !inMissQueue(cache_addr, sr_is_secure)) {
7612614Sgabeblack@google.com                        generation_ended = true;
7712614Sgabeblack@google.com                        break;
786691Stjones1@inf.ed.ac.uk                    }
796691Stjones1@inf.ed.ac.uk                }
807811Ssteve.reinhardt@amd.com            }
816691Stjones1@inf.ed.ac.uk            if (generation_ended) {
826691Stjones1@inf.ed.ac.uk                // 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