iain@cs.strath.ac.uk (Iain Buchanan) (05/12/88)
RESEARCH ASSOCIATESHIP ON TRANSPUTER PROJECT
Dynamic Programming on the Meiko Supercomputer
SERC has funded a project to develop parallel algorithms to solve
dynamic programming (DP) problems using the Edinburgh Concurrent
Supercomputer. A wide range of Operational Research problems may be
formulated as DP problems, for example stock control, equipment
maintenance and replacement, queue control, capacity expansion and
manpower planning. These are all special cases of Markov decision
processes. Unfortunately realistic problems often produce formulations
with huge state spaces. Such problems require too much memory and take
too long to solve using existing algorithms on sequential machines and
this limits the practical application of DP.
The programme of research will involve developing and implementing
parallel versions of algorithms based on the standard, decomposition,
aggregation and reward revision methods used on serial machines. We plan
to investigate automatic ways of using the structure of a problem to decide
how to divide it up between the processors so as to minimize communication
traffic.
The grant is for 3 years starting in October 1988 and has funding for a
research assistant or fellow on the 1B or 1A scale, salary 8675-15720
pounds according to qualification. The person appointed will need to
become familiar with programming the Edinburgh Concurrent Supercomputer
and with the theory of DP. A quantitative background and some computing
experience is important. For further details please contact one of the
grant holders listed below.
Prof. Lyn Thomas, Business Studies, Edinburgh University, WRB, George Square,
Edinburgh EH9 8JY, Tel (031) 667 1011 ext 6577.
Dr. Ken McKinnon, Maths Department, Edinburgh University, King's Buildings,
Edinburgh EH9 3JZ, Tel (031) 667 1081 ext 2941.
Dr Iain Buchanan, Computer Science, Strathclyde University, Glasgow G1 1XH,
Tel (041) 552 4400 ext 3424.
--
"iain@uk.ac.strath.cs"