Question 7699 – Engineering-Mathematics

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

p Trans (X, Y, N)

if N = 1

then Y[1, 1] ← X[1, 1]

else partition X into four (N/2) × (N/2) submatrices X₁₁, X₁₂,
X₂₁, X₂₂

partition Y into four (N/2) × (N/2) submatrices X₁₁, X₁₂,
X₂₁, X₂₂

spawn p Trans (X₁₁, Y₁₁, N/2)

spawn p Trans (X₁₂, Y₁₂, N/2)

spawn p Trans (X₂₁, Y₂₁, N/2)

spawn p Trans (X₂₂, Y₂₂, N/2)

What is the asymptotic parallelism of the algorithm?

Correct Answer: A