3

OPENMP を使用してマージソート用に C で並列コードを実装しました。私は 3.9 秒の速度アップを取得します。これは、同じコードのシーケンシャル バージョン (3.6 を取得する) よりもかなり遅いです。コードを可能な限り最適な状態に最適化しようとしていますが、速度を上げることはできません。これを手伝ってもらえますか？ありがとう。

 void partition(int arr[],int arr1[],int low,int high,int thread_count)
 {
int tid,mid;

#pragma omp if
if(low<high)
{
    if(thread_count==1)
    {
            mid=(low+high)/2;
            partition(arr,arr1,low,mid,thread_count);
            partition(arr,arr1,mid+1,high,thread_count);
                sort(arr,arr1,low,mid,high);
    }
    else
    {
        #pragma omp parallel num_threads(thread_count) 
        {
                mid=(low+high)/2;
                #pragma omp parallel sections  
                {
                    #pragma omp section
                    {
                        partition(arr,arr1,low,mid,thread_count/2);
                        }
                    #pragma omp section
                    {   
                        partition(arr,arr1,mid+1,high,thread_count/2);
                    }
                }
        }
        sort(arr,arr1,low,mid,high);

    }
}
 }
4

2 に答える 2

3

正しく指摘されたように、コードには正しい実行を妨げるいくつかの間違いがあるため、まずこれらのエラーを確認することをお勧めします。

とにかく、OpenMP のパフォーマンスがスレッドに応じてどのようにスケーリングするかのみを考慮すると、タスク ディレクティブに基づく実装は、以前の回答ですでに指摘されている制限を克服するため、より適している可能性があります。

セクション ディレクティブには 2 つのセクションしかないため、parallel 句で 2 つより多くのスレッドを生成してもメリットはないと思います

このような実装の痕跡を以下に示します。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <sys/time.h>

void getTime(double *t) {

  struct timeval tv;

  gettimeofday(&tv, 0);
  *t = tv.tv_sec + (tv.tv_usec * 1e-6);
}

int compare( const void * pa, const void * pb ) {

  const int a = *((const int*) pa);
  const int b = *((const int*) pb);

  return (a-b);
}

void merge(int * array, int * workspace, int low, int mid, int high) {

  int i = low;
  int j = mid + 1;
  int l = low;

  while( (l <= mid) && (j <= high) ) {
    if( array[l] <= array[j] ) {
      workspace[i] = array[l];
      l++;
    } else {
      workspace[i] = array[j];
      j++;
    }
    i++;
  }
  if (l > mid) {
    for(int k=j; k <= high; k++) {
      workspace[i]=array[k];
      i++;
    }
  } else {
    for(int k=l; k <= mid; k++) {
      workspace[i]=array[k];
      i++;
    }
  }
  for(int k=low; k <= high; k++) {
    array[k] = workspace[k];
  }
}

void mergesort_impl(int array[],int workspace[],int low,int high) {

  const int threshold = 1000000;

  if( high - low > threshold  ) {
    int mid = (low+high)/2;
    /* Recursively sort on halves */
#ifdef _OPENMP
#pragma omp task 
#endif
    mergesort_impl(array,workspace,low,mid);
#ifdef _OPENMP
#pragma omp task
#endif
    mergesort_impl(array,workspace,mid+1,high);
#ifdef _OPENMP
#pragma omp taskwait
#endif
    /* Merge the two sorted halves */
#ifdef _OPENMP
#pragma omp task
#endif
    merge(array,workspace,low,mid,high);
#ifdef _OPENMP
#pragma omp taskwait
#endif
  } else if (high - low > 0) {
    /* Coarsen the base case */
    qsort(&array[low],high-low+1,sizeof(int),compare);
  }

}

void mergesort(int array[],int workspace[],int low,int high) {
  #ifdef _OPENMP
  #pragma omp parallel
  #endif
  {
#ifdef _OPENMP
#pragma omp single nowait
#endif
    mergesort_impl(array,workspace,low,high);
  }
}

const size_t largest = 100000000;
const size_t length  = 10000000;

int main(int argc, char *argv[]) {

  int * array = NULL;
  int * workspace = NULL;

  double start,end;

  printf("Largest random number generated: %d \n",RAND_MAX);
  printf("Largest random number after truncation: %d \n",largest);
  printf("Array size: %d \n",length);
  /* Allocate and initialize random vector */
  array     = (int*) malloc(length*sizeof(int));
  workspace = (int*) malloc(length*sizeof(int));
  for( int ii = 0; ii < length; ii++)
    array[ii] = rand()%largest;
  /* Sort */  
  getTime(&start);
  mergesort(array,workspace,0,length-1);
  getTime(&end);
  printf("Elapsed time sorting: %g sec.\n", end-start);
  /* Check result */
  for( int ii = 1; ii < length; ii++) {
    if( array[ii] < array[ii-1] ) printf("Error:\n%d %d\n%d %d\n",ii-1,array[ii-1],ii,array[ii]);
  }
  free(array);
  free(workspace);
  return 0;
}

パフォーマンスを追求する場合は、再帰関数呼び出しによる実質的なオーバーヘッドを回避するために、再帰の基本ケースが十分に粗いことも保証する必要があることに注意してください。それ以外に、どの部分を最適化する価値があるかについて良いヒントを得ることができるように、コードをプロファイリングすることをお勧めします。

于 2012-09-16T17:28:55.667 に答える
2

少し恥ずかしいですが、それを見ると答えはとても簡単です。

質問にあるように、プログラムは正しく動作しません。代わりに、いくつかの実行でランダムにいくつかの数字が複製され、他の数字が失われます。これは、変数 thread_count == 1 を使用してプログラムを実行した場合には発生しない、完全に並列エラーのようです。

プラグマ「並列セクション」は、並列とセクションを組み合わせたディレクティブであり、この場合、前の領域内で 2 番目の並列領域を開始することを意味します。他の並列領域内の並列領域は問題ありませんが、ほとんどの実装では、ネストされた並列領域に遭遇したときに余分なスレッドが提供されないと思います。

修正は交換です

 #pragma omp parallel sections

と

 #pragma omp sections

この修正の後、プログラムは正しい答えを出し始め、2 つのコア システムと 100 万の数字の場合、次の結果のタイミングを取得します。

1 つのスレッド:

time taken: 0.378794

2 つのスレッド:

time taken: 0.203178

セクション ディレクティブには 2 つのセクションしかないため、parallel 句で 2 つ以上のスレッドを生成してもメリットはないと思います。そのため、num_threads(thread_count) -> num_threads(2) を変更します。

しかし、少なくとも私が試した 2 つの実装では、入れ子になった並列領域に対して新しいスレッドを生成することができないため、現状のプログラムは 2 つ以上のスレッドに拡張できません。

于 2012-09-16T16:16:14.627 に答える