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

ピン留めされたアイテム

以下の書籍の学習ノート。
プログラマーのためのCPU 入門 CPU は如何にしてソフトウェアを高速に実行するか

 CPU時間CPU時間 = CPUの性能。以下の式で表す

CPU時間 = \frac{実行命令数}{プログラム }× \frac{クロックサイクル数}{実行命令数} × \frac{秒数}{クロックサイクル数}

 第1項1つのプログラムを表現するのに必要な命令数
「命令(instruction)」とは、CPUが解釈して実行できる演算やデータの転送などの指令
命令が少ないほど短時間で実行される
この項は以下の要素によっても左右される
コンパイラ(プログラムをCPUの命令に変換する)
ソフトウェアの書き方

命令セットアーキテクチャ
CPUが備えている命令の仕様
同じプログラムでもCPUによって動作が変わる
e.g.) スマホやタブレットで使われるARM、パソコンやサーバーで使われるx86



 第2項CPUハードウェアの内部構造で決まる。
この仕様はマイクロアーキテクチャと呼ばれる。

 第3項半導体プロセス(半導体の製造技術)や回路実装技術によって主に決まる。

Alma

 CISCとRISCx86とarmって何が違うんだ？と思っていたけど腑に落ちた。高速化の方針が違うよう。

 CISC(Complex Instruction Set Computer)1つの命令を高機能にすることで、1つのプログラムに必要な命令数を削減する。
すなわち、第1項を小さくするというアプローチ。
e.g.) x86

 RISC(Reduced Instruction Set Computer)1つの命令を単純にすることで、各命令を短いクロックサイクルで実行できるようにする。
すなわち、第2項を小さくするアプローチ。
e.g.) Arm, RISC-V

Alma

 パイプライン化
 パイプライン方式先行命令の完了を待たずに次の命令を次々と開始する方式
命令はフェッチ→デコード→実行という段階で処理されるが、先の命令を実行完了を待ってから次の命令をフェッチするのでは時間がかかる、そのため、実行し終わる前に次の命令のフェッチを開始しておく。
ただし、このような投機的な処理ではキャンセルが複雑になる。
CPUハードウェア設計ではキャンセルの正しい実装は難しいものであり、バグの温床の1つ。
e.g.) SpectreとMeltdownと呼ばれるセキュリティ課題

参考：CPUの脆弱性「Spectre（スペクター）」と「Meltdown（メルトダウン）」

 スーパースカラ方式物理的に複数のパイプライン資源を用意して命令を並列に処理し、高速化する。
ただし、複数パイプラインの関係を制御するために、CPUハードウェアの設計の複雑さが増す。

 スーパーパイプライン方式パイプラインのステージをより細分化する。
ただし、CPUハードウェアの設計の複雑さが増す。

Alma

 データ依存関係2つの命令が同じレジスタやメモリに対して読み出しや書き込みをするとき、依存関係があると言う。

いくつかのパターンがある。

 真のデータ依存関係先行命令の書き込み結果を、後続命令が読み込む場合

 アウトオブオーダー実行真のデータ依存関係によって失われる命令実行機械の損失を緩和し、埋め合わせるためのハードウェアによる対策。真のデータ依存関係がない別の命令の実行開始を前倒しする。
命令の実行後に再順序化(リオーダー)を行う必要がある。

 ソフトウェアによる緩和レイテンシが長い命令を避ける
e.g.) 除算ではなく逆数にした上で乗算にする

レイテンシが長い命令が先行されるように配置する
真のデータ依存関係のない命令で埋める
ループアンローリング最適化

Alma

 分岐命令分岐を実現するためには、PCレジスタを変更する命令(分岐命令)を使う。
自身が実行されるタイミングで、PCレジスタに対して分岐先のアドレスを伝える。
(分岐命令によって命令実行部から命令フェッチ部へと分岐先のアドレスが供給される)
分岐命令によってPCレジスタの値が変更されると、先行的にフェッチした命令をキャンセルし、その時点から新たな命令流のフェッチをやり直さなければならない。
分岐命令による機会損失のサイクル数は、少なくとも命令フェッチステージから命令実行ステージまでのステージ数に相当する。
また、ハードウェア実装上の課題もある。
命令の記述時点で分岐命令よりも後続の処理はどれも実行を完了させてはならず、先行した命令はキャンセルしてはいけない、などの場合分けはハードウェアの実装が難しい。

 ErrataCPU各社が公開しているCPUの不具合。
分岐命令やキャンセル系のミスが散見される(複雑な条件の実装は難しい)。

 分岐命令の種類無条件分岐命令
指定アドレスを先頭とする命令列に処理を切り替える命令
e.g.) whileループで先頭に戻る

条件分岐命令
条件が成立する場合に指定のアドレスに切り替える命令
e.g.) if文やswitch/case文

コール命令 / リターン命令
コール命令は指定アドレスに処理を切り替えるが、その際に「プログラムの記述順で後続の命令のアドレス」を特別なレジスタに保存しておく。この特別なレジスタに保存されたアドレス(復帰先アドレス)にはリターン命令を呼び出すことで復帰できる。
e.g.) 抽象化した関数、手続きあるいはメソッド

条件分岐命令では、条件が成立しない場合はそのままPCレジスタを更新してプログラム順に命令流の処理を続けるので、無駄な空きサイクルによる性能ダメージを受けない。

 分岐予測実行ステージよりも早いステージで分岐先を予測し、分岐先の命令フェッチ開始を前倒しするというCPUハードウェア上の仕組み。

 ソフトウェアによる緩和分岐命令をなくす
分岐命令の実行回数を減らす
分岐予測の予測精度を高める
e.g. ) 複数の条件分岐命令型中に入れ子で実行される状況では、実行される頻度が高く、かつ分岐方向の偏りが大きい分岐命令をより先に優先的に配置することで、分岐予測が当たる可能性を高くできる場合がある

Alma

 キャッシュメモリメモリアクセスは分岐命令と双璧をなす、ソフトウェアの実行を遅くする要因の一つ。
CPUからDRAM(主記憶)へのメモリアクセスには、サイクル数にして数10サイクルから100サイクル規模の時間が費やされる。そのため、メモリアクセスはパイプラインの工夫による命令流の高密度化を激しく損なう。
そこで、主記憶の一部をコピーして近くに配置することでメモリアクセスを高速化するのがキャッシュメモリ(ただし、キャッシュからの読み出しアクセスにも複数のサイクルが必要)

 キャッシュと主記憶の整合性データのストア時に主記憶ではなくキャッシュのみへ書きこむことで、主記憶との間で値が異なっていく。その不一致を解消するため、キャッシュの値を主記憶に書き戻す操作をライトバックと言う。
ライトバックを効率的に行うため、不一致となったエントリのみにダーティと呼ばれる印をつけてキャッシュを管理する仕組みが一般的に採用されている。ダーティの管理およびライトバックは、いずれもCPUハードウェアが自動で行う。

 キャッシュミスメモリアクセス時にアクセス対象がキャッシュに存在していない状態。
主記憶へアクセスするのはキャッシュへのアクセスより圧倒的に遅いため、性能を著しく劣化させる原因となる。
キャッシュミスの要因は以下の3種類に体系化されている。
初期参照ミス
容量性ミス
競合性ミス

 初期参照ミス初回のメモリアクセス時にキャッシュに値が存在していないこと。
緩和策は「先に持ってくる」こと。ハードウェアには以下のような仕組みがある。

 キャッシュライン
メモリアクセスにおける空間局所性(近くの要素が一緒に使われる可能性が高い)を利用し**、該当アドレスへのアクセス時に近所の値もまとめて一緒にキャッシュへコピーする**こと
Armやx86などのCPUでは64バイト程度が一般的
ただし、以下の問題もある
すぐには使用しない値を無駄にコピーしてしまう可能性があり、キャッシュ容量を圧迫する可能性がある
コピーを行う時間が増加する
主記憶への余分なアクセスが生じる


 プリフェッチ特定のアドレスの要素を主記憶からキャッシュへと先行的にコピーする機能。

 ソフトウェアによる緩和時間的に近いタイミングで使用されるデータを空間的に近い場所、つまり近いアドレスに配置する
配列構造のようなデータに対するアクセスで連続的な添字を利用する
明示的なプリフェッチ命令が使用できないか検討する

 容量性ミスキュッシュの容量には限りがあるので、中身を自動的に入れ替える(リプレースメント)。
追い出されたアドレスはキャッシュに存在しなくなるので、2回目以降のアクセスにも関わらず主記憶へのアクセスが必要となる。
容量性ミスはキャッシュミスの多くを占める要因。
緩和策としては以下がある。

 ハードウェアの大容量化
ただし、キャッシュの容量を主記憶と同程度にすることはできない。キャッシュの物理的な構成要素であるSRAMの速度の壁がある

 キャッシュの階層化
L1, L2のように階層化し、アクセス速度では劣るが大容量にしたキャッシュを中間階層に設ける

 明示的なキャッシュ操作
キャッシュを使用しない(2回以上アクセスしない)ことをヒントとして明示できる命令がある
また、しばらく使用しないアドレス範囲がわかっている場合、それらを強制的にキャッシュから追い出す命令がCPUによっては用意されている

 ソフトウェアによる緩和容量性ミスを上位層のソフトウェアで緩和することは容易ではないが、キャッシュの容量や階層的な構造を意識しながら適宜キャッシュ操作用の命令を使うことで緩和できる可能性がある
e.g.) 巨大な配列などのデータ構造をキャッシュの容量以下のブロックに分割して処理sる

プロセス切り替えの時間を長くする
キャッシュはプロセス間の共有資源であるため、プロセスの切り替えは容量性ミスを誘発する


 競合性ミスアドレスの一部が共通する別のアクセスによってキャッシュが追い出されてしまうこと。

 セットアソシアティブ方式エントリの記録位置に対して、検索キーであるアドレスの一部を、テーブル中の各エントリ位置に対応づけるという制約を設ける。これにより取り出す際に検索対象のアドレスを高速に探し出せるようになるが、共通のアドレスを1個しかキャッシュに記録できないため、インデックスが共通のメモリアクセスが生じるたびに、既に格納されている値が追い出されてしまう。
たとえば、ここでは簡単のために「アドレスの末尾の2桁をインデックスにする」というルールを設けるとしよう。その際にアドレスが「001」と「101」のものは末尾2桁が同じで共通のインデックスの位置に記録されるため、片方にアクセスするたびにキャッシュからもう片方が追い出されることになる。

 連想度1つのインデックスに対して記録できるエントリ数。単位はway
テーブルを多重化することで競合性ミスを緩和できる。
ただし、wayが増えると動作速度が遅くなる。

 ソフトウェアによる緩和インデックスに対応するアドレスのビット位置はCPUにより異なるので、CPUによらない競合性ミスの対策は難しい。
ただし、アドレスの一部が競合するようなメモリアクセスのパターンを避けることで緩和できる可能性はある。
e.g.) wayあたりの容量値と一致するアドレス間隔でメモリアクセスが発生すると、激しい競合性ミスを起こす可能性がある