Lab Contact: Mark Batty
Supervisor: Jagdish Modi
Special Resources: None

Efficient parallel route planning on the national rail network, with use of the Fox-Otto algorithm.

This should appeal to students interested in the design of parallel algorithms, but does not assume any previous parallel computing expertise. 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 an analogue 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 part of the National rail 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 using the Fox-Otto algorithm [3,4].

Further developments might include:
The dataset can be downloaded from the Association of Train Operating Companies (ATOC) Rail Industry Data website. An additional suggestion for the project is to limit its scope and concentrate on specific rail network operators, to ensure that the number of nodes to be dealt with is manageable.

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. 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 [5], 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] Grama, Gupta, Karypis, Kumar. Introduction to Parallel Computing, Pearson Education, second edition, 2005.
[4] Akpan, O. Efficient parallel implementation of the Fox algorithm. Computer Science Department, Bowie State University, 2003.
[5] Modi J. Parallel Algorithms and Matrix Computation, OUP, 1988.