ALGORITHM FOR PARALLEL COMPUTATION OF PARTIAL SUMS.

An algorithm for parallel computation of several partial sums is proposed. The partial sums are partitioned into sets of r sums each. All sets are computed in parallel. In each set the redundancy shown to be inherent to the problem is utilized to reduce the required computation. In addition to a memory-accumulator architecture proposed earlier to implement this algorithm, a permuter-adder tree implementation is considered. Both approaches admit of implementation in VLSI, CCD or software form. The addition operation could be replaced by any commutative and associative binary operation, with implications for a wide class of applications.