**Advantages of
parallel compared with serial computation, for route-planning problems and how
increased data size may affect this.**

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 we have usually assumed
that the number of processing elements and the problem size are comparable.
Here, however, the emphasis is on a much larger data size with a given smaller
number of processing elements available in practice [3,6].

Students have considered rail and road
networks, minimizing a single parameter such as distance or time, and found an
algorithm analogous to matrix multiplication to be
suitable for parallel computation [1].

The main aim of the project is to
implement such an algorithm, for example,
applying it to the California road network, and also 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].

It will then be of interest to see how
one deals with different cases, the ratio of data size to the number of
processing elements on a given system, and whether there is any fundamental
change to the design of the algorithm as one progresses
to even bigger data sizes.

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.