The extensive use of embedded systems to process approximate data from sensors in critical, cyber-physical, IoT and other applications orients online testing methods to check the validity of approximate results in arithmetic operations. Traditional methods of on-line testing are designed for exact data, i.e. integer by nature. The development of the data model from exact to approximate form changes the purpose of on-line testing for arithmetic components from fault detection to estimation of trustworthiness of the calculated results. The approximate result contains the most and least significant bits, in which the faults of the digital circuit produces essential and inessential errors with respect to the trustworthiness of the result. As a rule, the approximate calculations are characterized by a low probability of an essential error. Traditional on-line testing methods had high error detection probability and low trustworthiness, which approached the probability of an essential error. We propose a method of on-line testing with simplified operation in checking to increase trustworthiness in conditions of low probability of essential error. The method monitors the result of an operation on a limited set of inputs while maintaining the ability to detect typical array circuit faults in the same way as residue checking. The method uses conditions that restrict the input data and logical operations with them. An error detection circuit has been developed and an example of on-line testing of the iterative array multiplier has been considered. The advantages of the suggested method in trustworthiness compared to residue checking are shown.
On-line testing plays an important role in maintaining the functionality of the embedded
system by evaluating the results calculated at the outputs of the digital circuits in its
components [
The main stage of on-line testing development took place within the model of exact
data, i.e. integer by nature. This model is reflected in the theory and practice of totally
self-checking circuits [
The orientation of modern embedded systems and information technologies
implemented in them towards the dominance of approximate calculations is not an accident,
but, on the contrary, is of a natural property, which is explained from the perspective
of the resource approach [
Increased efficiency of on-line testing is also stimulated by its development along the natural path with increased level of parallelism and fuzziness following the objects of diagnostics. The purpose of this paper is to show the need to improve the data model, transforming it from an exact form to an approximate one for the on-line testing of embedded systems. We suggest to consider the impact that the development of the data model has on on-line testing in its purpose and the trustworthiness of methods. Section 2 deals with the trustworthiness of on-line testing methods in the context of improved data models. The high trustworthiness of traditional methods is found to be low within the approximate data model. Section 3 proposes a method of on-line testing with simplification of operation in checking to increase trustworthiness of monitoring the results calculated by embedded systems. The proposed method is shown on the example of online testing for iterative array multiplier.
Approximate data processing shows the insolvency of the on-line testing purpose
declared in the theory of totally self-checking circuits. On-line testing is aimed not at
detection of faults in digital circuits, but at estimation of trustworthiness of calculated
results. These two goals are indistinguishable within a model of exact data. In this case,
the detected error indicates both the fault and the non-reliable result distorted by it [
Unlike exact data, the approximate result can be both erroneous and reliable because
it consists of most and least significant bits [
In practice, on-line testing distinguishes between objectives developed within exact
and approximate data models. We can see this by detecting a transient fault as a
shortterm self-eliminating fault. Transient fault causes much more often than permanent one
[
The exact result contains only most significant bits, in which all errors are essential. The fault detection purpose ignores the difference between essential and inessential errors because least significant bits and inessential errors are not present within the exact data model.
The method of on-line testing is as reliable as it correctly assesses the trustworthiness
of the result. Therefore, the trustworthiness of the on-line testing method is determined
by the following formula [
T = PE PD + (1 – PE) (1 – PD), (1) where PE – probability of an essential error;
PD – probability of error detection.
Formula (1) shows a particular case of exact data where all errors are essential and PE = 1. This is why the trustworthiness of the on-line testing methods is the same for exact data with the probability of error and fault detection, i.e. T = PD.
Traditional solutions using totally self-checking circuits provide fault detection from a given set with PD = 1 probability. In this case, the trustworthiness of traditional online testing methods, for example residue checking, is determined by the formula (1) as TТ = PE.
The value of PE probability can be estimated based on the following judgements.
Multiplication is a key operation of approximate calculations because it is used in the
representation of numbers in floating-point formats: (−1) SIGN × B EXPONENT ×
SIGNIFICAND, where B is the base of the number system [
Thus, the TТ trustworthiness of traditional methods is as low as the PE probability. Their high PD probability is mainly used to detect the most frequently occurring inessential errors, i.e. to reject erroneous but reliable results. 2.2
Analysis of formula (1) shows that the trustworthiness T = 0.5 if at least one of the PE or PD parameters takes such a value, i.e. PE = 0.5 or PD = 0.5.
Trustworthiness T > 0.5 is achieved if both parameters PE and PD are on one side of value 0.5, i.e. in two cases, which determine two ways to increase trustworthiness of on-line testing methods: 1) PE > 0.5 and PD > 0.5; 2) PE < 0.5 and PD < 0.5.
Note that formula (1) is symmetric, i.e. it does not change when the PE and PD parameters are changed. However, these parameters play a different role in it: the PE probability of an essential error characterizes the object of diagnosis, and the PD probability of error detection – the method of on-line testing. Thus, the task for the on-line testing is determined on the basis of the required trustworthiness T and the characteristic PE of the diagnostic object. By these parameters, the PD probability of error detection is determined according to formula (1) as follows:
PD = (T + PE – 1) / (2PE – 1), (2)
The value of PD probability obtained in formula (2) is used to select the on-line testing method.
The first way to increase the trustworthiness of on-line testing methods is only
possible in the case of PE > 0.5, which is excluded when performing complete arithmetic
operations. The truncated operations calculate the result, which is twice or almost twice
as short as the complete [
For example, the truncated multiplication of n-bit operands defines the (n + log2 n)bit product. In this case, the probability of an essential error can be estimated as PE = n / (n + log2 n). The probability is PE = 0.86 and PE = 0.91 for n = 32 and n = 64, respectively.
The first way is implemented in the residue checking of truncated operations [
The advantage of these methods is increased trustworthiness with a high probability of error detection.
However, even truncated operations do not guarantee a high probability PE of an essential error due to its halving after each multiplication and during normalization / renormalization operations. For example, if the operation follows X multiplication operations and Y addition operations, each of which shifts the operand to the right by n / 4 positions with loss of n / 4 least significant bits, the PE probability may be reduced to a value 0.5 X (0.75) Y PE, i.e. up to 0.38 PE and 0.14 PE in the case of X = Y = 1 and X = Y = 2, respectively.
Thus, the case of PE << 0.5 is most typical for on-line testing of floating-point arithmetic operations just as the second path becomes the main one in improving trustworthiness. 3
3.1
We offer a method of on-line testing, which increases its trustworthiness along the
second path for diagnostic objects with probability PE < 0.5. In this case, the probability
of error detection should also be low, i.e. PD < 0.5. Reduction of PD probability is
achieved by execution of checking for operation simplified by its consideration on
limited set of input data [
The method lowers the PD probability to a δ PD value, where the reduction coefficient can be estimated as δ = H / G, where H and G are the size of the limited and of the total set of input data, respectively.
The main requirement for the proposed method is to detect errors caused by typical
faults of monitored arithmetic units. A set of such faults can be determined based on
the capability of the residue checking modulo-three method, i.e. the proposed method
should detect errors produced by all faults F that are detected by the modulo-three
checking. This method is chosen as a reference in detecting of a set of faults based on
our experiments. We have developed a program model of the Brown multiplier [
The basis of the proposed method is conditions limiting the number of test words, i.e. input words, on which the result of the operation is monitored. To store the F set of faults, conditions are generated based on the modulo-three casting out operation.
The modulo-three residue takes 4 values: 1 = 012, 2 = 102, +0 = 002 and –0 = 112. In the theory of totally self-checking circuits, codes 012 and 102 are called allowed and codes 002 and 112 are called forbidden.
Definition. Conditions that restrict the result of an operation equally or differently are called dependent and independent, respectively.
For example, for the A × B = V multiplication operation, conditions A mod 3 = 0 and B mod 3 = 0 are dependent because they equally limit the complete product: V mod 3 = 0. The product can be presented by the older VH and the younger VL half. The older VH part is a rounded result. The younger VL part is discarded. Thus, the condition VL mod 3 = 0 is independent with respect to the first two conditions.
Multiple conditions require you to define the logical operations to perform with them. For example, the dependent conditions considered may be executed simultaneously: or at least one of them: or only one of them: (A mod 3 = 0) AND (B mod 3 = 0) (A mod 3 = 0) OR (B mod 3 = 0) (A mod 3 = 0) XOR (B mod 3 = 0).
It should be noted that each of the dependent conditions considered limits the set of test words as H = G / 3, which determines the coefficient δ = 1 / 3.
The logical operations AND, OR, and XOR define a coefficient δ to the operations with the sets:
δ AND = 1 / 3 × 1 / 3 = 1 / 9 ≈ 11.1%; δ OR = 1 / 3 + 1 / 3 – δ AND = 5 / 9 ≈ 55.6%; δ XOR = 1 / 3 + 1 / 3 – 2δ AND = 4 / 9 ≈ 44.4%.
The logical operations used must retain the F set of faults. Analysis of two-operands logical operations has highlighted two such operations for dependent conditions: OR, XOR, and one operation for independent conditions: AND.
A complete condition that combines logical operations with all dependent and independent conditions used determines a set of all test words. The result constraints define a condition for monitoring it on this set. The reduction coefficient δ of PD probability is formed by selecting conditions and logical operations thereon.
The minimum value of the δ coefficient may be limited to the allowable fault detection time (number of cycles), which may be estimated as τ = ln 2 / PD. If the probability of error detection decreases compared to residue checking, the reduced probability is the same as the δ coefficient, i.e. the monitoring is performed with the probability PD = δ. 3.2
The suggested method monitors the result at the output of the arithmetic unit according to the error detection circuit shown in Fig. 1.
CR
The circuit contains a test word identification block BI, a result checking block BC, and a check code generating block BR. The BI block analyzes the operands and generates the CI code of inverse identification of a test word. This code takes the forbidden values 002 or 112 if the operands form a test word and allowed values 012 or 102 otherwise. The BC block verifies the result according to the condition for its monitoring and generates a result check code CC which receives the forbidden values 002 or 112 in case of condition violation and the allowed values 012 or 102 otherwise. The BR block receives the CI and CC codes and generates a CR check code that receives the forbidden values 002 or 112 if both the CI and CC codes receive the forbidden values 002 or 112 and the allowed values otherwise.
The BI block allows monitoring of the result by the forbidden values 002 or 112 so that the fault of the short circuit between the bits of the CI code does not cause blocking of the monitoring circuit.
Dependent and independent conditions for operands and condition for monitoring the results are realized using modulo-three casting out unit, which are totally selfchecking, i.e. show their own faults.
Logical operations with allowed and forbidden condition codes can be performed in functional-complete basis of operations: AND, NOT or OR, NOT.
The AND logic operation with the allowed codes is performed on a totally
selfchecking Carter element, which is a modulo-three multiplier [
The OR logic operation with the forbidden values 002 or 112 is also performed on a modulo-three multiplier. The modulo-three multiplication result takes a forbidden value of zero if at least one of the multipliers is zero, i.e. is a forbidden value.
The NOT logical operation converts allowed codes to forbidden ones and vice versa. The circuit implementing this operation contains one inverter inverting one of the bits of the converted code.
The application of the method can be illustrated by an example of an iterative array matrix multiplier monitoring that performs a complete operation with 8-bit operand codes A{1, …, 8}, B{1, …, 8} and calculates the V{1, …, 16} product. The old half V{1, …, 8} of the product is the result. The PD probability is set at 9% – 10%.
A method can use two dependent conditions and an OR operation with them: (A{1, …, 8} mod 3 = 0) OR (B{1, …, 8} mod 3 = 0).
In addition, the lower part of the product V{9, …, 16} can be used to create independent conditions, for example:
V{9, 10} mod 3 = 0; V{11, …, 16} mod 3 = 0.
V{1, …, 8} mod 3 = 0.
An AND operation is performed with all mutually independent conditions. The condition for result monitoring takes into account the constraints imposed by dependent and independent conditions by the following formula:
KA
KB A{1, …, 8} B{1, …, 8}
V{9, 10} V{11, …, 16}
M 1.3 V{1, …, 8}
M 2
BC
OR 1.4 AND 1.5 CC
AND 1.6
BI
CI
BF AND 3
CR
The diagram contains modulo-three casting out units М 1.1 - 1.3 and 2, OR unit 1.4, AND units 1.5, 1.6 and 3.
Units M 1.1 and 1.2 calculate dependent condition codes: KA = A{1, …, 8} mod 3 and KB = B{1, …, 8} mod 3. The OR 1.4 unit performs an OR operation with the KA and KB codes as forbidden values and calculates the KA OR B result in the form of allowed values at the inverse output. The M 1.3 unit calculates the KV11, …, 16 = V{11, …, 16} mod 3 code of the independent condition V{11, …, 16} mod 3 = 0. The AND 1.5 and 1.6 units carry out the operations AND with KV19, 10 = V{10, 10} mod 3 = V{9, 10}, KV11, …, 16 and KA OR B codes of independent conditions and calculate the CI code at the output of the BI block.
The M 2 unit calculates the CС = V{11, …, 16} mod 3 code of conditions for the result and transfers it to the output of block BC.
The AND 3 unit receives the CI and CC codes to the inverse inputs and performs AND operation with the allowed values. The result of the operation is generated at the inverse output of the unit and is transferred to the output of the BF block and the circuit as the CR code. Forbidden CR code values indicate an error detection on the test word. Allowed values are generated if the correct result is calculated on the check word, or if the input word is not a test word.
The PD probability is estimated taking into account the probability of performance of the dependent and independent conditions, as well as logical operations with them according to the following formula:
PD = δ = AND (OR (δKA, δ KB), δKV{9, 10}, δKV{11, …, 16}), (3) где δKX = X1 / X2, X1 and X2 – number of multiple values and all code values KX; δKA = δKB = 84 / 256; δKV{9, 10} = 2 / 4; δKV{11, …, 16} = 22 / 64; δOR = OR (δKA, δKB) = δKA + δKB - δKA × δKB; δ = AND (δOR, δKV{9, 10}, δKV{11, …, 16}) = δOR × δKV{9, 10} × δKV{11, …, 16}.
Formula (3) determines the PD = 9.4% probability. In this case, the trustworthiness of the proposed method is represented by the formula (1) as TS = 0.094 PE + 0.906 (1 – PE).
Fig. 3 shows diagrams of the trustworthiness of the proposed method and the traditional solution (on the example of modulo-three residue checking) versus the PE probability of an essential error.
90 80 70 60 50 40 30 20 10 0 0,05 0,1 0,15 0,2 0,25 0,3 0,35 0,4 0,45 0,5
PE TS
TT Fig. 3. Trustworthiness of suggested method and residue checking. Embedded systems are most commonly used to handle approximate sensor data in critical applications, cyber-physical structures, and IoT solutions. Under these conditions, the on-line testing should also be oriented to approximate calculations.
Traditional on-line testing methods developed within the exact data model lose effectiveness in the trustworthiness of approximate result monitoring.
The proposed method of on-line testing with simplification of check operation is developed for the most frequent case of low probability of essential error in approximate data processing.
The method performs monitoring the operation result on a limited set of input data without reducing the set of faults detected by the traditional residue checking method. The proposed method shows an advantage in trustworthiness over residue checking. This advantage increases with reduced probability of essential error. 41. Intel Quartus Prime Standard Edition User Guide: Getting Started. Available at: https://www.intel.com/content/dam/www/programmable/us/en/pdfs/literature/ug/ug-qpsgetting-started.pdf