Skip to main content

Accelerating nonuniform fast Fourier transform via reduction in memory access latency

Publication ,  Journal Article
Debroy, N; Pitsianis, NP; Sun, X
Published in: Proceedings of SPIE - The International Society for Optical Engineering
December 17, 2008

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.

Duke Scholars

Published In

Proceedings of SPIE - The International Society for Optical Engineering

DOI

ISSN

0277-786X

Publication Date

December 17, 2008

Volume

7074

Related Subject Headings

  • 5102 Atomic, molecular and optical physics
  • 4009 Electronics, sensors and digital hardware
  • 4006 Communications engineering
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Debroy, N., Pitsianis, N. P., & Sun, X. (2008). Accelerating nonuniform fast Fourier transform via reduction in memory access latency. Proceedings of SPIE - The International Society for Optical Engineering, 7074. https://doi.org/10.1117/12.795208
Debroy, N., N. P. Pitsianis, and X. Sun. “Accelerating nonuniform fast Fourier transform via reduction in memory access latency.” Proceedings of SPIE - The International Society for Optical Engineering 7074 (December 17, 2008). https://doi.org/10.1117/12.795208.
Debroy N, Pitsianis NP, Sun X. Accelerating nonuniform fast Fourier transform via reduction in memory access latency. Proceedings of SPIE - The International Society for Optical Engineering. 2008 Dec 17;7074.
Debroy, N., et al. “Accelerating nonuniform fast Fourier transform via reduction in memory access latency.” Proceedings of SPIE - The International Society for Optical Engineering, vol. 7074, Dec. 2008. Scopus, doi:10.1117/12.795208.
Debroy N, Pitsianis NP, Sun X. Accelerating nonuniform fast Fourier transform via reduction in memory access latency. Proceedings of SPIE - The International Society for Optical Engineering. 2008 Dec 17;7074.

Published In

Proceedings of SPIE - The International Society for Optical Engineering

DOI

ISSN

0277-786X

Publication Date

December 17, 2008

Volume

7074

Related Subject Headings

  • 5102 Atomic, molecular and optical physics
  • 4009 Electronics, sensors and digital hardware
  • 4006 Communications engineering