Publishing House SB RAS:

Publishing House SB RAS:

Address of the Publishing House SB RAS:
Morskoy pr. 2, 630090 Novosibirsk, Russia

Advanced Search


2003 year, number 3

Diffusion-reaction process simulation by cellular automata

Pages: 5–15

Abstract >>
A method is proposed for constructing a probabilistic cellular automaton (CA) whose evolution simulates a spatially distributed diffusion-reaction process. In the method, both the diffusion and reaction process components, which are usually given as a Laplace operator and a nonlinear function, respectively, are represented by special operations on Boolean arrays. The kernel of the operations is a transformation  of a real spatial function into a Boolean array whose averaged form approximates the initial function. Transition rules of the resulting CA are a combination of the transition function of a CA-model of the diffusion component and a probabilistic threshold function depending on the reaction. Approximation errors are assessed and some simulation results are presented.

Parallel substitution algorithm of a loop self-replicating in two directions

Pages: 16–20

Abstract >>
A parallel substitution algorithm (PSA) is developed. It models the process of structure self-replication in the cellular space in two directions (from bottom to top and from left to right); the structure having the shape of a tetragonal loop. The proposed PSA self-replication model is much more laconic compared with the classical cellular automaton model.

An associative version of the Lengauer-Tarjan algorithm for finding immediate dominators in a graph

Pages: 21–28

Abstract >>
An associative version of the Lengauer-Tarjan algorithm on a model of a parallel vertical data processor is presented. The algorithm is implemented as a procedure in the STAR language. The time complexity is estimated and correctness of the procedure is substantiated.

On percolation thresholds in homogeneous structures

Pages: 29–36

Abstract >>
Practically important results concerned with determination of percolation thresholds in homogeneous structures are proposed. Their usage allows one to estimate the bounds of reliability of homogeneous computing systems and the minimal requirements to reliability of processor elements.

3D cellular automaton model of viscous fluid flows

Pages: 37–43

Abstract >>
Cellular automaton models applied to hydrodynamics problems and also an original 3D model of a viscous fluid flow with 12 neighbors are considered. A program package for 3D flow simulation using the proposed model and results of experimental simulation are presented.

A computer cellular model of a visual cryptographic scheme

S.V.Piskunov and D.P.Shashkov
A cellular automaton implementation of a visual threshold secret sharing scheme is proposed. The implementation is done as a computer model in the WinALT fine-grain computation simulation system and can be the basis for constructing optoelectronic special-purpose devices executing such secret sharing schemes.
Pages: 44–51


Using the residue number system arithmetic for simulation of diffusion

Pages: 52–61

Abstract >>
Computational potentialities of the residue number system for simulation of a 1D diffusion process is investigated. The conventional finite-difference diffusion representation is modified in terms of the residue number system (RNS). Numerical simulation of the diffusion process was performed. The computational characteristics (stability, accuracy, and time complexity) are assessed and compared with similar ones obtained by the explicit method solution of partial differential equations.

Parallelization of the multiprogram complex for mathematical modeling of high-speed flows of a real gas

G.A.Tarnavsky and V.D.Korneev
Pages: 62–71

Abstract >>
The present paper is focused on application of modern computing technologies and methods of parallel programming directed to increasing the efficiency of solution of fundamental scientific and application problems. Technological aspects of parallelization of the computing system

Mapping parallel program structures onto structures of robust distributed computer systems

Pages: 72–83

Abstract >>
A technique for mapping parallel program structures onto structures of robust distributed computer systems (CS) is proposed. Effective algorithms are developed for implementation of the technique stages: 1) a heuristic algorithm for mapping nodes of the parallel program graph onto the graph of the distributed CS; the algorithm substantially reduces the mapping time with respect to the well-known Bokhari algorithm; 2) a decent- ralized algorithm for mapping the program graph edges which do not coincide with edges of the CS graph onto shortest paths on the CS graph. Mapping one-dimensional (line, ring) and two-dimensional (mesh, torus) parallel program structures onto regular structures (torus, two-dimensional circulant, and hypercube) of robust computer systems with faulty components (computers and intercomputer connections) is investigated. It is shown that: one-dimensional parallel program structures are mapped onto structures of distributed CS better than two-dimensional ones; and if defects (failures of the CS components) arise in the CS structure, the quality of mapping one-dimensional structures deteriorates less than the quality of mapping two-dimensional structures.

Parallelization of a Three-Dimensional Analogue of the Peaceman-Rachford Method

V.P.Il’in, V.M.Sveshnikov, and S.A.Litvinenko
Pages: 84–94

Abstract >>
The method of domain decomposition using a three-dimensional analogue of the Peaceman-Rachford algorithm is considered. Estimations of parallelization efficiency and results of numerical experiments on computers RM-600-E30 and MVS-1000 for different grid domains and processor topologies are presented.

Parallel program debugger for a multicomputer

V.E.Malyshkin and A.A.Romanenko
Pages: 95–99

Abstract >>
A parallel program debugger GEPARD developed in the Siberian Supercomputer Center is presented. The motives for creating the debugger, and also the architecture, implementation, and applications are considered.

On parallel implementation of the numerical model of gravitating system physics

V.A.Vshivkov, E.A.Kuksheva, S.A.Nikitin, A.V.Snytnikov, and V.N.Snytnikov
Pages: 100–107

Abstract >>
Parallel implementation and computational aspects of the problem of simulating dynamics of gravitating systems, in particular, a protoplanetary disc, are considered. The mathematical model of the disc involves the Vlasov-Liouville multidimensional kinetic equation, the Poisson equation, and gas dynamics equations. One of the main problems of numerical simulation of gravitational dynamics is the necessity of multiple solution of the Poisson equation. A fast parallel solver for this equation and a dynamic load balancing algorithm for processor elements are presented. They employ the physical peculiarities of the problem.


V.E.Malyshkin and A.A.Tsygulin
Pages: 108–118

Abstract >>
Basic ideas and algorithms for generating parallel programs for numerical modeling of large-scale problems are presented. Generation of a wide spectrum of programs is based on using a good man-made code, an assembly technology of parallel programming, parameterization, and macrogeneration. It is shown that these technological techniques taken altogether ensure a high quality of generated parallel programs and relieve the system user of having to program the procedures of synchronization, dynamic load balancing, and other elements of parallel program development whose implementation is difficult. The approach is implemented in the ParaGen system.