UNB/ CS/ David Bremner/ teaching/ cs3383/ assignments/ CS3383 Assignment 8

1 Write a multithreaded algorithm to compute the product of an n × n matrix and an n-vector.

2 Consider the following parallel search algorithm.

function ParSearch (A, p, q, k)
  If p > q return FALSE
  If A[p] = k  return TRUE
  if p = q return FALSE
  right ← spawn ParSearch(A, p + 2, q, k)
  left ← ParSearch(A, p+1,p+1, k)
  return left OR right
end function

3 (ex 27.1-7 from Cormen et. al) Consider the following multithreaded pseudocode for transposing an n×n matrix A in place:

        P-TRANSPOSE (A)
            n ← A.rows
            parallel for j ← 2 to n
                parallel for i ← 1 to j - 1
                    swap A[i,j],A[j,i]

Analyze the work, span, and parallelism of this algorithm.