{'fraction_non_alphanumeric': 0.03695836873406967, 'fraction_numerical': 0.02881619937694704, 'mean_word_length': 4.280373831775701, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Novel Approach for Fast and Accurate Mean Error Distance Computation in Approximate Adders

In error-tolerant applications, approximate adders have been exploited extensively to achieve energy efficient system designs. Mean error distance is one of the important error metrics used as a performance measure of approximate adders. In this work, a fast and efficient methodology is proposed to determine the exact mean error distance in approximate lower significant bit adders. A detailed description of the proposed algorithm along with an example has been demonstrated in this paper. Experimental analysis shows that the proposed method performs better than existing Monte Carlo simulation approach both in terms of accuracy and execution time.


I. INTRODUCTION
In recent years, approximate computing has come forth as an encouraging solution to counter the rapid increase in energy consumption in modern-day applications like image processing and machine learning [1]. Approximate computing targeted for error-tolerant applications introduces selective approximation in arithmetic computations, which causes an occasional deviation from the theoretical output while achieving significant improvements in area, delay, and power. Adders being the key functional component in most of the errortolerant applications have attracted a significant amount of research interest in this aspect [2]- [7].
Approximate adders can be classified into two broad categories: Block-based approximate adders and approximate lower significant bit (LSB) adders. In block-based adders, the sum of each bit is calculated from speculative carry bits computed from previous LSB inputs [8]. The concept of block-based adders has originated from the principle that the probability of longer carry propagation is quite low for random input conditions [2]. Examples of such type of adders are almost correct adder (ACA), error-tolerant adder, carry skip adder, carry speculative adder [9]- [12]. On the other hand, in approximate LSB adders, the full adders in LSB positions are replaced with approximate adders. The fulladders in most significant bit positions are kept accurate. The approximate LSB adder includes lower-part OR adder (LOA) and approximate mirror adders (AMA) as examples [4], [5], [13]. The block-based adders have high speed compared to approximate LSB adders. However, approximate LSB adders are comparably more hardware and power efficient [14].
Various error-metrics have been introduced in literature to evaluate the efficiency of approximate adders along with traditional performance metrics such as area, delay and power [15]. The error metrics include error rate (ER), mean error distance (MED), mean square error distance (MSED), mean relative error distance (MRED). For image processing applications, peak-signal-to-noise-ratio (PSNR) is typically used as a performance measure to evaluate image quality. It has been found that PSNR has higher dependence on error metric MED as compared to the ER [16]. Though the approximate LSB adders have a very high ER compared to block based adders, the analysis presented in [14] shows that they have a moderate MED.
It is imperative to evaluate error statistics of various approximate adders for selecting an optimum design for a certain application. Several approximate circuit synthesis techniques have been proposed in literature where error metrics such as ER, MED are used as a constraining factor [17]- [19]. One of the biggest challenge is fast and accurate evaluation of error metrics. An exact MED calculation would require computation for all possible input combinations i.e 2 2n iterations for nbit addition. For example, calculation of MED for a 12bit adder requires a simulation time of roughly 20 seconds running on Intel I5@3.2GHz processor core. Time-consuming exhaustive simulation can be avoided by adopting Monte Carlo sampling technique which provides near-exact measures of error metrics related to approximate adder designs [16], [20]. Accurate methods to calculate error statistics in block based adders are presented in [21] and [22]. However, to the best of our knowledge, no analysis has been presented in existing literature which shows accurate computation of error characteristics in approximate LSB adders. In this article, we propose a novel accurate and efficient approach of MED calculation in approximate LSB adders.
The paper is structured as follows.The algorithm for MED computation in approximate LSB adders is presented in Section II. An example for MED calculation of 2-bit approximate adder is also illustrated in this section. Analysis of the proposed algorithm in terms of iteration count and runtime is carried out in section III. Section IV summarizes the contribution of this paper.

II. NOVEL FAST AND ACCURATE MED COMPUTATION APPROACH
Error distance (ED) is defined as the absolute difference between the accurate computation result and the approximate result. The ED value averaged over all possible input combi-arXiv:1803.08005v1 [cs.OH] 6 Mar 2018 nations gives the mean error distance (MED) parameter. MED for n-bit adder is given by (1) ED is the absolute error distance whereas SU M ACC and SU M AP P are the results of the accurate and the approximate addition of two n-bit inputs respectively. The generalized approximate LSB adder configuration considered for the MED computation is shown in Fig. 1. An n-bit approximate adder can be composed of m-bit approximate adders and (n − m)bit accurate adder. Each m-bit approximate adder can be composed of several uniform k-bit approximate sub-adders with variable configurations.
Compute CoutE, SumEq:p, CoutA, SumAq:p. 10 Compute Sum Dif f erence(); The main objective of our proposed algorithm is to build a 2-D memory database of size M × 2. The parameter M corresponds to the maximum absolute difference possible for an n-bit adder with m LSB approximated which gives M = 2 m+1 . Four such memory elements generically named as M AT {CoutE CoutA} as shown in Fig. 2a are created for four different carry-out conditions of m th bit. CoutE and CoutA represent exact and approximate carry-out bits respectively. Each of the row indices represent the differences between accurate and approximate addition for a certain combination of n-bit input A and B. The elements in the matrix refer to the number of input combination of A and B that has the sum difference equal to the row index value. The first column specifies the positive difference while the second column indicates a negative difference in sum. The generalized memory structure of the final M AT matrix is shown in Fig. 2b. The MED calculation approach proceeds from LSB to MSB bits of adder. We can consider the initial difference in sum between accurate and approximate adder as 0 by assuming m = −1. Hence, four matrices of size (2 −1+1 ×2) i.e (1×2) are initialized. As we gradually approach towards higher significant bits from 0 th bit to m th bit, the matrix size also grows accordingly from (1×2) to (2 m+1 ×2). The proposed algorithm M ED Cal (Algorithm 1) computes (a) 0 0 1 1 • STEP-1{Lines 1-2}:Initially, four matrices LM AT 00, LM AT 01, LM AT 10, LM AT 11 are initialized to |10|, |00|, |00| and |00| respectively which would act as an input matrix for the 1 st iteration. Zero carry-in bit is considered for both accurate and approximate adder. This is the reason why the value stored at (0, 0) index of matrix LM AT 00 is kept at 1. • STEP-2{Lines 3-5}: In this step, four output matrices HM AT 00, HM AT 01, HM AT 10, HM AT 11 are defined, and all the elements of the matrices are initialized to zero. The size of the matrix is given as where i is the loop counter variable. The MSB and LSB of the approximate k-bit sub-adder considered in current iteration are represented by q and p respectively.
• STEP-6{Line 13}: The steps 2 − 5 are then repeated m k times until we get 4 matrix each of size M × 2. The error distance for the final matrix HM AT {CoutECoutA} is then evaluated using function Calculate M ED(). The cumulative ED for any matrix of type shown in Fig. 2b can be calculated using Eqn. 4. The parameter µ in this equation equals to +1 and −1 for unsigned number and signed numbers respectively. If ED tot00 , ED tot01 , ED tot10 , ED tot11 corresponds to the cumulative ED computed from HM AT 00, HM AT 00, HM AT 00, HM AT 00 respectively, the final MED then can be computed using Eqn. 5.
For a clear understanding of the algorithm, an example is presented for MED computation of an unsigned approximate adder with m = 2, k = 1 and C in = 0. This assumption leads to a 2-bit approximate adder with an LSB half-adder and an MSB full-adder. The truth-table of LSB and MSB adder of a random 2-bit approximate adder example are illustrated in Table. I. Since initial carry-in is fixed to zero, there will be only one carry-in condition resulting in 4 iterations for i = 0. For i = 1, there will be 16 iterations, 4 iteration for all possible 4 carry-in conditions. All the iterative steps are presented in Table II.  0  0  1  0  1  0  0  0  0  0  1  0  1  1  0  1  1  0  0  1  1  1  1  1  0  0  1  1  0  0  0  1  1  1  1  1  1  0  1  1  0  1  1  0  1  1  1  1  1 1 0 Four 2 × 2 matrices HM AT 00, HM AT 01, HM AT 10, HM AT 110 are initialized to zero. The four matrix elements correspond to a difference of +0, −0, +1, −1 between exact and approximate adders. For 1 st iteration, 00 input condition is considered for which carry-out for both accurate and approximate adder is 0. Hence, the matrix to be modified is HM AT 00. The difference of the sum bit defined as 2 i (SU M E − SU M A ) computes to 0 corresponding to the HM AT 00[0, 0] index position. Element 1 in input matrix HM AT 00[0, 0] index position is then copied to HM AT 00[0, 0]. Thus new HM AT 00 becomes |1 0 ; 0 0| 2×2 which means there is one input combination with zero difference while producing a 0 carry-out bit in both exact and approximate adder. All the other matrices remains unchanged. Similar operations are performed for next 3 possible input combinations. After 4 iterations, one can observe that only 3 matrices are modified which would then be used in subsequent iterations as input matrices. For i = 1, four 4 × 2 new matrices HM AT 00, HM AT 01, HM AT 10, HM AT 11 are initialized to zero. Here, the 0 th column index positions refer to sum difference of +0, +1, +2, +3 while 1 st column index positions correspond to sum difference of −0, −1, −2, −3 between exact and approximate adder. Let us consider an intermediate iteration step 6. In this step, an input combination of 00 is considered for MSB with exact carry-in of 0 and approximate carry-in of 1. Hence, LM AT 01 is used as an input matrix. The carry-out bits for such a combination is 0 for both exact and inexact additions. Hence, a matrix operation is performed on the HM AT 00 matrix. The difference is computed as -2. The [0, 0], [1,0], [1,1] index position element of LM AT 01 is added to [1,2], [1,1], [1,3]  III. EXPERIMENTAL RESULTS AND ANALYSIS MED calculation using exhaustive simulation method have a time complexity of O(2 2m ). On the contrary, the asymptotic runtime of our MED computation method is O(m) for k m. The total number of iterations can be represented using Eqn. 6. We can observe that as k → m, the number of iterations becomes comparable to the exhaustive method. However, k is typically 1 for well-known LSB approximate adders such as LOA and AMA. For our experiments and analysis, we have considered k = 1.
Runtime Speed − up = M C sampling method runtime P roposed method runtime The proposed algorithm is implemented in C++ to evaluate the MED parameter of approximate LSB adders. Several 16-bit and 32-bit approximate LSB adders are generated randomly whose MED value is then computed using our proposed method. We have compared the simulation runtime of our method with the Monte-Carlo (MC) sampling method presented in [20]. All the simulations are done in Linux operating system environment with Intel I5@3.2GHz processor core. Fig. 3a and Fig. 3b shows the speed-up in runtime (Eqn. 7) of the proposed method compared to MC sampling method with samples(S) equal to 2 12 and 2 16 respectively for the 16-bit adder. The results are plotted for different values of m = 6, 8, 10, 12. Similarly, the results for 32-bit adder with m = 10, 12, 14, 16 are also represented in Fig. 3c and Fig.  3d for S equal to 2 16 and 2 20 respectively. Since the MC sampling method only provides an estimate of the actual MED value, there would be some finite error in the calculated MED. The error distribution of calculated MED using MC sampling method in log2 scale is also plotted in the form of box plots. We have considered random 5000 approximate Compared to our accurate technique, MC sampling method have an error median of 4 with maximum absolute error as 23 for 5000 approximate LSB adder cases. Similarly for n = 32 and m = 16, the proposed method is roughly 2 and 34 times faster compared to MC sampling method with 2 16 and 2 20 samples respectively. The respective median error for MC sampling method is 35 and 16.21, whereas the maximum error observed was 80 and 45 respectively. The number of exhaustive simulations required for m equal to 6, 8, and 10 is 2 12 , 2 16 , and 2 20 respectively. Hence, there is no error for respective sample size which is shown by the absence of MED error distribution plot in Fig. 3a, 3b, and 3c.

IV. CONCLUSIONS
This article has proposed a new efficient algorithm to determine accurate MED of approximate LSB adders. The execution time of the proposed method has a linear dependence on the number of LSBs approximated, thus making it much faster than the exhaustive technique. Experimental analysis shows that for k taken as unity, the proposed method is superior to MC sampling method. The developed MED evaluation technique can be modified to compute other errors metrics such as ER, MSED, MRED for approximate LSB adders. In future, we wish to extend our work by developing algorithms which would compute and analyze all error metrics related to approximate LSB adders.