From self-reproduction
cellular automaton to spatial dynamics models
Fine grained parallelism takes its origin from von-Neumann’s Cellular
Automaton (CA), which is nowadays referred to as a classical one. It was
a model of a certain biological community consisting of a set of bistable
identical “cells”, allocated in space and capable to compute a logical
function of neighboring cell states. All cells act simultaneously in parallel,
simulating in such a way a spatially distributed process. At first, a
CA was considered and used as an intellectual game (“game of life”) which,
nevertheless, resulted in better appreciation the fact that the cooperative
functioning of many very simple identical cells is capable to model complex
nonlinear processes. CA got its practical sense with the vigorous development
of microelectronics. At that time many fast parallel computational VLSI
devices have been designed on the base of CA-model.
A new epoch in CA theory and practice is associated with the search of
new, alternative relative to PDE, models of nonlinear dynamics. A number
of CA-models, such as CA for simulating viscous fluids (Gas-Lattice Models),
phase transitions, pattern formation and others were proposed and investigated.
Depending on the properties of modeled process some CA models were enriched
either by a powerful alphabet, or by complicated cell interaction structure,
or by probabilistic state transition functions. The whole scope of such
models, algorithms, and based on them computing technologies form the
concept of “fine-grained parallelism”. The growing interest in fine-grained
parallelism in modeling spatial dynamics has a twofold motivation. On
the one hand, being implemented in hardware fine-grained computations
may be three orders faster than those performed on the ordinary computer.
On the other hand, simulating nonlinear spatial dynamics using PDE systems
meets serious difficulties which may be partially overcome by fine grained
approach. Particularly, allocation of a big problem on the multiprocessor
system is efficient only when explicit time-space discretization is used,
i.e. when PDE representation meets the main condition of fine grained
modeling – locality and parallelism of intercell interaction, and, therefore,
may be considered as a “continuous CA”. Moreover, fine-grained algorithms
are simple to program, free of round off errors and stable.
Due to relatively short period of studying fine-grained parallelism for
modeling natural phenomena, there are many unsolved and sometimes not
yet stated problems. Some of them constitute the subject of our research.
Topics of the research and obtained results
Our research is performed in the following three directions.
1 Although originally CA – algorithms were perceived to be efficient
only for special purpose machines (CAM-8 being the bright example), their
advantages and, sometimes, absence of alternative possibility brings up
to the problem of assessment of their computational properties (accuracy,
stability, performance), when implemented on conventional computers or
multiprocessor systems, and to try to improve them. To approach the problem
a series of experiments were performed. In the framework of that direction
the following results are obtained.
- All known CA-models of diffusion are experimentally studied and compared
in order to choose the best for using in reaction-diffusion algorithms
[Bandman -2, Markova-9].
- The FHP Gas-Lattice model was experimentally studied and a modification
was proposed which allowed increasing the Reynolds’s number without
increasing the algorithm complexity [Medvedev-1].
- Three phase-separation models were experimentally studied in sequential
and parallel mode of implementation [Bandman -11].
- The 1D soliton was simulated as fine-grained explicit PDE solution
in sequential and parallel mode of implementation [Markova - 10].
2. Development of methods of fine-grained algorithms composition. Till
now we know a limited number of CA-models which have been worked out each
for a certain process (diffusion, Gas-Lattice, phase-separation, snow
flakes formation). In order to simulate complex processes, methods of
composition are needed. The similar problem is in mathematical physics.
There is a set of typical functions and differential operators, simulating
diffusion, convection, wave propagation etc. which being composed may
represent a large amount of processes. To approach the problem the following
research is performed:
- Algebraic properties of Cellular Automata were studied to form a
basis for composition methods [Bandman-10, Bandman-11]
- Some examples of fine-grained algorithms composition were performed
and experimentally studied [Bandman- 4, Bandman- 6]
3. A new 3D Gas-Lattice model with cellular structure, based on rhombododecahedra
is proposed and investigated. Each cell has only 12 neighbors which yield
in the quite allowable complexity of the transition function. [Medvedev-3,
Medvedev-4] This price of the low (relative to the known FCHC –model)
computational complexity is incomplete isotropy of the structure:
the isotropy conditions are met for tensors up to their third order (comparative
to fourth order for FCHC-model). A programming complex has been developed
for simulating viscous flows on a single computer and on the multiprocessor
[Medvedev-7]. A series of experiments showed a good compatibility with
analytical results for flows through tubes and for flows through the porous
medium [Medvedev-6].
4 A method of constructing irregular adaptive cellular space is proposed,
which is based on the neural network paradigm called Self Organizing Map
by Kohonen [Nechaeva, 1, 2]. The method is a learning procedure which
extends a regular mesh over the area given as a bitmap image, cell size
being determined by its local color. The program has been developed for
cellar space constructing and complexity of learning process is assessed
[Nechaeva-3, Nechaeva-4]. The method is intended to be used for simulating
natural processes by means of fine-grained algorithms on the stage of
their study.
Problems to be solved
Future research is intended to be directed to the following investigations.
1. Improvement fine-grained parallel computing technology by means of
accumulation the experience and refinement of program realization of fine-grained
algorithms
2. Extension the domain of fine-grained algorithms application by means
of
- developing and improving composition methods,
- developing fine-grained computing methods on adaptive cellular arrays.
3. Development of 3D Gas-Lattice-Boltzmann model of fluid flows to the
base of 3D rhombododecahedron structure.
The research team:
Prof. Olga Bandman- supervisor
of the project
Dr. Valentina Markova - senior researcher
Yuri Medvedev - researcher
Olga Nechaeva - junior researcher
|