Share Email Print
cover

Proceedings Paper

Implementation of two-dimension FFT on massively parallel processing system DAWN1000
Author(s): Yan-Ting Wang; Zhen-Song Wang
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

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.

Paper Details

Date Published: 19 September 1997
PDF: 8 pages
Proc. SPIE 3166, Parallel and Distributed Methods for Image Processing, (19 September 1997); doi: 10.1117/12.279611
Show Author Affiliations
Yan-Ting Wang, Institute of Electronics (China)
Zhen-Song Wang, Institute of Electronics (China)


Published in SPIE Proceedings Vol. 3166:
Parallel and Distributed Methods for Image Processing
Hongchi Shi; Patrick C. Coffield, Editor(s)

© SPIE. Terms of Use
Back to Top