1

私は、OpenCL とハッシュの長所と短所を見つけようとしている OpenCL のまったくの初心者です。

たとえば、自明なハッシュ関数があるとします。

public static uint GetHash(string str)
{
  uint s = 21; // seed
  foreach (char ch in str)
      s = (s + (uint)ch) * 10;
  return s;
}

(これが恐ろしいハッシュであることはわかっていますが、これは単なる例です)

a-zA-Z0-9_ここで、文字のすべての順列を 50 の長さまで計算したいとします。たとえば、次のようになります。

a
b
...
_
aa
ab
...
__

明らかに、これは膨大な数 (63^50) のハッシュを計算する必要があるため、OpenCL と GPU コンピューティングを使用することにしました。

私の質問は、OpenCL/GPU コンピューティングがもたらす落とし穴はありますか? 私は以下を読みました：

  1. PCIe バス経由でデータを転送するのは遅いです。
  2. GPU 上のグローバル メモリへのアクセスは sloooooooooooowwwwww
  3. ワープ内のすべての「スレッド」は同じ命令を実行する必要があります

これにより、この場合の GPU コンピューティングの有効性に疑問が生じます。次のアプローチのいずれかを使用する必要があるように思われるからです。

  • 各スレッドに独自の順列を計算させます (各スレッドで実行するインクリメントの数が異なるため、#3 に違反します)。
  • 各スレッドに、他のすべてのスレッドに影響する 1 つのインクリメントを実行させる (違反 #2)
  • CPUで順列を計算し、それらをGPUにディスパッチします（＃1に違反します。さらに、基本的にGPUを使用してハッシュを計算しています...）

それらの結論は正確ですか？そうでない場合、その理由と、他に注意すべきことはありますか?

4

1 に答える 1

1

スローは相対的な用語です。しかし、一般的に、GPU との間で大量のデータを転送することは避けたいと考えています。別の言い方をすれば、事前に GPU でかなりの量の計算を行うことによって、データ転送のコストを「価値のある」ものにする必要があります。結果を転送します。

だから、あなたが現在述べているように（私が理解しているように）あなたの問題を見て、あなたはしたい：

  1. ホスト (CPU) で可能な各文字列を生成する
  2. 元の文字列を GPU に転送する
  3. これらの文字列のハッシュを GPU で並列に計算する
  4. 計算されたハッシュをホスト (CPU) に転送します。

ハッシュの計算は計算上かなり自明であり、大部分の時間はデータ転送の実行に費やされるため、これはうまく実行されません。

間違いなく、GPU で文字列順列を生成する必要があります。これにより、(2) のコストが回避されます。これらを作業項目に分割することは、それほど難しいことではありません。'aaaa' などのベース文字列があり、サフィックス文字ごとに 4 つの次元がある場合、各スレッドでハッシュを計算します (ハッシュ関数によっては、プレフィックスのハッシュが大幅に節約される場合もあります)。 「aaaa」は一度事前計算して再利用できます)、それを出力に入れます。

しかし、このアプローチは、生成されたハッシュをホストに転送する際にまだボトルネックになると思います。既知のハッシュとの等価性のチェックなど、後でハッシュを処理する必要がある場合は、これを GPU でも行うことができます。 63 ^ 50ではなく、グローバルメモリへの一致（またはいくつかの一致）文字列/結果ハッシュ。

于 2013-10-26T06:03:14.123 に答える