SnipersimのPentium M分岐予測器の実装を読む (1. 分岐予測器の構成)

github.com

Pentium M プロセッサの分岐予測器アーキテクチャを模した実装を解析していく。この分岐予測器は、複数の予測器を組み合わせたハイブリッド型の設計となっている。

1. クラスの構成要素

class PentiumMBranchPredictor : public BranchPredictor {
public:
   PentiumMBranchPredictor(String name, core_id_t core_id);
   ~PentiumMBranchPredictor();

   bool predict(bool indirect, IntPtr ip, IntPtr target);
   void update(bool predicted, bool actual, bool indirect, IntPtr ip, IntPtr target);

private:
   void update_pir(...);
   IntPtr hash_function(IntPtr ip, IntPtr pir);

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

   IntPtr m_pir;                       // Path Information Register（PIR）
   bool   m_last_gp_hit;              // 直前の global predictor の命中フラグ
   bool   m_last_bm_pred;             // 直前の bimodal 予測結果
   bool   m_last_lpb_hit;             // 直前の loop predictor 命中フラグ

   std::unordered_map<IntPtr,uint64_t> m_incorrect_per_ip;
};

主要なコンポーネントは以下の通りである：

• m_global_predictor: 長い履歴を使う Global History ベースの予測器
• m_btb: Branch Target Buffer、分岐先アドレスのキャッシュ
• m_bimodal_table: シンプルな 2 ビットカウンタを持つ Bimodal 予測器
• m_lpb: ループ分岐向けの Loop Branch Predictor
• ibtb: 間接分岐（indirect branch）向けのターゲットバッファ
• m_pir: 分岐のパターンを収集する小さなシフトレジスタ (Path Information Register)
• m_incorrect_per_ip: IP（命令アドレス）ごとのミス予測回数カウント

デストラクタでは、m_incorrect_per_ip の内容を CSV (branch_mispredicts.csv) に書き出しており、IP ごとのミス予測ホットスポット分析に使用できる。

2. 予測フェーズ (predict メソッド)

   BranchPredictorReturnValue global_pred_out = m_global_predictor.lookup(ip, target, m_pir);
   BranchPredictorReturnValue btb_out = m_btb.lookup(ip, target);
   BranchPredictorReturnValue lpb_out = m_lpb.lookup(ip, target);
   
   bool bimodal_out = m_bimodal_table.predict(indirect, ip, target);

   m_last_gp_hit = global_pred_out.hit;
   m_last_bm_pred = bimodal_out;
   m_last_lpb_hit = lpb_out.hit & btb_out.hit;

   // Outcome prediction logic
   bool result;// = ibtb.predict(ip,target);
   if (global_pred_out.hit )
   {
      result = global_pred_out.prediction;
   }
   else if (lpb_out.hit & btb_out.hit)
   {
      result = lpb_out.prediction;
   }
   else
   {
      result = bimodal_out;
   }
   if (result == true)
   {
      result = ibtb.predict(indirect,ip,target);
   }
   // TODO FIXME: Failed matches against the target address should force a branch or fetch miss

   return result;

m_global_predictorは、PentiumMGlobalPredictorクラスのインスタンスであり、その実体はGlobalPredictorクラスを継承・拡張したものとなっている。

   BranchPredictorReturnValue lookup(IntPtr ip, IntPtr target, IntPtr pir)
   {

      UInt32 index, tag;
      BranchPredictorReturnValue ret = { 0, 0, 0, BranchPredictorReturnValue::InvalidBranch };

      gen_index_tag(ip, pir, index, tag);

      for (unsigned int w = 0 ; w < m_num_ways ; ++w )
      {
         if (m_ways[w].m_valid[index] && m_ways[w].m_tags[index] == tag)
         {
            ret.hit = 1;
            ret.prediction = m_ways[w].m_predictors[index].predict();
            break;
         }
      }

      return ret;
   }

   // 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;
   }

予測の優先順位は以下のようだ：

1. Global Predictor が命中した場合はその予測を使用
2. ループ予測＆BTB がヒットした場合はループ予測を使用
3. それ以外は Bimodal 予測を使用
4. "taken" と予測した場合は、間接分岐なら ibtb.predict(...) で最終判断