Vladimir Beletskyy
Technical University of Szczecin
Poland
email: vbeletskyy@wi.ps.pl
Alexander Chemeris
Institute of Problems of Modeling in Energetics
Ukraine
email: a.chemeris@ukrpost.net
Asynchronous iterative processes for control of calculations in multiprocessor and multi-computer systems are considered. The opportunity of asynchronous work at the realization of various numerical methods for the solving of the algebraic equations systems, both linear and nonlinear, was discussed enough for a long time [1,2]. However, the practical realization of these processes is coveredlittle. The paper shows the opportunity of realization of asynchronous iterative processes in computers with common memory and in distributed systems.
The organization of asynchronous process is performed as follows. We shall consider the most simple case when the computing system consists of two processors. Let the first processor calculates sub-vector of unknowns with indexes 
, and the second one supports
correspondingly. Because of non-uniform computing loads the idle times of processors occur in the case of synchronous iterative processes. As continuation of calculations needs updating of all components of unknowns then one of processors should expect the finishing of the second one calculations for the current iteration. After that the synchronous iterative process may be continued.
In case of asynchronous algorithm the finished calculations processor after storing of results in the common memory does not expect other processors. It continues calculations with the values, which are received for this moment of time. Thus, the idle times of processors are avoided.
In earlier published works it is shown that the class of asynchronous iterative algorithms is more general modification of known synchronous ones. So, there were explored the convergence problems in [4], necessary and sufficient conditions were defined and there were shown that asynchronous methods are suitable in cases where their synchronous analogues do not work.
The purpose of our paper is to show an opportunity of realization of asynchronous iterative methods by means of modern operating systems. So, Unix, Linux and WindowsNT/2000/XP allow to work with several processors by the multi-threads programs. The same processes can be realized in the distributed systems due to using of MPI.
As a practical problem the modeling of transient processes in a linear pipe of gas-transport system is chosen. In a general view the processes are described by a system of differential equations which joins pressure, temperature and the flow rate of gas in various points of the pipeline. The methods to solve such systems are known. For example, in [3] the iterative method of Newton is applied and its linearization is carried out. Thus, the problem is reduced to the solving of the linear algebraic equations system of 3*N dimensions, where N is the number of the pipeline discretization points.
The simulation of the transient processes in a linear part of a pipeline was executed on a dual-processor computer and the number of threads are varied. Time of program execution is measured. The model was with the following parameters: the length of the pipeline is 10 km; the flow rate values, pressures and temperatures of gas were calculated in 5 points. The values were measured in time with step that is 180 sec. Results of experiments were presented as dependence of calculation time on number of threads. The realization with one thread is equivalent to synchronous algorithm. Thus, practical experiments show that for the such simple problem the fivefold reduction of the time of solving is achieved by changing the uniprocessor realization to the dual-processor one. The small time increase at three, four, etc. threads is explained by an overhead charge for access to the common memory.
References:
[1]. Baudet G.M. "Asynchronous Iterative methods for Multiprocessors" // J. of the ACM - 1978 - 25, N2 - pp. 226-244.
[2]. A. Bojanczyk, "Optimal asynchronous Newton method for the solution of nonlinear equations", J. Assoc. Comput. Mach. 31 (1984) pp792-803.
[3]. Beletsky V.N. "Multiprocessing and Parallel Structures with asynchronous calculations." - Kiev: Naukova Dumka, 1988 - 240 P.
[4]. Kulik M.N., Matveev S.V. "Mathematical model and an algorithm for analysis of non-stationary modes of the main gas pipelines". - Electronic modeling, 1985, N5, pp. 3-11.