src/mem/cache/prefetch/Prefetcher.py

   1 # Copyright (c) 2012, 2014 ARM Limited
   2 # All rights reserved.
   3 #
   4 # The license below extends only to copyright in the software and shall
   5 # not be construed as granting a license to any other intellectual
   6 # property including but not limited to intellectual property relating
   7 # to a hardware implementation of the functionality of the software
   8 # licensed hereunder.  You may use the software subject to the license
   9 # terms below provided that you ensure that this notice is replicated
  10 # unmodified and in its entirety in all distributions of the software,
  11 # modified or unmodified, in source code or in binary form.
  12 #
  13 # Copyright (c) 2005 The Regents of The University of Michigan
  14 # All rights reserved.
  15 #
  16 # Redistribution and use in source and binary forms, with or without
  17 # modification, are permitted provided that the following conditions are
  18 # met: redistributions of source code must retain the above copyright
  19 # notice, this list of conditions and the following disclaimer;
  20 # redistributions in binary form must reproduce the above copyright
  21 # notice, this list of conditions and the following disclaimer in the
  22 # documentation and/or other materials provided with the distribution;
  23 # neither the name of the copyright holders nor the names of its
  24 # contributors may be used to endorse or promote products derived from
  25 # this software without specific prior written permission.
  26 #
  27 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  28 # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  29 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  30 # A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  31 # OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  32 # SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  33 # LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  34 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  35 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  36 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  37 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  38 #
  39 # Authors: Ron Dreslinski
  40 #          Mitch Hayenga
  41
  42 from m5.SimObject import *
  43 from m5.params import *
  44 from m5.proxy import *
  45
  46 from m5.objects.ClockedObject import ClockedObject
  47 from m5.objects.IndexingPolicies import *
  48 from m5.objects.ReplacementPolicies import *
  49
  50 class HWPProbeEvent(object):
  51     def __init__(self, prefetcher, obj, *listOfNames):
  52         self.obj = obj
  53         self.prefetcher = prefetcher
  54         self.names = listOfNames
  55
  56     def register(self):
  57         if self.obj:
  58             for name in self.names:
  59                 self.prefetcher.getCCObject().addEventProbe(
  60                     self.obj.getCCObject(), name)
  61
  62 class BasePrefetcher(ClockedObject):
  63     type = 'BasePrefetcher'
  64     abstract = True
  65     cxx_header = "mem/cache/prefetch/base.hh"
  66     cxx_exports = [
  67         PyBindMethod("addEventProbe"),
  68     ]
  69     sys = Param.System(Parent.any, "System this prefetcher belongs to")
  70
  71     # Get the block size from the parent (system)
  72     block_size = Param.Int(Parent.cache_line_size, "Block size in bytes")
  73
  74     on_miss = Param.Bool(False, "Only notify prefetcher on misses")
  75     on_read = Param.Bool(True, "Notify prefetcher on reads")
  76     on_write = Param.Bool(True, "Notify prefetcher on writes")
  77     on_data  = Param.Bool(True, "Notify prefetcher on data accesses")
  78     on_inst  = Param.Bool(True, "Notify prefetcher on instruction accesses")
  79     prefetch_on_access = Param.Bool(Parent.prefetch_on_access,
  80         "Notify the hardware prefetcher on every access (not just misses)")
  81     use_virtual_addresses = Param.Bool(False,
  82         "Use virtual addresses for prefetching")
  83
  84     _events = []
  85     def addEvent(self, newObject):
  86         self._events.append(newObject)
  87
  88     # Override the normal SimObject::regProbeListeners method and
  89     # register deferred event handlers.
  90     def regProbeListeners(self):
  91         for event in self._events:
  92            event.register()
  93         self.getCCObject().regProbeListeners()
  94
  95     def listenFromProbe(self, simObj, *probeNames):
  96         if not isinstance(simObj, SimObject):
  97             raise TypeError("argument must be of SimObject type")
  98         if len(probeNames) <= 0:
  99             raise TypeError("probeNames must have at least one element")
 100         self.addEvent(HWPProbeEvent(self, simObj, *probeNames))
 101
 102 class QueuedPrefetcher(BasePrefetcher):
 103     type = "QueuedPrefetcher"
 104     abstract = True
 105     cxx_class = "QueuedPrefetcher"
 106     cxx_header = "mem/cache/prefetch/queued.hh"
 107     latency = Param.Int(1, "Latency for generated prefetches")
 108     queue_size = Param.Int(32, "Maximum number of queued prefetches")
 109     queue_squash = Param.Bool(True, "Squash queued prefetch on demand access")
 110     queue_filter = Param.Bool(True, "Don't queue redundant prefetches")
 111     cache_snoop = Param.Bool(False, "Snoop cache to eliminate redundant request")
 112
 113     tag_prefetch = Param.Bool(True, "Tag prefetch with PC of generating access")
 114
 115 class StridePrefetcher(QueuedPrefetcher):
 116     type = 'StridePrefetcher'
 117     cxx_class = 'StridePrefetcher'
 118     cxx_header = "mem/cache/prefetch/stride.hh"
 119
 120     # Do not consult stride prefetcher on instruction accesses
 121     on_inst = False
 122
 123     max_conf = Param.Int(7, "Maximum confidence level")
 124     thresh_conf = Param.Int(4, "Threshold confidence level")
 125     min_conf = Param.Int(0, "Minimum confidence level")
 126     start_conf = Param.Int(4, "Starting confidence for new entries")
 127
 128     table_sets = Param.Int(16, "Number of sets in PC lookup table")
 129     table_assoc = Param.Int(4, "Associativity of PC lookup table")
 130     use_master_id = Param.Bool(True, "Use master id based history")
 131
 132     degree = Param.Int(4, "Number of prefetches to generate")
 133
 134     # Get replacement policy
 135     replacement_policy = Param.BaseReplacementPolicy(RandomRP(),
 136         "Replacement policy")
 137
 138 class TaggedPrefetcher(QueuedPrefetcher):
 139     type = 'TaggedPrefetcher'
 140     cxx_class = 'TaggedPrefetcher'
 141     cxx_header = "mem/cache/prefetch/tagged.hh"
 142
 143     degree = Param.Int(2, "Number of prefetches to generate")
 144
 145 class SignaturePathPrefetcher(QueuedPrefetcher):
 146     type = 'SignaturePathPrefetcher'
 147     cxx_class = 'SignaturePathPrefetcher'
 148     cxx_header = "mem/cache/prefetch/signature_path.hh"
 149
 150     signature_shift = Param.UInt8(3,
 151         "Number of bits to shift when calculating a new signature");
 152     signature_bits = Param.UInt16(12,
 153         "Size of the signature, in bits");
 154     signature_table_entries = Param.MemorySize("1024",
 155         "Number of entries of the signature table")
 156     signature_table_assoc = Param.Unsigned(2,
 157         "Associativity of the signature table")
 158     signature_table_indexing_policy = Param.BaseIndexingPolicy(
 159         SetAssociative(entry_size = 1, assoc = Parent.signature_table_assoc,
 160         size = Parent.signature_table_entries),
 161         "Indexing policy of the signature table")
 162     signature_table_replacement_policy = Param.BaseReplacementPolicy(LRURP(),
 163         "Replacement policy of the signature table")
 164
 165     max_counter_value = Param.UInt8(7, "Maximum pattern counter value")
 166     pattern_table_entries = Param.MemorySize("4096",
 167         "Number of entries of the pattern table")
 168     pattern_table_assoc = Param.Unsigned(1,
 169         "Associativity of the pattern table")
 170     strides_per_pattern_entry = Param.Unsigned(4,
 171         "Number of strides stored in each pattern entry")
 172     pattern_table_indexing_policy = Param.BaseIndexingPolicy(
 173         SetAssociative(entry_size = 1, assoc = Parent.pattern_table_assoc,
 174         size = Parent.pattern_table_entries),
 175         "Indexing policy of the pattern table")
 176     pattern_table_replacement_policy = Param.BaseReplacementPolicy(LRURP(),
 177         "Replacement policy of the pattern table")
 178
 179     prefetch_confidence_threshold = Param.Float(0.5,
 180         "Minimum confidence to issue prefetches")
 181     lookahead_confidence_threshold = Param.Float(0.75,
 182         "Minimum confidence to continue exploring lookahead entries")
 183
 184 class SignaturePathPrefetcherV2(SignaturePathPrefetcher):
 185     type = 'SignaturePathPrefetcherV2'
 186     cxx_class = 'SignaturePathPrefetcherV2'
 187     cxx_header = "mem/cache/prefetch/signature_path_v2.hh"
 188
 189     signature_table_entries = "256"
 190     signature_table_assoc = 1
 191     pattern_table_entries = "512"
 192     pattern_table_assoc = 1
 193     max_counter_value = 15
 194     prefetch_confidence_threshold = 0.25
 195     lookahead_confidence_threshold = 0.25
 196
 197     global_history_register_entries = Param.MemorySize("8",
 198         "Number of entries of global history register")
 199     global_history_register_indexing_policy = Param.BaseIndexingPolicy(
 200         SetAssociative(entry_size = 1,
 201         assoc = Parent.global_history_register_entries,
 202         size = Parent.global_history_register_entries),
 203         "Indexing policy of the global history register")
 204     global_history_register_replacement_policy = Param.BaseReplacementPolicy(
 205         LRURP(), "Replacement policy of the global history register")
 206
 207 class AccessMapPatternMatching(ClockedObject):
 208     type = 'AccessMapPatternMatching'
 209     cxx_class = 'AccessMapPatternMatching'
 210     cxx_header = "mem/cache/prefetch/access_map_pattern_matching.hh"
 211
 212     block_size = Param.Unsigned(Parent.block_size,
 213         "Cacheline size used by the prefetcher using this object")
 214
 215     limit_stride = Param.Unsigned(0,
 216         "Limit the strides checked up to -X/X, if 0, disable the limit")
 217     start_degree = Param.Unsigned(4,
 218         "Initial degree (Maximum number of prefetches generated")
 219     hot_zone_size = Param.MemorySize("2kB", "Memory covered by a hot zone")
 220     access_map_table_entries = Param.MemorySize("256",
 221         "Number of entries in the access map table")
 222     access_map_table_assoc = Param.Unsigned(8,
 223         "Associativity of the access map table")
 224     access_map_table_indexing_policy = Param.BaseIndexingPolicy(
 225         SetAssociative(entry_size = 1, assoc = Parent.access_map_table_assoc,
 226         size = Parent.access_map_table_entries),
 227         "Indexing policy of the access map table")
 228     access_map_table_replacement_policy = Param.BaseReplacementPolicy(LRURP(),
 229         "Replacement policy of the access map table")
 230     high_coverage_threshold = Param.Float(0.25,
 231         "A prefetch coverage factor bigger than this is considered high")
 232     low_coverage_threshold = Param.Float(0.125,
 233         "A prefetch coverage factor smaller than this is considered low")
 234     high_accuracy_threshold = Param.Float(0.5,
 235         "A prefetch accuracy factor bigger than this is considered high")
 236     low_accuracy_threshold = Param.Float(0.25,
 237         "A prefetch accuracy factor smaller than this is considered low")
 238     high_cache_hit_threshold = Param.Float(0.875,
 239         "A cache hit ratio bigger than this is considered high")
 240     low_cache_hit_threshold = Param.Float(0.75,
 241         "A cache hit ratio smaller than this is considered low")
 242     epoch_cycles = Param.Cycles(256000, "Cycles in an epoch period")
 243     offchip_memory_latency = Param.Latency("30ns",
 244         "Memory latency used to compute the required memory bandwidth")
 245
 246 class AMPMPrefetcher(QueuedPrefetcher):
 247     type = 'AMPMPrefetcher'
 248     cxx_class = 'AMPMPrefetcher'
 249     cxx_header = "mem/cache/prefetch/access_map_pattern_matching.hh"
 250     ampm = Param.AccessMapPatternMatching( AccessMapPatternMatching(),
 251         "Access Map Pattern Matching object")
 252
 253 class DeltaCorrelatingPredictionTables(SimObject):
 254     type = 'DeltaCorrelatingPredictionTables'
 255     cxx_class = 'DeltaCorrelatingPredictionTables'
 256     cxx_header = "mem/cache/prefetch/delta_correlating_prediction_tables.hh"
 257     deltas_per_entry = Param.Unsigned(20,
 258         "Number of deltas stored in each table entry")
 259     delta_bits = Param.Unsigned(12, "Bits per delta")
 260     delta_mask_bits = Param.Unsigned(8,
 261         "Lower bits to mask when comparing deltas")
 262     table_entries = Param.MemorySize("128",
 263         "Number of entries in the table")
 264     table_assoc = Param.Unsigned(128,
 265         "Associativity of the table")
 266     table_indexing_policy = Param.BaseIndexingPolicy(
 267         SetAssociative(entry_size = 1, assoc = Parent.table_assoc,
 268         size = Parent.table_entries),
 269         "Indexing policy of the table")
 270     table_replacement_policy = Param.BaseReplacementPolicy(LRURP(),
 271         "Replacement policy of the table")
 272
 273 class DCPTPrefetcher(QueuedPrefetcher):
 274     type = 'DCPTPrefetcher'
 275     cxx_class = 'DCPTPrefetcher'
 276     cxx_header = "mem/cache/prefetch/delta_correlating_prediction_tables.hh"
 277     dcpt = Param.DeltaCorrelatingPredictionTables(
 278         DeltaCorrelatingPredictionTables(),
 279         "Delta Correlating Prediction Tables object")
 280
 281 class IrregularStreamBufferPrefetcher(QueuedPrefetcher):
 282     type = "IrregularStreamBufferPrefetcher"
 283     cxx_class = "IrregularStreamBufferPrefetcher"
 284     cxx_header = "mem/cache/prefetch/irregular_stream_buffer.hh"
 285
 286     max_counter_value = Param.Unsigned(3,
 287         "Maximum value of the confidence counter")
 288     chunk_size = Param.Unsigned(256,
 289         "Maximum number of addresses in a temporal stream")
 290     degree = Param.Unsigned(4, "Number of prefetches to generate")
 291     training_unit_assoc = Param.Unsigned(128,
 292         "Associativity of the training unit")
 293     training_unit_entries = Param.MemorySize("128",
 294         "Number of entries of the training unit")
 295     training_unit_indexing_policy = Param.BaseIndexingPolicy(
 296         SetAssociative(entry_size = 1, assoc = Parent.training_unit_assoc,
 297         size = Parent.training_unit_entries),
 298         "Indexing policy of the training unit")
 299     training_unit_replacement_policy = Param.BaseReplacementPolicy(LRURP(),
 300         "Replacement policy of the training unit")
 301
 302     prefetch_candidates_per_entry = Param.Unsigned(16,
 303         "Number of prefetch candidates stored in a SP-AMC entry")
 304     address_map_cache_assoc = Param.Unsigned(128,
 305         "Associativity of the PS/SP AMCs")
 306     address_map_cache_entries = Param.MemorySize("128",
 307         "Number of entries of the PS/SP AMCs")
 308     ps_address_map_cache_indexing_policy = Param.BaseIndexingPolicy(
 309         SetAssociative(entry_size = 1,
 310         assoc = Parent.address_map_cache_assoc,
 311         size = Parent.address_map_cache_entries),
 312         "Indexing policy of the Physical-to-Structural Address Map Cache")
 313     ps_address_map_cache_replacement_policy = Param.BaseReplacementPolicy(
 314         LRURP(),
 315         "Replacement policy of the Physical-to-Structural Address Map Cache")
 316     sp_address_map_cache_indexing_policy = Param.BaseIndexingPolicy(
 317         SetAssociative(entry_size = 1,
 318         assoc = Parent.address_map_cache_assoc,
 319         size = Parent.address_map_cache_entries),
 320         "Indexing policy of the Structural-to-Physical Address Mao Cache")
 321     sp_address_map_cache_replacement_policy = Param.BaseReplacementPolicy(
 322         LRURP(),
 323         "Replacement policy of the Structural-to-Physical Address Map Cache")
 324
 325 class SlimAccessMapPatternMatching(AccessMapPatternMatching):
 326     start_degree = 2
 327     limit_stride = 4
 328
 329 class SlimDeltaCorrelatingPredictionTables(DeltaCorrelatingPredictionTables):
 330     table_entries = "256"
 331     table_assoc = 256
 332     deltas_per_entry = 9
 333
 334 class SlimAMPMPrefetcher(QueuedPrefetcher):
 335     type = 'SlimAMPMPrefetcher'
 336     cxx_class = 'SlimAMPMPrefetcher'
 337     cxx_header = "mem/cache/prefetch/slim_ampm.hh"
 338
 339     ampm = Param.AccessMapPatternMatching(SlimAccessMapPatternMatching(),
 340         "Access Map Pattern Matching object")
 341     dcpt = Param.DeltaCorrelatingPredictionTables(
 342         SlimDeltaCorrelatingPredictionTables(),
 343         "Delta Correlating Prediction Tables object")