並べ替えられた配列のインデックスについての並列計算

Question

並べ替えられた配列のメンバーに関する最初のインデックスを計算するためにcudaを使用すると問題が発生しました。たとえば、並べ替えられた配列の1つに[1,1,2,2,5,5 、5]、私は0（1の最初のインデックス）、2（最初のインデックス2）、4（最初のインデックス5）を返す必要があります。この問題を解決するためのいくつかの並列方法がありますか？この操作を実行する

Answer 1

一つの可能​​な方法は次のようになります

1. adjacent difference方法は各サブシーケンスの開始を識別するために（各並列スレッドがその要素とその隣に見える）の使用。隣人と比較して差異のない要素は、部分配列の開始ではありません。隣接する要素と異なる要素は、サブシーケンスの開始（または終了、または開始+終了）を表します。

2. 各サブシーケンスの開始が識別されたら、stream compactionメソッドを使用して、指定されたシーケンスを各サブシーケンスの開始を表す要素のシーケンスだけに縮小します。ストリーム圧縮も並行して行うことができ、典型的なアプローチでは、圧縮されたシーケンス内の各要素の宛先アドレスを識別するために、パラレルプレフィックス和を使用することを含む。

上記のアルゴリズムの最初の部分は、CUDAコードを直接書くのはかなり簡単です。 2番目の部分は少し複雑です。なぜならparallel prefix sumは少し書くのが難しいからです。さらに、並列プリフィックス和、並列縮小、並べ替えなどのアルゴリズムに対しては、私はを返すことはありません。はゼロからこれらを書くことをお勧めします。可能であれば、常にライブラリの実装を使用する必要があります。

したがって、the thrust libraryは、CUDAの上に構築された、このようなソリューションのプロトタイプを作成するのは簡単なアプローチを可能ルーチンのセットを提示：

$ cat t1200.cu 
#include <thrust/device_vector.h> 
#include <thrust/copy.h> 
#include <thrust/adjacent_difference.h> 
#include <thrust/iterator/counting_iterator.h> 
#include <iostream> 

typedef int mytype; 

using namespace thrust::placeholders; 

int main(){ 

    mytype data[] = {1,1,2,2,5,5,5}; 
    int dsize = sizeof(data)/sizeof(data[0]); 

    thrust::device_vector<mytype> d_data(data, data+dsize); 
    thrust::device_vector<mytype> d_diffs(dsize); 
    thrust::adjacent_difference(d_data.begin(), d_data.end(), d_diffs.begin()); 
    thrust::device_vector<int> d_result(dsize); 
    int rsize = thrust::copy_if(thrust::counting_iterator<int>(0), thrust::counting_iterator<int>(dsize), d_diffs.begin(), d_result.begin(), _1 > 0) - d_result.begin(); 
    thrust::copy_n(d_result.begin(), rsize, std::ostream_iterator<int>(std::cout, ",")); 
    std::cout << std::endl; 
    return 0; 
} 

$ nvcc -o t1200 t1200.cu 
$ ./t1200 
0,2,4, 
$ 

に応じて処理する必要がある場合がありますさまざまなコーナーケースがあります。入力データの正確な構成。上記のコードは、可能な方法を示すための単純な例です。たとえば、ソートされたシーケンスの最初の要素がゼロまたは負の場合、上記のコードはわずかに変更する必要があります。入力データの最初の要素はで常にサブシーケンスの開始点であるため、copy_ifの使用の直前に、d_diffsの最初の要素を正の値に設定する余分なコード行で扱うことができます。