I Recursive Halving and Doubling Suppose there are 4 processors and the length of each vector is also 4 Step 1: Processor pO sends the first two components of the vector to rocessor p1, and p1 sends the last two components of the vector to pO. Then po gets the partial sums for the last two components, and p1 gets the partial sums for the first two components. So do p2 and p3 Step 2: Processor po sends the partial sum of the third component to processor p3. Processor p3 then adds to get the total sum of the third component. Similarly, processor 0, 1 and 2 find the total sums of the 4th, 2nd, and 1st components, respectively. Now the sum of the vectors are found and the components are stored in different processors Step 3: Broadcast the result using the reverse of the above communication processRecursive Halving and Doubling • Suppose there are 4 processors and the length of each vector is also 4. • Step 1: Processor p0 sends the first two components of the vector to processor p1, and p1 sends the last two components of the vector to p0. Then p0 gets the partial sums for the last two components, and p1 gets the partial sums for the first two components. So do p2 and p3. • Step 2: Processor p0 sends the partial sum of the third component to processor p3. Processor p3 then adds to get the total sum of the third component. Similarly, processor 0,1 and 2 find the total sums of the 4th, 2nd, and 1st components, respectively. Now the sum of the vectors are found and the components are stored in different processors. • Step 3: Broadcast the result using the reverse of the above communication process