Research PapersNo Access

Fast Parallel Algorithm for Prefix Computation in Multi-Mesh Architecture

Department of Engineering & Technological Studies, Kalyani University, Kalyani Nadia, West Bengal 741235, India

E-mail Address: amitdatta_wb@yahoo.co.in

Department of Computer Science and Engineering, Dr. Sudhir Chandra Sur Degree Engineering College, 540, Dum Dum Road, Kolkata, West Bengal 700074, India

E-mail Address: demallika@yahoo.com

Search for more papers by this author

, and

Bhabani P. Sinha

ACM Unit, Indian Statistical Unit, 203, Barrackpore Trunk Road, Kolkata, West Bengal 700108, India

E-mail Address: bhabani@isical.ac.in

Search for more papers by this author

https://doi.org/10.1142/S0129626417500098Cited by:2 (Source: Crossref)

Abstract

A parallel algorithm for prefix computation on $N$ data elements mapped on a Multi Mesh (MM) network of $N = n^{4}$ processing elements is presented here. The time required by the proposed algorithm is significantly less than that by any of the existing algorithms for prefix computation on mesh-like architectures due to the specific interconnection pattern used in the MM network. The proposed technique requires $O (N^{1 / 4})$ time for data communication and $O (log N^{1 / 4})$ time for computation, when mapped on a MM network constituted by $N^{1 / 2}$ meshes, each of size $N^{1 / 4} \times N^{1 / 4}$ . The data communication time in the proposed algorithm is less than the prefix sum algorithm proposed in extended Multi Mesh. To be precise, instead of $(13 N^{1 / 4} - 5) τ$ communication time the proposed algorithm requires a data communication time of $7.5 N^{1 / 4} τ$ only. Moreover, the proposed parallel algorithm does not need any extra inter block links as used in the extended Multi Mesh.

Keywords:

References

1. A. Gamma, G. Karypis, V. Kumar and A. Gupta, Introduction to Parallel Computing (Addison-Wesley, January 26, 2003), 2nd edition. Google Scholar
2. H. S. Stone, An efficient parallel algorithm for the solution of a tridigonal linear system of equations, Journal of the ACM (1892) 27–38. Google Scholar
3. O. Egecioglu and A. Srinivasan, Optimal parallel prefix on mesh architecture, Parallel Algorithm (1993) 191–209. Crossref, Google Scholar
4. Y. C. Lin and C. M. Lin, Efficient parallel prefix algorithm on fully connected message passing computers, Trivandrum, 3rd Int. Conf on High Performance Computing (HiPC), India, December 1996, pp. 19–22. Google Scholar
5. S. Jha, An improved parallel prefix computation on 2D-mesh network, Proc. International Conference on Computational Intelligence: Modelling Techniques and Applications, University of Kalyani, India, (2013), pp. 919–926. Google Scholar
6. D. Das, M. De and B. P. Sinha, A new network topology with multiple meshes, IEEE Transactions on Computers 48(5) (1999) 536–551. Crossref, Web of Science, Google Scholar
7. A. Datta, M. De, S. De and A. Bhattacharya, Fast parallel algorithm for discrete fourier transform in multi mesh, Parallel and Distributed Computing Networks (Acta Press, April 2014), pp. 1–15. Google Scholar
8. A. Datta and M. De, A new approach for parallel discrete fourier transform in multi mesh network, Proc. 1st International Conference on Recent Advances in Information Technology (RAIT 2014) (Springer, March 2014), pp. 87–94. Google Scholar
9. B. P. Sinha, Multi-mesh – An efficient topology for parallel processing, Proc. 9th International Parallel Processing Symposium (IPPS) (1995), pp. 17–21. Google Scholar
10. B. P. Sinha and A. Mukherjee, Parallel sorting algorithm using multiway merge tree and its implementation on a multi-mesh network, Journal of Parallel and Distributed Computing 60 (January 2000), 891–960. Google Scholar
11. P. K. Jana, B. D. Naidu, S. Kumar, M. Arora and B. P. Sinha, Parallel prefix computation on extended multi-mesh network, Information Processing Letters 84 (Elsevier Science, October 2002) 295–303. Crossref, Web of Science, Google Scholar
12. P. K. Jana and B. P. Sinha, An improved parallel prefix algorithm on OTIS-Mesh, Parallel Processing Letters 16(4) (December 2006) 429–440. Link, Google Scholar
13. A. Gupta, Improved Parallel prefix algorithm on OTIS-Mesh of trees, ACEEE Int. J. on Information Technology 1(3) (December 2011) 05–10. Google Scholar
14. N. Afroz, B. P. Sinha, R. Islam and S. Bandyopadhyay, A new network topology with multiple three-dimensional meshes, Proc. 6th International Workshop on Distributed Computing (IWDC 2004), (Indian Statistical Institute, Kolkata, 27–30 December, 2004), LNCS, Vol. 3326, pp. 379–384. Google Scholar