Lab Contact: Dr Timothy G. Griffin
Supervisor: Dr Jagdish J. Modi
Special Resources: None
This should appeal to students interested in the design of parallel algorithms, but does not assume any previous parallel computing expertise.
In the past students have considered rail networks, both underground and overground, minimizing a single parameter such as distance or time, and found an algorithm analogous to matrix multiplication to be suitable for parallel computation [1].
Dijkstra’s algorithm (see [2]) is essentially serial and does not parallelise well to lead to a performance improvement. An alternative method involves using a modified form of matrix multiplication, in which we find the minimum of a sum of weights (route-lengths), instead of forming a sum of products. By repeatedly ‘multiplying’ the route matrix with itself, we can find the lengths of the shortest paths between all pairs of destinations. Since matrix multiplication is a highly parallel operation, this method is well suited to parallel computation.
The aim of the project is to implement such an algorithm, applying it to the California road network. Furthermore, if possible to consider such developments as improving the efficiency of computation by avoiding large sparse areas in order to minimise data movements, for example by adapting the Cannon or Fox-Otto algorithm [4,5].
Parallel computers have as a core structure a set of interconnected processors. The optimal choice of interconnection for a particular problem may not always be available. In fact, in practice the interconnection usually takes place within some sort of plane two-dimensional lattice. In the consideration of the parallel algorithm, it would be interesting to explore the features of the two-dimensional graph arising from the connections between destinations (edges), and to relate this to the lattice of processor connectivity. It may be worthwhile to investigate certain properties possessed by the processor graph, such as degree of symmetry and homogeneity [3], as well as the extent to which it can be embedded in a lattice.
The dataset can be built up using the California Road Network data available from the website at the following URL https://www.cs.utah.edu/~lifeifei/SpatialDataset.htm, which provides the required data for the proposed project.
Extension
If time permits the implementation could utilise FPGA execution resources which are available in the lab, which will significantly reduce calculation time. Furthermore, the SIMD nature of the algorithms also makes it more amenable in harnessing the FPGA architecture.
References:
[1] Batty M. Parallel Route Planning for the London Underground, Diploma in Computer Science, Computer Laboratory, 2007.
[2] Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, second edition, 2003.
[3] Modi J. Parallel Algorithms and Matrix Computation, OUP, 1988.
[4] Grama, Gupta, Karypis, Kumar. Introduction to Parallel Computing, Pearson Education, second edition, 2005.
[5] Akpan, O. Efficient parallel implementation of the Fox algorithm. Computer Science Department, Bowie State University, 2003.