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
Giandomenico Spezzano - ISI-CNR
Tel: +39 984 839047