Abstract of master's work

Development and research of topological analysis subsystem of network dynamic systems as objects of simulation

Introduction

Topic actuality

Different areas of modern science require the tools that would allow simulation of complex dynamic systems. These tools could predict the behavior of the system and identify possible errors with a sufficiently high accuracy at the early stage of its development without full-scale experiments.

Complex dynamical systems (CDS) are those physical systems that are characterized by purposeful changes in certain parameters over time and can be mathematically represented by a set of ordinary differential equations in Cauchy form and nonlinear algebraic equations.

A mathematical model of the CDS consists of a formal description of its topology and the set of equations that determine the physical nature of dynamic processes.

One of the CDS are network dynamic objects (NDO). These include mine ventilation network of the coal industry, which are represented as graphs. Input topology of such objects, graphical visual representation of the elements of the topology and the connections between them, the proper coding and the construction of the topological characteristics that are obvious or transformed as part of the mathematical description of the system, require significant time of qualified experts.

Thus, the overall computer support of this process is an actual problem: need to develop the subsystem of topological analysis (STA), which will automate the work with the topology of the NDO as part of a distributed parallel environment simulator (DPES). In addition, considering the current level of development of computer technology is the good possibility to use parallel programming for clusters. This requires development of special algorithms for the topological analyzer that will prepare all the necessary data for the parallelization of the modeling process and improve its performance.

The main goal is developing of the network topological analysis subsystem of NDO as a separate independent software module of DPES. The main resource, which will focus the work - a cluster of DonNTU - MIMD-system with distributed memory.

The problems of work

As a part of the development of topological analysis subsystem should be solved the following problems:

1. Developed data structures for representation of topology and characteristics of the NDO.
2. Designed algorithms for the analysis of the primary topology, its approximation, the partition of the original graph to a tree/anti-tree.
3. The principles of interaction with other subsystems and functioning as part of the DPES.

Scientific novelty:

1. Developed new optimized data structures for representation of the topology and algorithms for their processing.
2. Developed special algorithms for the implementation of graph partitioning on a tree/anti-tree and its approximation.
3. Developed data structures and specific methods for implementing the exchange of information with other subsystems of DPES.
4. For the first time realized and investigated topological analyzer for network dynamical systems as an independent software module within the DPES.

The practical importance of work:

1. Implemented a topological analyzer in the DPES for NDO with distributed parameters.
2. A software implementation of algorithms for the proposed new approach to coding the topology.
3. The algorithms for optimal partitioning of the topology graph to the tree/anti-tree and its approximation.
4. Developed a data structure to represent graph topology, algorithms and software implementations used in the research work of the CE department of the CST faculty.

↑ Go to top

STA functions

STA has the following functions:

1. Enter initial data representing the topology of the NDO and the physical characteristics of its components:
   • Getting NDO topology in the form of a data structure.
   • Reading the topology from the specialized file.
2. Topological analysis process:
   • Partition of the primary topology to the tree and anti-tree.
   • Construction of the incidence matrix A and matrix of independent circuits S.
   • Approximation of the branches of the graph and generating the secondary topology.
   • Topological analysis by the levels of parallelism.
   • Conversion of topological information units to the convenient form for generating equations.
   • Generating summary information.
3. Interaction with other subsystems (represented by UML-diagram in Fig. 1):
   • Getting initial data from the database (DB) through the subsystem of data exchange (SDE).
   • Processing of functions with given parameters, which determined by control subsystem (CS) at various stages of the DPES work.
   • Transferring data to subsystem of generating equations (SGE).
   • Save the results to the DB through the SDE.

Figure 1. Interaction diagram of STA with other subsystems

Silverlight animation: file size - 56,1 KB, dimensions - 477х222, duration - 15 sec, number of key frames - 67, multilingual, start by user click.

↑ Go to top

Conclusions

Thus, as a result of a detailed study of the topic of topological analysis revealed that there are no specialized practical developments of analyzers of NDO, which would be a part of the DPES and worked in its composition. This makes the implementation of the topological analyzer perspective, since working with large-scale topologies of NDO requires automation and computer support. In DonNTU this issue was fairly comprehensively reviewed and developed some algorithms, but they can not be implemented as a subsystem in the DPES with the proposed decomposition. Necessary to develop a new optimal data structures, methods of working with them and ways of interaction of STA with other subsystems.

When writing this abstract the master’s work was not completed yet. Final completion: December 2011. Full text of the work and materials can be obtained from the author or his supervisor after that date.

↑ Go to top

References

1. Simulation and Model-Based Design [Electronic resource] / Internet-resource. – Access mode : www/ URL: http://www.mathworks.com/products/simulink/. – Title from screen.
2. Easy5 for Controls and Systems Simulation [Electronic resource] / Internet-resource. – Access mode : www/ URL: http://www.mscsoftware.com/Products/CAE-Tools/Easy5.aspx. – Title from screen.
3. VisSim [Electronic resource] / Internet-resource. – Access mode : www/ URL: http://www.vissim.com/. – Title from screen.
4. Modelica and Modelica Association [Electronic resource] / Internet-resource. – Access mode : www/ URL: http://www.modelica.org/. – Title from screen.
5. Святний В. А. Стан розробок та перспектива інтеграції паралельних моделюючих середовищ з Grid-технологіями [Text] / В. А. Святний, О. В. Молдованова, А. М. Чут // Наукові праці Донецького національного технічного університету. Серія “Інформатика, кібернетика та обчислювальна техніка” (ІКОТ-2008). Випуск 9 (132). – Donets’k : DonNTU, 2008. – P. 103-110.
6. Dissertation (Master: Alexey Smagin, Group: VT-97-v) [Electronic resource] / Internet-resource. – Access mode : www/ URL: http://masters.donntu.ru/2002/fvti/smagin/diss/index.html. – Title from screen.
7. Давлетханов ДВ Моделирование сетевых динамических объектов Реферат [Electronic resource] / Internet-resource. – Access mode : www/ URL: http://masters.donntu.ru/2006/fvti/davlethanov/diss/diss.htm. – Title from screen.
8. Топологический анализатор [Electronic resource] / Internet-resource. – Access mode : www/ URL: http://www.students.cs.donntu.ru/vt95/vt95g/pererva/topan.html. – Title from screen.
9. Молдованова О. В. Способи організації паралельних обчислень в задачах математичного моделювання шахтних вентиляційних мереж [Text] : diss. … cand. of science : 01.05.02 / Молдованова Ольга Володимирівна. – K., 2008. – 152 p.
10. Чайка МА Автореферат [Electronic resource] / Internet-resource. – Access mode : www/ URL: http://masters.donntu.ru/2007/fvti/chayka/diss/index.htm. – Title from screen.

↑ Go to top