question archive In this problem we will parallelize the Floyd-Warshall algorithm
In this problem we will parallelize the Floyd-Warshall algorithm
Subject:Computer SciencePrice: Bought3
In this problem we will parallelize the Floyd-Warshall algorithm. Use the following pseudocode as your starting point. (The CLRS version had D = W for line 2; we replace this with lines 2-5 to make the loops needed for array assignment explicit.)
Floyd-Warshall(W)
1 n = W.rows
2 create n x n array D
3 for i = 1 to n
4 for j = 1 to n
5 D[i,j] = W[i,j]
6 for k = 1 to n
7 for i = 1 to n
8 for j = 1 to n
9 D[i,j] = min(D[i,j], D[i,k] + D[k,j])
10 return D
(a) Design a parallel version of this algorithm using spawn, sync, and/or parallel for as appropriate. (Copy and modify the pseudocode.) Think carefully about what can be parallelized and what can't, and explain your choices.
(b) Analyze the asymptotic runtime of your algorithm in terms of its work, span, and parallelism (all three).
