Solution for QID #70825: In this problem we will parallelize the Floyd-Warshall algor | StudyHelpMe

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).