diff options
Diffstat (limited to 'cpu/o3/tournament_pred.cc')
| -rw-r--r-- | cpu/o3/tournament_pred.cc | 256 |
1 files changed, 256 insertions, 0 deletions
diff --git a/cpu/o3/tournament_pred.cc b/cpu/o3/tournament_pred.cc new file mode 100644 index 000000000..3fb580510 --- /dev/null +++ b/cpu/o3/tournament_pred.cc @@ -0,0 +1,256 @@ +/* + * Copyright (c) 2004-2005 The Regents of The University of Michigan + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer; + * redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution; + * neither the name of the copyright holders nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "cpu/o3/tournament_pred.hh" + +TournamentBP::TournamentBP(unsigned _local_predictor_size, + unsigned _local_ctr_bits, + unsigned _local_history_table_size, + unsigned _local_history_bits, + unsigned _global_predictor_size, + unsigned _global_ctr_bits, + unsigned _global_history_bits, + unsigned _choice_predictor_size, + unsigned _choice_ctr_bits, + unsigned _instShiftAmt) + : localPredictorSize(_local_predictor_size), + localCtrBits(_local_ctr_bits), + localHistoryTableSize(_local_history_table_size), + localHistoryBits(_local_history_bits), + globalPredictorSize(_global_predictor_size), + globalCtrBits(_global_ctr_bits), + globalHistoryBits(_global_history_bits), + choicePredictorSize(_global_predictor_size), + choiceCtrBits(_choice_ctr_bits), + instShiftAmt(_instShiftAmt) +{ + //Should do checks here to make sure sizes are correct (powers of 2) + + //Setup the array of counters for the local predictor + localCtrs = new SatCounter[localPredictorSize]; + + for (int i = 0; i < localPredictorSize; ++i) + localCtrs[i].setBits(localCtrBits); + + //Setup the history table for the local table + localHistoryTable = new unsigned[localHistoryTableSize]; + + for (int i = 0; i < localHistoryTableSize; ++i) + localHistoryTable[i] = 0; + + // Setup the local history mask + localHistoryMask = (1 << localHistoryBits) - 1; + + //Setup the array of counters for the global predictor + globalCtrs = new SatCounter[globalPredictorSize]; + + for (int i = 0; i < globalPredictorSize; ++i) + globalCtrs[i].setBits(globalCtrBits); + + //Clear the global history + globalHistory = 0; + // Setup the global history mask + globalHistoryMask = (1 << globalHistoryBits) - 1; + + //Setup the array of counters for the choice predictor + choiceCtrs = new SatCounter[choicePredictorSize]; + + for (int i = 0; i < choicePredictorSize; ++i) + choiceCtrs[i].setBits(choiceCtrBits); + + threshold = (1 << (localCtrBits - 1)) - 1; + threshold = threshold / 2; +} + +inline +unsigned +TournamentBP::calcLocHistIdx(Addr &branch_addr) +{ + return (branch_addr >> instShiftAmt) & (localHistoryTableSize - 1); +} + +inline +void +TournamentBP::updateHistoriesTaken(unsigned local_history_idx) +{ + globalHistory = (globalHistory << 1) | 1; + globalHistory = globalHistory & globalHistoryMask; + + localHistoryTable[local_history_idx] = + (localHistoryTable[local_history_idx] << 1) | 1; +} + +inline +void +TournamentBP::updateHistoriesNotTaken(unsigned local_history_idx) +{ + globalHistory = (globalHistory << 1); + globalHistory = globalHistory & globalHistoryMask; + + localHistoryTable[local_history_idx] = + (localHistoryTable[local_history_idx] << 1); +} + +bool +TournamentBP::lookup(Addr &branch_addr) +{ + uint8_t local_prediction; + unsigned local_history_idx; + unsigned local_predictor_idx; + + uint8_t global_prediction; + uint8_t choice_prediction; + + //Lookup in the local predictor to get its branch prediction + local_history_idx = calcLocHistIdx(branch_addr); + local_predictor_idx = localHistoryTable[local_history_idx] + & localHistoryMask; + local_prediction = localCtrs[local_predictor_idx].read(); + + //Lookup in the global predictor to get its branch prediction + global_prediction = globalCtrs[globalHistory].read(); + + //Lookup in the choice predictor to see which one to use + choice_prediction = choiceCtrs[globalHistory].read(); + + //@todo Put a threshold value in for the three predictors that can + // be set through the constructor (so this isn't hard coded). + //Also should put some of this code into functions. + if (choice_prediction > threshold) { + if (global_prediction > threshold) { + updateHistoriesTaken(local_history_idx); + + assert(globalHistory < globalPredictorSize && + local_history_idx < localPredictorSize); + + globalCtrs[globalHistory].increment(); + localCtrs[local_history_idx].increment(); + + return true; + } else { + updateHistoriesNotTaken(local_history_idx); + + assert(globalHistory < globalPredictorSize && + local_history_idx < localPredictorSize); + + globalCtrs[globalHistory].decrement(); + localCtrs[local_history_idx].decrement(); + + return false; + } + } else { + if (local_prediction > threshold) { + updateHistoriesTaken(local_history_idx); + + assert(globalHistory < globalPredictorSize && + local_history_idx < localPredictorSize); + + globalCtrs[globalHistory].increment(); + localCtrs[local_history_idx].increment(); + + return true; + } else { + updateHistoriesNotTaken(local_history_idx); + + assert(globalHistory < globalPredictorSize && + local_history_idx < localPredictorSize); + + globalCtrs[globalHistory].decrement(); + localCtrs[local_history_idx].decrement(); + + return false; + } + } +} + +// Update the branch predictor if it predicted a branch wrong. +void +TournamentBP::update(Addr &branch_addr, unsigned correct_gh, bool taken) +{ + + uint8_t local_prediction; + unsigned local_history_idx; + unsigned local_predictor_idx; + bool local_pred_taken; + + uint8_t global_prediction; + bool global_pred_taken; + + // Load the correct global history into the register. + globalHistory = correct_gh; + + // Get the local predictor's current prediction, remove the incorrect + // update, and update the local predictor + local_history_idx = calcLocHistIdx(branch_addr); + local_predictor_idx = localHistoryTable[local_history_idx]; + local_predictor_idx = (local_predictor_idx >> 1) & localHistoryMask; + + local_prediction = localCtrs[local_predictor_idx].read(); + local_pred_taken = local_prediction > threshold; + + //Get the global predictor's current prediction, and update the + //global predictor + global_prediction = globalCtrs[globalHistory].read(); + global_pred_taken = global_prediction > threshold; + + //Update the choice predictor to tell it which one was correct + if (local_pred_taken != global_pred_taken) { + //If the local prediction matches the actual outcome, decerement + //the counter. Otherwise increment the counter. + if (local_pred_taken == taken) { + choiceCtrs[globalHistory].decrement(); + } else { + choiceCtrs[globalHistory].increment(); + } + } + + if (taken) { + assert(globalHistory < globalPredictorSize && + local_predictor_idx < localPredictorSize); + + localCtrs[local_predictor_idx].increment(); + globalCtrs[globalHistory].increment(); + + globalHistory = (globalHistory << 1) | 1; + globalHistory = globalHistory & globalHistoryMask; + + localHistoryTable[local_history_idx] |= 1; + } + else { + assert(globalHistory < globalPredictorSize && + local_predictor_idx < localPredictorSize); + + localCtrs[local_predictor_idx].decrement(); + globalCtrs[globalHistory].decrement(); + + globalHistory = (globalHistory << 1); + globalHistory = globalHistory & globalHistoryMask; + + localHistoryTable[local_history_idx] &= ~1; + } +} |