1

O(N^7) の時間計算量を持つプログラムの最適化に取り組んでいます。32 ビット整数として表される文字列の配列があり、各ビットは入力文字列の特定の文字に対応しています。仕事は、入力文字列のすべての組み合わせを見つけることです。各文字は 1 回だけ存在し、すべての文字が存在します。単純なソリューションには、7 つの層の再帰が必要であり、各層はリスト全体を反復します。これはすぐに非常に遅くなります。

そのため、cuda を使用してプロセスを少し高速化できるかどうか疑問に思っていました。GPU に可能な文字列の配列と、一致してはならないビットマスクを供給し、フィルター処理されたリストを取得することで、少し再帰的なステップ。

問題は、この種のフィルタリングは並列処理に適しているかということです。

私が現在 C で行っていることを以下に説明します。

void recursive_search (unsigned int used, unsigned int *list, int listlen,
                       int start,unsigned int * stack, int reclevel) {
  int index, newindex;
  newindex = 0;

  for (index=0; index< listlen; index++) {
    if (!list[index] & used) {
      newlist[newindex++] = list[index];
    }
  }      

  if ((newindex == 1 && (used | newlist[0])) == 0xffffffff) {
    /* Hooray! We have a match */
    stack[reclevel] = newlist[0];
    report_match(stack);
    return;
  }

  for (index = 0;index < newindex; index++) {
    recursive_search (used | newlist[index], newlist, newindex,
                      index, stack, reclevel + 1);
  }
}

これで私の質問が明確になることを願っています。

4

1 に答える 1

1
  1. 完全なアルゴリズムを単一のカーネルに変換しようとしないでください。各ステップを 1 つずつ並列化してみてください。

以下のコード セクションは、copy_if ステートメントに変換できます。

for (index=0; index< listlen; index++) {
    if (!list[index] & used) {
        newlist[newindex++] = list[index];
    }
}

そして、ステートメントは次のようになります

thrust::copy_if(list.begin(), list.end(), newlist.begin(), predicate());

したがって、新しいリストを簡単に達成できます。

GPU で可能な文字列の配列を生成できますか?

再帰について:

  • GPU で非常に多くのスレッドがアクティブになるため、複数の結果/一致が発生する可能性があります。最初の一致、またはすべての一致を返すことが問題になる場合があります。
  • 再帰が必要な場合は、部分的な進行状況を毎回グローバル メモリに保存することで、カーネルを数回呼び出すことができます。
  • @harrism が示したように、再帰部分をより単純なフローに変換し、並列処理でそれぞれのケースを処理できるようにすることができます。
于 2012-10-08T12:37:02.013 に答える