Share Email Print

Proceedings Paper

Accelerating nonuniform fast Fourier transform via reduction in memory access latency
Author(s): Nihshanka Debroy; Nikos P. Pitsianis; Xiaobai Sun
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper 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.

Paper Details

Date Published: 3 September 2008
PDF: 8 pages
Proc. SPIE 7074, Advanced Signal Processing Algorithms, Architectures, and Implementations XVIII, 707404 (3 September 2008); doi: 10.1117/12.795208
Show Author Affiliations
Nihshanka Debroy, Duke Univ. (United States)
Nikos P. Pitsianis, Duke Univ. (United States)
Aristotle Univ. (Greece)
Xiaobai Sun, Duke Univ. (United States)

Published in SPIE Proceedings Vol. 7074:
Advanced Signal Processing Algorithms, Architectures, and Implementations XVIII
Franklin T. Luk, Editor(s)

© SPIE. Terms of Use
Back to Top