Redirected
edited by
455 views
0 votes
0 votes

The following multithreaded algorithm computes transpose of a matrix in parallel:

p Trans $(X,Y,N)$

if $N=1$

then $Y[1,1] \leftarrow X[1,1]$

else partition $X$ into four $(N/2) \times (N/2)$ submatrices $X_{11}, X_{12}, X_{21}, X_{22}$

partition $Y$ into four $(N/2) \times (N/2)$ submatrices $Y_{11}, Y_{12}, Y_{21}, Y_{22}$

spawn p Trans $X_{11}, Y_{11}, N/2)$

spawn p Trans $X_{12}, Y_{12}, N/2)$

spawn p Trans $X_{21}, Y_{21}, N/2)$

spawn p Trans $X_{22}, Y_{22}, N/2)$

What is the asymptotic parallelism of the algorithm?

  1. $T_1 / T_\infty$ or $\theta(N^2/ \lg N)$
  2. $T_1 / T_\infty$ or $\theta(N/ \lg N)$
  3. $T_1 / T_\infty$ or $\theta(\lg N/N^2)$
  4. $T_1 / T_\infty$ or $\theta(\lg N / N)$
edited by

1 Answer

0 votes
0 votes

$\underline{\textbf{Answer:}\Rightarrow}\;\;1)\;\;\mathrm{\dfrac{T_1}{T_\infty}=\Theta \left (\dfrac{N^2}{\log N} \right)}$

$\underline{\textbf{Explanation:}\Rightarrow}$

$\mathrm{T_1(N) = 4T_1 \left (\dfrac{N}{2} \right ) + O(1) = \Theta(N^2)\;\;\;[Using Master's theorem]}$

$\mathrm{T_\infty \left ( N \right ) = T_{\infty} \left (\dfrac{N}{2} \right ) + O(1) = \Theta \left (\log N \right)\;\;\;[Using Master's theorem]}$

$\text{The asymptotic parallelism of the algorithm}=\mathrm {\dfrac{T_1}{T_{\infty}} = \Theta \left (\dfrac{N^2}{\log N} \right)}$


https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/exams/final_sol.pdf

Master's Theorem.
Caption

 

edited by

Related questions

1 votes
1 votes
2 answers
1
4 votes
4 votes
6 answers
3
soujanyareddy13 asked May 12, 2021
1,865 views
The Boolean expression $AB+A \overline{B}+\overline{A}C+AC$ is unaffected by the value of the Boolean variable _________.$A$$B$$C$$A, B$ and $C$