Aspire's Library
Study Stuff for MCA Examinations - NIMCET
Previous Year Question (PYQs)
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?
Solution
Parallelism is given by:
$\dfrac{T_1}{T_\infty}$
Here, $T_1$ is total work.
The algorithm recursively divides the matrix into $4$ subproblems of size $N/2$.
So,
$T_1(N)=4T_1(N/2)+\theta(1)$
Hence,
$T_1(N)=\theta(N^2)$
Now, span or critical path time is:
$T_\infty(N)=T_\infty(N/2)+\theta(1)$
because recursive calls run in parallel.
So,
$T_\infty(N)=\theta(\lg N)$
Therefore,
$\dfrac{T_1}{T_\infty}=\dfrac{\theta(N^2)}{\theta(\lg N)}$
$=\theta(N^2/\lg N)$
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
