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 Access Map Pattern Matching Prefetcher
33  *
34  * References:
35  *     Access map pattern matching for high performance data cache prefetch.
36  *     Ishii, Y., Inaba, M., & Hiraki, K. (2011).
37  *     Journal of Instruction-Level Parallelism, 13, 1-24.
38  */
39
40#ifndef __MEM_CACHE_PREFETCH_ACCESS_MAP_PATTERN_MATCHING_HH__
41#define __MEM_CACHE_PREFETCH_ACCESS_MAP_PATTERN_MATCHING_HH__
42
43#include "mem/cache/prefetch/associative_set.hh"
44#include "mem/cache/prefetch/queued.hh"
45#include "mem/packet.hh"
46#include "sim/clocked_object.hh"
47
48struct AccessMapPatternMatchingParams;
49
50class AccessMapPatternMatching : public ClockedObject
51{
52    /** Cacheline size used by the prefetcher using this object */
53    const unsigned blkSize;
54    /** Limit the stride checking to -limitStride/+limitStride */
55    const unsigned limitStride;
56    /** Maximum number of prefetch generated */
57    const unsigned startDegree;
58    /** Amount of memory covered by a hot zone */
59    const uint64_t hotZoneSize;
60    /** A prefetch coverage factor bigger than this is considered high */
61    const double highCoverageThreshold;
62    /** A prefetch coverage factor smaller than this is considered low */
63    const double lowCoverageThreshold;
64    /** A prefetch accuracy factor bigger than this is considered high */
65    const double highAccuracyThreshold;
66    /** A prefetch accuracy factor smaller than this is considered low */
67    const double lowAccuracyThreshold;
68    /** A cache hit ratio bigger than this is considered high */
69    const double highCacheHitThreshold;
70    /** A cache hit ratio smaller than this is considered low */
71    const double lowCacheHitThreshold;
72    /** Cycles in an epoch period */
73    const Cycles epochCycles;
74    /** Off chip memory latency to use for the epoch bandwidth calculation */
75    const Tick offChipMemoryLatency;
76
77    /** Data type representing the state of a cacheline in the access map */
78    enum AccessMapState
79    {
80        AM_INIT,
81        AM_PREFETCH,
82        AM_ACCESS,
83        AM_INVALID
84    };
85
86    /** AccessMapEntry data type */
87    struct AccessMapEntry : public TaggedEntry
88    {
89        /** vector containing the state of the cachelines in this zone */
90        std::vector<AccessMapState> states;
91
92        AccessMapEntry(size_t num_entries) : states(num_entries, AM_INIT)
93        {}
94
95        /** Reset the entries to their initial values */
96        void reset() override
97        {
98            for (auto &entry : states) {
99                entry = AM_INIT;
100            }
101        }
102    };
103    /** Access map table */
104    AssociativeSet<AccessMapEntry> accessMapTable;
105
106    /**
107     * Number of good prefetches
108     * - State transitions from PREFETCH to ACCESS
109     */
110    uint64_t numGoodPrefetches;
111    /**
112     * Number of prefetches issued
113     * - State transitions from INIT to PREFETCH
114     */
115    uint64_t numTotalPrefetches;
116    /**
117     * Number of raw cache misses
118     * - State transitions from INIT or PREFETCH to ACCESS
119     */
120    uint64_t numRawCacheMisses;
121    /**
122     * Number of raw cache hits
123     * - State transitions from ACCESS to ACCESS
124     */
125    uint64_t numRawCacheHits;
126    /** Current degree */
127    unsigned degree;
128    /** Current useful degree */
129    unsigned usefulDegree;
130
131    /**
132     * Given a target cacheline, this function checks if the cachelines
133     * that follow the provided stride have been accessed. If so, the line
134     * is considered a good candidate.
135     * @param states vector containing the states of three contiguous hot zones
136     * @param current target block (cacheline)
137     * @param stride access stride to obtain the reference cachelines
138     * @return true if current is a prefetch candidate
139     */
140    inline bool checkCandidate(std::vector<AccessMapState> const &states,
141                        Addr current, int stride) const
142    {
143        enum AccessMapState tgt   = states[current - stride];
144        enum AccessMapState s     = states[current + stride];
145        enum AccessMapState s2    = states[current + 2 * stride];
146        enum AccessMapState s2_p1 = states[current + 2 * stride + 1];
147        return (tgt != AM_INVALID &&
148                ((s == AM_ACCESS && s2 == AM_ACCESS) ||
149                (s == AM_ACCESS && s2_p1 == AM_ACCESS)));
150    }
151
152    /**
153     * Obtain an AccessMapEntry  from the AccessMapTable, if the entry is not
154     * found a new one is initialized and inserted.
155     * @param am_addr address of the hot zone
156     * @param is_secure whether the address belongs to the secure memory area
157     * @return the corresponding entry
158     */
159    AccessMapEntry *getAccessMapEntry(Addr am_addr, bool is_secure);
160
161    /**
162     * Updates the state of a block within an AccessMapEntry, also updates
163     * the prefetcher metrics.
164     * @param entry AccessMapEntry to update
165     * @param block cacheline within the hot zone
166     * @param state new state
167     */
168    void setEntryState(AccessMapEntry &entry, Addr block,
169        enum AccessMapState state);
170
171    /**
172     * This event constitues the epoch of the statistics that keep track of
173     * the prefetcher accuracy, when this event triggers, the prefetcher degree
174     * is adjusted and the statistics counters are reset.
175     */
176    void processEpochEvent();
177    EventFunctionWrapper epochEvent;
178
179  public:
180    AccessMapPatternMatching(const AccessMapPatternMatchingParams* p);
181    ~AccessMapPatternMatching()
182    {}
183    void startup() override;
184    void calculatePrefetch(const BasePrefetcher::PrefetchInfo &pfi,
185        std::vector<QueuedPrefetcher::AddrPriority> &addresses);
186};
187
188struct AMPMPrefetcherParams;
189
190class AMPMPrefetcher : public QueuedPrefetcher
191{
192    AccessMapPatternMatching &ampm;
193  public:
194    AMPMPrefetcher(const AMPMPrefetcherParams* p);
195    ~AMPMPrefetcher()
196    {}
197    void calculatePrefetch(const PrefetchInfo &pfi,
198                           std::vector<AddrPriority> &addresses) override;
199};
200#endif//__MEM_CACHE_PREFETCH_ACCESS_MAP_PATTERN_MATCHING_HH__
201