sbooe.hh revision 13735:52ab3bab4f28 
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 'Sandbox Based Optimal Offset Estimation'
33 * Reference:
34 *   Brown, N. T., & Sendag, R. Sandbox Based Optimal Offset Estimation.
35*/
36
37#ifndef __MEM_CACHE_PREFETCH_SBOOE_HH__
38#define __MEM_CACHE_PREFETCH_SBOOE_HH__
39
40#include <deque>
41#include <unordered_map>
42#include <vector>
43
44#include "mem/cache/prefetch/queued.hh"
45#include "mem/packet.hh"
46
47struct SBOOEPrefetcherParams;
48
49class SBOOEPrefetcher : public QueuedPrefetcher
50{
51    private:
52
53        /** Prefetcher parameters */
54        const int latencyBufferSize;
55        const int sequentialPrefetchers;
56
57        /** Threshold used to issue prefetchers */
58        const unsigned int scoreThreshold;
59
60        /**
61         * Holds the current demand addresses and tick. This is later used to
62         * calculate the average latency buffer when the address is filled in
63         * the cache.
64         */
65        std::unordered_map<Addr, Tick> demandAddresses;
66
67        /**
68         * The latency buffer holds the elapsed ticks between the demand and
69         * the fill in the cache for the latest N accesses which are used to
70         * calculate the average access latency which is later used to
71         * predict if a prefetcher would be filled on time if issued.
72         */
73        std::deque<Tick> latencyBuffer;
74
75        /** Holds the current average access latency */
76        Tick averageAccessLatency;
77
78        /** Holds the current sum of the latency buffer latency */
79        Tick latencyBufferSum;
80
81        struct SandboxEntry {
82            /** Cache line predicted by the candidate prefetcher */
83            Addr line;
84            /** Tick when the simulated prefetch is expected to be filled */
85            Tick expectedArrivalTick;
86            /** To indicate if it was initialized */
87            bool valid;
88
89            SandboxEntry()
90                : valid(false)
91            {}
92        };
93
94        struct Sandbox {
95            /** FIFO queue. Max entries is 'sandboxEntries' */
96            std::vector<SandboxEntry> entries;
97            /**
98             * Accesses during the eval period that were present
99             * in the sandbox
100             */
101            unsigned int sandboxScore;
102            /** Hits in the sandbox that wouldn't have been filled on time */
103            unsigned int lateScore;
104            /** Index of the oldest entry in the FIFO */
105            unsigned int index;
106            /** Sequential stride for this prefetcher */
107            const int stride;
108
109            Sandbox(unsigned int max_entries, int _stride)
110                : sandboxScore(0), lateScore(0), index(0), stride(_stride)
111            {
112                entries.resize(max_entries);
113            }
114
115            /**
116             * Insert the line address being accessed to the cache into the
117             * FIFO queue of the sandbox.
118             * @param line Line address being accessed
119             * @param tick Tick in which the access is expected to be filled
120             */
121            void insert(Addr line, Tick tick);
122
123            /** Calculate the useful score
124             *  @return Useful score of the sandbox. Sandbox score adjusted by
125             *          by the late score
126             */
127            unsigned int score() const {
128                return (sandboxScore - lateScore);
129            }
130        };
131
132        std::vector<Sandbox> sandboxes;
133
134        /** Current best sandbox */
135        Sandbox * bestSandbox;
136
137        /** Number of accesses notified to the prefetcher */
138        unsigned int accesses;
139
140        /**
141         * Process an access to the specified line address and update the
142         * sandbox counters counters.
143         * @param line Address of the line being accessed
144         * @return TRUE if the evaluation finished, FALSE otherwise
145         */
146        bool access(Addr line);
147
148        /** Update the latency buffer after a prefetch fill */
149        void notifyFill(const PacketPtr& pkt) override;
150
151    public:
152        SBOOEPrefetcher(const SBOOEPrefetcherParams *p);
153
154        void calculatePrefetch(const PrefetchInfo &pfi,
155                               std::vector<AddrPriority> &addresses) override;
156};
157
158#endif // __MEM_CACHE_PREFETCH_SBOOE_HH__
159