07-05-2012, 05:07 PM
Parallel Algorithm for Sum of n Numbers Using Binary Tree
Parallel Algorithm for Sum of n Numbers Using.pptx (Size: 100.55 KB / Downloads: 34)
Explanation
Suppose we want to compute the sum of n integers.
Suppose that n is the power of 2; should this not be the case, merely add dummy, zero elements as required.
These n elements are placed at the leaves of a complete binary tree.
How computation is done
In algorithms for a binary tree of processors, we will assume that the data elements are initially held by the leaf processors only.
The nonleaf (inner) processors participate in the computation, but do not hold data elements of their own.
Analysis
During one trip round the loop on i, each processor involved performs two memory access to read its operands, one addition and a final memory access to store result.
Since we assume that a memory access takes a constant time, the total work required from each processor also takes constant time.
Finally, because the processor work in parallel, all the work required in one trip round the outer loop can be executed in constant time.
Special characteristic
The same technique can be applied to such problems as:
finding the product
Maximum or minimum of n elements
Or deciding if they are all zero.