Assignment 8 Solution

$35.00 $30.80


Question 1 Matrices Multiplication:


  • (5 marks) Given two square matrices An nand Bn n, design a multithreded algorithm (in pseducode) that computes A B with work (n3) but span only (log n).


  • (6 marks) Using your algorithm in (a) as a base, design a multithreaded algorithm that compute A B where Ap qand Bq r are two given matrices.


  • (6 marks) Analyze both of your algorithms in (a) and (b).


Note: in part (b), your algorithm should be highly parallel even if any of p, q, and r are 1.


Question 2 (a) (5 marks) Given a square matrix An n, design an e cient multithreaded algorithm that compute AT (A-transpose) in place by using a divide-and-conquer approach (i.e. dividing the matrix recursively into four (n=2 n=2) submatrices C, D, E, and F .)





A = C D ;
E F n  n

where the dimensions of all C; D; E; and F are (n2 n2 )

  • (3 marks) Analyze your algorithm in (a).