multiperspective_perceptron.cc revision 14034:937e704c6807
1/* 2 * Copyright 2019 Texas A&M University 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are met: 6 * 7 * 1. Redistributions of source code must retain the above copyright notice, 8 * this list of conditions and the following disclaimer. 9 * 10 * 2. Redistributions in binary form must reproduce the above copyright notice, 11 * this list of conditions and the following disclaimer in the documentation 12 * and/or other materials provided with the distribution. 13 * 14 * 3. Neither the name of the copyright holder nor the names of its 15 * contributors may be used to endorse or promote products derived from this 16 * software without specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 * 30 * Author: Daniel A. Jiménez 31 * Adapted to gem5 by: Javier Bueno Hedo 32 * 33 */ 34 35 /* 36 * Multiperspective Perceptron Predictor (by Daniel A. Jiménez) 37 */ 38 39#include "cpu/pred/multiperspective_perceptron.hh" 40 41#include "debug/Branch.hh" 42 43int 44MultiperspectivePerceptron::xlat[] = 45 {1,3,4,5,7,8,9,11,12,14,15,17,19,21,23,25,27,29,32,34,37,41,45,49,53,58,63, 46 69,76,85,94,106,}; 47int 48MultiperspectivePerceptron::xlat4[] = 49 {0,4,5,7,9,11,12,14,16,17,19,22,28,33,39,45,}; 50 51MultiperspectivePerceptron::ThreadData::ThreadData(int num_filters, 52 int n_local_histories, int local_history_length, int assoc, 53 const std::vector<std::vector<int>> &blurrypath_bits, int path_length, 54 int ghist_length, int block_size, 55 const std::vector<std::vector<std::vector<bool>>> &acyclic_bits, 56 const std::vector<int> &modhist_indices, 57 const std::vector<int> &modhist_lengths, 58 const std::vector<int> &modpath_indices, 59 const std::vector<int> &modpath_lengths, 60 const std::vector<int> &table_sizes, int n_sign_bits) 61 : filterTable(num_filters), acyclic_histories(acyclic_bits.size()), 62 acyclic2_histories(acyclic_bits.size()), 63 blurrypath_histories(blurrypath_bits.size()), 64 ghist_words(ghist_length/block_size+1, 0), 65 path_history(path_length, 0), imli_counter(4,0), 66 localHistories(n_local_histories, local_history_length), 67 recency_stack(assoc), last_ghist_bit(false), occupancy(0) 68{ 69 for (int i = 0; i < blurrypath_bits.size(); i+= 1) { 70 blurrypath_histories[i].resize(blurrypath_bits[i].size()); 71 } 72 73 for (int i = 0; i < acyclic_bits.size(); i += 1) { 74 acyclic_histories[i].resize(acyclic_bits[i].size()); 75 acyclic2_histories[i].resize(acyclic_bits[i].size()); 76 } 77 78 int max_modhist_idx = -1; 79 for (auto &elem : modhist_indices) { 80 max_modhist_idx = (max_modhist_idx < elem) ? elem : max_modhist_idx; 81 } 82 if (max_modhist_idx >= 0) { 83 mod_histories.resize(max_modhist_idx + 1); 84 } 85 for (int i = 0; i < modhist_lengths.size(); i+= 1) { 86 mod_histories[modhist_indices[i]].resize(modhist_lengths[i]); 87 } 88 89 int max_modpath_idx = -1; 90 for (auto &elem : modpath_indices) { 91 max_modpath_idx = (max_modpath_idx < elem) ? elem : max_modpath_idx; 92 } 93 if (max_modpath_idx >= 0) { 94 modpath_histories.resize(max_modpath_idx + 1); 95 } 96 for (int i = 0; i < modpath_lengths.size(); i+= 1) { 97 modpath_histories[modpath_indices[i]].resize(modpath_lengths[i]); 98 } 99 100 for (int i = 0; i < table_sizes.size(); i += 1) { 101 mpreds.push_back(0); 102 tables.push_back(std::vector<short int>(table_sizes[i])); 103 sign_bits.push_back(std::vector<std::array<bool, 2>>(table_sizes[i])); 104 for (int j = 0; j < table_sizes[i]; j += 1) { 105 for (int k = 0; k < n_sign_bits; k += 1) { 106 sign_bits[i][j][k] = (i & 1) | (k & 1); 107 } 108 } 109 } 110} 111 112MultiperspectivePerceptron::MultiperspectivePerceptron( 113 const MultiperspectivePerceptronParams *p) : BPredUnit(p), 114 blockSize(p->block_size), pcshift(p->pcshift), threshold(p->threshold), 115 bias0(p->bias0), bias1(p->bias1), biasmostly0(p->biasmostly0), 116 biasmostly1(p->biasmostly1), nbest(p->nbest), tunebits(p->tunebits), 117 hshift(p->hshift), imli_mask1(p->imli_mask1), imli_mask4(p->imli_mask4), 118 recencypos_mask(p->recencypos_mask), fudge(p->fudge), 119 n_sign_bits(p->n_sign_bits), pcbit(p->pcbit), decay(p->decay), 120 record_mask(p->record_mask), hash_taken(p->hash_taken), 121 tuneonly(p->tuneonly), extra_rounds(p->extra_rounds), speed(p->speed), 122 budgetbits(p->budgetbits), speculative_update(p->speculative_update), 123 threadData(p->numThreads, nullptr), doing_local(false), 124 doing_recency(false), assoc(0), ghist_length(1), modghist_length(1), 125 path_length(1), randSeed(0xdeadbeef), thresholdCounter(0), 126 theta(p->initial_theta), imli_counter_bits(4), modhist_indices(), 127 modhist_lengths(), modpath_indices(), modpath_lengths() 128{ 129 fatal_if(speculative_update, "Speculative update not implemented"); 130} 131 132void 133MultiperspectivePerceptron::init() 134{ 135 createSpecs(); 136 137 for (auto &spec : specs) { 138 // initial assignation of values 139 table_sizes.push_back(spec->size); 140 } 141 142 // Update bit requirements and runtime values 143 for (auto &spec : specs) { 144 spec->setBitRequirements(); 145 } 146 const MultiperspectivePerceptronParams *p = 147 static_cast<const MultiperspectivePerceptronParams *>(params()); 148 149 computeBits(p->num_filter_entries, p->num_local_histories, 150 p->local_history_length); 151 152 for (int i = 0; i < threadData.size(); i += 1) { 153 threadData[i] = new ThreadData(p->num_filter_entries, 154 p->num_local_histories, 155 p->local_history_length, assoc, 156 blurrypath_bits, path_length, 157 ghist_length, blockSize, acyclic_bits, 158 modhist_indices, modhist_lengths, 159 modpath_indices, modpath_lengths, 160 table_sizes, n_sign_bits); 161 } 162} 163 164void 165MultiperspectivePerceptron::computeBits(int num_filter_entries, 166 int nlocal_histories, int local_history_length) { 167 int totalbits = 0; 168 for (auto &imli_bits : imli_counter_bits) { 169 totalbits += imli_bits; 170 } 171 totalbits += ghist_length; 172 totalbits += path_length * 16; 173 totalbits += (threshold >= 0) ? (tunebits * specs.size()) : 0; 174 for (auto &len : modhist_lengths) { 175 totalbits += len; 176 } 177 for (auto &len : modpath_lengths) { 178 totalbits += 16 * len; 179 } 180 totalbits += doing_local ? (nlocal_histories * local_history_length) : 0; 181 totalbits += doing_recency ? (assoc * 16) : 0; 182 183 for (auto &bv : blurrypath_bits) { 184 for (auto &bve : bv) { 185 totalbits += bve; 186 } 187 } 188 totalbits += num_filter_entries * 2; 189 190 for (auto &abi : acyclic_bits) { 191 for (auto &abj : abi) { 192 for (auto abk : abj) { 193 totalbits += abk; 194 } 195 } 196 } 197 198 int remaining = budgetbits - totalbits; 199 200 // count the tables that have already been assigned sizes 201 int num_sized = 0; 202 for (int i = 0; i < specs.size(); i +=1) { 203 if (table_sizes[i] != 0) { 204 int sz = table_sizes[i] * (specs[i]->width + (n_sign_bits - 1)); 205 totalbits += sz; 206 remaining -= sz; 207 num_sized += 1; 208 } 209 } 210 211 // whatever is left, we divide among the rest of the tables 212 int table_size_bits = (remaining / (specs.size()-num_sized)); 213 for (int i = 0; i < specs.size(); i += 1) { 214 // if a table doesn't have a size yet, give it one and count those bits 215 if (!table_sizes[i]) { 216 int my_table_size = table_size_bits / 217 (specs[i]->width + (n_sign_bits - 1)); // extra sign bits 218 table_sizes[i] = my_table_size; 219 totalbits += my_table_size * (specs[i]->width + (n_sign_bits - 1)); 220 } 221 } 222 223 DPRINTF(Branch, "%d bits of metadata so far, %d left out of " 224 "%d total budget\n", totalbits, remaining, budgetbits); 225 DPRINTF(Branch, "table size is %d bits, %d entries for 5 bit, %d entries " 226 "for 6 bit\n", table_size_bits, 227 table_size_bits / (5 + (n_sign_bits - 1)), 228 table_size_bits / (6 + (n_sign_bits - 1))); 229 DPRINTF(Branch, "%d total bits (%0.2fKB)\n", totalbits, 230 totalbits / 8192.0); 231} 232 233void 234MultiperspectivePerceptron::findBest(ThreadID tid, 235 std::vector<int> &best_preds) const 236{ 237 if (threshold < 0) { 238 return; 239 } 240 struct BestPair { 241 int index; 242 int mpreds; 243 bool operator<(BestPair const &bp) const 244 { 245 return mpreds < bp.mpreds; 246 } 247 }; 248 std::vector<BestPair> pairs(best_preds.size()); 249 for (int i = 0; i < best_preds.size(); i += 1) { 250 pairs[i].index = i; 251 pairs[i].mpreds = threadData[tid]->mpreds[i]; 252 } 253 std::sort(pairs.begin(), pairs.end()); 254 for (int i = 0; i < (std::min(nbest, (int) best_preds.size())); i += 1) { 255 best_preds[i] = pairs[i].index; 256 } 257} 258 259unsigned int 260MultiperspectivePerceptron::getIndex(ThreadID tid, const MPPBranchInfo &bi, 261 const HistorySpec &spec, int index) const 262{ 263 unsigned int g = spec.getHash(tid, bi.getPC(), bi.getPC2(), index); 264 unsigned long long int h = g; 265 // shift the hash from the feature to xor with the hashed PC 266 if (hshift < 0) { 267 h <<= -hshift; 268 h ^= bi.getPC2(); 269 } else { 270 h <<= hshift; 271 h ^= bi.getHPC(); 272 } 273 // xor in the imli counter(s) and/or recency position based on the masks 274 if ((1ull<<index) & imli_mask1) { 275 h ^= threadData[tid]->imli_counter[0]; 276 } 277 if ((1ull<<index) & imli_mask4) { 278 h ^= threadData[tid]->imli_counter[3]; 279 } 280 if (doing_recency) { 281 if ((1ull<<index) & recencypos_mask) { 282 h ^= RECENCYPOS::hash(threadData[tid]->recency_stack, table_sizes, 283 bi.getPC2(), 31, index); 284 } 285 } 286 h %= table_sizes[index]; 287 return h; 288} 289 290int 291MultiperspectivePerceptron::computeOutput(ThreadID tid, MPPBranchInfo &bi) 292{ 293 // list of best predictors 294 std::vector<int> best_preds(specs.size(), -1); 295 296 // initialize sum 297 bi.yout = 0; 298 299 // bias the prediction by whether the local history is 300 // one of four distinctive patterns 301 int lhist = threadData[tid]->localHistories[bi.getPC()]; 302 int history_len = threadData[tid]->localHistories.getLocalHistoryLength(); 303 if (lhist == 0) { 304 bi.yout = bias0; 305 } else if (lhist == ((1<<history_len)-1)) { 306 bi.yout = bias1; 307 } else if (lhist == (1<<(history_len-1))) { 308 bi.yout = biasmostly0; 309 } else if (lhist == ((1<<(history_len-1))-1)) { 310 bi.yout = biasmostly1; 311 } 312 // find the best subset of features to use in case of a low-confidence 313 // branch 314 findBest(tid, best_preds); 315 316 // begin computation of the sum for low-confidence branch 317 int bestval = 0; 318 319 for (int i = 0; i < specs.size(); i += 1) { 320 HistorySpec const &spec = *specs[i]; 321 // get the hash to index the table 322 unsigned int hashed_idx = getIndex(tid, bi, spec, i); 323 // add the weight; first get the weight's magnitude 324 int counter = threadData[tid]->tables[i][hashed_idx]; 325 // get the sign 326 bool sign = 327 threadData[tid]->sign_bits[i][hashed_idx][bi.getHPC() % n_sign_bits]; 328 // apply the transfer function and multiply by a coefficient 329 int weight = spec.coeff * ((spec.width == 5) ? 330 xlat4[counter] : xlat[counter]); 331 // apply the sign 332 int val = sign ? -weight : weight; 333 // add the value 334 bi.yout += val; 335 // if this is one of those good features, add the value to bestval 336 if (threshold >= 0) { 337 for (int j = 0; 338 j < std::min(nbest, (int) best_preds.size()); 339 j += 1) 340 { 341 if (best_preds[j] == i) { 342 bestval += val; 343 break; 344 } 345 } 346 } 347 } 348 // apply a fudge factor to affect when training is triggered 349 bi.yout *= fudge; 350 return bestval; 351} 352 353void 354MultiperspectivePerceptron::satIncDec(bool taken, bool &sign, int &counter, 355 int max_weight) const 356{ 357 if (taken) { 358 // increment sign/magnitude 359 if (sign) { 360 // go toward 0 away from negative max weight 361 if (counter == 0) { 362 sign = false; // moved to positive 0 363 } else { 364 counter -= 1; 365 } 366 } else { 367 // go toward max weight away from 0 368 if (counter < max_weight) { 369 counter += 1; 370 } 371 } 372 } else { 373 // decrement sign/magnitude 374 if (sign) { 375 // go toward negative max weight down from 0 376 if (counter < max_weight) { 377 counter += 1; 378 } 379 } else { 380 // go toward 0 away from max weight 381 if (counter == 0) { 382 sign = true; // negative 0 383 } else { 384 counter -= 1; 385 } 386 } 387 } 388} 389 390void 391MultiperspectivePerceptron::train(ThreadID tid, MPPBranchInfo &bi, bool taken) 392{ 393 std::vector<std::vector<short int>> &tables = threadData[tid]->tables; 394 std::vector<std::vector<std::array<bool, 2>>> &sign_bits = 395 threadData[tid]->sign_bits; 396 std::vector<int> &mpreds = threadData[tid]->mpreds; 397 // was the prediction correct? 398 bool correct = (bi.yout >= 1) == taken; 399 // what is the magnitude of yout? 400 int abs_yout = abs(bi.yout); 401 // keep track of mispredictions per table 402 if (threshold >= 0) if (!tuneonly || (abs_yout <= threshold)) { 403 bool halve = false; 404 405 // for each table, figure out if there was a misprediction 406 for (int i = 0; i < specs.size(); i += 1) { 407 HistorySpec const &spec = *specs[i]; 408 // get the hash to index the table 409 unsigned int hashed_idx = getIndex(tid, bi, spec, i); 410 bool sign = sign_bits[i][hashed_idx][bi.getHPC() % n_sign_bits]; 411 int counter = tables[i][hashed_idx]; 412 int weight = spec.coeff * ((spec.width == 5) ? 413 xlat4[counter] : xlat[counter]); 414 if (sign) weight = -weight; 415 bool pred = weight >= 1; 416 if (pred != taken) { 417 mpreds[i] += 1; 418 if (mpreds[i] == (1 << tunebits) - 1) { 419 halve = true; 420 } 421 } 422 } 423 // if we reach the maximum counter value, halve all the counters 424 if (halve) { 425 for (int i = 0; i < specs.size(); i += 1) { 426 mpreds[i] /= 2; 427 } 428 } 429 } 430 // if the branch was predicted incorrectly or the correct 431 // prediction was weak, update the weights 432 bool do_train = !correct || (abs_yout <= theta); 433 if (!do_train) return; 434 435 // adaptive theta training, adapted from O-GEHL 436 if (!correct) { 437 thresholdCounter += 1; 438 if (thresholdCounter >= speed) { 439 theta += 1; 440 thresholdCounter = 0; 441 } 442 } 443 if (correct && abs_yout < theta) { 444 thresholdCounter -= 1; 445 if (thresholdCounter <= -speed) { 446 theta -= 1; 447 thresholdCounter = 0; 448 } 449 } 450 451 // train the weights, computing what the value of yout 452 // would have been if these updates had been applied before 453 int newyout = 0; 454 for (int i = 0; i < specs.size(); i += 1) { 455 HistorySpec const &spec = *specs[i]; 456 // get the magnitude 457 unsigned int hashed_idx = getIndex(tid, bi, spec, i); 458 int counter = tables[i][hashed_idx]; 459 // get the sign 460 bool sign = sign_bits[i][hashed_idx][bi.getHPC() % n_sign_bits]; 461 // increment/decrement if taken/not taken 462 satIncDec(taken, sign, counter, (1 << (spec.width - 1)) - 1); 463 // update the magnitude and sign 464 tables[i][hashed_idx] = counter; 465 sign_bits[i][hashed_idx][bi.getHPC() % n_sign_bits] = sign; 466 int weight = ((spec.width == 5) ? xlat4[counter] : xlat[counter]); 467 // update the new version of yout 468 if (sign) { 469 newyout -= weight; 470 } else { 471 newyout += weight; 472 } 473 } 474 475 // if the prediction still would have been incorrect even 476 // with the updated weights, update some more weights to 477 // try to fix the problem 478 if ((newyout >= 1) != taken) { 479 if (extra_rounds != -1) { 480 int round_counter = 0; 481 bool found; 482 do { 483 // udpate a random weight 484 int besti = -1; 485 int nrand = rand_r(&randSeed) % specs.size(); 486 int pout; 487 found = false; 488 for (int j = 0; j < specs.size(); j += 1) { 489 int i = (nrand + j) % specs.size(); 490 HistorySpec const &spec = *specs[i]; 491 unsigned int hashed_idx = getIndex(tid, bi, spec, i); 492 int counter = tables[i][hashed_idx]; 493 bool sign = 494 sign_bits[i][hashed_idx][bi.getHPC() % n_sign_bits]; 495 int weight = ((spec.width == 5) ? 496 xlat4[counter] : xlat[counter]); 497 int signed_weight = sign ? -weight : weight; 498 pout = newyout - signed_weight; 499 if ((pout >= 1) == taken) { 500 // we have found a weight that if we blow 501 // it away will help! 502 besti = i; 503 break; 504 } 505 } 506 if (besti != -1) { 507 int i = besti; 508 HistorySpec const &spec = *specs[i]; 509 unsigned int hashed_idx = getIndex(tid, bi, spec, i); 510 int counter = tables[i][hashed_idx]; 511 bool sign = 512 sign_bits[i][hashed_idx][bi.getHPC() % n_sign_bits]; 513 if (counter > 1) { 514 counter--; 515 tables[i][hashed_idx] = counter; 516 } 517 int weight = ((spec.width == 5) ? 518 xlat4[counter] : xlat[counter]); 519 int signed_weight = sign ? -weight : weight; 520 int out = pout + signed_weight; 521 round_counter += 1; 522 if ((out >= 1) != taken) { 523 found = true; 524 } 525 } 526 } while (found && round_counter < extra_rounds); 527 } 528 } 529} 530 531void 532MultiperspectivePerceptron::uncondBranch(ThreadID tid, Addr pc, 533 void * &bp_history) 534{ 535 MPPBranchInfo *bi = new MPPBranchInfo(pc, pcshift, false); 536 std::vector<unsigned int> &ghist_words = threadData[tid]->ghist_words; 537 538 bp_history = (void *)bi; 539 unsigned short int pc2 = pc >> 2; 540 bool ab = !(pc & (1<<pcbit)); 541 for (int i = 0; i < ghist_length / blockSize + 1; i += 1) { 542 bool ab_new = (ghist_words[i] >> (blockSize - 1)) & 1; 543 ghist_words[i] <<= 1; 544 ghist_words[i] |= ab; 545 ghist_words[i] &= (1 << blockSize) - 1; 546 ab = ab_new; 547 } 548 memmove(&threadData[tid]->path_history[1], 549 &threadData[tid]->path_history[0], 550 sizeof(unsigned short int) * (path_length - 1)); 551 threadData[tid]->path_history[0] = pc2; 552} 553 554bool 555MultiperspectivePerceptron::lookup(ThreadID tid, Addr instPC, 556 void * &bp_history) 557{ 558 MPPBranchInfo *bi = new MPPBranchInfo(instPC, pcshift, true); 559 bp_history = (void *)bi; 560 561 bool use_static = false; 562 563 if (!threadData[tid]->filterTable.empty()) { 564 unsigned int findex = 565 bi->getHashFilter(threadData[tid]->last_ghist_bit) % 566 threadData[tid]->filterTable.size(); 567 FilterEntry &f = threadData[tid]->filterTable[findex]; 568 if (f.alwaysNotTakenSoFar()) { 569 bi->filtered = true; 570 bi->prediction = false; 571 return false; 572 } else if (f.alwaysTakenSoFar()) { 573 bi->filtered = true; 574 bi->prediction = true; 575 return true; 576 } 577 if (f.neverSeen()) { 578 use_static = true; 579 } 580 } 581 582 int bestval = computeOutput(tid, *bi); 583 if (use_static) { 584 bi->prediction = false; 585 } else { 586 if (abs(bi->yout) <= threshold) { 587 bi->prediction = (bestval >= 1); 588 } else { 589 bi->prediction = (bi->yout >= 1); 590 } 591 } 592 593 return bi->prediction; 594} 595 596void 597MultiperspectivePerceptron::update(ThreadID tid, Addr instPC, bool taken, 598 void *bp_history, bool squashed, 599 const StaticInstPtr & inst, 600 Addr corrTarget) 601{ 602 assert(bp_history); 603 MPPBranchInfo *bi = static_cast<MPPBranchInfo*>(bp_history); 604 assert(corrTarget != MaxAddr); 605 if (squashed) { 606 //delete bi; 607 return; 608 } 609 610 if (bi->isUnconditional()) { 611 delete bi; 612 return; 613 } 614 615 bool do_train = true; 616 617 if (!threadData[tid]->filterTable.empty()) { 618 int findex = bi->getHashFilter(threadData[tid]->last_ghist_bit) % 619 threadData[tid]->filterTable.size(); 620 FilterEntry &f = threadData[tid]->filterTable[findex]; 621 622 // compute this first, so we don't not train on the 623 // first time a branch is seen. 624 bool transition = false; 625 if (f.alwaysNotTakenSoFar() || f.alwaysTakenSoFar()) { 626 do_train = false; 627 } 628 if (taken) { 629 if (f.alwaysNotTakenSoFar()) { 630 transition = true; 631 } 632 f.seenTaken = true; 633 } else { 634 if (f.alwaysTakenSoFar()) { 635 transition = true; 636 } 637 f.seenUntaken = true; 638 } 639 // is this the first time time the branch has gone both ways? 640 if (transition) { 641 threadData[tid]->occupancy += 1; 642 } 643 // for every new dynamic branch, when there ar 644 // more than 'decay' number of branches in the 645 // filter, blow a random filter entry away 646 if (decay && transition && 647 ((threadData[tid]->occupancy > decay) || (decay == 1))) { 648 int rnd = rand_r(&randSeed) % threadData[tid]->filterTable.size(); 649 FilterEntry &frand = threadData[tid]->filterTable[rnd]; 650 if (frand.seenTaken && frand.seenUntaken) { 651 threadData[tid]->occupancy -= 1; 652 } 653 frand.seenTaken = false; 654 frand.seenUntaken = false; 655 } 656 } 657 658 if (do_train) { 659 train(tid, *bi, taken); 660 } 661 662#define RECORD_FILTERED_IMLI 1 663#define RECORD_FILTERED_GHIST 2 664#define RECORD_FILTERED_PATH 4 665#define RECORD_FILTERED_ACYCLIC 8 666#define RECORD_FILTERED_MOD 16 667#define RECORD_FILTERED_BLURRY 32 668// should never record a filtered local branch - duh! 669#define RECORD_FILTERED_LOCAL 64 670#define RECORD_FILTERED_RECENCY 128 671 672 // four different styles of IMLI 673 if (!bi->filtered || (record_mask & RECORD_FILTERED_IMLI)) { 674 unsigned int target = corrTarget; 675 if (target < bi->getPC()) { 676 if (taken) { 677 threadData[tid]->imli_counter[0] += 1; 678 } else { 679 threadData[tid]->imli_counter[0] = 0; 680 } 681 if (!taken) { 682 threadData[tid]->imli_counter[1] += 1; 683 } else { 684 threadData[tid]->imli_counter[1] = 0; 685 } 686 } else { 687 if (taken) { 688 threadData[tid]->imli_counter[2] += 1; 689 } else { 690 threadData[tid]->imli_counter[2] = 0; 691 } 692 if (!taken) { 693 threadData[tid]->imli_counter[3] += 1; 694 } else { 695 threadData[tid]->imli_counter[3] = 0; 696 } 697 } 698 } 699 700 bool hashed_taken = hash_taken ? (taken ^ !!(bi->getPC() & (1<<pcbit))) 701 : taken; 702 // record into ghist 703 if (!bi->filtered || (record_mask & RECORD_FILTERED_GHIST)) { 704 bool ab = hashed_taken; 705 assert(threadData[tid]->ghist_words.size() > 0); 706 for (int i = 0; i < ghist_length / blockSize + 1; i += 1) { 707 unsigned int a = threadData[tid]->ghist_words[i]; 708 bool ab_new = (a >> (blockSize - 1)) & 1; 709 a <<= 1; 710 a |= ab; 711 ab = ab_new; 712 a &= (1 << blockSize) - 1; 713 threadData[tid]->ghist_words[i] = a; 714 } 715 } 716 717 // record into path history 718 if (!bi->filtered || (record_mask & RECORD_FILTERED_PATH)) { 719 assert(threadData[tid]->path_history.size() > 0); 720 memmove(&threadData[tid]->path_history[1], 721 &threadData[tid]->path_history[0], 722 sizeof(unsigned short int) * (path_length - 1)); 723 threadData[tid]->path_history[0] = bi->getPC2(); 724 } 725 726 // record into acyclic history 727 if (!bi->filtered || (record_mask & RECORD_FILTERED_ACYCLIC)) { 728 threadData[tid]->updateAcyclic(hashed_taken, bi->getHPC()); 729 } 730 731 // record into modulo path history 732 if (!bi->filtered || (record_mask & RECORD_FILTERED_MOD)) { 733 for (int ii = 0; ii < modpath_indices.size(); ii += 1) { 734 int i = modpath_indices[ii]; 735 if (bi->getHPC() % (i + 2) == 0) { 736 memmove(&threadData[tid]->modpath_histories[i][1], 737 &threadData[tid]->modpath_histories[i][0], 738 sizeof(unsigned short int) * (modpath_lengths[ii]-1)); 739 threadData[tid]->modpath_histories[i][0] = bi->getPC2(); 740 } 741 } 742 } 743 744 // update blurry history 745 if (!bi->filtered || (record_mask & RECORD_FILTERED_BLURRY)) { 746 std::vector<std::vector<unsigned int>> &blurrypath_histories = 747 threadData[tid]->blurrypath_histories; 748 749 for (int i = 0; i < blurrypath_histories.size(); i += 1) 750 { 751 if (blurrypath_histories[i].size() > 0) { 752 unsigned int z = bi->getPC() >> i; 753 if (blurrypath_histories[i][0] != z) { 754 memmove(&blurrypath_histories[i][1], 755 &blurrypath_histories[i][0], 756 sizeof(unsigned int) * 757 (blurrypath_histories[i].size() - 1)); 758 blurrypath_histories[i][0] = z; 759 } 760 } 761 } 762 } 763 764 // record into modulo pattern history 765 if (!bi->filtered || (record_mask & RECORD_FILTERED_MOD)) { 766 for (int ii = 0; ii < modhist_indices.size(); ii += 1) { 767 int i = modhist_indices[ii]; 768 if (bi->getHPC() % (i + 2) == 0) { 769 for (int j = modhist_lengths[ii] - 1; j > 0; j -= 1) { 770 threadData[tid]->mod_histories[i][j] = 771 threadData[tid]->mod_histories[i][j-1]; 772 } 773 threadData[tid]->mod_histories[i][0] = hashed_taken; 774 } 775 } 776 } 777 778 // insert this PC into the recency stack 779 if (doing_recency) { 780 if (!bi->filtered || (record_mask & RECORD_FILTERED_RECENCY)) { 781 threadData[tid]->insertRecency(bi->getPC2(), assoc); 782 } 783 } 784 785 // record into a local history 786 if (!bi->filtered || (record_mask & RECORD_FILTERED_LOCAL)) { 787 threadData[tid]->localHistories.update(bi->getPC(), hashed_taken); 788 } 789 790 // update last ghist bit, used to index filter 791 threadData[tid]->last_ghist_bit = taken; 792 793 delete bi; 794} 795 796void 797MultiperspectivePerceptron::btbUpdate(ThreadID tid, Addr branch_pc, 798 void* &bp_history) 799{ 800} 801 802void 803MultiperspectivePerceptron::squash(ThreadID tid, void *bp_history) 804{ 805 assert(bp_history); 806 MPPBranchInfo *bi = static_cast<MPPBranchInfo*>(bp_history); 807 delete bi; 808} 809