OPTIMAL PARALLEL PREFIX ON MESH ARCHITECTURES
Ömer Eğeci̇oğlu, Ashok Srinivasan · International Journal of Parallel Emergent and Distributed Systems · 1993
Algorithms for efficient implementation of computation of prefix produce on mesh-connected processor arrays are presented. Assuming that an arithmetic operation takes unit time and communication/computation ratio for a single input item is τ, we show that the prefixes of n items can be computed in time 2τ√n + O(log n) on a square mesh with n processors. If n processors are configured as a disc with respect to the Manhattan metric, then the parallel time for the problem becomes √2τ√n + O(√τ 4√n. We show that both of these algorithms are asymptotically optimal.