Beta Operations: Efficient Implementation of a Primitive Parallel Operation

[摘要] We will consider the primitive parallel operation of the Connection Machine, the Beta Operation. Let the imput size of the problem be N and output size M. We will show how to perforrn the Beta Operation on an N-node hypercube in O(log N + $log^2$ M) time. For a $\sqrt{N} x \sqrt{M}$ mesh-of-trees, we require O(log N + $\sqrt{M}$) time.

[学科分类] 计算机科学（综合）