Parallella for Genetic Algorithms

[Weps]

I am working on a project that uses a genetic algorithm to generate design permutations that are then analyzed by a separate program and the results returned. This is a perfect candidate for parallel computing, as each design permutation can be analyzed completely independently. I'm hoping the Parallella can adapt to the problem, as my current design space is 1,000*N^2!

I would really like to order the cluster, but I have some feasability questions:

- Everything is written in C or Fortran, so compiling within Ubuntu should be straightforward. Can the Parallella be used as it's own design environment, or will it just be a headless cluster?

- The analysis program is about 2 Mb in size. Ideally, once the design stack is generated, every available core would take a design, analyze it, output results, and fetch the next waiting design. Is this even possible with Parallella? Is the analysis program too big, I.e. only executable by the ARM?

- And most importantly: To leverage the Epiphany cores, would I need to rewrite all my code? If I don't, will it just execute sequentially?

I'm really excited about the possibilities Parallella offers, as the more cores the better for these types of problems. Unfortunately, the only examples I've seen so far involve simple math/matrix operations, and I can't determine just what is possible for larger problems. I just hope my problem fits!

[LamsonNguyen]

[mhonman]

[CIB]

[mhonman]

[Weps]

[mhonman]

Weps, you're on the right track there. As you've spotted, it will be a killer to operate on data while it is in external RAM, but you can manage it by treating the internal RAM as an explicitly managed cache.

In other words, the core program fetches a chunk of the "problem" from external RAM, processes it, and shuffles it back to external RAM (the Adapteva matrix multiplication demo is an example of this technique, even if the C code is a bit mind-bending to read).

Since the Epiphany cores have two DMA channels, it is feasible (if the chunks are sufficiently small) to have fresh input data being read and results being written while calculation is in progress. There will probably be practical pitfalls - the approach takes one further & further away from the original code.

The ideal is for each core to have enough internal RAM that back-and-forth shuffling is not needed, but I suspect that is not a realistic expectation. 20+ years ago, 256KB was a tight fit for a SPMD parallelised 3D Navier-Stokes CFD code (half code + buffers, half data). On Parallella, much of that code could go into the external RAM, but that leaves 128KB of data to find a home for. Increasing the amount of internal RAM and/or increasing the speed and parallelism of external RAM would make Epiphany systems more generally useful.

[timpart]

You really want to avoid executing code from external RAM. It is very slow. I understand Embecosm (the compiler people) are looking into an overlay system for code.

Tim

[davidl]

Greetings to everyone,
I'm working now on my master thesis, and I'm trying to implement a genetic algorithm that runs on the Epiphany processor. I want to know if someone continued with this project, and what type of parallel algorithm was implemented (master-slave, coarse-grained). Any type of information will be really appreciated.

Respectfully,

David