Motivation:

As VLSI technology advances, number of transistors and circuit complexity increase which results in increased power consumption. With the development in wearable electronics, portable devices that uses batteries, there is a need for designing digital integrated circuits with maximum processing speed while consuming low power. Approximate computing is emerging as a new design methodology to achieve low power consumption that involves trade off between hardware performance and computational accuracy. There are many applications including image processing and machine learning that need intensive computations and can also tolerate error. Arithmetic circuits of these applications play a major role in deciding the computational speed and energy consumption. Among the four basic arithmetic operations, division is least used due to its high latency. Approximate divider proves to be the solution for low power as well as low latency by simplifying the hardware structure.

Project description:

The proposed approximate divider is aimed to reduce the critical path delay of exact restoring divider i.e., 𝑂( 𝑛2). By introducing small error in the truth table of subtractor cell, the complexity in the divider cell has been reduced which minimizes critical path delay, area, and power of the approximate restoring divider when compared to its exact counterpart. Accuracy of the restoring division can be varied by introducing approximation factor 𝑝. Approximation factor is the number of exact divider cells that has been replaced by the approximate divider cell. In the proposed approximate restoring divider, 𝑝(𝑝+1)/2 exact restoring divider cells are replaced by approximate restoring divider cells in triangle replacement fashion as shown in Fig. 1

Fig 1: An example of 8/4 proposed approximate restoring divider

Fig. 2: Exact divider cell

Fig 3: (a) AD1 cell, (b) AD2 cell, (c) AD3 cell, (d) AD4 cell.

Results:

Error analysis:

The error characteristics of approximate circuits have been evaluated by measuring NMED, MRED that are widely used. Error distance (ED) is difference between accurate output and approximate output and Normalized Mean Error Distance (NMED) is defined as mean of ED normalized by maximum possible output of accurate design. Mean Relative Error Distance (MRED) is defined as the mean value of ratio between error distance and the accurate output. A python script is used to generate all possible input combinations such that no overflow is generated for the accurate Q and R output of 16-by-8 divider. Q-NMED, R-NMED are listed in Fig. 2. Accuracy evaluation of AD2 shows that quotient NMED is low for smaller values of 𝑝. For 𝑝 = 2, 3, 4 AD4 is having Q-NMED, R-NMED order of magnitude smaller than other designs. Although R-NMED for AD2, AD4 are higher, they are still competitive for approximation factors 𝑝 = 2, 3. AD4 with approximation factor 𝑝 = 14 is notably having Q-NMED smaller than any other designs. Overall AD4 with lowest Q-NMED than any other design can be used in error tolerant applications with improved hardware performance.

Table 1: Error analysis summary table

Hardware performance:

The proposed designs are described at the structural level using Verilog HDL. The simulation and functionality verification has been carried out in iVerilog and GTKwave. All the divider designs have been synthesized using Cadence Genus ® with 180nm CMOS technology. The critical path, area and power consumption have been measured. Table 2 reports the area, power and delay for exact divider and proposed divider. The simulation result shows that the proposed dividers have significant performance improvement over the exact divider. The proposed divider AD1, AD2, AD3, AD4 with approximation factor of 14, results in power reduction of 32%, 56%, 45%, 62% respectively when compared to exact design.

Table 2: Area, Power, Timing summary

Application analysis:

Change detection:

Image division is performed for detecting changes between two images or frames in a video. Output from change detection shows the difference between the two images. change detection is widely used in application such as CCTV surveillance, intrusion detection, remote sensing etc. The first image is multiplied by 64 to fit in 16-bit dividend and the second image is directly fed as a 8-bit divisor. AD4 with approximation factor 𝑝 = 14, produces an PSNR of 38.14db as shown in Fig. 4. The comparison between PSNR and SSIM of proposed design is shown in table 3

Fig. 4: Change detection between (a)Image-1 (b)Image-2 (c)Exact divider (d)AD4: P = 14, PSNR = 38.1402db, SSIM = 0.9716

Background removal:

Image division can be extended to remove unwanted or dimmed background from the image. First the input image is scaled to fit in 16-bit input range of dividend. The background of the image is estimated and fed into the divisor. The PSNR, SSIM values for all implemented design for various approximation factor is summarized in Table 3. The images produced by AD4 for 𝑝 = 14 is shown in Fig. 5. The output images of highest quality is produced by AD4 closely followed by AD2. As 𝑝 increases, PSNR/SSIM decreases (SSIM not less than 0.9) because of increase in number of approximate cells. Notably AD4 with 𝑝 = 14 produces PSNR of 42db closely followed by AD-M1 with 38db for 𝑝 = 14. 

Fig. 5: (a)Test image (b)Estimated background (c)Exact divider (d)Proposed design 4: P = 14, PSNR = 42.836db, SSIM = 0.98

Table 3: PSNR/SSIM for change detection and background removal application

Conclusion:

Four designs of approximate divider cells AD1, AD2, AD3 and AD4 are proposed and analyzed for error metrices and hardware performance. AD1 and AD2 introduces approximation in full subtractor cell whereas AD3 and AD4 approximates entire divider cell which results in better hardware performance. AD4 with 𝑝 = 14 shows an power savings of 62% with an reduction in delay of 6ns when compared to exact design. Reduction in number of exact divider cells reduces area and power consumption. The feasibility of employing proposed dividers for real time applications have been demonstrated with change detection and background removal applications.

References:

[1]. restoring division L. Chen, J. Han, W. Liu and F. Lombardi, "On the Design of Approximate Restoring Dividers for Error-Tolerant Applications," in IEEE Transactions on Computers, vol. 65, no. 8, pp. 2522-2533, 1 Aug. 2016, doi: 10.1109/TC.2015.2494005.

[2]. S. Venkatachalam, E. Adams and S. Ko, "Design of Approximate Restoring Dividers," 2019 IEEE International Symposium on Circuits and Systems (ISCAS), 2019, pp. 1-5, doi: 10.1109/ISCAS.2019.8702363.

[3]. J. Liang, J. Han and F. Lombardi, "New Metrics for the Reliability of Approximate and Probabilistic Adders," in IEEE Transactions on Computers, vol. 62, no. 9, pp. 1760-1771, Sept. 2013, doi: 10.1109/TC.2012.146.