Community
cancel
Showing results for 
Search instead for 
Did you mean: 
Semen_K_
Beginner
132 Views

OpenMP* Threading for FFT Computation

 

Dear Sir/Madam,

As I understood from an example on https://software.intel.com/en-us/mkl-developer-reference-c-examples-of-using-openmp-threading-for-ff..., you calculate with 4 threads 4 different 2D-FFT (50x100 points). My question is - is it possible to calculate NxN FFT where I divide data between 2 processors where each will get NxM FFT and NXK FFT where M+K = N? I worry about the result, is it will be correct by following your example? Also, how do you do it inside and how I can apply it to fftw?

Thanks,
Sem  

0 Kudos
12 Replies
MGRAV
New Contributor I
132 Views

I don't kwon if it answer to your question.

But if you use the fftw interface the function you are looking for is probably 

fftw_plan_with_nthreads(int nthreads);

 

Semen_K_
Beginner
132 Views


Hi Mathieu,

Thanks for your reply, but it is not exactly what I needed. Actually, I want to calculate, for instance, one part of 2D FFT on one socket and another part 2D FFT on another socket, after this to combine them in one that is will be correct. Like - FFT = FFT[0, N/2-1] + FFT[N/2, N].

Thanks,
Sem

Ying_H_Intel
Employee
132 Views

Hi Sem, 

Yes, the example on https://software.intel.com/en-us/mkl-developer-reference-c-examples-of-u..., you calculate with 4 threads 4 different 2D-FFT (50x100 points). 

is it possible to calculate NxN FFT where I divide data between 2 processors where each will get NxM FFT and NXK FFT where M+K = N?

From MKL FFT point of views,  we take the problem as below you expected to do NxN FFT on 2 processors.   Actually, both MKL FFT and FFTW support internal multi-threads,  which means ,  MKL FFT or FFTW will use the existing processors (2 here) and distribute the compute tasks of NXN FFT to mult-threads to compute and then return the correct result. then developer don't need take care of how to seperate the task.  

What is your N size? Please see mkl use guide to check if the 2D FFT are  multi-threaded  in https://software.intel.com/en-us/mkl/documentation

Best Regards,

Ying  

Semen_K_
Beginner
132 Views


Hi Ying,

Thanks. My N can be 1024 and so on till 48540. I do not get how you combine the result in the end. I have checked and my result is not exactly correct when I calculated following by your method. I devide N*N/2, so one socket with 18 threads has N*N/2 data and another has also N*N/2. When I checked the result, it was incorrect. So, if you are saying that it is correct way to do one FFT by deviding it on different sockets, then I think I did some mistake, I need to check it again. 

Thanks,
Sem

Ying_H_Intel
Employee
132 Views

Hi Sem,

Sorry for unclear reply. I mean, you can call N (1024, 48540) FFT directly. You don't have to divide the data yourself.  MKL will distribute the compute tasks in two socket automatically.

Best Regards,

Ying

Semen_K_
Beginner
132 Views


Hi, Ying,

Yes, I know and thanks again but I want to be able to manage data between threads and sockets by myself. This is why I have such kind of question.

Thanks,
Sem

Ying_H_Intel
Employee
132 Views

Hi Sem,

Get it. then you may  want to implement one mult-thread FFT by parallel method actually.  then you may refer to the source code of FFTW multhreads or on-line source like https://www.codeproject.com/Questions/706613/How-To-Write-an-FFT-Algorithm-With-Thread.

Best Regards,

Ying

Semen_K_
Beginner
132 Views


Hi Ying,

Thank you. I thought I can just use your function. Another way to do it I think with MPI, do you have some example mkl fftw with MPI? Or you don't use them together?

Thanks,
Sem

MGRAV
New Contributor I
132 Views

I am not sure to understand well, but you can still write you 2D FFT with two set of 1D FFTs, basically 2D FFT is a FFT along one axis and after the second one. (If you do R2C the first one is R2C and after you have C2C along teh second axis ).

And if you like you can still write, you set of 1D FFT as 2 subset (n/2 first one lines and n/2 last one lines) and the same after with columns. I use this decomposition when I know that a line is only with zeros I don't compute it, that gives me the opportunity to win some small % of computation.

If you do it over two sockets, the (manuel) memory management can be problematic (at least complex), if you look at the algorithm that is a divide and conquer, you will see that at the last step you need memory of both sides.

Ying_H_Intel
Employee
132 Views

Hi Sem,

MKL provide Cluster FFT, which support MPI. It allows you to manage data between MPI threads and sockets by yourself.  You can refer to MKL user guide and https://software.intel.com/en-us/mkl-linux-developer-guide-linking-with-intel-mkl-cluster-software  ; and MKL provide the sample code under <install Dir /examples>

​Agree with Mathieu, there are some ways to parallel the FFT.  But the manual memory management can be problematic if your purpose here is get higher performance N FFT result, but not how to write a FFT multithread code.

Best Regards,
Ying

Semen_K_
Beginner
132 Views


Hi Mathieu,

Thanks, yes, actually I am doing this way now. I thought there is a way to do it without transpose but just to sum results somehow from two parts of 2D FFT.

Hi Ying,

Thanks too, I have checked but did not find any example of implementation of mpi. Ok, I can do MPI + Multithreading in fftw, but would be good if the same I can do in mklfft. 

Thanks,
Sem

MGRAV
New Contributor I
132 Views

Transpose ? What are you transposing ? Can you not just use the stride option ?

have maybe a look one : http://www.fftw.org/fftw3_doc/Advanced-Complex-DFTs.html

 

Basically, it looks like:

1) first compute the lines, that I suppose is ok

2) compute column-wise 

    fftw_plan_many_dft(1, numberOfLines, numberOfColumn,

                in, numberOfLines,

                numberOfColumn, 1,

                out, numberOfLines,

                numberOfColumn, 1,

                FFTW_FORWARD, FFTW_PLAN_OPTION);

    if you do C2C it's ok, if you do R2C you need to transform numberOfColumn in numberOfColumn/2+1, or something like that. I let you find out check that.

3) nothing else.

 

PS: I hope what I write is right ;)

PPS: in = out is fine too !

Reply