djhaxton
commented
9 years ago An alternative, something that I will try first -- but I will not try this for a while, I don't think -- is to implement MPI Cooley Tukey. Cooley Tukey is the FFT algorithm in which a fourier transform of a vector NM long is decomposed into N M-long FTs which are then assembled into the NM-long FT using what are called "twiddle factors."
https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm
Doing the recursive Cooley-Tukey algorithm with MPI seems natural but this is not the way Khaled and Thorsten suggested. They suggested the method with three all-to-alls, the current method, with three batches of one-dimensional FFTs.
Getting Intel MPI 3D FFT going would be great. But we might be able to do just as well and have a code that compiles on machines without intel MPI FFT. The ultimate algorithm might speed up the code substantially. This is because a near optimal 1D MPI FFT in the z direction for the kinetic energy operator might enable the Toeplitz trick (1D) to beat the usual matvec. That would mean that MPI Cooley Tukey might speed up both the two-electron operator, the triple toeplitz matvec, and kinetic energy via single toeplitz matvec. Hypothetically, this could mean a big speedup, for huge problems. Replacing all-to-all with sendrecv seems like a great idea.
The algorithm for MPI Cooley Tukey would presumably substantially follow that in the kinetic energy matrix vector multiplication routine mult_circ_z(). N=nprocs. The twiddle factors, a matrix NM x NM x M big, are raised to successive powers each time deltaproc is incremented, they are multiplied by the local 3D FFT NM x NM x M big, then the result is communicated via sendrecv, and the results are summed to produce the local NM x NM x M block of the NM x NM x NM fourier transform.
At the very least, just with the two-electron operator, triple toeplitz matvec, I think this will give us a speedup of three, going from::
3 x ( 1D intel fft , all-to-all permutation of indices ) to::
1 x [ 3D intelfft, (N-1) x (multiply twiddle factors then sendrecv) ]Programming MPI Cooley Tukey is on my list, but I am not going to get to it soon. At the least, it is interesting to think about!
ZBWalters
Folks,
This is a double-post -- it also occurs in the TO-DO wiki, because it is a big important issue.
However surely very little work needs to be done, to get it working. It is not difficult, surely, if you know what you are doing. I don't.
I have not yet had success with this. I expect significant speedup, perhaps x3 with intel MPI 3D FFT, as opposed to the current intel 1D FFT + transpose + all-to-all, three times over, the current method. Subroutine mytranspose will not be called.
Note
COMPDIRS/notbin.ecs.hermnorm.law.mpifft
and the -D MPIFFTW flag that occurs in its Makefile.header.