並列ビートソートを改善するより良い方法

Question

私は既存のビートソートを改善するために、その実行時間を短縮して、いくつかのケースでは動作しますが、すべてではありません。たとえば、20のようなサイズの小さな配列の場合、最適化された時間はより良いですが、10,000以上の大きさの配列の場合は、実行時間が半分になり、残りの半分が最適化されます。これは私が持っているものです：
Nthreadsは、グローバルに宣言されました。4です。

void parallel_bitonicSort(int a[], int low, int cnt, int dir)    
{ 
    if (cnt > 1) 
    { 
     int k = cnt/2; 
     omp_set_nested(1); 
     #pragma omp parallel sections 
     { 
      #pragma omp section 
       parallel_bitonicSort(a, low, k, 1);  // sort in ascending order since dir here is 1 
      #pragma omp section 
       parallel_bitonicSort(a, low + k, k, 0); // sort in descending order since dir here is 0 
     } 
     bitonicMerge(a, low, cnt, dir);     // Will merge whole sequence in ascending order since dir=1. 
    } 
} 

void Opt_parallel_bitonicSort(int a[], int low, int cnt, int dir) // optimized version 
{ 
    if (cnt > 1) 
    { 
     int k = cnt/2; 
     omp_set_nested(1); 
     #pragma omp parallel sections num_threads(Nthreads)  
     { 
      #pragma omp section   
       Opt_parallel_bitonicSort(a, low, k, 1); 
      #pragma omp section  
       Opt_parallel_bitonicSort(a, low + k, k, 0); 
     } 
     bitonicMerge(a, low, cnt, dir); 
    } 
} 

Answer 1

このように、すべての再帰呼び出しで2つの新しいスレッドが生成されるため、スレッド数は指数関数的に増加します。 omp_set_nested

並列バージョンは、再帰の最上位レベルでのみ呼び出すように調整する必要があります。あなたはNthreads-1の新しいスレッドだけを生成したいと思う。 MCVEを投稿する場合は修正することができます。