Report Number: CS-TR-86-1129
Institution: Stanford University, Department of Computer Science
Title: Beta Operations: Efficient Implementation of a Primitive Parallel Operation
Author: Cohn, Evan R.
Abstract: 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.