Publishing House SB RAS:

Publishing House SB RAS:

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

Advanced Search


2006 year, number 3

Analysis of Parallelization Efficiency of the Algorithm for Image-Sequence Geometrical Transformation

M. S. Tarkov1, G. A. Gienko2, B. V. Norenko2 and A. A. Zorin3
1Institute of Semiconductor Physics, SB RAS, Novosibirsk
2University of the South Pacific 3Siberian Research Institute of Optical Systems, Novosibirsk
Pages: 4-12

Abstract >>
A method for finding the mutual correspondence between stereopair frames and geometrical transforming a videoimage sequence is presented. The method is adapted to parallelization and implementation on a cluster computer system. Two schemes for parallelization of the videoframe transformation process are considered. Efficiency of the proposed parallelization algorithms is analyzed a priori.

investigation of Wave-Process Cellular Automaton Models

M. V. Deikun and V. P. Markova
Institute of Computational Mathematics and Mathematical Geophysics, SB RAS, Novosibirsk
Pages: 13-20

Abstract >>
Models based on Lattice Gas Cellular Automata (LGCA) can be considered as an alternative to the traditional approach to spatial dynamics simulation. The possibilities of using LGCA automata to simulate a 2D wave are investigated. Results of some experiments (simulation of moving boundaries, effects of quiescent particles on the wave propagation speed, and wave simulation in inhomogeneous media) are discussed.

Applying the Cellular Automaton Model of a Viscous Fluid Flow in investigating 3D Porous Media

Yu. G. Medvedev
Institute of Computational Mathematics and Mathematical Geophysics, SB RAS, Novosibirsk
Pages: 21-29

Abstract >>
the problem of cellular automaton simulating fluid flows in porous media is considered. A 3D cellular automaton model RD-1 was used. the model structure is briefly described. The boundary conditions and the time averaging procedure are considered in detail. A series of computational experiments concerned with simulating a fluid flow through a porous medium is presented. The flow characteristics are compared with the Darcy law and other physical laws.Tthe velocity field of a model flow in a porous medium is illustrated.

Parallel Realization of the Particle-in-Cell Method for Simulating Gravitational Cosmodynamics Problems

S. E. Kireev
Institute of Computational Mathematics and Mathematical Geophysics, SB RAS, Novosibirsk
Pages: 3-35

Abstract >>
An algorithm for 3D gyrodynamics simulation of a dust cloud by the particle-in-cell method is considered. Approaches to parallelization of the methods are presented. Three versions of parallel realizations are compared. The best parallel program version gave a 7-times speedup on 32 processors.

Neural Network Approach to Constructing 2D Adaptive Meshes

O. I. Nechaeva
Institute of Computational Mathematics and Mathematical Geophysics, SB RAS, Novosibirsk
Pages: 36-44

Abstract >>
A neural network approach to constructing finite-difference adaptive meshes is proposed. It is based on the learning algorithm for Kohonen self-organizing maps. An algorithm for constructing meshes illustrated by an example of 2D domains on a plane is presented. It is shown that the proposed approach allows parallel mesh construction with a more than 90 % efficiency.

Vertical Data Representation in Image Processing on Multiprocessor Computers

E. V. Rusin
Institute of Computational Mathematics and Mathematical Geophysics, SB RAS, Novosibirsk
Pages: 45-54

Abstract >>
An experimental Parallel Library for Vertical Image Processing (PLVIP) based on vertical data representation is considered. The main characteristics of the library (data format, computing process management, and implemented programs) and examples of its application are presented.

A Parallel Method for Solving the Poisson Equation

A. V. Snytnikov
Institute of Computational Mathematics and Mathematical Geophysics, SB RAS, Novosibirsk
Pages: 55-60

Abstract >>
A parallel method for solving the Poisson equation as a result of using the fast Fourier transform is constructed. The main feature of the method is increasing speedup of a parallel program due to applying a multigrid method to calculating the zero potential harmonic. A multigrid method for cylindrical geometry is implemented.

Simple Procedures of Self-Reproducing Cellular Structure Rearrangement

S. M. Achasova
Institute of Computational Mathematics and Mathematical Geophysics, SB RAS, Novosibirsk
Pages: 61-66

Abstract >>
A parallel substitution algorithm was the base for developing a simple procedure of constructing a self-reproducing cellular structure of arbitrary size.

Reducing the Problem of Nodes of the Percolation theory to the Problem of Links

V. A. Vorobyev1 and N. V. Lakhodynova2
1Pomorsk State University, Arkhangelsk E-mail:
2Tomsk State University of Architecture and Building, Tomsk E-mail:
Pages: 67-73

Abstract >>
A method for replacing the problem of nodes of the percolation theory by the problem of links is described. It is hypothesized that the correlations arising between the states of grid elements do not change the values of critical percolation probabilities. the hypothesis is partially substantiated.

Parallel Automaton Model

V. A. Vorobyev
Pomorsk State University, Arkhangelsk E-mail:
Pages: 74-80

Abstract >>
A definition of a parallel automaton, that is a P-automaton, is given. Notions of atomic, partial, and complete states of a P-automaton, a parallel input and output are introduced. Parallel functions of transitions and outputs, which are given by transition and output matrices, are defined on these sets. Conditions to which the matrices should correspond in order to ensure a correct and unique P-automation description are formulated. Three modes of its functioning, namely, synchronous, ordinary, and mixed, are considered. Statements about the conditions of reducing a P-automaton to a parallel-sequential composition of sequential automata and on sufficiency of the ordinary P-automaton model are formulated.

Closed Cluster integration Based on inter-Cluster Communication Service

A. V. Selikhov
Institute of Computational Mathematics and MathematicalGeophysics, SB RAS, Novosibirsk
Pages: 81-89

Abstract >>
A new approach to integration of computing clusters for higher total performance is presented. the limits arising from local addressing of nodes in the clusters are overcome. the architecture of inter-cluster communication service, the functions of its components, and a model of application management based on the Service are considered. the dependence of the number of inter-cluster communication channels on the number of clusters and processes of a parallel application is shown. Results of performance tests of the Service are illustrated by a model and real systems of two closed clusters. Efficiency of utilizing the Service is shown in comparison with utilizing low-level functions of the protocol TCP/IP.

Triple Circulant Communication Networks of Parallel Computer Systems

E. A. Monakhova
Institute of Computational Mathematics and Mathematical Geophysics, SB RAS, Novosibirsk
Pages: 90-101

Abstract >>
Problems of optimizing the structure and organizing the exchanges in circulant networks used as communication networks of parallel computer systems are considered and results obtained in this field are reviewed. Triple analytically defined circulant networks of any diameter with the maximum number of vertices are obtained. An effective dynamic two-terminal routing algorithm and a broadcasting algorithm that minimizes the time of execution and the load of messages in the network are developed for them.

Dependence of the Structural Robustness of Embedded Diagnostic Group Graph on Choosing the initial Vertices of Its Cosets

Yu. K. Dimitriev
Institute of Semiconductor Physics, SB RAS, Novosibirsk E-mail:
Pages: 102-110

Abstract >>
Embedding of a diagnostic circulant graph into a graph of computing system intermodule connections is considered. the host graph is a graph of group of direct product of cyclic subgroups. The embedding is bases on partitioning the group into cossets via a cyclic subgroup of the chosen element degrees. Dependence of the introduced robustness index of the embedded circulant on the relative position of initial vertices in cossets of group is studied. It is found that the structural robustness index value depends substantially on the mentioned factor. Embedding parameters for which the embedded graph structural robustness does not depend on the relative position of initial vertices in its cossets are found.