indirect_memory.hh revision 13772 
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/**
32 * Implementation of the Indirect Memory Prefetcher
33 *
34 * References:
35 * IMP: Indirect memory prefetcher.
36 * Yu, X., Hughes, C. J., Satish, N., & Devadas, S. (2015, December).
37 * In Proceedings of the 48th International Symposium on Microarchitecture
38 * (pp. 178-190). ACM.
39 */
40
41#ifndef __MEM_CACHE_PREFETCH_INDIRECT_MEMORY_HH__
42#define __MEM_CACHE_PREFETCH_INDIRECT_MEMORY_HH__
43
44#include <vector>
45
46#include "mem/cache/prefetch/associative_set.hh"
47#include "mem/cache/prefetch/queued.hh"
48
49struct IndirectMemoryPrefetcherParams;
50
51class IndirectMemoryPrefetcher : public QueuedPrefetcher
52{
53    /** Maximum number of prefetches generated per event */
54    const unsigned int maxPrefetchDistance;
55    /** Shift values considered */
56    const std::vector<int> shiftValues;
57    /** Counter threshold to start prefetching */
58    const unsigned int prefetchThreshold;
59    /** Maximum value of the confidence indirectCounter */
60    const unsigned int maxIndirectCounterValue;
61    /** streamCounter value to trigger the streaming prefetcher */
62    const int streamCounterThreshold;
63    /** Number of prefetches generated when using the streaming prefetcher */
64    const int streamingDistance;
65
66    /** Prefetch Table Entry */
67    struct PrefetchTableEntry : public TaggedEntry
68    {
69        /* Stream table fields */
70
71        /** Accessed address */
72        Addr address;
73        /** Whether this address is in the secure region */
74        bool secure;
75        /** Confidence counter of the stream */
76        unsigned int streamCounter;
77
78        /* Indirect table fields */
79
80        /** Enable bit of the indirect fields */
81        bool enabled;
82        /** Current index value */
83        int64_t index;
84        /** BaseAddr detected */
85        Addr baseAddr;
86        /** Shift detected */
87        int shift;
88        /** Confidence counter of the indirect fields */
89        int indirectCounter;
90        /**
91         * This variable is set to indicate that there has been at least one
92         * match with the current index value. This information is later used
93         * when a new index is updated. If there were no increases in the
94         * indirectCounter, the counter is decremented.
95         */
96        bool increasedIndirectCounter;
97
98        PrefetchTableEntry() : TaggedEntry(), address(0), secure(false),
99            streamCounter(0), enabled(false), index(0), baseAddr(0), shift(0),
100            indirectCounter(0), increasedIndirectCounter(false)
101        {}
102
103        void reset() override {
104            address = 0;
105            secure = false;
106            streamCounter = 0;
107            enabled = false;
108            index = 0;
109            baseAddr = 0;
110            shift = 0;
111            indirectCounter = 0;
112            increasedIndirectCounter = false;
113        }
114    };
115    /** Prefetch table */
116    AssociativeSet<PrefetchTableEntry> prefetchTable;
117
118    /** Indirect Pattern Detector entrt */
119    struct IndirectPatternDetectorEntry : public TaggedEntry
120    {
121        /** First index */
122        int64_t idx1;
123        /** Second index */
124        int64_t idx2;
125        /** Valid bit for the second index */
126        bool secondIndexSet;
127        /** Number of misses currently recorded */
128        int numMisses;
129        /**
130         * Potential BaseAddr candidates for each recorded miss.
131         * The number of candidates per miss is determined by the number of
132         * elements in the shiftValues array.
133         */
134        std::vector<std::vector<Addr>> baseAddr;
135
136        IndirectPatternDetectorEntry(unsigned int num_addresses,
137                                     unsigned int num_shifts)
138          : idx1(0), idx2(0), secondIndexSet(false), numMisses(0),
139            baseAddr(num_addresses, std::vector<Addr>(num_shifts))
140        {}
141
142        void reset() override {
143            idx1 = 0;
144            idx2 = 0;
145            secondIndexSet = false;
146            numMisses = 0;
147            setInvalid();
148        }
149    };
150    /** Indirect Pattern Detector (IPD) table */
151    AssociativeSet<IndirectPatternDetectorEntry> ipd;
152
153    /** Entry currently tracking misses */
154    IndirectPatternDetectorEntry *ipdEntryTrackingMisses;
155
156    /** Byte order used to access the cache */
157    const ByteOrder byteOrder;
158
159    /**
160     * Allocate or update an entry in the IPD
161     * @param pt_entry Pointer to the associated page table entry
162     * @param index Detected first index value
163     */
164    void allocateOrUpdateIPDEntry(const PrefetchTableEntry *pt_entry,
165                                  int64_t index);
166    /**
167     * Update an IPD entry with a detected miss address, when the first index
168     * is being tracked
169     * @param miss_addr The address that caused the miss
170     */
171    void trackMissIndex1(Addr miss_addr);
172
173    /**
174     * Update an IPD entry with a detected miss address, when the second index
175     * is being tracked
176     * @param miss_addr The address that caused the miss
177     */
178    void trackMissIndex2(Addr miss_addr);
179
180    /**
181     * Checks if an access to the cache matches any active PT entry, if so,
182     * the indirect confidence counter is incremented
183     * @param addr address of the access
184     */
185    void checkAccessMatchOnActiveEntries(Addr addr);
186
187  public:
188    IndirectMemoryPrefetcher(const IndirectMemoryPrefetcherParams *p);
189    ~IndirectMemoryPrefetcher() {}
190
191    void calculatePrefetch(const PrefetchInfo &pfi,
192                           std::vector<AddrPriority> &addresses) override;
193};
194#endif//__MEM_CACHE_PREFETCH_INDIRECT_MEMORY_HH__
195