24

私はまだ C++ で任意の長整数のルーチンに取り組んでいます。これまでのところ、64 ビット Intel CPU の加算/減算と乗算を実装しました。

すべて正常に動作しますが、SSE を使用して少し高速化できないかと考えました。SSE ドキュメントとプロセッサ命令リストを参照しましたが、使用できると思われるものを見つけることができませんでした。その理由は次のとおりです。

  • SSE には整数命令がいくつかありますが、ほとんどの命令は浮動小数点を処理します。整数で使用するように設計されているようには見えません (例えば、less の整数比較はありますか?)

  • SSE の考え方は SIMD (同じ命令、複数のデータ) であるため、2 つまたは 4 つの独立した操作の命令を提供します。一方、私は128ビットの整数加算（128ビットの入力と出力）のようなものを持ちたいと思っています。これは存在しないようです。（まだ？AVX2で？）

  • 整数の加算と減算は、入力キャリーも出力キャリーも処理しません。そのため、手動で行うのは非常に面倒です (したがって遅い)。

私の質問は次のとおりです。私の評価は正しいですか、それとも見落としているものはありますか? 長整数ルーチンは SSE の恩恵を受けることができますか? 特に、add、sub、または mul ルーチンをより迅速に作成するのに役立ちますか?

4

1 に答える 1

32

以前は、この質問に対する答えは「いいえ」でした。しかし、2017 年現在、状況は変わりつつあります。

ただし、先に進む前に、背景となる用語について説明します。

  1. フルワード算術
  2. 部分単語算術


フルワード演算:

これは、数値が32 ビットまたは 64 ビットの整数の配列を使用して基数 2 32または 2 64で格納される標準的な表現です。多くの bignum ライブラリとアプリケーション (GMP を含む) は、この表現を使用します。

フルワード表現では、すべての整数に固有の表現があります。比較などの操作は簡単です。しかし、加算のようなものは、キャリー伝搬が必要なため、より困難です。

bignum 算術のベクトル化をほとんど不可能にしているのは、このキャリー伝搬です。


部分語算術

これは、数値がハードウェアのワードサイズよりも小さい基数を使用する、あまり使用されない表現です。たとえば、各 64 ビット ワードに 60 ビットのみを配置します。または1,000,000,000、10 進演算に 32 ビット ワード サイズの base を使用します。

GMP の作成者はこれを「ネイル」と呼び、「ネイル」は単語の未使用部分です。

以前は、部分語演算の使用は、非バイナリ ベースで動作するアプリケーションにほとんど制限されていました。しかし、今日では、キャリーの伝搬を遅らせることができるという点で、より重要になってきています。

全語演算の問題:

フルワード演算のベクトル化は、歴史的に失われた原因でした:

  1. SSE/AVX2 はキャリー伝搬をサポートしていません。
  2. SSE/AVX2 には 128 ビットの加減算がありません。
  3. SSE/AVX2 には、64 x 64 ビットの整数乗算はありません。*

*AVX512-DQ は、下位半分の 64x64 ビット乗算を追加します。しかし、まだ上半分の命令はありません。

さらに、x86/x64 には、bignum 用の特殊なスカラー命令がたくさんあります。

  • キャリー付き加算: adc, adcx, adox.
  • ダブルワード乗算: シングルオペランドmuland mulx.

これを考慮すると、bignum-add と bignum-multiply の両方で、SIMD が x64 でスカラーを打ち負かすことは困難です。SSEまたはAVXでは絶対にありません。

AVX2 では、データを再配置して、4 つの SIMD レーンのそれぞれで同じ長さの 4 つの異なる(独立した) 乗算の「垂直ベクトル化」を有効にすると、SIMD はスカラー bignum-multiply とほぼ競合します。

AVX512 は、垂直方向のベクトル化を想定して、再び SIMD を支持するように物事を傾けます。

しかし、ほとんどの場合、bignum の「水平方向のベクトル化」は、(同じサイズの) 多数の bignum があり、「垂直」にするためにそれらを転置するコストを負担できない限り、大部分は失われた原因のままです。


部分単語演算のベクトル化

部分ワード演算では、追加の「ネイル」ビットにより、キャリーの伝播を遅らせることができます。

したがって、単語をオーバーフローしない限り、SIMD add/sub は直接実行できます。多くの実装では、部分単語表現は符号付き整数を使用して、単語が負になることを許可します。

(通常) キャリーアウトを実行する必要がないため、部分ワードの SIMD 加算/減算は、垂直方向と水平方向の両方のベクトル化された bignum で同等に効率的に実行できます。

水平方向にベクトル化された bignum のキャリーアウトは、次のレーンに釘を移動するだけなので、まだ安価です。ほとんど同じである 2 つの数値を比較する必要がない限り、釘のビットを完全にクリアして一意の表現に到達するための完全なキャリーアウトは、通常は必要ありません。

部分ワード演算では、ネイル ビットを処理する必要があるため、乗算はより複雑になります。しかし、add/sub と同様に、水平方向にベクトル化された bignum に対しても効率的に実行できます。

AVX512-IFMA (Cannonlake プロセッサに付属) には、52 x 52 ビット乗算 (おそらく FPU ハードウェアを使用) の完全な 104 ビットを与える命令があります。これは、1 ワードあたり 52 ビットを使用する部分ワード表現で非常にうまく機能します。


FFT を使用した大きな乗算

bignum が非常に大きい場合、乗算は高速フーリエ変換 (FFT)を使用して最も効率的に実行されます。

FFT は独立した で動作するため、完全にベクトル化できdoubleます。これが可能なのは、基本的に、FFT が使用する表現が部分 語表現であるためです。

要約すると、bignum 演算のベクトル化は可能です。しかし、犠牲を払わなければなりません。

SSE/AVX が、表現やデータ レイアウトに根本的な変更を加えることなく、既存の bignum コードの一部を高速化できると期待している場合、それは実現しない可能性があります。

それでも、bignum 算術はベクトル化できます。

開示：

私は、大量の算術演算を行うy-cruncherの作成者です。

于 2012-01-15T02:05:51.577 に答える