src/mem/cache/prefetch/stride.hh

   1 /*
   2  * Copyright (c) 2018 Inria
   3  * Copyright (c) 2012-2013, 2015 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) 2005 The Regents of The University of Michigan
  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 /**
  43  * @file
  44  * Describes a strided prefetcher.
  45  */
  46
  47 #ifndef __MEM_CACHE_PREFETCH_STRIDE_HH__
  48 #define __MEM_CACHE_PREFETCH_STRIDE_HH__
  49
  50 #include <string>
  51 #include <unordered_map>
  52 #include <vector>
  53
  54 #include "base/sat_counter.hh"
  55 #include "base/types.hh"
  56 #include "mem/cache/prefetch/associative_set.hh"
  57 #include "mem/cache/prefetch/queued.hh"
  58 #include "mem/cache/replacement_policies/replaceable_entry.hh"
  59 #include "mem/cache/tags/indexing_policies/set_associative.hh"
  60 #include "mem/packet.hh"
  61 #include "params/StridePrefetcherHashedSetAssociative.hh"
  62
  63 class BaseIndexingPolicy;
  64 class BaseReplacementPolicy;
  65 struct StridePrefetcherParams;
  66
  67 namespace Prefetcher {
  68
  69 /**
  70  * Override the default set associative to apply a specific hash function
  71  * when extracting a set.
  72  */
  73 class StridePrefetcherHashedSetAssociative : public SetAssociative
  74 {
  75   protected:
  76     uint32_t extractSet(const Addr addr) const override;
  77     Addr extractTag(const Addr addr) const override;
  78
  79   public:
  80     StridePrefetcherHashedSetAssociative(
  81         const StridePrefetcherHashedSetAssociativeParams *p)
  82       : SetAssociative(p)
  83     {
  84     }
  85     ~StridePrefetcherHashedSetAssociative() = default;
  86 };
  87
  88 class Stride : public Queued
  89 {
  90   protected:
  91     /** Initial confidence counter value for the pc tables. */
  92     const SatCounter initConfidence;
  93
  94     /** Confidence threshold for prefetch generation. */
  95     const double threshConf;
  96
  97     const bool useMasterId;
  98
  99     const int degree;
 100
 101     /**
 102      * Information used to create a new PC table. All of them behave equally.
 103      */
 104     const struct PCTableInfo
 105     {
 106         const int assoc;
 107         const int numEntries;
 108
 109         BaseIndexingPolicy* const indexingPolicy;
 110         BaseReplacementPolicy* const replacementPolicy;
 111
 112         PCTableInfo(int assoc, int num_entries,
 113             BaseIndexingPolicy* indexing_policy,
 114             BaseReplacementPolicy* replacement_policy)
 115           : assoc(assoc), numEntries(num_entries),
 116             indexingPolicy(indexing_policy),
 117             replacementPolicy(replacement_policy)
 118         {
 119         }
 120     } pcTableInfo;
 121
 122     /** Tagged by hashed PCs. */
 123     struct StrideEntry : public TaggedEntry
 124     {
 125         StrideEntry(const SatCounter& init_confidence);
 126
 127         void invalidate() override;
 128
 129         Addr lastAddr;
 130         int stride;
 131         SatCounter confidence;
 132     };
 133     typedef AssociativeSet<StrideEntry> PCTable;
 134     std::unordered_map<int, PCTable> pcTables;
 135
 136     /**
 137      * Try to find a table of entries for the given context. If none is
 138      * found, a new table is created.
 139      *
 140      * @param context The context to be searched for.
 141      * @return The table corresponding to the given context.
 142      */
 143     PCTable* findTable(int context);
 144
 145     /**
 146      * Create a PC table for the given context.
 147      *
 148      * @param context The context of the new PC table.
 149      * @return The new PC table
 150      */
 151     PCTable* allocateNewContext(int context);
 152
 153   public:
 154     Stride(const StridePrefetcherParams *p);
 155
 156     void calculatePrefetch(const PrefetchInfo &pfi,
 157                            std::vector<AddrPriority> &addresses) override;
 158 };
 159
 160 } // namespace Prefetcher
 161
 162 #endif // __MEM_CACHE_PREFETCH_STRIDE_HH__