src/mem/cache/prefetch/bop.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 '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
  46 struct BOPPrefetcherParams;
  47
  48 class 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__ */