Prefetcher.py revision 13963:94555f0223ba 
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
42from m5.SimObject import *
43from m5.params import *
44from m5.proxy import *
45
46from m5.objects.ClockedObject import ClockedObject
47from m5.objects.IndexingPolicies import *
48from m5.objects.ReplacementPolicies import *
49
50class 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
62class 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
102class 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
115class 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
138class 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
145class 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    num_indirect_counter_bits = Param.Unsigned(3,
160        "Number of bits 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
180class 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    num_counter_bits = Param.UInt8(3,
201        "Number of bits of the saturating counters")
202    pattern_table_entries = Param.MemorySize("4096",
203        "Number of entries of the pattern table")
204    pattern_table_assoc = Param.Unsigned(1,
205        "Associativity of the pattern table")
206    strides_per_pattern_entry = Param.Unsigned(4,
207        "Number of strides stored in each pattern entry")
208    pattern_table_indexing_policy = Param.BaseIndexingPolicy(
209        SetAssociative(entry_size = 1, assoc = Parent.pattern_table_assoc,
210        size = Parent.pattern_table_entries),
211        "Indexing policy of the pattern table")
212    pattern_table_replacement_policy = Param.BaseReplacementPolicy(LRURP(),
213        "Replacement policy of the pattern table")
214
215    prefetch_confidence_threshold = Param.Float(0.5,
216        "Minimum confidence to issue prefetches")
217    lookahead_confidence_threshold = Param.Float(0.75,
218        "Minimum confidence to continue exploring lookahead entries")
219
220class SignaturePathPrefetcherV2(SignaturePathPrefetcher):
221    type = 'SignaturePathPrefetcherV2'
222    cxx_class = 'SignaturePathPrefetcherV2'
223    cxx_header = "mem/cache/prefetch/signature_path_v2.hh"
224
225    signature_table_entries = "256"
226    signature_table_assoc = 1
227    pattern_table_entries = "512"
228    pattern_table_assoc = 1
229    num_counter_bits = 4
230    prefetch_confidence_threshold = 0.25
231    lookahead_confidence_threshold = 0.25
232
233    global_history_register_entries = Param.MemorySize("8",
234        "Number of entries of global history register")
235    global_history_register_indexing_policy = Param.BaseIndexingPolicy(
236        SetAssociative(entry_size = 1,
237        assoc = Parent.global_history_register_entries,
238        size = Parent.global_history_register_entries),
239        "Indexing policy of the global history register")
240    global_history_register_replacement_policy = Param.BaseReplacementPolicy(
241        LRURP(), "Replacement policy of the global history register")
242
243class AccessMapPatternMatching(ClockedObject):
244    type = 'AccessMapPatternMatching'
245    cxx_class = 'AccessMapPatternMatching'
246    cxx_header = "mem/cache/prefetch/access_map_pattern_matching.hh"
247
248    block_size = Param.Unsigned(Parent.block_size,
249        "Cacheline size used by the prefetcher using this object")
250
251    limit_stride = Param.Unsigned(0,
252        "Limit the strides checked up to -X/X, if 0, disable the limit")
253    start_degree = Param.Unsigned(4,
254        "Initial degree (Maximum number of prefetches generated")
255    hot_zone_size = Param.MemorySize("2kB", "Memory covered by a hot zone")
256    access_map_table_entries = Param.MemorySize("256",
257        "Number of entries in the access map table")
258    access_map_table_assoc = Param.Unsigned(8,
259        "Associativity of the access map table")
260    access_map_table_indexing_policy = Param.BaseIndexingPolicy(
261        SetAssociative(entry_size = 1, assoc = Parent.access_map_table_assoc,
262        size = Parent.access_map_table_entries),
263        "Indexing policy of the access map table")
264    access_map_table_replacement_policy = Param.BaseReplacementPolicy(LRURP(),
265        "Replacement policy of the access map table")
266    high_coverage_threshold = Param.Float(0.25,
267        "A prefetch coverage factor bigger than this is considered high")
268    low_coverage_threshold = Param.Float(0.125,
269        "A prefetch coverage factor smaller than this is considered low")
270    high_accuracy_threshold = Param.Float(0.5,
271        "A prefetch accuracy factor bigger than this is considered high")
272    low_accuracy_threshold = Param.Float(0.25,
273        "A prefetch accuracy factor smaller than this is considered low")
274    high_cache_hit_threshold = Param.Float(0.875,
275        "A cache hit ratio bigger than this is considered high")
276    low_cache_hit_threshold = Param.Float(0.75,
277        "A cache hit ratio smaller than this is considered low")
278    epoch_cycles = Param.Cycles(256000, "Cycles in an epoch period")
279    offchip_memory_latency = Param.Latency("30ns",
280        "Memory latency used to compute the required memory bandwidth")
281
282class AMPMPrefetcher(QueuedPrefetcher):
283    type = 'AMPMPrefetcher'
284    cxx_class = 'AMPMPrefetcher'
285    cxx_header = "mem/cache/prefetch/access_map_pattern_matching.hh"
286    ampm = Param.AccessMapPatternMatching( AccessMapPatternMatching(),
287        "Access Map Pattern Matching object")
288
289class DeltaCorrelatingPredictionTables(SimObject):
290    type = 'DeltaCorrelatingPredictionTables'
291    cxx_class = 'DeltaCorrelatingPredictionTables'
292    cxx_header = "mem/cache/prefetch/delta_correlating_prediction_tables.hh"
293    deltas_per_entry = Param.Unsigned(20,
294        "Number of deltas stored in each table entry")
295    delta_bits = Param.Unsigned(12, "Bits per delta")
296    delta_mask_bits = Param.Unsigned(8,
297        "Lower bits to mask when comparing deltas")
298    table_entries = Param.MemorySize("128",
299        "Number of entries in the table")
300    table_assoc = Param.Unsigned(128,
301        "Associativity of the table")
302    table_indexing_policy = Param.BaseIndexingPolicy(
303        SetAssociative(entry_size = 1, assoc = Parent.table_assoc,
304        size = Parent.table_entries),
305        "Indexing policy of the table")
306    table_replacement_policy = Param.BaseReplacementPolicy(LRURP(),
307        "Replacement policy of the table")
308
309class DCPTPrefetcher(QueuedPrefetcher):
310    type = 'DCPTPrefetcher'
311    cxx_class = 'DCPTPrefetcher'
312    cxx_header = "mem/cache/prefetch/delta_correlating_prediction_tables.hh"
313    dcpt = Param.DeltaCorrelatingPredictionTables(
314        DeltaCorrelatingPredictionTables(),
315        "Delta Correlating Prediction Tables object")
316
317class IrregularStreamBufferPrefetcher(QueuedPrefetcher):
318    type = "IrregularStreamBufferPrefetcher"
319    cxx_class = "IrregularStreamBufferPrefetcher"
320    cxx_header = "mem/cache/prefetch/irregular_stream_buffer.hh"
321
322    num_counter_bits = Param.Unsigned(2,
323        "Number of bits of the confidence counter")
324    chunk_size = Param.Unsigned(256,
325        "Maximum number of addresses in a temporal stream")
326    degree = Param.Unsigned(4, "Number of prefetches to generate")
327    training_unit_assoc = Param.Unsigned(128,
328        "Associativity of the training unit")
329    training_unit_entries = Param.MemorySize("128",
330        "Number of entries of the training unit")
331    training_unit_indexing_policy = Param.BaseIndexingPolicy(
332        SetAssociative(entry_size = 1, assoc = Parent.training_unit_assoc,
333        size = Parent.training_unit_entries),
334        "Indexing policy of the training unit")
335    training_unit_replacement_policy = Param.BaseReplacementPolicy(LRURP(),
336        "Replacement policy of the training unit")
337
338    prefetch_candidates_per_entry = Param.Unsigned(16,
339        "Number of prefetch candidates stored in a SP-AMC entry")
340    address_map_cache_assoc = Param.Unsigned(128,
341        "Associativity of the PS/SP AMCs")
342    address_map_cache_entries = Param.MemorySize("128",
343        "Number of entries of the PS/SP AMCs")
344    ps_address_map_cache_indexing_policy = Param.BaseIndexingPolicy(
345        SetAssociative(entry_size = 1,
346        assoc = Parent.address_map_cache_assoc,
347        size = Parent.address_map_cache_entries),
348        "Indexing policy of the Physical-to-Structural Address Map Cache")
349    ps_address_map_cache_replacement_policy = Param.BaseReplacementPolicy(
350        LRURP(),
351        "Replacement policy of the Physical-to-Structural Address Map Cache")
352    sp_address_map_cache_indexing_policy = Param.BaseIndexingPolicy(
353        SetAssociative(entry_size = 1,
354        assoc = Parent.address_map_cache_assoc,
355        size = Parent.address_map_cache_entries),
356        "Indexing policy of the Structural-to-Physical Address Mao Cache")
357    sp_address_map_cache_replacement_policy = Param.BaseReplacementPolicy(
358        LRURP(),
359        "Replacement policy of the Structural-to-Physical Address Map Cache")
360
361class SlimAccessMapPatternMatching(AccessMapPatternMatching):
362    start_degree = 2
363    limit_stride = 4
364
365class SlimDeltaCorrelatingPredictionTables(DeltaCorrelatingPredictionTables):
366    table_entries = "256"
367    table_assoc = 256
368    deltas_per_entry = 9
369
370class SlimAMPMPrefetcher(QueuedPrefetcher):
371    type = 'SlimAMPMPrefetcher'
372    cxx_class = 'SlimAMPMPrefetcher'
373    cxx_header = "mem/cache/prefetch/slim_ampm.hh"
374
375    ampm = Param.AccessMapPatternMatching(SlimAccessMapPatternMatching(),
376        "Access Map Pattern Matching object")
377    dcpt = Param.DeltaCorrelatingPredictionTables(
378        SlimDeltaCorrelatingPredictionTables(),
379        "Delta Correlating Prediction Tables object")
380
381class BOPPrefetcher(QueuedPrefetcher):
382    type = "BOPPrefetcher"
383    cxx_class = "BOPPrefetcher"
384    cxx_header = "mem/cache/prefetch/bop.hh"
385    score_max = Param.Unsigned(31, "Max. score to update the best offset")
386    round_max = Param.Unsigned(100, "Max. round to update the best offset")
387    bad_score = Param.Unsigned(10, "Score at which the HWP is disabled")
388    rr_size = Param.Unsigned(64, "Number of entries of each RR bank")
389    tag_bits = Param.Unsigned(12, "Bits used to store the tag")
390    offset_list_size = Param.Unsigned(46,
391                "Number of entries in the offsets list")
392    negative_offsets_enable = Param.Bool(True,
393                "Initialize the offsets list also with negative values \
394                (i.e. the table will have half of the entries with positive \
395                offsets and the other half with negative ones)")
396    delay_queue_enable = Param.Bool(True, "Enable the delay queue")
397    delay_queue_size = Param.Unsigned(15,
398                "Number of entries in the delay queue")
399    delay_queue_cycles = Param.Cycles(60,
400                "Cycles to delay a write in the left RR table from the delay \
401                queue")
402
403class SBOOEPrefetcher(QueuedPrefetcher):
404    type = 'SBOOEPrefetcher'
405    cxx_class = 'SBOOEPrefetcher'
406    cxx_header = "mem/cache/prefetch/sbooe.hh"
407    latency_buffer_size = Param.Int(32, "Entries in the latency buffer")
408    sequential_prefetchers = Param.Int(9, "Number of sequential prefetchers")
409    sandbox_entries = Param.Int(1024, "Size of the address buffer")
410    score_threshold_pct = Param.Percent(25, "Min. threshold to issue a \
411        prefetch. The value is the percentage of sandbox entries to use")
412
413class STeMSPrefetcher(QueuedPrefetcher):
414    type = "STeMSPrefetcher"
415    cxx_class = "STeMSPrefetcher"
416    cxx_header = "mem/cache/prefetch/spatio_temporal_memory_streaming.hh"
417
418    spatial_region_size = Param.MemorySize("2kB",
419        "Memory covered by a hot zone")
420    active_generation_table_entries = Param.MemorySize("64",
421        "Number of entries in the active generation table")
422    active_generation_table_assoc = Param.Unsigned(64,
423        "Associativity of the active generation table")
424    active_generation_table_indexing_policy = Param.BaseIndexingPolicy(
425        SetAssociative(entry_size = 1,
426            assoc = Parent.active_generation_table_assoc,
427            size = Parent.active_generation_table_entries),
428        "Indexing policy of the active generation table")
429    active_generation_table_replacement_policy = Param.BaseReplacementPolicy(
430        LRURP(), "Replacement policy of the active generation table")
431
432    pattern_sequence_table_entries = Param.MemorySize("16384",
433        "Number of entries in the pattern sequence table")
434    pattern_sequence_table_assoc = Param.Unsigned(16384,
435        "Associativity of the pattern sequence table")
436    pattern_sequence_table_indexing_policy = Param.BaseIndexingPolicy(
437        SetAssociative(entry_size = 1,
438            assoc = Parent.pattern_sequence_table_assoc,
439            size = Parent.pattern_sequence_table_entries),
440        "Indexing policy of the pattern sequence table")
441    pattern_sequence_table_replacement_policy = Param.BaseReplacementPolicy(
442        LRURP(), "Replacement policy of the pattern sequence table")
443
444    region_miss_order_buffer_entries = Param.Unsigned(131072,
445        "Number of entries of the Region Miss Order Buffer")
446    reconstruction_entries = Param.Unsigned(256,
447        "Number of reconstruction entries")
448
449class HWPProbeEventRetiredInsts(HWPProbeEvent):
450    def register(self):
451        if self.obj:
452            for name in self.names:
453                self.prefetcher.getCCObject().addEventProbeRetiredInsts(
454                    self.obj.getCCObject(), name)
455
456class PIFPrefetcher(QueuedPrefetcher):
457    type = 'PIFPrefetcher'
458    cxx_class = 'PIFPrefetcher'
459    cxx_header = "mem/cache/prefetch/pif.hh"
460    cxx_exports = [
461        PyBindMethod("addEventProbeRetiredInsts"),
462    ]
463
464    prec_spatial_region_bits = Param.Unsigned(2,
465        "Number of preceding addresses in the spatial region")
466    succ_spatial_region_bits = Param.Unsigned(8,
467        "Number of subsequent addresses in the spatial region")
468    compactor_entries = Param.Unsigned(2, "Entries in the temp. compactor")
469    stream_address_buffer_entries = Param.Unsigned(7, "Entries in the SAB")
470    history_buffer_size = Param.Unsigned(16, "Entries in the history buffer")
471
472    index_entries = Param.MemorySize("64",
473        "Number of entries in the index")
474    index_assoc = Param.Unsigned(64,
475        "Associativity of the index")
476    index_indexing_policy = Param.BaseIndexingPolicy(
477        SetAssociative(entry_size = 1, assoc = Parent.index_assoc,
478        size = Parent.index_entries),
479        "Indexing policy of the index")
480    index_replacement_policy = Param.BaseReplacementPolicy(LRURP(),
481        "Replacement policy of the index")
482
483    def listenFromProbeRetiredInstructions(self, simObj):
484        if not isinstance(simObj, SimObject):
485            raise TypeError("argument must be of SimObject type")
486        self.addEvent(HWPProbeEventRetiredInsts(self, simObj,"RetiredInstsPC"))
487