CPU | Notion

ポイント

1クロックの命令を $10^9$ 回実行すると、0.3秒くらいかかる。
メモリ確保は O(1) だけど100クロックくらいかかってとても遅い

CPU情報の取得

cat /proc/cpuinfo

AtCoder環境

CPU: Ice lake
クロック周波数: 3.5GHz

CPU命令

CPU の各種命令のクロック数などがわかるサイト: https://www.uops.info/table.html

サイトの見方
- M16 は Memory から 16bit , R16 はレジスタから16bit という意味
- Lat は Latency
  - 命令を発行してから完了するまでのクロック数
- TP は Throughput
  - 同じ命令を続けて発行するときに待つクロック数
  - 参考: CPUのレイテンシとスループット
- (一般にスループットと言ったら、単位時間あたりに処理できる量を表す。一般的なスループットとCPUのスループットは違うので注意)

代表的な命令とその Latency と Throughput (すべて64bit レジスタ上での計算)

命令	意味	Latency	Throughput
MOV	代入	1	0.25
ADD	足し算	1	0.25
SUB	引き算	1	0.25
IMUL	掛け算	4	1
IDIV	商とあまり	18	10
AND	論理和	1	0.25
OR	論理積	1	0.25
XOR	排他的論理和	1	0.25
SHR	右シフト	1	0.5
SHL	左シフト	1	0.25
NOT	否定	1	0.25
ADDSD	浮動小数点足し算	4	0.5
MULSD	浮動小数点掛け算	4	0.5
POPCNT	popcount	3	1

ALU が4つあるから足し算などの TP が 0.25 になっている？

32bit にしても ADD などのクロック数は変わらない。IDIV とかは変わる。

コンパイル結果が見れるサイト: https://godbolt.org/
- Rust リリースビルド用のオプション
```
-C opt-level=3  --emit asm -Cllvm-args=--x86-asm-syntax=intel --crate-type rlib --color=always
```
  - cargo build —release では opt-level=3 でコンパイルされる
アセンブリの命令が調べられるサイト: https://www.felixcloutier.com/x86/
コンパイルの最適化例
- 2べきの掛け算割り算はビット演算に最適化される
  - わざわざ自分でシフト演算を書かなくてもよい。
- 998244353 などの定数の mod は実際には除算命令は呼ばれず、シフト演算・掛け算・引き算などで行い、クロック数が削減されている。
AtCoder 環境では 3.5GHz なので、1クロックの命令を10^9回実行すると大体0.3秒掛かる。
具体例
- for 文で10^9 回割り算（並列化可能）をしたら何秒かかる？
```
// C++ の場合
for(i=1; i<=N; i++) s+= N/i;

// Rust の場合
(1..=n).map(|i| N/i).sum()
```
  - レジスタの 32bit 除算のスループットが6クロックなので、(10^9×6)/(3.5×10^9) = 1.714秒くらい。
- 4×10^16 + 63 (素数) の素数判定は何秒？
  - 素数判定では $\sqrt{N}$ 回割り算をする。
  - 64bit整数の割り算のスループットは10クロック
  - つまり、10×(2×10^8)/(3.5×10^9) = 0.571 秒くらい
- p=998244353 のとき、(p-1)! mod p を愚直に計算したら何秒？
  - 並列化はできない。掛け算のLatency が 4 クロックで、割り算の Latency が 18クロックだから、(4+18)×99844353/(3.5×10^9) = 6.27秒 …...ではない。
  - 実際に実行すると3.58秒くらいになる。(コンパイル結果のアセンブリでは割り算は使われずに他の軽量な命令が使われる）
  - Rust のサンプルコード

ポイント

CPU情報の取得

CPU命令

パイプライン・分岐予測