The following multithreaded algorithm computes transpose of a matrix in…
2019
The following multithreaded algorithm computes transpose of a matrix in parallel:
p Trans \((𝑋,𝑌,𝑁)\)
if \(𝑁=1\)
then \(𝑌[1,1]←𝑋[1,1]\)
else partition \(𝑋\) into four \((𝑁/2)×(𝑁/2)\) submatrices \(X_{11}, X_{12}, X_{21}, X_{22}\)
partition 𝑌 into four \((𝑁/2)×(𝑁/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?
- A.
\(T_1 / T_\infty\)or\(\theta(N^2/ \lg N)\) - B.
\(T_1 / T_\infty\)or\(\theta(N/ \lg N)\) - C.
\(T_1 / T_\infty\)or\(\theta(\lg N/N^2)\) - D.
\(T_1 / T_\infty\)or\(\theta(\lg N / N)\)
Attempted by 22 students.
Show answer & explanation
Correct answer: A
Key idea: compute the total work and the span (critical path) and take their ratio.
Total work T1(N): The recurrence is T1(N) = 4·T1(N/2) + Θ(1) because the problem is split into four equal subproblems and only constant overhead is added at each level.
By the master theorem (a = 4, b = 2), T1(N) = Θ(N^2).
Span (critical path) T∞(N): Because the four recursive calls at each node run in parallel, the longest dependence chain follows one subproblem, giving T∞(N) = T∞(N/2) + Θ(1).
Solving this recurrence yields T∞(N) = Θ(log N).
Parallelism = T1 / T∞ = Θ(N^2) / Θ(log N) = Θ(N^2 / log N).
A video solution is available for this question — log in and enroll to watch it.