Accelerating nonuniform fast Fourier transform via reduction in memory access latency

Nihshanka Debroy; Nikos P. Pitsianis; Xiaobai Sun

doi:10.1117/12.795208

3 September 2008 Accelerating nonuniform fast Fourier transform via reduction in memory access latency

Nihshanka Debroy, Nikos P. Pitsianis, Xiaobai Sun

Proceedings Volume 7074, Advanced Signal Processing Algorithms, Architectures, and Implementations XVIII; 707404 (2008) https://doi.org/10.1117/12.795208
Event: Optical Engineering + Applications, 2008, San Diego, California, United States

Abstract

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.

Citation Download Citation

Nihshanka Debroy, Nikos P. Pitsianis, and Xiaobai Sun "Accelerating nonuniform fast Fourier transform via reduction in memory access latency", Proc. SPIE 7074, Advanced Signal Processing Algorithms, Architectures, and Implementations XVIII, 707404 (3 September 2008); https://doi.org/10.1117/12.795208

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available