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) x (N/2) X X X X submatrices 11, 12, 21, 22 partition Y into four (N/2) x (N/2) submatrices Y Y Y Y 11, 12, 21, 22 X Y spawn p Trans ( 11. 11.N/2) X Y spawn p Trans ( 12. 12.N/2) X Y spawn p Trans ( 21. 21.N/2) X Y spawn p Trans ( 22. 22.N/2) What is the asymptotic parallelism of the algorithm?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. T₁/T∞ = Θ(N²/lg N)
Explanation
Work T₁ = Θ(N²) (every element is copied); span T∞ = Θ(lg N) (recursion depth). Parallelism = Θ(N²/lg N).
More Data Structures and Algorithms questions
- Consider the following statements : (a) The running time of dynamic programming θ(ρ) ρ algorithm is alway where is number of subproblems. (…
- With preconditions p ≥ 1 and n ≥ 0 (no overflow): int x = p; int k = n; int m = 1; while (k != 0) { if (k is odd) m = m * x; x = x * x; k =…
- Match List I with List II. List I: (a) Prim's algorithm, (b) Dijkstra's algorithm, (c) Faster all-pairs shortest path, (d) Edmonds-Karp alg…
- There are many sorting algorithms based on comparison. The running time of heapsort O(n lg n) P Q algorithm is . Like , but unlike , (P, Q)…
- Which of the following is best running time to n n2 − 1 sort integers in the range 0 to ?
- Which of the following is application of depth- first search?