edu.rit.smp.network

Class FloydSmpCol

java.lang.Object

edu.rit.smp.network.FloydSmpCol

public class FloydSmpCol
extends java.lang.Object

Class FloydSmpCol is an SMP parallel program that uses Floyd's Algorithm to calculate the length of the shortest path from each node to every other node in a network, given the distance from each node to its adjacent nodes.

Floyd's Algorithm's running time is O(N³), where N is the number of nodes. The algorithm is as follows. On input, D is an NxN matrix where D[i,j] is the distance from node i to adjacent node j; if node j is not adjacent to node i, then D[i,j] is infinity. On output, D[i,j] has been replaced by the length of the shortest path from node i to node j; if there is no path from node i to node j, then D[i,j] is infinity.

     for i = 0 to N-1
         for r = 0 to N-1
             for c = 0 to N-1
                 D[r,c] = min (D[r,c], D[r,i] + D[i,c])
 

Usage: java -Dpj.nt=K edu.rit.smp.network.FloydSmpCol infile outfile
K = Number of parallel threads
infile = Input distance matrix file
outfile = Output distance matrix file

The input file (infile) is a binary file written in the format required by class DoubleMatrixFile.

The output file (outfile) is a binary file written in the format required by class DoubleMatrixFile containing the distance matrix after running Floyd's Algorithm.

The computation is performed in parallel on multiple processors. The inner loop over the distance matrix columns is a parallel loop. The program measures the total running time (including I/O) and the computation's running time (excluding I/O).

Method Summary

Modifier and Type	Method and Description
static void	main(java.lang.String[] args) Main program.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

main

public static void main(java.lang.String[] args)
                 throws java.lang.Exception

Main program.

Throws:

java.lang.Exception