A Fast Parallel Prefix Algorithm on OTIS-Modified Mesh of Trees

In this paper we map parallel prefix Algorithm on a new and improved version of OTISMesh Of Trees called OTIS-Modified Mesh Of Trees. In OTIS-Modified Mesh Of Trees, we add some extra links in each group called wrap around row connections. A parallel algorithm for prefix computation reported recently on interconnection network called OTIS-Mesh of Trees[5]. Using n4 processors, algorithm shown to run in 10log n + O(1) electronic moves and 1 optical move for n4 data points. In this paper we describe that we can perform the prefix on OTIS-Modified Mesh of Trees on n4 processors in 9log n + O(1) electronic moves and 1 optical move. This complexity can be achieved by applying the prefix algorithm of Modified Mesh of Trees[2] in each group on parallel algorithm of prefix computation on OTIS-Mesh of Trees[5]. However the cost increases because we add some extra links as wrap around row connections.