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: at89@dial.pipex.com

  Special Resources: None

  Various investigations have been made into parallel algorithms for fastest-route determination, in particular (for example [1]) 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.

  References:

  [1]Reynolds M, Improved Parallel Route Planning for the London Underground, Computer Science Tripos, Part II, Computer Laboratory, 2008.
  [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.