edu.rit.clu.network

Class FloydClu

java.lang.Object

edu.rit.clu.network.FloydClu

public class FloydClu
extends java.lang.Object

Class FloydClu is a cluster 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.np=K edu.rit.clu.network.FloydClu infile outfile
K = Number of parallel processes
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.

Each process writes its own output file containing a row slice of the distance matrix after running Floyd's Algorithm. Each output file is a binary file written in the format required by class DoubleMatrixFile. If outfile is specified as, for example, "output.dat", then the per-process output files are named "output_0.dat", "output_1.dat", and so on through K-1.

The computation is performed in parallel in multiple processors. 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.Throwable

Main program.

Throws:

java.lang.Throwable