1

CUDA で CUDPP を使用してセグメント化された並べ替えを行うことは可能ですか? セグメント化ソートとは、以下のようなフラグで保護された配列の要素をソートすることを意味します。 

A[10,9,8,7,6,5,4,3,2,1]

Flag array[1,0,1,0,0,1,0,0,0,0]

連続する 1 の間にある A の要素を並べ替えます。
期待される出力 

[9,10,6,7,8,1,2,3,4,5]
4

1 に答える 1

6

単一のソートパスでこれを行うことができます。アイデアは、ソートが「セグメント」内でのみ要素を再配置するように配列内の要素を調整することです

あなたの例のために：

A[10,9,8,7,6,5,4,3,2,1]
flag[0,0,1,0,0,1,0,0,0,0]

(最初の 1 つは不要なので削除しました)

最初にフラグ配列をスキャンします。

scanned_flag[0,0,1,1,1,2,2,2,2,2]

次に、数値タイプに応じて多くのオプションがあります。たとえば、符号なし整数の場合、「セグメント」を区別するために最上位ビットを設定できます。最も簡単な方法は、scanned_flags を掛けた最大の要素を追加することです。

A + scanned_flag*10 = [10,9,18,17,16,25,24,23,22,21]

残りは簡単です。配列をソートし、変換を逆にします。ここに 2 つのバージョンがあります: Arrayfire と推力を使用します。好きな方にチェックを入れてください。

アレイファイア:

void af_test() {
 int A[] = {10,9,8,7,6,5,4,3,2,1};  
 int S[] = {0, 0,1,0,0,1,0,0,0,0};  
 int n = sizeof(A) / sizeof(int);

 af::array devA(n, A, af::afHost);
 af::array devS(n, S, af::afHost);
 // obtain the max element
 int maxi = af::max< int >(devS);

 // scan the keys
 // keys = 0,0,1,1,1,2,2,2,2,2
 af::array keys = af::accum(devS);

 // compute: A = A + keys * maxi
 // A = 10,9,18,17,16,25,24,23,22,21
 devA = devA + keys * maxi;

 // sort the array
 // A = 9,10,16,17,18,21,22,23,24,25
 devA = af::sort(devA);

 // compute: A = A - keys * maxi
 // A = 9,10,6,7,8,1,2,3,4,5
 devA = devA - keys * maxi;
 // print the results
 print(devA);
}

スラスト:

template<typename T>
struct add_mul : public binary_function<T,T,T>
{
add_mul(const T& _factor) : factor(_factor) {
}
   __host__ __device__ T operator()(const T& a, const T& b) const 
{
    return (a + b * factor);
}
const T factor;
}; 

void thrust_test()
{
  int A[] = {10,9,8,7,6,5,4,3,2,1};  
  int S[] = {0, 0,1,0,0,1,0,0,0,0};  
  int n = sizeof(A) / sizeof(int);
  thrust::host_vector< int > hA(A, A + n), hS(S, S + n);

  thrust::device_vector< int > devA = hA, devS = hS, keys(n);
  // scan the keys 
  thrust::inclusive_scan(devS.begin(), devS.end(), keys.begin());
  // obtain the maximal element
  int maxi = *(thrust::max_element(devA.begin(), devA.end()));
  // compute: A = A + keys * maxi
  thrust::transform(devA.begin(), devA.end(), keys.begin(), devA.begin(), add_mul< int >(maxi)); 
  // sort the array
  thrust::sort(devA.begin(), devA.end());
  // compute: A = A - keys * maxi
  thrust::transform(devA.begin(), devA.end(), keys.begin(), devA.begin(), add_mul< int >(-maxi)); 
  // copy back to the host 
  hA = devA;
  std::cout << "\nSorted array\n";
  thrust::copy(hA.begin(), hA.end(), std::ostream_iterator<int>(std::cout, "\n"));
}
于 2012-11-22T17:33:26.610 に答える