Reduce (parallel pattern): Difference between revisions

Revision as of 09:52, 22 March 2018

Revision as of 10:15, 22 March 2018

Line 60:

=== Algorithm description ===

The animation shows the execution of such an algorithm in a [[Duplex (telecommunications)|full-duplex]] communication model. Communication links are represented by black lines between the vectors of elements and build a Fibonacci tree of size seven in this example. WhenIf an element is send to another processing unit the link is colored with the color of the corresponding element. An element that is received by a processor is added to the already existing element of same color (at the same index in the vector).

The algorithm itself propagates the partial sums from bottom to top until all elements are contained in the sum at the root processor on top. In the first step of the execution, the processing units which are leafs in the underlying tree send their first elements to their parent. This is similar to the send operations of the binomial tree algorithm with the key difference that the leaf units each have two more elements which have to be send and therefore do not become inactive, but can continue to send elements, which is analogous to the pipelined approach and improves efficiency. Processing units that are not leafs start to send their elements in order of the indices in the vector once they have received an element from a child. In the example they send green, blue and red elements in this order. If two processors compete to send their elements to the same processor, then the element of the right child is received first. Because of the structure of the Fibonacci tree all processors send or receive elements while the "pipeline" is filled. The pipeline is filled from the point where each unit has received an element and until the leaf units have no more elements to send.

=== Runtime ===