0

並列のquickosortアルゴリズムを実装しています。過剰な並列スレッドのオーバーヘッドを回避するために、ベクトルサイズが特定のしきい値よりも小さい場合に、並列アルゴリズムを順次アルゴリズムに変換するカットオフ戦略を採用しました。ただし、現在、再帰の深さに基づいてカットオフ戦略を設定しようとしています。つまり、特定の再帰深度に達したときにアルゴリズムを順次回転させたいのです。私は次のコードを採用しましたが、それはうまくいきません。どうすればいいのかわかりません。何か案は？

template <class T>
void ParallelSort::sortHelper(typename vector<T>::iterator start, typename vector<T>::iterator end, int level =0) //THIS IS THE QUICKSoRT INTERFACE
{
  static int depth =0;

  const int insertThreshold = 20;
  const int threshold = 1000;
  if(start<end)
  {
    if(end-start < insertThreshold) //thresholf for insert sort
    {
      insertSort<T>(start, end);
    }
    else if((end-start) >= insertThreshold && depth<threshold) //threshhold for non parallel quicksort
    {
      int part = partition<T>(start,end);
      depth++;
      sortHelper<T>(start, start + (part - 1), level+1);
      depth--;
      depth++;
      sortHelper<T>(start + (part + 1), end, level+1);
      depth--;
    }
    else
    {
      int part = partition<T>(start,end);
      #pragma omp task
      {
        depth++;
        sortHelper<T>(start, start + (part - 1), level+1);
        depth--;
      }
      depth++;
      sortHelper<T>(start + (part + 1), end, level+1);
      depth--;
    }
  }
}

depth静的変数と非静的変数を試しましたlevelが、どちらも機能しません。注：上記の切り取りは、にのみ依存しdepthます。level試行された両方の方法を示すために含まれています

4

2 に答える 2

0

了解しました。わかりました。それは私の側の愚かな間違いでした。

スタックサイズがしきい値よりも大きい場合、アルゴリズムはシーケンシャルコードにフォールバックする必要があります。そうすることで問題が解決し、スピードアップが得られます。

于 2013-03-25T19:46:31.663 に答える
0

static depth2つのスレッドから書き込まれると、それらの書き込みが行うことは指定されていないため、コードは指定されていない動作を実行します。

たまたま、あなたはlevel受け継いでいます。これはあなたの再帰の深さです。各レベルで、スレッド数を2倍にします。したがって、6に等しいレベルの制限（たとえば）は、最大で2^6スレッドに相当します。コードはメインスレッドで発生するため、コードは半分しか並列化partitionされていません。そのため、一度に実行されるスレッドの理論上の最大数よりも少ない可能性があります。

template <class T>
void ParallelSort::sortHelper(typename vector<T>::iterator start, typename vector<T>::iterator end, int level =0) //THIS IS THE QUICKSoRT INTERFACE
{

  const int insertThreshold = 20;
  const int treeDepth = 6; // at most 2^6 = 64 tasks
  if(start<end)
  {
    if(end-start < insertThreshold) //thresholf for insert sort
    {
      insertSort<T>(start, end);
    }
    else if(level>=treeDepth) // only 2^treeDepth threads, after which we run in sequence
    {
      int part = partition<T>(start,end);
      sortHelper<T>(start, start + (part - 1), level+1);
      sortHelper<T>(start + (part + 1), end, level+1);
    }
    else // launch two tasks, creating an exponential number of threads:
    {
      int part = partition<T>(start,end);
      #pragma omp task
      {
        sortHelper<T>(start, start + (part - 1), level+1);
      }
      sortHelper<T>(start + (part + 1), end, level+1);
    }
  }
}
于 2013-03-25T20:27:11.503 に答える