src/mem/ruby/structures/RubyPrefetcher.hh

   1 /*
   2  * Copyright (c) 2020 Inria
   3  * Copyright (c) 2020 ARM Limited
   4  * All rights reserved
   5  *
   6  * The license below extends only to copyright in the software and shall
   7  * not be construed as granting a license to any other intellectual
   8  * property including but not limited to intellectual property relating
   9  * to a hardware implementation of the functionality of the software
  10  * licensed hereunder.  You may use the software subject to the license
  11  * terms below provided that you ensure that this notice is replicated
  12  * unmodified and in its entirety in all distributions of the software,
  13  * modified or unmodified, in source code or in binary form.
  14  *
  15  * Copyright (c) 1999-2012 Mark D. Hill and David A. Wood
  16  * All rights reserved.
  17  *
  18  * Redistribution and use in source and binary forms, with or without
  19  * modification, are permitted provided that the following conditions are
  20  * met: redistributions of source code must retain the above copyright
  21  * notice, this list of conditions and the following disclaimer;
  22  * redistributions in binary form must reproduce the above copyright
  23  * notice, this list of conditions and the following disclaimer in the
  24  * documentation and/or other materials provided with the distribution;
  25  * neither the name of the copyright holders nor the names of its
  26  * contributors may be used to endorse or promote products derived from
  27  * this software without specific prior written permission.
  28  *
  29  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  30  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  31  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  32  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  33  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  34  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  35  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  36  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  37  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  38  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  39  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  40  */
  41
  42 #ifndef __MEM_RUBY_STRUCTURES_PREFETCHER_HH__
  43 #define __MEM_RUBY_STRUCTURES_PREFETCHER_HH__
  44
  45 // Implements Power 4 like prefetching
  46
  47 #include <bitset>
  48
  49 #include "base/circular_queue.hh"
  50 #include "base/statistics.hh"
  51 #include "mem/ruby/common/Address.hh"
  52 #include "mem/ruby/network/MessageBuffer.hh"
  53 #include "mem/ruby/slicc_interface/AbstractController.hh"
  54 #include "mem/ruby/slicc_interface/RubyRequest.hh"
  55 #include "mem/ruby/system/RubySystem.hh"
  56 #include "params/RubyPrefetcher.hh"
  57 #include "sim/sim_object.hh"
  58 #include "sim/system.hh"
  59
  60 #define MAX_PF_INFLIGHT 8
  61
  62 class PrefetchEntry
  63 {
  64     public:
  65         /// constructor
  66         PrefetchEntry()
  67         {
  68             // default: 1 cache-line stride
  69             m_stride   = (1 << RubySystem::getBlockSizeBits());
  70             m_use_time = Cycles(0);
  71             m_is_valid = false;
  72         }
  73
  74         //! The base address for the stream prefetch
  75         Addr m_address;
  76
  77         //! stride distance to get next address from
  78         int m_stride;
  79
  80         //! the last time that any prefetched request was used
  81         Cycles m_use_time;
  82
  83         //! valid bit for each stream
  84         bool m_is_valid;
  85
  86         //! L1D prefetches loads and stores
  87         RubyRequestType m_type;
  88
  89         //! Bitset for tracking prefetches for which addresses have been
  90         //! issued, which ones have completed.
  91         std::bitset<MAX_PF_INFLIGHT> requestIssued;
  92         std::bitset<MAX_PF_INFLIGHT> requestCompleted;
  93 };
  94
  95 class RubyPrefetcher : public SimObject
  96 {
  97     public:
  98         typedef RubyPrefetcherParams Params;
  99         RubyPrefetcher(const Params *p);
 100         ~RubyPrefetcher() = default;
 101
 102         void issueNextPrefetch(Addr address, PrefetchEntry *stream);
 103         /**
 104          * Implement the prefetch hit(miss) callback interface.
 105          * These functions are called by the cache when it hits(misses)
 106          * on a line with the line's prefetch bit set. If this address
 107          * hits in m_array we will continue prefetching the stream.
 108          */
 109         void observePfHit(Addr address);
 110         void observePfMiss(Addr address);
 111
 112         /**
 113          * Observe a memory miss from the cache.
 114          *
 115          * @param address   The physical address that missed out of the cache.
 116          */
 117         void observeMiss(Addr address, const RubyRequestType& type);
 118
 119         /**
 120          * Print out some statistics
 121          */
 122         void print(std::ostream& out) const;
 123         void setController(AbstractController *_ctrl)
 124         { m_controller = _ctrl; }
 125
 126         void regStats();
 127
 128     private:
 129         struct UnitFilterEntry
 130         {
 131             /** Address to which this filter entry refers. */
 132             Addr addr;
 133             /** Counter of the number of times this entry has been hit. */
 134             uint32_t hits;
 135
 136             UnitFilterEntry(Addr _addr = 0)
 137               : addr(_addr), hits(0)
 138             {
 139             }
 140         };
 141
 142         struct NonUnitFilterEntry : public UnitFilterEntry
 143         {
 144             /** Stride (in # of cache lines). */
 145             int stride;
 146
 147             NonUnitFilterEntry(Addr _addr = 0)
 148               : UnitFilterEntry(_addr), stride(0)
 149             {
 150             }
 151
 152             void
 153             clear()
 154             {
 155                 addr = 0;
 156                 stride = 0;
 157                 hits = 0;
 158             }
 159         };
 160
 161         /**
 162          * Returns an unused stream buffer (or if all are used, returns the
 163          * least recently used (accessed) stream buffer).
 164          * @return  The index of the least recently used stream buffer.
 165          */
 166         uint32_t getLRUindex(void);
 167
 168         //! allocate a new stream buffer at a specific index
 169         void initializeStream(Addr address, int stride,
 170             uint32_t index, const RubyRequestType& type);
 171
 172         //! get pointer to the matching stream entry, returns NULL if not found
 173         //! index holds the multiple of the stride this address is.
 174         PrefetchEntry* getPrefetchEntry(Addr address,
 175             uint32_t &index);
 176
 177         /**
 178          * Access a unit stride filter to determine if there is a hit, and
 179          * update it otherwise.
 180          *
 181          * @param filter Unit filter being accessed.
 182          * @param line_addr Address being accessed, block aligned.
 183          * @param stride The stride value.
 184          * @param type Type of the request that generated the access.
 185          * @return True if a corresponding entry was found.
 186          */
 187         bool accessUnitFilter(CircularQueue<UnitFilterEntry>* const filter,
 188             Addr line_addr, int stride, const RubyRequestType& type);
 189
 190         /**
 191          * Access a non-unit stride filter to determine if there is a hit, and
 192          * update it otherwise.
 193          *
 194          * @param line_addr Address being accessed, block aligned.
 195          * @param type Type of the request that generated the access.
 196          * @return True if a corresponding entry was found and its stride is
 197          *         not zero.
 198          */
 199         bool accessNonunitFilter(Addr line_addr, const RubyRequestType& type);
 200
 201         /// determine the page aligned address
 202         Addr pageAddress(Addr addr) const;
 203
 204         //! number of prefetch streams available
 205         uint32_t m_num_streams;
 206         //! an array of the active prefetch streams
 207         std::vector<PrefetchEntry> m_array;
 208
 209         //! number of misses I must see before allocating a stream
 210         uint32_t m_train_misses;
 211         //! number of initial prefetches to startup a stream
 212         uint32_t m_num_startup_pfs;
 213
 214         /**
 215          * A unit stride filter array: helps reduce BW requirement
 216          * of prefetching.
 217          */
 218         CircularQueue<UnitFilterEntry> unitFilter;
 219
 220         /**
 221          * A negative unit stride filter array: helps reduce BW requirement
 222          * of prefetching.
 223          */
 224         CircularQueue<UnitFilterEntry> negativeFilter;
 225
 226         /**
 227          * A non-unit stride filter array: helps reduce BW requirement of
 228          * prefetching.
 229          */
 230         CircularQueue<NonUnitFilterEntry> nonUnitFilter;
 231
 232         /// Used for allowing prefetches across pages.
 233         bool m_prefetch_cross_pages;
 234
 235         AbstractController *m_controller;
 236
 237         const Addr m_page_shift;
 238
 239         //! Count of accesses to the prefetcher
 240         Stats::Scalar numMissObserved;
 241         //! Count of prefetch streams allocated
 242         Stats::Scalar numAllocatedStreams;
 243         //! Count of prefetch requests made
 244         Stats::Scalar numPrefetchRequested;
 245         //! Count of successful prefetches
 246         Stats::Scalar numHits;
 247         //! Count of partial successful prefetches
 248         Stats::Scalar numPartialHits;
 249         //! Count of pages crossed
 250         Stats::Scalar numPagesCrossed;
 251         //! Count of misses incurred for blocks that were prefetched
 252         Stats::Scalar numMissedPrefetchedBlocks;
 253 };
 254
 255 #endif // __MEM_RUBY_STRUCTURES_PREFETCHER_HH__