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.
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