An Improved Parallel Prefix Computation on 2D-Mesh Network

摘要

Parallel prefix is an important technique that has been widely accepted in many area of scientific and engineering research. In this paper we propose an improved parallel prefix computation algorithm on n x n mesh network that requires 2n + 5 times. Our proposed algorithm can be compare with the traditional parallel prefix algorithm [1-4, 9] that requires 3n + 2 time on same architecture.