8

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))相対時間で実行されます。ゼロとゼロの要素のペアと非ゼロの非ゼロの要素のペアを並べ替える (交換する) 時間を無駄にする必要がないため、これよりも高速なアルゴリズムが存在する可能性があると思います (順序を維持する必要はありません)。

したがって、どの方法が最も速いかはよくわかりませんが、これを処理するより良い方法があると思います。助言がありますか？

4

3 に答える 3