Considers the functioning of a parallel computing system (PCS) as part of a robotic complex that is exposed to external extremely destructive influences (EDI), leading to its destruction. A model of parallel computations under the conditions of possible EDI is proposed. Examples of modeling the functioning of the PCS of a robotic complex with estimates of the maximum possible efficiency of its functioning for various implementations of parallel computation plans are given. Conclusions are made and proposals are formulated for planning parallel processing of information in terms of EDI on a robotic complex. On the basis of modeling the functioning of a robotic complex, the analysis of known algorithms for planning parallel computations with estimates of the quality indicator of the functioning of PVS for various implementations of plans for parallel computations is carried out. A new algorithm for planning parallel information processing in a computing system is proposed, taking into account the probable destruction of a robotic complex, and the results of its study presented.
1 One of the topical areas of application of robotic systems is their use in extreme conditions of destructive environmental influences, in which human work is impossible or extremely dangerous.
Trends in the development of robotic
systems for various purposes are associated with
the need to implement a significant amount of
computation and require a scientifically based
approach to modeling and planning
computational processes occurring in their computing
systems. As is known [
The problem of modeling and planning
parallel computing processes (PСP) under
normal functioning of a computing system
(CS) is successfully solved [
External destructive effects on the robotic complex can be of a different nature (high temperature, critical shock loads, radiation exposure). Without losing the generality of modeling the processes of functioning of robotic complexes in various conditions of destructive influences, the article discusses EDI, the implementation of which leads to a complete loss of the robotic complex's performance.
Based on the concept of preventive
functional-parametric configuration of the CS [
The issues of planning parallel information
processing have been given sufficient attention
[
Let us consider the functioning of the СS of a robotic complex, consisting of several computational modules (processors or separate computers) under the conditions of possible EDI.
The execution of a set of programs in real time is realized according to the plan of a parallel computational process. We will assume that PСP planning is aimed at ensuring the execution of programs (tasks) on a given set of computational modules (СM) by a given directive date. The implementation of PСP under the conditions of external destructive influences can be interrupted by the destruction of the CS, which leads to a reduction in the completion time of calculations and the execution of not all planned tasks, but only some of them.
The PСP plan (Fig. 1) can be represented as an array of tuples containing the task number, the number of the computing module that will execute the task, and the scheduled start (end) time of the task. The figure shows the interval [0, tD] of the normal functioning of the CS and the interval [0, tp] of functioning, limited by the extreme destructive effect (EDE) on the complex.
S (ξ) = n ∑ хi(ξ) ⋅ τi i=1 min (ξ, max{t i}) i where τ i – is the execution time of the i-th task; ti – time of completion of the i-th task; ξ – the time moment of the destruction of the CS.
Note that in the absence of EDI, this
indicator coincides with the acceleration factor of
parallel computations [
The task of organizing the functioning of the CS of the robotic complex under the conditions of EDI can be formulated as follows. For the given task parameters, the parameters of the CS of the robotic complex, the parameters of the possible EDI on the CS, find
the dependence of the value of the maximum possible efficiency of the functioning of the BCS on the plan of the computing process (modeling task);
a plan for a parallel computing process that ensures the maximum value of the CS performance factor (scheduling problem).
Mathematical formulation of the problem.
Given: 1) a set Z of tasks with parameters: {τi}, i = 1,.., n ; τi – is the time of solving the i-th task, n is the number of tasks;
2) the distribution function F(t) of the moments of time for the implementation of the EDI on the CS;
Find: the plan of the computational process, where, Ξ ={t1, t 2,.., t n} are the planned time points for the completion of tasks, such that Ξ* = arg max S Ξ( Z , F ) Ξ* ∈ Ξadmis , where S Ξ is the mathematical expectation of the CS performance factor, Ξadmis is the set of admissible plans. 3. A model of a parallel computational process during the operation of a computing system under conditions of extreme destructive influences
If, in accordance with the PСP plan, the i-th task, i = 1, 2,..., n, ends at the moment of time ti and the distribution function F(t) of the moment of completion of calculations caused by the EDI is known, then problems will be solved with probability F (ti) = 1 − F (ti) , the planned completion time of which is not is superior ti (Fig. 2). in this case, the value of the CS performance coefficient at the moment of time is determined by the expression 1 n S(ti) =∑ τi ⋅(1 − F (ti)) (2) ti i=1
The values ti, and hence the value of expression (2) for a given distribution function F(t) of the completion time of calculations, depend on the duration and order (sequence) of task execution.
To find the mathematical expectation of the CS performance coefficient for the entire time of its operation, we divide the calculation scheduling interval into q intervals 0, χ1), χ1, χ2),..., χ q−1, χ q) so that the right boundary of each interval corresponds to the time of completion of at least one task.
Then the mathematical expectation SΞ of the CS performance coefficient for the entire time of its operation will be
n q ∑ τi ⋅ хi(χi) S Ξ =∑ i=1 ⋅( F (χi+1) − F (χi)). (3) i=1 Note that F (χ q+1) = 1 since computations χi end at a moment in time χ q .
Indicator (3) is the average value of the coefficient of performance of the CS and can be used as a generalized indicator of the quality of functioning of the CS of the robotic complex in the conditions of EDI.
Note that in the absence of destructive
effects on the CS F (ξ) = 0, the indicator (3)
coincides with the "traditional" coefficient of
acceleration of parallel information processing
[
The analysis shows that the type of EDI
distribution and the procedure for assigning
tasks to computational modules affect the
performance indicators of the CS functioning.
The difference in the value of the CS
productivity factor can reach 20%.
4. Algorithm for scheduling
parallel computations in a
computing system operating under
extreme destructive influences
Let us show the influence of the parallel
computation plan on the value of the indicator
of the quality of the CS functioning (3) by the
example of the distribution of 10 tasks with the
execution time correspondingly 1, 2, ..., 9, 10
units of time by three different scheduling
algorithms: the list scheduling algorithms [
PCP scheduling algorithms minimize the number of computational modules to complete computations by a given (directive) deadline or minimize the computation completion time for a given structure of the computing system. Under the conditions of the functioning of the OCS described above, its degradation is possible before the planned completion date of calculations, therefore, it is required to construct a plan that maximizes the value (3). This formulation of the problem of scheduling parallel computations, which consists in performing the maximum possible amount of computational work with an indefinite deadline for the completion of computations, is new.
PCP scheduling algorithms that provide an
optimal result belong to the class of
NPcomplete, therefore, in practice, real-time
systems use heuristic algorithms for assigning
tasks to CMs [
The analysis of the results of the application of the known algorithms for planning PCP under the conditions of CS degradation showed that the value of the performance coefficient (3) strongly depends on the time of CS degradation.
Four algorithms were analyzed two list algorithms: LTM - a task with a shorter duration is assigned earlier than others and GTM - a task with a longer duration is assigned earlier than others;
Multi-Fit algorithm - FFD-procedure (FirstFit-Decreacing) for packing objects into containers with iterative selection of the container volume;
Multi-Fit algorithm with tasks reordering in increasing duration (MF +).
The analysis consisted in calculating the indicator (3) for the VFD plan constructed by the selected algorithm for a given distribution function of the time of degradation of the CS. A random variable was simulated - the time of degradation of the air force, distributed according to uniform, exponential and normal distribution laws.
Regardless of the law of the distribution of the time ξ of degradation of the CS, it was found that with a mathematical expectation ξ close to the beginning of the PCP plan, a greater value of the residual productivity is provided by the LTM algorithm, and if it is close to the end of the PCP plan - by the Multi-Fit algorithms.
The idea of the proposed algorithm is based on a combination of two scheduling procedures for a parallel computational process: the LTM list scheduling and the Multi-Fit reordering algorithm.
Assigning tasks to computational modules goes through two phases. In the first phase, some of the tasks with the shortest duration are distributed among computational modules (CM) in accordance with the list algorithm for assigning tasks with the LTM function. In the second phase, the remaining tasks are distributed across the CM using the Multi-Fit algorithm, after which, on each CM, the tasks are finally reordered according to their nondecreasing duration.
An important parameter of the proposed
distribution of tasks is the ratio between the
number of tasks (amount of computations)
distributed by the LTM algorithm and by the
Multi-Fit algorithm. This ratio can be
formalized by the value
n
∆ =ΣLTM / ∑i=1τi ,
where Σ LTM is the total duration of tasks
distributed over the CM by the LTM
algorithm. Let's call this parameter the “phase
level” of the task distribution. The phase level ∆
changes in the interval [
Let us give a formal description of a twophase planning algorithm for a degrading PCP (let's call it LTM + MF).
Step 1. Ordering tasks in non-increasing duration: τ 1 ≥τ 2 ≥ ... ≥τ n .
Step 2. Using the given value ∆ , determine the maximum number k of the last tasks in this sequence with numbers n − k + 1, n − k + 2,..., n −1, n for which condition ∑ τn−i+1 / ∑ τi ≤ Δ i =1 i =1 is satisfied.
Step 3. Sequentially assign tasks numbered n, n-1,…, n-k-1 to those CMs on which the next task will start its execution earlier than on other CMs.
Step 4. For the remaining n-k problems, apply the Multi-Fit assignment algorithm.
Step 5. In the resulting PCP plan, on each CM, reorder the tasks according to their nondecreasing duration.
For any initial data (the number and duration of tasks, the number of CMs, the mathematical expectation of the point in time ξ of PCP degradation), it is possible to determine the value of the phase level that provides the maximum average value of the CS performance factor. 4.2. Results of statistical tests of algorithms for planning parallel computing processes in a computing system operating under extreme destructive influences
To analyze the effectiveness of the application of the developed two-phase algorithm for planning parallel computational processes, an imitation model of the functioning of an CS of a robotic complex under conditions of destructive influences was created.
The modeling consisted of multiple
generation of PCP plans by various planning
algorithms (LTM, GTM, MF, MF + and the
developed two-phase algorithm LTM + MF),
generation of a random variable - the time of CS
degradation, calculation and comparison of the
average residual capacity of the CS, which
implements different PCP plans ... When
modeling the time of degradation of the CS, three
distribution laws of a random variable were
used - uniform, exponential, and normal [
Comparison of the planning efficiency by different algorithms was carried out through the ratio of the average residual performance of the CS operating according to the PCP plan, formed by the developed two-phase algorithm LTM + MF, to the average residual productivity of the CS, operating according to the PCP plans, formed, respectively, by the LTM, GTM, MF, MF + algorithms: εLTM = S LTM + MF ; εGTM = S LTM + MF ;
S LTM SGTM εMF = S LTM + MF ; εMF + = S LTM + MF .
S MF S MF +
Figure 5 shows the dependences, where is the algorithm with which the two-phase LTM + MF algorithm is compared, on the value of p, which is equal to the ratio of the mathematical expectation of the time of the CS destruction to the planning interval of the PCP. The value represents the relative gain (in percent) in CS performance that can be obtained using the LTM + MF algorithm. This gain depends on the type and parameters of the distribution of the time of CS degradation.
In the numerical experiment carried out, the smallest average gain was noted in comparison with the LTM algorithm: up to 9% with a normal distribution of the time of CS degradation, up to 12% – with an exponential one, and up to 13% – with a uniform one.
The proposed approach to modeling and planning the functioning of the computing system of a robotic complex provides a solution to computational problems in conditions of possible destruction of the robotic complex caused by EDI.
The novelty of the considered model lies in the ability to assess the value of the indicator of the quality of the functioning of the CS of the robotic complex - the productivity coefficient with stochastic EDI on it.
The proposed algorithm of polynomial complexity provides operational planning of parallel information processing in the CS of the robotic complex. The scientific novelty of the presented algorithm lies in the fact that, in contrast to the known ones, it allows you to rationally distribute the work (tasks) among the performers with a random or indefinite directive deadline for the total completion of all work.
An analysis of the results of simulation modeling of the functioning of a robotic complex under conditions of its possible destruction indicates the possibility of a significant increase in the value of the performance coefficient of parallel information processing in an CS based on the application of the proposed two-phase planning algorithm for PCP.
For an in-depth study of the state of
research on the topics touched upon by us, it is
recommended to familiarize yourself with
works [