Booklog - プログラマーのための CPU 入門 CPU は如何にしてソフトウェアを高速に実行するか

序文と目次と付録 B。 如何に CPU がソフトウェアを実行するのか、ミクロな振る舞いから肌感を養いソフトウェアの高速化につなげるという本。 CPU 命令に馴染みのない人は付録 B を読めとのことなので先に読んでおいた。 CISC, RISC の設計思想の違いが見えたり。 ミクロな振る舞いに着目するから表紙も小人なんか、より糸は thread やったりして。 これまで CPU-bound, Memory-bound, I/O-bound とかの言葉は使ってきたが、そこの解像度が上がるとよいな。

2025-01-15, read count: 1, page: i ~ xii, 246 ~ 256

第 1 章 CPU は如何にしてソフトウェアを高速に実行するか。 この本はヘネパタの定義に沿った CPU 時間が短いほど「CPU の性能」が良いとする。 CPU 時間 = ①実行命令数/プログラム × ②クロックサイクル数/実行命令数 × ③秒数/クロックサイクル数 ① はプログラムやコンパイラや命令セット、 ② は CPU ハードウェア内部構造、 ③ は半導体プロセスや回路 で決まる。 この本は近年は外から見えにくい ② microarchitecture に焦点を当てて、ソフトウェア高速化にどのような効果をもたらすかを知るのが目的。 初っ端からヘネパタ。読後のチャレンジ課題か。

2025-01-16, read count: 1, page: 1 ~ 2

第 1 章 CPU は如何にしてソフトウェアを高速に実行するか。 現代主流の CPU から見て、ソフトウェアは「小さい命令の流れ」でありその流れが速いほど速く実行できる。 現代の命令セットアーキテクチャと CPU の内部構造(マイクロアーキテクチャ)は分離されてる。 かつては Lisp マシンや Prolog マシンのような CPU もあったが「小さい命令の流れ」を処理する方が汎用性・高速化・小型化に向いていて廃れた。

2025-01-21, read count: 1, page: 3 ~ 9

第 2 章 命令の密度を上げるさまざまな工夫。 現代の CPU は命令流を逐次的に処理する。ハードウェア的には命令流の命令を 3 つのステージに分けて扱う(簡単のため。実際のステージは CPU 毎に異なる)。 命令フェッチ(PC レジスタに従い命令メモリからフェッチ)・命令でコード(フェッチした命令のバイト列をデコード)・命令実行(デコードした命令に従いデータメモリとレジスタ間の読み書きや演算器でレジスタの値を加工、演算で使うデータや値 = オペランド(operand)の読み込み)。 逐次処理方式は単純に命令 1 つの実行が終わってから次の命令を実行するため、 2 ステージ分のサイクルが無駄になる。 ここでいうサイクルは CPU のクロックサイクルで、命令実行に要するサイクルをレイテンシと呼ぶ。 なんかうっすら記憶にあると思ったけど情報処理技術者試験で覚えたやつか。

2025-01-22, read count: 1, page: 10 ~ 17

第 2 章 命令の密度を上げるさまざまな工夫。 逐次処理方式は安全な実装。比べてパイプライン処理(pipelining)は投機的で、ステージが完了したら次の命令を実行するため、 2 サイクル分速くなる。 代わりに命令のキャンセル処理が煩雑になる。キャンセル処理は CPU のバグの温床。 スーパースカラ(superscalar)方式は、パイプラインを増やして同時に処理する命令を増やす。 スーパーパイプライン(superpipelining)方式は、命令を扱うステージを細かく分けて処理を高速化する(具体的に何段からという定義はない)。 いずれもある種力技で、 CPU 設計の複雑さが増し性能上の制約も出てくるらしい。 いずれの高速化も速さの代わりに失うものがあると。

2025-01-23, read count: 1, page: 17 ~ 22

第 2 章 命令の密度を上げるさまざまな工夫。 スーパースカラは空間方向に流量を、スーパーパイプラインは時間方向に流速を高める。 同時に利用でき CPU の命令の密度を高められるが、投機的な実行には設計の複雑さなどのリスクが伴う。 また同時に処理できる命令は増えるが 1 命令の処理時間は変わらなのが現代の CPU の高速化。 命令の高密度化を更に高めたのがベクトル型スパコンや GPU 。 ここまで命令流が滞らない大前提であり、実際には流れを阻害する要因や回避策がある。 命令自体は速くならないというのはちゃんと理解してなかったかも。 CPU クロックの頭打ちの話か。

2025-01-24, read count: 1, page: 23 ~ 26

第 3 章 データ依存関係。 真のデータ依存関係(後続の命令の読み込みレジスタが先発する命令の書き込みレジスタに依存)、 逆依存関係(後続の命令の書き込みレジスタが先発する命令の読み込みレジスタに依存)、出力依存関係(先発・後続の命令の書き込みレジスタが同じ)、 入力依存関係(先発・後続の命令の読み込みレジスタが同じ)等あるデータ依存関係の中で命令流を滞らせるのが、真のデータ依存関係。 スーパースカラでもスーパーパイプラインでも後続の命令が待たされる。これをペナルティサイクル(penalty cycle)といい、流れを妨げる要因をハザード(hazard)という。 依存関係にない命令を入れ替えるアウトオブオーダー実行(out-of-order execution)で緩和できるが、結果の整合性を保つためには再順序化(reorder)が必要となる。 ただし命令数分の re-order buffer が必要となりそれ以上の実行はできない制約ため実装に関して大きな問題がある。 アウトオブオーダー実行では逆依存関係や出力依存関係も影響を受けるため、依存関係にあるレジスタを解消するためのレジスタリネーム(register renaming)が必要となる。 これも専用のレジスタが必要なため、数が足りなければ実行する命令数を制約することになる。 速度を求めた結果の制約が重いというのがわかってきた。

2025-01-25, read count: 1, page: 27 ~ 35

第 3 章 データ依存関係。 レイテンシが大きい命令を避けるソフトウェア実装の工夫に触れられる。 レイテンシが大きい命令自体の利用を避けるとか、レイテンシが大きい命令を先行させるソフトウェアパイプライニング最適化(software pipelining optimization)、 依存関係のない命令で空きを埋めるループアンローリング最適化(loop unrolling optimization)等。 ここで言うソフトウェアはアセンブリレベルの話で、コンパイラによる最適化が大きいのかな。 高次の言語での四則演算のような演算がそのまま命令に翻訳されるなら、なるべく除算と乗算のようなレイテンシの大きい命令を避けるという工夫はできるが。

2025-01-26, read count: 1, page: 35 ~ 38

第 3 章 データ依存関係。 CPU の仕様書以外にレイテンシ、スーパースカラの同時実行、アウトオブオーダー実行の特性を知るために計測する方法。 CPU のミクロな挙動の計測が難しい点、 CPU の設計次第では特定の命令とレジスタの組み合わせのが速く・遅くなるようなものがある点を踏まえた上で、真のデータ依存関係を作ったアセンブリプログラムで perf コマンドを使って計測し、 cycles と instructions からレイテンシ等の特性を知る。

2025-01-27, read count: 1, page: 38 ~ 44

第 4 章 分岐命令。 PC レジスタに分岐先のアドレス(branch target address)を伝えることを分岐命令(branch instruction)という。分岐命令は特権レベルの変更を伴わずに命令流を切り替えることをいう。 これは投機的にフェッチした先行命令をキャンセルするため、パイプライン、スーパースカラ、スーパーパイプライン、アウトオブオーダーの性能を下げる。 失われるサイクルは少なくとも「命令フェッチから命令実行までのステージ数」になる。またハードウェア的にも切り替えによるキャンセル処理が煩雑になる。 文献やベンダによって分岐命令の区分や名前が異なるが、ここでいう分岐命令は無条件分岐命令(unconditional branch instruction)、条件分岐命令(conditional branch instruction)、コール命令(call instruction)/リターン命令(return instruction)(最近の CPU は無条件～のみ実装している)をさす。 この辺は暗記。

2025-01-28, read count: 1, page: 44 ~ 49

第 4 章 分岐命令。 空きステージを減少させる方法として分岐先の命令を先読みでフェッチする分岐予測(branch prediction)がある。 分岐予測では、分岐命令の存在(過去の分岐命令を保存し命令フェッチ時に判定)、分岐先アドレス(BTB(Branch Target Buffer), BTAC(Branch Target Address Cache), リターンスタック(return stack, return address stack)を使う)、条件分岐命令の分岐方向(branch direction)(BHT(Branch History table), PHT(Pattern History Table), BHB(Branch History Buffer)を使う)を予測する。 分岐予測の成功率は(プログラムや CPU によるが)傾向的に 90% 台中程度で予測ミス(mis-prediction)も発生する。 過去の命令履歴に依存するので新しい命令パターンや、ハードウェア面の制約からテーブルやスタックの容量を超える数の命令やパターンを予測することはできない。 分岐予測とアウトオブオーダー実行の組み合わせで初めて、狭義の投機実行(speculative execution)が実現される。 レイテンシが大きい基本ブロック先頭付近荷配置される命令の実行前倒しができるため、アウトオブオーダー実行を導入する最大の動機といえると。 CPU の中は先読みして実行の試行錯誤の繰り返しみたいなイメージになってきた。

2025-01-29, read count: 1, page: 49 ~ 57

第 4 章 分岐命令。 ソフトウェア的にはループ内の分岐をなくしたり、インライン展開でコール・リターン命令を減らして分岐命令の影響を緩和できる。インライン展開は命令数が増えて命令キャッシュを圧迫するデメリットもある。 また多くの CPU では条件分岐命令を減らすために単純な条件実行命令が提供される。 ループアンローリング最適化により分岐命令の実行回数を減らせる可能性もあるが、ループ回数が多いほうが分岐予測の精度は上がるためトレードオフの関係がある。 分岐予測でソフトウェア的にできることはあまりないが、ループ回数の固定や優先度の高い分岐を先に配置するなどの工夫ができる。 最後に予測ミスの計測実験。ランダムな分岐条件だと予測がほぼ完全に失敗するが、偏りがあると予測の成功率が上がる例。

2025-01-30, read count: 1, page: 57 ~ 64

第 5 章 キャッシュメモリ。 主記憶(main memory)である命令メモリとデータメモリを統合したハードウェア DRAM へのアクセスは 10 ~ 100 サイクル程度かかる。これを緩和するために SRAM からなるキャッシュメモリが使われる。 ただし常にキャッシュヒット(cache hit)が起きるわけではなく、キャッシュミス(cache miss)が起きるとその性能は大きく低下する。 キャッシュミスの種類は主に、初期参照ミス(compulsory miss, cold start miss)、容量ミス(capacity miss)、競合性ミス(conflict miss, collision miss)がある(他にもある)。 これらの緩和策として、キャッシュライン(cache ine)・プリフェッチ(prefetch)での先読み、キャッシュの階層化がある。キャッシュ自体の容量増加は現時点では技術的に難しい。 ソフトウェアによる緩和の可能性(空間局所性を高める、配列アクセスは chunk して操作、多次元配列の index は内側から操作)もあるが、容易ではない。 最後にキャシュミスの計測実験。ランダムな分岐条件だと予測がほぼ完全に失敗するが、偏りがあると予測の成功率が上がる例。 情報処理技術者試験では暗記だったが今は何故その構造が必要なのかがわかってきたかな。

2025-01-31, read count: 1, page: 65 ~ 86

第 6 章 仮想記憶。 仮想記憶の中核となるのは、仮想アドレス空間(virtual address space)と物理アドレス空間(physical address space)を対応付けるアドレス変換(address translation)を行う機能。 主記憶よりも大きなメモリがあるように見せかける等メモリの使い勝手を飛躍的に高める。 この対応付けはページテーブル(page table)と呼ばれるデータ構造によって行われ、ページサイズ(page size)の単位で行われる。 主記憶上のページテーブルから変換ルールを読み出すのをテーブルウォーク(table walk)と呼ぶ。 このため本来のアクセスに加えテーブルウォークのため 2 回主記憶にアクセスが必要になり、無駄に長いサイクルがかかる。 この本を読んでると、一難去ってまた一難という感じで次々に課題と緩和策の繰り返しから CPU のありがたみが沁みるよな。

2025-02-01, read count: 1, page: 87 ~ 90

第 6 章 仮想記憶。 TLB(Translation Lookaside Buffer)はページテーブルの一部を高速に主記憶から読み込んでおくためのハードウェアで、テーブルウォークの遅さを緩和する。 ページテーブルと TLB は主記憶とキャッシュメモリの関係に近い。 TLB は主に 4KB のページ単位のため、空間局所性が高ければより発生しにくいが、ミスは発生しうる。これを TLB ミス(TLB miss)と呼ぶ。キャッシュミスよりその頻度は低いが、コストはより高い。 TLB ミスの要因やダメージもキャッシュと同様。 ただしフルアソシティブ(full associtive)の TLB はキャッシュは競合性ミスが発生しない。 TLB は流石に初めて聞いた気がする。ここでも緩和のための仕組みがさらなる複雑さを...

2025-02-02, read count: 1, page: 91 ~ 94

第 6 章 仮想記憶。 仮想記憶のソフトウェア制御は OS の仕事なので(開発者が書く)ソフトウェアで対処できるようなものではない。 それでも TLB ミスはキャッシュミスと共通する点(初期参照ミス・容量性ミス・競合性ミス)があり同じ手法が有効。 仮想記憶にはアドレス変換の他に重大なダメージをもたらすページフォールト(page fault)(disk I/O が発生する)ある。 ここまで来るとソフトウェア的な対策は一定程度可能とはいえ CPU 毎にも異なるからどうしようもない感出てくるな。

2025-02-03, read count: 1, page: 94 ~ 100

第 7 章 I/O。 本書では CPU の外部デバイスの内主記憶を除くデバイスへの操作を I/O アクセスと呼ぶ。 I/O アクセスはメモリのように見せかけるメモリマップド I/O(memory-mapped I/O)とデバイス専用アドレス空間を用いる I/O アドレス空間(I/O address space)を用いる I/O 専用命令がある。 I/O アクセスにより、デバイスへの指示(I/O デバイスへの書き込み)、状態の取得(I/O デバイスからの読み込み)、ネットワークからの受信とかディスクへの書き出しといったデータ転送(I/O デバイス→レジスタ→主記憶の転送)といった操作が実現できる。 この章は I/O bound の話なので多少イメージつきやすそう。逆に今までよく掘り下げずに来たなという自戒...

2025-02-04, read count: 1, page: 101 ~ 106

第 7 章 I/O。 I/O デバイスはコストと消費電力の観点から CPU に比べると動作周波数が低いため CPU から見て遅い。 I/O バスもそれ同様なのと、多数のデバイスを識別する新規デバイスへの対応、動的な着脱、バスの規格やプロトコル・複数のバスをまたぐことで、遅い。 また I/O デバイス自体がキャッシュ・バッファ・プリフェッチといった高速化手法を使えず、遅い。 これらの特性は汎用的な対処が難しいので CPU 的に割り込み要求(interrupt request)、 CPU を介さずメモリ間でデータ転送する DMA(Direct Memory Access) といった I/O アクセス自体を減らす仕組みがある。 CPU によっては I/O アクセスを制御する命令、 I/O デバイスから主記憶に直接アクセス可能、 I/O デバイスと CPU が L3 キャッシュを共有するなどの工夫もある。 I/O デバイスの遅さを緩和するためなら何でもやるなという印象。

2025-02-05, read count: 1, page: 106 ~ 111

第 7 章 I/O。 ソフトウェア的な I/O デバイスの遅さを緩和する方法は基本的に I/O アクセスの回数を減らす方法。 I/O デバイスへのアクセスをページキャッシュ・バッファキャッシュで減らす、また 1 回の I/O アクセスにまとめる等。 ただし I/O デバイスへのアクセス回数の減少はそのまま応答性の劣化につながると。ここでいう応答性はリアルタイム性能？ 計測実験は RTC(Real Time Clock) と PCI Express 。 I/O なくしてソフトウェアは成り立たないのでなくすことはできないが緩和策を使ってうまく付き合おう、というわけか。悩ましいな。

2025-02-06, read count: 1, page: 111 ~ 118

第 8 章 システムコール、例外、割り込み。 分岐命令の他に命令流の特別な切り替えが存在する。それらの呼び方や定義は CPU によってまちまちなので、本書では例外・割り込み系と総称する。 システムコール(内部的に特権レベルの変更命令で明示的に発生)、例外(内部的に命令実行時のエラーなどハードウェアが検知し暗黙的に発生)、割り込み(外部的要求により発生)の 3 つに分類する。 発生頻度が比較的稀であること、ソフトウェア的な観点で対策が難しく、もっと低いレイヤでの対応が主。 この図がわかり良いよな言葉に出来ないけど。発生する場所とか考えたことなかった。

2025-02-07, read count: 1, page: 119 ~ 122

第 8 章 システムコール、例外、割り込み。 システムコールは、デバイスへのアクセス要求・メモリ割り当て等で利用される。専用の命令で発生しレベル変更と命令流切替を行う。戻るためにも専用の命令を実行する。 システムコールの特権レベル(privileded level, 例外レベル exception level とも)には最も制限された user level と広いアクセスが許可された supervisor level(kernel level/OS level とも)、仮想化を支援する hypervisor level 等がある。 例外は、ゼロ除算やアクセス違反など命令を続行できないケースをハードウェアが検知して発生する。これにより異常が生じてもシステムを健全に保てるようにする。 割り込みは CPU 外部からの要求をまとめる割り込みコントローラが割り込み要求をして CPU にとって非同期に発生する。 教科書的に覚えるゾーン。

2025-02-17, read count: 1, page: 122 ~ 127

第 8 章 システムコール、例外、割り込み。 これらの挙動は CPU のパイプラインの挙動に似て、事象の発生で命令フェッチが始まる。切替先命令列を handler と呼ぶ。 handler の先頭アドレスは vector table からロードされ、 PC レジスタに書き込まれ、命令フェッチが始まる。 命令流の切替は特権レベルも伴い、多くはユーザレベルから上位へ遷移するが、そのままの場合もある。 これらの処理が終わると元のソフトウェアの命令に戻る。戻り先やレベルは一般的に CPU が自動的に専用のレジスタへ保存する。 切替後の振る舞いは事象によって異なり、例えば例外では元の命令流をキャンセルする必要があり、割り込みでは要求が受け入れられなかったりする。 これらは、一般的に分岐予測の対象しない、特権レベルの変更と handler から戻るときに逐次的実行が必要になる(アウトオブオーダー実行できない、パイプラインを空にする(pipeline flush))、 vector table , handler の分岐予測ミス・キャッシュミス・ TLB ミス、といった通常の分岐命令との違いで遅くなる。 どんだけ遅くなる要素があるねんという気がしてきた...

2025-02-18, read count: 1, page: 127 ~ 132

第 8 章 システムコール、例外、割り込み。 頻度が稀であるのと、 CPU 毎による差異、対処にシステムレベルの対応が必要なためソフトウェア的にできることは少ない。 システムコールの呼出回数を減らすためのバッファリングや一部の命令をユーザーレベルで実行。 例外では性能課題になりうるページフォールトがあるが、命令流切替と相対して小さいので割り切ってもよい。 割り込みは発生頻度を抑えることで改善できるが、その場合デバイスの応答性を下げるトレードオフになる。 最後は実験。ゼロ除算が Linux の場合整数と浮動小数点を SIGFPE 荷集約して区別しない場合があるの初めて知った。

2025-02-19, read count: 1, page: 133 ~ 140

第 9 章 マルチプロセッサ。 multiprocessor は 2 つ以上の CPU を持つハードウェア形態。 CPU パイプライン観点では命令流を増やすことで命令流の密度を高める。 ざっくり様々な形式がある。異種・同種の CPU による構成、 SIMD 型・ MIMD 型、集中共有メモリ型(UMA 型)・分散共有メモリ型(NUMA 型)。 つまり最近の Ryzen AI 9 HX 370 なんかは異種の構成か。heterogeneous multiprocessor という。 MIMD(Multiple Instruction stream, Multiple Data stream)型 は各 CPU が個別の命令流を、 SIMD(Single Instruction stream, Multiple Data stream)型は同じ 1 つの命令流を処理する(SIMD 命令とは別)。 SIMD 型は PC レジスタを共有し命令制御のハードウェアを共通化できるため規則的な大量データ処理に向き、 GPU で使われる。 共有メモリ型(Shared Memory Architecture)は各 CPU でメモリアドレスを共有する。 集中 UMA(Uniform Memory Access)と SMP(Symmetric Multiprocessing)はメモリアクセス時間が一定で、分散 NUMA(Non-Uniform Memory Access)はメモリアクセス時間に差が出る。 メモリアドレスを共有しない構成は、メッセージ交換型(Message Passing System)、私有メモリ型(Private Memory)、 NORMA(NO Remote Memory Access)、分散メモリ(Distributed Memory)型等。 近年主流の MIMD 型かつ共有メモリ型の採用は、ハードウェアの実装効率や性能向上よりもソフトウェアの実装が容易な構成に寄せてると。なるほどなー、それだけソフトウェア実装も大変なんやろう。

2025-02-20, read count: 1, page: 141 ~ 149

第 9 章 マルチプロセッサ。 自動並列化コンパイラは研究されているが、現状では開発者がソフトウェアを並列・並行化しなければマルチプロセッサを活かせない。 並列化は OpenMP, MPI, oneTBB 等のライブラリ、並行化は pthread(native thread), goroutine(M:N mapping), Erlang のプロセス(これは何分類？)等。 各 CPU で動くソフトウェアを「協調」させるために、 mutex, semaphore, バリア同期、条件変数、 event, signal 等の「タイミング調整(同期)」、 mailbox, channel, 共有変数等の「データ送受信」のを利用する必要がある。 プロセッサ的には同期もデータ送受信で実現している。 共有メモリ型・メッセージ交換型で仕組みが異なり、後者はつまるところ CPU 同士の I/O であり、使い勝手が良い前者の共有メモリを利用する方法が現代では一般的。 ただし協調のための仕組みがキャッシュコヒーレンス、メモリ順序付け、不可分操作に関係する性能劣化を引き起こす。 ソフトウェア周りは概ね分かるがバリア同期、条件変数は何のことかわからなかったので宿題。地味に並列化もやったことない。 いずれにせよ共有メモリ型のプロセッサは代償を払ってるのねというのを知れた。

2025-02-21, read count: 1, page: 149 ~ 156