Approximate Hybrid High Radix Encoding for Energy-Efficient Inexact Multipliers

Approximate Hybrid High Radix Encoding for Energy-Efficient Inexact Multipliers

ABSTRACT:

Approximate computing forms a design alternative that exploits the intrinsic error resilience of various applications and produces energy-efficient circuits with small accuracy loss. In this paper, we propose an approximate hybrid high radix encoding for generating the partial products in signed multiplications that encodes the most significant bits with the accurate radix-4 encoding and the least significant bits with an approximate higher radix encoding. The approximations are performed by rounding the high radix values to their nearest power of two. The proposed technique can be configured to achieve the desired energy–accuracy tradeoffs. Compared with the accurate radix-4 multiplier, the proposed multipliers deliver up to 56% energy and 55% area savings, when operating at the same frequency, while the imposed error is bounded by a Gaussian distribution with near-zero average. Moreover, the proposed multipliers are compared with state-of-the-art inexact multipliers, outperforming them by up to 40% in energy consumption, for similar error values. Finally, we demonstrate the scalability of our technique.

SOFTWARE IMPLEMENTATION:

  • Modelsim
  • Xilinx 14.2

EXISTING SYSTEM:

In modern embedded systems and data centers, energy efficiency is a mandatory design concern. Considering that a large amount of application domains exhibits an intrinsic error tolerance, e.g., digital signal processing (DSP), image processing, data analytics, and data mining, approximate computing appears as an effective solution to reduce their power dissipation. In approximate computing, error has been viewed as a commodity that can be traded for significant gains in cost (e.g., power, energy, and performance), and as a result, it composes a promising design paradigm targeting energy-efficient systems by extremely decreasing the power consumption of inherently error resilient applications.

Specifically, approximate computing exploits the innate error tolerance of the respective applications and deliberately relaxes the correctness of some computations, in order to decrease their power consumption and/or accelerate their execution. Recently, targeting to take advantage of its benefits, massive research has been conducted in the field of hardware approximate circuits. The main targets are arithmetic units, e.g., adders and multipliers, that are the core components in many embedded devices and hardware accelerators. Extensive research is reported in approximate adders, providing significant gains in terms of delay and power dissipation. However, research activities on the approximate multipliers is less comprehensive compared with the respective on approximate adders. In inexact multipliers, approximations can be applied on the partial product generation, as well as the partial product accumulation. Approximations on the partial product generation and approximations on their accumulation are synergistic, and can be applied in collaboration in order to achieve higher power reduction.

Although significant research has been conducted in the partial product accumulation, research activity on the approximation of the partial product generation is still limited. Finally, another limitation of the existing approximate multipliers is that the majority of them does not examine signed multiplication. In this paper, targeting the design of inexact multipliers by applying approximations on the partial product generation, we propose a novel approximate hybrid high radix encoding. In the proposed technique, the most significant bits (MSBs) of the multiplicand are encoded using the radix-4 encoding, whereas the k least significant bits (LSBs) are encoded using a radix-2k (with k ≥ 4). To simplify the increased complexity induced by the proposed hybrid encoding, the circuit for generating the partial products is approximated by altering accordingly its truth table.

Hence, the number of the partial products decreases significantly and simpler tree architectures are used for their accumulation, reducing the multiplier’s energy consumption, area, and critical path delay. The major contributions of this paper are summarized as follows. 1) We propose and enable the application of hybrid high radix encodings for the generation of energy-efficient approximate multipliers, exceeding the increased hardware complexity of very high radix encodings. 2) The proposed technique can be applied to any multiplier architecture and is reconfigurable, enabling the user to select the optimal per application energy–error tradeoff. 3) An analytical error analysis is conducted, showing that the output error of the proposed technique is bounded and predictable. Such a rigorous error analysis leads to precise and a priori error estimation for any input distribution, without the need of time-consuming simulations. 4) We show that t terms of hardware and accuracy, achieving up to 40% less energy dissipation for comparable error values. More specifically, the proposed technique is applied to a 16×16 bit multiplier and is evaluated using industrial strength tools, i.e., Synopsys Design Compiler, Prime Time, and Mentor Graphics ModelSim. Compared with the accurate multiplier, the proposed technique delivers up to 55% energy and area reduction, for mean relative error up to 0.93%. Moreover, compared with related state-of-the-art approximate computing signed multipliers, our technique outperforms them significantly in terms of energy consumption and error. Finally, we examine the scalability of the proposed technique and show that for the same error value, the delivered energy savings increase as the multiplier size increases.

DISADVANTAGES:

  • Accuracy is less
  • Energy efficiency is low
  • Area size is high and
  • Errors are not reduced

PROPOSED SYSTEM:

Approximate hybrid high radix multipliers

High radix encodings offer partial products reduction, and as a result, their accumulation requires smaller trees, leading to energy, area, and/or delay savings. However, high radix encodings require complex encoding and partial product generation circuits, negating thus the benefits of the partial products reduction. In this section, the proposed hybrid high radix encoding and the performed approximations for simplifying its circuit complexity are presented. In the proposed technique, the multiplicand B is encoded using the approximate high radix encoding, generating , and the approximate multiplication A· is performed. Finally, its adaptation on inexact 16-bit hardware multipliers is described, and a qualitative analysis is conducted, targeting to estimate the potential area gains.

Hybrid High Radix Encoding

In the proposed hybrid high radix encoding, B is divided in two groups: the MSB part of n −k bits and the LSB part of k bits. The configuration parameter, k ≥ 4, is an even number, namely, k = 2m: m ∈ Z, with m ≥ 2. The MSB part is encoded using the radix-4 (modified Booth) encoding, while the LSB part is encoded with the high radix-2 kencoding where and The radix-4 encoding includes (n − k)/2 digits ∈ {0, ±1, ±2}, while ∈ {0, ±1, ±2, ±3,…, ± (2k−1 − 1), −2k −1} corresponds to the radix2k – encoding. Overall, B is encoded with (n − k)/2 + 1 digits. The above hybrid high radix encoding is characterized by increased logic complexity, due to the high radix values of that are not power of two, and thus, an approximate version is proposed. However, in order to retain high accuracy, the radix-4 encoding of the MSB is performed accurately. In particular, in the approximate encoding, all the values that are not power of two and the k − 4 smallest powers of two as well, are rounded to the nearest of the 4 largest powers of two or 0, so that the sum of all the values of the approximate digit is 0. We choose to keep only the four largest powers of two, so that the radix-2k  encoding circuit requires only about the double area in comparison with the accurate radix-4 encoder. Therefore, B is approximately encoded as follows:

where Table I presents the accurate radix-4 encoding. The output signals sign j , ×1 j , and ×2 j define the radix-4 digit  . Their logic equations are the following:

Table II presents the approximate radix-2k encoding. The logic equations of the encoding signals that define the radix2k digit  are the following:

 

The effectiveness of the approximate hybrid radix encoding technique is explored with its application to 16-bit signed numbers, for k = 6, 8, 10, namely, the LSBs are encoded using

Fig. 1.i-bit partial product generator based on (a) accurate radix-4 encoding and the approximate (b) radix-64, (c) radix-256, and (d) radix-1024 encoding. ai :i-bit of operand A, ai = ai⊕ sign.

Fig. 2. Partial product tree based on the hybrid encoding of accurate radix-4 and approximate (a) radix-64, (b) radix-256, and (c) radix-1024 encoding partial product bits from the approximate high radix encoding. •: partial product bits from the accurate radix-4 encoding inverted MSBs of the partial products. sign factors.

the radix-64, radix-256, and radix-1024 encoding, respectively. In the radix-64 encoding, the bits of B are grouped as in

The following values of the digit are rounded to their nearest power of two: ±1, ±3, ±5, ±6, ±7, ±9, … , ±15, ±17, … , ±31 are rounded to ±4, ±8, ±16, or ±32, while the smallest powers of two, i.e., ±1 and ±2, are rounded to 0 or ±4. o 0 or ±4.

In radix-1024 encoding, the bits of B are grouped as follows:

Similarly, the nonpowers of two are rounded to ±64, ±128, ±256, or ±512, and the smallest powers of two (±1, ±2, ±4, ±8, ±16, ±32) are rounded to 0 or ±64. The encoder’s inputs are the bits b9, b8,…, b0, the approximate radix-1024 digit is∈ {0, ±64, ±128, ±256, ±512}, and the output signals that define  are sign, ×64, ×128, ×256, ×512.

Partial Product Generation

In the proposed hybrid encoding, the n − k MSBs of B are encoded with the accurate radix-4 encoding, while the k LSBs are encoded with an approximate radix-2k encoding. The accurate radix-4 encoder produces the signals defined, whereas the approximate high radix encoder produces the signals. Overall, there is a reduction of k/2 − 1 partial products generated in the multiplication A · B˜.

In Fig. 1, four partial product generators are presented, i.e., the circuit of the accurate radix-4 encoding and the ones of the three approximate high radix encodings discussed. The partial products created from each encoding are shown in Table III. In addition, the three hybrid high radix encodings create the partial product trees shown in Fig. 2. The trees also include the encoding’s correction term (constant terms and sign factors). The implementation of the partial product accumulation can be chosen by the designer. In this paper, an accurate Wallace treeis used to implement the partial product’s sum, whereas the two outputs produced by the Wallace tree are added using a prefix (fast) adder. Overall, the multiplication circuit consists of stages of operand hybrid radix encoding, partial product generation, partial product accumulation, and final addition. The proposed approximate multipliers are named RAD2k , showing the selected approximate high radix encoding, e.g., RAD64, RAD256, and RAD1024.

ADVANTAGES:

  • Accuracy is high
  • Energy efficiency is high
  • Area size is low and
  • Errors are reduced

REFERENCES:

Vasileios Leon , GeorgiosZervakis , DimitriosSoudris, and KiamalPekmestzi, “Approximate Hybrid High Radix Encoding forEnergy-Efficient Inexact Multipliers”, IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, 2018.

About the Author