BranchPredictor.py revision 13810:f50e3b82df73 
1# Copyright (c) 2012 Mark D. Hill and David A. Wood
2# Copyright (c) 2015 The University of Wisconsin
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# Authors: Nilay Vaish and Dibakar Gope
29
30from m5.SimObject import SimObject
31from m5.params import *
32from m5.proxy import *
33
34class BranchPredictor(SimObject):
35    type = 'BranchPredictor'
36    cxx_class = 'BPredUnit'
37    cxx_header = "cpu/pred/bpred_unit.hh"
38    abstract = True
39
40    numThreads = Param.Unsigned(Parent.numThreads, "Number of threads")
41    BTBEntries = Param.Unsigned(4096, "Number of BTB entries")
42    BTBTagSize = Param.Unsigned(16, "Size of the BTB tags, in bits")
43    RASSize = Param.Unsigned(16, "RAS size")
44    instShiftAmt = Param.Unsigned(2, "Number of bits to shift instructions by")
45
46    useIndirect = Param.Bool(True, "Use indirect branch predictor")
47    indirectHashGHR = Param.Bool(True, "Hash branch predictor GHR")
48    indirectHashTargets = Param.Bool(True, "Hash path history targets")
49    indirectSets = Param.Unsigned(256, "Cache sets for indirect predictor")
50    indirectWays = Param.Unsigned(2, "Ways for indirect predictor")
51    indirectTagSize = Param.Unsigned(16, "Indirect target cache tag bits")
52    indirectPathLength = Param.Unsigned(3,
53        "Previous indirect targets to use for path history")
54    indirectGHRBits = Param.Unsigned(13, "Indirect GHR number of bits")
55
56
57
58class LocalBP(BranchPredictor):
59    type = 'LocalBP'
60    cxx_class = 'LocalBP'
61    cxx_header = "cpu/pred/2bit_local.hh"
62
63    localPredictorSize = Param.Unsigned(2048, "Size of local predictor")
64    localCtrBits = Param.Unsigned(2, "Bits per counter")
65
66
67class TournamentBP(BranchPredictor):
68    type = 'TournamentBP'
69    cxx_class = 'TournamentBP'
70    cxx_header = "cpu/pred/tournament.hh"
71
72    localPredictorSize = Param.Unsigned(2048, "Size of local predictor")
73    localCtrBits = Param.Unsigned(2, "Bits per counter")
74    localHistoryTableSize = Param.Unsigned(2048, "size of local history table")
75    globalPredictorSize = Param.Unsigned(8192, "Size of global predictor")
76    globalCtrBits = Param.Unsigned(2, "Bits per counter")
77    choicePredictorSize = Param.Unsigned(8192, "Size of choice predictor")
78    choiceCtrBits = Param.Unsigned(2, "Bits of choice counters")
79
80
81class BiModeBP(BranchPredictor):
82    type = 'BiModeBP'
83    cxx_class = 'BiModeBP'
84    cxx_header = "cpu/pred/bi_mode.hh"
85
86    globalPredictorSize = Param.Unsigned(8192, "Size of global predictor")
87    globalCtrBits = Param.Unsigned(2, "Bits per counter")
88    choicePredictorSize = Param.Unsigned(8192, "Size of choice predictor")
89    choiceCtrBits = Param.Unsigned(2, "Bits of choice counters")
90
91class TAGEBase(SimObject):
92    type = 'TAGEBase'
93    cxx_class = 'TAGEBase'
94    cxx_header = "cpu/pred/tage_base.hh"
95
96    numThreads = Param.Unsigned(Parent.numThreads, "Number of threads")
97    instShiftAmt = Param.Unsigned(Parent.instShiftAmt,
98        "Number of bits to shift instructions by")
99
100    nHistoryTables = Param.Unsigned(7, "Number of history tables")
101    minHist = Param.Unsigned(5, "Minimum history size of TAGE")
102    maxHist = Param.Unsigned(130, "Maximum history size of TAGE")
103
104    tagTableTagWidths = VectorParam.Unsigned(
105        [0, 9, 9, 10, 10, 11, 11, 12], "Tag size in TAGE tag tables")
106    logTagTableSizes = VectorParam.Int(
107        [13, 9, 9, 9, 9, 9, 9, 9], "Log2 of TAGE table sizes")
108    logRatioBiModalHystEntries = Param.Unsigned(2,
109        "Log num of prediction entries for a shared hysteresis bit " \
110        "for the Bimodal")
111
112    tagTableCounterBits = Param.Unsigned(3, "Number of tag table counter bits")
113    tagTableUBits = Param.Unsigned(2, "Number of tag table u bits")
114
115    histBufferSize = Param.Unsigned(2097152,
116            "A large number to track all branch histories(2MEntries default)")
117
118    pathHistBits = Param.Unsigned(16, "Path history size")
119    logUResetPeriod = Param.Unsigned(18,
120        "Log period in number of branches to reset TAGE useful counters")
121    numUseAltOnNa = Param.Unsigned(1, "Number of USE_ALT_ON_NA counters")
122    useAltOnNaBits = Param.Unsigned(4, "Size of the USE_ALT_ON_NA counter(s)")
123
124    maxNumAlloc = Param.Unsigned(1,
125        "Max number of TAGE entries allocted on mispredict")
126
127    # List of enabled TAGE tables. If empty, all are enabled
128    noSkip = VectorParam.Bool([], "Vector of enabled TAGE tables")
129
130    speculativeHistUpdate = Param.Bool(True,
131        "Use speculative update for histories")
132
133# TAGE branch predictor as described in https://www.jilp.org/vol8/v8paper1.pdf
134# The default sizes below are for the 8C-TAGE configuration (63.5 Kbits)
135class TAGE(BranchPredictor):
136    type = 'TAGE'
137    cxx_class = 'TAGE'
138    cxx_header = "cpu/pred/tage.hh"
139    tage = Param.TAGEBase(TAGEBase(), "Tage object")
140
141class LTAGE_TAGE(TAGEBase):
142    nHistoryTables = 12
143    minHist = 4
144    maxHist = 640
145    tagTableTagWidths = [0, 7, 7, 8, 8, 9, 10, 11, 12, 12, 13, 14, 15]
146    logTagTableSizes = [14, 10, 10, 11, 11, 11, 11, 10, 10, 10, 10, 9, 9]
147    logUResetPeriod = 19
148
149class LoopPredictor(SimObject):
150    type = 'LoopPredictor'
151    cxx_class = 'LoopPredictor'
152    cxx_header = 'cpu/pred/loop_predictor.hh'
153
154    logSizeLoopPred = Param.Unsigned(8, "Log size of the loop predictor")
155    withLoopBits = Param.Unsigned(7, "Size of the WITHLOOP counter")
156    loopTableAgeBits = Param.Unsigned(8, "Number of age bits per loop entry")
157    loopTableConfidenceBits = Param.Unsigned(2,
158            "Number of confidence bits per loop entry")
159    loopTableTagBits = Param.Unsigned(14, "Number of tag bits per loop entry")
160    loopTableIterBits = Param.Unsigned(14, "Nuber of iteration bits per loop")
161    logLoopTableAssoc = Param.Unsigned(2, "Log loop predictor associativity")
162
163    # Parameters for enabling modifications to the loop predictor
164    # They have been copied from TAGE-GSC-IMLI
165    # (http://www.irisa.fr/alf/downloads/seznec/TAGE-GSC-IMLI.tar)
166    #
167    # All of them should be disabled to match the original LTAGE implementation
168    # (http://hpca23.cse.tamu.edu/taco/camino/cbp2/cbp-src/realistic-seznec.h)
169
170    # Add speculation
171    useSpeculation = Param.Bool(False, "Use speculation")
172
173    # Add hashing for calculating the loop table index
174    useHashing = Param.Bool(False, "Use hashing")
175
176    # Add a direction bit to the loop table entries
177    useDirectionBit = Param.Bool(False, "Use direction info")
178
179    # If true, use random to decide whether to allocate or not, and only try
180    # with one entry
181    restrictAllocation = Param.Bool(False,
182        "Restrict the allocation conditions")
183
184    initialLoopIter = Param.Unsigned(1, "Initial iteration number")
185    initialLoopAge = Param.Unsigned(255, "Initial age value")
186    optionalAgeReset = Param.Bool(True,
187        "Reset age bits optionally in some cases")
188
189class TAGE_SC_L_TAGE(TAGEBase):
190    type = 'TAGE_SC_L_TAGE'
191    cxx_class = 'TAGE_SC_L_TAGE'
192    cxx_header = "cpu/pred/tage_sc_l.hh"
193    abstract = True
194    tagTableTagWidths = [0]
195    numUseAltOnNa = 16
196    pathHistBits = 27
197    maxNumAlloc = 2
198    logUResetPeriod = 10
199    useAltOnNaBits = 5
200    # TODO No speculation implemented as of now
201    speculativeHistUpdate = False
202
203    # This size does not set the final sizes of the tables (it is just used
204    # for some calculations)
205    # Instead, the number of TAGE entries comes from shortTagsTageEntries and
206    # longTagsTageEntries
207    logTagTableSize = Param.Unsigned("Log size of each tag table")
208
209    shortTagsTageFactor = Param.Unsigned(
210        "Factor for calculating the total number of short tags TAGE entries")
211
212    longTagsTageFactor = Param.Unsigned(
213        "Factor for calculating the total number of long tags TAGE entries")
214
215    shortTagsSize = Param.Unsigned(8, "Size of the short tags")
216
217    longTagsSize = Param.Unsigned("Size of the long tags")
218
219    firstLongTagTable = Param.Unsigned("First table with long tags")
220
221    truncatePathHist = Param.Bool(True,
222        "Truncate the path history to its configured size")
223
224
225class TAGE_SC_L_TAGE_64KB(TAGE_SC_L_TAGE):
226    type = 'TAGE_SC_L_TAGE_64KB'
227    cxx_class = 'TAGE_SC_L_TAGE_64KB'
228    cxx_header = "cpu/pred/tage_sc_l_64KB.hh"
229    nHistoryTables = 36
230
231    minHist = 6
232    maxHist = 3000
233
234    tagTableUBits = 1
235
236    logTagTableSizes = [13]
237
238    # This is used to handle the 2-way associativity
239    # (all odd entries are set to one, and if the corresponding even entry
240    # is set to one, then there is a 2-way associativity for this pair)
241    # Entry 0 is for the bimodal and it is ignored
242    # Note: For this implementation, some odd entries are also set to 0 to save
243    # some bits
244    noSkip = [0,0,1,0,0,0,1,0,0,1,1,1,1,1,1,1,1,1,1,
245                1,1,1,1,0,1,0,1,0,1,0,0,0,1,0,0,0,1]
246
247    logTagTableSize = 10
248    shortTagsTageFactor = 10
249    longTagsTageFactor = 20
250
251    longTagsSize = 12
252
253    firstLongTagTable = 13
254
255class TAGE_SC_L_TAGE_8KB(TAGE_SC_L_TAGE):
256    type = 'TAGE_SC_L_TAGE_8KB'
257    cxx_class = 'TAGE_SC_L_TAGE_8KB'
258    cxx_header = "cpu/pred/tage_sc_l_8KB.hh"
259
260    nHistoryTables = 30
261
262    minHist = 4
263    maxHist = 1000
264
265    logTagTableSize = 7
266    shortTagsTageFactor = 9
267    longTagsTageFactor = 17
268    longTagsSize = 12
269
270    logTagTableSizes = [12]
271
272    firstLongTagTable = 11
273
274    truncatePathHist = False
275
276    noSkip = [0,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1]
277
278    tagTableUBits = 2
279
280# LTAGE branch predictor as described in
281# https://www.irisa.fr/caps/people/seznec/L-TAGE.pdf
282# It is basically a TAGE predictor plus a loop predictor
283# The differnt TAGE sizes are updated according to the paper values (256 Kbits)
284class LTAGE(TAGE):
285    type = 'LTAGE'
286    cxx_class = 'LTAGE'
287    cxx_header = "cpu/pred/ltage.hh"
288
289    tage = LTAGE_TAGE()
290
291    loop_predictor = Param.LoopPredictor(LoopPredictor(), "Loop predictor")
292
293class TAGE_SC_L_LoopPredictor(LoopPredictor):
294    type = 'TAGE_SC_L_LoopPredictor'
295    cxx_class  = 'TAGE_SC_L_LoopPredictor'
296    cxx_header = "cpu/pred/tage_sc_l.hh"
297    loopTableAgeBits = 4
298    loopTableConfidenceBits = 4
299    loopTableTagBits = 10
300    loopTableIterBits = 10
301    useSpeculation = False
302    useHashing = True
303    useDirectionBit = True
304    restrictAllocation = True
305    initialLoopIter = 0
306    initialLoopAge = 7
307    optionalAgeReset = False
308
309class StatisticalCorrector(SimObject):
310    type = 'StatisticalCorrector'
311    cxx_class  = 'StatisticalCorrector'
312    cxx_header = "cpu/pred/statistical_corrector.hh"
313    abstract = True
314
315    # Statistical corrector parameters
316
317    numEntriesFirstLocalHistories = Param.Unsigned(
318        "Number of entries for first local histories")
319
320    bwnb = Param.Unsigned("Num global backward branch GEHL lengths")
321    bwm = VectorParam.Int("Global backward branch GEHL lengths")
322    logBwnb = Param.Unsigned("Log num of global backward branch GEHL entries")
323
324    lnb = Param.Unsigned("Num first local history GEHL lenghts")
325    lm = VectorParam.Int("First local history GEHL lengths")
326    logLnb = Param.Unsigned("Log number of first local history GEHL entries")
327
328    inb = Param.Unsigned(1, "Num IMLI GEHL lenghts")
329    im = VectorParam.Int([8], "IMLI history GEHL lengths")
330    logInb = Param.Unsigned("Log number of IMLI GEHL entries")
331
332    logBias = Param.Unsigned("Log size of Bias tables")
333
334    logSizeUp = Param.Unsigned(6,
335        "Log size of update threshold counters tables")
336
337    chooserConfWidth = Param.Unsigned(7,
338        "Number of bits for the chooser counters")
339
340    updateThresholdWidth = Param.Unsigned(12,
341        "Number of bits for the update threshold counter")
342
343    pUpdateThresholdWidth = Param.Unsigned(8,
344        "Number of bits for the pUpdate threshold counters")
345
346    extraWeightsWidth = Param.Unsigned(6,
347        "Number of bits for the extra weights")
348
349    scCountersWidth = Param.Unsigned(6, "Statistical corrector counters width")
350
351# TAGE-SC-L branch predictor as desribed in
352# https://www.jilp.org/cbp2016/paper/AndreSeznecLimited.pdf
353# It is a modified LTAGE predictor plus a statistical corrector predictor
354# The TAGE modifications include bank interleaving and partial associativity
355# Two different sizes are proposed in the paper:
356# 8KB => See TAGE_SC_L_8KB below
357# 64KB => See TAGE_SC_L_64KB below
358# The TAGE_SC_L_8KB and TAGE_SC_L_64KB classes differ not only on the values
359# of some parameters, but also in some implementation details
360# Given this, the TAGE_SC_L class is left abstract
361# Note that as it is now, this branch predictor does not handle any type
362# of speculation: All the structures/histories are updated at commit time
363class TAGE_SC_L(LTAGE):
364    type = 'TAGE_SC_L'
365    cxx_class = 'TAGE_SC_L'
366    cxx_header = "cpu/pred/tage_sc_l.hh"
367    abstract = True
368
369    statistical_corrector = Param.StatisticalCorrector(
370        "Statistical Corrector")
371
372class TAGE_SC_L_64KB_LoopPredictor(TAGE_SC_L_LoopPredictor):
373    logSizeLoopPred = 5
374
375class TAGE_SC_L_8KB_LoopPredictor(TAGE_SC_L_LoopPredictor):
376    logSizeLoopPred = 3
377
378class TAGE_SC_L_64KB_StatisticalCorrector(StatisticalCorrector):
379    type = 'TAGE_SC_L_64KB_StatisticalCorrector'
380    cxx_class  = 'TAGE_SC_L_64KB_StatisticalCorrector'
381    cxx_header = "cpu/pred/tage_sc_l_64KB.hh"
382
383    pnb = Param.Unsigned(3, "Num variation global branch GEHL lengths")
384    pm = VectorParam.Int([25, 16, 9], "Variation global branch GEHL lengths")
385    logPnb = Param.Unsigned(9,
386        "Log number of variation global branch GEHL entries")
387
388    snb = Param.Unsigned(3, "Num second local history GEHL lenghts")
389    sm = VectorParam.Int([16, 11, 6], "Second local history GEHL lengths")
390    logSnb = Param.Unsigned(9,
391        "Log number of second local history GEHL entries")
392
393    tnb = Param.Unsigned(2, "Num third local history GEHL lenghts")
394    tm = VectorParam.Int([9, 4], "Third local history GEHL lengths")
395    logTnb = Param.Unsigned(10,
396        "Log number of third local history GEHL entries")
397
398    imnb = Param.Unsigned(2, "Num second IMLI GEHL lenghts")
399    imm = VectorParam.Int([10, 4], "Second IMLI history GEHL lengths")
400    logImnb = Param.Unsigned(9, "Log number of second IMLI GEHL entries")
401
402    numEntriesSecondLocalHistories = Param.Unsigned(16,
403        "Number of entries for second local histories")
404    numEntriesThirdLocalHistories = Param.Unsigned(16,
405        "Number of entries for second local histories")
406
407    numEntriesFirstLocalHistories = 256
408
409    logBias = 8
410
411    bwnb = 3
412    bwm = [40, 24, 10]
413    logBwnb = 10
414
415    lnb = 3
416    lm = [11, 6, 3]
417    logLnb = 10
418
419    logInb = 8
420
421class TAGE_SC_L_8KB_StatisticalCorrector(StatisticalCorrector):
422    type = 'TAGE_SC_L_8KB_StatisticalCorrector'
423    cxx_class  = 'TAGE_SC_L_8KB_StatisticalCorrector'
424    cxx_header = "cpu/pred/tage_sc_l_8KB.hh"
425    gnb = Param.Unsigned(2, "Num global branch GEHL lengths")
426    gm = VectorParam.Int([6, 3], "Global branch GEHL lengths")
427    logGnb = Param.Unsigned(7, "Log number of global branch GEHL entries")
428
429    numEntriesFirstLocalHistories = 64
430
431    logBias = 7
432
433    bwnb = 2
434    logBwnb = 7
435    bwm = [16, 8]
436
437    lnb = 2
438    logLnb = 7
439    lm = [6, 3]
440
441    logInb = 7
442
443# 64KB TAGE-SC-L branch predictor as described in
444# http://www.jilp.org/cbp2016/paper/AndreSeznecLimited.pdf
445class TAGE_SC_L_64KB(TAGE_SC_L):
446    type = 'TAGE_SC_L_64KB'
447    cxx_class = 'TAGE_SC_L_64KB'
448    cxx_header = "cpu/pred/tage_sc_l_64KB.hh"
449
450    tage = TAGE_SC_L_TAGE_64KB()
451    loop_predictor = TAGE_SC_L_64KB_LoopPredictor()
452    statistical_corrector = TAGE_SC_L_64KB_StatisticalCorrector()
453
454# 8KB TAGE-SC-L branch predictor as described in
455# http://www.jilp.org/cbp2016/paper/AndreSeznecLimited.pdf
456class TAGE_SC_L_8KB(TAGE_SC_L):
457    type = 'TAGE_SC_L_8KB'
458    cxx_class = 'TAGE_SC_L_8KB'
459    cxx_header = "cpu/pred/tage_sc_l_8KB.hh"
460
461    tage = TAGE_SC_L_TAGE_8KB()
462    loop_predictor = TAGE_SC_L_8KB_LoopPredictor()
463    statistical_corrector = TAGE_SC_L_8KB_StatisticalCorrector()
464