statistical_corrector.cc revision 13685:bb3377c81303
1/* 2 * Copyright (c) 2018 Metempsy Technology Consulting 3 * All rights reserved. 4 * 5 * Copyright (c) 2006 INRIA (Institut National de Recherche en 6 * Informatique et en Automatique / French National Research Institute 7 * for Computer Science and Applied Mathematics) 8 * 9 * All rights reserved. 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions are 13 * met: redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer; 15 * redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution; 18 * neither the name of the copyright holders nor the names of its 19 * contributors may be used to endorse or promote products derived from 20 * this software without specific prior written permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 23 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 24 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 25 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 26 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 27 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 28 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 29 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 30 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 31 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 32 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 33 * 34 * Author: André Seznec, Pau Cabre, Javier Bueno 35 * 36 */ 37 38/* 39 * Statistical corrector base class 40 */ 41 42 #include "cpu/pred/statistical_corrector.hh" 43 44 #include "params/StatisticalCorrector.hh" 45 46 StatisticalCorrector::StatisticalCorrector( 47 const StatisticalCorrectorParams *p) 48 : SimObject(p), 49 logBias(p->logBias), 50 logSizeUp(p->logSizeUp), 51 logSizeUps(logSizeUp / 2), 52 numEntriesFirstLocalHistories(p->numEntriesFirstLocalHistories), 53 bwnb(p->bwnb), 54 logBwnb(p->logBwnb), 55 bwm(p->bwm), 56 lnb(p->lnb), 57 logLnb(p->logLnb), 58 lm(p->lm), 59 inb(p->inb), 60 logInb(p->logInb), 61 im(p->im), 62 chooserConfWidth(p->chooserConfWidth), 63 updateThresholdWidth(p->updateThresholdWidth), 64 pUpdateThresholdWidth(p->pUpdateThresholdWidth), 65 extraWeightsWidth(p->extraWeightsWidth), 66 scCountersWidth(p->scCountersWidth), 67 firstH(0), 68 secondH(0) 69{ 70 wb.resize(1 << logSizeUps, 4); 71 72 initGEHLTable(lnb, lm, lgehl, logLnb, wl, 7); 73 initGEHLTable(bwnb, bwm, bwgehl, logBwnb, wbw, 7); 74 initGEHLTable(inb, im, igehl, logInb, wi, 7); 75 76 updateThreshold = 35 << 3; 77 78 pUpdateThreshold.resize(1 << logSizeUp, 0); 79 80 bias.resize(1 << logBias); 81 biasSK.resize(1 << logBias); 82 biasBank.resize(1 << logBias); 83 for (int j = 0; j < (1 << logBias); j++) { 84 switch (j & 3) { 85 case 0: 86 bias[j] = -32; 87 biasSK[j] = -8; 88 biasBank[j] = -32; 89 break; 90 case 1: 91 bias[j] = 31; 92 biasSK[j] = 7; 93 biasBank[j] = 31; 94 break; 95 case 2: 96 bias[j] = -1; 97 biasSK[j] = -32; 98 biasBank[j] = -1; 99 break; 100 case 3: 101 bias[j] = 0; 102 biasSK[j] = 31; 103 biasBank[j] = 0; 104 break; 105 } 106 } 107} 108 109StatisticalCorrector::BranchInfo* 110StatisticalCorrector::makeBranchInfo() 111{ 112 return new BranchInfo(); 113} 114 115StatisticalCorrector::SCThreadHistory* 116StatisticalCorrector::makeThreadHistory() 117{ 118 return new SCThreadHistory(); 119} 120 121void 122StatisticalCorrector::initGEHLTable(unsigned numLenghts, 123 std::vector<int> lengths, std::vector<int8_t> * & table, 124 unsigned logNumEntries, std::vector<int8_t> & w, int8_t wInitValue) 125{ 126 assert(lengths.size() == numLenghts); 127 if (numLenghts == 0) { 128 return; 129 } 130 table = new std::vector<int8_t> [numLenghts]; 131 for (int i = 0; i < numLenghts; ++i) { 132 table[i].resize(1 << logNumEntries, 0); 133 for (int j = 0; j < ((1 << logNumEntries) - 1); ++j) { 134 if (! (j & 1)) { 135 table[i][j] = -1; 136 } 137 } 138 } 139 140 w.resize(1 << logSizeUps, wInitValue); 141} 142 143unsigned 144StatisticalCorrector::getIndBias(Addr branch_pc, BranchInfo* bi, 145 bool bias) const 146{ 147 return (((((branch_pc ^(branch_pc >>2))<<1) ^ (bi->lowConf & bias)) <<1) 148 + bi->predBeforeSC) & ((1<<logBias) -1); 149} 150 151unsigned 152StatisticalCorrector::getIndBiasSK(Addr branch_pc, BranchInfo* bi) const 153{ 154 return (((((branch_pc ^ (branch_pc >> (logBias-2)))<<1) ^ 155 (bi->highConf))<<1) + bi->predBeforeSC) & ((1<<logBias) -1); 156} 157 158unsigned 159StatisticalCorrector::getIndUpd(Addr branch_pc) const 160{ 161 return ((branch_pc ^ (branch_pc >>2)) & ((1 << (logSizeUp)) - 1)); 162} 163 164unsigned 165StatisticalCorrector::getIndUpds(Addr branch_pc) const 166{ 167 return ((branch_pc ^ (branch_pc >>2)) & ((1 << (logSizeUps)) - 1)); 168} 169 170int64_t 171StatisticalCorrector::gIndex(Addr branch_pc, int64_t bhist, int logs, int nbr, 172 int i) 173{ 174 return (((int64_t) branch_pc) ^ bhist ^ (bhist >> (8 - i)) ^ 175 (bhist >> (16 - 2 * i)) ^ (bhist >> (24 - 3 * i)) ^ 176 (bhist >> (32 - 3 * i)) ^ (bhist >> (40 - 4 * i))) & 177 ((1 << (logs - gIndexLogsSubstr(nbr, i))) - 1); 178} 179 180int 181StatisticalCorrector::gPredict(Addr branch_pc, int64_t hist, 182 std::vector<int> & length, std::vector<int8_t> * tab, int nbr, 183 int logs, std::vector<int8_t> & w) 184{ 185 int percsum = 0; 186 for (int i = 0; i < nbr; i++) { 187 int64_t bhist = hist & ((int64_t) ((1 << length[i]) - 1)); 188 int64_t index = gIndex(branch_pc, bhist, logs, nbr, i); 189 int8_t ctr = tab[i][index]; 190 percsum += (2 * ctr + 1); 191 } 192 percsum = (1 + (w[getIndUpds(branch_pc)] >= 0)) * percsum; 193 return percsum; 194} 195 196void 197StatisticalCorrector::gUpdate(Addr branch_pc, bool taken, int64_t hist, 198 std::vector<int> & length, std::vector<int8_t> * tab, 199 int nbr, int logs, std::vector<int8_t> & w, 200 BranchInfo* bi) 201{ 202 int percsum = 0; 203 for (int i = 0; i < nbr; i++) { 204 int64_t bhist = hist & ((int64_t) ((1 << length[i]) - 1)); 205 int64_t index = gIndex(branch_pc, bhist, logs, nbr, i); 206 percsum += (2 * tab[i][index] + 1); 207 ctrUpdate(tab[i][index], taken, scCountersWidth); 208 } 209 210 int xsum = bi->lsum - ((w[getIndUpds(branch_pc)] >= 0)) * percsum; 211 if ((xsum + percsum >= 0) != (xsum >= 0)) { 212 ctrUpdate(w[getIndUpds(branch_pc)], ((percsum >= 0) == taken), 213 extraWeightsWidth); 214 } 215} 216 217bool 218StatisticalCorrector::scPredict(ThreadID tid, Addr branch_pc, bool cond_branch, 219 BranchInfo* bi, bool prev_pred_taken, bool bias_bit, 220 bool use_conf_ctr, int8_t conf_ctr, unsigned conf_bits, 221 int hitBank, int altBank, int64_t phist) 222{ 223 bool pred_taken = prev_pred_taken; 224 if (cond_branch) { 225 226 bi->predBeforeSC = prev_pred_taken; 227 228 // first calc/update the confidences from the TAGE prediction 229 if (use_conf_ctr) { 230 bi->lowConf = (abs(2 * conf_ctr + 1) == 1); 231 bi->medConf = (abs(2 * conf_ctr + 1) == 5); 232 bi->highConf = (abs(2 * conf_ctr + 1) >= (1<<conf_bits) - 1); 233 } 234 235 int lsum = 0; 236 237 int8_t ctr = bias[getIndBias(branch_pc, bi, bias_bit)]; 238 lsum += (2 * ctr + 1); 239 ctr = biasSK[getIndBiasSK(branch_pc, bi)]; 240 lsum += (2 * ctr + 1); 241 ctr = biasBank[getIndBiasBank(branch_pc, bi, hitBank, altBank)]; 242 lsum += (2 * ctr + 1); 243 244 lsum = (1 + (wb[getIndUpds(branch_pc)] >= 0)) * lsum; 245 246 int thres = gPredictions(tid, branch_pc, bi, lsum, phist); 247 248 // These will be needed at update time 249 bi->lsum = lsum; 250 bi->thres = thres; 251 252 bool scPred = (lsum >= 0); 253 254 if (pred_taken != scPred) { 255 bool useScPred = true; 256 //Choser uses TAGE confidence and |LSUM| 257 if (bi->highConf) { 258 if (abs (lsum) < (thres / 4)) { 259 useScPred = false; 260 } else if (abs (lsum) < (thres / 2)) { 261 useScPred = (secondH < 0); 262 } 263 } 264 265 if (bi->medConf) { 266 if (abs (lsum) < (thres / 4)) { 267 useScPred = (firstH < 0); 268 } 269 } 270 271 bi->usedScPred = useScPred; 272 if (useScPred) { 273 pred_taken = scPred; 274 bi->scPred = scPred; 275 } 276 } 277 } 278 279 return pred_taken; 280} 281 282void 283StatisticalCorrector::scHistoryUpdate(Addr branch_pc, int brtype, bool taken, 284 BranchInfo * tage_bi, Addr corrTarget) 285{ 286 // Non speculative SC histories update 287 if (brtype & 1) { 288 if (corrTarget < branch_pc) { 289 //This branch corresponds to a loop 290 if (!taken) { 291 //exit of the "loop" 292 scHistory->imliCount = 0; 293 } else { 294 if (scHistory->imliCount < ((1 << im[0]) - 1)) { 295 scHistory->imliCount++; 296 } 297 } 298 } 299 300 scHistory->bwHist = (scHistory->bwHist << 1) + 301 (taken & (corrTarget < branch_pc)); 302 scHistory->updateLocalHistory(1, branch_pc, taken); 303 } 304} 305 306void 307StatisticalCorrector::condBranchUpdate(ThreadID tid, Addr branch_pc, 308 bool taken, BranchInfo *bi, Addr corrTarget, bool b, int hitBank, 309 int altBank, int64_t phist) 310{ 311 bool scPred = (bi->lsum >= 0); 312 313 if (bi->predBeforeSC != scPred) { 314 if (abs(bi->lsum) < bi->thres) { 315 if (bi->highConf) { 316 if ((abs(bi->lsum) < bi->thres / 2)) { 317 if ((abs(bi->lsum) >= bi->thres / 4)) { 318 ctrUpdate(secondH, (bi->predBeforeSC == taken), 319 chooserConfWidth); 320 } 321 } 322 } 323 } 324 if (bi->medConf) { 325 if ((abs(bi->lsum) < bi->thres / 4)) { 326 ctrUpdate(firstH, (bi->predBeforeSC == taken), 327 chooserConfWidth); 328 } 329 } 330 } 331 332 if ((scPred != taken) || ((abs(bi->lsum) < bi->thres))) { 333 ctrUpdate(updateThreshold, (scPred != taken), updateThresholdWidth); 334 ctrUpdate(pUpdateThreshold[getIndUpd(branch_pc)], (scPred != taken), 335 pUpdateThresholdWidth); 336 337 unsigned indUpds = getIndUpds(branch_pc); 338 unsigned indBias = getIndBias(branch_pc, bi, b); 339 unsigned indBiasSK = getIndBiasSK(branch_pc, bi); 340 unsigned indBiasBank = getIndBiasBank(branch_pc, bi, hitBank, altBank); 341 342 int xsum = bi->lsum - 343 ((wb[indUpds] >= 0) * ((2 * bias[indBias] + 1) + 344 (2 * biasSK[indBiasSK] + 1) + 345 (2 * biasBank[indBiasBank] + 1))); 346 347 if ((xsum + ((2 * bias[indBias] + 1) + (2 * biasSK[indBiasSK] + 1) + 348 (2 * biasBank[indBiasBank] + 1)) >= 0) != (xsum >= 0)) 349 { 350 ctrUpdate(wb[indUpds], 351 (((2 * bias[indBias] + 1) + 352 (2 * biasSK[indBiasSK] + 1) + 353 (2 * biasBank[indBiasBank] + 1) >= 0) == taken), 354 extraWeightsWidth); 355 } 356 357 ctrUpdate(bias[indBias], taken, scCountersWidth); 358 ctrUpdate(biasSK[indBiasSK], taken, scCountersWidth); 359 ctrUpdate(biasBank[indBiasBank], taken, scCountersWidth); 360 361 gUpdates(tid, branch_pc, taken, bi, phist); 362 } 363} 364 365void 366StatisticalCorrector::updateStats(bool taken, BranchInfo *bi) 367{ 368 if (taken == bi->scPred) { 369 scPredictorCorrect++; 370 } else { 371 scPredictorWrong++; 372 } 373} 374 375void 376StatisticalCorrector::init() 377{ 378 scHistory = makeThreadHistory(); 379} 380 381void 382StatisticalCorrector::regStats() 383{ 384 scPredictorCorrect 385 .name(name() + ".scPredictorCorrect") 386 .desc("Number of time the SC predictor is the provider and " 387 "the prediction is correct"); 388 389 scPredictorWrong 390 .name(name() + ".scPredictorWrong") 391 .desc("Number of time the SC predictor is the provider and " 392 "the prediction is wrong"); 393} 394