Parallel Prefix on Mesh of Trees and OTIS Mesh of Trees.
Dheeresh K. Mallick, Prasanta K. Jana · Parallel and Distributed Processing Techniques and Applications · 2008
$ The corresponding author, Member, IEEE and IEEE Computer Society Abstract: In this paper, we first develop a parallel algorithm for prefix computation on an n × n mesh of trees (MOT). For n data elements, the algorithm requires 4 log n + O(1) time using n2 processors. Using the MOT prefix, we next propose a prefix algorithm on an n × n OTIS mesh of trees. This algorithm for n4 data elements is shown to map in 13 log n + O(1) electronic moves + 2 OTIS moves using n processors.