AESOP home

Projects

CIMP: Communication Intensive Massively Parallel Algorithms

Staff
Prof. Peter Harrison
Dr Tony Field
Prof. John Darlington
EPSRC project GR/H46299/01
Started in April 1992
Completed in April 1995
Funded value
£93,536

Communication Intensive Massively Parallel (CIMP) Algorithms are unusual in that they solve problems by iterative message passing through the rich communication networks available on massively parallel machines. Information from both the presence and absence of incoming communication is applied during the process of reaching a solution.

The objective of the CIMP project is to widen the class of CIMP algorithms with special emphasis on solving pattern recognition problems.

Progress:

The CIMP technique has proved to be a very valuable mind set to use when designing novel pattern recognition algorithms. We have developed CIMP algorithms for pattern processing in audio and visual data with the following applications:

Recognition of fractally-compressed images. The CIMP algorithm provides robustness to rotation, scaling, displacement and noise, (paper at the International Conference on Parallel Processing, 1993). The image normalisation techniques developed are reusable for example to enhance Aleksanders WISARD machine.

Fundamental pitch period detection - in human vocalisations (paper at the International Conference on Acoustics, Speech and Signal Processing, 1993).

Recognition of temporal sequences - for example musical tunes and human speech. Dr Janko Mrsic-Flogel has designed a novel neural structure that can carry out implicit time warping (papers at international conferences on neural networks). A novel sequence recognition technique - with particular application to tune recognition - is being patented by Imperial College.

CIMP algorithms have been developed for Voronoi diagram construction, parallel sorting, Fourier transformation and fractal image generation. (Papers have been presented at European and IEEE conferences both on the algorithms and techniques for algebraically deriving CIMP algorithms from high level functional specifications).

During our collaboration with Dr Lyndon While of the University of Western Australia, we discovered that CIMP algorithms execute very quickly on sequential computers, as well as on parallel ones. This is because sequential computers can simulate interprocessor communication by indirect addressing on arrays, which is a very fast operation. For example the CIMP pitch detection algorithm executes in real time on a 486 PC.

In addition to the above algorithms we have produced an adaptive planning system, derived theoretical storage results for RAM-based neural networks and developed an entropy analysis tool for pruning the training data fed to neural networks.