McGill University
School of Computer Science

Computer Science 308-767: Parallel Programming

Life and death in the ocean: fish and sharks (WATOR)

In this assignment we are going to seek dynamical load balancing in a problem that involves synchronous computation: our program must wait for all the processors to finish each step, because the global result of each step is needed for the next (this is very typical of physical models whenever there is time ticking).

The problem involves a simple model of population dynamics studied in ecology. This model became famous after it was presented in the Computer Recreations column of Scientific American [A. K. Dewdney, Sharks and fish wage an ecological war on the toroidal planet Wator, Scientific American, December 1984]. Wator is a toroidal (donut-shaped) planet, entirely covered by a warm ocean. The ocean is inhabited by predators (sharks) and prey (fish), and it is represented by a rectangular matrix: each element of the matrix corresponds to a location in the ocean, which can be empty, contain exactly one fish, or contain exactly one shark. Time is also subdivided in standard units, known as chronons.

This is how we model the behavior of predator and prey:

These rules are sufficient to create a simple model of predator-prey interaction that displays a behavior similar to that observed in some populations in nature. . When there are enough fish to go around, the sharks can prosper and breed: but if the number of sharks grows too large, they will eat most of the fish and a famine will ensue.

In this assignment, you are going to write a parallel program that implements the Wator model by subdividing (dynamically, for load-balancing purposes) the rectangular matrix that represents the ocean between the parallel processors.

The Assignment