問題タブ [avx512]

潜在的な階乗素数 (n!+-1 の形式の数) の約数を見つけようとしましたが、最近 Skylake-X ワークステーションを購入したので、AVX512 命令を使用して速度を上げることができると考えました。

アルゴリズムは単純で、主なステップは、同じ除数に関してモジュロを繰り返し取ることです。主なことは、広い範囲の n 値をループすることです。これはcで書かれた単純なアプローチです（Pは素数の表です）：

ここでの考え方は、n の広い範囲、たとえば 1,000,000 -> 10,000,000 を同じ除数のセットに対してチェックすることです。したがって、同じ除数を数百万回モジュロ尊重します。DIV の使用は非常に遅いため、計算の範囲に応じていくつかのアプローチが可能です。ここで、私の場合、n は 10^7 未満である可能性が高く、潜在的な除数 p は 10,000 G (< 10^13) 未満です。したがって、数値は 64 ビット未満であり、53 ビット未満でもあります!最大剰余 (p-1) x n が 64 ビットより大きい。したがって、64ビットより大きい数値からモジュロを取得しているため、モンゴメリー法の最も単純なバージョンは機能しないと思いました。

double を使用する場合、FMA を使用して最大 106 ビット (推測) の正確な積を取得する、power pc の古いコードを見つけました。そこで、このアプローチを AVX 512 アセンブラー (Intel Intrinsics) に変換しました。これは、FMA メソッドの単純なバージョンです。これは Dekker (1971) の作業に基づいています。Dekker プロダクトと TwoProduct の FMA バージョンは、この背後にある理論的根拠を見つけたり、グーグルで調べたりするときに役立つ言葉です。また、このアプローチについては、このフォーラム (例:ここ) で議論されています。

ここで私は魔法の定数を使用しました

つまり、倍精度の 2^51 + 2^52 マジック ナンバーです。

これを AVX512 (ループごとに 32 の潜在的な除数) に変換し、IACA を使用して結果を分析しました。スループットのボトルネック: 割り当てリソースが利用できないため、バックエンドとバックエンドの割り当てが停滞していることがわかりました。私はアセンブラーの経験があまりないので、質問は、これを高速化し、このバックエンドのボトルネックを解決するためにできることはありますか?

AVX512 コードはここにあり、 githubからも見つけることができます