🚀

SIMD高速化のための知識とノウハウ

2024/08/16に公開

C++

プログラミングでSIMD命令を使い倒すために知っておくべきこと

1.記事の概要・対象読者

本記事ではプログラムの高速化手法の1つである「SIMD命令」に焦点を当てて、どの程度の効果が得られるのかと、SIMD命令を最大限活用するために気を付けるべきポイント を解説していきます。SIMD命令を使って高速化を図る人を対象読者としています。

なお、本記事ではSIMD命令の能力を引き出す手法の解説を目標とするため、SIMD命令を使ったコードの具体例や、SIMD命令が具体的にどんな演算に対応しているのかは解説しません。それらは他の方の記事や、対応命令の場合は参考文献6.[1]を参照してください。またSIMD命令以外にも共通するような高速化手法も基本的に取り扱わないので、それは別記事を参照してください。

別記事：一般的な高速化手法

2.事前知識

まずSIMDとは何かについて説明していきます。知ってる方は読み飛ばしていただいて大丈夫です。

SIMDとは1つの命令を同時に複数のデータに対して行うことです。これを行うSIMD命令を利用することで、1命令で複数データ分を一度に処理できて処理速度が向上します。

SIMD命令にも種類があり、PC向けCPUでは256bit分を一度に扱えるAVX2が主流で、int型,float型(32bit)なら8個のデータを一度に処理できます。データセンター向け等では512bit扱えるAVX512が、ArmではNEONというSIMD命令セットが用意されています。

3.SIMD命令の理想と現実

AVXやAVX2のような256bitのSIMD命令ではint型やfloat型を8個同時に扱えるので、SIMD命令を使えば理想的には処理速度が8倍、実際の使用場面でも処理速度が4,5倍程度にはなるように思えます。しかし実際には大抵高速化の効果が1.5～2倍程度で頭打ちし、全く性能を引き出せません。

その理由はメモリにあります。この記事を書いているPC(CPU:i5-13600K,RAM:DDR4 3200MHz)で考えてみましょう。最大負荷をかけた場合、CPUは4.5GHz程度で動作し、コア数は計20個あるので

4.5 \rm{GHz} \times 20 = 900\rm{億clock/s}

つまり1clockで計算できる命令なら毎秒900億回処理でき、これにAVX2を適用すれば、理想的にはint型に対し毎秒

900億回 \times 8 = 7200

億回の処理が行えます。

しかし問題はメモリです。デュアルチャネル運用でのメモリの帯域幅は

3200 \rm{MHz} \times 64\rm{bit} \times 2 = 51.2\rm{GB/s}

これはint型を毎秒128億個転送する速度です。これを先ほどの処理速度と比較すると、CPUとメモリが両方最高速度で動いた場合、メモリがint型1個分転送する間にCPUはSIMD命令なしでもint型7個分ほど処理が行えるわけで、こうなると大抵メモリが律速になって処理速度が頭打ちします。このため仮にSIMD命令を使って計算速度を8倍にしたところで、大抵メモリ律速だから処理速度がたいして上がらないという結果になるわけです。

SIMD命令初心者向けに書かれたコードで速度が4,5倍になった！というのも時折見かけますが、その大抵の理由はシングルスレッドコードだからです。1コアなら処理速度はコア数分の1まで落ちるので、私のCPUならSIMDなしで毎秒45億回程度になります。これならメモリ律速でなくなり、SIMD命令がきちんと効果を発揮するわけです。しかし普通は環境依存の強いSIMD命令を利用する前にコードのマルチスレッド化で高速化をすべきなので、上に書いたようにメモリ律速となってSIMD命令が性能を発揮できなくなります。

4.SIMD命令での高速化手法

前項で書いたようにSIMD命令の性能が引き出しきれない原因のほとんどはメモリが足を引っ張っていることなので、この項で紹介するほとんどの内容もメモリ律速を解消するための方法となります。

4.1.キャッシュを使え

毎回メモリにアクセスしていてはそこがボトルネックになることは明白なので、キャッシュの活用は必須です。現在のCPUでは1コア当たりL2キャッシュが1MB程度、L3キャッシュが数MB程度あるので、int型で数十万データ分はキャッシュに入ります。 一番良いのは計算に使うデータ全体を10MB程度に抑えることですが、数GB～数十GBもメモリがあることを前提とする現代のプログラミングにおいて、それは正直厳しいです。そこで大量のメモリを使いつつキャッシュも活用する方法として、forループを小さく区切るという方法があります。

例えば1億データに対して次のように計算を行うことを考えます。

  for(int i=0; i<100000000; i++){
    (処理A);
  }

  (処理X);

  for(int i=0; i<100000000; i++){
    (処理B);
  }

  (処理Y);

  for(int i=0; i<100000000; i++){
    (処理C);
  }

このときのデータ量は400MBなので当然キャッシュには収まらず、それぞれのforループにおいてメモリ律速となります。しかしもし1万データ程度の繰り返しに変換することができたなら、具体的には

  for(int j=0; j<10000; j++){

    for(int k=0; k<10000; k++){
      i = j*10000 + k;
      (処理A');
    }

    (処理X');

    for(int k=0; k<10000; k++){
      i = j*10000 + k;
      (処理B');
    }

    (処理Y');

    for(int k=0; k<10000; k++){
      i = j*10000 + k;
      (処理C');
    }

  }

のように1万データ分のループを1万回繰り返すように書き換えられたのならば、扱うデータ総量は1億データのままで、1万データ分、すなわち40KB程度のキャッシュに乗るようになります。ただし当然計算順序は変わるので、どうやって書き換えれば良いのかは計算内容によります。しかしキャッシュにうまく乗ればSIMD命令で理論値に近い8倍高速化もあり得ます。

4.2.演算をまとめろ

メモリ、キャッシュと来れば次に目を向けるべきはレジスタです。要はレジスタにデータを置いたまま計算を行えるなら、メモリアクセスは最小限で済みます。具体例としてベクトルデータA,B,Cの和をとることを考えると、

  D = _mm256_add_epi32(A,B);
  E = _mm256_add_epi32(D,C);

と書けます。Dの結果がいらない場合、これを

  E = _mm256_add_epi32(_mm256_add_epi32(A,B),C);

とした方が計算が速くなるという話です。後者の書き方だとDがその後の計算で使われないことが確定するので、計算の途中でメモリアクセスを行わず、コンパイラがレジスタ内で計算を完結させる可能性が上がります。もちろん前者でも最適化によりDをメモリに格納しないこともありますが、最適化はコンパイラ次第なので、速度を求めるなら最適化されやすい記述を心掛けるべきです。

このように命令をまとめて1行に書くことで、最適化されやすくするというテクニックはSIMD命令以外でも使われることがあるのですが、見づらくなるのでPCが高性能化した最近のプログラミングではあまり推奨されません。しかしSIMD命令が必要な速度要件がシビアなコードであれば、見づらくなることを承知で書くことも1つの選択肢になります。

4.3.演算に肩代わりさせろ

ここまでは扱うデータ量をそのままにメモリアクセスを減らす方法の紹介でしたが、ここで紹介するのはそのデータ量自体を減らす方法です。一般的な高速化手法として何度も使う計算結果はあらかじめ計算して格納しておくというのがあります。 例えばある数列とその平方を計算で利用する場合、数列に加えて各値の平方もメモリに格納することで計算量を減らして高速化できます。しかしこの方法には問題があり、これで高速化するのは計算速度が律速になっている場合 だということです。確かに計算量は減りますが、メモリアクセス・メモリ使用量は増加しますのでSIMD命令を使うような状況にはあっていません。むしろSIMD命令を使っていればメモリ帯域幅に比べて演算速度は余っています。ゆえにある程度の計算量ならばあらかじめ計算などせず、必要になるたびに再計算して演算量増加と引き換えにメモリアクセスを削減した方が効率的です。

4.4.データを無駄なく使え

メモリ帯域幅は基本不足気味なので、扱うデータはとにかく無駄なく活用することが大切です。 具体的にデータの無駄遣いになっている例としてはbool型があります。bool型は2値変数なので1bitあれば格納できるのですが、原則1byte=8bit分使って格納されています。そのため必要量の8倍のメモリを使っており、転送する際には必要量の8倍の帯域を食っています。ここまで露骨なものは稀ですが、例えばデータに対してand演算などでマスク処理をする場合、マスクを掛けなかった部分のデータは捨てられてしまうわけです。この捨てられた分も当然帯域幅を食っているので、もし処理方法を工夫して最初からこの部分を削って転送できたならば、処理速度を上げられます。実際にどうすればいいかは処理内容によって違いますが、データ量を減らせる余地があることを認識することは高速化の上で非常に重要です。

4.5.極力単純な命令を使え

AVXやAVX2などのSIMD命令セットにはかなり沢山の命令が用意されています(参考文献6.[1]参照)。そのため同じ計算であっても違う関数群を用いて2通り以上で表現できる場合があります。そのときにはなるべく単純な関数を多用しているものを選ぶ というのが基本です。これはレイテンシを抑えることを目的としています。

ここでレイテンシとスループットの2つの用語について軽く解説しておきます。レイテンシとは命令が発行されてから計算が完了するまでのクロック数、スループットは同時に発行できる命令数の逆数です。これらはいずれも小さい方が処理速度が速いです。

一般的に加算やbit演算などの基本的なSIMD演算におけるレイテンシ・スループットはかなり低く、反対に丸め処理などの少し特殊な演算では大きくなります。よって基本的な演算を多く利用するよう意識することで早く処理してくれる可能性が上がります。ただこれはあくまで一般的に基本演算の方が処理が速いという話なので、本当に早いのかどうかは参考文献のSIMD命令表を確認してください。

5.おわりに

SIMD命令を活用する場面では高い処理速度が求められ、期待される計算速度もはるかに高いので、一般のプログラミングとはかなり異なる高速化が必要になります。そういった中でSIMD命令の性能を十分に引き出すためには、メモリや演算速度に関する詳細な知識や、ボトルネックを特定する力が必要です。後者の能力はすぐ身につくものではないですが、実際にコードを書いて処理速度を測定することを繰り返すことでつかめてくると思います。

6.参考文献

[1] 「Intel Intrinsics Guide」(SIMD命令の一覧)

(2024/08/15 参照)

[2] 北川洋幸著,『AVX命令入門　Intel CPU のSIMD命令を使い倒せ』,シナノ書籍印刷株式会社,初版第1刷,ISBN 978-4-87783-369-5