make_index_sequenceを短く書いた（C++11用）

std::make_index_sequence<N>は、std::index_sequence<0, 1, 2, ..., N-1>に展開される、メタプログラミングを行う場合や最適化に便利なエイリアステンプレートです。 しかし、以下の問題点があります。

  • C++14で追加されたため、C++11環境では使えない*1
  • 多くの場合、コンパイル時空間計算量*2がΩ(N2)となるような実装が行われている

C++の新しい機能を使えば簡単に実装できます。 しかし、自分で実装するのは、C++11環境で使いたいため自分で実装する必要がある、という状況でしょう。 したがって、C++の新しい機能を使わない、かつ簡潔な実装が必要とされます。

コンパイル時空間計算量がΩ(N2)となる、非常に簡潔な実装

#include <cstddef>

template<std::size_t...> struct index_sequence {};

template<std::size_t I, std::size_t... Is> struct S : S<I-1, I-1, Is...> {};
template<std::size_t... Is> struct S<0, Is...> { index_sequence<Is...> f(); };

template<std::size_t N> using make_index_sequence = decltype(S<N>{}.f());

make_index_sequenceは、たったこれだけで定義可能です。

このコードを作るにあたって考慮した点は、以下のような感じです。

  • using type = typename S<N>::type;などとやってしまうと長くなるため、関数とdecltypeを使う
  • ただし、テンプレートの再帰の終端ケースであるかの分岐が必要であるため、必ず構造体を作る必要がある*3
  • 継承を使うと構造体テンプレートの末尾再帰を簡潔に書ける

コンパイル時空間計算量がΩ(N)となる、工夫した実装

#include <cstddef>

template<std::size_t...> struct index_sequence {};

template<std::size_t N, bool> struct S { template<std::size_t... Is> index_sequence<Is..., (Is+N)...> f(index_sequence<Is...>); };
template<std::size_t N> struct S<N, true> { template<std::size_t... Is> index_sequence<Is..., (Is+N)..., N*2> f(index_sequence<Is...>); };

template<std::size_t N> struct Q { decltype(S<N/2, N%2>{}.f(Q<N/2>{}.g())) g(); };
template<> struct Q<0> { index_sequence<> g(); };

template<std::size_t N> using make_index_sequence = decltype(Q<N>{}.g());

再帰深度を対数回に抑えたバージョンです。

この形式の場合、普通は末尾再帰になりません*4。 そのため継承を使った方法は使えませんが、Nの偶奇によって分岐が発生するため、構造体にする必要はあります。 テンプレートを分解する場合は関数引数が最も簡単です。 よってこのような形になりました。

*1:C++11未満の環境では、可変テンプレートが使えないので利用価値が低いです。

*2:空間計算量は、時間計算量の下限を与えます。

*3:std::enable_ifは構造体です。constexpr ifはC++17以降です。

*4:アキュムレータ変数を追加すれば末尾再帰にすること自体は可能ですが、記述が長くなります

リングバッファを作るときstd::dequeを使うのはちょっと楽でちょっと損

容量に上限があるキューを実現するためには、リングバッファを用いるのが最も効率的です。

しかし、ポインタの操作を含むコードを自分で書くのは間違いのもとです。効率を最優先する場合以外は、ライブラリを使うほうが良いです。

C++の場合、std::deque*1を使うと以下の意味でそれほど効率が落ちることはありません。

  • 挿入のたびにメモリ確保が走ることはない（std::listのような連結リストではこの要件を満たせない）
  • 挿入または削除のたびに要素の移動が発生することはない（std::vectorには効率の良いpop_frontが存在せず、erase(vec.begin())などとするとこの要件を満たせない）

正しく実装されたリングバッファと比べて、劣る点は以下の点です。

  • かなり多くのメモリを要求する（libstdc++の実装では、少なくとも8192バイト*2必要です）
  • TLBをたくさん占有する（非常に小さいリングバッファであれば一つのページ内に収まります。一方、std::dequeで作った場合、デフォルトのアロケータはページ境界を無視して4096バイト取るため、四つのページを使用することが多いです）
  • キャッシュヒットしにくい（大きな領域を事実上使い捨てていくことになるためです）

*1:std::queueとしないほうが、デバッグの時に中身を出力できて楽です。

*2:https://ja.cppreference.com/w/cpp/container/deque によれば一つのチャンクが4096バイトで、リングバッファを運用するためには二チャンク必要なためです。実際計測してみるとそうなっています。

gshare分岐予測器について、の補足

gshare分岐予測器について - よーるの補足です。

分岐命令の上位アドレスとグローバル分岐履歴をxor、について

吉瀬 謙二, 片桐 孝洋, 本多 弘樹, 弓場 敏嗣:「高性能プロセッサのための代表的な分岐予測器の実装と評価」Technical Report UEC-IS-2003-2, Version 2003-05-0

http://www.arch.cs.titech.ac.jp/~kise/SimAlpha/doc/uec-is-2003-02.pdf

という論文に書いてありました。

直近の分岐履歴を分岐命令の上位アドレスとxor、について

直近の分岐履歴を分岐命令の下位アドレスとxorする場合、以下のようなパターンでインデックスが衝突してしまう可能性があります。 従って、直近の分岐履歴を分岐命令の下位アドレスとxorする場合、理想的なハッシュ関数を使った場合と比べて衝突が増えます。

  • PCαは、分岐方向履歴とは無関係に、予測不可能な分岐をする。
  • PCαがtakenだった場合、いくつかの当てられる分岐が来た後、PCβが予測の難しい（しかし分岐方向履歴を見れば当てられる）分岐である。
  • PCαがnot-takenだった場合、いくつかの当てられる分岐が来た後、PCγが予測の難しい（しかし分岐方向履歴を見れば当てられる）分岐である。
  • PCβとPCγは同じ関数内の近い位置にあり、その上位アドレスは一致している。

直近の分岐履歴を分岐命令の上位アドレスとxorする場合、このようなプログラムの構造（taken側とnot-taken側のPCのビット表現が似ていることが多い）が原因で生じる理想的なハッシュ関数とのずれは、かなり低く抑えられます。

cbp5の分岐トレースが440個、について

443個ありうち3個壊れています、と書きましたが、どうやら壊れているのではなくあまりにも予測が簡単すぎてmisp. /KIが0.0000になっているようです。 集計用スクリプトの書き方が甘く、misp. /KIが0.0000のものはエラー落ちしたものとみなしているのが原因だったようです。

グローバル分岐履歴長を22より大きくするのは性能を低下させる、について

グローバル分岐履歴長22というのは具体的に意味のある数字ではなく、どのようなトレースを選ぶかに大きく依存します。 cbp5の分岐トレースの中には、23回周期のループを回っているだけのようなトレース（SHORT_MOBILE-53、上で壊れていると勘違いしたトレース）が存在します。 これはグローバル分岐履歴長を22以上にすると完璧に当てることができるようになるため、少し無理してでもグローバル分岐履歴長22を確保したほうがよいという結論が得られています。

無限に容量がある場合でもgshare分岐予測器で取り扱うことのできるグローバル分岐履歴長はそれほど大きくできないということは、一般論として事実です。

分岐履歴を折りたたむことでより長い分岐履歴を使ったほうが良いか、について

エントリ数2Mi（512KiB、インデックスは21bit）の時、グローバル分岐履歴長22を使うほうがやや性能が高くなりました。 同様の現象は、この事例以外には見つかりませんでした。

gshare分岐予測器について

gshare分岐予測器というのは、単純な構造の分岐予測器の中では最も性能が良い分岐予測器であり、1993年に発表されました。

このgshare分岐予測器について、あまり教科書に書いていないことを調べたので、まとめておきます。

この記事には、以下のものが含まれます。

  • gshareの適切なインデックスの作り方
  • 容量ごとに最適なグローバル分岐履歴とその理由

以下では、分岐予測器の簡単な仕組みおよびbimodal分岐予測器（per Address 2-bit saturating counter scheme）についての知識を前提とします。

gshare分岐予測器とは

bimodal分岐予測器は、単にその分岐命令の分岐方向の偏りだけを頼りに分岐方向を予測します。 分岐命令のアドレス（の下位Nビット）をインデックスとし、パターンヒストリーテーブル(PHT)という飽和二ビットカウンターの配列にアクセスすることで、予測を行います。

それに対しgshare分岐予測器は、グローバル分岐履歴（直近いくつかの条件分岐命令の分岐方向の系列）を利用し、他の分岐命令の分岐方向との相関をもとらえることで予測精度を向上させる手法です。 分岐命令のアドレス（の下位Nビット）とグローバル分岐履歴をxorしたものをインデックスとし、PHTにアクセスすることで予測を行います。 xorした場合情報が失われてしまいますが、使われていないPHTエントリを有効活用できるようになります。

ちなみに、分岐命令のアドレス（の下位Nビット）とグローバル分岐履歴を連結したものをインデックスとする分岐予測器はgselect分岐予測器と呼ばれますが、利用されるPHTエントリに偏りが生じるため、gshare分岐予測器のほうが性能が良いとされています。

正しいインデックスの作り方

分岐命令のアドレス（の下位Nビット）とグローバル分岐履歴をxorするという手法は有名ですが、具体的にどのようにxorするのかについて、詳細に書かれた教科書を見たことがありません。

実は、ここでのxorの仕方は結構重要です。複数の異なる分岐命令＆グローバル分岐履歴が同じインデックスになってしまう（エイリアスが起こる）場合、破壊的な学習が行われ、予測精度が低下してしまいます。

理想的なハッシュ関数を使えばエイリアス頻度を最小限に抑えることができます。しかし、xorするだけという単純なハッシュ関数を用いて理想的なエイリアス頻度を達成するには、少し工夫が必要です。

【間違い】分岐命令の下位アドレスとグローバル分岐履歴をxor

PC9 PC8 PC7 PC6 PC5 PC4 PC3 PC2 PC1 PC0
ghist3 ghist2 ghist1 ghist0

このようにしてしまうと、頻繁にエイリアスが発生してしまいます。なぜなら、プログラムの多く実行される部分は狭い範囲に集中していることが多く、そこに含まれる分岐命令のPCの上位ビットは似ていることが多いからです。

【正解】分岐命令の上位アドレスとグローバル分岐履歴をxor

PC9 PC8 PC7 PC6 PC5 PC4 PC3 PC2 PC1 PC0
ghist3 ghist2 ghist1 ghist0

このようにすることで、近くに存在する分岐命令との狭い範囲にある分岐命令がお互いにエイリアスの関係になってしまう事態が避けられます。 当然遠い位置にある特定の分岐命令との間でエイリアスが起こる可能性は残されるのですが、理想的なハッシュ関数と比べそのような事態が発生する頻度が高いということはないはずです。

【最良】直近の分岐履歴を分岐命令の上位アドレスとxor

PC9 PC8 PC7 PC6 PC5 PC4 PC3 PC2 PC1 PC0
ghist0 ghist1 ghist2 ghist3 ghist4 ghist5 ghist6

もし使用するグローバル分岐履歴長が長めである場合、順番を逆にし、直前の分岐履歴がPCの最上位ビットとxorされるようにするほうがやや良い性能を示すようです。 一般に、直近の分岐履歴のほうが需要であることが原因であると思われます。

PHTの容量と分岐履歴長毎の予測性能

一般に、bimodal分岐予測器もgshare分岐予測器も、PHTの容量を増やせば増やすほど予測性能が向上します。もちろん、エイリアスが十分発生しなくなる容量まで増やすと、性能向上は頭打ちとなります。

gshare分岐予測器では、グローバル分岐履歴長を伸ばせば伸ばすほど遠い分岐命令との相関もとらえられるようになります。しかし、それに伴い以下の二種類の問題が発生するため、グローバル分岐履歴長を伸ばせば伸ばすほど予測性能が上がるわけではありません。

  • 学習するべきパターンが増加し、エイリアスの可能性が増加する（グローバル分岐履歴長3であれば、一つの分岐アドレスにつき最大で8パターン覚える必要がある*1）
  • 遠い過去の分岐履歴との相関がない分岐について、初見のパターンである割合が増加する（bimodal分岐予測器なら前に見たことのある分岐命令アドレスで当てられたのに、というケース）

実測

分岐予測器の世界的な大会である、cbp5のルールに従って、各手法の分岐予測ミス率を測りました。cbp5では、分岐命令の系列（トレース）が440個*2公開されており、付属のシミュレータを使うと千命令当たりの予測ミス回数（misp./KI）が出力されます。440個のトレースについて、その平均をとることで、いろいろな分岐パターンを当てることができるかを評価します。

440回もシミュレータを動かす必要があるため、データを取るには10時間以上かかります。

f:id:lpha_z:20200308222444p:plainf:id:lpha_z:20200308222535p:plain
図1 PHT容量ごとの分岐予測ミス率（cbp5トレースにおける千命令あたりの分岐予測ミス数）

図1は、PHTのエントリ数を変更したときの、各分岐予測器（bimodal, gshareでグローバル分岐履歴長が1, 2, 4, 8, 12, 16, 22, 28のもの）の予測ミス率を表しています*3。

測定の結果わかったことは、

  • PHTエントリ数が256未満なら、gshareを使わずにbimodalを使ったほうが良い
  • PHTエントリ数が256～64 Kiくらいの時、容量を二倍にするごとにグローバル分岐履歴長を2増やすくらいがよい。グローバル分岐履歴長を伸ばしすぎるとかえって性能が低下する
  • PHTエントリ数が64 Ki～4 Miくらいの時、PHTのインデックスのビット数と同じだけのグローバル分岐履歴長が良い*4
  • PHTエントリ数が4 Mi以上ある場合でも、グローバル分岐履歴長を22より大きくするのは性能を低下させる

なぜそうなるのか

PHTエントリ数が256未満なら、gshareを使わずにbimodalを使ったほうが良い

PHTエントリ数が非常に小さいため、エイリアスの可能性が非常に高く、容量性ミスが発生しています。したがって、学習するべきパターン数を抑えることが重要です。

PHTエントリ数が256～64 Kiくらいの時、容量を二倍にするごとにグローバル分岐履歴長を2増やすくらいがよい。グローバル分岐履歴長を伸ばしすぎるとかえって性能が低下する

PHTエントリ数は標準的な数ですが、エイリアスの可能性がそれなりにあり、競合性ミスが発生しています。したがって、破壊的な競合の発生確率を下げるためにグローバル分岐履歴長をほどほどに抑えることが重要です*5

PHTエントリ数が64 Ki～4 Miくらいの時、PHTのインデックスのビット数と同じだけのグローバル分岐履歴長が良い

PHTエントリ数は非現実的な数になってきており、十分なエントリ数があります。したがって、遠くの分岐との相関を捉えるため、グローバル分岐履歴長をなるべく長くすることが重要です。

PHTエントリ数が4 Mi以上ある場合でも、グローバル分岐履歴長を22より大きくするのは性能を低下させる

PHTエントリ数は事実上無限大とみなせます。グローバル分岐履歴が長すぎる場合、「過去の分岐との相関はないが、分岐方向は偏っている分岐」を当てるために非常に多くのパターンを学習する必要があります。つまり、"初期参照ミス"の発生が支配的な領域です。したがって、"初期参照ミス"の数を減らすため、グローバル分岐履歴長をむやみに長くしないことが重要です。

エントリー数4 GiのPHTを使用したときの、分岐履歴長毎のgshare分岐予測器の性能の比較

f:id:lpha_z:20200308230450p:plain

分岐履歴長22のところで最小値を取っていることがわかります。

bimodal分岐予測器と、容量ごとに最適な分岐履歴長を使用したgshare分岐予測器の性能の比較

f:id:lpha_z:20200308225810p:plain

分岐予測器としてよく使われる1KiB～64KiBの範囲で、効率よく性能向上が得られています。 特に、容量をつぎ込んだbimodal分岐予測器の限界10.397 misp./KIをたったの512 Byteで実現できます。

また、どれだけ容量をつぎ込んだとしても、5.585 misp./KI止まりです。 gshare分岐予測器には先ほど見たような複数のトレードオフが存在するため、容量をつぎ込めば性能が上がるというわけではありません。

まとめ

gshare分岐予測器について、xorでインデックスを作るといってもエイリアスが起こりにくい作り方をするためには一工夫いることがわかりました。

また、シミュレータで非現実的な大きさまでのgshare分岐予測器の実験を行うことにより、最適なグローバル分岐履歴長の選び方と、なぜそうなるのかの理由がわかりました。

*1:実際に出現するパターンは限られており、指数的には増えないとされています

*2:実際には443個ですが、3つは壊れています

*3:ちなみに、現在最も性能が高いと思われている分岐予測器であるBATAGE（2018年発表）は、8 KiB（PHTエントリ数32768に相当）でmisp./KIが4.183です。

*4:もしかしたら、分岐履歴を折りたたむことでより長い分岐履歴を使ったほうが良い可能性もあります

*5:この問題に対し、1990年代後半にエイリアス発生率を下げる手法が広く研究されました。Bi-mode分岐予測器、Agree-mode分岐予測器、gskew分岐予測器などがその一例です