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

第 10 章 キャッシュコヒーレンス。 共有メモリ型のマルチプロセッサシステムで個々の CPU が持つキャッシュに書き込んだ値を適切に他の CPU に伝える仕組みがキャッシュコヒーレンス制御。 coherence とは「最新の値が読み出されること」。 ハードウェア的に解決する方法としては CPU の状態を除き見する snoop 方式と共通のテーブルで管理する directory 方式がある。プロセッサ数が多いと後者が用いられる傾向があるが 1 回あたりの処理性能は前者が優る。 スヌープ方式には書き込み時に他のキャッシュを無効化する write invalidate と他のキャッシュにも書き込む write update があり、前者が主流。 write invalidate の主流プロトコル MSI では無効化されたキャッシュの次に他の CPU のキャッシュを取得するため CPU 間の通信が発生する。 キャッシュが無効化されることで他の CPU で必ずキャッシュミスを起こす。これを coherence miss という。 また false sharing と呼ばれる、異なる CPU が同じキャッシュラインを使うことで本来は関係ない箇所でキャッシュミスが発生する問題もある。 false sharing やばいな...こんなん padding で回避とか？限界がある気がするけど。

2025-03-05, read count: 1, page: 157 ~ 169

第 10 章 キャッシュコヒーレンス。 ソフトウェア的には汎用的な対策は難しい。 送受信の頻度を下げる、キャッシュライン配置の工夫、 write combine, write gather といったハードウェア的な支援、 NUMA 構成のような CPU のグループ内の通信コストが低くなるような構成がある。 コヒーレンスミスの実験では POSIX thread 間で同一のキャッシュラインに書き込み false sharing を再現。実行する CPU が 1 つの方が速くなる。 低レベルまで降りないと中々実感で来ないけど恐ろしい話や。

2025-03-06, read count: 1, page: 170 ~ 176

第 11 章 メモリ順序付け。 共有メモリ型のマルチプロセッサに於いて、主にメモリアクセスの高速化のために 1 つの CPU から見たメモリアクセスの順序が入れ替わることがある。 この対象となるのは一般的には異なるアドレスへの複数のメモリアクセスのみ。同一のアドレスの場合はデータ依存関係を壊す可能性があるため。 メモリアクセス順序の入れ替えを許可する・しない状況は CPU 各社によって違う。 x86 は控えめで Arm RISC-V は積極的。 メモリアクセスが 1 つの CPU からどう見える化を memory consistency と呼び、いくつかのモデルが定式化されている。 x86 は Total Store Ordering 、 Arm や RISC-V は release consistency 、他にも sequential consistency 、 weak ordering 等がある。 実際のところ、各 CPU のメモリアクセス仕様は定式化されたモデルよりも複雑。 GCC の最適化で命令の並び替えがあったと思うが、アレの CPU 実行時レベルでのやつかな？

2025-03-07, read count: 1, page: 177 ~ 181

第 11 章 メモリ順序付け。 メモリアクセス順序が変わるメカニズム。 バンク構成≒メモリアクセスを同時処理する領域で待ちが発生したとき。 ストアバッファ(store buffer, store queue, write buffer)の先行処理の滞留。 先行する処理でキャッシュミス、後続する処理でキャッシュがあるようなとき。 複数の CPU の組み合わせで異なるメモリアクセス順序になると偶発的なソフトウェアの不具合の原因になる。 この不具合となり得る状態は非同期なプログラムでもよくあるから感覚はつかめるよな。

2025-03-08, read count: 1, page: 181 ~ 187

第 11 章 メモリ順序付け。 メモリ順序付け命令で memory ordering instruction (memory barrier instruction, memory fence instruction とも) で必要な箇所でメモリアクセスの順序を強制する 双方向(ロードのみ、ストアのみ、全て)・単方向の種類がある。 x86 には単方向がない。 単方向では acquire release があり、これにより保護したい区間の順序を保持しつつ、区間外からの入れ替えを許容してある程度性能劣化を抑制できる利点がある。 ただし順序の強制によって入れ替えが抑制され、命令実行の機会を失うことになる。 はじめの方で学んだ高速化のツケが回ってきてるなという感じがしなくもないが高速化しないと意味ないしなあ。難し。

2025-03-09, read count: 1, page: 188 ~ 194

第 11 章 メモリ順序付け。 性能対策が必要な場合はまずソフトウェア的に正しく動作する前提で、 CPU 命令レベルで対処せず、メモリ順序付けを隠蔽するチャネルなどのソフトウェア機構で対処すべき。 その上で、データ送受信の頻度を下げ CPU 間の送受信を減らす、影響範囲を狭める適切な CPU 命令の選択する。 また x86 はメモリ順序の入れ替えに慎重なため、ソフトウェアを ARM や RISC-V にポーティングする際には注意が必要。 最後にメモリ順序入れ替わりの再現。 Linux Kernel のメモリ順序付けのドキュメントにハードウェア設計者宛の助言(苦言)が書いてるらしいので後で読も。 いわゆる高級言語を使ってると下位 layer に投げっぱなしで触れることないが知れてよかった。

2025-03-10, read count: 1, page: 195 ~ 202

第 12 章 不可分操作。 共有メモリ型のマルチプロセッサでは同一アドレスに対する Read Modify Write で競合が発生、 カウンタのインクリメントや状態の書き換え等でデータの不整合を引き起こす。 この競合を避けるために不可分操作、アトミック操作(atomic operation)で複数のメモリ操作を 1 つの操作として扱う。 不可分操作により、バリア同期(barrier synchronization)、排他制御(mutual exclusion)といった CPU のタイミング調整が可能になる。 かつての CPU はバスロック方式で実現していたが、現在はキャッシュコヒーレンスプロトコルにより実現されている。 不可分命令には、交換(swap)・比較付き交換(compare and swap)・演算()・LL/SC(load linked/store conditional) がある。 このへんは低いレイヤにおける非同期なプログラムの問題そのものという印象。

2025-03-11, read count: 1, page: 203 ~ 221

第 12 章 不可分操作。 不可分操作は共有メモリの同一アドレスへのアクセスを逐次化する為遅い。 また不可分制御はメモリ書き込みを伴うためラインインバリデートが行われ、次の同一アドレスへの不可分制御でコヒーレンスミスが発生し遅くなる。 さらに不可分制御の多くは占有権などメモリの順序関係が重要なため、メモリ順序付けを伴った命令を提供しており、これも遅い。 必要な機構なのでソフトウェア的な緩和策は難しいが、不可分操作の頻度を下げる、協調アルゴリズムの選択(Test and test-and-set 、統計カウンタ、 Read Copy Update)、 適切な不可分命令の利用(といった手段を取れるが、ただし CPU 挙動まで考慮した汎用的対応は非常に難しい。 あとは不可分操作の再現実験。この本の性能劣化の分類としては最後の章なので全部盛りみたいな END GAME 感あった。

2025-03-12, read count: 1, page: 221 ~ 230

第 13 章 高速なソフトウェアを書く際には何に注目すべきか。 ソフトウェア開発において CPU の性能劣化に関して、その発生頻度、損失サイクル、と要因を制御できるかを基準に、著者の主観で分類している。 発生頻度の高い真のデータ依存関係・分岐命令の予測ミス・キャッシュミスは注目すべきだが、ソフトウェアによって I/O やシステムコールの頻度も重要になる。 プログラミング言語によっては VM を介すものなど低レイヤの制御が難しいが、キャッシュミスに対してはデータ構造の設計次第で改善できる可能性がある。 最後に著者の主観での優先順位付けで終わる。 この章の取れる手段はソフトウェア開発で並列処理や最適なアルゴリズム・メモリ構造を選択していればある程度カバーできそう。ただ真のデータ依存関係は低レイヤまで見えるようにならないと難しそう。 あと付録 B 以外読んだら終わり。

2025-03-13, read count: 1, page: 231 ~ 236

付録 A CPU についてさらに広く深く知るには。 書籍・論文・特許・ オープンソースハードウェア・講義資料・特定の CPU の資料などを利用できる。 書籍でいうと、パタヘネが入門、ヘネパタが中級。オープンソースソフトウェアだと RISC-V 。 ヘネパタは積んだまま読めてないけどアレで中級か...とりあえずこの本で多少ハードル下がった気はする。

2025-03-14, read count: 1, page: 237 ~ 246

付録 C 現代的な CPU の実装例(BOOM)。 現代的な CPU 実装例として RISC-V 実装の BOOM(Berkley Out-of-Order Machine)。 最新版 BOOMv3 は MIPS 社 R10000 や DEC 社 Alpha 21264 の影響を受けてる。 命令デコードが 4 、命令実行が 8(浮動小数点 2 、整数 4 、メモリアクセス 2) の並列度を持ち、アウトオブオーダー実行した結果をライトバックステージで並べ直す。 ハードウェア記述言語を使わず Scala の Chisel で記述されているらしいので読んでみるのも良さそう。

2025-03-15, read count: 1, page: 257 ~ 262

付録 D マイクロオペレーション方式とその命令レイテンシ。 CISC 系のように一つの命令をハードウェアの都合の良いように複数の命令ステージに分割するものをマイクロオペレーション方式という。 分割した各々の命令を都合の良いタイミングで実行することを個別発行制御という。 命令が分割されることで、パイプラインの資源不足やデータ依存関係によりレイテンシの揺れがある。 そもそも分割された命令は真のデータ依存関係を有するため、レイテンシが短くなることはない。 こういった複雑な命令体系に対して、 RISC 系ではシンプルな命令体系を採用していると。 人間の把握しやすいレベルにシンプル化しないと高速化もままならんということかな。

2025-03-16, read count: 1, page: 263 ~ 268

付録 E GPU およびベクトル方式におけるパイプラインの高密度化の工夫。 GPU とスパコンのベクトル方式では SIMD 型の命令を採用している。いずれも真のデータ依存関係による機会損失は避けられない。 GPU では空いた機会を細粒度マルチスレッド(Fine-Grained MultiThreading)で埋めることで高速化している。 ベクトル方式では空いた機会を同一ベクトル内の他の要素で埋めることで高速化している。 ループアンローリング最適化で必要な多数のレジスタをベクトルの要素数を増やすことで克服したとも考えることができる。 GPU は CPU より更によく知らんので勉強になるわ。

2025-03-17, read count: 1, page: 269 ~ 273

付録 F CPU の性能向上の物理的な難しさ。 1 つのステージは flip-flop で囲まれた論理ゲートで作り込まれるが、 CPU の動作周期から定まるクロックサイクル内に収まるよう、利用できる論理ゲートの数に制限がある。 また製造品質のばらつきや実行環境の変化に対応させるためにクロックサイクル丸ごとを論理ゲートに費やせない。 また論理ゲート自体にも制限がある。大きな論理ゲート、多くの論理ゲート、遠くの論理ゲートへの信号は遅くなる等。 論理ゲートより下位だと電子レベルの特性で遅くなるなど。 知らないことだらけだが物理的な影響がこう繋がってくるねんなという感想。

2025-03-18, read count: 1, page: 274 ~ 280

あとがき、参考文献、索引など。 情報処理技術者試験レベルしか把握してなかったから CPU に対する解像度が上がり、以前の何も知らなかった頃には戻れなくなった感じがする。 この流れでパタヘネ、ヘネパタも読めればよいが。 あとがきに出てくるラム社の本はいくつか読んだし改めて読み直すもよいか。

2025-03-19, read count: 1, page: 281 ~ 300