アーキテクチャシミュレータGem5を使ってみる　その2「OoOを実感する」

# はじめに

アーキテクチャシミュレータ[Gem5](http://gem5.org/Main_Page)を使ってみる。

* [その１](https://qiita.com/kaityo256/items/00fc50221d86ce3ff2ea)　インストールと実行まで
* その2　OoOを実感する

実行環境としては以下を想定している。

* リモート(プログラムのコンパイル環境)： Linux (CentOS + GCC)
* ローカル(Gem5の実行環境)： Mac 

# OoO実行について

OoOとは「Out of Order実行」のことだ。CPUがプログラムを実行する時には、

* Fetch：命令をメモリからとってくる
* Decode: 命令を解釈する
* Issue： 命令を適切な実行ユニットに投げて実行する
* Write Back: 結果を書き戻す

といった順番で実行される。しかし、例えば命令を実行するのに必要なレジスタが他の命令によって使われている時、そのレジスタが使用可能になるまでその命令の実行を待たなければならない。これをストールと呼び、CPUはその分だけ空回りする。

OoOは、「待ち」に入った命令の後に実行可能な命令があれば、それを先に実行してしまうことで、なるべくCPUや演算器を遊ばせない仕組みだ。この様子をGem5を使って見てみよう、というのが本稿の趣旨である。

# Gem5におけるx86のOoOシミュレーションについて

Gem5は、O3CPUというCPUモデルが実装されている。O3は「Out of Order」のことだ。x86命令セットに対応しているが、このCPUモデルはx86ではなく[Alpha 21264を模したもの](http://gem5.org/O3CPU)であることに注意。従って、x86命令をGem5でシミュレートした時、これはx86実機と必ずしも同じ動作をしない。

また、x86では一つのCISC命令を複数のRISC的命令にバラして実行する「μOPS」という仕組みがあり、Gem5はこれをサポートしているため、実行時に一つの命令が複数の命令として実行されているように見える。筆者の知る限り、IntelからμOPSに対する公式なドキュメントは公開されていない。有志による情報としては、以下の二つが有名。

* [Agner FogによるPDF](http://www.agner.org/optimize/instruction_tables.pdf) 様々な石でのx86のレイテンシやスループットを集めた表。x86でチューニングをする人なら一度はお世話になったことがあるはず。μOPSの命令数も書いてある。
* [uops.info](https://www.uops.info/) 命令ごとのμOPSの数がまとめられた表。ウェブで検索できるので便利

# Konataによる可視化

Gem5には、パイプラインを可視化するためのツール`o3-pipeview.py`があり、`trace.out`を食わせて色付きのテキストファイルを出力することができるが、あくまでもビューワがlessなのでいろいろ使いづらい。ここは塩谷さんの[Konata](https://github.com/shioyadan/Konata)というツールを使うのが便利だ。Konataの使い方については[こちらのスライド(PDF)](http://learning.gem5.org/tutorial/presentations/vis-o3-gem5.pdf)が詳しいので一読されたい。

# 最低限のプログラム

Gem5でプログラムを実行する際、普通にCプログラムをコンパイルし、`-static`でリンクしてしまうと、プログラムが大きくなりすぎてしまい、欲しい情報が見づらくなってしまう。例えば「Hello World」を表示するだけのプログラム、

```test.c
#include <stdio.h>

int main(){
  printf("Hello Wordl\n");
  return 0;
}
```

を、普通にコンパイル、リンクしても、大した情報量はない。

```sh
$ gcc test.c
$ objdump -S ./a.out | wc
    182     982    8187
```

しかし、Gem5のために静的にリンクすると、実行バイナリが膨れ上がる。

```sh
$ gcc test.c -static
$ objdump -S ./a.out | wc
 150290 1071310 8097726
```

なんと15万行である。みたいところはほんの数行〜数十行なのに、15万行もあるといろいろ面倒くさい。

そこで、「必要最低限」のアセンブリで実行バイナリを作ってしまうのが良い。

詳しくはtanakmuraさんの[実践的低レイヤプログラミング](https://tanakamura.github.io/pllp/docs/index.html)の[リンカ](https://tanakamura.github.io/pllp/docs/linker.html)の稿を参照して欲しいが、例えば以下のようなプログラムが「Gem5で実行可能な最小のプログラム」である。

```nasm:test.s
  .globl  _start
_start:
  call main
  mov $60, %rax
  syscall

main:
  ret
```

最初のエントリポイントである`_start`で`main`を呼び、`main`は何もせずに`ret`して、最後にプログラムの終了処理のシステムコールをしておしまいである。

ここから以下のように実行バイナリを作る。

```sh
$ as test.s -o test.o  
$ ld test.o
$ ./a.out

```

何もしないプログラムが完成した。実行バイナリも非常に小さい。

```sh
$  objdump -S ./a.out | wc

./a.out:     ファイル形式 elf64-x86-64


セクション .text の逆アセンブル:

0000000000400078 <_start>:
  400078:	e8 09 00 00 00       	callq  400086 <main>
  40007d:	48 c7 c0 3c 00 00 00 	mov    $0x3c,%rax
  400084:	0f 05                	syscall 

0000000000400086 <main>:
  400086:	c3                   	retq
```

これをKonataで可視化しよう。

まずは実行バイナリをローカルに落としてきて、Gem5に食わせて`trace.out`を出力させる。

```sh
$ ./build/X86/gem5.opt --debug-flags=O3PipeView --debug-file=trace.out configs/example/se.py --cpu-type=DerivO3CPU --caches -c ./a.out
```

これにより、カレントディレクトリに`m5out`というディレクトリができて、その中に`trace.out`が出力されるので、Konataを起動してそこにドラッグアンドドロップすると、実行状況が可視化される。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/79744/135df1d6-9326-fab7-72e9-f889cd74a9b8.png)

例えば`callq`はobjdumpにより`400078`にあるが、Konataの可視化でも`0x00400078`にあることがわかる。

ここで、`callq`にあたる「CALL_NEAR_I」が、同じアドレス(`0x00400078`)で、5つの命令として並んでいることに注意。[uops.info](https://www.uops.info/html-instr/CALL_NEAR_M64.html)では4ないし5と書いてあるが、Gem5では5opsを採用しているようだ。

# OoOの確認

## In-Order 実行

さて、早速Out of Order実行を確認してみよう。まずはこんなコードを書いてみる。

```nasm:test1.s
  .globl  _start
_start:
  call main
  mov $60, %rax
  syscall

main:
  mov $1, %rax
  mov $2, %rbx
  mov $3, %rcx
  mov $4, %rdx
  add %rbx, %rax
  add %rdx, %rcx
  ret
```
ただ、`rax`,`rbx`,`rcx`,`rdx`にそれぞれ1,2,3,4の即値を代入して、`rax+rbx`、`rcx+rdx`を実行するだけのコードだ。

先程と同様な方法で実行バイナリを作ると、そのままアセンブリになっていることがわかる。

```sh
$ as test1.s -o test1.o
$ ld test1.o
$ objdump -S ./a.out

./a.out:     ファイル形式 elf64-x86-64


セクション .text の逆アセンブル:

0000000000400078 <_start>:
  400078:	e8 09 00 00 00       	callq  400086 <main>
  40007d:	48 c7 c0 3c 00 00 00 	mov    $0x3c,%rax
  400084:	0f 05                	syscall 

0000000000400086 <main>:
  400086:	48 c7 c0 01 00 00 00 	mov    $0x1,%rax
  40008d:	48 c7 c3 02 00 00 00 	mov    $0x2,%rbx
  400094:	48 c7 c1 03 00 00 00 	mov    $0x3,%rcx
  40009b:	48 c7 c2 04 00 00 00 	mov    $0x4,%rdx
  4000a2:	48 01 d8             	add    %rbx,%rax
  4000a5:	48 01 d1             	add    %rdx,%rcx
  4000a8:	c3                   	retq   
```

これをGem5で実行して、パイプラインを可視化してみよう。

```sh
$ ./build/X86/gem5.opt --debug-flags=O3PipeView --debug-file=trace.out configs/example/se.py --cpu-type=DerivO3CPU --caches -c ./a.out
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/79744/4ed3b7cb-2627-0de0-9cc9-8ed7e7ec4d3a.png)

何も不思議なことは起きていない。4つのMov命令が同時に実行(Issue: Is)され、その1クロック後にAdd命令が二つ実行されているだけである。なお、ここでは`retq`由来の`RET_NEAR`が3つのμOPSに分解され、そのうち2つがMovと同時にissueされているが、ここでは詳細は省く。

## Out-of-Order 実行

次に、命令の順番を少し変えてみよう。

```nasm:test2.s
  .globl  _start
_start:
  call main
  mov $60, %rax
  syscall

main:
  mov $1, %rax
  mov $2, %rbx
  add %rbx, %rax
  mov $3, %rcx
  mov $4, %rdx
  add %rdx, %rcx
  ret
```

今度は、`mov $2, %rbx`の直後に`add %rbx, %rax`を置いた。`add %rbx,%rax`は直前の`mov $0x2,%rbx`の実行が完了するまで実行できない。その実行を待っていると、玉突き的に次の命令も待たされてしまう(この例ではスーパースカラによって実行できてしまうのだが、ここでは詳細は省く)。


これを先程と同じような手続きで実行バイナリにして、Gem5で実行しよう。ただし今回は`trace2.out`という名前でトレースファイルを吐く(`--debug-file=trace2.out`)。

```sh
$ ./build/X86/gem5.opt --debug-flags=O3PipeView --debug-file=trace2.out configs/example/se.py --cpu-type=DerivO3CPU --caches -c ./a.out
```

Konataで可視化するとこうなる。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/79744/a9f1ecdb-1cee-7f21-6a88-6344aef1eb28.png)

`limm rcx, 0x3`や`limm rdx, 0x4`といったmov命令(limmはおそらくload immediateの略)が、その前にある`add rax, rax, rbx`の実行(Is)を飛び越して実行(Is:issue)されていることがわかるだろう。これがOut of Order実行である。

なお、近年のOoOの石では、「命令のフェッチ」と「命令の終了(Retire)」はアセンブリの順序を守る。なので、途中で命令の実行順序が入れ替わっても、フェッチ(F)と実行終了(Cmのお尻)は順番通りに並ぶ。順序が入れ替わるのはあくまで命令の実行(Issue, IS)である。

Konataには「Transparent Mode」というものがあり、二つのトレース情報を重ねて表示できる。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/79744/f4003cb6-b821-24c5-41e4-f7535a3adee1.png)

二つの実行プロファイルで、命令の実行順序は入れ替わっても、命令の終了時刻(クロック)は変わらないことがわかるであろう。

# まとめ

Gem5により、x86のOut of Order実行による命令の実行順序入れ替えをシミュレートしてみた。Gem5はあくまでAlpha 21264を模したCPUモデルを採用しており、必ずしもx86の実行をエミュレートしているわけではないのだが、とりあえず「OoOだなぁ」と実感することはできたと思う。また、Gem5を使うのに普通のc言語からコンパイルするとバイナリが膨れ上がっていろいろ面倒なので、ここに挙げたシンプルなバイナリを作るアセンブリで解析するのが楽じゃないかな。トレースファイルも小さくなるし。

ちなみにガチでx86の性能予測をしようとすると、OoOやμOPS、スーパースカラ、分岐予測などが絡んでくるので非常に難しい、というか常人には不可能だと思う。

# 追記

x86のコードアナライザとしてIntelから[Intel Architecture Code Analyzer (IACA)](https://software.intel.com/en-us/articles/intel-architecture-code-analyzer)というものが公開されており、uops.infoでも実測値とIACAの値が併記されているのだが、現在ステータスがEnd Of Lifeになっているそうだ(thx, hiroさん)。同様なツールとして、LLVMから[llvm-mca - LLVM Machine Code Analyzer](https://llvm.org/docs/CommandGuide/llvm-mca.html)というものが出ており、IACAもそっちを使うことを推奨しているようなので、興味のある方は参照されたい。