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