第1章 CPUは如何にしてソフトウェアを高速に実行するのか
序文
ソフトウェアのめざましい進化が十分に進歩した技術の中核となっている。そしてそのソフトウェアは計算機(ハードウェア)の上で動いている。 CPU(Central Processing Unit)には50年以上の歴史があり、たくさんの研究者や技術者の創意工夫によって作られてきた。 その構造や動作は非常に複雑であるためか、ソフトウェアプログラマは詳細を知らないことも多い。
本書は、ソフトウェアを高速化するために CPU について知りたいプログラマに向けて書かれた。 そのアプローチは、「命令の流れ」や「クロックサイクル粒度のミクロな振る舞い」に着目して各要因ごとに分解して提示することで CPU の性能についての原理を説明した上で、各種の CPU に共通する高速化のための知見を獲得する、というものである。
Note
Any sufficiently advanced technology is indistinguishable from magic.(十分に発達した技術は魔法と区別がつかない)
余談
J. L. Hennessy and D. A. Pattersonによる、『コンピュータアーキテクチャ 第 6 版 定量的アプローチ』(エスアイビー・アクセス, 2019)という本がある。 この本は、CPUやGPUのマイクロアーキテクチャに関するもので、非常に有名である。 が、難しいのとかなり分量がある。 みやじまも学生のころに輪講して、非常に難しかった思い出がある。いつか輪講できるようになるといいな。
第1章
CPUの性能とは?
本書では、以下の式で表されるCPU時間が短いことをCPUの性能が良い、と定義する。 ここでは、CPU時間は処理にかかる時間と同義。
各値は、それぞれ以下のようなもの
- 実行命令数:アセンブリコードの行数と同義で、プログラムの書き方やコンパイラの善し悪し、CPUの命令セットアーキテクチャに左右される。
- プログラム:プログラムサイズやプログラムの行数と同義で、プログラマの能力やプログラムの書き方に左右される。行数が少ないことが常に良いとは限らないが、CPU時間の観点では少ないことが良い。
- クロックサイクル数:動作周波数と同義で、CPUで3GHz程度、GPUで1.5GHz程度。消費電力の都合でここ10年くらいはあまり動作周波数は上がっていない。ほぼ固定値
- 秒数:CPUを地球で動かしているかぎり普遍なので、一般人にはどうしようもない
各項は、それぞれ以下のように説明できる。
- 第1項目:CPU時間におけるプログラムサイズと実行命令数の影響を示した項。コンパイラやソフトウェアの書き方、命令セットアーキテクチャに左右される。どちらかと言えばソフトウェア的な部分。
- 第2項目:CPU時間における実行命令数の影響を示した項。CPUのマイクロアーキテクチャ(micro-architecture)と、それをどう使うかに左右される。本書が対象としている部分。
- 第3項目:CPU時間における動作周波数の影響を示した項。どちらもほぼ固定値なので、結構どうしようもない。半導体プロセスや回路実装技術によって左右される。物理設計の部分。
1.1 CPUはソフトウェアを「命令流」として見ている
人から見たソフトウェアとCPUから見えるソフトウェアは異なる。
- 人から見たソフトウェア:C、Ruby、Python、JavaScript、Java、Goなどの人間が記述することを前提としたさまざまなプログラミング言語
- CPUから見えるソフトウェア:アセンブリコードやマイクロコードなどの命令列や、それを時系列に処理する命令流。CPUは、命令を順番に並べたものに基づいてデータの読み書きと加工を行う機械だと言える。
具体的例:二乗するC++プログラムと、そのアセンブリコード。Compiler Explorerで、x86-64向けGCC 14.2でコンパイルした結果。
-
人から見たソフトウェア
1 2 3 4 5 6 7 8 9 10
#include <iostream> int square(int num) { return num * num; } int main(void){ int squared_value = square(2); std::cout << (squared_value); }
-
CPUから見えるソフトウェア。上から順番に処理するので、時系列に処理する命令流。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
square(int): push rbp ; 現在のベースポインタをスタックに保存 mov rbp, rsp ; スタックポインタをベースポインタにコピー mov DWORD PTR [rbp-4], edi ; 関数の引数(整数)をスタック上のローカル変数に保存 mov eax, DWORD PTR [rbp-4] ; ローカル変数の値をeaxレジスタにロード imul eax, eax ; eaxレジスタの値を自分自身と掛け算(平方計算) pop rbp ; ベースポインタを復元 ret ; 関数から戻る main: push rbp ; 現在のベースポインタをスタックに保存 mov rbp, rsp ; スタックポインタをベースポインタにコピー sub rsp, 16 ; スタックに16バイトの領域を確保 mov edi, 2 ; ediレジスタに整数2をセット(square関数の引数) call square(int) ; square関数を呼び出し mov DWORD PTR [rbp-4], eax ; 関数の戻り値をスタック上のローカル変数に保存 mov eax, DWORD PTR [rbp-4] ; ローカル変数の値をeaxレジスタにロード mov esi, eax ; eaxレジスタの値をesiレジスタにコピー(出力用) mov edi, OFFSET FLAT:std::cout ; std::coutのアドレスをediレジスタにセット call std::ostream::operator<<(int) ; std::coutに整数を出力する関数を呼び出し mov eax, 0 ; プログラムの戻り値を0にセット leave ; ベースポインタを復元し、スタックポインタを調整 ret ; main関数から戻る
ここから言えることは、
Note
この命令流を高速に"処理"すれば、それだけCPUでソフトウェアを高速に実行できる。具体的には、結果が破綻しないように、命令流や命令列の順番を変更したり、並列に実行したりすることでCPU時間を短縮していく。各命令列は依存関係があったり、それぞれ実行時間が異なるため、これらを考慮して順番を変える必要がある。
1.2 CPUごとにどのような命令があるか
命令セットアーキテクチャ(ISA: Instruction Set Architecture)とは、CPUから見えるソフトウェア、つまり、命令の集合を定義したもの。 ISAはCPUとプログラムの間の境界であり、以下のような要素が含まれる。また、CPU時間や互換性に大きな影響を与える。 ISAはマイクロアーキテクチャとは分離されており、IBM社のSystem/360でこの考え方が導入され、互換性の向上に寄与している。
- 命令形式: 各命令がどのようなビットパターンで表現されるかを定義する。オペコード(操作コード)やオペランド(操作対象)が含まれる。
- 命令の種類: 算術演算、論理演算、データ転送、制御フローなど、プロセッサが実行できる基本的な操作を定義する。
- レジスタセット: プロセッサが持つレジスタの数と種類を定義する。
- アドレッシングモード: メモリ内のデータにアクセスする方法を定義する。直接アドレッシング、間接アドレッシング、インデックスアドレッシングなどがある。
- データ型: プロセッサが扱えるデータの種類(整数、浮動小数点数、文字列など)を定義する。
現在の代表的な命令セットアーキテクチャは以下の3つ。 CPU ごとに詳細な命令セットアーキテクチャの仕様は異なっているものの、いずれも同程度の粒度の命令を持つに至っている。
- Intel/AMD x86:Intel社の「Intel 64 and IA-32 Architecture仕様」、および、AMD社の「AMD64 Architecture 仕様」
- Arm v8 AArch64:Arm 社の「Arm Architecture A-profile 仕様」のうち、64 ビット CPU 向けのAArch64 仕様で、中でも現在広く普及している v8 以降のバージョン
- RISC-V RV64I:RISC-V International が定義する「RISC-V 仕様」のうち、64 ビット CPU 向けである RV64I 仕様
命令 | Arm v8 AArch64 | RISC-V RV64I | Intel/AMD x86 |
---|---|---|---|
転送 | mov x5, x6 |
mv x5, x6 |
mov rax, rbx |
加算 | add x5, x6, x7 |
add x5, x6, x7 |
add rax, rbx |
比較 | cmp x6, x7 |
slt x5, x6, x7 |
cmp rax, rbx |
無条件分岐 | b target |
j target |
jmp target |
メモリ読み出し(ロード) | ldr x5, [x6] |
ld x5, (x6) |
mov rax, [rbx] |
メモリ書き込み(ストア) | str x5, [x6] |
sd x5, (x6) |
mov [rbx], rax |
二乗するC++プログラムのARM64向けアセンブリコード。Compiler Explorerで、ARM64向けGCC 14.2でコンパイルした結果。 x86向けのアセンブリコードとちょっと違う。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1.3 CPUで人から見えるソフトウェアをそのまま扱っていない理由
現代のCPUは、命令列を「1. 小さな命令の並び」を「2. 時間軸に沿って順番に実行する」という原理で動作するものが主流である。 これは、そのほうが汎用性が高く、高速化や小型化にも向いているからである。 もちろん、FPGAやCGRAなどCPUとは異なる動作原理を持った計算機も存在するが、主流とは言えない。
- 小さな命令の並び
現代のCPUは単純で小さな命令を組み合わせるアプローチで、ハードウェア(電子回路)の制御構造や規模を抑えながら、さまざまなプログラミング言語の機能を実現している。 例えば、ループ文は、CPUがループ文命令を持っているわけではなく、ループの終了を判定するための「比較命令」や、ループの先頭の命令列に処理を戻すための「分岐命令」などを組み合わせて実現されている。 ループ構造を電子回路で実現しようとすると結構たいへん。
1 2 3 4 5 6 7 8 9 10 11 |
|
for文はjmp
命令で実現される
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|
- 時間軸に沿って順番に実行する
コンパイラは処理したい順番に命令を並べた命令列を生成し、CPUはそれを順に実行する。 ループやジャンプ、関数呼び出しなど、並んだ順番以外の命令を実行したい(命令の流れを変更したい)場合には、変更先の命令列の先頭を明示的に指定する命令を作成・実行する。 この単純な方式は、特別な指示がない限り記述順序で後続の命令を次に実行すればよいことから、命令流を高速に処理するうえで著しく有利である。
1.4 プログラムはどのようなCPUの命令列に変換されるか
Compiler Explorerを使わなくても、コンパイル系の言語では命令列を出力できる。
- GCCの
-S
オプションでアセンブリ(.s
ファイル)を生成して見てみる
Stop after the stage of compilation proper; do not assemble. The output is in the form of an assembler code file for each non-assembler input file specified.
By default, the assembler file name for a source file is made by replacing the suffix .c, .i, etc., with .s.
Input files that don't require compilation are ignored.
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0でやってみると
1 |
|
二乗するプログラムのアセンブリコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
|
- 実行ファイルを逆アセンブル(機械語やバイナリを、アセンブリに変換)する。
objdump displays information about one or more object files. The options control what particular information to display. This information is mostly usefl to programmers who are working on the compilation tools, as opposed to programmers who just want their program to compile and work.
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0でやってみると
1 2 |
|
二乗するプログラムの逆アセンブル結果
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 |
|
アセンブリコードの出力は、インタープリタ方式や JIT コンパイル方式、バイトコードへのコンパイル方式などを採用している処理系では通常は行えません。