Open Access
Subscription or Fee Access
Fast All Sum Algorithm Over 2D-Mesh Network
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).
Refbacks
This site has been shifted to https://stmcomputers.stmjournals.com/