I am the lab contact for Dr. Jagdish Modi, a potential supervisor for students interested in parallel algorithms. This project should appeal to students interested in the design of parallel algorithms, but does not assume any previous parallel computing expertise.

Supervisor: Jagdish Modi
Special Resources: None

Efficient parallel route-planning methods for the London Underground and the Moscow Metro

Various investigations have been made into parallel algorithms for fastest-route determination, in particular for journeys between London Underground stations (for example [1]). These involve a sequence of operations on route matrices.

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 repeating 'multiplying' the route matrix with itself, we can find the lengths of the shortest paths between all pairs of stations. 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 algorithm, applying it to two different topologies: those of the London Underground and the Moscow Metro. The former is a much bigger data set compared to the latter, and should allow a more accurate evaluation of how processor architecture affects the efficiency of the algorithm. 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 stations (edges), and to relate this to the lattice of processor connectivity. If the student is mathematically inclined, 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.

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.