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