Exploring parallelization strategies for NUFFT data translation
Yuanrui Zhang, Mahmut Kandemir, Nikos P. Pitsianis, Xiaobai Sun · 2009
This paper introduces parallelization strategies for the Non-Uniform FFT (NUFFT) data translation on multicore architectures. The NUFFT enables the use of the cele-brated FFT with un-equally spaced data in numerous situ-ations in signal and image processing as well as in scientific computing. The critical extension lies at the translation of non-equally spaced or non-uniformly sampled data onto an equally spaced Cartesian grid or vice versa. The data trans-lation can be made sufficiently accurate, with the arithmetic complexity linearly proportional to the size of the data en-semble. For large NUFFTs, however, the data translation is found substantially dominant in computation time on mod-ern computers while it is expected to be dominated by the FFT. In order to match the FFT performance achieved by FFTW, data locality and parallelism in the data translation must be explored and exploited as well. We are concerned with two fundamental issues. First, the data translation can be described as a matrix-vector multiplication with a matrix of irregular sparsity. This is beyond the effective scope of the conventional tiling and parallelization schemes applied by a compiler for performance improvement on computa-tion with dense matrices. Secondly, multicore processors exist and emerge in many different configurations, and are expected to evolve further in architectural variety. This may mean the end of performance tuning on a single type of ar-chitecture. In this paper, we introduce an automation tool that takes two specifications as input, one on an application-specific data translation algorithm, the other on a target multicore processor architecture. The tool generates a par-allel code that explores the data locality and parallelism by utilizing both geometric structures in data translation and the processor-memory configurations in the target architec-