113554Sjavier.bueno@metempsy.com/**
213554Sjavier.bueno@metempsy.com * Copyright (c) 2018 Metempsy Technology Consulting
313554Sjavier.bueno@metempsy.com * All rights reserved.
413554Sjavier.bueno@metempsy.com *
513554Sjavier.bueno@metempsy.com * Redistribution and use in source and binary forms, with or without
613554Sjavier.bueno@metempsy.com * modification, are permitted provided that the following conditions are
713554Sjavier.bueno@metempsy.com * met: redistributions of source code must retain the above copyright
813554Sjavier.bueno@metempsy.com * notice, this list of conditions and the following disclaimer;
913554Sjavier.bueno@metempsy.com * redistributions in binary form must reproduce the above copyright
1013554Sjavier.bueno@metempsy.com * notice, this list of conditions and the following disclaimer in the
1113554Sjavier.bueno@metempsy.com * documentation and/or other materials provided with the distribution;
1213554Sjavier.bueno@metempsy.com * neither the name of the copyright holders nor the names of its
1313554Sjavier.bueno@metempsy.com * contributors may be used to endorse or promote products derived from
1413554Sjavier.bueno@metempsy.com * this software without specific prior written permission.
1513554Sjavier.bueno@metempsy.com *
1613554Sjavier.bueno@metempsy.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1713554Sjavier.bueno@metempsy.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1813554Sjavier.bueno@metempsy.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1913554Sjavier.bueno@metempsy.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2013554Sjavier.bueno@metempsy.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2113554Sjavier.bueno@metempsy.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2213554Sjavier.bueno@metempsy.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2313554Sjavier.bueno@metempsy.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2413554Sjavier.bueno@metempsy.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2513554Sjavier.bueno@metempsy.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2613554Sjavier.bueno@metempsy.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2713554Sjavier.bueno@metempsy.com *
2813554Sjavier.bueno@metempsy.com * Authors: Javier Bueno
2913554Sjavier.bueno@metempsy.com */
3013554Sjavier.bueno@metempsy.com
3113554Sjavier.bueno@metempsy.com /**
3213554Sjavier.bueno@metempsy.com  * Implementation of the Access Map Pattern Matching Prefetcher
3313554Sjavier.bueno@metempsy.com  *
3413554Sjavier.bueno@metempsy.com  * References:
3513554Sjavier.bueno@metempsy.com  *     Access map pattern matching for high performance data cache prefetch.
3613554Sjavier.bueno@metempsy.com  *     Ishii, Y., Inaba, M., & Hiraki, K. (2011).
3713554Sjavier.bueno@metempsy.com  *     Journal of Instruction-Level Parallelism, 13, 1-24.
3813554Sjavier.bueno@metempsy.com  */
3913554Sjavier.bueno@metempsy.com
4013554Sjavier.bueno@metempsy.com#ifndef __MEM_CACHE_PREFETCH_ACCESS_MAP_PATTERN_MATCHING_HH__
4113554Sjavier.bueno@metempsy.com#define __MEM_CACHE_PREFETCH_ACCESS_MAP_PATTERN_MATCHING_HH__
4213554Sjavier.bueno@metempsy.com
4313554Sjavier.bueno@metempsy.com#include "mem/cache/prefetch/associative_set.hh"
4413554Sjavier.bueno@metempsy.com#include "mem/cache/prefetch/queued.hh"
4513554Sjavier.bueno@metempsy.com#include "mem/packet.hh"
4613700Sjavier.bueno@metempsy.com#include "sim/clocked_object.hh"
4713554Sjavier.bueno@metempsy.com
4813700Sjavier.bueno@metempsy.comstruct AccessMapPatternMatchingParams;
4913554Sjavier.bueno@metempsy.com
5013700Sjavier.bueno@metempsy.comclass AccessMapPatternMatching : public ClockedObject
5113554Sjavier.bueno@metempsy.com{
5213700Sjavier.bueno@metempsy.com    /** Cacheline size used by the prefetcher using this object */
5313700Sjavier.bueno@metempsy.com    const unsigned blkSize;
5413700Sjavier.bueno@metempsy.com    /** Limit the stride checking to -limitStride/+limitStride */
5513700Sjavier.bueno@metempsy.com    const unsigned limitStride;
5613554Sjavier.bueno@metempsy.com    /** Maximum number of prefetch generated */
5713554Sjavier.bueno@metempsy.com    const unsigned startDegree;
5813554Sjavier.bueno@metempsy.com    /** Amount of memory covered by a hot zone */
5913554Sjavier.bueno@metempsy.com    const uint64_t hotZoneSize;
6013554Sjavier.bueno@metempsy.com    /** A prefetch coverage factor bigger than this is considered high */
6113554Sjavier.bueno@metempsy.com    const double highCoverageThreshold;
6213554Sjavier.bueno@metempsy.com    /** A prefetch coverage factor smaller than this is considered low */
6313554Sjavier.bueno@metempsy.com    const double lowCoverageThreshold;
6413554Sjavier.bueno@metempsy.com    /** A prefetch accuracy factor bigger than this is considered high */
6513554Sjavier.bueno@metempsy.com    const double highAccuracyThreshold;
6613554Sjavier.bueno@metempsy.com    /** A prefetch accuracy factor smaller than this is considered low */
6713554Sjavier.bueno@metempsy.com    const double lowAccuracyThreshold;
6813554Sjavier.bueno@metempsy.com    /** A cache hit ratio bigger than this is considered high */
6913554Sjavier.bueno@metempsy.com    const double highCacheHitThreshold;
7013554Sjavier.bueno@metempsy.com    /** A cache hit ratio smaller than this is considered low */
7113554Sjavier.bueno@metempsy.com    const double lowCacheHitThreshold;
7213554Sjavier.bueno@metempsy.com    /** Cycles in an epoch period */
7313554Sjavier.bueno@metempsy.com    const Cycles epochCycles;
7413554Sjavier.bueno@metempsy.com    /** Off chip memory latency to use for the epoch bandwidth calculation */
7513554Sjavier.bueno@metempsy.com    const Tick offChipMemoryLatency;
7613554Sjavier.bueno@metempsy.com
7713554Sjavier.bueno@metempsy.com    /** Data type representing the state of a cacheline in the access map */
7813554Sjavier.bueno@metempsy.com    enum AccessMapState
7913554Sjavier.bueno@metempsy.com    {
8013554Sjavier.bueno@metempsy.com        AM_INIT,
8113554Sjavier.bueno@metempsy.com        AM_PREFETCH,
8213554Sjavier.bueno@metempsy.com        AM_ACCESS,
8313554Sjavier.bueno@metempsy.com        AM_INVALID
8413554Sjavier.bueno@metempsy.com    };
8513554Sjavier.bueno@metempsy.com
8613554Sjavier.bueno@metempsy.com    /** AccessMapEntry data type */
8713554Sjavier.bueno@metempsy.com    struct AccessMapEntry : public TaggedEntry
8813554Sjavier.bueno@metempsy.com    {
8913554Sjavier.bueno@metempsy.com        /** vector containing the state of the cachelines in this zone */
9013554Sjavier.bueno@metempsy.com        std::vector<AccessMapState> states;
9113554Sjavier.bueno@metempsy.com
9213554Sjavier.bueno@metempsy.com        AccessMapEntry(size_t num_entries) : states(num_entries, AM_INIT)
9313554Sjavier.bueno@metempsy.com        {}
9413554Sjavier.bueno@metempsy.com
9513554Sjavier.bueno@metempsy.com        /** Reset the entries to their initial values */
9613554Sjavier.bueno@metempsy.com        void reset() override
9713554Sjavier.bueno@metempsy.com        {
9813554Sjavier.bueno@metempsy.com            for (auto &entry : states) {
9913554Sjavier.bueno@metempsy.com                entry = AM_INIT;
10013554Sjavier.bueno@metempsy.com            }
10113554Sjavier.bueno@metempsy.com        }
10213554Sjavier.bueno@metempsy.com    };
10313554Sjavier.bueno@metempsy.com    /** Access map table */
10413554Sjavier.bueno@metempsy.com    AssociativeSet<AccessMapEntry> accessMapTable;
10513554Sjavier.bueno@metempsy.com
10613554Sjavier.bueno@metempsy.com    /**
10713554Sjavier.bueno@metempsy.com     * Number of good prefetches
10813554Sjavier.bueno@metempsy.com     * - State transitions from PREFETCH to ACCESS
10913554Sjavier.bueno@metempsy.com     */
11013554Sjavier.bueno@metempsy.com    uint64_t numGoodPrefetches;
11113554Sjavier.bueno@metempsy.com    /**
11213554Sjavier.bueno@metempsy.com     * Number of prefetches issued
11313554Sjavier.bueno@metempsy.com     * - State transitions from INIT to PREFETCH
11413554Sjavier.bueno@metempsy.com     */
11513554Sjavier.bueno@metempsy.com    uint64_t numTotalPrefetches;
11613554Sjavier.bueno@metempsy.com    /**
11713554Sjavier.bueno@metempsy.com     * Number of raw cache misses
11813554Sjavier.bueno@metempsy.com     * - State transitions from INIT or PREFETCH to ACCESS
11913554Sjavier.bueno@metempsy.com     */
12013554Sjavier.bueno@metempsy.com    uint64_t numRawCacheMisses;
12113554Sjavier.bueno@metempsy.com    /**
12213554Sjavier.bueno@metempsy.com     * Number of raw cache hits
12313554Sjavier.bueno@metempsy.com     * - State transitions from ACCESS to ACCESS
12413554Sjavier.bueno@metempsy.com     */
12513554Sjavier.bueno@metempsy.com    uint64_t numRawCacheHits;
12613554Sjavier.bueno@metempsy.com    /** Current degree */
12713554Sjavier.bueno@metempsy.com    unsigned degree;
12813554Sjavier.bueno@metempsy.com    /** Current useful degree */
12913554Sjavier.bueno@metempsy.com    unsigned usefulDegree;
13013554Sjavier.bueno@metempsy.com
13113554Sjavier.bueno@metempsy.com    /**
13213554Sjavier.bueno@metempsy.com     * Given a target cacheline, this function checks if the cachelines
13313554Sjavier.bueno@metempsy.com     * that follow the provided stride have been accessed. If so, the line
13413554Sjavier.bueno@metempsy.com     * is considered a good candidate.
13513554Sjavier.bueno@metempsy.com     * @param states vector containing the states of three contiguous hot zones
13613554Sjavier.bueno@metempsy.com     * @param current target block (cacheline)
13713554Sjavier.bueno@metempsy.com     * @param stride access stride to obtain the reference cachelines
13813554Sjavier.bueno@metempsy.com     * @return true if current is a prefetch candidate
13913554Sjavier.bueno@metempsy.com     */
14013554Sjavier.bueno@metempsy.com    inline bool checkCandidate(std::vector<AccessMapState> const &states,
14113554Sjavier.bueno@metempsy.com                        Addr current, int stride) const
14213554Sjavier.bueno@metempsy.com    {
14313554Sjavier.bueno@metempsy.com        enum AccessMapState tgt   = states[current - stride];
14413554Sjavier.bueno@metempsy.com        enum AccessMapState s     = states[current + stride];
14513554Sjavier.bueno@metempsy.com        enum AccessMapState s2    = states[current + 2 * stride];
14613554Sjavier.bueno@metempsy.com        enum AccessMapState s2_p1 = states[current + 2 * stride + 1];
14713554Sjavier.bueno@metempsy.com        return (tgt != AM_INVALID &&
14813554Sjavier.bueno@metempsy.com                ((s == AM_ACCESS && s2 == AM_ACCESS) ||
14913554Sjavier.bueno@metempsy.com                (s == AM_ACCESS && s2_p1 == AM_ACCESS)));
15013554Sjavier.bueno@metempsy.com    }
15113554Sjavier.bueno@metempsy.com
15213554Sjavier.bueno@metempsy.com    /**
15313554Sjavier.bueno@metempsy.com     * Obtain an AccessMapEntry  from the AccessMapTable, if the entry is not
15413554Sjavier.bueno@metempsy.com     * found a new one is initialized and inserted.
15513554Sjavier.bueno@metempsy.com     * @param am_addr address of the hot zone
15613554Sjavier.bueno@metempsy.com     * @param is_secure whether the address belongs to the secure memory area
15713554Sjavier.bueno@metempsy.com     * @return the corresponding entry
15813554Sjavier.bueno@metempsy.com     */
15913554Sjavier.bueno@metempsy.com    AccessMapEntry *getAccessMapEntry(Addr am_addr, bool is_secure);
16013554Sjavier.bueno@metempsy.com
16113554Sjavier.bueno@metempsy.com    /**
16213554Sjavier.bueno@metempsy.com     * Updates the state of a block within an AccessMapEntry, also updates
16313554Sjavier.bueno@metempsy.com     * the prefetcher metrics.
16413554Sjavier.bueno@metempsy.com     * @param entry AccessMapEntry to update
16513554Sjavier.bueno@metempsy.com     * @param block cacheline within the hot zone
16613554Sjavier.bueno@metempsy.com     * @param state new state
16713554Sjavier.bueno@metempsy.com     */
16813554Sjavier.bueno@metempsy.com    void setEntryState(AccessMapEntry &entry, Addr block,
16913554Sjavier.bueno@metempsy.com        enum AccessMapState state);
17013554Sjavier.bueno@metempsy.com
17113554Sjavier.bueno@metempsy.com    /**
17213554Sjavier.bueno@metempsy.com     * This event constitues the epoch of the statistics that keep track of
17313554Sjavier.bueno@metempsy.com     * the prefetcher accuracy, when this event triggers, the prefetcher degree
17413554Sjavier.bueno@metempsy.com     * is adjusted and the statistics counters are reset.
17513554Sjavier.bueno@metempsy.com     */
17613554Sjavier.bueno@metempsy.com    void processEpochEvent();
17713554Sjavier.bueno@metempsy.com    EventFunctionWrapper epochEvent;
17813554Sjavier.bueno@metempsy.com
17913554Sjavier.bueno@metempsy.com  public:
18013700Sjavier.bueno@metempsy.com    AccessMapPatternMatching(const AccessMapPatternMatchingParams* p);
18113700Sjavier.bueno@metempsy.com    ~AccessMapPatternMatching()
18213700Sjavier.bueno@metempsy.com    {}
18313832Sjavier.bueno@metempsy.com    void startup() override;
18413700Sjavier.bueno@metempsy.com    void calculatePrefetch(const BasePrefetcher::PrefetchInfo &pfi,
18513700Sjavier.bueno@metempsy.com        std::vector<QueuedPrefetcher::AddrPriority> &addresses);
18613700Sjavier.bueno@metempsy.com};
18713700Sjavier.bueno@metempsy.com
18813700Sjavier.bueno@metempsy.comstruct AMPMPrefetcherParams;
18913700Sjavier.bueno@metempsy.com
19013700Sjavier.bueno@metempsy.comclass AMPMPrefetcher : public QueuedPrefetcher
19113700Sjavier.bueno@metempsy.com{
19213700Sjavier.bueno@metempsy.com    AccessMapPatternMatching &ampm;
19313700Sjavier.bueno@metempsy.com  public:
19413700Sjavier.bueno@metempsy.com    AMPMPrefetcher(const AMPMPrefetcherParams* p);
19513700Sjavier.bueno@metempsy.com    ~AMPMPrefetcher()
19613700Sjavier.bueno@metempsy.com    {}
19713554Sjavier.bueno@metempsy.com    void calculatePrefetch(const PrefetchInfo &pfi,
19813554Sjavier.bueno@metempsy.com                           std::vector<AddrPriority> &addresses) override;
19913554Sjavier.bueno@metempsy.com};
20013554Sjavier.bueno@metempsy.com#endif//__MEM_CACHE_PREFETCH_ACCESS_MAP_PATTERN_MATCHING_HH__
201