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 flow problems lie in the intersection of
computer science, operations research, applied mathematics, and
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.