A Cellular Automata Programming Environment for Computational Steering
by Giandomenico Spezzano
Cellular Automata (CA) theory
is a powerful tool that can be used to model and simulate complex systems
in many fields of computational science and engineering. Programming environments
that allow the interactive construction, debugging and steering of large
scale scientific computations are needed to simplify the work of scientists
and engineers. CAMEL is a system based on CA that integrates computation,
visualization and control into one tool for the interactive steering of
scientific computations on a parallel machine. It has been used to develop
high performance applications in geology, traffic planning, image processing,
genetic algorithms and in the CABOTO project, funded by the ESPRIT PCI
programme, to model and simulate the bioremediation of contaminated soils.
Many scientific areas, such as physics, chemistry, geology, and engineering,
are using computational simulation as an essential tool in research and
experimentation. The advantages of computer simulation over doing a real
experiment are that the user has full control over the conditions under
which the experiment is run and can observe all features of the phenomenon
at any time. Most computational problems in science and engineering exhibit
a significant degree of parallelism. Generally, these problems are 'regular'
in that identical operations can be performed in parallel on each computational
element (eg, grid cell or particle) and 'static' so that the topology of
interactions between neighbouring elements does not change as the simulation
progresses. In this case, the use of the CA paradigm is very effective.
CA are discrete dynamic systems composed of a set of cells in a regular
spatial lattice, either one dimensional or multidimensional. They are characterized
by the following properties:
- each cell can have any one of a finite number of states
- the states of all cells are updated synchronously according to a local
rule, called transition function
- the evolution takes place in discrete time steps.
CA are very effective at solving scientific problems because they can
capture the essential features of systems in which global behaviour arises
from the collective effect of numerous simple, locally interacting components.
CA model a problem in a naturally parallel way as a collection of identical
transition functions (set of rules) applied to all the cells of the automaton.
This bottom-up approach differs from that standard to parallel computation,
in which a problem is split into independent subproblems, each solved by
a different processor, and then combined in order to yield the final solution.
Figure 1: The CAMEL's graphical user interface.
Figure 2: A snapshot of the visualization tool.
Although CA provide an intrinsically parallel model, to use this model
effectively on a parallel machine a programming environment has to be built.
CAMEL is an interactive parallel programming environment, developed in
the CABOTO project, that uses the CA model both as a computational model
for parallel processing and as a tool to model and simulate dynamic complex
phenomena. CAMEL has been designed to allow an efficient simulation of
CA models on a parallel machine. It offers the computing power of a parallel
computer although hiding the architectural issues from the user. The environment
consists of:
- a programming language, called CARPET, which can be used to define
a cellular algorithm within the CAMEL environment
- a graphic user interface (GUI) for editing, compiling, configuring,
executing and steering the computation
- a tool for the interactive visualization of the results.
CARPET is a high-level language based on C with additional constructs
to describe the rules of the transition function of a single cell of a
cellular automaton. The main features of CARPET are the possibility to
describe the state of a cell as a set of typed substates, each one as a
user-defined type, and the simple definition of complex neighbourhoods
(eg hexagonal, Margolus, etc.) that can be also time dependent, in an n-dimensional
discrete Cartesian space. CAMEL visualizes the results on the fly at each
visualization step defined by the user. Using the results of the visualization,
through the GUI, a user can interactively change the parameters of the
model, the value of some substates, and other aspects of the simulation
to control and steer the computation to better fit the experimental data.
CAMEL has been used with success to simulate many real world applications
by an interdisciplinary team of computer scientists, geologists, mathematicians,
and physicists. The applications developed with CAMEL regard the simulation
of lava flows from Mount Etna and the evolution of landslides, a microscopic
simulation of highway traffic, and the bioremediation of contaminated soils.
This last simulation has been carried out within the CABOTO project. More
information on the partners, the model and the results of the CABOTO project
can be found at: http://isi-cnr.deis.unical.it:1080/~spezzano/intercab/main.htm
Please contact:
Giandomenico Spezzano - ISI-CNR
Tel: +39 984 839047
E-mail: spezzano@deis.unical.it
