FMA(融合積和演算)を使ったら計算が遅くなった話


# はじめにだよ

「FMA(融合積和演算)を使うと早くなるよ」という記事を見かけて実際にやったら遅くなりました。どうして...


# 実行環境はこれだよ

OS : macOS High Sierra Version 10.13.5
CPU :  Intel(R) Core(TM) i5-4250U CPU @ 1.30GHz


古いOSやCPUだからダメだったらごめんなさいです...


# FMAを使ってみるよ


FMAについての記事は[この記事](https://qiita.com/mod_poppo/items/e6577df362f44a3ef8dd)を参考にさせて頂きました。

プログラムの高速化の視点で見るなら、FMAは`x*y+z`を1命令ですることができるので、FMAを用いることで簡単に高速化することができる可能性があります。嬉しいです。

ところで、C++11でstd::fmaという関数が実装されました。

`std::fma(x, y, z)` とすることで、FMAが使えるなら`x*y+z`がFMAで計算できる優れものです。(詳しくは[C++日本語リファレンス](https://cpprefjp.github.io/reference/cmath/fma.html)参照)
そして、`FP_FAST_FMA`等のマクロが定義されているなら、単純に`x*y+z`を計算するより早いそうです。(詳しくはやっぱり[C++日本語リファレンス](https://cpprefjp.github.io/reference/cmath/fp_fast_fma.html)参照)


というわけで、実際にやってみました。


C++のサンプルコードは次ようにしてみました。$2^{23}$次元のベクトルの内積計算をします。`FP_FAST_FMA`が定義されている時は`std::fma`を呼び、そうでない時は`x*y+z`を愚直に計算します。

```c++:test.cpp
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<chrono>

int main(void){
#ifdef FP_FAST_FMA
  printf("FP_FAST_FMA defined\n");
#else
  printf("FP_FAST_FMA not defined\n");
#endif
  srand(0);
  const size_t N = 1<<23;
  std::vector<double> a(N), b(N);
  const size_t M = 100;
  std::vector<double> t(M);
  double s = 0.0;
  for(size_t itr=0; itr<M; ++itr){
    for(size_t i=0; i<N; ++i){
      a[i] = (double)rand()/RAND_MAX-0.5;
      b[i] = (double)rand()/RAND_MAX-0.5;
    }
    std::chrono::system_clock::time_point start, end;
    start = std::chrono::system_clock::now();
    for(size_t i=0; i<N; ++i){
#ifdef FP_FAST_FMA
      s = std::fma(a[i],b[i],s);
#else
      s = a[i]*b[i]+s;
#endif
    }
    end = std::chrono::system_clock::now();
    t[itr] = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count();
  }
  printf("%lf\n", s);

  double t_ave = 0.0;
  for(size_t itr=0; itr<M; ++itr){
    t_ave  += t[itr]/M;
  }
  double t_var = 0.0;
  for(size_t itr=0; itr<M; ++itr){
    t_var += (t[itr]-t_ave)*(t[itr]-t_ave)/M;
  }

  printf("%lf +- %lf\n", t_ave, std::sqrt(t_var/(M-1)));

  return 0;
}
```



確認のため内積結果を出力するようにしてあります。

FMAはコンパイル時に引数 `-mfma`等を付けることで使用することができます。FMAを使わないのなら普通にコンパイルします。なので、Makefileは次のようにしました。


```makefile
all: test1 test2

test1: test.cpp
	g++ test.cpp -std=c++11 -o test1 -mfma -O3

test2: test.cpp
	g++ test.cpp -std=c++11 -o test2 -O3
```

実行して結果を比べてみます。

```bash
$ ./test1
FP_FAST_FMA defined
5905.793798
18.140000 +- 0.167585
$ ./test2
FP_FAST_FMA not defined
5905.793798
11.600000 +- 0.102494
```

|                          | FMAあり          | FMAなし          |
| ------------------------ | ---------------- | ---------------- |
| 内積計算実行時間(ミリ秒) | 18.14 $\pm$ 0.17 | 11.60 $\pm$ 0.10 |

`FP_FAST_FMA`がdefineされているからFMAが早いはずなのに、FMAを使うと遅くなったよ。悲しいね。

## アセンブリを見てみるよ

このままでは悲しいので`-save-temps`を付けてアセンブリ出力を確認します。

内積計算のループの部分を確認してみると、



```assembly:test1.s
LBB0_8:                                 ##   Parent Loop BB0_3 Depth=1
                                        ## =>  This Inner Loop Header: Depth=2
	vmovsd	-24(%r14,%rax,8), %xmm0 ## xmm0 = mem[0],zero
	vmovsd	-16(%r14,%rax,8), %xmm1 ## xmm1 = mem[0],zero
	vfmadd132sd	-24(%r15,%rax,8), %xmm2, %xmm0
	vfmadd231sd	-16(%r15,%rax,8), %xmm1, %xmm0
	vmovsd	-8(%r14,%rax,8), %xmm1  ## xmm1 = mem[0],zero
	vfmadd132sd	-8(%r15,%rax,8), %xmm0, %xmm1
	vmovsd	(%r14,%rax,8), %xmm2    ## xmm2 = mem[0],zero
	vfmadd132sd	(%r15,%rax,8), %xmm1, %xmm2
	addq	$4, %rax
	cmpq	$8388611, %rax          ## imm = 0x800003
	jne	LBB0_8
```



```assembly:test2.s
LBB0_8:                                 ##   Parent Loop BB0_3 Depth=1
                                        ## =>  This Inner Loop Header: Depth=2
	movsd	-24(%r14,%rax,8), %xmm0 ## xmm0 = mem[0],zero
	movsd	-16(%r14,%rax,8), %xmm1 ## xmm1 = mem[0],zero
	mulsd	-24(%r15,%rax,8), %xmm0
	addsd	%xmm2, %xmm0
	mulsd	-16(%r15,%rax,8), %xmm1
	addsd	%xmm0, %xmm1
	movsd	-8(%r14,%rax,8), %xmm0  ## xmm0 = mem[0],zero
	mulsd	-8(%r15,%rax,8), %xmm0
	addsd	%xmm1, %xmm0
	movsd	(%r14,%rax,8), %xmm2    ## xmm2 = mem[0],zero
	mulsd	(%r15,%rax,8), %xmm2
	addsd	%xmm0, %xmm2
	addq	$4, %rax
	cmpq	$8388611, %rax          ## imm = 0x800003
	jne	LBB0_8
```



となります。test1の方では確かにFMAの計算命令1命令が出ている一方、test2では積と和の2命令に分かれているのが分かります。

`vfmadd231sd A, B, C` は `mulsd A, B`+`addsd B, C`と等価なので、ここだけ置き換えます。

```assembly:test1_new.s
LBB0_8:                                 ##   Parent Loop BB0_3 Depth=1
                                        ## =>  This Inner Loop Header: Depth=2
	vmovsd	-24(%r14,%rax,8), %xmm0 ## xmm0 = mem[0],zero
	vmovsd	-16(%r14,%rax,8), %xmm1 ## xmm1 = mem[0],zero
	vfmadd132sd	-24(%r15,%rax,8), %xmm2, %xmm0
#vfmadd231sd	-16(%r15,%rax,8), %xmm1, %xmm0
	mulsd -16(%r15,%rax,8), %xmm1
	addsd %xmm1, %xmm0
	vmovsd	-8(%r14,%rax,8), %xmm1  ## xmm1 = mem[0],zero
	vfmadd132sd	-8(%r15,%rax,8), %xmm0, %xmm1
	vmovsd	(%r14,%rax,8), %xmm2    ## xmm2 = mem[0],zero
	vfmadd132sd	(%r15,%rax,8), %xmm1, %xmm2
	addq	$4, %rax
	cmpq	$8388611, %rax          ## imm = 0x800003
	jne	LBB0_8
```



もし、fmaddが計算時間を遅くする原因であるなら、この変更で (18.14-11.6)/4 ~ 1.6ミリ秒程度実行時間が早くなり、内積実行時間が18.14-1.6 ~ 16.5ミリ秒程度になるはずです。

変更した`test1_new.s`を実行してみました。

```bash
$ c++ test1_new.s -o test1_new
$ ./test1_new
FP_FAST_FMA defined
5905.793798
16.460000 +- 0.198184
```

|                          | FMAあり          | 一部FMAあり      | FMAなし          |
| ------------------------ | ---------------- | ---------------- | ---------------- |
| 内積計算実行時間(ミリ秒) | 18.14 $\pm$ 0.17 | 16.46 $\pm$ 0.20 | 11.60 $\pm$ 0.10 |

予想通りの実行時間になりました（白目）

どうして...