Jagdish Modi Suggestions
Application of the Cannon and Fox-Otto algorithms to efficient
parallel route planning methods
Lab Contact: Andrew Moore
Originator: Jagdish Modi, email: email@example.com
Special Resources: None
Various investigations have been made into parallel algorithms for
fastest-route determination, in particular (for example ) for journeys
between London Underground stations, based on the available travel
information. These involve a sequence of operations on route matrices. For
efficient computation it is useful both to avoid large sparse areas and to
minimize data movements.
One approach could be to modify the Cannon algorithm or Fox -Otto
algorithm, which work on sub-blocks and are very space efficient. The use
of Cannons algorithm, for example, avoids the need for a single processor
to collect and redistribute the data before and after each operation, and
therefore is efficient in both time and space. The Fox -Otto algorithm is
similar, where for a matrix product A*B each sub-block of matrix A is
broadcast across each row of processors and then multiplied with each
sub-block of matrix B. The B blocks are then rotated upwards and another
row broadcast is performed.
Developments might include:
novel ways of using an analogue of matrix squaring instead of
successive multiplications, to reduce the total number of steps, and
incorporating the path specification for all paths simultaneously
to investigate different data layout algorithms taking account of
the processor topology, and their effect on the overall performance; a
layout algorithm that takes an arbitrary topology and returns an optimal
data layout would be of interest
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 preparation of the parallel algorithm, it will be interesting to
explore the features of the two-dimensional graph arising from the
connections of stations (nodes) and the travel times between stations
(edges), and to compare this with the lattice of processor connectivity. If
the student is mathematically inclined, it may be worthwhile to investigate
certain properties possessed by the two-dimensional graph, such as degree
of symmetry and homogeneity, as well as the extent to which they can be
embedded onto a lattice.
In addition it may be useful to implement the algorithm on a random
topology of interconnected processors, evaluate the cost component, and
then to compare this with the cost on a lattice connectivity, so as to
determine the extent to which interconnection between processors plays an
important role. In this case it would be instructive to find out what other
attributes of the parallel machine have a bearing on the overall cost.
Reynolds M, Improved Parallel Route Planning for the London
Underground, Computer Science Tripos, Part II, Computer Laboratory, 2008.
Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms,
second edition, 2003.
Modi J, Parallel Algorithms and Matrix Computation, OUP,
Grama, Gupta, Karypis, Kumar, Introduction to Parallel
Computing, Pearson Education, second edition, 2005.
Akpan, O. Efficient parallel implementation of the Fox
algorithm. Computer Science Department, Bowie State University, 2003.