Question

1. Parallelize the program of finding the sum of n numbers (a₁+a₂+...+a_n) using n/2 processors.

(1) Draw the diagram;

(2) Find the numbers of operations for the implementations of the sequential algorithm and the parallel program;

Answer 1

Algorithm for summation of using n processors in parallel-

int arr[n],summation=0

for i=0 to n-1 in parallel

summation=a[i]

Time Complexity - O(n)

Algorithm for summation of using n/2 processors in parallel-

for i = 0 to n-1 do in parallel

temp[i] = a[i];

for i = 0 to n-1 do in parallel

for j = 1 to log n do

if (i mod 2^j == 2^j - 1) then

temp[i] = temp[i] + temp[i - 2^(j-1)];

sum = temp[n-1];

Time Complexity - O(logn)

For serial algorithms Number of operation For posallel algosithm, mumber of operatia