CN113312021B - Approximate hybrid divider circuit based on array and logarithmic divider - Google Patents

Abstract

The present invention provides an approximate hybrid divider circuit based on an array divider and a logarithmic divider, wherein the improved array divider module in the circuit is used to ensure the accuracy requirement, and the logarithmic divider module is used to achieve the improvement in hardware performance. The circuit adopts a truncation method, proposes the concept of approximate depth, and configures the operands into bit widths of different lengths to be allocated to the array divider and the logarithmic divider, so that different accuracy and hardware resource requirements can be configured. The user can select the most suitable truncation method (i.e., the appropriate approximate depth) according to the requirements, and while meeting the requirements, other unnecessary consumption is reduced as much as possible. Compared with the previously proposed approximate array divider, the circuit uses fewer hardware resources, greatly reduces the unit cost, and the accuracy loss is within the range of 10 ^‑3 to 10 ^‑4 . Compared with the logarithmic divider, the accuracy is greatly improved.

Description

Approximate hybrid divider circuit based on array and logarithmic divider

Technical field:

The invention relates to the field of approximate circuit design, and in particular to an approximate hybrid divider circuit based on an array and a logarithmic divider.

Background technology:

As the demand for higher computing speeds in digital systems continues to grow, along with the accompanying requirements for low power/high energy efficiency in mobile and other non-mobile devices, a new source of computing efficiency is urgently needed to design more efficient (faster, lower power) computing platforms.

Approximate computing has attracted widespread attention as a low-power design method. Its idea comes from the tolerance of applications to inaccurate results. The core principle is to perform effective calculations by producing results that are good enough or of sufficient quality. This effective calculation allows designers to use this error tolerance to add a new dimension to design optimization, in which calculation accuracy is used to reduce power consumption and design complexity. The difference between approximate computing and precise computing is that precise computing will cause the computing system to require higher power and hardware complexity, while in the approximate computing method, system performance is improved and hardware complexity is reduced at the cost of accuracy, and this energy saving is very significant.

Existing precise dividers have many disadvantages such as long critical path, large delay, high power consumption, large area, etc. However, for some specific applications (such as image processing, computer vision, etc.), precise results are not required, and there is a certain tolerance for the output. In this case, it is necessary to design a new type of high-speed, low-power and small-area approximate divider to replace the precise divider to improve the overall performance of the system.

Logarithmic operations can convert complex division operations into simple subtraction operations. Compared with traditional precise array dividers, it greatly shortens the critical path, reduces latency, and greatly reduces the consumption of hardware resources, greatly reducing power consumption. However, its disadvantage is that its calculation accuracy is very poor, especially for operands with large bit widths, the error value is larger. In order to combine the advantages of both, an approximate hybrid divider circuit structure is designed, which is faster, smaller in area, and lower in power consumption than a precise divider; compared with using logarithmic operations entirely, its calculation accuracy is guaranteed.

Summary of the invention:

Purpose of the invention: To solve the above technical problems, the present invention proposes an approximate hybrid divider circuit based on an array and a logarithmic divider, which has a small area, high speed and low power consumption.

Technical solution: To achieve the above technical effects, the technical solution provided by the present invention is:

An approximate hybrid divider circuit based on an array and a logarithmic divider is characterized in that it includes an improved leading bit detection technology, a truncation module for controlling the accuracy of the output of an adjustment circuit and hardware indicators, an optimized precise array divider structure, and a logarithmic divider module using the improved leading bit detection technology; the divider is a divider with a dividend of 16 bits and a divisor of 8 bits, and the final quotient result is 16 bits. The concept of approximate depth is introduced in the design and is defined as h. The depth is selected according to different requirements of the user for specific accuracy, and the range is 8 to 16. The 16-hbits high bits of the quotient result are generated by the optimized precise array divider module; the h bits low bits of the quotient result are generated by the inaccurate logarithmic divider module; wherein,

The truncation module is the input that controls the approximation depth h. Different values of the truncation module determine the allocation of operands, which can be configured to meet different precision and hardware resource requirements. By selecting the appropriate approximation depth value, a good compromise between computational accuracy and hardware performance can be achieved. The dividend of the operand is truncated by the selected approximation depth h value, and the high bits of the 16-h bits are allocated to the precise array divider module, and the low bits of the h bits are allocated to the logarithmic divider.

The precise array divider module is composed of multiple precise array divider units, each of which is composed of a one-bit full subtractor and a data selector. The quotient value is determined by the positive or negative of the partial remainder obtained by subtracting each row, and the obtained quotient value is fed back to the upper level to control whether the partial remainder enters the calculation of the next quotient value. Each row generates a quotient value, and the operation is performed in sequence to finally obtain the high-order quotient value of 16-h bits and the final remainder of 8 bits.

The final remainder of 8 bits obtained by the precise array divider is input in series with the low-order operand of hbits assigned to the logarithmic divider by the truncation module as the dividend of the logarithmic divider. The logarithmic divider module first detects the leading bit of the operand to determine the position of its most significant "1", and then converts the operand from binary to logarithm. The conversion of division to logarithm is equivalent to subtraction. The result of subtraction is the logarithm of the quotient value, which is then converted from logarithm to binary. Finally, by detecting the position of the leading "1", a simple shift operation is performed on the result to obtain the low-order quotient value of h bits. Finally, the high-order quotient value of 16-h bits generated by the precise array divider and the low-order quotient value of hbits generated by the logarithmic divider are output in series to obtain the final quotient value result.

The present invention also proposes a design method of an approximate hybrid divider based on a restoration array and a logarithmic divider, which is characterized by comprising the steps of:

(1) Construct an approximate hybrid divider;

(2) Assume that the dividend is X with a bit width of 16 bits and the divisor is Y with a bit width of 8 bits. The operand is truncated by approximating the depth h, and the 16-h bits of high bits are assigned to the precise array divider, and the h bits of low bits are assigned to the logarithmic divider. The dividend of the precise array divider module is defined as X ₁ with a bit width of 16-h bits, the final remainder generated is defined as R ₁ with a bit width of 8 bits, and the high-order quotient value generated is defined as Q ₁ with a bit width of 16-h bits; the part of the dividend assigned to the logarithmic divider is defined as X ₂ with a bit width of h bits, and the low-order quotient value generated is defined as Q ₂ with a bit width of h bits; the series output of Q ₁ and Q ₂ is the final quotient value, defined as Q, with a bit width of 16 bits.

(3) In the precise array divider, a 16-h bits operand requires 16-h row units. Each row unit performs the subtraction of the dividend and the divisor, i.e., _X1 -Y, from high to low. Each row unit generates a 1-bit high-order quotient value and feeds it back to the row unit, and controls the output of its partial remainder through the data selector. If the quotient value obtained by the row is "1", the data selector selects the partial remainder to be input to the next row; if the quotient value obtained by the row is "0", the data selector selects _X1 to be input to the next row. The expression of the high-order quotient value _Q1 obtained by the precise array divider is:

(4) Assume that T = R ₁ × 2 ^h + X ₂ , and its bit width is equal to 8 + h bits. Take T as the dividend input of the logarithmic divider, and the output is still Y. First, the leading bit of the operand must be detected to determine the position of its most significant bit "1", which is represented by k ₁ and k _2. Then, the operand is converted from binary to logarithmic. The operand can be written in the form of the following expression: Among them, the bit width of _k1 is 4 bits, and the bit width of _k2 is 3 bits. _m1 and _m2 are the mantissa parts, and the range is [0, 1). In this way, the expression of the low-order quotient value generated by the logarithmic divider is: Convert it from binary to logarithm: log ₂ Q ₂ =k ₁ -k ₂ +log ₂ (1+m ₁ )-log ₂ (1+m ₂ ); in mathematical operations, when 0≤m＜1, log ₂ (1+m)≈m, and substitute it into the previous expression to obtain the approximate expression of the low-order quotient value Q ₂ : log ₂ Q ₂ ≈k ₁ -k ₂ +m ₁ -m ₂ ; It can be seen from the expression that only a simple subtraction operation is required to obtain the approximate logarithm value of the low-order quotient value; then convert the calculated logarithm value to binary to obtain the expression of the low-order quotient value: Finally, the obtained _Q1 and _Q2 are output in series to obtain the final quotient value Q.

The design method of the approximate hybrid divider based on the recovery array and the logarithmic divider is further described. The precise array divider module is different from the traditional array divider. For a 16/8 divider, instead of fixing 8 precise array divider units in each row, the number of redundant precise array divider units can be reduced according to the different approximate depths, thereby reducing the consumption of hardware resources and further reducing power consumption. The specific implementation steps are as follows:

(1) Perform leading bit detection on the divisor Y to detect the position information k of the most significant "1";

(2) By using the selected approximate depth value, the dividend bit width assigned to the precise array divider module is determined to be 16-h bits, and the (16-h)/(16-h+1) array structure is used to calculate the precise high-order quotient value.

(3) Based on the leading bit information k of the divisor obtained in step (1) and the array structure in step (2), if k>16-h+1, the divisor Y is truncated from the highest bit to (16-h+1) bits as the divisor; if k<16-h+1, the divisor Y is truncated from the lowest bit to (16-h+1) bits as the divisor.

The advantage of this method is that it can effectively reduce the consumption of redundant hardware resources, further reduce power consumption, and improve system performance. At the same time, the result is still an accurate value without any error.

The leading bit detection algorithm described in the design method of the approximate hybrid divider based on the recovery array and the logarithmic divider is different from the traditional priority encoder. The leading bit detection technical steps in the design method are as follows:

(1) The bit width of the data to be detected is defined as 8 bits (all binary numbers), and the data is defined as A = a ₇ a ₆ a ₅ a ₄ a ₃ a ₂ a ₁ a ₀ ; it can be seen that the maximum output bit width of the data for the 8-bit leading bit detection is 3 bits, which is defined as B = b ₂ b ₁ b ₀ ;

(2) Compare a ₇ a ₆ a ₅ a ₄ with 0000. If they are equal, b ₂ = 0; otherwise, b ₂ = 1.

(3) According to the comparison result of step (2), if b ₂ = 0, then a ₃ a ₂ is compared with 00; if b ₂ = 1, then a ₇ a ₆ is compared with 00; if the comparison result is equal, then b ₁ = 0; if not equal, then b ₁ = 1;

(4) According to the comparison results of steps (2) and (3), if b ₂ b ₁ = 00, then a ₁ is compared with 0; if b ₂ b ₁ = 01, then a ₃ is compared with 0; if b ₂ b ₁ = 10, then a ₅ is compared with 0; if b ₂ b ₁ = 11, then a ₇ is compared with 0; if the comparison results are equal, then b ₀ = 0; if not equal, then b ₀ = 1;

(5) Based on the comparison results of steps (2), (3), and (4), the position of the final leading bit "1" is obtained.

Description of the drawings:

FIG1 is a diagram showing the overall hardware implementation of an approximate hybrid divider based on a recovery array and a logarithmic divider;

Fig. 2 is a circuit diagram of a precision array divider unit;

FIG3 is a circuit diagram of an 8/4 precision array divider;

FIG4 is a block diagram of the operation realization of a logarithmic divider;

FIG5 is a schematic diagram of the improved array structure when h=14 in the design;

FIG6 is a hardware implementation diagram of a 16/8-bit approximate mixed divider with h=14.

FIG. 7 is a data flow diagram of an 8/4-bit approximate mixed divider with h=6.

Specific implementation method:

Take h=14 as an example, that is, the upper 2 bits of the quotient result are precisely designed, while the lower 14 bits are approximately designed for a 16/8 bit approximate mixed divider. The technical solution of the present invention is further described in detail in conjunction with the accompanying drawings:

As shown in Figure 6, the hardware implementation diagram of the approximate hybrid divider based on the recovery array and the logarithmic divider of the present invention when h=14 includes an optimized precise array divider module, a leading bit detection module, a truncation module for controlling the accuracy of the adjustment circuit output and the hardware indicators, a binary to logarithmic module, a subtraction unit module and a logarithmic to binary module.

The optimized precise array divider module only uses 6 precise array divider units, while the traditional precise divider requires 16. The redundancy precise array divider units are marked with × in Figure 6. First, the leading bit of the divisor is detected to obtain the position information of its most significant bit k ₂ . Since the high 2 bits of the dividend are allocated to the precise array divider, only 2/3 bits of the precise array are needed to obtain the precise result. The obtained value of k ₂ is compared with 3. If it is greater than 3, 3 bits of the divisor are selected from the high position as the divisor; if it is less than 3, 3 bits of the divisor are selected from the low position as the divisor. Through the operation, a 2-bit precise high-order quotient value and a 3-bit remainder are generated. However, since the dividend is 2 bits, the significant bits of the remainder are only the last two bits, and the first bit is 0.

Then the obtained 2-bit effective remainder and the 14-bit dividend assigned to the logarithmic divider are input in series as the dividend of the logarithmic divider. Then the leading bit of the dividend is detected to obtain the position information of its most significant bit k ₁ , and the two operands are converted from binary to logarithmic to obtain m ₁ and m _2. Next, k ₁ and m ₁ are connected in series, k ₂ and m ₂ are connected in series, k ₁ and k ₂ are used as the integer part, m ₁ and m ₂ are used as the decimal part, and the subtraction operation k ₁ +m ₁ -k ₂ +m ₂ is performed to obtain the difference result, and the result is added by 1, and then a simple shift operation is performed, shifting k ₁ -k ₂ bits. If k ₁ -k ₂ > 0, a left shift is performed; if k ₁ -k ₂ < 0, a right shift is performed. Finally, the 14-bit approximate low-order quotient value is obtained.

The 2-bit accurate high-order quotient value generated by the accurate array divider and the 14-bit approximate low-order quotient value generated by the logarithmic divider are connected in series and output to obtain the final quotient result.

The present invention also provides an application of an 8/4 approximate mixed divider. Figure 7 provides a data flow chart when h=6.

The above is only a description of the preferred embodiment of the present invention. For those skilled in the art, other advantages and variations can be easily associated with the above embodiment. Therefore, the present invention is not limited to the above embodiment, which is only used as an example to provide a detailed and exemplary description of one form of the present invention. Without departing from the scope of the purpose of the present invention, the usual changes and substitutions made by those skilled in the art within the scope of the technical solution of the present invention should be included in the protection scope of the present invention.

Claims (4)

1. The mixed approximate divider circuit based on the array divider and the logarithmic divider is characterized by comprising a cut-off module for controlling and adjusting the accuracy and hardware index of the circuit output, an optimized accurate array divider module and a logarithmic divider module using an improved leading bit detection technology; the divider circuit is a divider with divisor 16bits and divisor 8bits, the final quotient result is 16bits, the 16-h bits high bit of the quotient result of the divider circuit is generated by the precise array divider module, h is approximate depth, and the range is 8-16; h bits low bits of the quotient result of the divider circuit are generated by the logarithmic divider module;

The truncation module is used for controlling the input of the approximate depth h, and the distribution condition of operands is determined by the difference of values of the truncation module, so that the truncation module is configured into different precision and hardware resource requirements, and a good compromise between the calculation precision and the hardware performance is achieved by selecting a proper approximate depth value; cutting off the divisor of the operand by the selected approximate depth h value, distributing the high order of 16-h bits to the precise array divider module, and distributing the low order of h bits to the logarithmic divider module;

The precise array divider module is formed by combining a plurality of precise array divider units, and each precise array divider unit is formed by a one-bit full-dimmer and a data selector; the accurate array divider module judges the quotient value of the corresponding bit through the positive and negative of the partial remainder obtained by subtracting each row, and feeds back the obtained quotient value to the upper stage to control whether the partial remainder enters the operation of the next quotient value; generating a quotient value by each row of the precise array divider units, and sequentially operating to finally obtain a high-order quotient value of 16-h bits and a final remainder of 8 bits;

Inputting the final remainder of 8bits obtained by the precise array divider and the low-order operand of hbits distributed to the logarithmic divider module by the truncation module in series as the dividend of the logarithmic divider module; the logarithmic divider module firstly detects leading bits of operands, judges the position of the most effective 1, then carries out binary-to-logarithmic conversion on the operands, realizes the operation of converting division into logarithms through subtraction operation, namely the logarithm of quotient values, then carries out the conversion of the logarithm to binary values on the subtraction operation, finally carries out shift operation on the binary subtraction operation result through the detected position of the leading 1, namely the low-order quotient value of hbits, and finally carries out serial output on the high-order quotient value of 16-hbits generated by the precise array divider module and the low-order quotient value of h bits generated by the logarithmic divider module, thus obtaining the final quotient value result.

2. The design method of the approximate hybrid divider based on the recovery array and the logarithmic divider is characterized by comprising the following steps:

(1) Constructing an approximate hybrid divider circuit as defined in claim 1;

(2) Assuming that the dividend is X, the bit width is 16bits, the divisor is Y, and the bit width is 8bits; truncating an operand by an approximate depth h, distributing 16-h bits high bits to the precise array divider module, and distributing h bits low bits to the logarithmic divider module; the divisor of the precise array divider module is defined as X1, the bit width is 16-h bits, the generated final remainder is defined as R1, the bit width is 8bits, the generated high-order quotient is defined as Q1, and the bit width is 16-h bits; the partial dividend allocated to the logarithmic divider module is defined as X2, the bit width is h bits, the generated low-order quotient value is defined as Q2, and the bit width is hbits; the final quotient value is obtained through the serial output of Q1 and Q2, and is defined as Q, and the bit width is 16bits;

(3) In the precise array divider module, 16-h bit operands require 16-h row units, and each row unit performs subtraction of divisors and divisors, namely X1-Y, and sequentially extends from high order to low order; each row unit generates a high-order quotient value of 1bit, and feeds back the high-order quotient value to the row unit, and the output of partial remainder is controlled through a data selector; if the line obtains a quotient value of 1, the data selector selects a part of remainder to be input to the next line; if the quotient obtained by the row is 0, the data selector selects X1 to be input to the next row; the expression of the high quotient Q1 obtained by the precise array divider module is as follows:

(4) Let t=r ₁×2^h+X₂, the bit width of T be equal to 8+h bits; taking T as the dividend input of the logarithmic divider module, the divisor output still being Y; firstly, leading bit detection is carried out on an operand, and the position of the most significant bit '1' is judged, and is expressed by k1 and k 2; the operands are then binary-to-logarithmic converted, and the operands may be written first in the form of the following expression:

wherein k1 has a bit width of 4bits, k2 has a bit width of 3bits, m1 and m2 are mantissa portions, and the range is [0, 1); thus, the logarithmic divider module generates a low quotient having the following expression:

Binary to logarithmic conversion of Q ₂: log2 q2=k1-k2+log2 (1+m1) -log2 (1+m2); when 0.ltoreq.m < 1, log2 (1+m). Apprxeq.m is substituted into the previous expression, the expression of the approximate low quotient Q2 can be obtained: log2 q2=k1-k2+m1-m 2; then log2Q2 is converted from logarithm to binary number, and the low-order quotient expression is obtained as follows:

and finally, outputting the obtained Q1 and Q2 in series to obtain a final quotient value Q.

3. The method for designing an approximate hybrid divider based on a recovery array and logarithmic divider according to claim 2, wherein the exact array divider module reduces the number of exact array divider units redundant therein according to the difference of approximate depths, and the specific implementation steps are as follows:

leading bit detection is carried out on the divisor Y, and the position information k of the most effective '1' is detected;

Determining that the divisor bit width allocated to the precise array divider module is 16-h bits by the selected approximate depth value, and calculating a precise high-order quotient by using the array structure of (16-h)/(16-h+1);

according to the position information k and the array structure, if k is more than 16-h+1, the divisor Y is from the highest bit, and the (16-h+1) bit is intercepted as the divisor; if k < 16-h+1, then the divisor Y intercepts the (16-h+1) bits from the lowest order as the divisor.

4. The method for designing an approximate hybrid divider based on a recovery array and a logarithmic divider of claim 3, wherein the preamble detection specifically comprises:

Defining the detected data bit width as 8bits, and defining the data as a=a7a6a6a5a4a3a2a1a0; the maximum data output bit width of the 8bits preamble bit detection is 3bits, which is defined as b=b2b1b0;

comparing a7a6a5a4 with 0000, and if equal, b2=0; otherwise, b2=1;

If b2=0, then a3a2 is next compared to 00; if b2=1, then a7a6 is next compared to 00; if the comparison results are equal, b1=0; if not, b1=1;

If b2b1=00, then a1 is next compared to 0; if b2b1=01, then a3 is next compared to 0; if b2b1=10, then a5 is next compared to 0; if b2b1=11, then a7 is next compared to 0; if the comparison results are equal, b0=0; if not, b0=1;

based on the result of b2b1b0, the position of the final leading bit "1" is obtained.