Somen De, Amit Datta, Asit B. Bhattacharya, and Mallika De
2D mesh, multi-mesh, wrap-around connection, DFT, FFT, VLSI
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
