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