Russion version

Subdepartment of Real-Time CAD Systems

Institution of Russian Academy of Sciences
Dorodnicyn Computing Centre of RAS


works at the next problems:

1. Elaboration of Real-Time-Systems CAD;

2. Algorithms of work planning in multiprocessor systems;

3. Estimation of initial gas reserves and transfers in gas deposit.

1. Elaboration of Real-Time-Systems CAD - RTS-CONSTRUCTOR

RTS-CONSTRUCTOR is used for computer aided design and generation of real-time systems, fulfiling data processing of periodically entering from outside input data in the tempo of data entering, with time restrictions. With the help of RTS-CONST-RUCTOR the user can quickly build his own real-time system of application modules.

RTS-CONSTRUCTOR is nessessary everywhere the real-time systems are applied:

automation of experimental investigations;

control of complicated technical systems;

medicine - permanent control of patients state;

ecological monitoring;

scientific forecasting and passing of intellectual decisions.

Generation of real-time system

To generate his own real-time system a user must provide application modules ( C, FORTRAN, PASCAL and Assembler are allowed) and task for data processing in real time mode (RT-program).

All other job will be done by our RTS-CONSTRUCTOR!

It will successfully deal with such problems as synchronization of modules and data interchange, eliminating of deadlocks and optimization of application modules passing.

So, our RTS-CONSTRUCTOR supports all functions of system analyst and system programmer.

Basic principles of source language

Input data enter the computer periodically through I/O ports. These data form data frames. The structure of the frame must be described by user in his RT-program.

Using special constructions, named RT-loops, the user also defines tempoes of data processing and results visialization to be produced by different application modules in ratio to the period of data input. If these tempoes can be implemented, RTS-CONSTRUCTOR garantees that all directive periods will not be disturbed. Otherwise it prints a message that such data processing isn't possible to be produced on the user's computer.

RTS-CONSTRUCTOR differs from data stream systems, it permits to work with different data generations simultaniously - the system reserves special buffers for them.

The source launguage also gives an opportunity to react on input aperiodical signals (useful in case of extraordinary situaton with controlled object) and to fulfil application modules in background mode.

Algorithmic support

RTS-CONSTRUCTOR uses the original method of sheduling, ensures fulfilment of application modules in pre-defined derective periods. For this purpose the system builds the mathematical model of data processing in form of data stream graph.

Original algorithms also ensure optimal memory allocation during real-time session.

Current situation and nearest future

At present time version 1.0 of RTS-CONSTRUCTOR for IBM-compatible computers with MS DOS 3.30 and later is available for users. Application object modules must satisfy the MICROSOFT object standart for large memory model.

RTS, designed with RTS-CONSTRUCTOR, can recieve input information through ports COM1 and COM2, as well as through non-standard serial or parallel I/O ports.

In the nearest future we complete the system with dialog shell which gives a user an opportunity to write source task with menus only, avoiding source launguage.

2. Algorithms of work planning in multiprocessor systems

Preemptive and nonpreemptive sheduling algorithms are elaborated for multiprocessor systems when speeds of processors and release times, due data and processing requirements are known. Next problems were researched:

1. Demands to execute the jobs are entering periodically. A polynomial algorithm of construction of feasible schedule was elaborated. The algorithm is based on reduction this problem to network flow problem.

2. Interruption and preemption expenditures are took into consideration. This problem is NP-complete. For some particular cases algorithms were elaborated.

3. A restrictions of the processors communications which can be time-variable are took into consideration. This problem is NP-complete. The algorithm is based on reduction of initial problem to integer multiproduct network flow problem. This algorithm finds a feasible schedule and minimizes the number of

interruptions and preemptions.

4. In a case when demands to execute the jobs are entering periodically a set of processor speeds for which feasible shedule exist was constructed. This set is described by a system of linear inequalities.

5. A heuristic algorithm was elaborated. 4000 numerical experiments (when number of jobs was equal to 200 - 1000 and number of processors was equal to 50 - 250) showed that this algorithm requires a computer memory hundreds times as less and a processor time tens times as less than exact algorithms. The same time the number of sums in which feasible schedule exists but it has not been found by the heuristic algorithm was less than 5 %.

3. Estimation of initial gas reserves and transfers in gas deposit

The method of estimation of gas deposit parameters (gas reserves and transfer coefficients) was eleborated. The method is based on use of gas deposit block model elaborated by P.A. Geresh and on solving a material balance equations system.

As a rule, in the case of a pressures difference in different parts of exploited deposit is small a matrix of coefficients at undeterminate parameters of this system is singular. Known methods of solving of material balance equations systems are characterized by instability of results in relation to small variation of initial data. Suggested method does not have this defect and enables to estimate gas reserves and transfer coefficients at initial stage of exploitation of deposit.

The problem consists in finding the initial gas reserves in each block and transfer coefficients given the pressures and qauntities of mined gas in each block. Elaborated method is based on minimizing the deviation of average pressure in blocks and pressure calculated by means of the model (direct comparison of parameters measured). The numerical methods of solving this problem and different its modifications were realized by system EXCEL and programming language C. Elaborated programs were used for calculation of gas reserves and transfers in Sovetabad, Shebelinsk and Yamburg gas deposits.


Our address:

Moscow, 119333, GSP-1, Vavilova street, 40

Dr. Meran G. Furugian, Dmitry R. Gonchar


Phone (499) 135-4029, fax 135-6159;