c++ - ソートされた配列内の要素の頻度を効率的に計算するために CUDA を使用することは可能ですか?

Question

私はCudaを初めて使用します。本からいくつかの章を読み、オンラインで多くのチュートリアルを読みました。ベクトルの加算と乗算を独自に実装しました。

もう少し先に進みたいので、ソートされた整数の配列を入力として受け取る関数を実装したいとしましょう。

私たちの目標は、配列内にある各整数の度数を見つけることです。

出力を生成するために、配列を 1 回スキャンすることができます。時間計算量は になりますO(n)。

グループが違うので、CUDAを活用できるはずです。

これが配列であるとします

   1
   1
   1
   1
   2
   2
   3
   3
   5
   5
   6
   7

完全な並列処理を実現するために、各スレッドは、合計を見つけるためにスキャンする必要がある配列の部分を正確に認識している必要があります。int dataPosPerThread[]これは、スレッドIDごとdataPosPerThread[threadId]に初期配列の開始位置を値として持つ別の配列を使用する場合にのみ実現できます。つまり、各スレッドはどこから開始し、どこで終了するかを知っているということです。

O(n)ただし、この方法では、ポジションを見つけるのに時間がかかるため、何も得られません。最終的に、総コストは、スレッドO(n) + cost_to_transfer_the_data_to_the_gpu + O(c) + cost_to_transfer_the_results_to_the_gpu がO(c)最終的な出力を見つけるのにかかる一定の時間になります。もちろん、初期配列内に多くの異なる整数があると仮定します。

余計な出費は避けたいO(n)。

これまで私が考えていたのは、 size の配列を持つことで、arraySize使用されるスレッドの合計量を指定します。totalAmountOfThreadsこれは、各スレッドが値をスキャンする必要があることを意味しtotalAmountOfThreads/arraySizeます。

最初のスレッド (id 0) は、位置 0 から位置 までスキャンを開始しtotalAmountOfThreads/arraySizeます。

2 番目のスレッドは次から始まりtotalAmountOfThreads/arraySize + 1ます。

問題は、一部のスレッドが異なる整数グループ、または他のスレッドによって処理されているより多くの値を持つ 1 つのグループで動作している可能性があることです。たとえば、上記の例で 6 つのスレッドがあると仮定すると、各スレッドは配列の 2 つの整数を受け取るため、次のようになります。

   1     <-------- thread 0
   1
   1     <-------- thread 1
   1
   2     <-------- thread 2
   2
   3     <-------- thread 3
   3
   5     <-------- thread 4
   5
   6     <-------- thread 5
   7

ご覧のとおり、スレッド 0 には1値しかありませんが、スレッド 2 によって処理されている他の1値があります。ただし、並列処理を実現するには、これらのスレッドが無関係なデータを処理する必要があります。このロジックを使用すると仮定すると、各スレッドは次の結果を計算します。

   thread 0 => {value=1, total=2}
   thread 1 => {value=1, total=2}
   thread 2 => {value=2, total=2}
   thread 3 => {value=3, total=2}
   thread 4 => {value=5, total=2}
   thread 5 => {{value=6, total=1}, {value=7, total=1}}

この結果を得ることによって、さらに何が達成できるのでしょうか? unordered_map単一のスレッドによって計算された各値に対して合計変数を効率的に更新できるように、追加の hash_map を使用することを誰かが提案できます。でも

1. Unordered_mapcudaコンパイラではサポートされていません

2. これは、異なるブロックの 2 つのスレッドが同じ値で動作する可能性があるため、スレッドが共有メモリを利用できないことを意味します。そのため、ハッシュ マップはグローバル メモリに存在する必要があります。

3. 上記の 2 つが問題にならなかったとしても、ハッシュ マップを更新するときにスレッド間で競合状態が発生します。

この問題にアプローチするには、どのような方法がよいでしょうか?

前もって感謝します