02204nas a2200229 4500008004100000022001400041245009200055210006900147300001400216490000800230520153700238653000801775653001801783653000801801653001501809653000801824653002501832653001701857653000801874100002101882856007101903 2019 eng d a0010-465500aBlackNUFFT: Modular customizable black box hybrid parallelization of type 3 NUFFT in 3D0 aBlackNUFFT Modular customizable black box hybrid parallelization a324 - 3350 v2353 a
Many applications benefit from an efficient Discrete Fourier Transform (DFT) between arbitrarily spaced points. The Non Uniform Fast Fourier Transform reduces the computational cost of such operation from O(N2) to O(NlogN) exploiting gridding algorithms and a standard Fast Fourier Transform on an equi-spaced grid. The parallelization of the NUFFT of type 3 (between arbitrary points in space and frequency) still poses some challenges: we present a novel and flexible hybrid parallelization in a MPI-multithreaded environment exploiting existing HPC libraries on modern architectures. To ensure the reliability of the developed library, we exploit continuous integration strategies using Travis CI. We present performance analyses to prove the effectiveness of our implementation, possible extensions to the existing library, and an application of NUFFT type 3 to MRI image processing. Program summary Program Title: BlackNUFFT Program Files doi: http://dx.doi.org/10.17632/vxfj6x2p8x.1 Licensing provisions: LGPL Programming language: C++ External routines/libraries: deal.II , FFTW, PFFT Nature of problem: Provide a modular and extensible implementation of a parallel Non Uniform Fast Fourier Transform of type 3. Solution method: Use of hybrid shared distributed memory paradigm to achieve high level of efficiency. We exploit existing HPC library following best practices in scientific computing (as continuous integration via TravisCI) to reach higher complexities and guarantee the accuracy of the solution proposed.
10aC++10aExtensibility10aFFT10aModularity10aMPI10aMRI image processing10aNUFFT type 310aTBB1 aGiuliani, Nicola uhttp://www.sciencedirect.com/science/article/pii/S0010465518303539