Sniperを使った各種分岐予測器の動作確認 (3. 分岐予測器のモデルを調査)

サイクル精度シミュレータを使って、各種分岐予測の実装でCoremarkの性能がどのように変化するかちょっと興味があって計ってみることにした。

サイクル精度シミュレータとしてはSniperを使用する。Sniperにはフロントエンドの分岐予測器の実装があって、これをコンフィグレーションで変更することができる。

PentiumMモデルは、以下の要素から構成されている。

• sniper/common/performance_model/branch_predictors/pentium_m_branch_predictor.h

   PentiumMGlobalPredictor m_global_predictor;
   PentiumMBranchTargetBuffer m_btb;
   PentiumMBimodalTable m_bimodal_table;
   PentiumMLoopBranchPredictor m_lpb;
   PentiumMIndirectBranchTargetBuffer ibtb;

PentiumMGlobalPredictor

これはグローバル分岐履歴だと思う。

• sniper/common/performance_model/branch_predictors/pentium_m_global_predictor.h

public:

   // The Pentium M Global Branch Predictor
   // 512-entries
   // 6 tag bits per entry
   // 4-way set associative
   PentiumMGlobalPredictor()
      : GlobalPredictor(2048, 6, 4)
   {}

};

このGlobalPredictorが何をしているのか見てみよう。

• sniper/common/performance_model/branch_predictors/global_predictor.h

class GlobalPredictor : BranchPredictor
{
/* ... 途中省略 ... */
   bool predict(bool indirect, IntPtr ip, IntPtr target, IntPtr pir)
   {
      UInt32 index, tag;

      gen_index_tag(ip, pir, index, tag);

この、 gen_index_tag() がグローバル分岐予測のインデックスを作っているのだと思うのだけれども... pir は分岐ヒストリだと思う。

• sniper/common/performance_model/branch_predictors/global_predictor.h

   // Pentium M-specific indexing and tag values
   void gen_index_tag(IntPtr ip, IntPtr pir, UInt32& index, UInt32 &tag)
   {
      index = ((ip >> 4) ^ (pir >> 6)) & 0x1FF;
      tag = ((ip >> 13) ^ pir) & 0x3F;
   }

• sniper/common/performance_model/branch_predictors/pentium_m_branch_predictor.cc

void PentiumMBranchPredictor::update_pir(bool actual, IntPtr ip, IntPtr target, BranchPredictorReturnValue::BranchType branch_type)
{
   IntPtr rhs;

   if ((branch_type == BranchPredictorReturnValue::ConditionalBranch) & actual)
   {
      rhs = ip >> 4;
   }
   else if (branch_type == BranchPredictorReturnValue::IndirectBranch)
   {
      rhs = (ip >> 4) | target;
   }
   else
   {
      // No PIR update
      return;
   }

   m_pir = ((m_pir << 2) ^ rhs) & 0x7fff;
}

BranchPredictorReturnValue::ConditionalBranch で、分岐が成立するならばPCを4ビットシフトする(これは下位の4ビットが同一キャッシュライン内だという仮定？)。これを2ビットシフトしたPIRに対してXORするという形で、ハッシュ関数を作っている。いうなれば、以下のような感じだと思う。これは単純な分岐の履歴ではないのか？

{pir, 2'b00} ^ ip[19: 4]

PIRというのは、いろいろ調べるとPath Based Indirect predictor Registerのことらしい。これまでに実行されたパス（つまりIP）をベースにしてハッシュ関数を作り、予測のためのインデックスを作るということなのか。