From: Jim Fairman
Date: 20 January 2012 17:37
New Fourier transform algorithm supposedly improves the speed of Fourier transforms get up to "a tenfold increase in speed" depending upon circumstances. Hopefully this will get incorporated into our refinement programs.
----------
From: Nat Echols
Perhaps if source code were available (freely and without
restrictions)... although I don't know enough theory to tell whether
this is applicable to X-ray crystallography or not. However, because
of the way most programs are structured it is unlikely to make a huge
difference in refinement speed in any case - maybe 25% faster, but
certainly not an order of magnitude.
-Nat
----------
From: Ethan Merritt
This report is interesting, but it is not immediately obvious to me that
crystallographic transforms are in the class of problems for which
this algorithm is applicable.
From reading the very non-technical article linked above, I conclude that
a better summary would be "New approach to Fourier approximation provides
a very cheap (fast) way of identifying and then discarding components that
contribute very little to the signal". In other words, it seems to be a
way of increasing the compression ratio for lossy image/audio compression
without increasing the amount of time required for compression.
So if you're doing map fitting while listening to streamed mp3 music
files, perhaps your map inversion will get a slightly larger slice of
the CPU time relative to LastFM.
On the other hand, it is possible that somewhere in here lies a clever
approach to faster solvent flattening.
Ethan
----------
From: Bosch, Juergen
----------
From: George Sheldrick
From the rather non-technical inofrmation available so far, it seems to me that it is like leaving out all but the strongest reflections (or perhaps the strongest normalized structure factors). This is unlikely to improve the quality of structure refinement, the importance of using as much data as possible and not leaving out the weakest reflections has often been emphasized. This is quite different to data compression of music. However there is one case where we are already doing this, namely small molecule direct methods or using the same programs to find the heavy atoms in SAD and MAD experiments. These programs use only the strongest 15-20% of the normalized structure factors (E-values). This is possible because the data to parameter ratio is still sufficient, and these reflections contain much of the useful information. However the Fourier routines used by these programs (at least the ones I wrote) are not taking full advantage of the 'sparseness' of the data, so if the MIT people have found a clever way of doing this it might still be useful for heavy atom location (though FFTW and the Intel MKL FFT will be difficult to beat).
George
----------
From: Philippe DUMAS
For all those interested in the technical details about this new Fourier stuff, I saw that the whole paper is available from the web site, not only the simplified account (look at right of this awfully wrong 3-term Fourier synthesis illutration that I would never show to beginners!)
P. Dumas
Date: 20 January 2012 17:37
New Fourier transform algorithm supposedly improves the speed of Fourier transforms get up to "a tenfold increase in speed" depending upon circumstances. Hopefully this will get incorporated into our refinement programs.
http://web.mit.edu/newsoffice/2012/faster-fourier-transforms-0118.html
--
Jim Fairman, Ph D.
Jim Fairman, Ph D.
----------
From: Nat Echols
Perhaps if source code were available (freely and without
restrictions)... although I don't know enough theory to tell whether
this is applicable to X-ray crystallography or not. However, because
of the way most programs are structured it is unlikely to make a huge
difference in refinement speed in any case - maybe 25% faster, but
certainly not an order of magnitude.
-Nat
----------
From: Ethan Merritt
This report is interesting, but it is not immediately obvious to me that
crystallographic transforms are in the class of problems for which
this algorithm is applicable.
From reading the very non-technical article linked above, I conclude that
a better summary would be "New approach to Fourier approximation provides
a very cheap (fast) way of identifying and then discarding components that
contribute very little to the signal". In other words, it seems to be a
way of increasing the compression ratio for lossy image/audio compression
without increasing the amount of time required for compression.
So if you're doing map fitting while listening to streamed mp3 music
files, perhaps your map inversion will get a slightly larger slice of
the CPU time relative to LastFM.
On the other hand, it is possible that somewhere in here lies a clever
approach to faster solvent flattening.
Ethan
----------
From: Bosch, Juergen
The problem is however, that the coffee break is lost in the noise of this FFT.
Jürgen
......................
Jürgen Bosch
Jürgen Bosch
----------
From: George Sheldrick
From the rather non-technical inofrmation available so far, it seems to me that it is like leaving out all but the strongest reflections (or perhaps the strongest normalized structure factors). This is unlikely to improve the quality of structure refinement, the importance of using as much data as possible and not leaving out the weakest reflections has often been emphasized. This is quite different to data compression of music. However there is one case where we are already doing this, namely small molecule direct methods or using the same programs to find the heavy atoms in SAD and MAD experiments. These programs use only the strongest 15-20% of the normalized structure factors (E-values). This is possible because the data to parameter ratio is still sufficient, and these reflections contain much of the useful information. However the Fourier routines used by these programs (at least the ones I wrote) are not taking full advantage of the 'sparseness' of the data, so if the MIT people have found a clever way of doing this it might still be useful for heavy atom location (though FFTW and the Intel MKL FFT will be difficult to beat).
George
----------
From: Philippe DUMAS
For all those interested in the technical details about this new Fourier stuff, I saw that the whole paper is available from the web site, not only the simplified account (look at right of this awfully wrong 3-term Fourier synthesis illutration that I would never show to beginners!)
P. Dumas
----------
From: Garib N Murshudov
After quick look at the manuscript: It is applicable to sparse signals (i.e. number of non-zero elements is not whole space). It would be applicable to inverse FFT after density modification and gain would not be that much. k-sparse approximation would loose signal (strictly speaking it does not produce exact FFT but an approximation, i.e. very weak signals (electron density, fourier coefficients) may be ignored)
At the moment I am a bit sceptical about its use in crystallography. Although with careful implementation twice speed up crystallographic FFT could be possible.
Garib
Garib N Murshudov
----------
From: Adam Ralph
Those people considering running faster code should consider using GPGPUs.
Advantages of GPUs are that they have many more cores than CPU. The
disadvantages are that the communication between the CPU and GPU is slow and
memory management is tricker. Thus there is no guarantee that code will run
faster when using GPUs.
CUDA is a set of extensions for C which will allow you to access hardware
accelerators (certain NVidia cards in this case). CUDA has been around for a
while and there are CUDA libraries for FFT and BLAS.
I have not used cuFFT myself, I know that its APIs are based on those of
FFTW. The capabilities and ease of use of these cards are improving with
each generation. If you are in the game of speeding up your FFTs then I
recommend you take a look.
Adam
----------
From: Nat Echols
Unfortunately this isn't going to make refinement programs much faster
either. I found that cuFFT was about 20x faster on a state-of-the-art
NVidia accelerator versus a single Intel Xeon core - but the memory
transfer knocks it down to 4x. OpenMP parallelization can give a
similar speedup without spending $2500 extra on the GPU, and with much
less butchering of the code. (And even that doesn't help much,
because FFTs still take up less than half the runtime during
refinement, at least in Phenix - I would be surprised if other
programs were significantly different in this respect.)
-Nat
----------
From: David S. Cerutti
I realize the list is large and I don't want to clutter inboxes, but
anyone who may be lightly considering GPU implementations should
understand that this technology, while useful for some applications, is
probably not economical for crystallography refinements. I do not have
personal programming experience with them, but the AMBER community has
found that it takes a very knowledgable programmer and a highly regular
problem to reap the most significant benefits from this technology. It is
a significant commitment of time to program a GPU code, both in terms of
the language learning curve and the extensive reoptimization of the CPU
implementation.
Multi-dimensional FFTs really are not the forte of GPUs, and in general
conditional statements must be avoided as much as possible. Random memory
lookup is also problem for GPUs, so these cryo-EM docking problems, while
they may seem like CPU-intensive and regular/uniform problems, may not be
so much suited for GPUs as for grid computing. Intel and other companies
are coming out with massively multicore chips that have their own
drawbacks but at least run commodity code.
The benefits of GPUs to crystallography have been, and will probably
continue to be, smoother visualization.
Dave
P.S. I agree with the consensus on this thread, lossy approximations to
FFTs are not of use to crystallographers but I they may be of use to
someone like me if I go back into docking and in-silico scanning
applications :-)
No comments:
Post a Comment