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#ifndef __MEM_CACHE_PREFETCH_DELTA_CORRELATING_PREDICTION_TABLES_HH_
32#define __MEM_CACHE_PREFETCH_DELTA_CORRELATING_PREDICTION_TABLES_HH_
33
34#include "mem/cache/prefetch/associative_set.hh"
35#include "mem/cache/prefetch/queued.hh"
36
37struct DeltaCorrelatingPredictionTablesParams;
38
39/**
40 * Delta Correlating Prediction Tables Prefetcher
41 * References:
42 *   Multi-level hardware prefetching using low complexity delta correlating
43 *   prediction tables with partial matching.
44 *   Marius Grannaes, Magnus Jahre, and Lasse Natvig. 2010.
45 *   In Proceedings of the 5th international conference on High Performance
46 *   Embedded Architectures and Compilers (HiPEAC'10)
47 *
48 * The filter feature is not implemented as gem5 already drops redundant
49 * prefetches.
50 * The main prefetcher logic is implemented on a separate SimObject as there
51 * are other prefetcher that can rehuse this component.
52 */
53
54class DeltaCorrelatingPredictionTables : public SimObject
55{
56    /** Number of bits of each delta */
57    const unsigned int deltaBits;
58    /** Number of lower bits to ignore from the deltas */
59    const unsigned int deltaMaskBits;
60
61    /** DCPT Table entry datatype */
62    struct DCPTEntry : public TaggedEntry
63    {
64        /** Last accessed address */
65        Addr lastAddress;
66        /**
67        * Position of the first free entry, or the oldest element, if it is
68        * full
69        */
70        unsigned int deltaPointer;
71        /** Stored deltas */
72        std::vector<Addr> deltas;
73
74        /**
75         * Constructor
76         * @param num_deltas number of deltas stored in the entry
77         */
78        DCPTEntry(unsigned int num_deltas) : lastAddress(0), deltaPointer(0),
79            deltas(num_deltas)
80        {}
81
82        /** Reset callback called when invalidating the entry */
83        void reset() override;
84
85        /**
86         * Adds an address to the entry, if the entry already existed, a delta
87         * will be generated
88         * @param address address to add
89         * @param delta_num_bits number of bits of the delta
90         */
91        void addAddress(Addr address, unsigned int delta_num_bits);
92
93        /**
94         * Attempt to generate prefetch candidates using the two most recent
95         * deltas. Prefetch candidates are added to the provided vector.
96         * @param pfs reference to a vector where candidates will be added
97         * @param mask_bits the number of lower bits that should be masked
98         *        (ignored) when comparing deltas
99         */
100        void getCandidates(std::vector<QueuedPrefetcher::AddrPriority> &pfs,
101                           unsigned int mask_bits) const;
102
103    };
104    /** The main table */
105    AssociativeSet<DCPTEntry> table;
106
107  public:
108    DeltaCorrelatingPredictionTables(
109        DeltaCorrelatingPredictionTablesParams *p);
110    ~DeltaCorrelatingPredictionTables()
111    {}
112
113    /**
114     * Computes the prefetch candidates given a prefetch event.
115     * @param pfi The prefetch event information
116     * @param addresses prefetch candidates generated
117     */
118    void calculatePrefetch(const BasePrefetcher::PrefetchInfo &pfi,
119        std::vector<QueuedPrefetcher::AddrPriority> &addresses);
120
121};
122
123struct DCPTPrefetcherParams;
124
125/** The prefetcher object using the DCPT */
126class DCPTPrefetcher : public QueuedPrefetcher
127{
128    /** DCPT object */
129    DeltaCorrelatingPredictionTables &dcpt;
130  public:
131    DCPTPrefetcher(const DCPTPrefetcherParams *p);
132    ~DCPTPrefetcher()
133    {}
134    void calculatePrefetch(const PrefetchInfo &pfi,
135        std::vector<AddrPriority> &addresses) override;
136};
137#endif//__MEM_CACHE_PREFETCH_DELTA_CORRELATING_PREDICTION_TABLES_HH_
138