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?
- $T_1 / T_\infty$ or $\theta(N^2/ \lg N)$
- $T_1 / T_\infty$ or $\theta(N/ \lg N)$
- $T_1 / T_\infty$ or $\theta(\lg N/N^2)$
- $T_1 / T_\infty$ or $\theta(\lg N / N)$