[SciPy-Dev] Robert Kern's accursed excellent DE implementation

[James Phillips]

I have been thinking about the parallelization of Differential Evolution
(DE), and would like to share my thoughts as this can be done in scipy.

For references, here are links to PDF versions of:

1) The original DE paper by Rainer Storn and Kenneth Price:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.9696&rep=rep1&type=pdf

2) An example strategy for SMP parallelization:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.3.6508&rep=rep1&type=pdf


There are two basic strategies for perallelization.

The first strategy is to process the calculations for each individual
generation in parallel chunks, which can be done if those calculations are
independent of each other.  This approach is embarrassingly parallel and
calculations can either be done on seperate CPU cores by either cluster or
SMP parallelization, or if a graphics processor is available they can be
moved to a GPU.  If you have the money, of course, a cluster of computers
each with a GPU would be wicked fast!

The second strategy, discussed in reference (2) above, is to process
different random subpopulations on multiple CPU cores or computers and
combine results.  This could make use of the first strategy as well,
running each separate subpopulation itself in parallel, bust is not
required.


If however a single CPU only is available, then the current serial-only
strategy of improving the population in-place is fastest on such a
machine.  While the first strategy above cannot be used to parallelize the
current implentation, the second strategy CAN!

So all is not lost, there is a way to parallelize the existing
implementation for machines that have single or multiple cores.  The
existing algorithm is not GPU parallelizable as calculations within a
generation are not independent, but for the second strategy this is
irrelevant.  No structural changes to the existing algorithm are required
and it can run as-is on single-CPU machines

 Combining the current in-place improvements with strategy #2 is the
fastest way DE can be run on multi core or many-core computers, but may
never have been done before. Is that a doctoral thesis I smell?

James
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20150327/284c26a0/attachment.html>