整数の配列を取り0、順序を維持するかどうかに関係なくすべてのを削除するCUDAを使用して並列アルゴリズムを構築しようとしています。
例：
グローバルメモリ：{0、0、0、0、14、0、0、17、0、0、0、0、13}
ホストメモリの結果：{17、13、14、0、0、...}
最も簡単な方法は、ホストを使用して0'をO(n)時間内に削除することです。しかし、私が周りに1000要素を持っていることを考えると、GPUにすべてを残し、送信する前に最初に凝縮する方がおそらく速いでしょう。
推奨される方法は、各スレッドがスタックに（任意の順序で）ポップおよびプッシュできるように、デバイス上のスタックを作成することです。ただし、CUDAにはこれが実装されていないと思います。
同等の（ただしはるかに遅い）方法は、すべてのスレッドが書き込みを終了するまで、書き込みを試行し続けることです。
kernalRemoveSpacing(int * array, int * outArray, int arraySize) {
if (array[threadId.x] == 0)
return;
for (int i = 0; i < arraySize; i++) {
array = arr[threadId.x];
__threadfence();
// If we were the lucky thread we won!
// kill the thread and continue re-reincarnated in a different thread
if (array[i] == arr[threadId.x])
return;
}
}
この方法には、O(f(x))時間内に実行するという点でのみ利点f(x)があります。ここで、は配列内にあるゼロ以外の値の平均数です（f(x) ~= ln(n)私の実装では、O(ln(n))時間ですが、O定数が高くなります）
最後に、クイックソートやマージソートなどのソートアルゴリズムも問題を解決し、実際にはO(ln(n))相対時間で実行されます。ゼロとゼロの要素のペア、およびゼロ以外の非ゼロの要素のペアの順序付け（順序を維持する必要はありません）に時間を浪費する必要がないため、これよりも高速なアルゴリズムがあると思います。
そのため、どちらの方法が最速かはよくわかりませんが、これを処理するためのより良い方法があると思います。助言がありますか？
あなたが求めているのは、ストリーム圧縮1と呼ばれる古典的な並列アルゴリズムです。
推力がオプションの場合は、単にを使用できますthrust::copy_if。これは安定したアルゴリズムであり、すべての要素の相対的な順序を保持します。
大まかなスケッチ：
#include <thrust/copy.h>
template<typename T>
struct is_non_zero {
__host__ __device__
auto operator()(T x) const -> bool {
return T != 0;
}
};
// ... your input and output vectors here
thrust::copy_if(input.begin(), input.end(), output.begin(), is_non_zero<int>());
推力がオプションでない場合は、ストリームの圧縮を自分で実装できます（このトピックに関する文献はたくさんあります）。これは楽しくて適度に単純な演習であると同時に、より複雑な並列プリミティブの基本的な構成要素でもあります。
（1）厳密に言えば、そうではありません正確にストリーム圧縮は、伝統的に安定したアルゴリズムであるとして、伝統的な意味でのストリーム圧密が、あなたの要件には、安定性が含まれていません。この緩和された要件は、おそらくより効率的な実装につながる可能性がありますか？
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加