10

いくつかの非常に大きな整数 (約 2 の 1 億乗) を処理するアルゴリズムをほぼ完成させました。このアルゴリズムはメモリ集約型ではないため、十分なメモリを備えた 16 コア サーバーで高度に並列化されたコードを実行するには、数時間かかります。.NET 4 で BigInteger クラスを利用します。

アルゴリズムの詳細は重要ではありませんが、コンテキストのために、これらの整数に対して実行される操作の完全なリストと、アルゴリズムのいくつかの顕著な機能を以下に示します。

  • 足し算・引き算。
  • 大きな数と小さな数の掛け算。
  • 大きな数を非常に小さな数 (2 など) で割る。
  • ベース 2 ログ。
  • ベース 2 パワー。
  • 2 つ以上の大きな数値 (最小/最大) の比較。
  • 素数の関与は一切ありません。
  • メモリアクセスのパフォーマンスへの影響は、一部のスマートなオンザフライ計算のパフォーマンスへの影響よりも大きいため、このアルゴリズムはメモリを集中的に使用しないように特別に設計されています。それにもかかわらず、メモリアクセスが改善されれば、アルゴリズムは合理的に利益を得ることができます.

コードを可能な限り最適化した結果、プロファイリングでボトルネックが 2 つだけ表示されるようになりました。

  • このような大きな数の基数 2 の対数を計算します。
  • これらの数値の 2 進数の定義済みパターンをチェックしています。これは、BigInteger の基になるデータにアクセスする唯一の方法は、インプレース操作ではなく ToByteArray を最初に使用することであるためです。また、バイトサイズのチャンクを操作してもパフォーマンスは向上しません。

メモリ アクセスとログ操作を考慮して、GPU と、一部の作業を効果的にオフロードできるかどうかについて考え始めました。GPU については、浮動小数点演算用に最適化されていること以外はほとんど知りません。

私の質問は、GPU .NET のようなライブラリを使用して、GPU でこのような大きな数を処理するにはどうすればよいですか? 浮動小数点の最適化を利用して、このような大きな数の Log を計算することはできますか?

戦略を立てるための出発点を探しています。

4

2 に答える 2

5

私は C# での GPU 作業を探しており、Tidepowerd.com GPU.NET と CUDAfy.NET を検討しています。私が最後に確認したとき、Nvidia固有のものとCUDAfyの両方が（まだ）モノをサポートしていませんでした。ただし、どちらも、GPU で実行される C# 内で、かなり普通に見えるコードを使用できます。

また、サードパーティ ライブラリの使用を検討しましたか? いくつかの非常に優れた BigInteger ライブラリがあり、これもオープン ソースです。GMP は非常に優れており、無料です。http://gmplib.org/には、少なくとも 1 つの C# ラッパーがあります (私は経験がありません) http://www.emilstefanov.net/Projects/GnuMpDotNet/

.NET の BigInteger クラスは不変であり、私の経験では便利ではありません。サイズの int が 2 つある場合 (約 100MB)、Add 操作により 3 番目の 100MB BigInt が生成されます。たとえば、2 つのオリジナルのうちの 1 つを変更する場合は、はるかに高速に実行できます。

C = A + B means allocating 100MB for C (this is what BigInt does)
A = A + B means you no longer have the original A, but a much faster calculation
于 2012-08-17T07:49:16.913 に答える