

2006 year, number 3
M. S. Tarkov^{1}, G. A. Gienko^{2}, B. V. Norenko^{2} and A. A. Zorin^{3}
^{1}Institute of Semiconductor Physics, SB RAS, Novosibirsk Email: tarkov@isp.nsc.ru ^{2}University of the South Pacific ^{3}Siberian Research Institute of Optical Systems, Novosibirsk
Pages: 412
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.

M. V. Deikun and V. P. Markova
Institute of Computational Mathematics and Mathematical Geophysics, SB RAS, Novosibirsk Email: markova@ssd.sscc.ru
Pages: 1320
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.

Yu. G. Medvedev
Institute of Computational Mathematics and Mathematical Geophysics, SB RAS, Novosibirsk Email: medvedev@ssd.sscc.ru
Pages: 2129
Abstract >>
the problem of cellular automaton simulating fluid flows in porous media is considered. A 3D cellular automaton model RD1 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.

S. E. Kireev
Institute of Computational Mathematics and Mathematical Geophysics, SB RAS, Novosibirsk Email: kireev@ssd.sscc.ru
Pages: 335
Abstract >>
An algorithm for 3D gyrodynamics simulation of a dust cloud by the particleincell 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 7times speedup on 32 processors.

O. I. Nechaeva
Institute of Computational Mathematics and Mathematical Geophysics, SB RAS, Novosibirsk Email: nechaeva@ssd.sscc.ru
Pages: 3644
Abstract >>
A neural network approach to constructing finitedifference adaptive meshes is proposed. It is based on the learning algorithm for Kohonen selforganizing 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.

E. V. Rusin
Institute of Computational Mathematics and Mathematical Geophysics, SB RAS, Novosibirsk Email: rev@ooi.sscc.ru
Pages: 4554
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. V. Snytnikov
Institute of Computational Mathematics and Mathematical Geophysics, SB RAS, Novosibirsk Email: snytav@ssd.sscc.ru
Pages: 5560
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.

S. M. Achasova
Institute of Computational Mathematics and Mathematical Geophysics, SB RAS, Novosibirsk Email: achasova@ssd.sscc.ru
Pages: 6166
Abstract >>
A parallel substitution algorithm was the base for developing a simple procedure of constructing a selfreproducing cellular structure of arbitrary size.

V. A. Vorobyev^{1} and N. V. Lakhodynova^{2}
^{1}Pomorsk State University, Arkhangelsk Email: vva@sanet.ru ^{2}Tomsk State University of Architecture and Building, Tomsk Email: lax@tomsk.su
Pages: 6773
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.

V. A. Vorobyev
Pomorsk State University, Arkhangelsk Email: vva@sanet.ru
Pages: 7480
Abstract >>
A definition of a parallel automaton, that is a Pautomaton, is given. Notions of atomic, partial, and complete states of a Pautomaton, 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 Pautomation description are formulated. Three modes of its functioning, namely, synchronous, ordinary, and mixed, are considered. Statements about the conditions of reducing a Pautomaton to a parallelsequential composition of sequential automata and on sufficiency of the ordinary Pautomaton model are formulated.

A. V. Selikhov
Institute of Computational Mathematics and MathematicalGeophysics, SB RAS, Novosibirsk Email: selikhov@ssd.sscc.ru
Pages: 8189
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 intercluster 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 intercluster 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 lowlevel functions of the protocol TCP/IP.

E. A. Monakhova
Institute of Computational Mathematics and Mathematical Geophysics, SB RAS, Novosibirsk Email: emilia@rav.sscc.ru
Pages: 90101
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 twoterminal routing algorithm and a broadcasting algorithm that minimizes the time of execution and the load of messages in the network are developed for them.

Yu. K. Dimitriev
Institute of Semiconductor Physics, SB RAS, Novosibirsk Email: dimi@isp.nsc.ru
Pages: 102110
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.

