Fast Parallel Algorithm for Prefix Computation in Multi-Mesh Architecture
Abstract
A parallel algorithm for prefix computation on data elements mapped on a Multi Mesh (MM) network of 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 time for data communication and time for computation, when mapped on a MM network constituted by meshes, each of size . 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 communication time the proposed algorithm requires a data communication time of only. Moreover, the proposed parallel algorithm does not need any extra inter block links as used in the extended Multi Mesh.
References
- 1. , Introduction to Parallel Computing (Addison-Wesley, January 26, 2003), 2nd edition. Google Scholar
- 2. , An efficient parallel algorithm for the solution of a tridigonal linear system of equations, Journal of the ACM (1892) 27–38. Google Scholar
- 3. , Optimal parallel prefix on mesh architecture, Parallel Algorithm (1993) 191–209. Crossref, Google Scholar
- 4. , 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. , 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. , A new network topology with multiple meshes, IEEE Transactions on Computers 48(5) (1999) 536–551. Crossref, ISI, Google Scholar
- 7. ,
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 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. , Multi-mesh – An efficient topology for parallel processing, Proc. 9th International Parallel Processing Symposium (IPPS) (1995), pp. 17–21. Google Scholar
- 10. , 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. , Parallel prefix computation on extended multi-mesh network, Information Processing Letters 84 (Elsevier Science, October 2002) 295–303. Crossref, ISI, Google Scholar
- 12. , An improved parallel prefix algorithm on OTIS-Mesh, Parallel Processing Letters 16(4) (December 2006) 429–440. Link, Google Scholar
- 13. , Improved Parallel prefix algorithm on OTIS-Mesh of trees, ACEEE Int. J. on Information Technology 1(3) (December 2011) 05–10. Google Scholar
- 14. , 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


