Translator Disclaimer
19 September 1997 Implementation of two-dimension FFT on massively parallel processing system DAWN1000
Author Affiliations +
Two-dimensional (2D) Discrete Fourier Transform (DFT) frequently needs to be performed in the digital image processing. Although the computing time of 2D DFT can be dramatically reduced by using 2D Fast Fourier Transform (FFT), the processing speed of a very large array is yet intolerable. The development of parallel processing system promotes the application of 2D FFT. In this paper, we present the implementation of 2D FFT as a general procedure by row-column method and vector-radix method based on a general-purpose massively parallel processing system--DAWN1000 developed in China. Even though the 2D FFT has parallel characteristics in nature, the requirement of corner-turning and the existence of data communication make its implementation more complicated. We analyze the impact of the machine capacity and the computing complexity on the algorithm efficiency and evaluate the implementation in terms of the arithmetic operations as well as the data transfer. The comparison of the two methods shows the fact that each method has its own advantages and disadvantages. Combining their traits, we design a new implementation algorithm concerning its flexibility, the efficiency and the complexity of the communication. As an example, we fulfill the spaceborne SAR image processing by using the new approach. Keywords: Parallel Processing, MPP, Row-Column Algorithm, Vector-Radix Algorithm, Block Algorithm, TwoDimensional FFT, SAR Image Processing.
© (1997) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Yan-Ting Wang and Zhen-Song Wang "Implementation of two-dimension FFT on massively parallel processing system DAWN1000", Proc. SPIE 3166, Parallel and Distributed Methods for Image Processing, (19 September 1997);


Back to Top