1.   Introduction

Nowadays, artificial intelligence, big data processing, and cloud computing are widely used. These applications require enormous amount of data and complex computations, resulting in an unprecedented challenge in computing hardware. To facilitate the development of these new technologies, energy-efficient computing systems with high performance are urgently needed. However, as the feature size of transistors is approaching its physical limit, Moore’s Law^[1] and Dennard’s Scaling Law^[2] have become difficult to maintain. In such circumstances, in order to step out the dilemma, the approximate circuit (AC) emerges and many related techniques have been developed. The AC relaxes the strict accuracy requirements in the calculation without affecting the results of certain human perception or recognition-related computations, such as multimedia processing, data mining, and deep neural network^[3-8].

Generally, the approximate circuits obtain obvious hardware overhead savings compared with their corresponding exact circuits with a negligible impact on the output accuracy. Table 1 lists the area, delay and power improvements and accuracy losses of some ACs. The series of AXA^[9] and CBAA^[10] are 1-bit and 128-bit approximate adders, respectively. The series of R4ABE^[11] and ABE^[12] are approximate Booth encoders of radix-4 Booth multipliers. Table 1 shows that the approximate designs bring significant improvements in area and energy efficiency with low accuracy losses. Furthermore, some work^{[13, 14]} also verifies the effects of ACs on some typical applications.

Table  1.  Hardware Savings and Accuracy Losses of Some ACs

AC	Average Improvement (%)				Accuracy Loss
	Area	Delay	Power		Error Rate (%)	Error Distance
AXA1[9]	20.00	100.00	15.22		/	4
AXA2[9]	40.00	43.96	25.07		/	4
AXA3[9]	20.00	–71.80	30.57		/	2
CBAA-Type I[10]	61.63	23.56	98.13		0.50	/
CBAA-Type II[10]	61.63	9.24	95.45		0.50	/
CBAA-Type III[10]	39.94	–54.79	44.27		0.10	/
CBAA-Type IV[10]	41.03	–7.33	73.81		0.20	/
R4ABE1[11]	59.45	12.50	53.27		12.50	/
R4ABE2[11]	83.74	37.50	88.44		25.00	/
ABE[12]	64.84	12.50	62.81		18.75	/

下载: 导出CSV 

| 显示表格

With the AC getting close to practical applications, the reliability issues of the approximate designs become increasingly important. In this paper, three reliability issues are reviewed and analyzed, i.e., error characteristics, reliability and test, and reliable design involving AC.

Compared with the conventional exact circuit, the first concern of the approximate design is the inaccuracy degree. To measure the quality of different approximate designs in the design space, multiple error metrics have been proposed. To evaluate the error characteristics of approximate arithmetic circuits, a lot of researches calculate one or multiple error metrics. The error characteristics are used to measure the approximation degree, judge several approximated candidates in design exploration and filter out the proper one which meets the customized requirement.

Once an approximate design steps into the physical realization, it will be imperative to analyze AC reliability and test problems. Enough attention should be paid to the problems in the physical implementation and future utilization of ACs. The main problem of nanoscale technology based ICs is their increasingly serious vulnerability to defects introduced during circuit manufacturing, and soft errors and aging effects introduced in the circuit’s lifetime. These issues need to be covered by the AC test and reliability analysis. The challenges of the AC test and reliability analysis lie in the consideration of acceptable errors. For an AC, affected by the faults, although the functional output is different from the output in the truth table of the AC, and it is also different from the output of the corresponding precise circuit, it might be acceptable by an error-resilient application. Thus, in the AC test and reliability evaluation, the acceptable functional output should be regarded as “correct”. Therefore, the functional output of an AC allows errors in a certain degree, as long as the calculation results of the application are acceptable. Indeed, CMOS technologies at nanoscale significantly affect the circuit yield and reliability^[15]. To take advantage of the opportunity offered by the AC, conventional test and reliability analysis need to be modified.

Additionally, although ACs conduct imprecise computation, they bring new opportunities and frameworks for the reliable design. Approximate designs can be used in some conventional fault-tolerant schemes to reduce the cost. The well-known error detection and correction schemes, such as dual and triple modular redundancy^[16], can defend both permanent and temporary faults; however, they use the full replication and introduce 100% and 200% area overhead, respectively. Some literatures^[16-18] apply an approximated design of the original module to replace the completely duplicated redundant module. Hence, the area and power consumption can be reduced. These approximate modular redundancies can be used to thwart Hardware Trojan insertion and provide obfuscation^[19]. Up to now, few researches have been conducted on the reliable design of ACs, a prospective issue of which is how to enhance the AC reliability taking into consideration manufacturing defects and failures and acceptable functional outputs.

The rest of this paper is organized as follows. Section 2 reviews the error characteristics analysis of ACs. Section 3 provides an overview of the AC reliability and test process. In Section 4, we survey the fault-tolerant techniques involving ACs. Finally, in Section 5, we conclude the paper and outline the research directions in the future.

2.   Error Characteristics Analysis of ACs

ACs save power and area by lowering the circuit size such as reducing the number of transistors. Besides basic circuit metrics, such as power, area and delay, accuracy is also an important design constraint in approximate computing. The error characteristic analysis is performed to evaluate the effectiveness of different approximate schemes, exploring the enormous approximate design space, and helping designers to choose the suitable design. In general, the output differences between an AC and its precise counterpart are computed to measure the approximation degree. To measure the accuracy of an AC, many error metrics have been proposed. We will explain and discuss some popular ones.

Error rate (ER) and error distance (ED)^[20] are two most basic error metrics. ER describes the percentage of cases where the output of the AC is different from that of the precise circuit. In some literatures^[21-23], ER is also called error probability (EP). ED indicates the arithmetic difference between the exact and approximate outputs. If the exact and approximate outputs are given as O and O', respectively, the ED can be expressed as ED = $|$O'–O$\ |$. Additionally, the relative error distance (RED)^[24] describes the relative difference with respect to the exact output and can be calculated as RED = ED/O. Furtherly, another metric called PRED represents the probability that RED is less than 2%. PRED has been utilized as an important error metric for evaluating the approximate Booth multipliers in [13] and [25]. ED and RED show two important features of an approximate design. Among two input combinations which cause the same ED, the one that leads to a larger output in the precise circuit will yield a smaller RED. The metrics of ED and RED evaluate the errors of individual input combinations. Considering all the input vectors, the average values of EDs and REDs denoted as mean error distance (MED) and mean relative error distance (MRED)^[26], respectively, are used to evaluate a whole approximate design. MED and MRED are derived from the following formulas

and

where n is the total number of input combinations for the circuit. $E{D}_{i}$ and $RE{D}_{i}$ are the ED and RED for the i-th input combination, respectively. $P\left(E{D}_{i}\right)$ and $P\left(RE{D}_{i}\right)$ mean the probabilities of the i-th input combination corresponding to $E{D}_{i}$ and $RE{D}_{i}$, respectively. For image processing applications, peak signal to noise ratio (PSNR) is a frequently-used measure to evaluate image quality. It has been found that PSNR has higher correlation with MED than with ER^[25]. The normalized MED is denoted as NMED, which is given by

where O_i is the AC output under the i-th input combination. NMED is helpful when comparing the error magnitudes of approximate designs of different sizes.

Similar to variance and root variance, mean square error (MSE) and root mean square error (RMSE) are computed by

and

respectively. They are also widely used to measure the extent of arithmetic errors.

Additionally, Mrazek et al.^[27] provided an open source library EvoApprox8b that consists of 8-bit approximate adders and multipliers. Meanwhile, they also provided some error metrics to evaluate these approximate designs. Several error metrics^[27] have the same meaning as the ones mentioned in (1)-(5). Different ones include the hamming distance (HD), worst case error (WCE), and worst case relative error (WCRE), which are also widely used in the accuracy evaluation of approximate designs. Particularly, WCE is the most popular one. These three error metrics are described as follows

and

where OneCount() is used to caculate the number of signal ``1'', and O and O' are the exact and approximate outputs, respectively.

The existing computation methods of AC error metrics have different emphases. In terms of research object, most literatures focus on approximate adders, some work points to approximate multipliers, and several methods do not distinguish the AC function. From the method property perspective, there are three categories of methods including simulation analyses, statistical or analytical methods, and formal methods. These three categories of error characteristic analyses methods are described in Subsections 2.1-2.3, respectively.

2.1   Simulation Methods

During the process of circuit reliability analysis, Monte Carlo (MC)^[28] simulation is a classical and accurate method to emulate circuit behaviors for both conventional precise circuits and ACs. Unlike the exhaustive simulation which exhausts all input combinations, MC relies on random number generators that sample the random activities of the analyzed circuit. The advantages of the MC simulation method include the intuitiveness and the ability to simulate models for which deterministic solutions are intractable, and thus it is more accurate than analytical methods and formal methods. However, for large-scale circuits, MC is very time-consuming. The possible long running time and the large amount of computation resources are required to complete the simulations. Hence, generally the simulation is taken as an auxiliary technique in the error characteristics analysis of ACs, which is used to deal with some relevant statistics. In addition, the MC simulation is also regarded as a golden method for verification, e.g., it is used to verify the intermediate or final results of the analytical error analysis methods^[29].

Generally, during accuracy evaluation, the simulation is only utilized as part of the whole process, or it is improved to avoid time-consuming exhaustive simulation. Venkatesan et al.^[30] introduced the so-called MACACO systematic methodology for the modelling and analysis of circuits for approximate computing. This methodology is applied to analyze a range of approximate implementations of data path building blocks and help the designer choose the required one. In the MACACO method, MC is utilized to construct the binary decision diagrams (BDDs) of the large bit-width modules. In [24], the simulation technique is combined with the analytical methods to carry out error estimation. Bonnot et al.^[31] used a geostatistical inference method Kriging to reduce the simulation time, and analyzed the noise power and word length of ACs. The simulation methods can be applied to ACs with different functions. These methods are relatively accurate but time-consuming. Moreover, during simulation, the error statistics and error distribution are described by numerical data; therefore, parametric calculation based on the circuit design cannot be carried out. Although exhaustive simulation is not preferred, the chosen number of MC simulations is not always optimal, and hence the quality of the error estimation results cannot always be predicted accurately.

2.2   Analytical Methods

Despite the simulation method can perform checking and quality assessment simultaneously, the exhaustive enumeration of the input combinations is tractable only for small-scale circuits. In order to address the time-consuming issue of simulation methods, various statistical and analytical methods have been proposed. These techniques have some common features, i.e., the error is expressed as a function of the inputs, the number of truncated bits, the length of carry-chain, the number of sub-components, etc. There are also some methods analyzing the error probability, which aim at some specific functions of ACs.

According to the way of improving the performance, the approximate adders can be classified into low power approximate adder (LPAA) and low latency approximate adder (LLAA)^[32]. The LPAA usually obtains low power consumption by simplifying the circuit structure, reducing the number of transistors and the internal node capacitance^{[33, 34]}. In the LLAA, the multi-bit adder is divided into several sub-adders, and the carry propagation chain is cut off. By predicting the carry, additions of the high-bit sub-adders and low-bit sub-adders are performed in parallel; hence the delay is decreased (e.g., [35]).

Due to the different architectures of LPAAs and LLAAs, the calculation methods of the error probability are different. Among the LPAA-related studies, the single-stage error probability evaluation is relatively simple and is always finished analytically^[36]. For multistage LPAAs, the work in [34] estimates the probability of errors occurring in the sum and carry signals, and carries out the exhaustive simulations for comparison. In [32], an analytical method is proposed to report the error probabilities for a cascade multistage LPAA. Iterative analysis is used to compute MED, MSE, and WCE in [26]. In order to make the computation more efficient, based on the quad-tree representation, the work in [37] accurately computes EP and MED for different input patterns. While in LLAAs, the number of bits of a sub-adder consists of the number of bits contributing to the final output and the number of bits used to predict the carry. Therefore, the error of an LLAA mainly comes from carry prediction. The error probability analysis is based on the calculation of the carry propagation probability and the carry generation probability^[28]. According to this rule, error probability evaluation is conducted for the low latency adder GeAr^[35]. In the evaluation model of the almost correct adder (ACA), the outputs of every two sub-adders are assumed to be independent and then the simplification process is adopted^[38]. However, the model^[38] is inaccurate in the case of strong correlations.

For approximate multipliers, there are some other error probability analysis methods where the analysis process is determined by the specific architecture of the multiplier. The existing approximate multipliers can be classified into four types.

Type 1. The multipliers are composed of approximate partial products that are accumulated by using precise adders. A large multiplier is constructed by small multiplier building blocks (e.g., [39, 40]).

Type 2. The multipliers are composed of precise partial products that are added by approximate adders or compressors (e.g., [41, 42]).

Type 3. In these multipliers, both partial products and addition parts are approximate.

Type 4. The multipliers are designed based on the approximate algorithms.

For the approximate multipliers of type 1, Mazahir et al.^[43] presented the probabilistic error analysis based on recursive computation. Since the approximate multipliers under consideration are constructed by small approximate multiplier building blocks, an error occurs in the approximate multiplier when any one of the building blocks generates an error. According to this observation, the error probability calculation model is then developed for the inputs under uniform and non-uniform distributions, respectively. For type 2 multipliers, a fast error analysis method for multipliers through topological traversal (FEMTO) is presented for Wallace multipliers consisting of approximate full adders (FAs)^[44]. In this work, the error probability mass function (PMF) of each FA is firstly obtained. Since the total error of the approximate multiplier is the sum of the errors introduced by the approximate FAs at all stages, the PMF of the total error is calculated by a convolution of a weighted set of error PMFs of individual FAs. For type 3 multipliers, the existing work^[45] mainly calculates the error metrics by using simulation and statistical methods. For type 4 multipliers, existing designs^{[14, 46]} focus on the logarithmic multipliers using approximation algorithms, e.g., converting multiplication to addition, approximating the transformation of input operands, and truncating some least significant bits. For this type of approximate multipliers, the error characteristic analysis is mainly based on the approximation algorithm, and the error metrics are calculated according to the logarithm calculation rule or other analytical models. For example, in [14], according to the approximation model of ${\log}_{2}N$, the MSE and MED are calculated by the bit width of the input operands and the input range of the approximate multiplier.

The analytical methods are relatively fast and efficient. On the other hand, some of these methods depend on the functions and design architectures of ACs. This kind of methods are suitable for some specific ACs.

2.3   Formal Methods

The accurate mathematical formulation is only suitable for some error metrics which can only be used for those ACs with regular structures. This limitation can be overcome in some degree by using formal methods such as BDDs^[30], Boolean satisfiability (SAT) solvers^[47] and symbolic computer algebra (SCA)^[48]. A formal approach is not limited by the specific structure or function of an AC. To apply the formal methods, the function comparison between an AC and its conventional exact circuit needs to be transformed into a Boolean satisfiability problem. In the error evaluation procedure, generally two Boolean functions are constructed: one is the exact function called F and the other is the AC function called F' (see Fig.1)^[47]. Several error metrics are measured by different Boolean algebra functions based on F and F'. Fig.1 shows a common approximate miter circuit to implement the Boolean algebra function of error metrics^[47]. Different designs of “error computation circuit” can measure different error metrics.

Figure  1.  Several error metrics computation by different Boolean functions^[47].

下载: 全尺寸图片 幻灯片

As shown in Fig.1, the error rate can be calculated in the computation circuit where the outputs of F and F' are connected via several XOR gates whose outputs are fed into an OR gate. The error metrics include the absolute error, the squared error, the relative error, Hamming distance and common equivalence checking metric under the average case and the worst case respectively.

Based on a SAT solver, [30] utilizes an ILP solver in the formal analysis of ACs. To be more efficient, SATOne and SATCount operations are used to formulate the error computation^[47]. The algorithms can be looked as a universal recipe on how to determine the error regardless of the chosen formal apparatus. Based on BDD, WCE, MED and ER are estimated by a generic algorithm of the approximate minimized BDD^[49]. Lately, a greedy bucket-based BDD minimization algorithm is proposed to compute MED, MRED and ER^[50]. In SCA, the circuit Boolean polynomials are divided by gate polynomials to obtain the remainder which denotes the error. In [51], the remainder is represented by the built algebraic decision diagram (ADD), and the error metrics of an AC are evaluated by a tailored ADD traversal algorithm. This method can measure WCE, WCRE, MED, MRED, MSE, ER and the maximum HD. Besides the main-stream approaches, some techniques have been developed to improve the miter construction and extend the applicable circuit scope^{[52, 53]}.

In summary, in the formal methods for error evaluation, firstly the approximate and its corresponding exact circuit functions are denoted as Boolean polynomials, and then a miter construction or some Boolean algebra computation models are used to filter out the approximate design which satisfies the error requirements. In some degree, this kind of methods are more efficient and universal than simulation and analytical methods. However, once the AC is large, the Boolean polynomial computation will be very complex even if the BDD and ADD are improved by minimization and tailoring techniques. Hence, formal methods are more suitable for the AC with small or medium scale. Additionally, compared with other kinds of error characteristic analysis methods, the formal methods do not distinguish AC functions. Hence, most of the formal methods can be used to analyze combinational ACs. While only a small number of methods evaluate the errors of sequential circuits, which is well worth investigating.

3.   Reliability and Test of AC

In this section, we discuss some crucial and under-investigated problems, which are the reliability prediction and state-of-the-art test for ACs, taking the acceptable output into consideration. Nowadays, one problem of nanoscale IC is its vulnerability to manufacturing defects (chiefly addressed by test) and to failures during its lifetime (chiefly addressed by reliability-enhancement techniques).

When the approximate computing circuits step into manufacturing and application, the process variability, transient faults and aging effects inevitably threaten their reliability^[54]. Some emerging technologies make the approximate circuit face the intrusion of defects. For example, some new types of defects may be caused by the continuous shrinking of one dimension, the multi-gate structure and the short channel effect in FinFET transistors. On the other hand, the reliability issues caused by transient defects or aging effects are varying over time. The circuit reliability also changes with the operation conditions such as the operating voltage, temperature, and switching activities. The fault probability distribution of wires is the key factor for electro-migration (EM) failure mechanism. The parameter-changing model of CMOS plays a key role in the bias temperature instability (BTI) and the oxide breakdown mechanisms.

The manufacturing defects and operational faults pose a threat to AC reliability, and determine whether the AC satisfies the truth table and can be used in an error-tolerant application. Therefore, the analysis of AC reliability and test is essential. Compared with conventional circuits, the test and reliability prediction of ACs need to consider their acceptable outputs.

3.1   Reliability Prediction of AC

In ACs, some functional outputs which are different from those of exact circuits may be acceptable in some error resilient applications. Therefore, the AC reliability constraints can be relaxed. Then, we define the reliability of an AC as the probability of obtaining acceptable outputs under the influence of manufacturing defects and operational faults. Reliability prediction can help circuit designers improve the AC structure during the design phase. In recent years our team has focused on the reliability prediction for ACs.

Currently the existing work mainly focuses on approximate arithmetic circuits. To estimate the AC reliability, several terminologies need to be introduced, which include: 1) acceptable output—the AC output that meets the application requirement; 2) approximate output (AO)—the output of the fault-free AC; 3) exact output (EO)—the output of the corresponding fault-free exact circuit. For the sum of approximate addition, the product of approximate multiplication, and the quotient of approximate division, the acceptable output range is considered to be [min(AO, EO), max(AO, EO)]. Then, the reliability can be estimated by the probability that the outputs are in the acceptable output range. Based on this consideration, our team has explored several approaches^[55-58].

In [53], based on the PTM model, two methods are presented to estimate the reliability of approximate adders. In order to get the acceptable outputs probability for one input vector, in the first method every acceptable output probability is added directly, and in the second method the sum is weighted. At last, the reliability is calculated as the average value of the acceptable outputs probabilities assuming inputs follow the uniform distribution. These two methods are relatively accurate but with exponential complexities. Furthermore, the correlations caused by the reconvergent fanouts are not considered. In [56], the iterative PTM concept^[53] is utilized and the correlation vectors are derived when calculating the approximate arithmetic circuit reliability. Hence, the correlation problem is alleviated and the scale of the evaluated circuit is increased. Furthermore, the evaluated circuits can be extended to approximate multipliers. In [57], Jiang et al. investigated the acceptable outputs of the quotient and remainder in an approximate divider, and presented three methods to estimate approximate arithmetic circuit reliability based upon PGM. This work can evaluate many approximate arithmetic circuits, including adders, multipliers, and dividers, and use three methods to trade off between the complexity and accuracy.

Except for the reliability evaluation, we still proposed an approach to calculating the failure probability of approximate arithmetic circuits^[58], i.e., the probability of yielding unacceptable outputs due to a soft error at the logic level. Furtherly, the algorithm is expanded to search the critical gate nodes whose infection leads to the maximum failure probability. Fig.2 shows the critical nodes found in an approximate adder in EvoApprox8b^[58]. This result is reasonable because the location distribution of the critical nodes coincides with that of the MSBs whose infection can cause large output errors.

Figure  2.  Critical nodes in add8_006^[58]. ni: node i.

下载: 全尺寸图片 幻灯片

Although some work has been done on the reliability prediction of ACs, some challenges need to be explored. Firstly, the acceptable output range is a key factor in the prediction of AC reliability. This is because the reliability is estimated by the probability that the function output belongs to the acceptable output range. In the current work, the acceptable output range is set to [min(AO, EO), max(AO, EO)], which is reasonable but not exact. To be more realistic, the acceptable output range needs to be explored according to the requirement of the error-tolerant application that uses the AC. Secondly, the fault type and the failure mechanism have not been fully considered in the reliability estimation. Current work mainly focuses on the logic level. However, the consideration of some defects occurring in the transistor level can make the reliability analysis more accurate. Thirdly, the considered ACs in the reliability evaluation are limited to approximate arithmetic circuits. Another possible research direction on AC reliability is to expand the types of the estimated ACs. We may consider other combinational and sequential circuits involving ACs in the next step.

Considering the defects in manufacturing and the faults in use, AC reliability is estimated in advance in the design stage, which helps the designer strengthen the design. At the manufacturing stage, the test of AC is another important procedure that is valuable to be explored.

3.2   Test of AC

Generally, the manufacturing test is to detect whether there is a physical defect in the chip. However, ACs are not necessarily to be defect-free. An AC should be tested as valid even though there are physical defects in the circuit, as long as the errors can be tolerated under approximation. Thus, the test constraints can be relaxed. The test rules for ACs are different from those for conventional exact circuits. The main difference lies in that a defect may cause the AC to behave differently from the exact circuit, while the output is still in the acceptable range. In this case, the circuit should not be abandoned. This rule may increase the yield since less circuits will be rejected. Furthermore, since the size of the test set is reduced, the test cost and time may be reduced. Meanwhile, the online testing can benefit from the time reduction. According to the whole procedure of the AC test, the approximation-aware (AxA) test flow is composed of three main stages^[59]: 1) AxA fault classification, 2) AxA test pattern generation and 3) AxA test set application. In AxA fault classification, the faults are divided into two categories, i.e., the faults producing catastrophic effects on the circuit behavior, and those producing acceptable effects. Hence, the test pattern generation needs to produce the test vectors which can cover all the catastrophic faults and peel off the acceptable faults as many as possible. At last, the test set application divides the ACs into fault-free, acceptably faulty and catastrophically faulty. The circuits falling into the third group should be discarded.

Fault classification is the first step of the AxA test. As mentioned, the possible faults consist of two subsets, i.e., acceptable and catastrophic fault sets. The faults in both subsets cause errors in the output of an AC.

As shown in Fig.3^[60], firstly an acceptable threshold Thr is set. If there is no fault, the error is certainly lower than Thr (the error set is denoted as E). If faults occur, every fault in the acceptable set Fa causes that the output error is always equal to or lower than Thr (the error set is denoted as Ea). In the catastrophic set Fc, for each fault there exists at least one input vector that produces an output error greater than Thr. The error set is denoted as Ec.

Figure  3.  Fault impact on ACs^[60].

下载: 全尺寸图片 幻灯片

The key point is to separate acceptable faults from catastrophic ones. During this procedure, it is crucial to measure the output errors of an AC for a proper classification. Some measures are based on the error metrics mentioned at the beginning of Section 2. In [61], given one error threshold for an AC, after calculating the error metrics of HD and WCE, each fault can be categorized into the acceptable set or the catastrophic set. In [62], single condition test (SCT) metrics are proposed, which cost less effort for the fault classification compared with the measures based on the mean error metrics. In [63], fault classification techniques are improved by utilizing a filter to mask the effects of acceptable faults. In this filter, the netlists of the AC and the exact circuit are both embedded into a classifying architecture. Only for a catastrophic fault, this architecture produces an abnormal result. Based on this classification architecture, the AxA test can use the conventional test approaches. This architecture is only simulated and is not manufactured. Compared with the work in [61], the method proposed in [63] spares much more time.

Test pattern generation is the second step of the AxA test. For ACs, test patterns need to cover all catastrophic faults and as few acceptable faults as possible. The work in [64] is not specific for ACs, but the structural and functional analysis for the approximate cases in conventional circuit tests can be regarded as a good starting point for the AC test. [64] identifies and protects just the vulnerable circuit part for the test pattern generation. [60, 65] begin to focus on the characteristics of ACs. Traiola et al.^[57] presented three ATPG approaches, the architecture under test (AUT), the fault simulation (FS), and the pattern sorting (PS), for test pattern generation of ACs. The AUT takes the AC netlist, the original exact circuit netlist, the error metric, and the error threshold as the inputs of ATPG. Taking WCE as the error metric, ATPG can find the patterns for testing the catastrophic faults. The AUT can achieve a significant test reduction but the test patterns may increase for some cases. The FS alleviates this problem, but its maximum amount of test reductions is lower than that of the AUT. Thus, based on the FS, the PS is presented. In the PS, the test patterns are sorted according to their coverages for the catastrophic faults, i.e., the first test pattern covers the most catastrophic faults. The PS approach increases the test pattern reduction at the cost of additional fault simulations for the sorting.

Based on the fully conventional ATPG, the difficulty of the AC test lies in how to compare the responses of an AC with those of its exact counterpart. Chandrasekharan et al.^[61] proposed a SAT-based augmented ATPG technique, using the SAT solver to pre-process and classify the faults before applying ATPG. However, since the conventional ATPG mainly focuses on the faults propagating to the primary outputs, the test pattern generation is not fully aware of the error tolerance margin. Furthermore, some detectable catastrophic faults can be mistakenly regarded as acceptable faults as the conventional ATPG tools always choose the shortest fault propagation path without checking every possible path. To overcome these two limitations, [66] evaluates all propagation paths and converts the error tolerance margin into the SAT formulation, which can help to classify the acceptable faults and undetectable faults correctly.

As discussed, compared with the conventional circuit test, the key difference of AC test lies in picking out the acceptable faults rather than the catastrophic faults. How to generate the test patterns which can detect the most catastrophic faults and as few acceptable faults as possible? Traiola et al.^[67] applied a new engine to deal with the AxA test pattern generation. In the input vector set, the engine tries to search the smallest subset which can cover all the catastrophic faults and the least acceptable faults. It measures the coverage rates of the two kinds of faults, and constructs and resolves an integer linear programming optimization problem to find the optimal subset.

The third step of AC test is the test set collection and application. In the flow proposed in [66], test set collection is conducted especially. As shown in Fig.4, firstly a fault is injected to the approximate sub-module, and the whole circuit containing the approximate and exact sub-modules is converted to a SAT instance. If and only if one or multiple input vectors lead to an output error beyond the error tolerance margin, the SAT instance is satisfiable and the catastrophic fault is found. After the SAT solver evaluates all propagation paths from the fault source to every primary output, the test patterns that can detect the catastrophic faults are then collected to form the test set.

Figure  4.  SAT-based ATPG for test set collection.

下载: 全尺寸图片 幻灯片

The AxA test set application technique is based on the well-known signature analysis concept^[68]. The signature analysis is applied to the AxA test and consists of two periods. At the design time, the test patterns are used and the faults are injected to the AC, and the test responses are compacted into a signature. During this period, the acceptable and catastrophic signatures are both obtained, and the acceptable signatures which overlap with the catastrophic ones are then removed. The remained acceptable signatures are called the AxA signatures. At the test time, the test patterns which detect as few acceptable faults as possible are chosen; the test responses are compacted into a signature and compared with those in the AxA signatures. As long as there is one match, the AC is considered as acceptable. Otherwise, the circuit is rejected.

In general, most of the AC tests can be carried out by conventional circuit test methods, such as the ATPG technique, the SAT solver and the signature analysis concept. In AC test, the key is differentiating the acceptable faults from the catastrophic faults. Currently the faults are classified by calculating the AC error metrics and setting the error thresholds. Nevertheless, in terms of fault acceptability, it is important to consider the accuracy requirement of the specific error-resilient application.

After the discussions on reliability analyses and test processes for ACs, we know how to predict and detect the reliability of an AC. In Section 4, we will review the reliable design involving ACs, which may be helpful for the investigation of AC reliable designs.

4.   Reliable Design Involving AC

In this section, we discuss how approximate designs support low-cost fault-tolerant architectures with enhanced reliability.

Among many error detection and correction techniques, one of the most frequently-used methods is the multiple modular redundancy^[16]. For example, dual modular redundancy (DMR) and triple modular redundancy (TMR) are popular for error detection and logic masking. The two techniques have full error detection or error masking capabilities; however, they introduce more than 100% and 200% area overhead, respectively. Since over 20 years ago, some researchers have explored on finding the optimal balance between the level of protection and the extra cost in area, power and performance. In the early periods, partial logic masking is carried out by using DMR or TMR with a partial replication of the logic^[16]. Partial logic masking may be effective, yet it is still based on a conventional technique; it has limited scalabilities and may introduce performance penalties. Hence, some literatures^{[17, 18]} began to study the application of approximate logic circuits in the fault-tolerant techniques, i.e., using approximate designs to replace the exact copies of the target circuit.

Generally, in the generation of the redundant module(s), according to the original exact logic function F, the approximate logic function F' needs to produce the same values as F for some inputs^[17]. The module with the approximate logic function F' is used for error detection or correction in the cases where F' overlaps with F. Currently, this idea has been applied in DMR, TMR and quadruple modular redundancy (QMR)^[17-19].

In the context of DMR, AC design is used to construct the redundant module for concurrent error detection^[18]. The approximate logic function is either a 0-approximation or a 1-approximation of the original exact logic function. For every input vector, a 0-approximation function $F'_0$ outputs 0, which can always guarantee the original function outputs 0. The 1-approximation function $F'_1$ has a similar property. Then, for every primary output of the circuit, a 1-approximation or a 0-approximation can be used for the detection of $1\to0$ or $0\to 1$ errors, respectively. The method of [18] uses a SAT algorithm to detect and discard incorrect approximations.

In TMR, sometimes two redundant modules are designed based on ACs in the error correction scheme. This kind of TMR is called approximate TMR (ATMR). The two ACs in ATMR are designed based on the 0-approximation $F'_0$ and 1-approximation $F'_1$ of the original function, respectively. According to the definitions of the 0-approximation and the 1-approximation, there exist $F'_0$ = 0 $\Rightarrow$ F = 0 (i.e., F = 1 $\Rightarrow$ $F'_0$ = 1) and $F'_1$ = 1 $\Rightarrow$ F = 1, and thus the three logic functions have the relationship shown in Fig.5. Errors in $F'_1$ can always be corrected in the on-set of F, and errors in $F'_0$ can always be corrected in the off-set of F. However, the area between $F'_0$ and $F'_1$ is the unprotected area. To deal with this problem, a new voter^[69] is designed by using an error masking function instead of majority voting. Based on the concept of the unate functions, [70] makes an improvement in the construction of ACs. In this work, the testability measure is used to increase the error coverage. In order to make better trade-off between area and error masking, some studies endeavour to find new computations of approximation functions^[71]; some researchers devise a full-ATMR that uses three approximate logic modules to compose TMR^[72].

Figure  5.  Relationship of the three logic functions in ATMR^[69].

下载: 全尺寸图片 幻灯片

Although using approximate designs in TMR can reduce the area cost and mask most of the faults, the approximate TMR generally has a partial error-masking capability and cannot be used in safety-critical scenarios. In ATMR, each approximate module has its own unique domain of approximation. If the output error of one approximate module caused by approximation coincides with the error of the original module due to hard faults, this error cannot be corrected. To resolve this problem, quadruple approximate modular redundancy (QAMR) is proposed, which can achieve the same level of reliability as the conventional TMR^[73]. QAMR constructs the QMR by four approximate modules with an overall smaller area overhead than the conventional TMR. Fig.6 shows a simplified example of a QAMR implementation. For a given input vector, at least three approximate modules can provide the voter with the same output as that of the original module. Thus, the voter has a majority of the correct responses. After this solution was presented, [74] further demonstrates the advantages of QAMR compared with TMR. It can be found that for a single fault, QAMR and TMR have the same fault-tolerant capability for all input vectors, while for multiple faults QAMR avoids the overprovision of TMR. In the design of QAMR, each approximate module is constructed by selecting four disjoint subsets of outputs and removing one specific subset for each output. While the design in [74] is not applicable in some degree, [75] proposes another scheme utilizing three identical approximate modules and one exact module to construct QMR. Also, a special voter is designed which is a two-step approximation-aware voter based on the error magnitude of the output. The final voter permits the acceptable error of the approximation which is qualified by ED. In this context the solution accomplishes 100% error tolerance.

Figure  6.  Illustration of QAMR^[73]. Approx.i means approximate module i, and Oi means output i.

下载: 全尺寸图片 幻灯片

As discussed in this section, approximate modules have been utilized to reduce the area and power cost of conventional fault-tolerant schemes (i.e., multiple modular redundancy). Based on these researches, a valuable topic would be exploring what fault-tolerant techniques can protect approximate designs and how the techniques affect ACs’ reliability and accuracy.

5.   Conclusions

In this article, the reliability related issues of ACs were reviewed in several aspects. In order to choose the proper approximate design among a large design space, error characteristic analyses of different approximate designs are needed. After the approximate design is picked out, considering the manufacture defects and faults in operation, the reliability estimation and testing methods were discussed for ACs. According to the prediction results of reliability and vulnerable node locations, designers can adjust and improve an AC design in the early stage. The AXA test can improve IC yield. These two aspects of research need more attention. For the high reliable design involving AC, some existing work utilizes ACs in conventional fault-tolerant schemes to reduce hardware overhead. However, the techniques to enhance AC reliability deserve further attention.

Furthermore, there are still some problems to be addressed for ACs. Since the AC is born for the error tolerance of many applications, how to analyze the AC accuracy and reliability for different specific applications is challenging. For example, both the error metric threshold in the error characteristic analysis and the acceptable output range in the reliability estimation need application-oriented explorations. Currently, although PSNR can be regarded as a knob for image processing, the research for other error tolerant applications, such as data mining, voice identification, is still vacant. This requires the cooperation of experts in specific fields, the study of professional knowledge, and the exploration of practical problems.