src/mem/cache/prefetch/sbooe.hh

   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
  47 struct SBOOEPrefetcherParams;
  48
  49 class 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__