Others involved: Kevin Sewell
Start date: 1989
Our aim is to make parallel processing much more easy to use by automatically converting programs into a parallel form. Whilst the need for parallel processing is recognised as a major method of increasing the performance of computer systems, there is a bottleneck in the design of parallel algorithms. Here the problem of designing parallel algorithms is completely bypassed by automatically converting ordinary programs into a form suitable to run on a network of computers.
It is in general very difficult to automatically parallelise programs. Just as it is difficult to reason about the correctness of procedurally designed programs, the same applies to analysing them for parallelisation. This problem is solved by parallelising functionally designed programs in LISP. It is possible to determine which functions are designed purely functionally, and thus to not restrict designers to 100% functional programs.
A key insight of this research is that one should only parallelise functions which are time consuming, and that it is possible to build models of how long functions will take to run. Many researchers believe that it is impossible to estimate how long a function will take to run. However, whilst this is true in general (otherwise the halting problem would be solvable), it is possible using heuristic techniques to build reliable estimators most of the time.
The AUTO PARALLEL LISP system currently runs on Apple Macintosh computers, and work is in hand to move the system to other platforms. Future research is possible in a number of areas including the extension to massively parallel systems and more sophisticated transformations into parallel code.
Page by Kevin H. Sewell
Last updated 24/October/95