Supercomputer Software Department

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' 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.