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 /**
32  * Implementation of the Spatio-Temporal Memory Streaming Prefetcher (STeMS)
33  * Reference:
34  *    Spatio-temporal memory streaming.
35  *    Somogyi, S., Wenisch, T. F., Ailamaki, A., & Falsafi, B. (2009).
36  *    ACM SIGARCH Computer Architecture News, 37(3), 69-80.
37  *
38  * Notes:
39  * - The functionality described in the paper as Streamed Value Buffer (SVB)
40  *   is not implemented here, as this is handled by the QueuedPrefetcher class
41  */
42
43#ifndef __MEM_CACHE_PREFETCH_SPATIO_TEMPORAL_MEMORY_STREAMING_HH__
44#define __MEM_CACHE_PREFETCH_SPATIO_TEMPORAL_MEMORY_STREAMING_HH__
45
46#include <vector>
47
48#include "base/sat_counter.hh"
49#include "mem/cache/prefetch/associative_set.hh"
50#include "mem/cache/prefetch/queued.hh"
51
52struct STeMSPrefetcherParams;
53
54class STeMSPrefetcher : public QueuedPrefetcher
55{
56    /** Size of each spatial region */
57    const size_t spatialRegionSize;
58    /** log_2 of the spatial region size */
59    const size_t spatialRegionSizeBits;
60    /** Number of reconstruction entries */
61    const unsigned int reconstructionEntries;
62
63    /**
64     * Entry data type for the Active Generation Table (AGT) and the Pattern
65     * Sequence Table (PST)
66     */
67    struct ActiveGenerationTableEntry : public TaggedEntry {
68        /** Physical address of the spatial region */
69        Addr paddress;
70        /** PC that started this generation */
71        Addr pc;
72        /** Counter to keep track of the interleaving between sequences */
73        unsigned int seqCounter;
74
75        /** Sequence entry data type */
76        struct SequenceEntry {
77            /** 2-bit confidence counter */
78            SatCounter counter;
79            /** Offset, in cache lines, within the spatial region */
80            unsigned int offset;
81            /** Intearleaving position on the global access sequence */
82            unsigned int delta;
83            SequenceEntry() : counter(2), offset(0), delta(0)
84            {}
85        };
86        /** Sequence of accesses */
87        std::vector<SequenceEntry> sequence;
88
89        ActiveGenerationTableEntry(int num_positions) : paddress(0), pc(0),
90            seqCounter(0), sequence(num_positions)
91        {}
92
93        void reset() override
94        {
95            paddress = 0;
96            pc = 0;
97            seqCounter = 0;
98            for (auto &seq_entry : sequence) {
99                seq_entry.counter.reset();
100                seq_entry.offset = 0;
101                seq_entry.delta = 0;
102            }
103        }
104
105        /**
106         * Update the entry data with an entry from a generation that just
107         * ended. This operation can not be done with the copy constructor,
108         * becasuse the TaggedEntry component must not be copied.
109         * @param e entry which generation has ended
110         */
111        void update(ActiveGenerationTableEntry const &e)
112        {
113            paddress = e.paddress;
114            pc = e.pc;
115            seqCounter = e.seqCounter;
116            sequence = e.sequence;
117        }
118
119        /**
120         * Add a new access to the sequence
121         * @param offset offset in cachelines within the spatial region
122         */
123        void addOffset(unsigned int offset) {
124            // Search for the offset in the deltas array, if it exist, update
125            // the corresponding counter, if not, add the offset to the array
126            for (auto &seq_entry : sequence) {
127                if (seq_entry.counter > 0) {
128                    if (seq_entry.offset == offset) {
129                        seq_entry.counter++;
130                    }
131                } else {
132                    // If the counter is 0 it means that this position is not
133                    // being used, and we can allocate the new offset here
134                    seq_entry.counter++;
135                    seq_entry.offset = offset;
136                    seq_entry.delta = seqCounter;
137                    break;
138                }
139            }
140            seqCounter = 0;
141        }
142    };
143
144    /** Active Generation Table (AGT) */
145    AssociativeSet<ActiveGenerationTableEntry> activeGenerationTable;
146    /** Pattern Sequence Table (PST) */
147    AssociativeSet<ActiveGenerationTableEntry> patternSequenceTable;
148
149    /** Data type of the Region Miss Order Buffer entry */
150    struct RegionMissOrderBufferEntry {
151        /** Address of the spatial region */
152        Addr srAddress;
153        /**
154         * Address used to index the PST table, generated using the PC and the
155         * offset within the spatial region
156         */
157        Addr pstAddress;
158        /** Delta within the global miss order sequence */
159        unsigned int delta;
160        /** Valid bit */
161        bool valid;
162    };
163
164    /** Region Miss Order Buffer (RMOB) */
165    std::vector<RegionMissOrderBufferEntry> rmob;
166    /** First free position (or older, if it is full) of the RMOB */
167    unsigned int rmobHead;
168
169    /** Counter to keep the count of accesses between trigger accesses */
170    unsigned int lastTriggerCounter;
171
172    /** Checks if the active generations have ended */
173    void checkForActiveGenerationsEnd();
174    /**
175     * Adds an entry to the RMOB
176     * @param sr_addr Spatial region address
177     * @param pst_addr Corresponding PST address
178     * @param delta Number of entries skipped in the global miss order
179     */
180    void addToRMOB(Addr sr_addr, Addr pst_addr, unsigned int delta);
181
182    /**
183     * Reconstructs a sequence of accesses and generates the prefetch
184     * addresses, adding them to the addresses vector
185     * @param rmob_idx rmob position to start generating from
186     * @param addresses vector to add the addresses to be prefetched
187     */
188    void reconstructSequence(unsigned int rmob_idx,
189                             std::vector<AddrPriority> &addresses);
190  public:
191    STeMSPrefetcher(const STeMSPrefetcherParams* p);
192    ~STeMSPrefetcher() {}
193    void calculatePrefetch(const PrefetchInfo &pfi,
194                           std::vector<AddrPriority> &addresses) override;
195};
196
197#endif//__MEM_CACHE_PREFETCH_SPATIO_TEMPORAL_MEMORY_STREAMING_HH__
198