Champsim の Hashed Perceptronの実装を読む (3. 予測の実行)

github.com

この辺の実装がどのようになっているのかを勉強したい。ChatGPTにお願いしながら、読み進めていくことにする。

msyksphinz.hatenablog.com

---

予測の実行

bool hashed_perceptron::predict_branch(champsim::address pc)
{
    auto get_index = [pc_slice = pc.slice_lower<TABLE_INDEX_BITS>().to<uint64_t>()](const auto &hist)
    {
        return hist.value() ^ pc_slice; // seed in the PC to spread accesses around (like gshare) XOR in the last word
    };
    perceptron_result result;
    std::transform(std::cbegin(ghist_words), std::cend(ghist_words), std::begin(result.indices), get_index);

    // add the selected weights to the perceptron sum
    result.yout = std::inner_product(std::begin(tables), std::end(tables), std::begin(result.indices), 0, std::plus<>{},
                                     [](const auto &table, const auto &index)
                                     { return table.at(index).value(); });
    last_result = result;
    return result.yout >= THRESHOLD;
}

1. 全体の流れ

1. PC(プログラムカウンタ)の下位ビットを取り出し、後述する「履歴ビット(hist)」とXORしてインデックスを生成するラムダ関数を作成する。
2. グローバル履歴を要素とする配列(ghist_words)に対して、そのラムダを適用し、各要素ごとに「テーブル参照用のインデックス」を計算する。
3. そのインデックスを使用して、各テーブルの重み(weight)を取り出して合計(内積)を計算する。
4. 合計値youtが閾値(THRESHOLD)以上ならtrue、未満ならfalseを返す。

Hashed Perceptronでは、この一連の処理によって「PCとグローバル履歴の組み合わせをハッシュし、複数の小さなテーブルから重みを引き出して合算」し、最終的に分岐(taken / not taken)を予測する。

2. PCの下位ビット抽出

pc.slice_lower<TABLE_INDEX_BITS>().to<uint64_t>()

• pcは分岐命令のアドレス(champsim::address型)である。
• slice_lower<TABLE_INDEX_BITS>()は、そのアドレスの下位ビット(ここではTABLE_INDEX_BITSビット分)を抽出する操作である。
• 例えばTABLE_INDEX_BITS = 10ならアドレスの下位10ビットを取り出し、それを整数化してuint64_tに変換している。
• 返り値をラムダキャプチャでpc_sliceという名前に束縛しており、以降「この分岐命令固有のシード値」として使用する。

3. ラムダ関数 get_index

auto get_index = [pc_slice = pc.slice_lower<TABLE_INDEX_BITS>().to<uint64_t>()](const auto &hist)
{
    return hist.value() ^ pc_slice;
};

目的：各「履歴ワード(hist)」とPCの下位ビットpc_sliceをXORし、最終的にテーブル参照用のインデックスを得る。

• histは「グローバル履歴を数ビットずつ区切ったもの」(ghist_words)の各要素である。hist.value()で、たとえば8–16ビット程度の履歴の断片を取り出している。
• XORを行う理由は以下の通りである：
  1. PCの下位ビットを混ぜ込むことで、同じ履歴パターンでも分岐先が違えばテーブル上の違う箇所を参照する(いわゆるgshareの考え方)
  2. 複数のテーブルを使用する際に、アクセスパターンを分散させ、コンフリクト(衝突)を減らす
• 結果として返される値が「テーブル内のインデックス」となる。テーブルのサイズは通常、2^TABLE_INDEX_BITSなどで設定しているケースが多い。

4. std::transformによるインデックス計算

std::transform(
    std::cbegin(ghist_words),
    std::cend(ghist_words),
    std::begin(result.indices),
    get_index
);

• ghist_words：グローバル履歴を分割したワードの配列である。例えば、グローバル履歴が64ビットなら8ビットずつ8個に分けた配列というイメージである。
• result.indices：perceptron_result型のメンバーで、「各テーブルを参照するためのインデックスを格納する配列」である。テーブルの数だけ要素を持っている。
• std::transformは以下の動作を行う：
  1. 第一引数／第二引数で指定した範囲(ここではghist_words全要素)を
  2. 第三引数のイテレータ先(result.indicesの先頭)に対して
  3. 第四引数のラムダ(get_index)を適用して、その返り値を次々に格納していく。

つまり、ghist_words[i]に対してget_index(ghist_words[i])を計算し、その結果をresult.indices[i]に格納する、という流れである。