5

I am really new to programming and Cuda. Basically I have a C function that reads a list of data and then checks each item against a hashmap (I'm using uthash for this in C). It works well but I want to run this process in Cuda (once it gets the value for the hash key then it does a lot of processing), but I'm unsure the best way to create a read only hash function that's as quick as possible in Cuda.

Background

Basically I'm trying to value a very very large batch of portfolio as quickly as possible. I get several million portfolio constantly that are in the form of two lists. One has the stock name and the other has the weight. I then use the stock name to look up a hashtable to get other data(value, % change,etc..) and then process it based on the weight. On a CPU in plain C it takes about 8 minutes so I am interesting in trying it on a GPU.

I have read and done the examples in cuda by example so I believe I know how to do most of this except the hash function(there is one in the appendix but it seems focused on adding to it while I only really want it as a reference since it'll never change. I might be rough around the edges in cuda for example so maybe there is something I'm missing that is helpful for me in this situation, like using textual or some special form of memory for this). How would I structure this for best results should each block have its own access to the hashmap or should each thread or is one good enough for the entire GPU?

Edit

Sorry just to clarify, I'm only using C. Worst case I'm willing to use another language but ideally I'd like something that I can just natively put on the GPU once and have all future threads read to it since to process my data I'll need to do it in several large batches).

4

3 に答える 3

9

これは、ハッシュ マップを CPU に保持することについての私のコメントを裏付けるために、GPU でハッシュ マップを使用する場合の潜在的なパフォーマンスの問題に関するいくつかの考えです。

NVIDIA GPU は、ワープと呼ばれる 32 個のスレッドのグループでスレッドを実行します。優れたパフォーマンスを得るには、ワープ内の各スレッドが本質的に同じことを行う必要があります。つまり、同じ命令を実行し、互いに近いメモリ位置から読み取る必要があります。

ハッシュ マップはこれらのルールの両方で壊れる可能性があり、GPU の速度が大幅に低下する可能性があるため、GPU にハッシュ マップを保持しても意味がありません。

warp で 32 個のスレッドが実行されるとどうなるかを考えてみましょう。

  • まず、各スレッドは株式名のハッシュを作成する必要があります。これらの名前の長さが異なる場合、長さごとにハッシュ ループのラウンド数が異なり、ワープ内のすべてのスレッドは、最長の名前のハッシュが完了するまで待機する必要があります。ハッシュ アルゴリズムによっては、ハッシュ アルゴリズム内でコードが使用できるパスが異なる場合があります。ワープ内の異なるスレッドが異なるパスを取る必要がある場合は常に、同じコードを複数回実行する必要があります (コード パスごとに 1 回)。これをワープダイバージェンスと呼びます。

  • warp 内のすべてのスレッドがそれぞれハッシュを取得すると、各スレッドはスロー グローバル メモリ (ハッシュで指定) の異なる場所から読み取る必要があります。GPU は、ワープ内の 32 のスレッドのそれぞれが緊密で一貫したパターンで読み取られたときに最適に実行されます。しかし現在、各スレッドはメモリ内の基本的にランダムな場所から読み取りを行っています。これにより、GPU がすべてのスレッドをシリアル化する必要が生じ、パフォーマンスが潜在的な 1/32 に低下する可能性があります。

  • スレッドが読み取るメモリの場所はハッシュ バケットです。それぞれに異なる数のハッシュが含まれている可能性があり、ワープ内のスレッドが異なることをしなければならなくなります。次に、マッピングされた実際の構造を取得するために、それぞれランダムな場所に再び分岐する必要がある場合があります。

代わりに、株式名とデータ構造を CPU 上のハッシュ マップに保持する場合、CPU を使用して、GPU が適切に処理できる正確なパターンで格納されている情報の配列をまとめることができます。CPU のビジー状態によっては、GPU が以前に送信された作業を処理している間にこれを実行できる場合があります。

これにより、CPU にある構造体の配列 (AoS) を GPU の配列の構造体 (SoA) に変更することもできます。この概念に慣れていない場合は、基本的に次のように変換します。

my_struct {
  int a;
  int b;
};
my_struct my_array_of_structs[1000];

に：

struct my_struct {
  int a[1000];
  int b[1000];
} my_struct_of_arrays;

これにより、すべてのaがメモリ内で互いに隣接して配置されるため、ワープ内の 32 のスレッドが を読み取る命令に到達するとa、すべての値が互いに隣り合ってきれいに配置され、ワー​​プ全体が をロードできるようになります。非常に迅速に評価します。bもちろん、同じことが にも当てはまります。

于 2012-06-09T18:42:39.167 に答える
2

cuda-thrust-extensionsライブラリには、CUDAThrustのhash_map拡張機能があります。私はそれを試していません。

于 2012-06-08T18:48:57.817 に答える
0

あなたのハッシュマップは非常に大きいので、データベースに置き換えることができると思います.mysqlまたは他の製品はすべて問題ありません.おそらく、ハッシュマップを自分で設計するよりも高速です. そして、Roger の見解に同意します。GPU に移動するのは適切ではありません。デバイス メモリを大量に消費し (それを収容できない可能性があります)、カーネル関数がデバイス上のグローバル メモリにアクセスするのが非常に遅くなります。

さらに、あなたのプログラムのどの部分が 8 分かかりますか? 後者ならGPUで高速化できるかも。

よろしくお願いします！

于 2012-06-10T04:09:23.277 に答える