FAST PARALLEL ALGORITHM FOR DISCRETE FOURIER TRANSFORM IN MULTI-MESH NETWORK

Somen De, Amit Datta, Asit B. Bhattacharya, and Mallika De

View Full Paper

Keywords

2D mesh, multimesh, wraparound connection, DFT, FFT, VLSI

Abstract

In this paper we propose a parallel algorithm for computing the discrete Fourier transform (DFT) coefficients of n2 points on a multi-mesh (MM) architecture [D. Das, M. De, and B.P. Sinha, A new network topology with multiple meshes, IEEE Transactions on Computers, 48(5), 1999, 536–551.] having n4 processing elements. Each processor in the MM architecture has the same number of neighbours, that is, four as in the case of two-dimensional (2D) torus yet, the time complexity of the proposed algorithm on this MM architecture is O(n) which may be contrasted with O(n2) time for computing n2 – point DFT coefficients on a 2D torus having the same nature of processors.

Important Links:



Go Back