[Icfp04-discuss] ant simulator in parallel?

[Mario Storti]

Hi all,

I wonder if it would be interesting to wrote a simulator in
parallel. I think in distributed computing in a Beowulf cluster using
MPI. I wrote a Conway's Life simulator, mainly as an example for a
Parallel Computing course i give. In that simulator the updating of
cells is not `sparse', it is done by simply looping on all the cells. 

In this cases it _should be_ sparse, and this poses some complexities
in writing the parallel code. One should write (and update) a graph of
the ants (by proximity in their cells). The graph should be
partitioned. This could be done every time step, or each `n' time
steps. In this last case one should include a `safety strip' of ghost
cells around the set being simulated in this processor. 

This kind of tasks are difficult to parallelize because the computing
time per step is very low, and any additional thing you do every time
step (like building the graph, for instance) may be more expensive
than the update itself. This pushes the scale of problems where
parallelization is efficient to very large number of ants. 

I wonder if it could have some interest to perform simulations
of very large number of ants on very large boards. Is this going to
give some essentially new global behaviors (for similar ant density),
or the results will be similar to those obtained with smaller boards? 

Regards, Mario

-------------------------
Mario Alberto Storti
CIMEC (INTEC/CONICET-UNL), Guemes 3450 - 3000 Santa Fe, Argentina
Tel/Fax: +54-342-4511594 e-mail: mstorti at intec.unl.edu.ar
http://www.cimec.org.ar/mstorti, http://www.cimec.org.ar
-------------------------