An alternative way of partitioning the matrix D(k) in Floyd's all-pairs shortest paths algorithm is to use the 1-D block mapping (Section 3.4.1). Each of the p processes is assigned n/p consecutive columns of the D(k) matrix.
a. Compute the parallel run time, speedup, and efficiency of 1-D block mapping on a hypercube-connected parallel computer. What are the advantages and disadvantages of this partitioning over the 2-D block mapping presented in Section 10.4.2?
b. Compute the parallel run time, speedup, and efficiency of 1-D block mapping on a pprocess mesh with store-and-forward routing, a p-process mesh with cut-through routing, and a p-process ring.