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