分岐予測の評価キット Branch Prediction Championship Kit を試す (4. Local Bimodal Branch Predictionを試す)

Branch Prediction Championship Simulatorの続きを試す。

Local Bimodal Branch Predictorを作ってみる

以下のようにPREDICTORを構成する。メンバ変数としてm_local(本当は2ビット)を4096個構成して、Local分岐予測として使用する。

#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <inttypes.h>
#include <math.h>

#include "utils.h"
#include <vector>

class PREDICTOR {

  const static int LOCAL_LEN = 4096;

  int8_t m_local[LOCAL_LEN];

  static UINT32 get_index(UINT64 PC) {
    return (PC >> 2) % LOCAL_LEN;
  }

public:

  PREDICTOR(void);
  bool    GetPrediction(UINT64 PC);
  void    UpdatePredictor(UINT64 PC, OpType OPTYPE,bool resolveDir, bool predDir, UINT64 branchTarget);
  void    TrackOtherInst(UINT64 PC, OpType opType, bool taken, UINT64 branchTarget);
};

#include "predictor_bimodal.h"

PREDICTOR::PREDICTOR (void)
{
  for (auto i = 0; i < LOCAL_LEN; i++) {
    m_local[i] = 2;   // weakly taken
  }
}

bool
PREDICTOR::GetPrediction (UINT64 PC)
{
  UINT32 index = get_index(PC);
  return m_local[index] >> 1;
}

void
PREDICTOR::UpdatePredictor (UINT64 PC, OpType OPTYPE, bool resolveDir,
                            bool predDir, UINT64 branchTarget)
{
  UINT32 index = get_index(PC);
  m_local[index] += (resolveDir ? 1 : -1);
  if (m_local[index] > 3) {
    m_local[index] = 3;
  } else if (m_local[index] < 0) {
    m_local[index] = 0;
  }
}

void
PREDICTOR::TrackOtherInst (UINT64 PC, OpType opType, bool taken,
                           UINT64 branchTarget)
{
}

基本的にHit/Missというか、分岐の結果に基づいてBimodal Branch Prediction Counterをアップデートする。

結果的に、以下のような結果となった。Staticよりも多少は良くなった。

   MPKBr_1K           :   187.0000
   MPKBr_10K              :    58.9000
   MPKBr_100K             :    52.5100
   MPKBr_1M           :    50.1210
   MPKBr_10M              :    50.0412
   MPKBr_30M              :    50.0323
   TRACE      : ../traces/SHORT_MOBILE-24.bt9.trace.gz
   NUM_INSTRUCTIONS               : 1000000000
   NUM_BR                         :   38684342
   NUM_UNCOND_BR                  :    2221649
   NUM_CONDITIONAL_BR             :   36462693
   NUM_MISPREDICTIONS             :    1935186
   MISPRED_PER_1K_INST            :     1.9352