c++ - 64ビット×64ビットの乗算でカラツバアルゴリズムを使用するのは本当に効率的ですか?

Question

私は AVX2 に取り組んでおり、64 ビット x64 ビット -> 128 ビットの拡大乗算を計算する必要があり、最速の方法で 64 ビットの上位部分を取得しました。AVX2 にはそのような命令がないので、カラツバ アルゴリズムを使用して効率と速度を上げることは合理的ですか?

Answer 1

いいえ。最新のアーキテクチャでは、カラツバが教科書の掛け算を打ち負かすクロスオーバーは、通常、8 ～ 24 マシン ワード (x86_64 では 512 ～ 1536 ビット) です。固定サイズの場合、しきい値はその範囲の小さい方の端にあり、新しい ADCX/ADOX 命令により、スカラー コードの場合は多少大きくなる可能性がありますが、64x64 はまだ小さすぎてカラツバの恩恵を受けられません。

Answer 2

AVX2 が、1 つのmulx命令で 64bx64b から 128b を実行する命令に勝る可能性はほとんどありません。浮動小数点 FFT を使用した大きな乗算を認識している例外が 1 つあります。

ただし、正確に 64bx64b から 128b を必要としない場合は、double-double 演算を使用して 53bx53b から 106b を検討できます。

4 つの 53 ビット数を乗算aしb、4 つの 106 ビット数を取得するには、2 つの命令のみが必要です。

__m256 p = _mm256_mul_pd(a,b);
__m256 e = _mm256_fmsub_pd(a,b,p);

を使用すると、1 つの命令で 1 つの 128 ビット数が得られるのに対し、これは 2 つの命令で 4 つの 106 ビット数を与えますmulx。