1. Proposed Approximate Adder Architecture

Fig. 3 demonstrates the block diagram of the proposed approximate adder, termed AND-based carry prediction and constant truncation approximate adder (AC$^{2}$A). We denote a pair of n-bit inputs and an n-bit output of the adder as A$_{n-1\colon 0}$, B$_{n-1\colon 0}$, and S$_{n-1\colon 0}$, respectively, and (i)$^{th}$ least significant bit (LSB) of the A, B, and S as A$_{i}$, B$_{i}$, and S$_{i}$, respectively. The n-bit adder is divided into a k-bit accurate and an (n-k)-bit inaccurate part. To ensure an overall accuracy, the k-bit precise adder is placed in the upper position containing the MSBs since it significantly impacts on the overall addition result. Note that any of the conventional adders (e.g., RCA and CLA) can be used for the precise one. Also, the proposed adder adopts an AND-based carry prediction scheme from the inaccurate part to the accurate part to improve the accuracy (see C$_{in}$). The inaccurate part is divided into two parts: 1) the modified FA part that includes an AND-based carry and an OR-based sum generation logics, which perform the approximate addition for A$_{n-k-1\colon l}$ and B$_{n-k-1\colon l}$ and 2) the constant part, which sets each output bit to ``1'' regardless of the corresponding input pair for the lowest l-bit containing LSBs. In the former part, the summation is basically conducted by ORing of the two input bits A$_{i}$ and B$_{i}$ and the carry predicted from the previous bit position C$_{i-1}$ and thus its Boolean equation becomes S$_{i}$= A$_{i}$+ B$_{i}$+ C$_{i-1}$. While the earlier works do not include bit-by-bit carry speculation logic <sup>[12-20]</sup>, the proposed design offers the AND-based carry signal C$_{i}$= A$_{i}$· B$_{i}$ for each bit position to improve overall accuracy performance. Here, it is important to note that the MSB position of the inaccurate part (i.e., (n-k-1)$^{th}$ bit position) exploits XOR instead of OR to approximately add the two input A$_{n-k-1}$ and B$_{n-k-1}$ since the XOR forms the exact half adder structure with an AND gate, resulting in a higher accuracy. The OR gate is relatively cheaper than the XOR in terms of hardware cost, but the XOR and OR gate yield the same output except for the case of A$_{i}$ = B$_{i}$ = 1 out of the four possible input combinations of the input pair. Therefore, to reduce hardware cost without any significant accuracy loss, we leverage the OR gate to produce the approximate summation of A$_{n-k-2\colon l}$ and B$_{n-k-2\colon l}$. In the latter part, the hardware cost reduction can be expected by simply setting the part that has a relatively small effect on the result of the addition (i.e., LSBs) to ``1'' without using any logic gate. Particularly, it reduces the error distance by setting the output to ``1'' rather than ``0'' because the carry prediction from the inaccurate part to the accurate part (i.e., C$_{in}$) may not be correct compared to the precise adder due to cut of the carry chain from the LSB, and the overall approximate summation could become smaller than the correct one. It is worth noting that the length of the constant part can be adjusted to obtain the good tradeoff between the computation accuracy and hardware efficiency. For example, a longer length of the constant part will improve the hardware efficiency but degrade the overall accuracy performance.

Fig. 3. Block diagram of the proposed approximate adder.

2. Error Rate Analysis

The error rate is one of the most important metrics when evaluating the accuracy of approximate adders. In this paper, we analyzed the case where errors occur by deriving a formula for the error rate of the proposed adder. We assume that two input operands A and B are bitwise independent. To derive the error rate in a simplistic way, we first take into account the input cases where no error is introduced. Then, we can obtain the error rate by the probability of a complementary event of the cases. Note that the analysis of the accurate part is excluded here since the exact adder does not generate any error. From (n-k-2)$^{th}$ bit to (l)$^{th}$ bit with OR gates applied instead of XOR gates, if each input pair of the bit position from (n-k-2)$^{th}$ to (l)$^{th}$ is both ``1'', then an error occurs because the corresponding output bit becomes ``1'' due to the OR operation. In other words, the output value is always correct when the input pair is not both ``1''. In addition, if A$_{n-k-2}$ ${\neq1}$ and B$_{n-k-2}$ ${\neq1}$ , the carry to $S_{n-k-1}$(i.e., C$_{n-k-2}$) is not propagated. Then, the error at the (n-k-1)$^{th}$ bit position can be excluded for the error rate analysis since this bit position forms a half adder structure. For the l-bit constant part, no error occurs when each bit of the input pair is different from each other. In other words, when each bit of the input pair is equal (i.e., A$_{i}$ = B$_{i}$), an error occurs with the corresponding bit output of ``1'' although the correct sum is ``0''. In short, the proposed adder always produces correct output under the following two conditions: 1) the input pair is A$_{i}$ ${\neq1}$ and B$_{i}$ ${\neq1}$ where n-k-2 ${\leq}$ i ${\leq}$ l and 2) each bit of the input pair is different from each other in the position from (l-1)$^{th}$ to (0)$^{th}$ bit. Considering both, we can define an event E$_{correct}$ that the adder yields correct additions by:

Then, the error rate of the proposed adder can be derived by the complementary probability of the event as follows:

To verify the adder’s error rate analysis, we conducted a simulation to obtain the error rate values by applying 10 million uniformly distributed random input pairs and compare them with the derived equation. Here, the lengths of the entire adder n and the precise one were set to 16 and 8, respectively. Also, the size of the constant part l was swept from 1 to 7. Table 1 shows the error rate values obtained by the simulation and formula. As can be seen, the derived error rate well matches the simulation results over the various parameter values.

1. Hardware Performance Analysis

For hardware performance analysis, all twelve adders in Table 2 were designed in Verilog HDL and synthesized with a 32-nm CMOS technology. As metrics of hardware performance evaluation, area, delay, power, and energy, which is the product of power and delay, were extracted. The RCA shows the largest area, the longest delay, and the largest power consumption due to the long carry chain from the LSB to the MSB by the FAs. The CLA has a quite shorter delay than the RCA thanks to the carry look-ahead generator while it occupies a larger area because its carry generator requires a considerable number of logic gates. The CLA consumes less energy than the RCA due to its significantly shorter delay than the RCA’s despite its marginally larger power consumption. The AMA5 and LOA predict the carry signal by one of the input pair and the AND operation result of the input pair, respectively. Therefore, the AMA5 goes through one logic gate less than the LOA, resulting in a marginally shorter delay than the LOA. The LOA, OLOCA, and AC$^{2}$A (l=0) show the same delay since they utilize AND-based carry prediction. The OLOCA demonstrates a smaller area and less power consumption than the LOA. Its energy is also smaller than that of the LOA because some output bits are set to ``1'' regardless of the input. The LOTA, which has a simpler structure than the OLOCA, shows superior performance in area and power consumption compared to the OLOCA. The ETAI has a shorter delay than the LOA due to a lack of carry prediction logic. The ETAI’s variants, such as the SETA and ETCA, also have the same delay as the ETAI. The SETA and ETCA, which are simplified versions of the ETAI, have better area, power, and energy performance than the ETAI. The EQSA has a delay that equals to the AMA5 since they perform carry prediction similarly. However, the EQSA has a larger area than the RCA due to its relatively complicated structure to adjust the computation accuracy dynamically according to the control signal. The HOAANED predicts a carry signal based on AND operations but has a longer delay than the LOA because the signal is also applied to the comparator of the inaccurate adder part, which leads to a larger fanout. The AC$^{2}$A (l=4) has the same delay as the LOA because it predicts a carry signal based on AND operation. In order to improve the hardware performance, the proposed adder adopts the nonzero constant truncation scheme. Therefore, the AC$^{2}$A (l=4) has a smaller area and less power consumption than the AC$^{2}$A (l=0). Specifically, the area and power of AC$^{2}$A (l=4) are reduced by 12% and 8%, respectively, compared to the AC$^{2}$A (l=0). The two designs have the same AND-based carry signal prediction, so they have the identical delay, but the AC$^{2}$A (l=4) reduces the energy consumption by 8% more than that of the AC$^{2}$A (l=0). Moreover, the proposed AC$^{2}$A (l=4) can reduce the area, power, and energy by 48.9%, 45.6%, and 45.4%, respectively, compared to the EQSA.

2. Accuracy Analysis

As the accuracy evaluation metrics, error rate, mean error distance (MED), mean relative error distance (MRED), and normalized mean error distance (NMED) were obtained by a software-based simulation using 10$^{7}$ uniformly distributed random input pairs, and these metrics are defined by the following equations:

where n is the number of inputs, ED$_{i}$ is the error distance for the i$^{th}$ item of input data, S$_{i}$ is the accurate output for the i$^{th}$ item of input data, and D is the maximum output of the accurate design ^[29]. The AMA5, which outputs one of the input pair as a summation result, lags behind in terms of accuracy compared to the LOA, OLOCA, ETAI, and SETA that adopt OR or modified XOR operations. Also, the LOTA has similar accuracy characteristics to the AMA5. Since the OLOCA is a design that improves the hardware performance of the LOA by exploiting the truncation scheme, it shows a marginally lower accuracy performance than the LOA in terms of MED, MRED, and NMED. The proposed designs AC$^{2}$A (l=0) and AC$^{2}$A (l=4) offer two of the most accurate approximate adders in terms of the error rate, MED, MRED, and NMED and, as expected, the AC$^{2}$A (l=0) shows slightly better than the AC$^{2}$A (l=4) in these metrics. In short, the proposed AC$^{2}$A (l=0) demonstrates the best accuracy performance in all the error metrics and has a very competitive accuracy performance among the adders considered here.

3. Joint Metric Analysis

In order to observe the tradeoff between hardware performance and accuracy collectively, we consider a joint metric. Here, we adopt the energy-MRED product obtained by multiplying the energy representing hardware performance by the MRED representing accuracy one. The energy-MRED product values were normalized based on the LOA and are shown in Fig. 4. Note that the smaller the value, the better the accuracy compared to the energy consumed by the adder. The EQSA shows the largest energy-MRED product because both the energy and MRED of the EQSA are the largest compared to other approximate adders (see Table 2). The LOTA shows the second largest energy-MRED product because its MRED is the second largest value, although its energy is above average. The proposed two adder designs show the top two energy-MRED performance among the adders, and the AC$^{2}$A (l=4) is the best. Specifically, the product value of the AC$^{2}$A (l=4) is 83% smaller than that of the EQSA. Therefore, considering both energy consumption and accuracy, the proposed adder AC$^{2}$A (l=4) has the best performance.

Fig. 4. Normalized energy-MRED products of various approximate adders.}

1. Machine Learning

K-means clustering is an unsupervised learning used for clustering, such as image classification, and is one of the most widely used machine learning applications. The purpose of k-means clustering is to find similarities in the given data and divide them into k clusters. The addition is heavily used in k-means clustering, and we replace the accurate addition with the approximate ones. The constant k, which means the number of clusters, was set to 5 in our experiment. The performance of k-means clustering can be expressed as the within-cluster sum of squares (WCSS). The WCSS means the distance of data belonging to the cluster from the center of each cluster, and the shorter the distance, the better the clustering. Fig. 5 shows the visualized results of k-means clustering with the accurate and approximate adders, and the WCSS value of the corresponding adder is indicated next to the name of each adder. While the proposed AC$^{2}$A (l=4) demonstrates the best clustering performance in terms of WCSS, which means that its output is closest to the one by the error-free adder, the HOAANED and AC$^{2}$A (l=0) have similar WCSS values to the AC$^{2}$A (l=4). The AMA5, ETAI, ETCA, and EQSA are some of the poorest clustering performances among the adders, and the LOA, OLOCA, SETA, and LOTA are in-between. Particularly, the WCSS by the AC$^{2}$A (l=4) is 56% smaller than that by the ETAI. This proves that the proposed adder is well suitable for the machine learning application.

Fig. 5. Output images of k-means clustering using various adders.

2. Digital Image Processing

To demonstrate that the proposed adder is applicable for image processing applications, the Gaussian filtering was performed using various adders. Specifically, we used a 7${\times}$7 Gaussian filter in ^[30]. This application also mainly utilizes the addition, which can be replaced by the approximate counterparts. The performance of the filtering can be represented by the Peak Signal-to-Noise Ratio (PSNR). Fig. 6 shows the output images of Gaussian filtering, and the PSNR value of the corresponding adder is indicated next to the name of each adder. Note that the PSNR was calculated against the image produced by the error-free adder RCA. The LOA and its variant OLOCA produce the images with the same PSNR value. The ETAI, its variants (SETA and ETCA), and EQSA are also the same. The AMA5 is in-between them. The AC$^{2}$A (l=4) and AC$^{2}$A (l=0) produce the images with the same PSNR value, which is the best value that exceeds 40 dB. This means that the proposed adders yield the output images closest to the one produced by the RCA. Therefore, we can expect the processing quality to be similar to those using the error-free adders with significantly reduced hardware resource consumption.

Fig. 6. Output images of Gaussian filtering using various adders.