ISSに分岐予測を実装する検討(2. 分岐予測の機構をISSに実装する)

前回で、分岐予測機構について簡単にまとめたので、今度は分岐予測をISSに実装しよう。

分岐予測の機構を実装する

まずは、必要なSRAMをモデル化する。

github.com

  /*
   * Branch Predictor implementation
   */
  const int32_t BRANCH_LOCAL_BIT     = 3;
  const int32_t BRANCH_ADDR_MASK_LEN = 10;
  const int32_t BRANCH_LOCAL_LENGTH  = 1 << BRANCH_ADDR_MASK_LEN;
  const int32_t BRANCH_STATUS_LENGTH = BRANCH_LOCAL_LENGTH * (1 << BRANCH_LOCAL_BIT);
  std::unique_ptr<uint8_t []> m_branch_his_table;
  std::unique_ptr<BranchPredStatus []> m_branch_status_table;

m_branch_his_tableは分岐履歴テーブル、m_branch_status_tableは分岐予測テーブルだ。分岐予測履歴テーブルのデータ型は、前回説明した分岐予測のステートマシンをそのままenumに変更した。

enum class BranchPredStatus {
  NotTakenStrong = 0,
  NotTakenWeak   = 1,
  TakenWeak      = 2,
  TakenStrong    = 3
};

分岐予測エントリテーブルの参照インデックスを生成する

分岐予測エントリテーブルの参照テーブルは、前回の説明図をそのままモデル化すると以下のようなプログラムで実現できる。

  Addr_t PredTableIndex (Addr_t addr) {
    return (addr >> 2) & ((1 << BRANCH_ADDR_MASK_LEN)-1);
  }
  Addr_t PredStatusTableIndex (Addr_t addr) {
    Addr_t his_table_idx = PredTableIndex (addr);
    uint8_t his_bit = m_branch_his_table[his_table_idx];

    return (his_table_idx << BRANCH_LOCAL_BIT) | his_bit & ((1 << BRANCH_LOCAL_BIT)-1);
  }

PredStatusTableIndex()はアドレスから参照すべき分岐予測テーブルのインデックスを生成する。 これを元に分岐予測を行い、実際の分岐予測結果から分岐予測テーブルのインデックスをアップデートする。

• 分岐予測を行う IsBranchTaken()

bool RiscvEnv::IsBranchTaken (Addr_t addr)
{
  if (FLAGS_sim_pred) {
    Addr_t status_table_idx = PredStatusTableIndex (addr);
    BranchPredStatus status_bit = m_branch_status_table[status_table_idx];

    DebugPrint ("[BR:%04d:", status_table_idx);

    switch (status_bit) {
      case BranchPredStatus::TakenWeak:      DebugPrint ("TW");  break;
      case BranchPredStatus::TakenStrong:    DebugPrint ("TS");  break;
      case BranchPredStatus::NotTakenWeak:   DebugPrint ("NTW"); break;
      case BranchPredStatus::NotTakenStrong: DebugPrint ("NTS"); break;
    }

    DebugPrint ("]\n");

    if ((status_bit == BranchPredStatus::TakenWeak) || (status_bit == BranchPredStatus::TakenStrong)) {
      return true;
    } else {
      return false;
    }
  }
}

• 分岐結果を元にテーブルをアップデートする UpdateBranchPrediction()

void RiscvEnv::UpdateBranchPrediction (Addr_t addr, bool is_taken)
{
  if (FLAGS_sim_pred) {
    Addr_t status_table_idx = PredStatusTableIndex (addr);
    BranchPredStatus status_bit = m_branch_status_table[status_table_idx];

    switch (status_bit) {
      case BranchPredStatus::NotTakenWeak :
        if (is_taken) { status_bit = BranchPredStatus::NotTakenStrong; }
        else          { status_bit = BranchPredStatus::NotTakenWeak;   }
        break;
      case BranchPredStatus::NotTakenStrong :
        if (is_taken) { status_bit = BranchPredStatus::TakenWeak;      }
        else          { status_bit = BranchPredStatus::NotTakenStrong; }
        break;
      case BranchPredStatus::TakenWeak :
        if (is_taken) { status_bit = BranchPredStatus::TakenStrong;    }
        else          { status_bit = BranchPredStatus::NotTakenWeak;   }
        break;
      case BranchPredStatus::TakenStrong :
        if (is_taken) { status_bit = BranchPredStatus::TakenStrong;    }
        else          { status_bit = BranchPredStatus::TakenWeak;      }
        break;
      default:
        break;
    }
    m_branch_status_table[status_table_idx] = status_bit;
  }

  return;
}

これを、各分岐命令の実装に追加していく。

void InstEnv::RISCV_INST_BGE (Word_t inst_hex)
{
  RegAddr_t rs1_addr = ExtractR1Field (inst_hex);
  RegAddr_t rs2_addr = ExtractR2Field (inst_hex);

  DWord_t rs1_val  = m_env->GRegRead<DWord_t> (rs1_addr);
  DWord_t rs2_val  = m_env->GRegRead<DWord_t> (rs2_addr);
  DWord_t imm    = ExtractSBField (inst_hex);

  Addr_t current_pc = m_env->GetPC();
  m_env->IsBranchTaken (current_pc);

  bool taken = (rs1_val >= rs2_val);
  if (taken) {
    DWord_t res_pc = current_pc + imm;
    m_env->SetPC (res_pc);
    m_env->SetJumped (true);
  }

  m_env->UpdateBranchPrediction (current_pc, taken);

これにより、シミュレータのログに以下のようなログが生成されるようになる。

[BR:3504:NTS]
        87:M:MBar:[000026d8][P000026d8] 04a7e263 : bltu       r15,r10,0x02         r15=>00000005 r10=>00000003

上記の例は、分岐命令により分岐予測テーブルのインデックス3504番が参照され、Not Taken Stronglyを予測された結果だ。

これで、分岐予測機構のモデル化は完了した。今度はこれをRTLに実装していくことになる。