114034Sjavier.bueno@metempsy.com/* 214034Sjavier.bueno@metempsy.com * Copyright 2019 Texas A&M University 314034Sjavier.bueno@metempsy.com * 414034Sjavier.bueno@metempsy.com * Redistribution and use in source and binary forms, with or without 514034Sjavier.bueno@metempsy.com * modification, are permitted provided that the following conditions are met: 614034Sjavier.bueno@metempsy.com * 714034Sjavier.bueno@metempsy.com * 1. Redistributions of source code must retain the above copyright notice, 814034Sjavier.bueno@metempsy.com * this list of conditions and the following disclaimer. 914034Sjavier.bueno@metempsy.com * 1014034Sjavier.bueno@metempsy.com * 2. Redistributions in binary form must reproduce the above copyright notice, 1114034Sjavier.bueno@metempsy.com * this list of conditions and the following disclaimer in the documentation 1214034Sjavier.bueno@metempsy.com * and/or other materials provided with the distribution. 1314034Sjavier.bueno@metempsy.com * 1414034Sjavier.bueno@metempsy.com * 3. Neither the name of the copyright holder nor the names of its 1514034Sjavier.bueno@metempsy.com * contributors may be used to endorse or promote products derived from this 1614034Sjavier.bueno@metempsy.com * software without specific prior written permission. 1714034Sjavier.bueno@metempsy.com * 1814034Sjavier.bueno@metempsy.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1914034Sjavier.bueno@metempsy.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2014034Sjavier.bueno@metempsy.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2114034Sjavier.bueno@metempsy.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2214034Sjavier.bueno@metempsy.com * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2314034Sjavier.bueno@metempsy.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2414034Sjavier.bueno@metempsy.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2514034Sjavier.bueno@metempsy.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2614034Sjavier.bueno@metempsy.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2714034Sjavier.bueno@metempsy.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2814034Sjavier.bueno@metempsy.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2914034Sjavier.bueno@metempsy.com * 3014034Sjavier.bueno@metempsy.com * Author: Daniel A. Jiménez 3114034Sjavier.bueno@metempsy.com * Adapted to gem5 by: Javier Bueno Hedo 3214034Sjavier.bueno@metempsy.com * 3314034Sjavier.bueno@metempsy.com */ 3414034Sjavier.bueno@metempsy.com 3514034Sjavier.bueno@metempsy.com /* 3614034Sjavier.bueno@metempsy.com * Multiperspective Perceptron Predictor (by Daniel A. Jiménez) 3714034Sjavier.bueno@metempsy.com */ 3814034Sjavier.bueno@metempsy.com 3914034Sjavier.bueno@metempsy.com#include "cpu/pred/multiperspective_perceptron.hh" 4014034Sjavier.bueno@metempsy.com 4114081Sjavier.bueno@metempsy.com#include "base/random.hh" 4214034Sjavier.bueno@metempsy.com#include "debug/Branch.hh" 4314034Sjavier.bueno@metempsy.com 4414034Sjavier.bueno@metempsy.comint 4514034Sjavier.bueno@metempsy.comMultiperspectivePerceptron::xlat[] = 4614034Sjavier.bueno@metempsy.com {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, 4714034Sjavier.bueno@metempsy.com 69,76,85,94,106,}; 4814034Sjavier.bueno@metempsy.comint 4914034Sjavier.bueno@metempsy.comMultiperspectivePerceptron::xlat4[] = 5014034Sjavier.bueno@metempsy.com {0,4,5,7,9,11,12,14,16,17,19,22,28,33,39,45,}; 5114034Sjavier.bueno@metempsy.com 5214034Sjavier.bueno@metempsy.comMultiperspectivePerceptron::ThreadData::ThreadData(int num_filters, 5314034Sjavier.bueno@metempsy.com int n_local_histories, int local_history_length, int assoc, 5414034Sjavier.bueno@metempsy.com const std::vector<std::vector<int>> &blurrypath_bits, int path_length, 5514034Sjavier.bueno@metempsy.com int ghist_length, int block_size, 5614034Sjavier.bueno@metempsy.com const std::vector<std::vector<std::vector<bool>>> &acyclic_bits, 5714034Sjavier.bueno@metempsy.com const std::vector<int> &modhist_indices, 5814034Sjavier.bueno@metempsy.com const std::vector<int> &modhist_lengths, 5914034Sjavier.bueno@metempsy.com const std::vector<int> &modpath_indices, 6014034Sjavier.bueno@metempsy.com const std::vector<int> &modpath_lengths, 6114034Sjavier.bueno@metempsy.com const std::vector<int> &table_sizes, int n_sign_bits) 6214034Sjavier.bueno@metempsy.com : filterTable(num_filters), acyclic_histories(acyclic_bits.size()), 6314034Sjavier.bueno@metempsy.com acyclic2_histories(acyclic_bits.size()), 6414034Sjavier.bueno@metempsy.com blurrypath_histories(blurrypath_bits.size()), 6514034Sjavier.bueno@metempsy.com ghist_words(ghist_length/block_size+1, 0), 6614034Sjavier.bueno@metempsy.com path_history(path_length, 0), imli_counter(4,0), 6714034Sjavier.bueno@metempsy.com localHistories(n_local_histories, local_history_length), 6814034Sjavier.bueno@metempsy.com recency_stack(assoc), last_ghist_bit(false), occupancy(0) 6914034Sjavier.bueno@metempsy.com{ 7014034Sjavier.bueno@metempsy.com for (int i = 0; i < blurrypath_bits.size(); i+= 1) { 7114034Sjavier.bueno@metempsy.com blurrypath_histories[i].resize(blurrypath_bits[i].size()); 7214034Sjavier.bueno@metempsy.com } 7314034Sjavier.bueno@metempsy.com 7414034Sjavier.bueno@metempsy.com for (int i = 0; i < acyclic_bits.size(); i += 1) { 7514034Sjavier.bueno@metempsy.com acyclic_histories[i].resize(acyclic_bits[i].size()); 7614034Sjavier.bueno@metempsy.com acyclic2_histories[i].resize(acyclic_bits[i].size()); 7714034Sjavier.bueno@metempsy.com } 7814034Sjavier.bueno@metempsy.com 7914034Sjavier.bueno@metempsy.com int max_modhist_idx = -1; 8014034Sjavier.bueno@metempsy.com for (auto &elem : modhist_indices) { 8114034Sjavier.bueno@metempsy.com max_modhist_idx = (max_modhist_idx < elem) ? elem : max_modhist_idx; 8214034Sjavier.bueno@metempsy.com } 8314034Sjavier.bueno@metempsy.com if (max_modhist_idx >= 0) { 8414034Sjavier.bueno@metempsy.com mod_histories.resize(max_modhist_idx + 1); 8514034Sjavier.bueno@metempsy.com } 8614034Sjavier.bueno@metempsy.com for (int i = 0; i < modhist_lengths.size(); i+= 1) { 8714034Sjavier.bueno@metempsy.com mod_histories[modhist_indices[i]].resize(modhist_lengths[i]); 8814034Sjavier.bueno@metempsy.com } 8914034Sjavier.bueno@metempsy.com 9014034Sjavier.bueno@metempsy.com int max_modpath_idx = -1; 9114034Sjavier.bueno@metempsy.com for (auto &elem : modpath_indices) { 9214034Sjavier.bueno@metempsy.com max_modpath_idx = (max_modpath_idx < elem) ? elem : max_modpath_idx; 9314034Sjavier.bueno@metempsy.com } 9414034Sjavier.bueno@metempsy.com if (max_modpath_idx >= 0) { 9514034Sjavier.bueno@metempsy.com modpath_histories.resize(max_modpath_idx + 1); 9614034Sjavier.bueno@metempsy.com } 9714034Sjavier.bueno@metempsy.com for (int i = 0; i < modpath_lengths.size(); i+= 1) { 9814034Sjavier.bueno@metempsy.com modpath_histories[modpath_indices[i]].resize(modpath_lengths[i]); 9914034Sjavier.bueno@metempsy.com } 10014034Sjavier.bueno@metempsy.com 10114034Sjavier.bueno@metempsy.com for (int i = 0; i < table_sizes.size(); i += 1) { 10214034Sjavier.bueno@metempsy.com mpreds.push_back(0); 10314034Sjavier.bueno@metempsy.com tables.push_back(std::vector<short int>(table_sizes[i])); 10414034Sjavier.bueno@metempsy.com sign_bits.push_back(std::vector<std::array<bool, 2>>(table_sizes[i])); 10514034Sjavier.bueno@metempsy.com for (int j = 0; j < table_sizes[i]; j += 1) { 10614034Sjavier.bueno@metempsy.com for (int k = 0; k < n_sign_bits; k += 1) { 10714034Sjavier.bueno@metempsy.com sign_bits[i][j][k] = (i & 1) | (k & 1); 10814034Sjavier.bueno@metempsy.com } 10914034Sjavier.bueno@metempsy.com } 11014034Sjavier.bueno@metempsy.com } 11114034Sjavier.bueno@metempsy.com} 11214034Sjavier.bueno@metempsy.com 11314034Sjavier.bueno@metempsy.comMultiperspectivePerceptron::MultiperspectivePerceptron( 11414034Sjavier.bueno@metempsy.com const MultiperspectivePerceptronParams *p) : BPredUnit(p), 11514034Sjavier.bueno@metempsy.com blockSize(p->block_size), pcshift(p->pcshift), threshold(p->threshold), 11614034Sjavier.bueno@metempsy.com bias0(p->bias0), bias1(p->bias1), biasmostly0(p->biasmostly0), 11714034Sjavier.bueno@metempsy.com biasmostly1(p->biasmostly1), nbest(p->nbest), tunebits(p->tunebits), 11814034Sjavier.bueno@metempsy.com hshift(p->hshift), imli_mask1(p->imli_mask1), imli_mask4(p->imli_mask4), 11914034Sjavier.bueno@metempsy.com recencypos_mask(p->recencypos_mask), fudge(p->fudge), 12014034Sjavier.bueno@metempsy.com n_sign_bits(p->n_sign_bits), pcbit(p->pcbit), decay(p->decay), 12114034Sjavier.bueno@metempsy.com record_mask(p->record_mask), hash_taken(p->hash_taken), 12214034Sjavier.bueno@metempsy.com tuneonly(p->tuneonly), extra_rounds(p->extra_rounds), speed(p->speed), 12314034Sjavier.bueno@metempsy.com budgetbits(p->budgetbits), speculative_update(p->speculative_update), 12414034Sjavier.bueno@metempsy.com threadData(p->numThreads, nullptr), doing_local(false), 12514081Sjavier.bueno@metempsy.com doing_recency(false), assoc(0), ghist_length(p->initial_ghist_length), 12614081Sjavier.bueno@metempsy.com modghist_length(1), path_length(1), thresholdCounter(0), 12714081Sjavier.bueno@metempsy.com theta(p->initial_theta), extrabits(0), imli_counter_bits(4), 12814081Sjavier.bueno@metempsy.com modhist_indices(), modhist_lengths(), modpath_indices(), modpath_lengths() 12914034Sjavier.bueno@metempsy.com{ 13014034Sjavier.bueno@metempsy.com fatal_if(speculative_update, "Speculative update not implemented"); 13114034Sjavier.bueno@metempsy.com} 13214034Sjavier.bueno@metempsy.com 13314034Sjavier.bueno@metempsy.comvoid 13414081Sjavier.bueno@metempsy.comMultiperspectivePerceptron::setExtraBits(int bits) 13514081Sjavier.bueno@metempsy.com{ 13614081Sjavier.bueno@metempsy.com extrabits = bits; 13714081Sjavier.bueno@metempsy.com} 13814081Sjavier.bueno@metempsy.com 13914081Sjavier.bueno@metempsy.comvoid 14014034Sjavier.bueno@metempsy.comMultiperspectivePerceptron::init() 14114034Sjavier.bueno@metempsy.com{ 14214034Sjavier.bueno@metempsy.com createSpecs(); 14314034Sjavier.bueno@metempsy.com 14414034Sjavier.bueno@metempsy.com for (auto &spec : specs) { 14514034Sjavier.bueno@metempsy.com // initial assignation of values 14614034Sjavier.bueno@metempsy.com table_sizes.push_back(spec->size); 14714034Sjavier.bueno@metempsy.com } 14814034Sjavier.bueno@metempsy.com 14914034Sjavier.bueno@metempsy.com // Update bit requirements and runtime values 15014034Sjavier.bueno@metempsy.com for (auto &spec : specs) { 15114034Sjavier.bueno@metempsy.com spec->setBitRequirements(); 15214034Sjavier.bueno@metempsy.com } 15314034Sjavier.bueno@metempsy.com const MultiperspectivePerceptronParams *p = 15414034Sjavier.bueno@metempsy.com static_cast<const MultiperspectivePerceptronParams *>(params()); 15514034Sjavier.bueno@metempsy.com 15614034Sjavier.bueno@metempsy.com computeBits(p->num_filter_entries, p->num_local_histories, 15714081Sjavier.bueno@metempsy.com p->local_history_length, p->ignore_path_size); 15814034Sjavier.bueno@metempsy.com 15914034Sjavier.bueno@metempsy.com for (int i = 0; i < threadData.size(); i += 1) { 16014034Sjavier.bueno@metempsy.com threadData[i] = new ThreadData(p->num_filter_entries, 16114034Sjavier.bueno@metempsy.com p->num_local_histories, 16214034Sjavier.bueno@metempsy.com p->local_history_length, assoc, 16314034Sjavier.bueno@metempsy.com blurrypath_bits, path_length, 16414034Sjavier.bueno@metempsy.com ghist_length, blockSize, acyclic_bits, 16514034Sjavier.bueno@metempsy.com modhist_indices, modhist_lengths, 16614034Sjavier.bueno@metempsy.com modpath_indices, modpath_lengths, 16714034Sjavier.bueno@metempsy.com table_sizes, n_sign_bits); 16814034Sjavier.bueno@metempsy.com } 16914034Sjavier.bueno@metempsy.com} 17014034Sjavier.bueno@metempsy.com 17114034Sjavier.bueno@metempsy.comvoid 17214034Sjavier.bueno@metempsy.comMultiperspectivePerceptron::computeBits(int num_filter_entries, 17314081Sjavier.bueno@metempsy.com int nlocal_histories, int local_history_length, bool ignore_path_size) 17414081Sjavier.bueno@metempsy.com{ 17514081Sjavier.bueno@metempsy.com int totalbits = extrabits; 17614034Sjavier.bueno@metempsy.com for (auto &imli_bits : imli_counter_bits) { 17714034Sjavier.bueno@metempsy.com totalbits += imli_bits; 17814034Sjavier.bueno@metempsy.com } 17914034Sjavier.bueno@metempsy.com totalbits += ghist_length; 18014081Sjavier.bueno@metempsy.com if (!ignore_path_size) { 18114081Sjavier.bueno@metempsy.com totalbits += path_length * 16; 18214081Sjavier.bueno@metempsy.com } 18314034Sjavier.bueno@metempsy.com totalbits += (threshold >= 0) ? (tunebits * specs.size()) : 0; 18414034Sjavier.bueno@metempsy.com for (auto &len : modhist_lengths) { 18514034Sjavier.bueno@metempsy.com totalbits += len; 18614034Sjavier.bueno@metempsy.com } 18714081Sjavier.bueno@metempsy.com if (!ignore_path_size) { 18814081Sjavier.bueno@metempsy.com for (auto &len : modpath_lengths) { 18914081Sjavier.bueno@metempsy.com totalbits += 16 * len; 19014081Sjavier.bueno@metempsy.com } 19114034Sjavier.bueno@metempsy.com } 19214034Sjavier.bueno@metempsy.com totalbits += doing_local ? (nlocal_histories * local_history_length) : 0; 19314034Sjavier.bueno@metempsy.com totalbits += doing_recency ? (assoc * 16) : 0; 19414034Sjavier.bueno@metempsy.com 19514034Sjavier.bueno@metempsy.com for (auto &bv : blurrypath_bits) { 19614034Sjavier.bueno@metempsy.com for (auto &bve : bv) { 19714034Sjavier.bueno@metempsy.com totalbits += bve; 19814034Sjavier.bueno@metempsy.com } 19914034Sjavier.bueno@metempsy.com } 20014034Sjavier.bueno@metempsy.com totalbits += num_filter_entries * 2; 20114034Sjavier.bueno@metempsy.com 20214034Sjavier.bueno@metempsy.com for (auto &abi : acyclic_bits) { 20314034Sjavier.bueno@metempsy.com for (auto &abj : abi) { 20414034Sjavier.bueno@metempsy.com for (auto abk : abj) { 20514034Sjavier.bueno@metempsy.com totalbits += abk; 20614034Sjavier.bueno@metempsy.com } 20714034Sjavier.bueno@metempsy.com } 20814034Sjavier.bueno@metempsy.com } 20914034Sjavier.bueno@metempsy.com 21014034Sjavier.bueno@metempsy.com int remaining = budgetbits - totalbits; 21114034Sjavier.bueno@metempsy.com 21214034Sjavier.bueno@metempsy.com // count the tables that have already been assigned sizes 21314034Sjavier.bueno@metempsy.com int num_sized = 0; 21414034Sjavier.bueno@metempsy.com for (int i = 0; i < specs.size(); i +=1) { 21514034Sjavier.bueno@metempsy.com if (table_sizes[i] != 0) { 21614034Sjavier.bueno@metempsy.com int sz = table_sizes[i] * (specs[i]->width + (n_sign_bits - 1)); 21714034Sjavier.bueno@metempsy.com totalbits += sz; 21814034Sjavier.bueno@metempsy.com remaining -= sz; 21914034Sjavier.bueno@metempsy.com num_sized += 1; 22014034Sjavier.bueno@metempsy.com } 22114034Sjavier.bueno@metempsy.com } 22214034Sjavier.bueno@metempsy.com 22314034Sjavier.bueno@metempsy.com // whatever is left, we divide among the rest of the tables 22414034Sjavier.bueno@metempsy.com int table_size_bits = (remaining / (specs.size()-num_sized)); 22514034Sjavier.bueno@metempsy.com for (int i = 0; i < specs.size(); i += 1) { 22614034Sjavier.bueno@metempsy.com // if a table doesn't have a size yet, give it one and count those bits 22714034Sjavier.bueno@metempsy.com if (!table_sizes[i]) { 22814034Sjavier.bueno@metempsy.com int my_table_size = table_size_bits / 22914034Sjavier.bueno@metempsy.com (specs[i]->width + (n_sign_bits - 1)); // extra sign bits 23014034Sjavier.bueno@metempsy.com table_sizes[i] = my_table_size; 23114034Sjavier.bueno@metempsy.com totalbits += my_table_size * (specs[i]->width + (n_sign_bits - 1)); 23214034Sjavier.bueno@metempsy.com } 23314034Sjavier.bueno@metempsy.com } 23414034Sjavier.bueno@metempsy.com 23514034Sjavier.bueno@metempsy.com DPRINTF(Branch, "%d bits of metadata so far, %d left out of " 23614034Sjavier.bueno@metempsy.com "%d total budget\n", totalbits, remaining, budgetbits); 23714034Sjavier.bueno@metempsy.com DPRINTF(Branch, "table size is %d bits, %d entries for 5 bit, %d entries " 23814034Sjavier.bueno@metempsy.com "for 6 bit\n", table_size_bits, 23914034Sjavier.bueno@metempsy.com table_size_bits / (5 + (n_sign_bits - 1)), 24014034Sjavier.bueno@metempsy.com table_size_bits / (6 + (n_sign_bits - 1))); 24114034Sjavier.bueno@metempsy.com DPRINTF(Branch, "%d total bits (%0.2fKB)\n", totalbits, 24214034Sjavier.bueno@metempsy.com totalbits / 8192.0); 24314034Sjavier.bueno@metempsy.com} 24414034Sjavier.bueno@metempsy.com 24514034Sjavier.bueno@metempsy.comvoid 24614034Sjavier.bueno@metempsy.comMultiperspectivePerceptron::findBest(ThreadID tid, 24714034Sjavier.bueno@metempsy.com std::vector<int> &best_preds) const 24814034Sjavier.bueno@metempsy.com{ 24914034Sjavier.bueno@metempsy.com if (threshold < 0) { 25014034Sjavier.bueno@metempsy.com return; 25114034Sjavier.bueno@metempsy.com } 25214034Sjavier.bueno@metempsy.com struct BestPair { 25314034Sjavier.bueno@metempsy.com int index; 25414034Sjavier.bueno@metempsy.com int mpreds; 25514034Sjavier.bueno@metempsy.com bool operator<(BestPair const &bp) const 25614034Sjavier.bueno@metempsy.com { 25714034Sjavier.bueno@metempsy.com return mpreds < bp.mpreds; 25814034Sjavier.bueno@metempsy.com } 25914034Sjavier.bueno@metempsy.com }; 26014034Sjavier.bueno@metempsy.com std::vector<BestPair> pairs(best_preds.size()); 26114034Sjavier.bueno@metempsy.com for (int i = 0; i < best_preds.size(); i += 1) { 26214034Sjavier.bueno@metempsy.com pairs[i].index = i; 26314034Sjavier.bueno@metempsy.com pairs[i].mpreds = threadData[tid]->mpreds[i]; 26414034Sjavier.bueno@metempsy.com } 26514034Sjavier.bueno@metempsy.com std::sort(pairs.begin(), pairs.end()); 26614034Sjavier.bueno@metempsy.com for (int i = 0; i < (std::min(nbest, (int) best_preds.size())); i += 1) { 26714034Sjavier.bueno@metempsy.com best_preds[i] = pairs[i].index; 26814034Sjavier.bueno@metempsy.com } 26914034Sjavier.bueno@metempsy.com} 27014034Sjavier.bueno@metempsy.com 27114034Sjavier.bueno@metempsy.comunsigned int 27214034Sjavier.bueno@metempsy.comMultiperspectivePerceptron::getIndex(ThreadID tid, const MPPBranchInfo &bi, 27314034Sjavier.bueno@metempsy.com const HistorySpec &spec, int index) const 27414034Sjavier.bueno@metempsy.com{ 27514034Sjavier.bueno@metempsy.com unsigned int g = spec.getHash(tid, bi.getPC(), bi.getPC2(), index); 27614034Sjavier.bueno@metempsy.com unsigned long long int h = g; 27714034Sjavier.bueno@metempsy.com // shift the hash from the feature to xor with the hashed PC 27814034Sjavier.bueno@metempsy.com if (hshift < 0) { 27914034Sjavier.bueno@metempsy.com h <<= -hshift; 28014034Sjavier.bueno@metempsy.com h ^= bi.getPC2(); 28114034Sjavier.bueno@metempsy.com } else { 28214034Sjavier.bueno@metempsy.com h <<= hshift; 28314034Sjavier.bueno@metempsy.com h ^= bi.getHPC(); 28414034Sjavier.bueno@metempsy.com } 28514034Sjavier.bueno@metempsy.com // xor in the imli counter(s) and/or recency position based on the masks 28614034Sjavier.bueno@metempsy.com if ((1ull<<index) & imli_mask1) { 28714034Sjavier.bueno@metempsy.com h ^= threadData[tid]->imli_counter[0]; 28814034Sjavier.bueno@metempsy.com } 28914034Sjavier.bueno@metempsy.com if ((1ull<<index) & imli_mask4) { 29014034Sjavier.bueno@metempsy.com h ^= threadData[tid]->imli_counter[3]; 29114034Sjavier.bueno@metempsy.com } 29214034Sjavier.bueno@metempsy.com if (doing_recency) { 29314034Sjavier.bueno@metempsy.com if ((1ull<<index) & recencypos_mask) { 29414034Sjavier.bueno@metempsy.com h ^= RECENCYPOS::hash(threadData[tid]->recency_stack, table_sizes, 29514034Sjavier.bueno@metempsy.com bi.getPC2(), 31, index); 29614034Sjavier.bueno@metempsy.com } 29714034Sjavier.bueno@metempsy.com } 29814034Sjavier.bueno@metempsy.com h %= table_sizes[index]; 29914034Sjavier.bueno@metempsy.com return h; 30014034Sjavier.bueno@metempsy.com} 30114034Sjavier.bueno@metempsy.com 30214034Sjavier.bueno@metempsy.comint 30314034Sjavier.bueno@metempsy.comMultiperspectivePerceptron::computeOutput(ThreadID tid, MPPBranchInfo &bi) 30414034Sjavier.bueno@metempsy.com{ 30514034Sjavier.bueno@metempsy.com // list of best predictors 30614034Sjavier.bueno@metempsy.com std::vector<int> best_preds(specs.size(), -1); 30714034Sjavier.bueno@metempsy.com 30814034Sjavier.bueno@metempsy.com // initialize sum 30914034Sjavier.bueno@metempsy.com bi.yout = 0; 31014034Sjavier.bueno@metempsy.com 31114034Sjavier.bueno@metempsy.com // bias the prediction by whether the local history is 31214034Sjavier.bueno@metempsy.com // one of four distinctive patterns 31314034Sjavier.bueno@metempsy.com int lhist = threadData[tid]->localHistories[bi.getPC()]; 31414034Sjavier.bueno@metempsy.com int history_len = threadData[tid]->localHistories.getLocalHistoryLength(); 31514034Sjavier.bueno@metempsy.com if (lhist == 0) { 31614034Sjavier.bueno@metempsy.com bi.yout = bias0; 31714034Sjavier.bueno@metempsy.com } else if (lhist == ((1<<history_len)-1)) { 31814034Sjavier.bueno@metempsy.com bi.yout = bias1; 31914034Sjavier.bueno@metempsy.com } else if (lhist == (1<<(history_len-1))) { 32014034Sjavier.bueno@metempsy.com bi.yout = biasmostly0; 32114034Sjavier.bueno@metempsy.com } else if (lhist == ((1<<(history_len-1))-1)) { 32214034Sjavier.bueno@metempsy.com bi.yout = biasmostly1; 32314034Sjavier.bueno@metempsy.com } 32414034Sjavier.bueno@metempsy.com // find the best subset of features to use in case of a low-confidence 32514034Sjavier.bueno@metempsy.com // branch 32614034Sjavier.bueno@metempsy.com findBest(tid, best_preds); 32714034Sjavier.bueno@metempsy.com 32814034Sjavier.bueno@metempsy.com // begin computation of the sum for low-confidence branch 32914034Sjavier.bueno@metempsy.com int bestval = 0; 33014034Sjavier.bueno@metempsy.com 33114034Sjavier.bueno@metempsy.com for (int i = 0; i < specs.size(); i += 1) { 33214034Sjavier.bueno@metempsy.com HistorySpec const &spec = *specs[i]; 33314034Sjavier.bueno@metempsy.com // get the hash to index the table 33414034Sjavier.bueno@metempsy.com unsigned int hashed_idx = getIndex(tid, bi, spec, i); 33514034Sjavier.bueno@metempsy.com // add the weight; first get the weight's magnitude 33614034Sjavier.bueno@metempsy.com int counter = threadData[tid]->tables[i][hashed_idx]; 33714034Sjavier.bueno@metempsy.com // get the sign 33814034Sjavier.bueno@metempsy.com bool sign = 33914034Sjavier.bueno@metempsy.com threadData[tid]->sign_bits[i][hashed_idx][bi.getHPC() % n_sign_bits]; 34014034Sjavier.bueno@metempsy.com // apply the transfer function and multiply by a coefficient 34114034Sjavier.bueno@metempsy.com int weight = spec.coeff * ((spec.width == 5) ? 34214034Sjavier.bueno@metempsy.com xlat4[counter] : xlat[counter]); 34314034Sjavier.bueno@metempsy.com // apply the sign 34414034Sjavier.bueno@metempsy.com int val = sign ? -weight : weight; 34514034Sjavier.bueno@metempsy.com // add the value 34614034Sjavier.bueno@metempsy.com bi.yout += val; 34714034Sjavier.bueno@metempsy.com // if this is one of those good features, add the value to bestval 34814034Sjavier.bueno@metempsy.com if (threshold >= 0) { 34914034Sjavier.bueno@metempsy.com for (int j = 0; 35014034Sjavier.bueno@metempsy.com j < std::min(nbest, (int) best_preds.size()); 35114034Sjavier.bueno@metempsy.com j += 1) 35214034Sjavier.bueno@metempsy.com { 35314034Sjavier.bueno@metempsy.com if (best_preds[j] == i) { 35414034Sjavier.bueno@metempsy.com bestval += val; 35514034Sjavier.bueno@metempsy.com break; 35614034Sjavier.bueno@metempsy.com } 35714034Sjavier.bueno@metempsy.com } 35814034Sjavier.bueno@metempsy.com } 35914034Sjavier.bueno@metempsy.com } 36014034Sjavier.bueno@metempsy.com // apply a fudge factor to affect when training is triggered 36114034Sjavier.bueno@metempsy.com bi.yout *= fudge; 36214034Sjavier.bueno@metempsy.com return bestval; 36314034Sjavier.bueno@metempsy.com} 36414034Sjavier.bueno@metempsy.com 36514034Sjavier.bueno@metempsy.comvoid 36614034Sjavier.bueno@metempsy.comMultiperspectivePerceptron::satIncDec(bool taken, bool &sign, int &counter, 36714034Sjavier.bueno@metempsy.com int max_weight) const 36814034Sjavier.bueno@metempsy.com{ 36914034Sjavier.bueno@metempsy.com if (taken) { 37014034Sjavier.bueno@metempsy.com // increment sign/magnitude 37114034Sjavier.bueno@metempsy.com if (sign) { 37214034Sjavier.bueno@metempsy.com // go toward 0 away from negative max weight 37314034Sjavier.bueno@metempsy.com if (counter == 0) { 37414034Sjavier.bueno@metempsy.com sign = false; // moved to positive 0 37514034Sjavier.bueno@metempsy.com } else { 37614034Sjavier.bueno@metempsy.com counter -= 1; 37714034Sjavier.bueno@metempsy.com } 37814034Sjavier.bueno@metempsy.com } else { 37914034Sjavier.bueno@metempsy.com // go toward max weight away from 0 38014034Sjavier.bueno@metempsy.com if (counter < max_weight) { 38114034Sjavier.bueno@metempsy.com counter += 1; 38214034Sjavier.bueno@metempsy.com } 38314034Sjavier.bueno@metempsy.com } 38414034Sjavier.bueno@metempsy.com } else { 38514034Sjavier.bueno@metempsy.com // decrement sign/magnitude 38614034Sjavier.bueno@metempsy.com if (sign) { 38714034Sjavier.bueno@metempsy.com // go toward negative max weight down from 0 38814034Sjavier.bueno@metempsy.com if (counter < max_weight) { 38914034Sjavier.bueno@metempsy.com counter += 1; 39014034Sjavier.bueno@metempsy.com } 39114034Sjavier.bueno@metempsy.com } else { 39214034Sjavier.bueno@metempsy.com // go toward 0 away from max weight 39314034Sjavier.bueno@metempsy.com if (counter == 0) { 39414034Sjavier.bueno@metempsy.com sign = true; // negative 0 39514034Sjavier.bueno@metempsy.com } else { 39614034Sjavier.bueno@metempsy.com counter -= 1; 39714034Sjavier.bueno@metempsy.com } 39814034Sjavier.bueno@metempsy.com } 39914034Sjavier.bueno@metempsy.com } 40014034Sjavier.bueno@metempsy.com} 40114034Sjavier.bueno@metempsy.com 40214034Sjavier.bueno@metempsy.comvoid 40314034Sjavier.bueno@metempsy.comMultiperspectivePerceptron::train(ThreadID tid, MPPBranchInfo &bi, bool taken) 40414034Sjavier.bueno@metempsy.com{ 40514034Sjavier.bueno@metempsy.com std::vector<std::vector<short int>> &tables = threadData[tid]->tables; 40614034Sjavier.bueno@metempsy.com std::vector<std::vector<std::array<bool, 2>>> &sign_bits = 40714034Sjavier.bueno@metempsy.com threadData[tid]->sign_bits; 40814034Sjavier.bueno@metempsy.com std::vector<int> &mpreds = threadData[tid]->mpreds; 40914034Sjavier.bueno@metempsy.com // was the prediction correct? 41014034Sjavier.bueno@metempsy.com bool correct = (bi.yout >= 1) == taken; 41114034Sjavier.bueno@metempsy.com // what is the magnitude of yout? 41214034Sjavier.bueno@metempsy.com int abs_yout = abs(bi.yout); 41314034Sjavier.bueno@metempsy.com // keep track of mispredictions per table 41414034Sjavier.bueno@metempsy.com if (threshold >= 0) if (!tuneonly || (abs_yout <= threshold)) { 41514034Sjavier.bueno@metempsy.com bool halve = false; 41614034Sjavier.bueno@metempsy.com 41714034Sjavier.bueno@metempsy.com // for each table, figure out if there was a misprediction 41814034Sjavier.bueno@metempsy.com for (int i = 0; i < specs.size(); i += 1) { 41914034Sjavier.bueno@metempsy.com HistorySpec const &spec = *specs[i]; 42014034Sjavier.bueno@metempsy.com // get the hash to index the table 42114034Sjavier.bueno@metempsy.com unsigned int hashed_idx = getIndex(tid, bi, spec, i); 42214034Sjavier.bueno@metempsy.com bool sign = sign_bits[i][hashed_idx][bi.getHPC() % n_sign_bits]; 42314034Sjavier.bueno@metempsy.com int counter = tables[i][hashed_idx]; 42414034Sjavier.bueno@metempsy.com int weight = spec.coeff * ((spec.width == 5) ? 42514034Sjavier.bueno@metempsy.com xlat4[counter] : xlat[counter]); 42614034Sjavier.bueno@metempsy.com if (sign) weight = -weight; 42714034Sjavier.bueno@metempsy.com bool pred = weight >= 1; 42814034Sjavier.bueno@metempsy.com if (pred != taken) { 42914034Sjavier.bueno@metempsy.com mpreds[i] += 1; 43014034Sjavier.bueno@metempsy.com if (mpreds[i] == (1 << tunebits) - 1) { 43114034Sjavier.bueno@metempsy.com halve = true; 43214034Sjavier.bueno@metempsy.com } 43314034Sjavier.bueno@metempsy.com } 43414034Sjavier.bueno@metempsy.com } 43514034Sjavier.bueno@metempsy.com // if we reach the maximum counter value, halve all the counters 43614034Sjavier.bueno@metempsy.com if (halve) { 43714034Sjavier.bueno@metempsy.com for (int i = 0; i < specs.size(); i += 1) { 43814034Sjavier.bueno@metempsy.com mpreds[i] /= 2; 43914034Sjavier.bueno@metempsy.com } 44014034Sjavier.bueno@metempsy.com } 44114034Sjavier.bueno@metempsy.com } 44214034Sjavier.bueno@metempsy.com // if the branch was predicted incorrectly or the correct 44314034Sjavier.bueno@metempsy.com // prediction was weak, update the weights 44414034Sjavier.bueno@metempsy.com bool do_train = !correct || (abs_yout <= theta); 44514034Sjavier.bueno@metempsy.com if (!do_train) return; 44614034Sjavier.bueno@metempsy.com 44714034Sjavier.bueno@metempsy.com // adaptive theta training, adapted from O-GEHL 44814034Sjavier.bueno@metempsy.com if (!correct) { 44914034Sjavier.bueno@metempsy.com thresholdCounter += 1; 45014034Sjavier.bueno@metempsy.com if (thresholdCounter >= speed) { 45114034Sjavier.bueno@metempsy.com theta += 1; 45214034Sjavier.bueno@metempsy.com thresholdCounter = 0; 45314034Sjavier.bueno@metempsy.com } 45414034Sjavier.bueno@metempsy.com } 45514034Sjavier.bueno@metempsy.com if (correct && abs_yout < theta) { 45614034Sjavier.bueno@metempsy.com thresholdCounter -= 1; 45714034Sjavier.bueno@metempsy.com if (thresholdCounter <= -speed) { 45814034Sjavier.bueno@metempsy.com theta -= 1; 45914034Sjavier.bueno@metempsy.com thresholdCounter = 0; 46014034Sjavier.bueno@metempsy.com } 46114034Sjavier.bueno@metempsy.com } 46214034Sjavier.bueno@metempsy.com 46314034Sjavier.bueno@metempsy.com // train the weights, computing what the value of yout 46414034Sjavier.bueno@metempsy.com // would have been if these updates had been applied before 46514034Sjavier.bueno@metempsy.com int newyout = 0; 46614034Sjavier.bueno@metempsy.com for (int i = 0; i < specs.size(); i += 1) { 46714034Sjavier.bueno@metempsy.com HistorySpec const &spec = *specs[i]; 46814034Sjavier.bueno@metempsy.com // get the magnitude 46914034Sjavier.bueno@metempsy.com unsigned int hashed_idx = getIndex(tid, bi, spec, i); 47014034Sjavier.bueno@metempsy.com int counter = tables[i][hashed_idx]; 47114034Sjavier.bueno@metempsy.com // get the sign 47214034Sjavier.bueno@metempsy.com bool sign = sign_bits[i][hashed_idx][bi.getHPC() % n_sign_bits]; 47314034Sjavier.bueno@metempsy.com // increment/decrement if taken/not taken 47414034Sjavier.bueno@metempsy.com satIncDec(taken, sign, counter, (1 << (spec.width - 1)) - 1); 47514034Sjavier.bueno@metempsy.com // update the magnitude and sign 47614034Sjavier.bueno@metempsy.com tables[i][hashed_idx] = counter; 47714034Sjavier.bueno@metempsy.com sign_bits[i][hashed_idx][bi.getHPC() % n_sign_bits] = sign; 47814034Sjavier.bueno@metempsy.com int weight = ((spec.width == 5) ? xlat4[counter] : xlat[counter]); 47914034Sjavier.bueno@metempsy.com // update the new version of yout 48014034Sjavier.bueno@metempsy.com if (sign) { 48114034Sjavier.bueno@metempsy.com newyout -= weight; 48214034Sjavier.bueno@metempsy.com } else { 48314034Sjavier.bueno@metempsy.com newyout += weight; 48414034Sjavier.bueno@metempsy.com } 48514034Sjavier.bueno@metempsy.com } 48614034Sjavier.bueno@metempsy.com 48714034Sjavier.bueno@metempsy.com // if the prediction still would have been incorrect even 48814034Sjavier.bueno@metempsy.com // with the updated weights, update some more weights to 48914034Sjavier.bueno@metempsy.com // try to fix the problem 49014034Sjavier.bueno@metempsy.com if ((newyout >= 1) != taken) { 49114034Sjavier.bueno@metempsy.com if (extra_rounds != -1) { 49214034Sjavier.bueno@metempsy.com int round_counter = 0; 49314034Sjavier.bueno@metempsy.com bool found; 49414034Sjavier.bueno@metempsy.com do { 49514034Sjavier.bueno@metempsy.com // udpate a random weight 49614034Sjavier.bueno@metempsy.com int besti = -1; 49714081Sjavier.bueno@metempsy.com int nrand = random_mt.random<int>() % specs.size(); 49814034Sjavier.bueno@metempsy.com int pout; 49914034Sjavier.bueno@metempsy.com found = false; 50014034Sjavier.bueno@metempsy.com for (int j = 0; j < specs.size(); j += 1) { 50114034Sjavier.bueno@metempsy.com int i = (nrand + j) % specs.size(); 50214034Sjavier.bueno@metempsy.com HistorySpec const &spec = *specs[i]; 50314034Sjavier.bueno@metempsy.com unsigned int hashed_idx = getIndex(tid, bi, spec, i); 50414034Sjavier.bueno@metempsy.com int counter = tables[i][hashed_idx]; 50514034Sjavier.bueno@metempsy.com bool sign = 50614034Sjavier.bueno@metempsy.com sign_bits[i][hashed_idx][bi.getHPC() % n_sign_bits]; 50714034Sjavier.bueno@metempsy.com int weight = ((spec.width == 5) ? 50814034Sjavier.bueno@metempsy.com xlat4[counter] : xlat[counter]); 50914034Sjavier.bueno@metempsy.com int signed_weight = sign ? -weight : weight; 51014034Sjavier.bueno@metempsy.com pout = newyout - signed_weight; 51114034Sjavier.bueno@metempsy.com if ((pout >= 1) == taken) { 51214034Sjavier.bueno@metempsy.com // we have found a weight that if we blow 51314034Sjavier.bueno@metempsy.com // it away will help! 51414034Sjavier.bueno@metempsy.com besti = i; 51514034Sjavier.bueno@metempsy.com break; 51614034Sjavier.bueno@metempsy.com } 51714034Sjavier.bueno@metempsy.com } 51814034Sjavier.bueno@metempsy.com if (besti != -1) { 51914034Sjavier.bueno@metempsy.com int i = besti; 52014034Sjavier.bueno@metempsy.com HistorySpec const &spec = *specs[i]; 52114034Sjavier.bueno@metempsy.com unsigned int hashed_idx = getIndex(tid, bi, spec, i); 52214034Sjavier.bueno@metempsy.com int counter = tables[i][hashed_idx]; 52314034Sjavier.bueno@metempsy.com bool sign = 52414034Sjavier.bueno@metempsy.com sign_bits[i][hashed_idx][bi.getHPC() % n_sign_bits]; 52514034Sjavier.bueno@metempsy.com if (counter > 1) { 52614034Sjavier.bueno@metempsy.com counter--; 52714034Sjavier.bueno@metempsy.com tables[i][hashed_idx] = counter; 52814034Sjavier.bueno@metempsy.com } 52914034Sjavier.bueno@metempsy.com int weight = ((spec.width == 5) ? 53014034Sjavier.bueno@metempsy.com xlat4[counter] : xlat[counter]); 53114034Sjavier.bueno@metempsy.com int signed_weight = sign ? -weight : weight; 53214034Sjavier.bueno@metempsy.com int out = pout + signed_weight; 53314034Sjavier.bueno@metempsy.com round_counter += 1; 53414034Sjavier.bueno@metempsy.com if ((out >= 1) != taken) { 53514034Sjavier.bueno@metempsy.com found = true; 53614034Sjavier.bueno@metempsy.com } 53714034Sjavier.bueno@metempsy.com } 53814034Sjavier.bueno@metempsy.com } while (found && round_counter < extra_rounds); 53914034Sjavier.bueno@metempsy.com } 54014034Sjavier.bueno@metempsy.com } 54114034Sjavier.bueno@metempsy.com} 54214034Sjavier.bueno@metempsy.com 54314034Sjavier.bueno@metempsy.comvoid 54414034Sjavier.bueno@metempsy.comMultiperspectivePerceptron::uncondBranch(ThreadID tid, Addr pc, 54514034Sjavier.bueno@metempsy.com void * &bp_history) 54614034Sjavier.bueno@metempsy.com{ 54714034Sjavier.bueno@metempsy.com MPPBranchInfo *bi = new MPPBranchInfo(pc, pcshift, false); 54814034Sjavier.bueno@metempsy.com std::vector<unsigned int> &ghist_words = threadData[tid]->ghist_words; 54914034Sjavier.bueno@metempsy.com 55014034Sjavier.bueno@metempsy.com bp_history = (void *)bi; 55114034Sjavier.bueno@metempsy.com unsigned short int pc2 = pc >> 2; 55214034Sjavier.bueno@metempsy.com bool ab = !(pc & (1<<pcbit)); 55314034Sjavier.bueno@metempsy.com for (int i = 0; i < ghist_length / blockSize + 1; i += 1) { 55414034Sjavier.bueno@metempsy.com bool ab_new = (ghist_words[i] >> (blockSize - 1)) & 1; 55514034Sjavier.bueno@metempsy.com ghist_words[i] <<= 1; 55614034Sjavier.bueno@metempsy.com ghist_words[i] |= ab; 55714034Sjavier.bueno@metempsy.com ghist_words[i] &= (1 << blockSize) - 1; 55814034Sjavier.bueno@metempsy.com ab = ab_new; 55914034Sjavier.bueno@metempsy.com } 56014034Sjavier.bueno@metempsy.com memmove(&threadData[tid]->path_history[1], 56114034Sjavier.bueno@metempsy.com &threadData[tid]->path_history[0], 56214034Sjavier.bueno@metempsy.com sizeof(unsigned short int) * (path_length - 1)); 56314034Sjavier.bueno@metempsy.com threadData[tid]->path_history[0] = pc2; 56414034Sjavier.bueno@metempsy.com} 56514034Sjavier.bueno@metempsy.com 56614034Sjavier.bueno@metempsy.combool 56714034Sjavier.bueno@metempsy.comMultiperspectivePerceptron::lookup(ThreadID tid, Addr instPC, 56814034Sjavier.bueno@metempsy.com void * &bp_history) 56914034Sjavier.bueno@metempsy.com{ 57014034Sjavier.bueno@metempsy.com MPPBranchInfo *bi = new MPPBranchInfo(instPC, pcshift, true); 57114034Sjavier.bueno@metempsy.com bp_history = (void *)bi; 57214034Sjavier.bueno@metempsy.com 57314034Sjavier.bueno@metempsy.com bool use_static = false; 57414034Sjavier.bueno@metempsy.com 57514034Sjavier.bueno@metempsy.com if (!threadData[tid]->filterTable.empty()) { 57614034Sjavier.bueno@metempsy.com unsigned int findex = 57714034Sjavier.bueno@metempsy.com bi->getHashFilter(threadData[tid]->last_ghist_bit) % 57814034Sjavier.bueno@metempsy.com threadData[tid]->filterTable.size(); 57914034Sjavier.bueno@metempsy.com FilterEntry &f = threadData[tid]->filterTable[findex]; 58014034Sjavier.bueno@metempsy.com if (f.alwaysNotTakenSoFar()) { 58114034Sjavier.bueno@metempsy.com bi->filtered = true; 58214034Sjavier.bueno@metempsy.com bi->prediction = false; 58314034Sjavier.bueno@metempsy.com return false; 58414034Sjavier.bueno@metempsy.com } else if (f.alwaysTakenSoFar()) { 58514034Sjavier.bueno@metempsy.com bi->filtered = true; 58614034Sjavier.bueno@metempsy.com bi->prediction = true; 58714034Sjavier.bueno@metempsy.com return true; 58814034Sjavier.bueno@metempsy.com } 58914034Sjavier.bueno@metempsy.com if (f.neverSeen()) { 59014034Sjavier.bueno@metempsy.com use_static = true; 59114034Sjavier.bueno@metempsy.com } 59214034Sjavier.bueno@metempsy.com } 59314034Sjavier.bueno@metempsy.com 59414034Sjavier.bueno@metempsy.com int bestval = computeOutput(tid, *bi); 59514034Sjavier.bueno@metempsy.com if (use_static) { 59614034Sjavier.bueno@metempsy.com bi->prediction = false; 59714034Sjavier.bueno@metempsy.com } else { 59814034Sjavier.bueno@metempsy.com if (abs(bi->yout) <= threshold) { 59914034Sjavier.bueno@metempsy.com bi->prediction = (bestval >= 1); 60014034Sjavier.bueno@metempsy.com } else { 60114034Sjavier.bueno@metempsy.com bi->prediction = (bi->yout >= 1); 60214034Sjavier.bueno@metempsy.com } 60314034Sjavier.bueno@metempsy.com } 60414034Sjavier.bueno@metempsy.com 60514034Sjavier.bueno@metempsy.com return bi->prediction; 60614034Sjavier.bueno@metempsy.com} 60714034Sjavier.bueno@metempsy.com 60814034Sjavier.bueno@metempsy.comvoid 60914034Sjavier.bueno@metempsy.comMultiperspectivePerceptron::update(ThreadID tid, Addr instPC, bool taken, 61014034Sjavier.bueno@metempsy.com void *bp_history, bool squashed, 61114034Sjavier.bueno@metempsy.com const StaticInstPtr & inst, 61214034Sjavier.bueno@metempsy.com Addr corrTarget) 61314034Sjavier.bueno@metempsy.com{ 61414034Sjavier.bueno@metempsy.com assert(bp_history); 61514034Sjavier.bueno@metempsy.com MPPBranchInfo *bi = static_cast<MPPBranchInfo*>(bp_history); 61614034Sjavier.bueno@metempsy.com assert(corrTarget != MaxAddr); 61714034Sjavier.bueno@metempsy.com if (squashed) { 61814034Sjavier.bueno@metempsy.com //delete bi; 61914034Sjavier.bueno@metempsy.com return; 62014034Sjavier.bueno@metempsy.com } 62114034Sjavier.bueno@metempsy.com 62214034Sjavier.bueno@metempsy.com if (bi->isUnconditional()) { 62314034Sjavier.bueno@metempsy.com delete bi; 62414034Sjavier.bueno@metempsy.com return; 62514034Sjavier.bueno@metempsy.com } 62614034Sjavier.bueno@metempsy.com 62714034Sjavier.bueno@metempsy.com bool do_train = true; 62814034Sjavier.bueno@metempsy.com 62914034Sjavier.bueno@metempsy.com if (!threadData[tid]->filterTable.empty()) { 63014034Sjavier.bueno@metempsy.com int findex = bi->getHashFilter(threadData[tid]->last_ghist_bit) % 63114034Sjavier.bueno@metempsy.com threadData[tid]->filterTable.size(); 63214034Sjavier.bueno@metempsy.com FilterEntry &f = threadData[tid]->filterTable[findex]; 63314034Sjavier.bueno@metempsy.com 63414034Sjavier.bueno@metempsy.com // compute this first, so we don't not train on the 63514034Sjavier.bueno@metempsy.com // first time a branch is seen. 63614034Sjavier.bueno@metempsy.com bool transition = false; 63714034Sjavier.bueno@metempsy.com if (f.alwaysNotTakenSoFar() || f.alwaysTakenSoFar()) { 63814034Sjavier.bueno@metempsy.com do_train = false; 63914034Sjavier.bueno@metempsy.com } 64014034Sjavier.bueno@metempsy.com if (taken) { 64114034Sjavier.bueno@metempsy.com if (f.alwaysNotTakenSoFar()) { 64214034Sjavier.bueno@metempsy.com transition = true; 64314034Sjavier.bueno@metempsy.com } 64414034Sjavier.bueno@metempsy.com f.seenTaken = true; 64514034Sjavier.bueno@metempsy.com } else { 64614034Sjavier.bueno@metempsy.com if (f.alwaysTakenSoFar()) { 64714034Sjavier.bueno@metempsy.com transition = true; 64814034Sjavier.bueno@metempsy.com } 64914034Sjavier.bueno@metempsy.com f.seenUntaken = true; 65014034Sjavier.bueno@metempsy.com } 65114034Sjavier.bueno@metempsy.com // is this the first time time the branch has gone both ways? 65214034Sjavier.bueno@metempsy.com if (transition) { 65314034Sjavier.bueno@metempsy.com threadData[tid]->occupancy += 1; 65414034Sjavier.bueno@metempsy.com } 65514034Sjavier.bueno@metempsy.com // for every new dynamic branch, when there ar 65614034Sjavier.bueno@metempsy.com // more than 'decay' number of branches in the 65714034Sjavier.bueno@metempsy.com // filter, blow a random filter entry away 65814034Sjavier.bueno@metempsy.com if (decay && transition && 65914034Sjavier.bueno@metempsy.com ((threadData[tid]->occupancy > decay) || (decay == 1))) { 66014081Sjavier.bueno@metempsy.com int rnd = random_mt.random<int>() % 66114081Sjavier.bueno@metempsy.com threadData[tid]->filterTable.size(); 66214034Sjavier.bueno@metempsy.com FilterEntry &frand = threadData[tid]->filterTable[rnd]; 66314034Sjavier.bueno@metempsy.com if (frand.seenTaken && frand.seenUntaken) { 66414034Sjavier.bueno@metempsy.com threadData[tid]->occupancy -= 1; 66514034Sjavier.bueno@metempsy.com } 66614034Sjavier.bueno@metempsy.com frand.seenTaken = false; 66714034Sjavier.bueno@metempsy.com frand.seenUntaken = false; 66814034Sjavier.bueno@metempsy.com } 66914034Sjavier.bueno@metempsy.com } 67014034Sjavier.bueno@metempsy.com 67114034Sjavier.bueno@metempsy.com if (do_train) { 67214034Sjavier.bueno@metempsy.com train(tid, *bi, taken); 67314034Sjavier.bueno@metempsy.com } 67414034Sjavier.bueno@metempsy.com 67514034Sjavier.bueno@metempsy.com#define RECORD_FILTERED_IMLI 1 67614034Sjavier.bueno@metempsy.com#define RECORD_FILTERED_GHIST 2 67714034Sjavier.bueno@metempsy.com#define RECORD_FILTERED_PATH 4 67814034Sjavier.bueno@metempsy.com#define RECORD_FILTERED_ACYCLIC 8 67914034Sjavier.bueno@metempsy.com#define RECORD_FILTERED_MOD 16 68014034Sjavier.bueno@metempsy.com#define RECORD_FILTERED_BLURRY 32 68114034Sjavier.bueno@metempsy.com// should never record a filtered local branch - duh! 68214034Sjavier.bueno@metempsy.com#define RECORD_FILTERED_LOCAL 64 68314034Sjavier.bueno@metempsy.com#define RECORD_FILTERED_RECENCY 128 68414034Sjavier.bueno@metempsy.com 68514034Sjavier.bueno@metempsy.com // four different styles of IMLI 68614034Sjavier.bueno@metempsy.com if (!bi->filtered || (record_mask & RECORD_FILTERED_IMLI)) { 68714034Sjavier.bueno@metempsy.com unsigned int target = corrTarget; 68814034Sjavier.bueno@metempsy.com if (target < bi->getPC()) { 68914034Sjavier.bueno@metempsy.com if (taken) { 69014034Sjavier.bueno@metempsy.com threadData[tid]->imli_counter[0] += 1; 69114034Sjavier.bueno@metempsy.com } else { 69214034Sjavier.bueno@metempsy.com threadData[tid]->imli_counter[0] = 0; 69314034Sjavier.bueno@metempsy.com } 69414034Sjavier.bueno@metempsy.com if (!taken) { 69514034Sjavier.bueno@metempsy.com threadData[tid]->imli_counter[1] += 1; 69614034Sjavier.bueno@metempsy.com } else { 69714034Sjavier.bueno@metempsy.com threadData[tid]->imli_counter[1] = 0; 69814034Sjavier.bueno@metempsy.com } 69914034Sjavier.bueno@metempsy.com } else { 70014034Sjavier.bueno@metempsy.com if (taken) { 70114034Sjavier.bueno@metempsy.com threadData[tid]->imli_counter[2] += 1; 70214034Sjavier.bueno@metempsy.com } else { 70314034Sjavier.bueno@metempsy.com threadData[tid]->imli_counter[2] = 0; 70414034Sjavier.bueno@metempsy.com } 70514034Sjavier.bueno@metempsy.com if (!taken) { 70614034Sjavier.bueno@metempsy.com threadData[tid]->imli_counter[3] += 1; 70714034Sjavier.bueno@metempsy.com } else { 70814034Sjavier.bueno@metempsy.com threadData[tid]->imli_counter[3] = 0; 70914034Sjavier.bueno@metempsy.com } 71014034Sjavier.bueno@metempsy.com } 71114034Sjavier.bueno@metempsy.com } 71214034Sjavier.bueno@metempsy.com 71314034Sjavier.bueno@metempsy.com bool hashed_taken = hash_taken ? (taken ^ !!(bi->getPC() & (1<<pcbit))) 71414034Sjavier.bueno@metempsy.com : taken; 71514034Sjavier.bueno@metempsy.com // record into ghist 71614034Sjavier.bueno@metempsy.com if (!bi->filtered || (record_mask & RECORD_FILTERED_GHIST)) { 71714034Sjavier.bueno@metempsy.com bool ab = hashed_taken; 71814034Sjavier.bueno@metempsy.com assert(threadData[tid]->ghist_words.size() > 0); 71914034Sjavier.bueno@metempsy.com for (int i = 0; i < ghist_length / blockSize + 1; i += 1) { 72014034Sjavier.bueno@metempsy.com unsigned int a = threadData[tid]->ghist_words[i]; 72114034Sjavier.bueno@metempsy.com bool ab_new = (a >> (blockSize - 1)) & 1; 72214034Sjavier.bueno@metempsy.com a <<= 1; 72314034Sjavier.bueno@metempsy.com a |= ab; 72414034Sjavier.bueno@metempsy.com ab = ab_new; 72514034Sjavier.bueno@metempsy.com a &= (1 << blockSize) - 1; 72614034Sjavier.bueno@metempsy.com threadData[tid]->ghist_words[i] = a; 72714034Sjavier.bueno@metempsy.com } 72814034Sjavier.bueno@metempsy.com } 72914034Sjavier.bueno@metempsy.com 73014034Sjavier.bueno@metempsy.com // record into path history 73114034Sjavier.bueno@metempsy.com if (!bi->filtered || (record_mask & RECORD_FILTERED_PATH)) { 73214034Sjavier.bueno@metempsy.com assert(threadData[tid]->path_history.size() > 0); 73314034Sjavier.bueno@metempsy.com memmove(&threadData[tid]->path_history[1], 73414034Sjavier.bueno@metempsy.com &threadData[tid]->path_history[0], 73514034Sjavier.bueno@metempsy.com sizeof(unsigned short int) * (path_length - 1)); 73614034Sjavier.bueno@metempsy.com threadData[tid]->path_history[0] = bi->getPC2(); 73714034Sjavier.bueno@metempsy.com } 73814034Sjavier.bueno@metempsy.com 73914034Sjavier.bueno@metempsy.com // record into acyclic history 74014034Sjavier.bueno@metempsy.com if (!bi->filtered || (record_mask & RECORD_FILTERED_ACYCLIC)) { 74114034Sjavier.bueno@metempsy.com threadData[tid]->updateAcyclic(hashed_taken, bi->getHPC()); 74214034Sjavier.bueno@metempsy.com } 74314034Sjavier.bueno@metempsy.com 74414034Sjavier.bueno@metempsy.com // record into modulo path history 74514034Sjavier.bueno@metempsy.com if (!bi->filtered || (record_mask & RECORD_FILTERED_MOD)) { 74614034Sjavier.bueno@metempsy.com for (int ii = 0; ii < modpath_indices.size(); ii += 1) { 74714034Sjavier.bueno@metempsy.com int i = modpath_indices[ii]; 74814034Sjavier.bueno@metempsy.com if (bi->getHPC() % (i + 2) == 0) { 74914034Sjavier.bueno@metempsy.com memmove(&threadData[tid]->modpath_histories[i][1], 75014034Sjavier.bueno@metempsy.com &threadData[tid]->modpath_histories[i][0], 75114034Sjavier.bueno@metempsy.com sizeof(unsigned short int) * (modpath_lengths[ii]-1)); 75214034Sjavier.bueno@metempsy.com threadData[tid]->modpath_histories[i][0] = bi->getPC2(); 75314034Sjavier.bueno@metempsy.com } 75414034Sjavier.bueno@metempsy.com } 75514034Sjavier.bueno@metempsy.com } 75614034Sjavier.bueno@metempsy.com 75714034Sjavier.bueno@metempsy.com // update blurry history 75814034Sjavier.bueno@metempsy.com if (!bi->filtered || (record_mask & RECORD_FILTERED_BLURRY)) { 75914034Sjavier.bueno@metempsy.com std::vector<std::vector<unsigned int>> &blurrypath_histories = 76014034Sjavier.bueno@metempsy.com threadData[tid]->blurrypath_histories; 76114034Sjavier.bueno@metempsy.com 76214034Sjavier.bueno@metempsy.com for (int i = 0; i < blurrypath_histories.size(); i += 1) 76314034Sjavier.bueno@metempsy.com { 76414034Sjavier.bueno@metempsy.com if (blurrypath_histories[i].size() > 0) { 76514034Sjavier.bueno@metempsy.com unsigned int z = bi->getPC() >> i; 76614034Sjavier.bueno@metempsy.com if (blurrypath_histories[i][0] != z) { 76714034Sjavier.bueno@metempsy.com memmove(&blurrypath_histories[i][1], 76814034Sjavier.bueno@metempsy.com &blurrypath_histories[i][0], 76914034Sjavier.bueno@metempsy.com sizeof(unsigned int) * 77014034Sjavier.bueno@metempsy.com (blurrypath_histories[i].size() - 1)); 77114034Sjavier.bueno@metempsy.com blurrypath_histories[i][0] = z; 77214034Sjavier.bueno@metempsy.com } 77314034Sjavier.bueno@metempsy.com } 77414034Sjavier.bueno@metempsy.com } 77514034Sjavier.bueno@metempsy.com } 77614034Sjavier.bueno@metempsy.com 77714034Sjavier.bueno@metempsy.com // record into modulo pattern history 77814034Sjavier.bueno@metempsy.com if (!bi->filtered || (record_mask & RECORD_FILTERED_MOD)) { 77914034Sjavier.bueno@metempsy.com for (int ii = 0; ii < modhist_indices.size(); ii += 1) { 78014034Sjavier.bueno@metempsy.com int i = modhist_indices[ii]; 78114034Sjavier.bueno@metempsy.com if (bi->getHPC() % (i + 2) == 0) { 78214034Sjavier.bueno@metempsy.com for (int j = modhist_lengths[ii] - 1; j > 0; j -= 1) { 78314034Sjavier.bueno@metempsy.com threadData[tid]->mod_histories[i][j] = 78414034Sjavier.bueno@metempsy.com threadData[tid]->mod_histories[i][j-1]; 78514034Sjavier.bueno@metempsy.com } 78614034Sjavier.bueno@metempsy.com threadData[tid]->mod_histories[i][0] = hashed_taken; 78714034Sjavier.bueno@metempsy.com } 78814034Sjavier.bueno@metempsy.com } 78914034Sjavier.bueno@metempsy.com } 79014034Sjavier.bueno@metempsy.com 79114034Sjavier.bueno@metempsy.com // insert this PC into the recency stack 79214034Sjavier.bueno@metempsy.com if (doing_recency) { 79314034Sjavier.bueno@metempsy.com if (!bi->filtered || (record_mask & RECORD_FILTERED_RECENCY)) { 79414034Sjavier.bueno@metempsy.com threadData[tid]->insertRecency(bi->getPC2(), assoc); 79514034Sjavier.bueno@metempsy.com } 79614034Sjavier.bueno@metempsy.com } 79714034Sjavier.bueno@metempsy.com 79814034Sjavier.bueno@metempsy.com // record into a local history 79914034Sjavier.bueno@metempsy.com if (!bi->filtered || (record_mask & RECORD_FILTERED_LOCAL)) { 80014034Sjavier.bueno@metempsy.com threadData[tid]->localHistories.update(bi->getPC(), hashed_taken); 80114034Sjavier.bueno@metempsy.com } 80214034Sjavier.bueno@metempsy.com 80314034Sjavier.bueno@metempsy.com // update last ghist bit, used to index filter 80414034Sjavier.bueno@metempsy.com threadData[tid]->last_ghist_bit = taken; 80514034Sjavier.bueno@metempsy.com 80614034Sjavier.bueno@metempsy.com delete bi; 80714034Sjavier.bueno@metempsy.com} 80814034Sjavier.bueno@metempsy.com 80914034Sjavier.bueno@metempsy.comvoid 81014034Sjavier.bueno@metempsy.comMultiperspectivePerceptron::btbUpdate(ThreadID tid, Addr branch_pc, 81114034Sjavier.bueno@metempsy.com void* &bp_history) 81214034Sjavier.bueno@metempsy.com{ 81314034Sjavier.bueno@metempsy.com} 81414034Sjavier.bueno@metempsy.com 81514034Sjavier.bueno@metempsy.comvoid 81614034Sjavier.bueno@metempsy.comMultiperspectivePerceptron::squash(ThreadID tid, void *bp_history) 81714034Sjavier.bueno@metempsy.com{ 81814034Sjavier.bueno@metempsy.com assert(bp_history); 81914034Sjavier.bueno@metempsy.com MPPBranchInfo *bi = static_cast<MPPBranchInfo*>(bp_history); 82014034Sjavier.bueno@metempsy.com delete bi; 82114034Sjavier.bueno@metempsy.com} 822