Institution: Stanford University, Department of Computer Science

Title: Beta Operations: Efficient Implementation of a Primitive Parallel Operation

Author: Cohn, Evan R.

Author: Haddad, Ramsey W.

Date: August 1986

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.

http://i.stanford.edu/pub/cstr/reports/cs/tr/86/1129/CS-TR-86-1129.pdf