Fast All Sum Algorithm Over 2D-Mesh Network

Authors

  • Gaytri Kumari Gupta Jharkhand Rai University, Ranchi INDIA
  • Sudhanshu Kumar Jha

DOI:

https://doi.org/10.37591/rtpc.v5i3.1843

Abstract

Total sum (aka summation, all sums) is an important mathematical tool which is used extensively in various computational and statistical techniques. Fastest summation plays a vital role in overall calculation of specific technique which reduces cost and time. Thus in this paper we propose an improved parallel summation algorithm on 2D-Mesh network with N (=n2) processing elements which will perform summation of N (= n2) summands (or addends) in + 2 (or n + 2) times. Our proposed algorithm can be compared with traditional parallel approach which runs in 2n times for N summands on the same network.

Keywords: All sums, 2D-mesh network, parallel algorithms, time complexity

Cite this Article
Gaytri Kumari Gupta, Sudhanshu Kumar Jha. Fast All Sum Algorithm over 2DMesh Network. Recent Trends in Parallel Computing. 2018; 5(3): 37–43p.

References

S. G. Akl : The Design Analysis of Parallel Algorithms, Englewood Cliffs, NJ: Prentice-Hall, (1989).

E. Horowitz, S. Sahni, S. Rajasekaran: Fundamentals of Computer Algorithms, G gotia Publications Pvt. Ltd., New Delhi, India, (1998).

S. K. Jha, P. K. Jana, Study and design of parallel algorithms for interconnection networks, LAP LAMBERT Academic Publishing, Germany, 2011.

Behrooz Parhami: Introduction to Parallel Processing: Algorithms and Architectures, 1 edition, Sprin-ger, (January 31, 1999).

A. Grama, G. Karypis, V. Kumar, A. Gupta: Introduction to Parallel Computing, 2 edn. , Addison Wesley, (January 26, 2003).

R. Madankan, et al. : Polynomial chaos quadrature-based minimum variance approach for source pa-rameters estimation, proceeding. of an international conference on Computational Science (ICCS-2012), Embassy Suites Omaha , USA, pp. 1129-1138 , 4-6 June (2012).

Feng Ding, Ximei Liu, Xingyun Ma : Kalman state filtering based least squares iterative parameter es-timation for observer canonical state space systems using decomposition, Journal of Computational and Applied Mathematics Volume 301, pp. 135–143, (1 August 2016).

S. Saha, P. K. Jana: A parallel algorithm for medial axis transformation, proceeding of the interna-tional conference 2003 on Parallel and distributed processing and applications, pp. 356-361, Aizu-Wakamatsu, Japan (2003).

Martin Blazek, Petr Pata : Image processing of globular clusters - Simulation for deconvolution tests (GlencoeSim) , Czech Technical University in Prague, New, Volume 48, pp. 24–29, October 2016.

Klaus Conrad, Dale W. Jorgenson, :Testing the integrability of consumer demand functions: Federal Republic of Germany, 1950–1973,European Economic Review, Volume 12, Issue 2, April 1979, pp 149-169.

Alverson et al.: The Tera Computer System, proceeding of International Conference on Supercomput-ing, Assoc. of Computer. Machinery, pp.1-6 N.Y., 1990.

White paper: On Intel Paragon installed at Caltech, available at the center for research for Parallel Computation at Rice University, volume 7, issue 1 spring summer (1999).

S. Scott and G. Thorson. : Optimized routing in the Cray T3D, Proceeding of First International Work-shop on parallel Computer Routing and Communication, volume 853 of Lecture Notes in Computer Science, pp. 281–294, 1994.

N A. Gara et al.: Overview of the Blue Gene/L system architecture, IBM J. Res. & Dev., 49(2/3):195–212, 2005.

InfiniBand Trade Association. InfiniBand architecture specification release 1.2, 2004.

G. Blelloch: Prefix sums and their applications, Synthesis of Parallel Algorithms, pp. 35–60 (1990).

H. Meijer and S. G. Akl : Optimal Computation of Prefix Sums on a Binary Tree of Processor, Interna-tional Journal of Parallel Programming, Volume 16, No. 2, April, (1987).

Roger, d., Assarsson, u., and Holzschuch: Efficient Stream Reduction on the GPU. In Workshop on General Purpose Processing on Graphics Processing Units, D. Kaeli and M. Leeser, Eds (2007).

K. T. Lucas: Parallel Algorithm for Prefix Computation on OTIS k-Ary 3-Cube Parallel Computers, International Journal of Recent Trends in Engineering, Volume 1, No. 1, (May 2009).

K. Nakano: Optimal parallel algorithms for computing the sum, the prefix-sums, and the summed area table on the memory machine models, IEICE Trans. on Information and Systems, volume E96-D, no. 12, pp. 2626–2634, (2013).

Downloads

Published

2019-01-02

Issue

Vol. 5 No. 3 (2018)

Section

Research Articles

License

Declaration and Copyright Transfer Form

(to be completed by authors)

I/ We, the undersigned author(s) of the submitted manuscript, hereby declare, that the above manuscript which is submitted for publication in the STM Journals(s), is not published already in part or whole (except in the form of abstract) in any journal or magazine for private or public circulation, and, is not under consideration of publication elsewhere.

  • I/We will not withdraw the manuscript after 1 week of submission as I have read the Author Guidelines and will adhere to the guidelines.
  • I/We Author(s ) have niether given nor will give this manuscript elsewhere for publishing after submitting in STM Journal(s).
  • I/ We have read the original version of the manuscript and am/ are responsible for the thought contents embodied in it. The work dealt in the manuscript is my/ our own, and my/ our individual contribution to this work is significant enough to qualify for authorship.
  •  I/We also agree to the authorship of the article in the following order:

Author’s name                                    

 

1. ________________

2. ________________

3. ________________

4. ________________

 

We  Author(s) tick this box and would request you to consider it as our signature as we agree to the terms of this Copyright Notice, which will apply to this submission if and when it is published by this journal.