Faculty: Computer Science
Speciality: System Programming
Abstract: Русский | Українська | English
Abstract of Master's Qualifying Work
“Implementation of parallel MIMD-simulator, 2nd level of paralleling”
Introduction
In many modern branches of science and technics, by development of technologies, in particular biotechnologies and environmental technologies, the concept of complex dynamic systems (CDS) plays the significant role. To CDS are generally referred automated technical objects, technological installations, lines, etc. Thus, progress in these branches depends on a level of the theory and practical realization of designing methods for complex dynamic systems. Development of parallel methods and algorithms for CDS-equation solvers is an actual problem of modern calculus mathematics.
Use of parallel resources opens essentially new opportunities of complex model construction and modelling support of CDS-projects, but it requires the new system organization of modelling means for CDS. Recently new directions of development and researches are forming - parallel modelling, territorially distributed modelling on the basis of GRID-technologies. The central problem of CDS parallel modelling is construction of distributed parallel modelling environments (DPME) of universal and specialized purpose.
The analysis shows, that parallel systems, that were built according SIMD- and MIMD-structures in 90th years, had proprietary languages of parallel programming based on Fortran, C, C++, Modula-2, etc. With intensive development of MIMD-based parallel computing systems and object-oriented approaches a necessity for standardization of means for parallel and distributed programming appeared. So, ANSI and ISO have defined C++-standards with libraries MPI, PVM and Pthreads. Necessity to build parallel models of dynamic systems with concentrated and distributed parameters forces developers to work at the level of available languages for parallel, consecutive programming and their libraries. It means, that software means of parallel models construction are at a level not above the second generation. [2] Therefore now development of language and system-organizational means which will provide the user with opportunities which surpass systems and languages of modelling of the fifth generation is expedient and actual for full-function development of modelling and simulating software for DPME.
Condition of the problem of DPME construction
Development of the parallel software for MIMD-systems was going in two directions - for modelling dynamic systems with concentrated parameters (DSCP) and for modelling dynamic systems with distributed parameters (DSDP).
In the software for DSCP MIMD-parallel languages of modelling are used; among them block-oriented, equation-oriented and object-oriented languages are distinguished. The program in one of these languages compiles to the program of the target computer. The compiler should generate virtual model of processor loading, construct process graphs, devirtualize models of processor loading, generate program codes of processes, distribute processors between processes and balance processor loading.
For the work of system the library is also necessary, which contains:
- support means for modelling languages (blocks for the block-oriented languages, operators for the equation-oriented and objects for object-oriented);
- parallel numeric methods of algebraic and differential equation solving;
- programs of visualization;
- auxiliary programs.
The parallel modelling software for DSDP is more complex. In this software the equation-oriented languages of DSDP-specification are used, which are capable to describe DSDP-equations of different types, system topology, edge and initial conditions, etc. Process of DSDP-model includes the analysis of system topology, generation of differential equations using an approximation method, generation of virtual model, construction of the process graph, balancing of processors loading using the static planning calculations, generation of program codes and process distribution between processors. After a model is constructed, it is debugged and realized on MIMD-resources.
The library which is used in the software for DSDP includes all means from DSCP library, a subsystem of visualization and auxiliary programs specific for DSDP, and support means for different types DSDP:
- parabolic;
- hyperbolic;
- elliptic;
- special, distinct from mentioned above. [2]
Development of a parallel MIMD-simulator for CDODP
Basic concepts:
- mathematical model - formal description of researched object;
- simulation model - model in the form, suitable for the numeric solving of equations;
- simulator - hardware-software realization of a simulation model;
- modelling and parallel modelling - all kinds of development and researches, aimed at construction and justification of consecutive and parallel simulators;
- research of DSDP using simulators is called modelling experiments or modelling. [2]
Development of a parallel MIMD-simulator for CDODP begins with structural analysis of CDS as an object of research and modelling. This analysis includes analysis of the physical processes flowing in the object, topological analysis of the object, etc.
Next development cycle is the construction of the mathematical model, including topology of the object and system of algebraic and differential equations. For complex DSCP and DSDP the generation of equation system is automated.
Mathematical model of CDODP
Mathematical model of the complex dynamic object with distributed parameters can be interpreted in the form of set containing the object graph and the system of differential equations describing each branch of the graph. For example, considering the model describing aerodynamic processes in the mine ventilating system, the system of the equations will have following form:
(1)
- P(x,t) - pressure in і-th branch of system;
- Q(x,t) - air flow rate in і-th branch of system;
- r - specific aerodynamic resistance;
- r' - adjustable specific aerodynamic resistance;
- x - spatial coordinate;
- F - cross-section area of excavation;
- а - sound speed in air;
- p - density of air. [1]
In a general view the system of differential equations in partial derivatives for the whole system will look like:
(2)
Animation 1. Mathematical model of a complex dynamic object with distributed parameters (gif-animation, 6 slides)
where n is the total number of branches in system.
Simulation model of CDODP
Development of the CDODP simulation model is going by means of the approximation of equation system in partial derivatives with system of the common differential equations with the help of the method of straight lines. The essence of a method is that each branch of object is represented in the form of a straight line divided into parts with length dx, as shown on fig.1:
Figure 1 - Representation of one branch of the object with the method of straight lines
Casting the above mentioned mathematical model to a kind, suitable for application of numerical methods of equation solving, we receive the system of a kind:
(3)
In a general view the system of differential equations in common derivatives for one branch of the system will look like:
(4)
Prior analysis of the virtual parallel model of second paralleling level
At the second level of paralleling one element of a branch (2 equations) corresponds to one process. The ratio "one element of a branch - one process" means, that the system of equations for k-th element (1 <= k <= n) branches is solved in corresponding k-th MIMD-process. The virtual parallel model for one branch is shown on fig.2.
Figure 2 - Virtual parallel model for one branch
From the illustration follows, that k-th process of a branch (QP)k executes such auxiliary operations:
- receives P(k) from next (k-1)-th process;
- receives Q(k+1) from next (k+1)-th process;
- sends Q(k) to next (k-1)-th process;
- sends P(k+1) to next (k+1)-th process.
Thus, on each step of a cycle each process should execute 4 exchange operations.
The level 2 virtual parallel model needs following quantity of virtual processes:
(5)
If the quantity of processors is known, minimal possible step is:
(6)
Conclusion
There are many branches for practical application of DPME. Modelling of mine ventilating networks and control systems for them, modelling of chemical technological processes, modelling of fuel elements and installations, and others can be referred to such branches.
It is possible to apply hybrid models of parallel programming (MPI+OpenMP) to development of simulators for DPME. Geographically distributed computing structures - GRID-systems also can be involved for solving this problem; that will play a significant role in the international cooperation.
Literature
- Svjatnyj V.A.: Virtuelle parallele Simulationsmodelle und Devirtualisierungsvorgang der Entwicklung von parallelen Simulatoren fur dynamische Netzobjekte mit verteilten Parametern / V.A.Svjatnyj.
- Святний В.А. Стан та перспективи розробок паралельних моделюючих середовищ для складних динамічних систем з розподіленими та зосередженими параметрами / В.А.Святний, О.В.Молдованова, А.М.Чут.
- Абрамов Ф.А. Моделирование динамических процессов рудничной аэрологии / Ф.А.Абрамов, Л.П.Фельдман, В.А.Святный. - К.: Наук. думка, 1981.
- Корнеев В.В. Параллельные вычислительные системы / В.В.Корнеев. - С. Пб.: "Нолидж", 1999.
- Святний В.А. Проблемно орієнтоване паралельне моделююче середовище для динамічних мережних об’єктів / В.А.Святний, О.В.Молдованова, А.О.Перерва. // Наукові праці ДонДТУ, серія «Інформатiка, кибернетика та обчислювальна технiка», вип. 29. – Донецьк, 2001.
- Гусєва Г.Б. MIMD-паралельний вирішувач рівнянь для мережного динамічного об’єкту з розподіленими параметрами / Г.Б.Гусєва, О.В.Молдованова. // Проблемы моделирования и автоматизации проектирования динамических систем: Сб. научн. тр. ДонНТУ, вып.6, Донецк, 2007.
- Масюк А.Л. Підсистема діалогу паралельного моделюючого середовища, орієнтованого на шахтні вентиляційні мережі / А.Л.Масюк. // Наукові праці ДонНТУ. Випуск 70. Серія ІКОТ: - Донецьк: ДонНТУ, 2003.
- Фельдман Л.П. Чисельні методи в інформатиці / Л.П.Фельдман, А.І.Петренко, О.А.Дмитрієва. К.:Видавнича група ВНV, 2006.
- PARALLEL.RU - Информационно-аналитический центр по параллельным вычислениям [Electronic resource]. http://parallel.ru/
- MPI Documents [Electronic resource]. http://www.mpi-forum.org/docs/
Abstract: Русский | Українська | English