パイプラインと分岐予測
この章でわかること:
- パイプライン: CPUが命令を流れ作業で重ねて処理する仕組み
- パイプラインを止める要因(ハザード)と、分岐予測・投機実行
- 分岐予測ミスのコストの実測。データの並び順だけで10倍の差が出る理由
- 分岐をなくすコードの書き方と、その効果
- スーパースカラとアウトオブオーダー実行。依存関係が速度を決めること
命令を流れ作業で重ねる
Section titled “命令を流れ作業で重ねる”1章では、CPUは命令を「フェッチ→デコード→実行」の順に処理すると 説明しました。ただし、1つの命令が終わってから次を始めるわけではありません。 それでは各段の回路が大半の時間、何もせず待つことになります。
そこでCPUは、命令の処理をパイプライン(pipeline)という方式で重ねます。 例えば、工場の流れ作業のようなものです。工程を担当ごとに分け、 1つ目の製品が第2工程に進んだら、すぐ2つ目の製品を第1工程に投入します。
5段パイプラインの例。サイクル5以降は、毎サイクル1つの命令が完成する
図は教科書的な5段構成の例です。1つの命令が完成するまでは5サイクル かかりますが、パイプラインが埋まっていれば毎サイクル1命令が完成します。 実際の現代CPUのパイプラインはもっと細かく、15〜20段程度に分かれています。
パイプラインを止めるもの
Section titled “パイプラインを止めるもの”流れ作業は、途中で手が止まると全体が止まります。 パイプラインの進行を妨げる要因をハザード(hazard)、 それによって生じる待ちをストール(stall)と呼びます。 主なハザードは2種類あります。
- データハザード — 前の命令の結果を次の命令が使う場合、 結果が出るまで待つ必要があります。前章のポインタチェイシングが 遅かったのは、「次に読む場所」が「今の読み出しの結果」に依存する、 データハザードの極端な例だったと言えます
- 制御ハザード —
ifやループの実体は「条件付きジャンプ命令」です。 ジャンプするかどうかが確定するまで、次にどの命令を フェッチすればよいかわかりません
このうち制御ハザードは深刻です。プログラムにはおおよそ 5〜6命令に1つの割合で分岐が現れるため、分岐のたびに パイプラインを止めていては、性能が数分の1になってしまいます。
分岐予測 — 「たぶんこっち」で走り出す
Section titled “分岐予測 — 「たぶんこっち」で走り出す”そこでCPUは、分岐予測器(branch predictor)という回路で 「この分岐はたぶんこちらに進む」と予測し、確定を待たずに 予測した側の命令を先に実行してしまいます。 これを投機実行(speculative execution)と呼びます。
- 予測が当たれば、分岐のコストはほぼゼロです
- 外れたら、先走って実行した分をすべて捨てて正しい側をやり直します。 このペナルティはおおよそ15〜25サイクルです
現代の分岐予測器は過去の分岐履歴をもとに学習し、的中率は高いです。 ループの終了判定はほぼ確実に当てますし、規則的なパターンも学習します。 当てられないのは、規則性のない、コイン投げのような分岐だけです。
実験: 予測ミスを目で見る
Section titled “実験: 予測ミスを目で見る”「コイン投げのような分岐」を意図的に作って、コストを測ってみます。 0〜255の乱数1000万個に対して「128以上なら合計に足す」だけの処理です。 同じ内容のデータを、並び順だけ変えて2回実行します。
use std::time::Instant;
// 疑似乱数(外部クレートなし)fn xorshift(state: &mut u64) -> u64 { *state ^= *state << 13; *state ^= *state >> 7; *state ^= *state << 17; *state}
fn main() { let n = 10_000_000; let mut state = 0x2545_F491_4F6C_DD1D_u64; let unsorted: Vec<u8> = (0..n) .map(|_| (xorshift(&mut state) & 0xFF) as u8) .collect(); let mut sorted = unsorted.clone(); sorted.sort_unstable();
// まったく同じコードを、並び順だけ違う同じ内容のデータに適用する for (name, data) in [("未ソート", &unsorted), ("ソート済", &sorted)] { let start = Instant::now(); let mut sum = 0u64; for &v in data.iter() { if v >= 128 { sum += v as u64; } } println!("{name}: {:>9.3?} (sum={sum})", start.elapsed()); }}筆者の実測(Playground)では、未ソートが約42ミリ秒、ソート済みが 約4ミリ秒。データの並び順を変えただけで10倍の差がつきました。
- 未ソートでは、
v >= 128は要素ごとにランダムに真偽が変わります。 予測器は学習のしようがなく、約半分の分岐で予測を外します。 1000万回の半分、500万回のミス×20数サイクルのペナルティが上乗せされます - ソート済みでは、前半はずっと偽、後半はずっと真です。 切り替わりの1回を除き、予測はほぼ全部当たります
計算量の考え方ではどちらもO(n)で同じです。しかし実行時間は 10倍違う。この差を説明できるかどうかが、CPUを知っている かどうかの分かれ目です。
なお、ソースコードのifが本物の分岐命令になるかどうかは
コンパイラの判断です。この実験では分岐として残っていることを
実測が示していますが、コンパイラの更新で結果が変わる可能性はあります。
実験の主眼は「予測できない分岐は高くつく」という仕組みの確認です。
分岐をなくす
Section titled “分岐をなくす”予測できない分岐が高くつくなら、分岐そのものをなくす手があります。 ブランチレス(branchless)と呼ばれる書き方です。
代表的な手法は、条件を0か1の数値に変換して算術に混ぜ込むことです。
ifは消え、常に同じ命令列が実行されます。
もう1つ、同じ処理をイテレータで書いた場合も測ってみます。
use std::time::Instant;
fn xorshift(state: &mut u64) -> u64 { *state ^= *state << 13; *state ^= *state >> 7; *state ^= *state << 17; *state}
fn main() { let n = 10_000_000; let mut state = 0x2545_F491_4F6C_DD1D_u64; let unsorted: Vec<u8> = (0..n) .map(|_| (xorshift(&mut state) & 0xFF) as u8) .collect(); let mut sorted = unsorted.clone(); sorted.sort_unstable();
// (1) if を算術に置き換える: 条件を 0/1 の数値にして掛ける for (name, data) in [("未ソート", &unsorted), ("ソート済", &sorted)] { let start = Instant::now(); let mut sum = 0u64; for &v in data.iter() { sum += u64::from(v >= 128) * v as u64; } println!("算術 {name}: {:>9.3?} (sum={sum})", start.elapsed()); }
// (2) イテレータで書く for (name, data) in [("未ソート", &unsorted), ("ソート済", &sorted)] { let start = Instant::now(); let sum: u64 = data .iter() .filter(|&&v| v >= 128) .map(|&v| v as u64) .sum(); println!("filter {name}: {:>9.3?} (sum={sum})", start.elapsed()); }}筆者の実測(Playground)では、算術版もイテレータ版も、未ソート・ソート済みの どちらでも約3.6ミリ秒でした。並び順への依存が消え、 未ソートに対しては元のコードの10倍以上速くなっています。
イテレータ版が速い点は注目に値します。filter().map().sum()という
書き方は、コンパイラにとって「全要素に同じ計算を適用する」構造が
明確なため、分岐のない命令列(さらにはSIMD命令)へ変換しやすいのです。
条件分岐を条件付き移動(conditional move)命令などの計算に置き換える
このコンパイラ最適化をif変換(if-conversion)と呼びます。
最初の実験のif文はif変換されず、本物の分岐として実行されていました。
同じ意味のコードでも、書き方によってコンパイラが分岐を消せる場合と
消せない場合があるということです(7章で再訪します)。
ただし、ブランチレスが常に勝つわけではありません。
条件の両側を毎回計算するコストがかかるため、
予測がよく当たる分岐(ほぼ常に真、など)はifのままのほうが速いことも
多くあります。判断は計測で行います(8章)。
1サイクルに複数の命令 — スーパースカラ
Section titled “1サイクルに複数の命令 — スーパースカラ”パイプラインで「毎サイクル1命令」になりました。現代のCPUは さらに先を行き、実行ユニットを複数持ち、1サイクルに4〜8命令程度を 同時に処理します。これをスーパースカラ(superscalar)実行と呼びます。
さらに、命令をプログラムの記述順どおりではなく、依存関係が 解決したものから実行するアウトオブオーダー実行(out-of-order execution)も 行います。命令の並びに隠れた「同時に実行できる度合い」を 命令レベル並列性(instruction-level parallelism、ILP)と呼び、 1サイクルあたりの実行命令数をIPC(instructions per cycle)と呼びます。
この仕組みを最大限使えるかどうかは、命令同士の依存関係で決まります。 実験で確かめます。浮動小数点数の合計を、 「1本の変数に足し込む」場合と「4本の変数に分けて足し込む」場合で比べます。
use std::time::Instant;
fn main() { // 100万要素 = 8MB。キャッシュにほぼ収まる大きさにして、メモリ待ちの影響を除く let n = 1_000_000; let data: Vec<f64> = (0..n).map(|i| (i % 100) as f64 * 0.01).collect(); let passes = 20;
// 1本のアキュムレータ: 前の加算が終わるまで次の加算を始められない let start = Instant::now(); let mut sum = 0.0f64; for _ in 0..passes { for &v in data.iter() { sum += v; } } println!("アキュムレータ1本: {:>9.3?} (sum={sum:.0})", start.elapsed());
// 4本のアキュムレータ: 依存しない4つの加算の連鎖が並行して進む let start = Instant::now(); let mut sum = 0.0f64; for _ in 0..passes { let mut s = [0.0f64; 4]; let mut chunks = data.chunks_exact(4); for c in &mut chunks { s[0] += c[0]; s[1] += c[1]; s[2] += c[2]; s[3] += c[3]; } sum += s.iter().sum::<f64>() + chunks.remainder().iter().sum::<f64>(); } println!("アキュムレータ4本: {:>9.3?} (sum={sum:.0})", start.elapsed());}コードの補足: chunks_exact(4)はスライスを4要素ずつの塊で
走査するイテレータで、4で割り切れなかった端数はremainder()で
取り出して別に処理します。
筆者の実測(Playground)では約19ミリ秒と約5ミリ秒、3.8倍の差でした。
1本の場合、sum += vは前の加算の結果に依存するため、
加算のレイテンシ(3〜4サイクル)ごとに1個しか進みません。
CPUにいくつ実行ユニットがあっても、依存の鎖が直列なら使えないのです。
4本に分けると独立した鎖が4本になり、加算が並行して進みます。
なお、整数の合計であればコンパイラが自動でこの種の変形を行いますが、 浮動小数点数では足す順序を変えると結果がわずかに変わりうるため、 コンパイラは勝手に変形しません。この話は次章で詳しく扱います。
- CPUは命令をパイプラインで重ね、スーパースカラ+アウトオブオーダーで 1サイクルに複数命令を実行します
- 分岐は予測して投機実行します。予測ミスは15〜25サイクル程度の損失で、 予測できない分岐はデータの並び順だけで10倍の差を生みました
- 予測できない分岐は、算術化やイテレータでブランチレスにできます。 ただし常に速いわけではなく、判断は計測で行います
- 速度を決めるのは命令数だけでなく依存関係です。 独立した計算の鎖を増やすとIPCが上がります
「全要素に同じ計算をする」処理は、分岐をなくせるだけでなく、 複数の要素を1命令でまとめて計算することもできます。 次章はその仕組み、SIMDです。