いまどきの☆あせんぶりーらんげーじ

概要

今のCPUは複雑すぎるのでコンパイラのほうが人間より賢いとか嘘である。

基本を抑えればそんなことないので、皆さんコンパイラに打ち勝ちましょう。

以下では、パイプライン化されてて、スーパースカラなマシンをいまどきの☆アーキテクチャとしている。(つってももう20年前くらいの話なんじゃないか…)

今でもスーパースカラじゃないRISCとかあるよ！！とかの意見は、自分のブログに書いておいてください。

あと、x86をいまどきのアーキテクチャと呼ぶのは抵抗あるけど、深追いするならx86が一番面白いと思うので、x86限定の話題も遠慮しないで書く。あと、アセンブリの記法はAT&Tです。

前提知識

x86アセンブリ

参考文献

これを読めばこの文書を読む必要は無い。

The microarchitecture of Intel and AMD CPU’s: An optimization guide for assembly programmers and compiler makers

AMD, Intelのアーキテクチャ解説。これは大変素晴らしいのでみんな読むべき。

http://www.agner.org/optimize/ここにある5本のPDFは基本的に読むべき

Intel(R) 64 and IA-32 Architectures(R) Optimization Reference Manual (PDF)

Intel の最適化マニュアル。

Software Optimization Guide for AMD64 Processors (PDF)

AMD の最適化マニュアル。読んだことない。

Instruction tables

上の「The microarchitecture～」の人と同じ人が書いたx86の各命令のレイテンシ一覧。公式ではないが、公式のと違って実行ユニット一覧も書いてあるので素晴らしい

「レイテンシ」と「スループット」 : (40年前の)いまどきの☆アーキテクチャについて(Wikipedia調べ)

いまどきの☆アーキテクチャで、命令サイクルを考える時には、各命令の「スループット」と「レイテンシ」についての理解が必須である。

このへんを考えないで「今どきのマシンでは、ほとんどの命令は1cycleで終わるよ」と、言うのは、少々曖昧で、正解とも言えるし、間違ってるとも言える。

いまどきの☆は、複数のパイプライン、演算器を持っていて、1cycleで複数の命令を実行できるようになっている。こうなっているアーキテクチャを「スーパースカラ」と呼ぶ。

スーパースカラで複数実行できることまで考慮して、ある命令にかかるcycle数を命令の「スループット」と呼ぶ。

例えば、無印Pentiumは、レジスタ間のADD等の単純な命令なら1cycleで二命令実行することが可能であり、実質、0.5cycleで一命令を実行できることになる。この場合、「無印Pentiumでは、レジスタ間ADD命令のスループットは0.5である」と言える。

さて、では、加算命令のスループットが0.5のマシンでは、いつでも2[命令/cycle]で実行できるか、というと、そうではない。「命令は依存関係があると、並行して実行できない」と、いう問題がある。

依存関係、これは、最適化する上で、アルゴリズムと並んで、最も重要なテーマである。僕の中では、アルゴリズム以外の最適化の問題は全て依存関係の問題になる、と、考えているが、これはまた別の話になるので次回。

hogeがhogehogeするぐらい、依存関係というのは重要な問題である。アーキテクチャを読む上では、「どこの依存関係が問題になっているのか」は、常に頭に入れておかないといけない

さて、で、スーパースカラなアーキテクチャでは、「依存関係があると並行して命令を実行できない」というのが問題なのだった。

例えば、以下のふたつのプログラムを考える

    add %eax, %ecx
    add %eax, %edx

    add %eax, %ecx
    add %ecx, %edx

さて、上のふたつのプログラム、どちらが速いだろうか。正解は、上のほうである。上のほうは、ふたつの命令を1cycleで実行できるが、そうではない。二回目のaddは、一回目のaddの結果を参照しているので、これは、1cycleでは実行できない。

では、下のほうは、2cycleで実行できるのだろうか？これを考えるには、命令の「レイテンシ」を知っておかなければならない。命令は実行開始後、数cycleしてから、結果が参照できるようになる。ここで、「命令実行後、参照できるようになるまでのcycle数」を、命令の「レイテンシ」と呼ぶ。

下のほうは、「一回目のaddを実行して、一回目のaddの結果を待って、二回目のaddが実行される」となる。ここで、「一回目のaddの結果を待って」というのは、どのくらい待つのか？というのが、命令のレイテンシである。無印Pentiumは、addのレイテンシが1なので、下のプログラムは、2cycleで実行できる。

おkだろうか。命令に必要なcycle数というのは、「N[cycle]で実行できるよ」、というようなものではない。正しくは、「1[cycle]でN命令同時発行できて、M[cycle]後に結果が参照できる」と、いうのが正しい。

(あと、ここまで書いてきた解説でも、「N[cycle]で実行」とか書いてあるのも表現として怪しいのだけど、めんどうなので放置)

たとえば、Instruction tables[insttable]には、PI, PMMX での ADDは、

Instruction	Operands	Clock cycles	Pairability
ADD SUB AND OR XOR	r, r/i	1	uv

となっている。

これの読み方は、「レジスタ間、もしくは、オペランド片方が定数のADD、SUB、AND、OR、XORは1cycleでU,Vのふたつの実行ユニットに命令を同時に発行できて、レイテンシは1」となる。ちなみに、無印Pentiumは、ふたつの命令を同時に実行できるのだけど、中には、片方でしか実行できない命令もあったりして、そこらへんを区別するために、「U」「V」という区別がある。U、Vという名前がどこから来てるのかは知らない。