Patent ID: 7933940

Claim:
An apparatus comprising: n prefix nodes arranged in a {square root over ‘n’}.times.{square root over ‘n’} mesh topology, wherein each of the prefix nodes is configured to compute an associative operation, and wherein each of the prefix nodes is a combinational circuit, wherein each of the prefix nodes corresponds to a position in an n-element vector of values, and wherein the apparatus computes a cyclic parallel prefix operation by performing actions of: aggregating in a (k+1)th column of the mesh topology, from the n prefix nodes, partial results of applying the associative operation to values in the n-element vector, where 0<k<{square root over ‘n’}−1, and wherein one of (a) k=[floor function over ({square root over ‘n’}−1)/2] and (b) k=[ceiling function over ({square root over ‘n’}−1)/2]; distributing said partial results across the mesh topology from the partial results in the (k+1)th column of the mesh topology; and combining, at least a subset of the n prefix nodes, said partial results with additional partial results associated with the at least a subset of the n prefix nodes to obtain a result of the cyclic parallel prefix operation.