Implement Floyd’s Algorithm [yourname]Floyd.py (Ch 9, Exercise 3, p 478), for th

Question

Implement Floyd’s Algorithm [yourname]Floyd.py (Ch 9, Exercise 3, p 478), for the five-node network displayed on p. 478.

Print the solution in the same format shown to represent a 5 X 5 array on p. 478 (including the column and row numbers, with separating lines, if possible: 5 points).

Include a counter which is used to print the total number of comparisons when the algorithm is executed – each execution of the ‘if” structure counts as one comparison.

Document the program

(10 points) What is the order of magnitude of this algorithm?

(10 points) Question 3 notes that this algorithm is simpler to implement than Dijkstra’s shortest path algorithm (see Ch 7, p. 365). Why then is it preferable that routers use Dijkstra’s algorithm rather than Floyd’s algorithm in routing traffic over the internet?

Explanation / Answer

Input: n — number of vertices a — adjacency matrix Output: Transformed a that contains the shortest path lengths for k 0 to n 1 for i 0 to n 1 for j 0 to n 1 a[i, j] min(a[i, j], a[i, k] + a[k, j]) endfor endfor endfor Floyd’s algorithm – p. 6 Some observations Floyd’s algorithm is an exhaustive and incremental approac h The entries of the a-matrix are updated n rounds a[i, j] is compared with all n possibilities, that is, against a[i, k] + a[k, j], for 0 k n 1 n 3 of comparisons in total Floyd’s algorithm – p. 7 Source of parallelism During the k’th iteration, the work is (in C syntax) for (i=0; i

Using Foster’s design methodology: Partitioning — each a[i, j] is a primitive task Communication — during the k’th iteration, updating a[i, j] needs values of a[i, k] and a[k, j] broadcast a[k, j] to a[0, j], a[1, j], . . . , a[n 1, j] broadcast a[i, k] to a[i, 0], a[i, 1], . . . , a[i, n 1]Let one MPI process be responsible for a piece of the a matrix Memory storage of a is accordingly divided The division can in principle be arbitrary, as long as the number of all a[i, j] entries is divided evenly However, a row-wise block data division is very convenient 2D arrays in C are row-major easy to send/receive an entire row of a We therefore choose to assign one MPI process with a number of consecutive rows of a Floyd’s algorithm – p. 10 Communication pattern Recall that in the k’th iteration: a[i, j] min( a[i, j], a[i, k] + a[k, j]) Since entries of a are divided into rowwise blocks, so a[i, k] is also in the memory of the MPI process that owns a[i, j] However, a[k, j] is probably in another MPI process’s memory Communication is therefore needed! Before the k’th iteration, the MPI process that owns the k’th row of the a matrix should broadcast this row to everyone elseSuppose a matrix (2D array) is divided into row-wise blocks and distributed among p MPI processes Process i only allocates storage for its assigned row block from row ( i · n )/p of matrix a until row (( i + 1) · n )/p 1 We need to know: Which global row does a local row correspond to? Mapping: local index global index On process number proc id global index=BLOCK LOW(proc id, p, n)+local index

void compute_shortest_paths (int id, int p, dtype **a, int n) { int i, j, k; int offset; / * Local index of broadcast row * / int root; / * Process controlling row to be bcast * / int * tmp; / * Holds the broadcast row * / tmp = (dtype *) malloc (n * sizeof(dtype)); for (k = 0; k < n; k++) { root = BLOCK_OWNER(k,p,n); if (root == id) { offset = k - BLOCK_LOW(id,p,n); for (j = 0; j < n; j++) tmp[j] = a[offset][j]; } MPI_Bcast (tmp, n, MPI_TYPE, root, MPI_COMM_WORLD); for (i = 0; i < BLOCK_SIZE(id,p,n); i++) for (j = 0; j < n; j++) a[i][j] = MIN(a[i][j],a[i][k]+tmp[j]); } free (tmp); }

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.