OpenMP遞歸比沒有線程慢

Question

我試圖在Karatsuba的多項式乘法中並行化遞歸。但它比沒有線程更慢。有什麼問題 我有這樣的代碼：

int karatsubaMain(int size) 
{ 
    Polynom pol1(size),pol2(size); 
    omp_set_num_threads(8); 
    double start = omp_get_wtime(); 
    int* result = mult(pol1.polynom,pol2.polynom,0,pol1.size); 
    double end = omp_get_wtime(); 
    printf("%f ", end - start); 
    return 0; 
} 

int * mult(int*a, int *b,int start, int N){ 
    int * c= new int[2*N-1]; 
    if(N==1){ 
     c[0]=a[start]*b[start]; 
     return c; 
    } 
    int * t1= new int[N/2]; 
    int * t2= new int[N/2]; 
    int * cM,*cL,*cH; 
    for(int i=0;i<N/2;i++){ 
     t1[i]=a[start +i]+a[start + i + N/2]; 
     t2[i]=b[start +i]+b[start + i + N/2 ]; 
    } 
    #pragma omp parallel shared(cM,cL,cH) 
    { 
    #pragma omp single nowait 
    { 
    #pragma omp task if(N > 4096) 
    cM=mult(t1,t2,0,N/2); 
    #pragma omp task if(N > 4096) 
    cL=mult(a,b,0,N/2); 
    #pragma omp task if(N > 4096) 
    cH=mult(a,b,N/2,N/2); 
    } 
    #pragma omp taskwait 
    } 
    c[N-1]=0; 
    for(int i=0;i<N-1;i++){ 
     c[i]=cL[i]; 
     c[N+i]=cH[i]; 
     c[N/2+i]+=(cM[i]-(cL[i]+cH[i])); 
    } 
    delete []t1; 
    delete []t2; 
    delete []cM; 
    delete []cL; 
    delete []cH; 
    return c; 
} 

Answer 1

首先我告訴你做什麼，你懂的變化更好：你這樣做

在每一步中：

#pragma omp parallel shared(cM,cL,cH) //open a new parallel region (ie create threads) 
{ 
    #pragma omp single nowait //only one thread should do the following 
    { 
    #pragma omp task if(N > 4096) //create task 
    cM=mult(t1,t2,0,N/2); 
    #pragma omp task if(N > 4096) //create task 
    cL=mult(a,b,0,N/2); 
    #pragma omp task if(N > 4096) //create task 
    cH=mult(a,b,N/2,N/2); 
    } //after this line all threads are working on the same 
    #pragma omp taskwait //before executing further the tasks should be finished 
} // close all threads created at this parallel 

你有意做：

創建一些線程，一旦創建了遞歸的根，每次遞歸調用都是一個任務，都應該在tas上工作KS，當所有的子任務完成後計算的結果，採取新的任務

在karatsubaMain()你應該再創建線程，然後一個線程插入根任務：

double start = omp_get_wtime(); 
int* result; 

#pragma omp parallel shared(result, a, b, size) 
{ 
    #pragma omp single //also #pragma omp master usable here 
    result = mult(a, b, 0, size); 
} 
double end = omp_get_wtime(); 

在mult()你只shoudl自創建任務該區域已經被不同的線程並行地處理：

for(int i = 0; i < N/2; i++) 
{ 
    t1[i] = a[start + i] + a[start + i + N/2]; 
    t2[i] = b[start + i] + b[start + i + N/2 ]; 
} 
#pragma omp task shared(cM) if(N > 4096) 
cM = mult(t1, t2, 0, N/2); 
#pragma omp task shared(cL) if(N > 4096) 
cL = mult(a, b, 0, N/2); 
#pragma omp task shared(cH) if(N > 4096) 
cH = mult(a, b, N/2, N/2); 
#pragma omp taskwait 

c[N - 1] = 0; 

以這種方式我能夠約15％，相對於加速代碼（多項式的INT-陣列INSEAD）的簡化版本，以sequen

tial代碼。

一般說法：大多數情況下，不建議使用嵌套並行區域