Accelerating nonuniform fast Fourier transform via reduction in memory access latency
Published
Journal Article
We address the discrepancy that existed between the low arithmetic complexity of nonuniform Fast Fourier Transform (NUFFT) algorithms and high latency in practical use of NUFFTs with large data sets, especially, in multi-dimensional domains. The execution time of a NUFFT can be longer by a factor of two orders of magnitude than what is expected by the arithmetic complexity. We examine the architectural factors in the latency, primarily on the non-even latency distribution in memory references across different levels in the memory hierarchy. We then introduce an effective approach to reducing the latency substantially by exploiting the geometric features in the sample translation stage and making memory references local. The restructured NUFFT algorithms render efficient computation in sequential as well as in parallel. Experimental results and improvements for radially encoded magnetic resonance image reconstruction are presented.
Full Text
Duke Authors
Cited Authors
- Debroy, N; Pitsianis, NP; Sun, X
Published Date
- December 17, 2008
Published In
Volume / Issue
- 7074 /
International Standard Serial Number (ISSN)
- 0277-786X
Digital Object Identifier (DOI)
- 10.1117/12.795208
Citation Source
- Scopus