Statement of the problem of optimization of the structure information processing computer appliances for real-time control systems

A real-time system (RTS) is a hardware and software complex (HSC) that solves the problems of controlling various processes in conditions of time constraints.

Many modern control systems are real-time systems for which performance is a critical parameter: the control action must be developed in the required time, otherwise it becomes useless. This class of control systems includes, for example, control systems used in the rocket and space industry, air traffic control systems or technological process control systems. [1; 2].

Such control systems are hardware and software complexes that are a set of hardware and software that work together to accomplish a given task.

Requirements for the performance of computing systems used in real-time control systems are constantly increasing due to the increasing complexity of control objects.

Increasing the speed of computing technology has traditionally gone in two ways: increasing the clock frequency of processors and developing multiprocessor systems. Today, we can state that the possibilities of increasing the clock frequency have been exhausted, which is due to physical limitations [3]. This means that real-time control systems will inevitably be created on the basis of multiprocessor computing systems.

It is important to understand that the hardware performance requirements for real-time control systems are determined by the software that is used to generate the control action. Special requirements are also imposed on the software of real-time control systems related to the need to ensure that the correct control action is obtained in a strictly defined time. Therefore it is advisable to study the performance of multiprocessor computing systems in close connection with the functioning of software.

For the design of multiprocessor hardware and software systems, a model of their performance is needed, which would make it possible to determine the speed of architecture options without experimentation, which can be extremely time-consuming and require significant costs.

The existing models of performance of multiprocessor computing systems [4–6] do not take into account the possibility of hardware failures and its recovery. In practice, when designing hardware and software complexes of control systems real-time, this aspect cannot be ignored, since a decrease in performance due to the failure of one of the processors can lead to the impossibility of generating a control action in the required time, which is unacceptable for real-time systems.

Performance model and formulation of the optimization problem

We consider a more general performance model, which includes additional states in which not all processors and buses are healthy, as well as transitions between states corresponding to processor and bus failures, as well as their recovery. The computing system is considered as a queuing system (QS).

The investigated HSC consists of N types of processors containing by M i ( i = 1, 2, ... N ) processors of each type with the average execution time of one instruction Т 0 i . Processors are combined with RAM via N 1 buses. The service time of a request from a processor of the i type is τ i . It is assumed that the time interval between any two adjacent claims obeys the Poisson distribution law with the parameter ν i . The total flow of failures from processors of all types and interface buses also obeys the Poisson distribution law with the parameter λ i . In addition, when evaluating the performance of a computing system, it is assumed that the time interval between two adjacent services obeys an exponential distribution law with the parameter µ i , and the recovery time of buses and processors of the i type obeys the exponential law with the parameter ξ i .

The states in which the considered system can be will be denoted as a ^{k , l} . In n , m ₁, m ₂, ..., m_N , j ₁, j ₂, ..., j_N .

this case, ( N 1 – n ) interface buses are in good order and participate in the computational process, and n are faulty and are restored, ( M 1 – m 1 ) processors of the first type are serviceable and participate in the computational process, while m 1 are defective and are being restored, ( M 2 – m 2 ) processors of the second type are serviceable and participate in the computational process, and m 2 are faulty and restored, ..., ( M N – m N ) processors of the N type are in good order and participate in the computational process, and m N are faulty and restored. The system contains j 1 requests from processors of the first type, j 2 requests from processors of the second type,…, j N requests from processors of N type, k buses are busy with servicing, and l requests are in queues for servicing.

Due to the ordinariness of the streams of memory accesses, memory servicing of processors, failures and recovery of hardware components, transitions are possible only between states that differ in the value of only one index, and this index can either increase or decrease by one.

Composing the system of Kolmogorov – Chapman equations [7] according to the general rules for queuing systems, we obtain a system of linear differential equations for the probabilities of states in which the system can be.

Equating the derivatives to zero in this system, we obtain a system of linear algebraic equations for the probabilities of states in a stationary mode.

Solving the system with one of the numerical methods of linear algebra, we obtain the values of the probabilities of various states that can be used to determine any performance characteristics of the analyzed system [8].

In order for the failures of software elements to be considered statistically independent, like failures of various pieces of equipment, these elements must be developed independently [9]. This approach to critical software development is called multiversion programming ( N -version programming) [10]. It is easy to understand that the performance of software developed using this approach increases with an increase in the number of different versions and an increase in the performance of their runtime environment [11].

Obviously by increasing the number of redundant hardware and software components, the system performance can be brought to any a given level [12]. However, such systems can be too expensive to develop and / or operate. Therefore performance models must be complemented by cost models. The cost of building hardware comes down to adding up the costs of the components. Models for estimating the costs of creating fault-tolerant software take into account the costs of developing multi-version software, labor costs of personnel employed at different stages of the software life cycle, etc. [13; 14].

The constructed models allow one to proceed to the formalization of the problem of choosing the optimal architecture options for multiprocessor hardware and software complexes of real-time control systems. In this case, two groups of criteria are obvious:

performance criteria that must be maximized (the probability of being in a state in which performance is sufficient to generate a control action, etc.);

cost criteria to be minimized (system cost, system development cost, operating cost, repair cost, etc.).

In this case, constraints will be imposed on the variable tasks, for example, in terms of energy consumption, speed, etc. To simplify the task, the cost criteria can be translated into constraints, since for all cost characteristics of the system, as a rule, there are upper bounds set by the customer of the system management. Having singled out the leader among the performance criteria, we get a one-criterion conditional optimization problem with a set of essential constraints, into which the rest of the criteria will go. In addition, there will be a set of natural constraints (for example, the number of hardware components is an integer and positive number).

We consider the type of variables in our optimization problem. In this case, we will assume given the maximum number of processor types N and software versions K , the maximum and minimum possible number of processors of each type and buses (for processors m i + and m i , respectively, i =1, ..., N , and for buses n + and n ). Let us denote by m i the number of processors of the i type included in the structure of the hardware-software complex ( i = 1,., N) , by n - the number of buses, and by k -the number of software versions. It is not difficult to see that the variables of our optimization problem ( k , m i , n ) are integer, that is, we have a discrete optimization problem.

Let us give a formal record of the posed problem of optimizing the structure of a hardware-software complex with multiversion software for real-time control systems:

Ro(m 1, .., mn, n, k) ^ max, under conditions                 Ri (m 1, .., mn, n, k) > Ri °, i = 1, .., Lr ,

Ci(m 1, ., mn, n, k) < Ci°, i =1, ., Lc, mi~ < mi < mi+, i = 1,., N, n- ≤ n ≤ n+,

• 1    ≤ k ≤ K .

In this problem, the following designations are adopted: R 0 is the leading criterion for evaluating performance; R i , i = 1, ., L r , are secondary performance evaluation criteria; C i , i = 1, ., L c , - cost estimation criteria; R l ⁰ , C l ⁰ - maximum permissible levels of criteria converted to restrictions.

When designing the optimal structure of the hardware-software complex one cannot focus on the maximum performance of special processors, but it is necessary to choose it so as to ensure the maximum performance of the entire hardware-software complex as a whole. For the formal statement of the problem, this means that the values of the average execution time of one instruction Т 0 i by processors of the i type cannot be constant, but must also be included in the number of optimization variables. Moreover, the parameters of the system ν i and µ i become functions of T 0 i ,, that is, ν i = ν i ( T 0 i ), µ i = µ i ( T 0 i ). This leads to a significant complication of the optimization problem, turning it into a two-level first hierarchical task:

(R0*(T01, …, T0i, T0N), Rl*( T01, …, T0i, T0N), Cl*( T01, …, T0i, T0N)) → extr, где R0*, Rl* и Cl* is optimization problem solution.

First of all, it should be noted that the space of possible solutions is discrete, since the configuration of the hardware-software complex is determined by the number of processors of various types and RAM buses, which can only be integers. At the same time, the power of the search space grows rapidly with the increase in the number of processor types.

If we roughly estimate the power of the optimization space, then we get the total number of possible configurations more than 1,6 ⋅ 10 ²⁰ . At the same time, significant restrictions will not significantly reduce the number of search points.

A significant problem for solving the resulting optimization problem is created by the method of calculating objective functions (criteria), which are mostly given algorithmically.

There are all the signs of a complex optimization problem: algorithmically specified functions, different types of problem variables, a variable number of sought variables, a large search area for an optimal solution.

When solving such optimization problems, evolutionary optimization algorithms have proven themselves well [15–18]. Therefore, the study of the effectiveness of evolutionary algorithms when optimizing the structure of hardware and software complexes of real-time control systems can be indicated as a possible direction for further research.

Conclusion

The existing performance models make it possible to determine the minimum hardware configuration of a multiprocessor computing complex. The approach proposed in this article makes it possible to find configurations that have hardware redundancy (compared to the minimum configuration), but, due to this, have a high probability of being in states that provide performance sufficient to achieve the goals of functioning of the designed real-time control system. The described approach is more flexible than simple duplication of all hardware components of the minimum configuration, which can be used to reduce the cost of creating and operating the designed control system.

The proposed model can be used to optimize the performance of multiprocessor hardware and software complexes of real-time control systems. It should be borne in mind that the resources allocated for the creation and operation of the hardware and software complex are always limited. Therefore, it is advisable to consider the problem of performance optimization as a multi-criteria one: one criterion will be performance, and the other will be the cost of creating a hardware-software complex.

Thus, this article presents the formulation of the problem of optimizing the structure of hardware and software complexes with multiversion software designed for real-time control systems. In the future, it is proposed to investigate the effectiveness of using evolutionary optimization methods to solve this problem.