Parallelism The hint for this problem is parallelism For the

Parallelism

The hint for this problem is parallelism. For the following parts, you only need to provide pseudocode and a brief high level explanation of the main idea. You do not need to provide a proof of correctness, time or work, unless explicitly stated. Of course, if your algorithm is unnecessarily slow or incorrect, then you will not receive full credit. Recall the SUM problem. Modify the code a little to compute the MAX of n numbers. Modify the code of SUM to compute SUMS, where SUMS(A[1...n])[j] = sigma^j_i = 1 A[i]. Use SUMS to solve the COMPACT problem. More formally, the COMPACT problem is to rearrange the array so that all zeros in the array appear after the nonzeros. Explain in detail how two n times n matrices can be multiplied using O(n^3) processors, O(log n) parallel time, and O(n^3) work. Suppose that you want to multiply matrices in parallel using Strassen\'s algorithm. Write the recurrences for parallel time (T) and work (W). What are the solutions of these recurrences? How many processors are required in the previous question? Explain.

Solution

Answer

Hopefully below is the SUM algorithm that your qestion refers to:

function sum(a(1..n)) ... sequential sum of n numbers
if (n=1)
return a(1)
x = sum(a(1..n/2))
y = sum(a(n/2+1..n))
return (x+y)

1.

Modifying the above code for MAX of n-numbers

max = 0
control = 0 //0 for sum, change it to 1 for max

if (n=1)
{  
return a(1)
  control = 1
}
x = sum(a(1..n/2))
if(x > max)
   max = x
y = sum(a(n/2+1..n))
if (y > max)
   max = y
//change control here according to what you want
if(control = 0)
return (x+y)
else
   return max