computer science

Algorithm Engineering

Associated Researchers: Prof. Raman, Dr. T. Erlebach, Dr. N. Rahman, Dr. S. Yang,

Algorithm engineering includes the implementation, experimental testing, and fine-tuning of theoretically efficient algorithms to the point where they can be usefully applied in practice. Algorithm engineering is a new branch of algorithms research that has grown rapidly in the past few years. Leicester is one of the UK's leading algorithm engineering centres.

Current work in this area includes (for related work in Leicester see the genetic algorithms and interconnection networks for parallel and mobile computing sections):

• Memory hierarchy optimisations: By analysing the data cache behaviour of sorting algorithms, we have developed very fast cache-efficient sorting algorithms. One of the algorithms we have developed, EPLSB radix sort, appears to be one of the fastest sorting algorithms for sorting integer and floating-point keys. Our experiments suggest that it is two and a half times as fast as highly-optimised Quicksort.
• Cache-oblivious algorithms: Cache-optimised algorithms typically need to have platform-specific parameters coded into them such as the size of the cache. An interesting new development is that of cache-oblivious algorithms which give optimal cache performance without knowing any cache parameters. The practical advantage is that cache-oblivous code can be ported easily between platforms. Several exciting new cache-oblivious algorithms have been developed recently. The practical worth of these ideas is as yet largely untested, but some promising results have been obtained at MIT as part of the FFTW (Fastest Fourier Transform in the West) project using related ideas.
• Exploiting word-level parallelism: Even ordinary "sequential" processors incorporate parallelism of various kinds. One fundamental form of parallelism — word-level parallelism (WLP) — exists at the level of hardware circuits, and is used by a processor to say add 64-bit numbers in one step. Recently there has been a great deal of activity in the underlying theory of trans-dichotomous RAM algorithms, where WLP has been exploited in imaginative ways to obtain asymptotically faster sorting and searching algorithms. Hopes for practical performance improvements have been improved by the introduction of so-called "multimedia" instruction sets in many processors (e.g. MMX/SSI and VIS instructions for Intel and Sun CPUs).
• Network flows: Network flow problems lie in the intersection of computer science, operations research, applied mathematics, and engineering. It is one of the classical combinatorial optimization problems and has numerous applications in areas as different as manufacturing, transportation, communication networks and financial analysis.
  The main network flow problems we investigate are the maximum flow problem, the minimum cost flow problem, generalised network flow problems, and dynamic network flow problems. We now focus on developing more efficient generalized maximum flow algorithms and on evaluating the existent ones. To meet the increasing demand on dynamic, real-time systems, our work will also extend to dynamic network flow problems. We also involve research on some relevant graph problems.

© University of Leicester 15th December 2000. Last modified: 17th April 2005, 22:47:54.
CS Web Maintainer. This document has been approved by the Head of Department.