ogata@degas.nswc.navy.mil (Eric Ogata) (03/15/91)
Hello,
Sorry if there are problems with this posting. Still trying to
figure this thing out.
I am working on a problem to develop 'good' task allocations for
parallel/distributed programs in a multiprocessing environment.
To be more precise, the problem is this. I have a graph that
represents some task decomposition of a program, where nodes represent
tasks and links show the task dependencies and data volumes. I also
have a description of a hardware architecture describing
interconnected processors, with some crude estimate of the expected
run times for the different tasks on different processors,
descriptions of the communications links with data-rate and data
latencies. The problem is to develop algorithms that will provide
'good' allocations of the tasks to the processors. The allocations may
optimize for run-time, space-utilization, fault tolerance or some
combination of these things. I am specifically interested in using
genetic algorithm or simulated annealing techniques to find good
allocations. Other techniques for solving problems of this nature
would also be of interest.
If you know of someone that is working on a similar problem, or of
any good references to work along these lines please e-mail me. I have
access to some of the obvious references to GAs by Holland, and
Goldberg, also Lawrence Davis' new book about GAs, but I am interested
in any work with GAs (particularly) on a similar problem and am
especially interested in any ideas for coding (as a GA) this problem
and developing reasonable objective (cost) functions for this problem.
Thanks,
Eric Ogata
NSWC (301) 394-2355
ogata@degas.nswc.navy.mil