OpenMP FFT 속도 올리기

Question

다항식 곱셈을위한 재귀 FFT algortihm을 가지고 있으며 openmp로 병렬 처리해야합니다. 일부 주위에 연구와 시도 후까지만 내가 작업을 제거 할 때, 단 2 스레드가 동시에 각 polynom를 계산됩니다 할 수있는 속도를, 나는이

Complex * multiply(Complex *p1, Complex *p2) 
{ 
#pragma omp parallel 
{ 
//evaluate p1 
#pragma omp single nowait 
pFFT(n,p1,1); 

#pragma omp single nowait 
pFFT(n,p2,1); 
} 

//...multiply part etc 

} 

void pFFT(int deg, Complex *pol,int sign) 
{ 
if(deg == 1) 
    return; 

//divide polynom into two parts with even and odd coeficients 
Complex *even = new Complex [deg/2]; 
Complex *odd = new Complex [deg/2]; 


for(int i = 0;i<deg/2;i++) 
{ 
    even[i] = pol[2*i]; 
    odd[i] = pol[2*i+1]; 
} 


#pragma omp task 
pFFT(deg/2,even,sign); 
#pragma omp task 
pFFT(deg/2,odd,sign); 
#pragma omp taskwait 
//wn = n-th root of unity 
int x = lg2(deg); 
Complex wn; 
wn.re = pcos[x]; 
wn.im = sign*psin[x]; 
Complex w; 
w.re = 1; 
w.im = 0; 
Complex *ret = pol; 

Complex product; 
if(deg==2) 
{ 
     product = mul(odd,&w); 
     ret[0].re = even[0].re+product.re; 
     ret[0].im = even[0].im+product.im; 
     ret[1].re = even[0].re-product.re; 
     ret[1].im = even[0].im-product.im; 
} 
else 
    for(int i = 0;i<deg/2-1;i+=2) 
    { 
     product = mul(odd+i,&w); 
     ret[i].re = even[i].re+product.re; 
     ret[i].im = even[i].im+product.im; 
     ret[i+deg/2].re = even[i].re-product.re; 
     ret[i+deg/2].im = even[i].im-product.im; 
     w = mul(&w,&wn); 
     product = mul(odd+i+1,&w); 
     ret[i+1].re = even[i+1].re+product.re; 
     ret[i+1].im = even[i+1].im+product.im; 
     ret[i+1+deg/2].re = even[i+1].re-product.re; 
     ret[i+1+deg/2].im = even[i+1].im-product.im; 
     w = mul(&w,&wn); 
    } 
delete[] even; 
delete[] odd; 
} 

에 도착하지만 코드가 순차적 버전보다 더 느립니다. 나는 많은 기억이 있지만 아직도해야 할 일이 있다는 것을 이해한다. 당신보다.

Answer 1

이전에 병렬 처리를 중단해야합니다. 크기 16, 64, 256으로 시도하십시오. 크기 2에서 중지하면 상대적으로 큰 오버 헤드가있는 너무 많은 작은 작업이 생성됩니다.