Open5

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

snowindysnowindy

2章まで。
CPUの高速化について話している。

パイプライン化

CPUが"命令流"をさばくために「命令フェッチ」「命令デコード」「命令実行」などのステージを準備している。

命令をDRAMなどから取ってきて、バイト列をCPUが分かる形に解釈し、実行する。

add(fetch)→add(decode)→add(run)→mov(fetch)...

とやるのではなく、

add(fetch)→mov(fetch)→...
(   休止   ) →add(decode)→mov(decode)→...
(   休止   ) → (   休止    )  →add(run)   →mov(run)→...

としたほうが早いということ。

fetch / decode / run などはそれぞれ別の部分の回路が担っているので、並列に動かせるのだ。

補足

並列による弊害として、前の命令が失敗した場合、後述の命令は確実にキャンセルしないといけないという制限が起こる。

キャンセルの制御は非常に難易度が高いらしく、Meltdownとかもその部分が原因だそうだ。

スーパースカラ化

スカラ(+)ということなので、一度のクロックサイクルに、2つ以上の命令をフェッチ・デコード・命令実行するというもの。

add(fetch)→...
mov(fetch)→...
(   休止   ) →add(decode)→...
(   休止   ) →mov(decode)→...
(   休止   ) → (   休止    )  →add(run)...
(   休止   ) → (   休止    )  →mov(run)→...

こういうこと。
そんなのあり?って感じだが物理的に2つ処理できるところをおけばできるそうだ。
相互制御やキャンセルがより複雑になるらしいので大変。

スーパーパイプライン化

これ実質パイプラインと何も変わらないんですが、パイプラインのステージが超多いとこれになるらしい。

snowindysnowindy

3、4章。上記だけでは解決できない命令を "詰める" 手法を述べている。

データ依存関係

データの依存関係?なにそれと思っていたが

mul x1, x23, x24 (x1がdst)
add x25, x26, x1

という命令流があった場合

mulの結果がx1に入ってからじゃないとaddの変数として使えないよね?という話。
確かに。他にも色々あるのだが割愛。

これのせいでせっかくスーパースカラ+パイプラインにしても、mulの命令実行をaddの命令実行が待たないといけないことになる。(mulの命令実行が10サイクル必要な場合、addや後続も同様に10サイクル待たされる

それを解決するのが後述のアウトオブオーダー実行である。

アウトオブオーダー実行

文字通り、命令の順序を無視して実行するというもの。
そんなんあり??という感じだが可能。

具体的には、add 以降の、データの依存関係が無い命令を先に実行する。

1 mul x1, x23, x24 (x1がdst)
2 add x25, x26, x1
3 mul x2, x3, x4
4 add x5, x6, x7

3, 4の命令はデータ依存関係が1, 2とは無いので先に実行してもあとに実行しても結果が変わらないということがわかる。
1 → 3, 4 → 2という順序で実行するのだ。

これだけでは細かい問題が起きるので、命令コミットステージを最後に用意しリオーダー
逆の依存関係(=アウトオブオーダーしたことによる見かけだけの依存関係)を解消するためのリネームが必要になる。

それぞれ、リオーダーバッファ、リネーム用のレジスタが命令数分必要になる。

ループアンローリング最適化

forループといえばjmp命令だが、jmp命令を待たずに次のループのデータ依存関係のない命令を先に実行できるはず。
それを実行することで最適化できる。

条件分岐による損失の緩和

先に条件分岐を示唆する命令の実行、条件分岐を予測する、などの方法でキャンセルを減らす努力をしている。

snowindysnowindy

5章。

キャッシュ

DRAMへのアクセスは 10 ~ 100サイクル程度必要。
秒にすると 数十ns くらい。

クソ早いがCPU的には超遅い。

そのために、命令フェッチ(DRAM→CPU)とデータストア(CPU→DRAM)の両方の前段にそれぞれ命令キャッシュデータキャッシュを置く。
取得と書き込みはまずはこれら2つに行う。

命令キャッシュについては、一般的なキャッシュと同じ用法と考えてもらって良い。

データキャッシュについては、ライトバックという方法を用いており、キャッシュとDRAMで不整合が出ないようにdirtyフラグで管理してあとでDRAMに書き戻す。

キャッシュレイヤ

キャッシュはL1とL2などレイヤー構造になっていることが多い。

CPU ⇔ L1 (命令/データ) ⇔ L2 ⇔ 主記憶

といった構造。

主記憶はDRAMが使われているが、L1, L2はより速いSRAMが使われている。高価。
どれくらい速いかという1回のアクセスが 100ps(0.1ns) とかのレベル。

L1は数十KBが限界ぽい。(わかりやすく言うと、二分木探索15回程度で1サイクルかかるため、インデックス 2^15 ~ 32K 前後が限度)
L2はちょっと遅くてもいい(10サイクルとか)ので、1MBほど可能。

L1にサイズ的に入らないデータがあれば、直接L2に書き込むこともある。

L1に書き込んだものは、L2にライトバック、その後主記憶にライトバックされる。(ライトバックキャッシュポリシー
L1から直接主記憶に書き込むものもあるが(ライトスルーキャッシュポリシー)ライトバックのほうが効率的のため基本的に採用されない。

アソシティブ、アソシエティビティ

二分木探索するより、インデックスを貼ったほうが速そうなのは直感と同じ。値の一部と一致するインデックスを貼り、それで探索するようにする(セットアソシティブ方式

また、アソシエティビティ(連想度, way数)という概念もあり、同じindexでway数分のエントリの保存ができるようにするものが一般的である。

snowindysnowindy

6章は仮想記憶周りについて。

ページ

Pagination Faultとかで聞くやつ。
ページとは、メモリ上の一部の領域である。
現在のCPUだと1ページが4KB程度の領域として設定されている事が多い。

アドレス変換

とっても大事。

主記憶の物理アドレスをそのまま使っていると、断片化したり、主記憶容量が限界になった際にどうしようもなくなる。
物理アドレスを仮想アドレスに変換して使えるようにすることで、上記の問題が解決する。

メリットは以下。

  • メモリ0番から始まるプログラムを干渉無しで並列で動かせる
  • 主記憶容量が圧迫したら余剰データを2次記憶(HDD, SSD)に配置できる
  • 不連続な物理アドレスを連続した仮想アドレスとして使用できる

ページテーブル

アドレス変換にはページテーブルが用いられる。

キーバリューで仮想←→物理アドレスを紐づける。サイズが大きくなる都合上、階層構造になっていることが多いらしく、実際に変換するには複数回のアクセスが必要である。(テーブルウォーク)

ページテーブルはMB級にデカく、主記憶に置かざるを得ない。
また、アドレス変換部は主にCPUとキャッシュの間に置かれる。物理アドレスでキャッシュしたほうが共有キャッシュとして有効だからである。

以上2点より、**キャッシュ上の主記憶のデータを取得するために、まず主記憶のアドレスを主記憶から取得する(???)**という状態になる。

それを避けるために、TLBが存在する。

TLB

Translation Lookaside Buffer : 変換テーブルなめ回しバッファ。

データキャッシュよりもページテーブルのキャッシュに特化させているキャッシュで、
テーブルウォークのタイミングで周りのアドレスとまとめてTLBにコピーしておく。

TLBはデータ用、命令用と分かれていて、それぞれにL1, L2が存在する。(L2は統合されていることも)
データと命令で置き場所が違うから、分離しているのは自然。

TLBのキャッシュミスは複数回の主記憶アクセスが必要になるためダメージが大きいが、ページ(4KB)単位のキャッシュを行っているため、キャッシュミスすることはほとんど無い。実装が悪いとキャッシュミスが頻発することもあるので気をつける。

ページフォールト

めちゃくちゃつらいやつ。
違反の方ではない。

TLBや主記憶になく二次記憶にページがあった場合。
この場合は人間が認識するレベルで遅れる可能性あり。
必要であれば仕方ないが意図的でないページフォールトは避けたい。

snowindysnowindy

7章

I/O

CPUがその周辺機器同士と通信するときのお話。
CPUが主人公なので、I/O readは周辺機器から読み出す、I/O writeは周辺機器に書き込む。

今回I/Oデバイスは主記憶とはまた別の、二次記憶やマウスやキーボード、ディスプレイなどを指す。

I/Oのアクセス方法としては、
memory-mapped I/O と port-mapped I/Oがあるようです

memory-mapped I/O

通常のメモリアクセスのようにI/Oデバイスにアクセスする。
つまり、

mov rax, [r12]
mov [r12], rax

のように普通に memory accessすればいい。
ARMなどRISC系のアーキテクチャはこの方式。

port-mapped I/O

メモリ空間と別にI/Oアドレス空間が存在し、そこにアクセスするには特別な命令が必要になる。

in eax, dx
out dx, eax

x86で使われている。

I/O アクセスは遅い

遅い。イメージ通りではある
read / write ともに 100 cycle~かかる。I/Oの性質により、キャッシュなどが使えなかったり、そもそも周波数が低い