Implementation of two-dimension FFT on massively parallel processing system DAWN1000

Yan-Ting Wang; Zhen-Song Wang

doi:10.1117/12.279611

19 September 1997 Implementation of two-dimension FFT on massively parallel processing system DAWN1000

Yan-Ting Wang, Zhen-Song Wang

Proceedings Volume 3166, Parallel and Distributed Methods for Image Processing; (1997) https://doi.org/10.1117/12.279611
Event: Optical Science, Engineering and Instrumentation '97, 1997, San Diego, CA, United States

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.

Citation Download Citation

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); https://doi.org/10.1117/12.279611

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