Parallel Prefix Sum Computation on Multi Mesh of Trees

In recent years, due to efficient topological properties, e.g., logarithmic diameter, simple routing etc, the multi mesh of trees (MMT) topology is center of attraction for researches. The multi-mesh of trees is a hybrid network of the multi-mesh (MM) and the mesh of trees (MoT) with n × n mesh of trees consists of n² processors. Prefix-computation on multi-mesh (MM) topology have been proposed with O(N^1/4) time for N=n⁴ data values while mapped on a multi-mesh using N processors. In this paper we proposed prefix-computation on MMT topology. We have calculated intrablock prefixes and then interblock prefixes. The complexity of our algorithm for prefix-computation in intrablock is O(n) on MMT topology with N processors and N=n⁴ data values. This can be compared with the prefix computation complexity obtained in multi mesh topology, and shows improvement.