ループアンローリングは高級言語のレイヤで手軽にできる最適化だ。 ループアンローリングは、ループに関するオーバーヘッドを削減することを目的として、わざとループ内で実行したい処理をループ内に展開する。
次のようなループを考える。
int i;
for (i = 0; i < 10; i++) {
std::cout << i << std::endl;
}
このコードは、以下と同じことをする。
std::cout << 0 << std::endl;
std::cout << 1 << std::endl;
std::cout << 2 << std::endl;
std::cout << 3 << std::endl;
std::cout << 4 << std::endl;
std::cout << 5 << std::endl;
std::cout << 6 << std::endl;
std::cout << 7 << std::endl;
std::cout << 8 << std::endl;
std::cout << 9 << std::endl;
この2つは、最適化を無視して考えると、下のほうが高速に動作する。 何故か? まず、ループ処理は次のように動作する。
このうち、①、②、④は本来やりたい処理に無関係な、単なるオーバーヘッドである。後者のコードではこれがないので早くなる。
ループアンローリングは、この事実をヒントに、プログラマが前者のコードを次のように書き換えるものだ。
int i;
for (i = 0; i < 10; i+=5) {
std::cout << i << std::endl;
std::cout << +1 << std::endl;
std::cout << i+2 << std::endl;
std::cout << i+3 << std::endl;
std::cout << i+4 << std::endl;
}
これをすると、ループ回数は2回になり、ジャンプ・分岐命令のオーバーヘッドが1/5になる。ループの中身を展開すればするほど、効果が大きくなる。これが基本的なループアンローリングのアイディアだ。
プログラマがループを書き換えることを静的ループアンローリング、コンパイラが自動で展開することを動的ループアンローリングと呼ぶらしい。
また、上記でループを完全に削除した例と、5つずつの処理を2回ループする例を出したが、前者を完全ループアンローリング、後者を部分ループアンローリングと呼ぶらしい。
オーバーヘッドが削減されるだけでなく、ループアンローリングによってベクトル化が可能になる。上記の例ではprintしているだけなので関係ないが、ループ内の処理によっては、展開した処理の数 (アンローリングファクターというらしい？上記の例では5) が、ベクトル命令用レジスタに配置できる数と一致していれば、ベクトル命令でループ内の処理をいっぺんに終わらせることができるかもしれない。
ループアンローリングすると命令の数が増えるため、命令キャッシュでのミスが発生しやすくなる。特に完全ループアンローリングの場合より発生しやすいので、命令サイズと命令キャッシュのサイズに注意してループアンローリングファクターを決めるのが良さそう。
上記例では10回ループするとわかっていたので5*2に分けることができたが、これがわかっていない場合どうするか？というテクニックが発見されているらしい。これはDuff's Deviceと呼ばれる (Duffさんが発見したから) 。
Duff's deviceはCのswitch-caseをハックしているので、ちゃんと理解するのはかなり難しい。
https://github.com/hidetatz/whale/tree/master/experiment/loopunroll
このコードで実験してみた。C++の場合は、コンパイラの最適化が効いてるようで若干の改善程度。Goでもやってみたが、Goはコンパイラがあまりアグレッシブに最適化しないので効果がかなり大きかった (それでも遅い) 。
現代のIntelプロセッサの理論FLOPSを計算するにあたっては、次のような前提知識が必要になる。
Intelの仕様書には、命令のスループットとレイテンシが載っている。
https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html
このスループットとレイテンシは、アプリケーションとかの文脈と微妙に意味が異なる。
まず、Intelのプロセッサにおけるスループットの定義は、「同じ命令を続けて発効するときに何クロックサイクル待つか」である。例えばスループットが1なら、1クロックサイクルで1回その命令が実行できる。0.5なら、1クロックサイクルで2回その命令が実行できる。
つまり、数字が小さいほうが発行できる命令数が多いのだ。これは割と直感的ではないと思う。通常スループットと言うと、「単位時間あたりの処理できる量」を言い、数字が大きいほうが性能が高い。したがって、意味合いが逆になっている印象を受ける。このため、StackoverflowやAgner fogさんのブログなどでは、Intelプロセッサのスループットは「Reciprocal throughput（逆数スループット）」と言われていたりする。
レイテンシは、「その命令が発行されてから何クロックサイクルでその命令は完了するか」を意味している。たとえばレイテンシが4なら、その命令は発効されてから４クロックサイクル後に命令が処理したデータが使えるようになる。
さて、このレイテンシとスループットがわかれば、1命令でクロックサイクルがどれだけかかるかがわかるのだが、ここでよくある誤解が「スループット * レイテンシ = かかるクロック数/命令」である、というものだ。例えば、スループットが0.5、レイテンシが4の場合、0.5 * 4で、1回の命令で2クロックサイクルかかる、という計算。これはどうやら間違っている。
正しい計算は、スループットが0.5なので、つまり1回のクロックサイクルで2回実行できるから、1回の命令では0.5クロックサイクルかかる、というものだ。
たとえば周波数をNとしたとき、前者の計算だとコアごとのFlopsは0.5Nになるが、後者の計算では2Nになる。 つまり、Flopsを不当に低く見積もってしまう。
何故レイテンシを考慮に入れなくて良いかと言うと、レイテンシは「その命令が終わるまでにどのくらいのクロックサイクルがかかるか」を示しているだけで、前の命令が終わっていなくても後続の命令を発行することは可能なためだ。
逆に言うと、前の命令の結果を利用して次の命令を発行しなければいけない場合（これを「データに依存関係がある」などという）、前者の計算でも良いことになる。ただ、純粋な性能、Flopsに関して議論する場合はデータの依存関係を考慮しないため、後者の計算の方が良い。
というスループットとレイテンシの話を踏まえて。
Fused Multiply Add命令は、"a * b + c"を1回の命令で実行できる。専用の回路がハードウェアに実装されている。
Sky lakeアーキテクチャではFMA命令はレイテンシ4、スループット0.5とある。したがってFlops計算時はFMA命令は2 * クロック周波数回実行できるとみなす。 また、Flops計算時はFMAが積和演算する際の「積」と「和」を別でカウントしてよい（Flopsは演算回数を示しているから）ので、さらに* 2することになる。
ベクトル命令では、専用の容量の大きいレジスタにデータをまとめて入れてまとめて計算しまとめて取り出す、ということができる。 これはFMAと組み合わせることができる。したがって、Flopsを計算するときは「1回のFMA命令で何個のデータを同時に処理できるか」が重要になる。これはすなわち、ベクトル命令で使うレジスタのサイズのことである。
ベクトル命令には種類が色々あり、例えばAVX2では256ビット（単精度浮動小数が同時に8個乗せられる）、SSEでは128ビット（4個）、AVX512では512ビット（16個）など、プロセッサがどの命令をサポートしているかによって異なる。
ここまでの話がわかればFlops計算は簡単である。Flopsは「1クロックサイクルで発効できる命令数」 * 「クロック数」 * 「コア数」だ。
「1クロックサイクルで発効できる命令数」は、FMAとベクトル命令を使って最大限盛った値を使うことになっている。例えばAVX2をサポートしたプロセッサで、FMAのスループットが0.5、レイテンシが4の場合は:
2 (積和なので) * 2 (スループットが0.5なので) * (256 / 32) (AVX2は256ビットのレジスタが使えて、そこに32ビットの浮動小数が何個載るかを計算したい = 単精度浮動小数の場合のFlopsを知りたいので。倍精度の場合は64で割ればよい)
という式になる。長くなったが要は2 * 2 * 8で、1クロックサイクルで32回の単精度浮動小数を演算できることになる。
私が使ってるIntel Core i9-10900は論理コア数20、クロック周波数は通常時2.8GHz、ターボブースト時5.2GHzなので、理論Flopsは
になる。ただし、256ビットのベクトル命令を使いまくっているとクロック周波数が落ちる仕様なため、ターボブースト時の理論Flopsを出すのは100%不可能と考えて良いだろう (たぶん) 。
また、倍精度浮動小数の場合は、ベクトル命令で載せられる数が半分になると考えればよいので、Flopsの値も単純に半分になる。一般的にFlopsといった場合、64ビット浮動小数の演算数を言うような気がしなくもない。
また、上記計算では論理コア数を用いて計算しているが、これでよいのかがよくわからない。演算器は物理コアごとに1つなため、ハイパースレッディングが効いていても各スレッドは演算器を取り合ってしまうおそれがある。従って物理コアを計算に使ったほうが無難な値にはなりそうだが、各スレッドは並列実行可能なため、実際のFlopsの観測値にどう影響するかは不明。
CPUID命令はAMD64 ISAに含まれていて、CPUのモデルやファミリー、サポートされている機能（SSEやAVXなど）、キャッシュラインのサイズ等、CPUの情報をソフトウェアから取得するためのもの。CPU Identificationの略。
EAXレジスタに適切なパラメータをセットしてからCPUIDをコールすると、EAX、EBX、ECX、EDXにそれぞれ何かしらの値が入っているのでそれを使う。
通常、まずEAXに0を入れてコールするとEAXに入れても良い最大値がわかるためそこからスタートするようだが、戻ってきたEAX (手元では10進数で22) の意味がイマイチわかってない。 EAXに0を入れた場合、EBX、ECX、EDXにはベンダIDというプロセッサの製造者を示す値が入っている。これは12文字固定で、EBX、EDX、ECXの順番でアスキーコードになっているようだ。手元では「GenuineIntel」となった。