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 IndirectMemoryPrefetcher(QueuedPrefetcher):
 146     type = 'IndirectMemoryPrefetcher'
 147     cxx_class = 'IndirectMemoryPrefetcher'
 148     cxx_header = "mem/cache/prefetch/indirect_memory.hh"
 149     pt_table_entries = Param.MemorySize("16",
 150         "Number of entries of the Prefetch Table")
 151     pt_table_assoc = Param.Unsigned(16, "Associativity of the Prefetch Table")
 152     pt_table_indexing_policy = Param.BaseIndexingPolicy(
 153         SetAssociative(entry_size = 1, assoc = Parent.pt_table_assoc,
 154         size = Parent.pt_table_entries),
 155         "Indexing policy of the pattern table")
 156     pt_table_replacement_policy = Param.BaseReplacementPolicy(LRURP(),
 157         "Replacement policy of the pattern table")
 158     max_prefetch_distance = Param.Unsigned(16, "Maximum prefetch distance")
 159     max_indirect_counter_value = Param.Unsigned(8,
 160         "Maximum value of the indirect counter")
 161     ipd_table_entries = Param.MemorySize("4",
 162         "Number of entries of the Indirect Pattern Detector")
 163     ipd_table_assoc = Param.Unsigned(4,
 164         "Associativity of the Indirect Pattern Detector")
 165     ipd_table_indexing_policy = Param.BaseIndexingPolicy(
 166         SetAssociative(entry_size = 1, assoc = Parent.ipd_table_assoc,
 167         size = Parent.ipd_table_entries),
 168         "Indexing policy of the Indirect Pattern Detector")
 169     ipd_table_replacement_policy = Param.BaseReplacementPolicy(LRURP(),
 170         "Replacement policy of the Indirect Pattern Detector")
 171     shift_values = VectorParam.Int([2, 3, 4, -3], "Shift values to evaluate")
 172     addr_array_len = Param.Unsigned(4, "Number of misses tracked")
 173     prefetch_threshold = Param.Unsigned(2,
 174         "Counter threshold to start the indirect prefetching")
 175     stream_counter_threshold = Param.Unsigned(4,
 176         "Counter threshold to enable the stream prefetcher")
 177     streaming_distance = Param.Unsigned(4,
 178         "Number of prefetches to generate when using the stream prefetcher")
 179
 180 class SignaturePathPrefetcher(QueuedPrefetcher):
 181     type = 'SignaturePathPrefetcher'
 182     cxx_class = 'SignaturePathPrefetcher'
 183     cxx_header = "mem/cache/prefetch/signature_path.hh"
 184
 185     signature_shift = Param.UInt8(3,
 186         "Number of bits to shift when calculating a new signature");
 187     signature_bits = Param.UInt16(12,
 188         "Size of the signature, in bits");
 189     signature_table_entries = Param.MemorySize("1024",
 190         "Number of entries of the signature table")
 191     signature_table_assoc = Param.Unsigned(2,
 192         "Associativity of the signature table")
 193     signature_table_indexing_policy = Param.BaseIndexingPolicy(
 194         SetAssociative(entry_size = 1, assoc = Parent.signature_table_assoc,
 195         size = Parent.signature_table_entries),
 196         "Indexing policy of the signature table")
 197     signature_table_replacement_policy = Param.BaseReplacementPolicy(LRURP(),
 198         "Replacement policy of the signature table")
 199
 200     max_counter_value = Param.UInt8(7, "Maximum pattern counter value")
 201     pattern_table_entries = Param.MemorySize("4096",
 202         "Number of entries of the pattern table")
 203     pattern_table_assoc = Param.Unsigned(1,
 204         "Associativity of the pattern table")
 205     strides_per_pattern_entry = Param.Unsigned(4,
 206         "Number of strides stored in each pattern entry")
 207     pattern_table_indexing_policy = Param.BaseIndexingPolicy(
 208         SetAssociative(entry_size = 1, assoc = Parent.pattern_table_assoc,
 209         size = Parent.pattern_table_entries),
 210         "Indexing policy of the pattern table")
 211     pattern_table_replacement_policy = Param.BaseReplacementPolicy(LRURP(),
 212         "Replacement policy of the pattern table")
 213
 214     prefetch_confidence_threshold = Param.Float(0.5,
 215         "Minimum confidence to issue prefetches")
 216     lookahead_confidence_threshold = Param.Float(0.75,
 217         "Minimum confidence to continue exploring lookahead entries")
 218
 219 class SignaturePathPrefetcherV2(SignaturePathPrefetcher):
 220     type = 'SignaturePathPrefetcherV2'
 221     cxx_class = 'SignaturePathPrefetcherV2'
 222     cxx_header = "mem/cache/prefetch/signature_path_v2.hh"
 223
 224     signature_table_entries = "256"
 225     signature_table_assoc = 1
 226     pattern_table_entries = "512"
 227     pattern_table_assoc = 1
 228     max_counter_value = 15
 229     prefetch_confidence_threshold = 0.25
 230     lookahead_confidence_threshold = 0.25
 231
 232     global_history_register_entries = Param.MemorySize("8",
 233         "Number of entries of global history register")
 234     global_history_register_indexing_policy = Param.BaseIndexingPolicy(
 235         SetAssociative(entry_size = 1,
 236         assoc = Parent.global_history_register_entries,
 237         size = Parent.global_history_register_entries),
 238         "Indexing policy of the global history register")
 239     global_history_register_replacement_policy = Param.BaseReplacementPolicy(
 240         LRURP(), "Replacement policy of the global history register")
 241
 242 class AccessMapPatternMatching(ClockedObject):
 243     type = 'AccessMapPatternMatching'
 244     cxx_class = 'AccessMapPatternMatching'
 245     cxx_header = "mem/cache/prefetch/access_map_pattern_matching.hh"
 246
 247     block_size = Param.Unsigned(Parent.block_size,
 248         "Cacheline size used by the prefetcher using this object")
 249
 250     limit_stride = Param.Unsigned(0,
 251         "Limit the strides checked up to -X/X, if 0, disable the limit")
 252     start_degree = Param.Unsigned(4,
 253         "Initial degree (Maximum number of prefetches generated")
 254     hot_zone_size = Param.MemorySize("2kB", "Memory covered by a hot zone")
 255     access_map_table_entries = Param.MemorySize("256",
 256         "Number of entries in the access map table")
 257     access_map_table_assoc = Param.Unsigned(8,
 258         "Associativity of the access map table")
 259     access_map_table_indexing_policy = Param.BaseIndexingPolicy(
 260         SetAssociative(entry_size = 1, assoc = Parent.access_map_table_assoc,
 261         size = Parent.access_map_table_entries),
 262         "Indexing policy of the access map table")
 263     access_map_table_replacement_policy = Param.BaseReplacementPolicy(LRURP(),
 264         "Replacement policy of the access map table")
 265     high_coverage_threshold = Param.Float(0.25,
 266         "A prefetch coverage factor bigger than this is considered high")
 267     low_coverage_threshold = Param.Float(0.125,
 268         "A prefetch coverage factor smaller than this is considered low")
 269     high_accuracy_threshold = Param.Float(0.5,
 270         "A prefetch accuracy factor bigger than this is considered high")
 271     low_accuracy_threshold = Param.Float(0.25,
 272         "A prefetch accuracy factor smaller than this is considered low")
 273     high_cache_hit_threshold = Param.Float(0.875,
 274         "A cache hit ratio bigger than this is considered high")
 275     low_cache_hit_threshold = Param.Float(0.75,
 276         "A cache hit ratio smaller than this is considered low")
 277     epoch_cycles = Param.Cycles(256000, "Cycles in an epoch period")
 278     offchip_memory_latency = Param.Latency("30ns",
 279         "Memory latency used to compute the required memory bandwidth")
 280
 281 class AMPMPrefetcher(QueuedPrefetcher):
 282     type = 'AMPMPrefetcher'
 283     cxx_class = 'AMPMPrefetcher'
 284     cxx_header = "mem/cache/prefetch/access_map_pattern_matching.hh"
 285     ampm = Param.AccessMapPatternMatching( AccessMapPatternMatching(),
 286         "Access Map Pattern Matching object")
 287
 288 class DeltaCorrelatingPredictionTables(SimObject):
 289     type = 'DeltaCorrelatingPredictionTables'
 290     cxx_class = 'DeltaCorrelatingPredictionTables'
 291     cxx_header = "mem/cache/prefetch/delta_correlating_prediction_tables.hh"
 292     deltas_per_entry = Param.Unsigned(20,
 293         "Number of deltas stored in each table entry")
 294     delta_bits = Param.Unsigned(12, "Bits per delta")
 295     delta_mask_bits = Param.Unsigned(8,
 296         "Lower bits to mask when comparing deltas")
 297     table_entries = Param.MemorySize("128",
 298         "Number of entries in the table")
 299     table_assoc = Param.Unsigned(128,
 300         "Associativity of the table")
 301     table_indexing_policy = Param.BaseIndexingPolicy(
 302         SetAssociative(entry_size = 1, assoc = Parent.table_assoc,
 303         size = Parent.table_entries),
 304         "Indexing policy of the table")
 305     table_replacement_policy = Param.BaseReplacementPolicy(LRURP(),
 306         "Replacement policy of the table")
 307
 308 class DCPTPrefetcher(QueuedPrefetcher):
 309     type = 'DCPTPrefetcher'
 310     cxx_class = 'DCPTPrefetcher'
 311     cxx_header = "mem/cache/prefetch/delta_correlating_prediction_tables.hh"
 312     dcpt = Param.DeltaCorrelatingPredictionTables(
 313         DeltaCorrelatingPredictionTables(),
 314         "Delta Correlating Prediction Tables object")
 315
 316 class IrregularStreamBufferPrefetcher(QueuedPrefetcher):
 317     type = "IrregularStreamBufferPrefetcher"
 318     cxx_class = "IrregularStreamBufferPrefetcher"
 319     cxx_header = "mem/cache/prefetch/irregular_stream_buffer.hh"
 320
 321     max_counter_value = Param.Unsigned(3,
 322         "Maximum value of the confidence counter")
 323     chunk_size = Param.Unsigned(256,
 324         "Maximum number of addresses in a temporal stream")
 325     degree = Param.Unsigned(4, "Number of prefetches to generate")
 326     training_unit_assoc = Param.Unsigned(128,
 327         "Associativity of the training unit")
 328     training_unit_entries = Param.MemorySize("128",
 329         "Number of entries of the training unit")
 330     training_unit_indexing_policy = Param.BaseIndexingPolicy(
 331         SetAssociative(entry_size = 1, assoc = Parent.training_unit_assoc,
 332         size = Parent.training_unit_entries),
 333         "Indexing policy of the training unit")
 334     training_unit_replacement_policy = Param.BaseReplacementPolicy(LRURP(),
 335         "Replacement policy of the training unit")
 336
 337     prefetch_candidates_per_entry = Param.Unsigned(16,
 338         "Number of prefetch candidates stored in a SP-AMC entry")
 339     address_map_cache_assoc = Param.Unsigned(128,
 340         "Associativity of the PS/SP AMCs")
 341     address_map_cache_entries = Param.MemorySize("128",
 342         "Number of entries of the PS/SP AMCs")
 343     ps_address_map_cache_indexing_policy = Param.BaseIndexingPolicy(
 344         SetAssociative(entry_size = 1,
 345         assoc = Parent.address_map_cache_assoc,
 346         size = Parent.address_map_cache_entries),
 347         "Indexing policy of the Physical-to-Structural Address Map Cache")
 348     ps_address_map_cache_replacement_policy = Param.BaseReplacementPolicy(
 349         LRURP(),
 350         "Replacement policy of the Physical-to-Structural Address Map Cache")
 351     sp_address_map_cache_indexing_policy = Param.BaseIndexingPolicy(
 352         SetAssociative(entry_size = 1,
 353         assoc = Parent.address_map_cache_assoc,
 354         size = Parent.address_map_cache_entries),
 355         "Indexing policy of the Structural-to-Physical Address Mao Cache")
 356     sp_address_map_cache_replacement_policy = Param.BaseReplacementPolicy(
 357         LRURP(),
 358         "Replacement policy of the Structural-to-Physical Address Map Cache")
 359
 360 class SlimAccessMapPatternMatching(AccessMapPatternMatching):
 361     start_degree = 2
 362     limit_stride = 4
 363
 364 class SlimDeltaCorrelatingPredictionTables(DeltaCorrelatingPredictionTables):
 365     table_entries = "256"
 366     table_assoc = 256
 367     deltas_per_entry = 9
 368
 369 class SlimAMPMPrefetcher(QueuedPrefetcher):
 370     type = 'SlimAMPMPrefetcher'
 371     cxx_class = 'SlimAMPMPrefetcher'
 372     cxx_header = "mem/cache/prefetch/slim_ampm.hh"
 373
 374     ampm = Param.AccessMapPatternMatching(SlimAccessMapPatternMatching(),
 375         "Access Map Pattern Matching object")
 376     dcpt = Param.DeltaCorrelatingPredictionTables(
 377         SlimDeltaCorrelatingPredictionTables(),
 378         "Delta Correlating Prediction Tables object")
 379
 380 class BOPPrefetcher(QueuedPrefetcher):
 381     type = "BOPPrefetcher"
 382     cxx_class = "BOPPrefetcher"
 383     cxx_header = "mem/cache/prefetch/bop.hh"
 384     score_max = Param.Unsigned(31, "Max. score to update the best offset")
 385     round_max = Param.Unsigned(100, "Max. round to update the best offset")
 386     bad_score = Param.Unsigned(10, "Score at which the HWP is disabled")
 387     rr_size = Param.Unsigned(64, "Number of entries of each RR bank")
 388     tag_bits = Param.Unsigned(12, "Bits used to store the tag")
 389     offset_list_size = Param.Unsigned(46,
 390                 "Number of entries in the offsets list")
 391     negative_offsets_enable = Param.Bool(True,
 392                 "Initialize the offsets list also with negative values \
 393                 (i.e. the table will have half of the entries with positive \
 394                 offsets and the other half with negative ones)")
 395     delay_queue_enable = Param.Bool(True, "Enable the delay queue")
 396     delay_queue_size = Param.Unsigned(15,
 397                 "Number of entries in the delay queue")
 398     delay_queue_cycles = Param.Cycles(60,
 399                 "Cycles to delay a write in the left RR table from the delay \
 400                 queue")
 401
 402 class SBOOEPrefetcher(QueuedPrefetcher):
 403     type = 'SBOOEPrefetcher'
 404     cxx_class = 'SBOOEPrefetcher'
 405     cxx_header = "mem/cache/prefetch/sbooe.hh"
 406     latency_buffer_size = Param.Int(32, "Entries in the latency buffer")
 407     sequential_prefetchers = Param.Int(9, "Number of sequential prefetchers")
 408     sandbox_entries = Param.Int(1024, "Size of the address buffer")
 409     score_threshold_pct = Param.Percent(25, "Min. threshold to issue a \
 410         prefetch. The value is the percentage of sandbox entries to use")