Algorithm Engineering
Associated Researchers:
Prof. Raman,
Dr. T. Erlebach,
Dr. N. Rahman,
Dr. S. Yang,
Algorithm engineering includes the implementation,
experimental testing, and finetuning 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
cacheefficient 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 floatingpoint keys.
Our experiments suggest that it
is two and a half times as fast as highlyoptimised Quicksort.

Cacheoblivious algorithms: Cacheoptimised algorithms typically
need to have platformspecific parameters coded into them such as
the size of the cache. An interesting
new development is that of cacheoblivious algorithms which
give optimal cache performance without knowing any cache parameters.
The practical advantage is that cacheoblivous code can be ported
easily between platforms.
Several exciting new cacheoblivious 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 wordlevel parallelism:
Even ordinary "sequential" processors incorporate
parallelism of various kinds. One fundamental form
of parallelism — wordlevel parallelism (WLP) — exists
at the level of hardware circuits, and is used by a
processor to say add 64bit numbers in one step.
Recently there has been a great deal of activity in the underlying
theory of transdichotomous 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 socalled "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, realtime systems, our work will
also extend to dynamic network flow problems. We also involve research on
some relevant graph problems.
