2

これは、プログラミングの問題というよりも、アルゴリズムの問​​題です。プレフィックス合計（または任意の）並列アルゴリズムを変更して、次のことを実現できるかどうか疑問に思っています。GPU上の2つの入力リストからO（N）時間未満で結果を生成したいと思います。

ルールは次のとおりです。キーの同じインデックスに含まれる値が小さくなるまで、データから最初の数値を実行します。

並列スキャンにマッピングしようとすると、現在のキーと比較するのに十分な距離まで運ばれた可能性のある以前のデータを知ることができないため、アップスイープで伝播するデータの値がわからないため、機能しません。 。この問題は、現在のインデックスと過去のすべてのインデックスを考慮する必要があるリップルキャリーを思い出させます。

繰り返しになりますが、並列スキャンのコードは必要ありません（それは素晴らしいことですが）。それがどのように実行できるのか、またはなぜ実行できないのかを理解するためにもっと探します。

int data[N] = {5, 6, 5, 5, 3, 1, 5, 5};
int keys[N] = {5, 6, 5, 5, 4, 2, 5, 5};
int result[N];

serial_scan(N, keys, data, result);
// Print result.  should be {5, 5, 5, 5, 3, 1, 1, 1, }

スキャンをシリアルで実行するためのコードは次のとおりです。

void serial_scan(int N, int *k, int *d, int *r)
{
  r[0] = d[0];
  for(int i=1; i<N; i++) 
    {
      if (k[i] >= r[i-1]) {
        r[i] = r[i-1];
      } else if (k[i] >= d[i]) {
        r[i] = d[i];
      } else {
        r[i] = 0;
      }
    }
}
4

1 に答える 1

0

並列スキャンの一般的な手法は、関数型言語の標準 ML で説明されているここにあります。これは、どの連想演算子でも実行できます。

直感的なポンプの 1 つは、配列の 2 つの半分の合計を再帰的に計算し、それらを加算することで、O(log(n)) スパン (無限プロセッサでの実行時間) で配列の合計を計算できることです。スキャンの計算では、現在のポイントの前の配列の合計を知る必要があります。

2 つの半分を並行して実行する配列のスキャンを計算できます。上記の手法を使用して、前半の合計を計算します。次に、2 つの半分のスキャンを順次計算します。前半は 0 から始まり、後半は前に計算した合計から始まります。完全なアルゴリズムは少し複雑ですが、同じ考え方を使用しています。

別の言語で並列スキャンを実行するための疑似コードを次に示します (int と加算の特定のケースについてですが、論理はどの結合演算子でも同じです)。

//assume input.length is a power of 2

int[] scanadd( int[] input) {
  if (input.length == 1)
    return input 
  else { 
    //calculate a new collapsed sequence which is the sum of sequential even/odd pairs 
    //assume this for loop is done in parallel

    int[] collapsed = new int[input.length/2]
    for (i <- 0 until collapsed.length) 
      collapsed[i] = input[2 * i] + input[2*i+1]

    //recursively scan collapsed values
    int[] scancollapse = scanadd(collapse)

    //now we can use the scan of the collapsed seq to calculate the full sequence

    //also assume this for loop is in parallel
    int[] output = int[input.length]
    for (i <- 0 until input.length) 
      //if an index is even then we can just look into the collapsed sequence and get the value
      // otherwise we can look just before it and add the value at the current index

      if (i %2 ==0) 
        output[i] = scancollapse[i/2]
      else 
        output[i] = scancollapse[(i-1)/2] + input[i]

    return output
  } 
}
于 2013-01-04T19:57:00.463 に答える