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

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

View Full Paper

References

  1. [1] T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to algorithms (Cambridge, MA: MIT Press, 1989).
  2. [2] S.G. Akl, The design and analysis of parallel algorithms (New York, NY: Prentice-Hall, 1989).
  3. [3] D. Das, M. De, and B.P. Sinha, A new network topology with multiple meshes, IEEE Transactions on Computers, 48(5), 1999, 536–551.
  4. [4] B.P. Sinha, Multi-mesh an efficient topology for parallel processing, Proc. 9th Int. Parallel Processing Symp. (IPPS ), Santa Barbara, CA, 1995, 17–21.
  5. [5] A. Dardalis, D. Andreas, and V.K. Prasanna, Fast parallel implementation of DFT using configurable devices, Proc. Int. Workshop on Field Programmable Logic and Applications, London, 1–3 September, 1997, 314–323.
  6. [6] M.V. Aliev, A.M. Belov, A.V. Ershov, and M.A. Chicheva, Parallel algorithms for a hyper complex discrete Fourier transform, Pattern Recognition and Image Analysis, 15(1), 2005, 110–112.
  7. [7] Z.C. Xiang, H.G. Qiang, and H.M. He, Some new parallel fast Fourier transform algorithms, Proc. Sixth Int. Conf. on Parallel and Distributed Computing Application and Technology (PDCAT ), 5–8 December, Dalian, China, 2005, 624–628.
  8. [8] R.A. Al Na’mneh, W.D. Pan, and S.M. Yoo, Parallel implementation of 1-D FFT without inter process communication, International Journal of Computers and Application, 29(2), 2007, 180–186.
  9. [9] S. Gurevich, R. Hadani, and N. Sochen, The finite harmonic oscillator and its applications to sequences, communication and radar, IEEE Transactions on Information Theory, 54 (9), 2008, 4239–4253.
  10. [10] J.M. Cooley and J.W. Tukey, An algorithm for the machine computation of the complex Fourier series, Mathematics of Computation, 19, 1965, 297–301.
  11. [11] B.P. Sinha and A. Mukherjee, Parallel sorting algorithm using multiway merge and its implementation on a multi-mesh network, Journal of Parallel and Distributed Computing, 60, 2000, 891–960.
  12. [12] B.P. Kundu, M. De, and B.P. Sinha, Wormhole routing for complete exchange in multi-mesh, Proc. 4th Int. Conf. on High Performance Computing (HIPC ), Bangalore, India, 1997, 432–437.
  13. [13] M. De, D. Das, and B.P. Sinha, An efficient sorting algorithm on the multi-mesh network, IEEE Transactions on Computers, 46(10), 1997, 1132–1137.
  14. [14] J.H. Reif and A. Tyagi, Efficient parallel algorithms for optical computing with discrete Fourier transform primitive, Applied Optics, 36(20), 1997, 7327–7340.
  15. [15] N. Afroz, S. Bandyopadhyay, R. Islam, and B.P. Sinha, On the implementation of links in multi-mesh network using WDM optical networks, Proc. 7th Int. Workshop on Distributed Computing, Kharagpur, India, December 27–30, 2005 (LNCS 3741 ), 183–188.
  16. [16] A. Sen, S. Bandyopadhyay, and B.P. Sinha, A new architecture and a new metric for lightwave networks, Journal of Lightwave Technology, 19(7), 2001, 913–925.
  17. [17] S. Murthy and A. Sen, A peer-to-peer network based on multi-mesh architecture, Global Telecommunications Conf., 7, 1–5 December, San Francisco, USA, 2003, 3840–3844.
  18. [18] I.D. Scherson and S. Sen, Parallel sorting algorithm in two-dimensional VLSI models, IEEE Transactions on Computers, 38(2), 1989, 238–249.
  19. [19] J. Ja Ja, An introduction to parallel algorithms (MA: Addition-Wesley, 1992).
  20. [20] A. Gupta, Mesh based algorithm for finite exponential function, Proc. 2nd Int. Conf. on Advanced Computing and Communication Technologies, Rothak, Haryana, India, 2012, 328–330.
  21. [21] Q. Jianxian, A time-space optimal parallel sorting on a hypercube, University Journal of Natural Sciences, 1(3/4), 1996, 465–469.
  22. [22] E. Dekkel, D. Nassimi, and S. Sahni, Parallel matrix and graph algorithms, SIAM Journal on Computing, 10(10), 1981, 657–673.
  23. [23] C.P. Katti and R. Kumari, A new parallel algorithm for Lagrange interpolation on a hypercube, Computers & Mathematics with Applications, 51(6–7), 2006, 1057–1064.
  24. [24] E.T. Leighton, Introduction on parallel algorithms and architectures: Array, trees and hypercubes (San Mateo, CA: Morgan Kaufmann, 1992).
  25. [25] D.K. Mallick and P.K. Jana, Parallel prefix on mesh of trees and OTIS mesh of trees, http://nguyendangbinh.org/proceedings/IPCV08/Papers/PDP4269.pdf.
  26. [26] P.K. Jana and B.P. Sinha, Fast parallel algorithm for polynomial interpolation, 29(4), 1995, 85–92.
  27. [27] C.D. Thompson and H.T. Kung, Sorting on a mesh connected parallel computer, Communications of the ACM, 20(4), 1977, 263–271.
  28. [28] A. Aggarwal, A comparative study of Xtree, pyramid and related machines, Proc. 25th Annual Symp. on Foundation of Computer Science, October, 1984, IEEE, New York, NY, 89–99.
  29. [29] A. Grama, A. Gupta, G. Karypis, and V. Kumar, Introduction to parallel Computing, 2nd ed. (Boston, MA: Addison Wesley, 2003).
  30. [30] J.P. Strong, The Fourier transform on mesh connected processing arrays such as massively parallel processors, Proc. 1985 IEEE Workshop on Computer Architecture for Pattern Analysis and Image Database Management, CAPAIDM, Miami Beach, Florida, 1985, 190–196.
  31. [31] W.G. Bliss and A.F. Julien, Efficient and reliable VLSI algorithms and architectures for the discrete Fourier transform, Proc. Int. Conf. on Acoustics Speech and Signal Processing, 2(3–6), 1990, 901–904.
  32. [32] H. Shousheng and M. Torkelson, A systolic array implementation of common factor algorithm to compute DFT, Int. Symp. on Parallel Architectures, Algorithms and Networks (ISPAN ), December 14–16, Kanazawa, Japan, 1994, 374–381.
  33. [33] C.N. Zhang and D.Y.Y. Yuns, Multidimensional systolic networks for discrete Fourier transform, Proc. ISCA ’84 11th Annual Int. Symp. on Computer Architecture, Ann Arbor, MI, June, 1984, 215–222.
  34. [34] P. Fragopoulou and S.G. Akl, A parallel algorithm for computing Fourier transform on the star graph, Transaction on Parallel and Distributed Systems, 5(5), 1994, 525–531.
  35. [35] I. Gertner and M. Rofheart, A parallel algorithm for 2D DFT computation with no interprocess communication, IEEE Transaction on Parallel and Distributed Systems, 1(3), 1990, 377–382.
  36. [36] N. Rakesh, Analysis of multi-sort algorithm on multi-mesh of trees (MMT) architecture, The Journal of Supercomputing, 57(3), September 2011, 276–313.
  37. [37] W. Bliss and A.W. Julien, Efficient and reliable VLSI algorithms and architectures for the discrete Fourier transform, Int. Conf. on Acoustics, Speech and Signal Processing (ICASSP), April 3–6, Albuquerque, NM, 1990, 901–904.
  38. [38] F. Qureshi and O. Gustafsson, Generation of all radix-2 fast Fourier transform algorithms using binary trees, Proc. 20th European Conf. on Circuit Theory and Design (ECCTD), August 29–31, Linkoping, Sweden, 2011, 667–680.

Important Links:

Go Back