MPI Genetic Monte Carlo Algorithm Resources?

Question

I have been working with some friends to convert a Matlab Genetic Algorithm to C++ and it works in a sequential order currently. Matlab is no longer a portion of our current code.

We are looking to use it on a cluster, but have been a little dry on resources. We have a cluster available at the University and it is equipped with Rocks and OpenMPI, but I'm not really sure where to begin working with it.

We currently have 2D and 3D Arrays setup with the data in them and when the system is doing crossover or exchanging between the models it just tries swapping parts of the 2D and 3D array. What are some good ways to separate these structures across multiple nodes?

Answer 1

If you're doing matrix computations, then whether there's even a good way to partition the calculations is highly dependent upon the calculation itself.

I'd highly recommend the Golub and van Loan book, "Matrix Computations, 3rd Ed.". In it there is an entire chapter devoted to parallel computations (Ch. 6).

OpenMPI is a fine middleware to use for this problem. Since you're doing this in C++, you might also take a look at zeromq. The two have different semantics, and one might favor your problem space or your skillset more than the other.

Also, you should know that parallel matrix computations (typically signal processing, but there are lots of other applications) is a very, very active area of research.

Answer 2

Fitness Calculation:

You typically just need to know about one individual to calculate its fitness, so you can just work through the population by doling out individuals to each core. When an individual's fitness has been calculated, hand that core a new individual.

Crossover:

A divide and conquer approach might be well suited to this problem. Break your arrays into blocks that are processed by each CPU core, then perhaps add a global crossover step (mating a subset of pairs) to ensure you have the ability to move through the multidimensional space appropriately.