Check out the new USENIX Web site. next up previous contents
Next: The Reduction Class Up: Reduction Previous: Reduction

The Reduction Skeleton

The reduction skeleton consists of a fan-in tree and a fan-out tree.

The fan-in tree has N nodes, where N is the number of threads in the rope. Each node is identified by a distinct thread index (0 to N-1). During the fan-in reduction computation the reduction operation takes place in a bottom up fashion - starting at the leaf and going to the root. At the end of this the root has the reduced value.

The fan-out tree also has N nodes and the nodes are identified by thread indices. The fan-out phase is a broadcast phase where the reduced value is broadcast to each individual thread in a top-down fashion - starting at the root and going to the leaf.

In reality there is only one tree as specified in the Reduction class, only the traversals specified by fan-in and fan-out are different.


Sundaresan Neelakantan
Thu May 15 16:11:49 PDT 1997