MaybeUnInit

Appearance

Return to top
On this page

「プログラマーのためのCPU入門」を読んだ

2023-02-22

目次を眺めたかぎり、まさに自分が欲していた内容だったので即購入した。

読後の感想としても期待を裏切らないもので、とても良かった。また個人的にはRust Atomics and Locksを読んでいる最中というのも幸いした。

両者をあわせて読むことで、知識を補完できたように思う。

目次

モチベーション

特に「キャッシュコヒーレンス制御」「メモリ順序付け」を詳しく知りたいというモチベーションがあった。これまでマルチコアなハードウェアを設計したこがなかったこともあり、キャッシュコヒーレンス制御がどう行われているのか意識したことがなかったためだ。

また、それが「メモリ順序付け」にどう影響を与えるかなども考えたことすらなかったためこの書籍を通してそのあたりの知識を得たいと考えた。これはRust Atomics and Locksで腑に落ちない点があったというのもある。

以下印象に残った箇所を挙げておく

パイプラインとそれを効率化する手法

まずはパイプラインの説明から始まり、アウトオブオーダー実行の話や分岐予測の話へとつながっていく。
第3章の終わりではアウトオブオーダー実行が可能なケースとデータ依存関係により先行命令を待つケースの比較。第4章の終わりでは分岐予測がほぼ成功するケースとときどき失敗するケースの比較が掲載されており面白かった。

これらの例は機械語で用意されており、結果もさることながら「どうやったら分岐予測が失敗するような状況を作り出せるか」などが分かって良かった。

キャッシュメモリ

第5章ではキャッシュの基本的な内容から、キャッシュを意図的にミスヒットさせてどれくらいパフォーマンスに違いがでるかの実験まで記載されている。

個人的には以下を知れたのが良かった

  • キャッシュテーブルの実装方式に「フルアソシエイティブ」「セットアソシエイティブ」という方式がある
  • 「セットアソシエイティブ」は検索キーであるアドレスの一部をテーブル内のindexに対応させる方式
  • キャッシュアクセスを高速に行うために一般的なCPUでは「セットアソシエイティブ」が採用されている
  • 競合性ミスの対策としてテーブルが多重化(way数)されており、一般的なCPUは2~8wayである

仮想記憶

第6章では主にTLB周りの話でこちらも章末の実験が面白かった。 ここでは「TLBアクセスをほぼ完全にミスさせる例」として「4096バイトずつ増分したアドレスへのアクセスを8192回ループする」という例が紹介されていた。L2 TLBエントリ数がたかだか数千なのでミスが発生するというものだ。 これをperf -e "dTLB-load-misses"で計測してたのだが、そもそも、このようにTLBのミスヒットを計測できることを知らなかったのでこれも収穫となった。

ここからは本書の内容と直接関係ないがTLBでだらだら検索していたら以下のページを見つけたので合わせて記録しておく。

https://docs.kernel.org/x86/tlb.html

要は、x86においてTLBをflushする方法はinvlpg命令でページ単位でTLBを無効にするか、2命令ですべてのTLBを無効化するかの選択があるがどちらが良いかはケースバイケース。

このときinvlpg命令が多く実行されているようであれば、ページ単位の無効化処理が多く以下の値を調整することでglobal flushの割合を増やすことができようなことが書いてある。

/sys/kernel/debug/x86/tlb_single_page_flush_ceiling

このあたりの挙動はちょうど読み直している「はじめて読む486」や「IA-32 インテル® アーキテクチャ ソフトウェア・デベロッパーズ・マニュアル」にある「ページング（仮想メモリ）の概要」などを見て補完するのが良さそうだ。

キャッシュコヒーレンス制御

これまでマルチコアにおけるキャッシュコヒーレンス制御についてあまり考えたことがなかったのだけど、第10章ではそのあたりの知識がまとまっている。

  • 現在主流なプロトコルはMSI(もしくはその派生)
    • これは他のCPUのキャッシュを覗き見しつつ管理するスヌープ方式
    • 書き込み時に他のキャッシュを無効化するライトインバリデート型
  • AMD社のx86はMOESI,Intel社のx86はMESIF,arm社はMESIやMOESIの採用例がある

このような仕組みのため複数のCPUから同一キャッシュライン上の異なるアドレスへのアクセスによりキャッシュがインバリデートされるfalse sharingという現象が発生することを学んだ。

false sharingは「Rust Atomics and Locks」でも、今読んでる「詳解システム・パフォーマンス」でも言及が合ったので短期間で何回も目にしている。

章末にfalse sharingを起こす実験コードがあるが、ひょっとしたらこれはRustのコードを見たほうがイメージが付きやすいかもしれない。以下の引用したコードを貼っておく。

これはA[1]がA[0],A[2]と同一キャッシュラインに乗るたキャッシュが有効にならない例だ。

rust
#[repr(align(64))] // This struct must be 64-byte aligned.
struct Aligned(AtomicU64);

static A: [Aligned; 3] = [
    Aligned(AtomicU64::new(0)),
    Aligned(AtomicU64::new(0)),
    Aligned(AtomicU64::new(0)),
];

fn main() {
    black_box(&A);
    thread::spawn(|| {
        loop {
            A[0].0.store(1, Relaxed);
            A[2].0.store(1, Relaxed);
        }
    });
    let start = Instant::now();
    for _ in 0..1_000_000_000 {
        black_box(A[1].0.load(Relaxed));
    }
    println!("{:?}", start.elapsed());
}

「詳解システム・パフォーマンス」では同じキャッシュラインに乗らないようにpaddingを設けようね。と書いてあったと記憶している。

メモリ順序付け

個人的にもっとも期待していたのが第11章の「メモリ順序付け」だった。
「Rust Atomics and Locks」を読んだでも書いたがいまいちx86におけるacquire release semanticsが腑に落ちていなかったのが大きな理由である。

これは先行ストアと後続ロードの入れ替えとストアバッファの挙動の関係が整理できていなかったことに起因していて、ようやく整理ができた気がしている。

特に以下のように書いてくれてあるのが良かった。

全体を高速化するために、滞留中のストアバッファから本体への書き込み処理の完了をまたずに読み出しアクセスを先に処理します。先行の滞留しているストアを後続のロードが追い越すことになるので、結果としてメモリアクセスの順序が入れ替わります。 このケースは、メモリアクセス順序の入れ替えに慎重なx86においても発生します

また以下のNOTEも良かった。というのもオーダリング周りを調べていくとアウトオブオーダー実行については言及していてもメモリシステムによる入れ替えに言及しているケースはあまり見られなかったように思うからだ。両者を混同しないようにと書いてあるのがとても良い。

メモリアクセスの順序入れ替えは、このアウトオブオーダー実行によっても発生しますが、インオーダー実行のCPUでもメモリシステムの仕組みにより発生する可能性があります。両者を混同しないように注意してください。

ちなみにこの点に関してはマニュアルにもちゃんと書いてある。この記述に気づいたのはこの書籍を読んでからだが...

インテル® Pentium® プロセッサおよびIntel486™プロセッサは、「プロセッサ・オーダリング」と定義されるメモリ・オーダリング・モデルを使用するが、ほとんどの状況ではストロング・オーダリング・プロセッサとして動作する。システムバスでは、読み取りと書き込みは常にプログラムされた順序で実行されるが、次のような場合には、プロセッサ・オーダリングが行われる。バッファリングされた書き込みがすべてキャッシュ・ヒットで、読み取りミスによってアクセスされるアドレスに指定されない場合は、システムバス上でバッファリングされている書き込みよりも先に読み取りミスを実行できる。

この章のおかげで理解が進んだのだが、逆に謎が深まった点もあり、それは軽く調べてみた。具体的には以下の記述だ。

x86でもメモリ領域(Write Combining属性領域など)やメモリ種別（キャッシュを使用しないメモリアクセう命令など）の混在によっては、表11.1で不可となっている組み合わせにおいてもメモリアクセス順序が入れ替わる可能性があります。

「表11.1で不可となっている組み合わせ」というのは先行ストアと後続ロードの入れ替え以外の入れ替えを指す。この前提が崩れるとacquire release semanticsがまたよくわからなくなってしまう。というわけで調べて見ると以下の資料を見つけた。

How to Implement a 64B PCIe* Burst Transfer on Intel® Architecture

どうもWrite Combining属性領域というのはframe bufferのメモリ領域などに設定されるもので、リング0でWRMSR命令を使用してMSRへ書き込むことで設定されるものらしい。ハードウェアに依存する話なのでおそらくOSが起動時に設定してくれているのだろうか。 fence命令で制御できそうなことも書いてあるが、ひとまず普通にプログラムを書く分には意識する必要はないのだろうと解釈した。

所感

実験付きでまとまっており、自分にはとてもいい書籍だったし、この書籍のおかげで「Rust Atomics and Locks」の理解が進んだ。また、これを機に「はじめて読む486」を読み直したり「詳解システム・パフォーマンス」を読み始めたりいいキッカケにもなっているし、永らく積んであるヘネパタも一回読まないといけないなと思い始めてる。（ちらっと見た感じキャッシュコヒーレンス制御の話などが詳しく書かれていそうに見えた。）

以上。