Bessere Methode zur Verbesserung der parallelen bitonischen Sortierung

Question

Ich versuche meine vorhandene bitonische Sortierung zu verbessern, indem ich ihre Ausführungszeit reduziere und sie funktioniert in einigen Fällen, aber nicht in allen Fällen. Zum Beispiel für kleine Arrays mit einer Größe von 20 ist die optimierte Zeit besser, aber für große Arrays mit Größen von 10.000+ haben sie die gleiche Ausführungszeit die Hälfte der Zeit und die andere Hälfte der optimierten Version ist schneller. Das habe ich:
Nthreads wurde global deklariert und entspricht 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

Wie geschrieben, laicht jeder rekursiven Aufruf zwei neue Themen, so dass die Anzahl der Threads steigt exponentiell. omp_set_nested

Sie müssen veranlassen, dass die parallele Version nur auf den obersten Rekursionsebenen aufgerufen wird. Ich vermute, du willst nur Nthreads-1 neue Threads spawnen. Wenn Sie eine MCVE veröffentlichen würden, könnten wir es beheben.