Bak-Sneppen

baksnep_start

Bak-Sneppen, A simplistic model of competitive evolution…

Definition of the Bak-Sneppen model

This problem was brought to my attention by another student working on developing it for a research problem. I thought I’d mock up a parallel version just to play around. Its not necessarily appropriate, but it was the flavor of the month for my hobbies.

The system works as follows:

  1. Create a random environment of unsigned 32-bit integers.
  2. For each element in the environment, give it an index of the element directly less than and greater than or equal to.
  3. Move this structures onto the GPU along with…
  4. A 3 * batchSize list random integers
  5. Now each thread checks if it has a valid less than index, if not, it and its neighbors pop integers off the random list, overwrite their values, record their indexes, and remove themselves from the structure.
  6. Each thread not removed checks if the removed elements are greater than or equal to them, and less than their greater value, if so they re-insert those elements above them.
  7. It does this batchSize times
  8. Then once a batch is done, the GPU starts over

Meanwhile

  • The CPU is updating an array with new random values, and swapping pointers to keep random values fresh.
  • The CPU is copying the recorded changed indices to keep a record of what elements “died”

All together it ends up being pretty darn fast.

baksnep_end

Advertisements