Ambiguities and their emergence conditions in self-testing of multiprocessor systems

Abstract

The article addresses the issue of organizing self-testing in multiprocessor systems. It examines cases where the state of certain processors (functional or faulty) remains ambiguous after executing a specific set of mutual processor tests. Determining the state of such processors requires additional capabilities, such as extra connections between processors. Ambiguity most often arises when the number of processors testing a given processor is less than the allowable number of faults. The study focuses on multiprocessor systems whose diagnostic graphs can be represented as circulant graphs, particularly graphs with two incoming and two outgoing edges. This relates to solving the problem of minimizing the number of mutual tests among system processors (each processor is tested by only two others). However, this approach can lead to ambiguity in determining the state of individual processors, especially when the allowable (and actual) number of faults in the system exceeds two. Theorems are formulated and proven to define the specific characteristics of the system for organizing mutual testing, under which the described phenomenon becomes feasible, however, in one way or another, the indices of processors with undefined states become known. The advantages of connection architectures described by circulant graphs are highlighted, particularly the fact that the number of processors in such architectures can be arbitrary – an attribute not always present in other cases (e.g., architectures with connection switches of the rectangular or hypercube type). Fault-tolerant multiprocessor systems with an allowable number of faults T = 2, 3, and 4 are examined in detail. It is shown that in the case of T = 2, no ambiguities arise; however, for T = 4, up to three ambiguities may occur (for T = 3 – up to two) depending on certain jumps in the circulant graph and specific combinations of functional and non-functional processors in the system. Examples of circulant graphs are provided where such ambiguities do not arise.