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