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: Ivan Pizarro
29 */
30
31/**
32 * Implementation of the 'A Best-Offset Prefetcher'
33 * Reference:
34 *   Michaud, P. (2015, June). A best-offset prefetcher.
35 *   In 2nd Data Prefetching Championship.
36 */
37
38#ifndef __MEM_CACHE_PREFETCH_BOP_HH__
39#define __MEM_CACHE_PREFETCH_BOP_HH__
40
41#include <queue>
42
43#include "mem/cache/prefetch/queued.hh"
44#include "mem/packet.hh"
45
46struct BOPPrefetcherParams;
47
48class BOPPrefetcher : public QueuedPrefetcher
49{
50    private:
51
52        enum RRWay {
53            Left,
54            Right
55        };
56
57        /** Learning phase parameters */
58        const unsigned int scoreMax;
59        const unsigned int roundMax;
60        const unsigned int badScore;
61        /** Recent requests table parameteres */
62        const unsigned int rrEntries;
63        const unsigned int tagMask;
64        /** Delay queue parameters */
65        const bool         delayQueueEnabled;
66        const unsigned int delayQueueSize;
67        const unsigned int delayTicks;
68
69        std::vector<Addr> rrLeft;
70        std::vector<Addr> rrRight;
71
72        /** Structure to save the offset and the score */
73        typedef std::pair<int16_t, uint8_t> OffsetListEntry;
74        std::vector<OffsetListEntry> offsetsList;
75
76        /** In a first implementation of the BO prefetcher, both banks of the
77         *  RR were written simultaneously when a prefetched line is inserted
78         *  into the cache. Adding the delay queue tries to avoid always
79         *  striving for timeless prefetches, which has been found to not
80         *  always being optimal.
81         */
82        struct DelayQueueEntry
83        {
84            Addr baseAddr;
85            Tick processTick;
86
87            DelayQueueEntry(Addr x, Tick t) : baseAddr(x), processTick(t)
88            {}
89        };
90
91        std::deque<DelayQueueEntry> delayQueue;
92
93        /** Event to handle the delay queue processing */
94        void delayQueueEventWrapper();
95        EventFunctionWrapper delayQueueEvent;
96
97        /** Hardware prefetcher enabled */
98        bool issuePrefetchRequests;
99        /** Current best offset to issue prefetches */
100        Addr bestOffset;
101        /** Current best offset found in the learning phase */
102        Addr phaseBestOffset;
103        /** Current test offset index */
104        std::vector<OffsetListEntry>::iterator offsetsListIterator;
105        /** Max score found so far */
106        unsigned int bestScore;
107        /** Current round */
108        unsigned int round;
109
110        /** Generate a hash for the specified address to index the RR table
111         *  @param addr: address to hash
112         *  @param way:  RR table to which is addressed (left/right)
113         */
114        unsigned int hash(Addr addr, unsigned int way) const;
115
116        /** Insert the specified address into the RR table
117         *  @param addr: address to insert
118         *  @param way: RR table to which the address will be inserted
119         */
120        void insertIntoRR(Addr addr, unsigned int way);
121
122        /** Insert the specified address into the delay queue. This will
123         *  trigger an event after the delay cycles pass
124         *  @param addr: address to insert into the delay queue
125         */
126        void insertIntoDelayQueue(Addr addr);
127
128        /** Reset all the scores from the offset list */
129        void resetScores();
130
131        /** Generate the tag for the specified address based on the tag bits
132         *  and the block size
133         *  @param addr: address to get the tag from
134        */
135        Addr tag(Addr addr) const;
136
137        /** Test if @X-O is hitting in the RR table to update the
138            offset score */
139        bool testRR(Addr) const;
140
141        /** Learning phase of the BOP. Update the intermediate values of the
142            round and update the best offset if found */
143        void bestOffsetLearning(Addr);
144
145        /** Update the RR right table after a prefetch fill */
146        void notifyFill(const PacketPtr& pkt) override;
147
148    public:
149
150        BOPPrefetcher(const BOPPrefetcherParams *p);
151        ~BOPPrefetcher() {}
152
153        void calculatePrefetch(const PrefetchInfo &pfi,
154                               std::vector<AddrPriority> &addresses) override;
155};
156
157#endif /* __MEM_CACHE_PREFETCH_BOP_HH__ */
158