src/mem/cache/prefetch/irregular_stream_buffer.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
  29 /**
  30  * Implementation of the Irregular Stream Buffer prefetcher
  31  * Reference:
  32  *   Jain, A., & Lin, C. (2013, December). Linearizing irregular memory
  33  *   accesses for improved correlated prefetching. In Proceedings of the
  34  *   46th Annual IEEE/ACM International Symposium on Microarchitecture
  35  *   (pp. 247-259). ACM.
  36  */
  37
  38 #ifndef __MEM_CACHE_PREFETCH_IRREGULAR_STREAM_BUFFER_HH__
  39 #define __MEM_CACHE_PREFETCH_IRREGULAR_STREAM_BUFFER_HH__
  40
  41 #include "base/callback.hh"
  42 #include "base/sat_counter.hh"
  43 #include "mem/cache/prefetch/associative_set.hh"
  44 #include "mem/cache/prefetch/queued.hh"
  45
  46 struct IrregularStreamBufferPrefetcherParams;
  47
  48 namespace Prefetcher {
  49
  50 class IrregularStreamBuffer : public Queued
  51 {
  52     /** Size in bytes of a temporal stream */
  53     const size_t chunkSize;
  54     /** Number of prefetch candidates per Physical-to-Structural entry */
  55     const unsigned prefetchCandidatesPerEntry;
  56     /** Number of maximum prefetches requests created when predicting */
  57     const unsigned degree;
  58
  59     /**
  60      * Training Unit Entry datatype, it holds the last accessed address and
  61      * its secure flag
  62      */
  63     struct TrainingUnitEntry : public TaggedEntry {
  64         Addr lastAddress;
  65         bool lastAddressSecure;
  66     };
  67     /** Map of PCs to Training unit entries */
  68     AssociativeSet<TrainingUnitEntry> trainingUnit;
  69
  70     /** Address Mapping entry, holds an address and a confidence counter */
  71     struct AddressMapping {
  72         Addr address;
  73         SatCounter8 counter;
  74         AddressMapping(unsigned bits) : address(0), counter(bits)
  75         {}
  76     };
  77
  78     /**
  79      * Maps a set of contiguous addresses to another set of (not necessarily
  80      * contiguos) addresses, with their corresponding confidence counters
  81      */
  82     struct AddressMappingEntry : public TaggedEntry
  83     {
  84         std::vector<AddressMapping> mappings;
  85         AddressMappingEntry(size_t num_mappings, unsigned counter_bits)
  86           : TaggedEntry(), mappings(num_mappings, counter_bits)
  87         {
  88         }
  89
  90         void
  91         invalidate() override
  92         {
  93             TaggedEntry::invalidate();
  94             for (auto &entry : mappings) {
  95                 entry.address = 0;
  96                 entry.counter.reset();
  97             }
  98         }
  99     };
 100
 101     /** Physical-to-Structured mappings table */
 102     AssociativeSet<AddressMappingEntry> psAddressMappingCache;
 103     /** Structured-to-Physical mappings table */
 104     AssociativeSet<AddressMappingEntry> spAddressMappingCache;
 105     /**
 106      * Counter of allocated structural addresses, increased by "chunkSize",
 107      * each time a new structured address is allocated
 108      */
 109     uint64_t structuralAddressCounter;
 110
 111     /**
 112      * Add a mapping to the Structured-to-Physica mapping table
 113      * @param structuralAddress structural address
 114      * @param is_secure whether this page is inside the secure memory area
 115      * @param physical_address corresponding physical address
 116      */
 117     void addStructuralToPhysicalEntry(Addr structuralAddress, bool is_secure,
 118                                       Addr physical_address);
 119
 120     /**
 121      * Obtain the Physical-to-Structured mapping entry of the given physical
 122      * address. If the entry does not exist a new one is allocated, replacing
 123      * an existing one if needed.
 124      * @param paddr physical address
 125      * @param is_secure whether this page is inside the secure memory area
 126      * @result reference to the entry
 127      */
 128     AddressMapping& getPSMapping(Addr paddr, bool is_secure);
 129   public:
 130     IrregularStreamBuffer(const IrregularStreamBufferPrefetcherParams &p);
 131     ~IrregularStreamBuffer() = default;
 132
 133     void calculatePrefetch(const PrefetchInfo &pfi,
 134                            std::vector<AddrPriority> &addresses) override;
 135 };
 136
 137 } // namespace Prefetcher
 138
 139 #endif//__MEM_CACHE_PREFETCH_IRREGULAR_STREAM_BUFFER_HH__