World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Fast Parallel Algorithm for Prefix Computation in Multi-Mesh Architecture

    A parallel algorithm for prefix computation on N data elements mapped on a Multi Mesh (MM) network of N=n4 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(N1/4) time for data communication and O(logN1/4) time for computation, when mapped on a MM network constituted by N1/2 meshes, each of size N1/4×N1/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 (13N1/45)τ communication time the proposed algorithm requires a data communication time of 7.5N1/4τ only. Moreover, the proposed parallel algorithm does not need any extra inter block links as used in the extended Multi Mesh.

    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. CrossrefGoogle 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, ISIGoogle 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, ISIGoogle 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. LinkGoogle 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