The work is devoted to assessing the completeness of the test for a given limit on the maximum number of faulty processors in the case of applying a formal method for determining the state of the processors of a multiprocessor system. This method is based on the results of performing mutual test checks, which consists in forming a specialized boolean equation based on the results of the tests, as well as its subsequent transformation. The above limitation is determined by the structure of the test or, in other words, the system's capabilities in terms of mutual testing of processors, which can be reflected in the form of a directed graph. A number of assertions are proved and criterions are formulated that are used to determine the maximum number of processors, the failure of which still guarantees the determination of the state of all processors in the system in the case of applying the method. Presented examples demonstrate the practical application of these criterions for estimating the maximum allowable number of faults. An important feature of the method is the possibility of applying it to systems corresponding to graphs of arbitrary topology, and not only to complete graphs.
Modern control systems (CS) for various objects are increasingly built on the basis of microprocessors. For the so-called systems of critical application, the failure of which control objects may lead to significant losses (control systems for transport, electricity generation, production facilities, military equipment, etc.), often put forward increased requirements for both reliability and performance [1-8]. This problem can be effectively solved by building a CS based on fault-tolerant multiprocessor systems (FTMS) [9, 10]. In such systems, the failure of some processors does not lead to the failure of the system as a whole. This effect is achieved, in particular, through the use of various types of redundancy, which makes it possible to reconfigure the system [11-15], and as a result, tasks are redistributed between serviceable processors.
For efficient system reconfiguration, it is important to have information about the current state (healthy/failed) of each of its processors, which can be obtained as a result of system testing [16, 17].
There are two main approaches to testing fault-tolerant multiprocessor systems: by using a specialized subsystem that performs testing, or by mutual testing of processors with each other.
The first approach is characterized by the relative simplicity of implementing the testing procedure (in particular, the procedure for determining the state of each of the system processors based on the test results is trivial), however, its disadvantage is the need to introduce an additional node into the system, which is also prone to failures (moreover, its failure leads to the impossibility of performing the testing process). This approach can be used, in particular, to implement system testing at the production and service stages.
The second approach is based on the performance of mutual test checks by the processors of the system and analysis of the test results. It should be noted that the organization of this approach is much more complicated, in particular, the task of determining the state of each of the processors of the system, depending on the results of test checks, becomes much more complicated [18]. This approach can be very effective for application during the operation phase of the system, and it is this approach that is considered in this article.
Processor testing can be carried out by executing a certain set of test tasks and comparing their results with reference values: if they match, the processor is considered to be serviceable, and otherwise, it is faulty. It should be noted that in the approach under consideration, two processors are involved in testing: the one that is testing and the one that is being tested, each of which, in turn, can be serviceable or faulty. It is assumed that the testing of the system is carried out in accordance with the Preparata-Metze-Chien (PMC-model) [19], in which the result of the test experiment will be 0 (no errors found) if the processor under test is serviceable or 1 (errors are found) if the tested processor is faulty. The above is true only if the testing processor is in good condition. Otherwise, the result can be either 0 or 1, regardless of the state of the processor under test.
To reflect the possibilities of conducting mutual test checks of the processors of the system, a digraph can be constructed, the vertices of which will correspond to the processors, and the presence of an arc from vertex a to vertex b is the possibility of carrying out a test check of the processor corresponding to vertex b by the processor corresponding to vertex a. This graph will actually reflect the capabilities of the system in terms of diagnosing. An example of such a graph is shown in Figure 1. h g a f b e c d
Special consideration may be granted for the case when the above graph is complete, i.e. it is possible to test each of the processors with any other processor. Such a case is considered, in particular, in [19], where it is shown that the state of the system can be uniquely determined if less than half of all processors in the system fail. It was shown in [20] that this is almost always possible even with a larger number of faults, and in [21] an algorithm was proposed that makes it possible to uniquely determine this state by conducting no more than N + 2p test checks, where N is the number of system processors, and p is the number of truly faulty processors. However, in practice it is far from always possible to implement the possibility of testing processors on a one-to-one basis. 2. Formal method for determining the state of processors in a multiprocessor system
In [22], a formal method was proposed for determining the state of a multiprocessor system based on the results of the test checks, which allows an arbitrary topology of a graph that reflects the capabilities of the system in terms of diagnosing. Note that the topology of this graph affects the allowable number of processor failures, in which the state of the system can still be determined.
The concept of M-diagnosability is also used in the literature [23–25]. Thus, a system is M-diagnosable if it is possible to establish the state of all its processors in case of failure of at most M of them.
According to the method proposed in [22], each of the processors of the system is associated with some boolean variable xi, which takes the value of 1 if it is in good condition and 0 if it is out of order. Any state of such a system corresponds to some constituent of one − an elementary conjunction containing all xi, moreover, without inversions if they correspond to serviceable processors and with inversions − if they are faulty. Note that for the real state of the system and only for it, such a constituent is equal to one.
It is also assumed that the system is M-diagnosable, i.e. its state can be established only in case of a failure of at most M processors, and therefore such situations are considered.
According to [22], each of the results of test checks is associated with an expression constructed in a special way, containing the variables xi. For the test, which consists in testing the processor corresponding to the variable xj by the processor corresponding to the variable xi, as a result of which the value rij was obtained, the expression will be built , ≜ ∨ ̅ ≡ ∨ ̅ , ̅ ∨ ̅ ≡ ̅ ∨ ̅ , = 0 = 1 .
With such a construction, the equality will be valid: , Based on the results of K tests, an expression VK can be constructed. = 1.
(
To determine the state of the system, in accordance with [22], the expression VK is transformed into a perfect disjunctive normal form (PDNF), i.e. disjunction of the constituents of one. In this case, all conjunctions containing more than M inversions are excluded at any stage of the transformation, which, as was shown in [22], does not lead to the exclusion of the conjunction corresponding to the real state of the system, if no more than M processors actually failed in it.
Thus, after performing the above transformations, VK will be represented in the following form:
where each of Cl – some constituent of one (containing no more than M inversions), and L is their
number. Taking into account (
, ∈
= 1. =
,
=1
= 1.
=1
All possible equalities of the form (
In the first case, the real state of the system corresponds to a single constituent and, as shown above, can be easily determined: the processors corresponding to the variables included in the constituent without inversions are considered to be serviceable, and those that enter it with inversions are considered to be faulty.
In the second case, equality contains more than one constituent, among which there is one corresponding to the real state of the system. Additional tests can be done to determine it. It is also worth noting that if some variable is included in all constituents without inversions, then the processor corresponding to it is unambiguously good, and if some variable is included in them with inversions, then the processor corresponding to it is unambiguously faulty. The state of all other processors (that is, those that correspond to variables included in some of the constituents with inversions, and in others without inversions) is not determined. Based on this information, the choice of subsequent test checks can be made. For example, it makes sense to choose such tests in which the testing processor is known to be good, but the state of the tested one is not defined. And the checks in which the testing processor is known to be faulty can be excluded. We note that all of the above is true only when no more than M processors actually failed in the system.
The third case, where the equality does not contain any constituents, is possible only if more than M processors are faulty in the system, i.e. conjunctions containing more than M inversions were illegitimately excluded. However, it is worth noting that the converse is generally not true, since in this case, depending on the results of the test checks, in principle any of the three situations is possible.
As already mentioned, in order to apply the method considered above, it is necessary to set the maximum allowable number of faulty processors M. This value obviously depends on the organization of the system, namely, the possibilities of mutual testing of its processors, which, as shown above, can be reflected in the form of a directed graph. Thus, the problem of determining the value of M depending on the structure of such a graph becomes relevant.
Let the diagnostics of a system containing N processors occur in accordance with the PMC-model and correspond to graph G. Let, in case of failure of no more than M arbitrary processors, as a result of a certain set of tests, it is possible to unambiguously determine the state of each of the processors using the method described above.
Let us formulate and prove several assertions for such a system.
If for some group of n processors, it is possible to establish the state of each of them by conducting mutual test checks between the processors that are only in this group in all cases when no more than any m of them fail, then with capacities respectively m and l = n – m. Since ≥ , then = − ≤ , and hence, l ≤ m. ≥ 2. We arbitrarily divide the considered set of processors into two subsets: A and B, 2 2
All processors from set A are operational, and all processors from set B are faulty. However, faults in these processors are such that always lead to inversion of test results by these processors of other processors, i.e. if such a processor tests another faulty processor, the test result will be 0, and if it tests a working processor, then 1 (as before it is said, according to the PMC-model, in case of failure of the testing processor, the results of test checks can take arbitrary values). Thus, in this situation we will have l ≤ m faulty processors.
As a result of testing some processor y with another processor x we get the following results:
<
2
(
0, if ∈ and ∈ ; 1, if ∈ and ∈ ; 1, if ∈ and ∈ ; 0, if ∈ and ∈ .
The situation is the opposite: all processors with A are faulty (and, as in the previous case, the test results are inverted), and all processors with B are operational. In this case we will have m faulty processors.
As a result of testing a processor y with a processor x we get the following results:
0, if ∈ and ∈ ; 1, if ∈ and ∈ ; 0, if ∈ and
∈ .
As you can see, in both cases the results of all possible tests coincide. At the same time, obviously, the states of the processors in each of these cases are different. That is, there is ambiguity, as a result of which it is not possible to determine the reliable state of the system based on test results. 2
≥
, it is not always possible to unambiguously determine the state of the system.∎ Note that for the case of a set that includes all processors of the system, Assertion 1 will take the form: < , 2 which corresponds to the results obtained in [19].
According to the proposed method, the reliable state of the system in case of failure of no more than M of its arbitrary processors with a given set of tests corresponding to diagnostic graph G, can be established if and only if for any set F of vertices of graph G with power K, > − vertices of the graph G exist, which are not contained in F, such that from each of them there is an arc in at least 2 one of the vertices from the set F.
Consider some set F of vertices of the graph G with power K. It corresponds to the set of processors Let the set E contain all vertices of the graph G that are not contained in F, and from each of which there is an arc in at least one of the vertices of the set F. T is the power of the set E. This set corresponds processors from Fp. That is, the number of faulty processors in the system: + ≤ .
2
≥ 2, then, based on Assumption 1, testing processors from Fp only with processors from Fp (i.e. only on their own) will not allow in all cases to unambiguously establish the state of all of them.
Other test checks on processors from Fp can only be performed by processors from Ep (because only vertices on set F have arcs on vertices on set E), but all of these processors are faulty, i.e. test results can be any, regardless of the state of the tested processors and therefore they will not help to establish 2 2 . Let all processors from Ep (T pieces) in the system fail, as well as , it is not always possible to unambiguously establish the state of all processors (7)
2 (8) = ∧ , = ∧ , (9) (10) Fp.
to the set of processors Ep.
Prove the necessity:
Assume that ≤ − the state of processors from Fp. in the system.
So if ≤ −
2
Prove sufficiency. following equation is obtained: are excluded from the equation). will be a test that will exclude it.
Suppose that after performing a set of test checks, according to the method described above, the 1 ∨ 2 ∨ … ∨ = 1.
We assume that when applying the method, the value of M was used, which meets the criteria of the assertion that is being proved. Thus, the number of inversion variables (corresponding to faulty processors) in each of the Ci conjunctions in expression (7) cannot exceed M (since such conjunctions Let Cr correspond to the real state of the system's processors. We prove that for each Ci, i ≠ r, there The expressions Ci and Cr can be represented as follows: with inversions. In addition, the number of variables in is denoted as L. where Ai – conjunction of all variables that coincide in Ci and Cr (i.e. in both cases are inverted or in obvious that all variables in will be inverted relative to the corresponding variables in Bi. both cases are inverted), and Bi and – conjunctions of all variables that differ in them, and it is Let = ⋀ , where
contains only variables without inversions, and – only variables Let = ⋀ , where contains only variables without inversions, and – only variables with inversions. In addition, the number of variables in and is denoted by P and Q, respectively.
Let also = ∧ variables that are part of . Moreover, contains only variables without inversions. These are all and therefore their number is Q. At the same time, contains only variables with inversions, and these are all variables that are part of , so their number is P.
Let Fp – the set of all processors to which the variables from Bi and correspond. Its power: K = Q + P. This set corresponds to some set F of vertices of the graph G. Let E be the set of vertices of the graph not contained in F and such that from each of them there is an arc in at least one of the vertices of the set F. The power of this set is denoted by T. The vertices will correspond to the set from Ep. Obviously, the sets Ep and Fp do not intersect, and therefore the processors from the set Ep correspond to variables only from Ai.
Note that L, Q and P – the number of inversions in Ai, Bi and respectively, and hence the number of inversions in Cr: L + Q, and in Ci: L + P. Recall that the number of inversions in Cr, as in Ci can not exceed M, so that L + Q ≤ M and L + P ≤ M, and therefore, Q ≤ M – L and P ≤ M – L. Then: = + ≤ 2 ∙ ( − ), that is 2 ≤ 2 − , respectively ≤ − , and given that L and M are 2 integers, the following is true: ≤ − .
2 2 If > −
≥ , then there is at least one processor from Еp, that does not correspond to any of the variables from
, and therefore it corresponds to the variable from both Cr and Ci. Let this processor, which we will call j-th, correspond to the vertex ∈ of the graph G, from which there is an arc to some vertex ∈ , which corresponds to the processor, which we will call k-th. Thus, it is possible to test the k-th processor with the j-th processor, resulting in the expression: already =
∨ ̅ , where xk is inverted or non-inverted depending on the test result. Because, as mentioned, xi is non-inverted in both
Cr and
Ci, then ∧ ≡ ∧ , and
∧ ≡ ∧ . On the other hand, since the k-th processor corresponds to the vertex from the set F, then xk is included in Bi (with or without inversion) and, accordingly, in in the opposite state). Thus, according to the test results, one of the conjunctions will be excluded. (but Obviously, this will be Ci, because Cr corresponds to the real state of the system and as shown in [22] , i.e. one that is inverted in can not be excluded).
Note that in the same way we can prove the existence of a test that excludes Ci for any i ≠ r. Therefore, all Ci except Cr will be excluded and, thus, the real state of the system will be established.
In particular, for the case of a set F with power Κ = 1, i.e. for a separate vertex of the graph G the condition of Assertion 2 can be reformulated as follows: the number of arcs T, entering each of the vertices must be at least Μ, i.e., the following condition must be satisfied: ≥ .
< 2 the graph G.
principle, 0 > − met.
Satisfaction of the condition of Assertion 1 for the set containing all processors of the system, i.e.
it is sufficient to fulfill the condition of Assertion 2 for the set F containing all the vertices of Obviously, if the set F contains all the vertices of the graph G, its power is equal to the number of processors in the system, i.e. K = N. On the other hand, there are no other vertices in the graph in therefore,
T = 0.
Thus, 2 . Taking into account that the condition
of < 2, we have − 2
Assertion
< 2 − 2 2 takes the
form ≤ 0, i.e. the condition is formulated.
The condition of Assertion 2 will always be satisfied for sets of vertices with power K > 2M.
It is easy to see that for K > 2M, we have of Assertion 2 will be satisfied for any Τ ≥ 0.
2 > 2 2 = . Therefore, −
< 0 and the condition 2
Thus, the choice of the value M for application in the method [22] can be carried out by checking all possible sets of vertices of the graph G for compliance with the conditions of Assertion 2. In addition, according to the statements proved above, somewhat simpler criteria for choosing this value can be The value of Μ must be less than half the number of processors in the system.
In the graph G, the number of arcs entering each of the vertices must be at least Μ. For each set F of vertices of the graph G with power Κ (2 ≤ Κ ≤ 2M), there must be vertices not contained in F and from which arcs that enter some vertices from the set Let's look at a few examples demonstrating the application of the above criteria.
Let us consider a system consisting of 5 processors corresponding to the graph G shown in Figure 2. From each vertex of the graph, arcs emanate to two neighboring vertices. Let us show that the state of all processors of such a system can be established based on the results of mutual test checks of processors in the event of failure of no more than 2 arbitrary processors, i.e. M = 2.
It should be noted that the graph shown in Figure 2 is symmetrical, which makes it possible to significantly simplify the analysis by reducing the enumeration of all possible groups of vertices.
Let us check the fulfillment of the criterions formulated above. The value Μ = 2 is indeed less than half the number of processors in the system, which is consistent with criterion 1. For any of the vertices of the graph, there are two vertices from which arcs emanate to the given one, which corresponds to criterion 2 for Μ = 2.
Consider different mutual arrangements of pairs of vertices (Figure 3 a, b) up to rotation, i.e. K = 2. As you can see, in these situations there are 2 or 3 vertices from which arcs emanate in them, i.e. T = 2 or T = 3. In both cases, the condition of criterion 3 for K = 2 and M = 2 is satisfied.
a e d c b
Next, consider the various relative positions of triples of vertices (Figure 3 c, d), i.e. K = 3. As we see, in both situations there are 2 vertices from which the arcs in them emanate, i.e. T = 2 and the condition of criterion 3 for K = 3 and M = 2 is satisfied.
For groups of four vertices (K = 4), there is only one possible mutual arrangement of vertices (Figure 3 e), and only one vertex from which arcs emanate to some of them (T = 1). In this case, the condition of criterion 3 for K = 4 and Μ = 2 is fulfilled.
As we can see, the conditions of all criteria are met, therefore, for this system, the use of the value Μ = 2 in the method described in [22] is admissible. Note that this result corresponds to the result obtained in [19] for a system of 5 processors, however, it does not require the graph G to be complete.
Let the system consist of processors organized in the form of a matrix × , A ≥ 3, B ≥ 3. We denote the processors of this system as xi,j, where i – the row number (i = 1, 2, …, A), j – the column number (j = 1, 2, …, B). In this case, the processor xi,j can participate in testing its neighboring processors, i.e. processors x(i + 1) mod A + 1,j, x(i – 1) mod A + 1,j, xi,(j + 1) mod B + 1, xi,(j – 1) mod B + 1 (Figure 4). Let us prove that the state of all processors of such a system can be determined from the results of mutual test checks of processors in the event of failure of no more than 4 arbitrary processors. … … …
Let us show that for any set of vertices of the graph G, the criteria formulated above for Μ = 4 will be satisfied.
1,1 1,2 1,3 1, 2,1 2,2 2,3 2, 3,1 3,2 3,3 3, … … … … ,1 ,2 ,3 , …
Recall that, according to the condition A ≥ 3 and B ≥ 3. Therefore, the number of processors = ∙ ≥ 9. Thus, the value Μ = 4 is indeed less than half the number of processors in the system, i.e., the condition of criterion 1 is met.
It is also easy to see that for any vertex of the graph, there are exactly 4 incoming arcs, which corresponds to criterion 2 for Μ = 4.
Next, we consider various options for the mutual arrangement of pairs of vertices of the graph G, as well as the vertices from which the arcs that enter them proceed (Figure 5 a-d). As we see, the least number of such vertices is Τ = 6, which satisfies the condition of criterion 3 for K = 2 and Μ = 4.
A similar operation can be performed for various triples of vertices (Κ = 3). As a result, for this situation, the minimum value Τ = 7 will be found (Figure 5 e), which, as it is easy to see, also corresponds to the condition of criterion 3 for K = 3 and Μ = 4. Further, the same can be done for all possible groups of vertices with power 4, 5, ... 8, which is omitted in order to reduce the volume of the article.
Consider a system consisting of 5 processors corresponding to the graph G shown in Figure 6. In this case, unlike the previous examples, the graph is not symmetrical. Let us show that, as in Example 1, the state of all processors of such a system can be established based on the results of mutual test checks of processors in the event of failure of no more than 2 arbitrary processors, i.e. Μ = 2. To do this, we check the fulfillment of the criteria formulated above.
The condition of criterion 1 is satisfied, because the value Μ = 2 is indeed less than half the number of processors in the system. Let us check the fulfillment of the conditions of criterion 2. Table 1 shows the number of arcs entering each of the vertices of the graph G, as well as the set Ε of vertices from which these arcs originate. As we can see, for each of the vertices there are exactly two incoming vertices, which corresponds to the condition of criterion 2 for M = 2.
To check the fulfillment of the conditions of criterion 3, the condition of Assertion 2 must be checked for each possible set of vertices of the graph G, which contains from 2 to 4 vertices. Due to the lack of symmetry in the graph G, in contrast to the previous examples, one has to perform a direct enumeration of all such sets.
Let us construct Table 2, in which for each set F of vertices of the graph G with power = | |, where 2 ≤ K ≤ 4, there is a set E of vertices that are not included in F and from which arcs emanate to any of the vertices of the set F, as well as the power of this set = | |. As we see, for Κ = 2 two cases are possible Τ = 2 or T = 3, for K = 3 in all cases T = 2, and for K = 4 always T = 1. It is easy to see that all these situations satisfy the condition criterion 3 for M = 2, i.e. > − 2 .
a e
b d c
Thus, the system under consideration satisfies all three criterions for M = 2; therefore, the state of all processors of such a system can indeed be established from the results of mutual test checks of processors in the event that no more than 2 of its arbitrary processors fail.
When developing a self-testing multiprocessor system, a separate task is the development of a test, i.e. set of mutual checks of processors in order to determine their state. This task can be quite difficult. At the same time, one of the important requirements for such a test is its completeness, i.e. guarantee of determining the state of the processors. In this case, the presence of certain restrictions is usually assumed, among which, in particular, sets of acceptable processor faults can be distinguished. In practice, instead of such sets, it is more convenient to use a simpler restriction, namely, the maximum allowable number of processors, upon failure of which the completeness of the test is preserved.
For an already developed test, it is important to be able to check its completeness for given constraints. This test actually reflects the capabilities of the system in terms of self-diagnosis, which can be described using a directed graph. In the article, a number of statements were proved, on the basis of which the criteria were formulated, which allow determining the maximum number of faults that allow the effective use of the method described in [22]. An important feature of the method under consideration is the possibility of applying it to systems corresponding to graphs of arbitrary topology, and not only to complete graphs.
In the general case, the verification of criterions conditions is associated with the enumeration and evaluation of all possible subsets of graph vertices, each of which corresponds to one of the system processors. However, in the case of symmetric and homogeneous structures, enumeration can be significantly reduced, as shown in the examples given in the article.