6

特定のセットからランダムな順列を生成するために使用できる並列アルゴリズムは何ですか? 特に、CUDA に適した論文への提案やリンクは役に立ちます。

これのシーケンシャル バージョンは、フィッシャー イェーツ シャッフルです。

例：

S={1, 2, ..., 7} をソース インデックスのセットとします。目標は、n 個のランダム順列を並行して生成することです。n 個の順列のそれぞれには、{7, 6, ..., 1} のように、各ソース インデックスが 1 回だけ含まれます。

4

3 に答える 3

17

Fisher-Yates シャッフルは並列化できます。たとえば、4 つの同時ワーカーは、8 要素のベクトルをシャッフルするのに 3 回の反復しか必要としません。最初の反復では、0<->1、2<->3、4<->5、6<->7 を交換します。2 回目の繰り返しでは 0<->2、1<->3、4<->5、6<->7; 最後の反復では、0<->4、1<->5、2<->6、3<->7 です。

ParallelFisherイェイツ

これは、CUDA コードとして簡単に実装できます (標準の最小/最大削減__device__に触発されました)。

const int id  = threadIdx.x;
__shared__ int perm_shared[2 * BLOCK_SIZE];
perm_shared[2 * id]     = 2 * id;
perm_shared[2 * id + 1] = 2 * id + 1;
__syncthreads();

unsigned int shift = 1;
unsigned int pos = id * 2;  
while(shift <= BLOCK_SIZE)
{
    if (curand(&curand_state) & 1) swap(perm_shared, pos, pos + shift);
    shift = shift << 1;
    pos = (pos & ~shift) | ((pos & shift) >> 1);
    __syncthreads();
}

ここでは curand 初期化コードが省略され、メソッドは値と をswap(int *p, int i, int j)交換します。p[i]p[j]

上記のコードには、次の前提があることに注意してください。

  1. 順列の長さは 2 * BLOCK_SIZE で、BLOCK_SIZE は 2 の累乗です。
  2. __shared__2 * CUDA デバイスのメモリに収まる BLOCK_SIZE 整数
  3. BLOCK_SIZE は CUDA ブロックの有効なサイズです (通常は 32 から 512 の間)

複数の順列を生成するには、異なる CUDA ブロックを利用することをお勧めします。目標が7つの要素の順列を作成することである場合(元の質問で言及されているように)、シングルスレッドで実行する方が高速になると思います。

于 2013-01-05T20:30:50.610 に答える
1

s = s_Lの長さの場合、これを行う非常に大雑把な方法を推力で実装できます。

http://thrust.github.com。

まず、sn回繰り返す長さs_Lxnのベクトルvalを作成します。

ベクトルを作成しますval_keysは、s_L回繰り返されるn個の一意のキーをvalの各要素に関連付けます。

  val = {1,2,...,7,1,2,...,7,....,1,2,...7}
  val_keys = {0,0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,...., n,n,n}

今、楽しい部分です。長さs_Lxnの一様分布確率変数のベクトルを作成します

  U  = {0.24, 0.1, .... , 0.83}

次に、val、val_keysに対してzipイテレータを実行し、Uに従って並べ替えることができます。

http://codeyarns.com/2011/04/04/thrust-zip_iterator/

両方のval、val_keysがいたるところにあるため、thrust :: stable_sort_by_key（）を使用してそれらを元に戻し、val[i]とval[j]の両方がkey[k]とvalに属していることを確認する必要があります。 [i]はランダムソートに続いてval[j]の前にあり、最終バージョンではval[i]はまだval[j]の前にあるはずです。すべてが計画どおりに進んだ場合、val_keysは以前と同じように見えるはずですが、valはシャッフルを反映している必要があります。

于 2012-11-02T23:18:11.747 に答える