マルチコアと並列処理

この章でわかること:

CPUにコアが複数ある理由と、コアごとのキャッシュの構成
キャッシュコヒーレンスと、「共有していないのに遅くなる」false sharing
データ競合と、Rustがそれをコンパイル時に防ぐ仕組みの要点
アトミック操作とメモリオーダリングの入門
Rayonによるデータ並列化と、並列化がスケールしない3つの要因

コアが増えた理由

2000年代半ばまで、CPUはクロック周波数の向上で速くなり続けました。しかし周波数を上げるほど消費電力と発熱が急増し、 1つの処理装置を速くする路線は限界を迎えます。そこで方針が変わりました。同じ処理装置を複数並べる方向です。

この処理装置の1つずつをコア(core)と呼びます。各コアは1章〜4章で見た仕組み(パイプライン、キャッシュ、SIMD)をそれぞれ独立に持っていて、別々のプログラムを同時に実行できます。現代のCPUは、ノートPCで数個〜十数個、サーバでは百個超のコアを持ちます。

なお、1つのコアに2つの命令の流れを混在させるSMT (simultaneous multithreading、Intelの呼び名はHyper-Threading)という技術もあり、OSからは「論理コア」が物理コアより多く見えることがあります。 Rustではstd::thread::available_parallelism()でこの値を取得できます。

ソフトウェア側の用語も整理しておきます。スレッド(thread)は OSが管理する命令の流れの単位で、OSが各コアに割り当てます。複数の仕事を(1コアでも)交互に進める構造を並行(concurrency)、複数のコアで文字どおり同時に実行することを並列(parallelism)と呼び分けます。この章の主題は並列です。

コアごとのキャッシュとコヒーレンス

2章のキャッシュ階層は、マルチコアでは例えば次の形になります。 L1・L2は各コア専用、L3は全コア共有という、よくある構成の一例です(実際の段数や共有範囲はCPUごとに異なります)。

flowchart TB
    subgraph c0 ["コア0"]
        core0["実行ユニット"] --- l1a["L1"] --- l2a["L2"]
    end
    subgraph c1 ["コア1"]
        core1["実行ユニット"] --- l1b["L1"] --- l2b["L2"]
    end
    l2a --- l3["L3 (共有)"]
    l2b --- l3
    l3 --- dram["メインメモリ"]

ここで新しい問題が生まれます。同じメモリ上のデータの写しが、複数のコアのL1に同時に存在できてしまうことです。コア0が値を書き換えたのに、コア1が古い写しを読み続けたら、プログラムは壊れます。

これを防ぐハードウェアの仕組みがキャッシュコヒーレンス (cache coherence)です。キャッシュライン単位で「共有中」「変更済み」などの状態を管理し、あるコアがラインに書き込むときは、他のコアが持つ同じラインの写しを無効化します(代表的な方式の頭文字からMESIプロトコルと呼ばれます)。

プログラマ視点の要点はこうです — 読むだけなら写しは何枚あってもよい。書くには、そのラインの排他的な「所有権」を得る必要がある。 複数のコアが同じラインに書き込み続けると、ラインの所有権がコア間を行き来し、そのたびに数十サイクルの通信コストがかかります。

所有権の奪い合いは、「同じ変数」を取り合うときだけ起きるのではありません。 同じキャッシュラインに載った別々の変数でも起きます。

2つのスレッドが、それぞれ自分専用のカウンタを増やすだけの実験です。2つのカウンタの置き場所(同じキャッシュラインか、別のラインか)だけを変えて比べます。ラインの幅はCPUによって 64バイトまたは128バイトなので、実験では128バイト境界を使ってどちらのCPUでも意図どおりになるようにしています。

コードの補足を3つ。#[repr(align(128))]は「この型を128バイト境界に置く」指定です。thread::scopeは「スコープを抜けるまでに中で作った全スレッドの終了を待つ」仕組みで、この保証があるため、スタック上の変数への参照をスレッドに渡せます。クロージャのmoveは、使う変数(ここでは参照)の所有権をクロージャに移す指定です。

use std::sync::atomic::{AtomicU64, Ordering};
use std::thread;
use std::time::Instant;

// 128バイト境界に整列した入れ物。2つのカウンタが必ず同じ
// キャッシュラインに載る(ライン幅が64でも128バイトでも)
#[repr(align(128))]
struct SameLine([AtomicU64; 2]);

// 1つで128バイトを占有する入れ物。2つ並べると
// カウンタは必ず別のキャッシュラインに載る
#[repr(align(128))]
struct Padded(AtomicU64);

fn main() {
    println!("利用可能な並列度: {:?}", thread::available_parallelism());

    let iters = 50_000_000u64;

    // (1) 同じキャッシュラインに載った2つのカウンタ
    let same = SameLine([AtomicU64::new(0), AtomicU64::new(0)]);
    let start = Instant::now();
    thread::scope(|s| {
        for c in &same.0 {
            s.spawn(move || {
                for _ in 0..iters {
                    c.fetch_add(1, Ordering::Relaxed);
                }
            });
        }
    });
    println!("同じライン: {:>9.3?}", start.elapsed());

    // (2) 別のキャッシュラインに載った2つのカウンタ
    let padded = [Padded(AtomicU64::new(0)), Padded(AtomicU64::new(0))];
    let start = Instant::now();
    thread::scope(|s| {
        for p in &padded {
            s.spawn(move || {
                for _ in 0..iters {
                    p.0.fetch_add(1, Ordering::Relaxed);
                }
            });
        }
    });
    println!("別のライン: {:>9.3?}", start.elapsed());
}

use std::sync::atomic::{AtomicU64, Ordering};
use std::thread;
use std::time::Instant;

// 128バイト境界に整列した入れ物。2つのカウンタが必ず同じ
// キャッシュラインに載る(ライン幅が64でも128バイトでも)
#[repr(align(128))]
struct SameLine([AtomicU64; 2]);

// 1つで128バイトを占有する入れ物。2つ並べると
// カウンタは必ず別のキャッシュラインに載る
#[repr(align(128))]
struct Padded(AtomicU64);

fn main() {
    println!("利用可能な並列度: {:?}", thread::available_parallelism());

let iters = 50_000_000u64;

// (1) 同じキャッシュラインに載った2つのカウンタ
    let same = SameLine([AtomicU64::new(0), AtomicU64::new(0)]);
    let start = Instant::now();
    thread::scope(|s| {
        for c in &same.0 {
            s.spawn(move || {
                for _ in 0..iters {
                    c.fetch_add(1, Ordering::Relaxed);
                }
            });
        }
    });
    println!("同じライン: {:>9.3?}", start.elapsed());

// (2) 別のキャッシュラインに載った2つのカウンタ
    let padded = [Padded(AtomicU64::new(0)), Padded(AtomicU64::new(0))];
    let start = Instant::now();
    thread::scope(|s| {
        for p in &padded {
            s.spawn(move || {
                for _ in 0..iters {
                    p.0.fetch_add(1, Ordering::Relaxed);
                }
            });
        }
    });
    println!("別のライン: {:>9.3?}", start.elapsed());
}

筆者の実測(Playground、2コア)では、同じラインに載せた配置が約670ミリ秒、別のラインに離した配置が約270ミリ秒。2.5倍の差です。

隣接した2つのAtomicU64(8バイト×2)は同じキャッシュラインに載ります。互いのカウンタに触れていなくても、ライン単位で所有権が行き来してしまう——この現象をfalse sharing(偽共有)と呼びます。論理的には何も共有していないのに、物理的な置き場所のせいで共有コストを払わされるわけです。

対策は実験のとおり、頻繁に書く変数をスレッドごとに別ラインへ離すことです。実験で使った#[repr(align(128))]のほか、 crossbeamクレートのCachePadded型がこの目的に使えます。

データ競合とRustの保証

ここまでのカウンタにAtomicU64という型を使いました。もし普通のu64を2つのスレッドから同期なしで書き換えたらどうなるか—— これはデータ競合(data race)と呼ばれ、C/C++では未定義動作、つまり「何が起きてもおかしくない」状態です。壊れた値が読めるだけでなく、コンパイラの最適化前提が崩れてプログラム全体が不正になります。

Rustの見どころは、unsafeを使わない範囲のコードについて、データ競合をコンパイル時に排除することです。所有権と借用の規則(可変参照&mutは同時に1つ)に加えて、「スレッド間で移動してよい型」を表すSend、「スレッド間で共有してよい型」を表すSyncというトレイトがあり、条件を満たさない型をスレッドへ渡すコードはコンパイルに失敗します。先ほどの実験でAtomicU64を使ったのは、まさにu64のままではコンパイラが拒否するからです。

正確に言うと、Rustが防ぐのは「データ競合」です。処理のタイミングに依存するバグ一般(競合状態)やデッドロックまで防ぐわけではありません。それでも「コンパイルが通った並列コードにデータ競合はない」という保証は、並列プログラミングの心理的なハードルを大きく下げます。

アトミック操作とメモリオーダリング

アトミック操作(atomic operation)は、他のスレッドから「途中の状態」が決して観測されない、分割不可能な読み書きのことで、 CPUの専用命令で実現されます。 fetch_addは「読んで、足して、書き戻す」を1つの不可分な操作として実行するため、ロックなしでカウンタを共有できます。複雑な共有状態にはMutexを使いますが、単一の数値やフラグならアトミック型のほうが軽量です。

アトミック操作の各メソッドにはOrderingという引数がありました。これはメモリオーダリング(memory ordering)、つまり「この操作の前後で、他の読み書きの順序をどこまで保証するか」の指定です。 3章で見たとおりCPUは命令を並べ替えて実行し、コンパイラもコードを並べ替えます。1スレッドの結果は変わらなくても、 他のスレッドから見える順序は変わりうるのです。

Relaxed — その変数の操作が不可分であることだけを保証します。実験のような単純なカウンタはこれで十分です
Acquire/Release — 例えばスレッドAがデータを書いてから readyフラグをReleaseで立て、スレッドBがreadyをAcquireで読んで真だったとします。このときBには、フラグ以前のAの書き込み (データ本体)もすべて見えることが保証されます。Relaxedにはこの保証がなく、「フラグは見えたがデータはまだ」がありえます
SeqCst — さらに、SeqCst同士の操作について、全スレッドで一致する1つの順序を保証します

正しい使い分けはそれ自体が1冊の本になる主題なので、本書では「順序の保証には段階がある」ことを知るにとどめます。詳しく学ぶ資料は付録に挙げました。

Rayonでデータ並列

低水準の話が続いたので、実用の並列化に進みます。「大量の要素それぞれに独立な計算をする」形の処理 (データ並列、data parallelism)なら、 Rustではrayonクレートで簡潔に並列化できます。

use rayon::prelude::*;
use std::time::Instant;

// コラッツ数列: n が 1 になるまでの手数を数える(1要素あたりの仕事が重い例)
fn collatz_steps(mut n: u64) -> u64 {
    let mut steps = 0;
    while n != 1 {
        n = if n % 2 == 0 { n / 2 } else { 3 * n + 1 };
        steps += 1;
    }
    steps
}

fn main() {
    let range = 1u64..2_000_000;

    // rayonのスレッドプールは初回利用時に作られるため、
    // 計測前に一度動かして準備しておく(ウォームアップ)
    rayon::join(|| (), || ());

    let start = Instant::now();
    let total: u64 = range.clone().map(collatz_steps).sum();
    println!("逐次: {:>9.3?} (total={total})", start.elapsed());

    // 変更点は into_par_iter() だけ
    let start = Instant::now();
    let total: u64 = range.into_par_iter().map(collatz_steps).sum();
    println!("並列: {:>9.3?} (total={total})", start.elapsed());
}

変更点は.into_par_iter()の1箇所だけです。rayonはスレッドプールを用意し、範囲を分割して各スレッドに配ります。手の空いたスレッドは他のスレッドの未処理分を引き取る(ワークスティーリング、 work stealing)ため、負荷が自然に均されます。

筆者の実測では、Playground(2コア共有)では354ミリ秒→214ミリ秒の約1.7倍、手元の10コアのMac(Apple M4)では231ミリ秒→29ミリ秒の 約8倍になりました。コア数なりの効果が出ています。

適用の目安は2つです。要素ごとの計算が十分重いこと (軽すぎると分配のオーバーヘッドが勝ちます)。そして要素間が独立であることです。

なお、Webアプリケーションの文脈では役割分担に注意してください。多数のリクエストを待ち受けて捌く「並行」はasyncランタイム(tokioなど)の領分です。rayonが受け持つのは、1つの重い計算を複数コアで割る「並列」です。リクエスト処理の中で重い計算をrayonに逃がす、という組み合わせはありえます。

並列化がスケールしない3つの要因

コアを2倍にしても2倍速くならないことは珍しくありません。主要な要因は3つあります。

逐次部分の存在 — プログラムの一部でも並列化できない部分が残ると、そこが上限を決めます。並列化できる割合が90%の場合、コアが無限にあっても最大10倍にしかなりません (Amdahlの法則、Amdahl’s law)
メモリ帯域の飽和 — 2章で見たとおり、単純な走査はメモリ律速です。コアを増やしても、メモリからデータを運ぶ帯域は共有なので頭打ちになります(12章で実測します)
同期と通信 — ロックの取り合い、アトミック操作の連打、 false sharing。いずれもコア間のライン移動という物理コストです

まとめ

現代のCPUは同じ構造のコアを複数持ち、L1/L2はコア専用、L3は共有です
キャッシュコヒーレンスにより、書き込みはライン所有権の奪い合いになります。別々の変数でも同じラインに載っていれば遅くなります(false sharing)
Rustはデータ競合になるコードをコンパイル時に拒否します
単純な共有カウンタやフラグはアトミック型で。順序保証には段階があります
データ並列はrayonで。10コアの手元環境で8倍の実測が得られました
スケールを阻むのは、逐次部分・メモリ帯域・同期コストの3つです

これでPart Iは終わりです。CPUの主要な仕組み——キャッシュ、パイプライン、分岐予測、SIMD、マルチコア——を一通り見ました。 Part IIでは視点をコンパイラに移します。Rustコンパイラがあなたのコードをどう機械語へ変換し、どんな最適化を施しているのか。 1章で「ループが消えた」種明かしの全体像です。