はじめにだよ

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

実行環境はこれだよ

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

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

FMAを使ってみるよ

FMAについての記事はこの記事を参考にさせて頂きました。

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

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

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

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

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

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は次のようにしました。

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

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

$ ./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を付けてアセンブリ出力を確認します。

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

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

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と等価なので、ここだけ置き換えます。

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を実行してみました。

$ 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

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

どうして...