Fast All Sum Algorithms on mesh of trees and Multi-Mesh of Trees architecture

Gaytri Kumari Gupta; Sudhanshu Kumar Jha

Abstract

The Network encapsulates the properties of Mesh of Trees and Multi-Mesh Network, forming a Multi Mesh of Trees network architecture and, hence yielding a lot of topological benefits. Several parallel algorithms have been successfully mapped on this architecture to solve various problems. In this paper, we propose an algorithm which may play a very important role in computations ranging from finding a sum to a high degree of calculations required in statistical and non-statistical methods. The proposed Fast All Sum algorithm on mesh of tree of N size (n× n=n2 processing elements) network, and for a multi mesh of trees of N×N size (n2×n2=n4 processing elements) network, takes O (log n) times for the summation of data which is far better than the general linear computations taking O(N) processing time.Keywords: Fast All Sum, Multi mesh of trees (MMT), parallel algorithms, time complexity, algorithm.Cite this Article: Gaytri Kumari Gupta, Sudhanshu Kumar Jha. Fast All Sum Algorithms on Mesh of Trees and Multi-Mesh of Trees architecture. Current Trends in Information Technology. 2020; 10(2): 6–11p.