Source:
(1998)
URL:
http://citeseer.ist.psu.edu/245675.html
Keywords:
genetic algorithms;
genetic programming;
memory
Abstract:
Many of the various proposals for tomorrow's
supercomputers have included clusters of
multiprocessors as an essential component. However,
when designing the systems of the future, it is
important to insure that the nature of the parallelism
provided matches up with some relevant and important
set of algorithms. This project presents empirical
program synthesis as an algorithm that can successfully
exploit the multiple levels of interconnect present in
an multi-SMP cluster system. When applying program
synthesis techniques to difficult problems, it is often
the case that two distinct levels of parallelism will
emerge. First, many example programs must be tested --
and can often be tested in parallel. This matches up
with the "slow" interconnect on a clump-based
system. Second, the execution of a particular program
can often be parallelized, especially if the program is
complicated or requires interactions with a complex
simulation. This level of parallelism, in contrast to
the first, often requires fine-grained communication.
Thus, this matches up with the "fast" level of the
clump-based system.
In particular, this project presents a multi-level
parallel system for the automatic program synthesis of
soccer-playing agents for the Robocup simulator
competition using genetic programming. The system uses
both the fast shared-memory communication of the SMP
system as well as a much slower mechanism for the
inter-SMP communication. The system is benchmarked on a
variety of configurations, and speedup curves are
presented. Additionally, a simple LogP analysis
comparing the performance of the designed system with a
single-processor based NOW system is presented.
Finally, the Robocup project is reviewed and the future
work outlined.