Approximate computation in digital systems using bit partitioning

Abstract

A computing methodology in digital systems for performing computationally expensive operations while lowering the required computing resources, the power consumed to accomplish the computation, and maximizing the system throughput. Intermediate computations within the operation may be analyzed and those that have low gain values are identified and may be either removed from the computation or calculated with lower precision.

Claims

1. A method for reducing power consumed in processing units used to calculate computationally expensive operations, the method comprising: receiving a dot-product computation to be calculated at a specified number of bits; breaking down the dot-product computation into a plurality of intermediate operations having 1-bit or 2-bit element input vectors; assigning a gain value to each intermediate operation in the plurality of intermediate operations, wherein the gain value assigned to each intermediate operation is based on an analysis of the 1-bit or 2-bit element input vectors; determining a threshold gain value; and reducing the calculation precision for the intermediate operations that do not meet or exceed the threshold gain value.

2. The method of claim 1, wherein the threshold gain value is based on the number of bits at which the dot-product computation is to be calculated.

3. The method of claim 1, wherein the threshold gain value is based on a number of elements in the input vectors in the intermediate operations.

4. The method of claim 1, wherein the threshold gain value is based on a number of bits at which the elements of the input vectors are represented.

5. The method of claim 1, wherein a simple logic AND gate is used to calculate the intermediate operations having 1-bit element vectors.

6. The method of claim 1, wherein a single hardware is used to implement all of the intermediate operations.

7. The method of claim 1, wherein multiple modules are used in parallel to implement the intermediate operations.

8. The method of claim 1, wherein intermediate operations that do not meet or exceed the threshold gain value are either removed from the dot-product computation or calculated at lower precision.

9. The method of claim 1, wherein multiplications between 2-bit elements of input vectors are performed by using adder/subtractor and shifter without using multiplication.

10. An accelerator architecture system comprising: a memory; and a processor coupled to the memory, the processor being configured to: receive a dot-product computation to be calculated at a specified number of bits; break down the dot-product computation into a plurality of intermediate operations having 1-bit or 2-bit element input vectors; assign a gain value to each intermediate operation in the plurality of intermediate operations, wherein the gain value assigned to each intermediate operation is based on an analysis of the 1-bit or 2-bit element input vectors; determine a threshold gain value; and reduce the calculation precision for the intermediate operations that do not meet or exceed the threshold gain value.

11. The system of claim 10, wherein the threshold gain value is based on the number of bits at which the dot-product computation is to be calculated.

12. The system of claim 10, wherein the threshold gain value is based on a number of elements in the input vectors in the intermediate operations.

13. The system of claim 10, wherein the threshold gain value is based on the number of bits at which the elements of the input vectors are represented.

14. The system of claim 10, wherein a simple logic AND gate is used to calculate the intermediate operations having 1-bit element vectors.

15. The system of claim 10, wherein a single hardware is used to implement all of the intermediate operations.

16. The system of claim 10, wherein multiple modules are used in parallel to implement the intermediate operations.

17. The system of claim 10, wherein intermediate operations that do not meet or exceed the threshold gain value are either removed from the dot-product computation or calculated at lower precision.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Example embodiments will be described and explained with additional specificity and detail through the use of the accompanying drawings in which:

(2) FIG. 1 illustrates an exemplary method for reducing power consumed in processing units used to calculate computationally expensive operations;

(3) FIG. 2 illustrates an example of a system implementing a dot-product between two 1-bit vectors using logic AND gates and accurate or approximate adder; and

(4) FIG. 3 illustrates an example of a system implementing a dot-product between two 2-bit vectors without using any multiplier.

DETAILED DESCRIPTION

(5) This disclosure provides a computing methodology in digital systems that, instead of lowering the precision of input data or just throwing away the LSB bits of the result, analytically and intellectually recognizes unimportant internal computations which may mainly affect the eventually discarded LSB bits. By not executing these computations in the first place, computations may be performed faster at lower power consumptions. While this method of computation may impact the accuracy of the result (so the so-called approximate computing), the introduced degradation is both predictable and adjustable as needed. In addition, it introduces a method to perform a multiplication-based computation without using any multiplication operation and just by using addition operations and logical gates.

(6) While the innovation introduced here may be applied to any similar computation, for the sake of simplicity and clarity, the focus herein is placed on the implementation of dot-product operation mainly because most other operations such as vector-by-matrix, matrix-by-matrix, tensor-by-tensor multiplications can be easily expressed as multiple dot product operations running in parallel.

(7) One or more embodiments of the present disclosure may include a method or an accelerator architecture to reduce the power consumed in processing units like accelerators when used to calculate the computationally expensive operations, which may be expressed based on dot product. The accelerator may lower the amount of computation by performing internal computations at lower precisions or not implementing unimportant computations at all with minimum impact on the final result of the computation. The computing methodology may determine the importance of each internal computation and its impact on the result and decide whether to do the computation or not and with what precision.

(8) For example, FIG. 1 illustrates a method for reducing power consumed in processing units used to calculate computationally expensive operations 10. The method may include, at action 12, receiving a dot-product computation to be calculated at a specified number of bits. In some embodiments, the method may include, at action 14, breaking down the dot-product computation or any other computation which can be expressed based on dot-product computation into smaller dot-product computations, or intermediate operations. For example, these intermediate operations may include dot-product computations having vectors with 1 or 2-bit elements. The method may include, at action 16, assigning a gain to each of these intermediate dot product operations determining their impact and importance on the final dot product result. Intermediate operations with low gain values may not have a large impact on the final dot product result and may be either removed from the computation or calculated with lower precision.

(9) In some embodiments, the gain value assigned to each intermediate operation may be based, at least in part, on an analysis of the 1-bit or 2-bit element input vectors. The decision on which term to keep or discard may also consider a resolution of elements in the input vectors, their statistics, the required output precision, the number of elements in each vector, etc.

(10) The gain of each intermediate dot product may depend on the precision (the number of bits) at which the dot product computation may be calculated. If the desired number of bits to represent the final dot product is much smaller than the maximum number of bits required to represent the dot product at maximum accuracy, more intermediate dot products may be removed from the calculation without affecting the output result. Avoiding unimportant computations may increase the speed and throughput of the digital system, while lowering its power consumption.

(11) The method may include, at action 18, determining a threshold gain value. This threshold gain value may be compared to the gain values assigned to each intermediate operation. The method may include, at action 20, reducing the calculation precision for the intermediate operations that do not meet or exceed the threshold gain value. In some embodiments, intermediate operations that do not meet or exceed the threshold gain value may be calculated at a lower precision. In some embodiments, intermediate operations that do not meet or exceed the threshold gain value may be removed from the calculation altogether.

(12) In some embodiments, the accelerator may use a single hardware to implement all the intermediate dot-products with low-precision elements or use multiple modules in parallel to accomplish the computations. Different terms or intermediate dot products may be added or removed from the computations on the fly depending on the desired output accuracy.

(13) In other embodiments, the method of implementing dot product operations based on intermediate low-precision dot products may be used to avoid using costly multipliers when implementing computationally complex operations.

(14) In some embodiments, a simple logic AND gate may be used to implement the multiplications between 1-bit elements.

(15) In some embodiments, the processing system may operate on unsigned numbers while in other embodiments the system may perform dot product on vectors with elements represented as 2's complement or sign-magnitude.

(16) In other embodiments, the approximate computing system may be used to implement computations of applications like deep neural networks and machine learning algorithms that can tolerate imprecise computations and errors at higher efficiencies minimizing the usage of resources and power.

(17) One or more embodiments of the present disclosure may include a computing system. The computing system may consist of a specialized engine or accelerator to perform a dot product operation between two input vectors X and W, each with m elements and producing the scalar output Y. Elements of input vectors X and W may be represented by N.sub.x and N.sub.w bits respectively. When performing error-free computation, the maximum possible value of Y may be equal to 2 to the power of N.sub.x+N.sub.w+log 2(m) having N.sub.x+N.sub.w+log 2(m) bits. The accelerator may reduce the output precision to N.sub.y bits where N.sub.y may be much smaller than N.sub.w+N.sub.w+log 2(m).

(18) In some embodiments, the input vectors may be represented as binary numbers and the dot product operation may be expressed based on the base-2 numeral representations of vectors X and W like:

(19) $Y=X.Math.W\left[\begin{array}{c}{x}_1\\ x_2\\ .Math.\\ x_m\end{array}\right].Math.\left[\begin{array}{c}{w}_1\\ w_2\\ .Math.\\ w_m\end{array}\right]=\left[\begin{array}{c}{\left({\mathrm{xb}}_{\mathrm{Nx}-1}^1,.Math.,{\mathrm{xb}}_1^1,{\mathrm{xb}}_0^1\right)}_2\\ {\left({\mathrm{xb}}_{\mathrm{Nx}-1}^2,.Math.,{\mathrm{xb}}_1^2,{\mathrm{xb}}_0^2\right)}_2\\ .Math.\\ {\left({\mathrm{xb}}_{\mathrm{Nx}-1}^m,.Math.,{\mathrm{xb}}_1^m,{\mathrm{xb}}_0^m\right)}_2\end{array}\right].Math.\left[\begin{array}{c}{\left({\mathrm{wb}}_{\mathrm{Nx}-1}^1,.Math.,{\mathrm{wb}}_1^1,{\mathrm{wb}}_0^1\right)}_2\\ {\left({\mathrm{wb}}_{\mathrm{Nx}-1}^2,.Math.,{\mathrm{wb}}_1^2,{\mathrm{wb}}_0^2\right)}_2\\ .Math.\\ {\left({\mathrm{wb}}_{\mathrm{Nx}-1}^m,.Math.,{\mathrm{wb}}_1^m,{\mathrm{wb}}_0^m\right)}_2\end{array}\right]=\left(2^{\mathrm{Nx}-1}\left[\begin{array}{c}{\mathrm{xb}}_{\mathrm{Nx}-1}^1\\ {\mathrm{xb}}_{\mathrm{Nx}-1}^2\\ .Math.\\ {\mathrm{xb}}_{\mathrm{Nx}-1}^m\end{array}\right]+.Math.+2^1\left[\begin{array}{c}{\mathrm{xb}}_1^1\\ {\mathrm{xb}}_1^2\\ .Math.\\ {\mathrm{xb}}_1^m\end{array}\right]+2^0\left[\begin{array}{c}{\mathrm{xb}}_0^1\\ {\mathrm{xb}}_0^2\\ .Math.\\ {\mathrm{xb}}_0^m\end{array}\right]\right).Math.\left(2^{\mathrm{Nw}-1}\left[\begin{array}{c}{\mathrm{wb}}_{\mathrm{Nw}-1}^1\\ {\mathrm{wb}}_{\mathrm{Nw}-1}^2\\ .Math.\\ {\mathrm{wb}}_{\mathrm{Nw}-1}^m\end{array}\right]+.Math.+2^1\left[\begin{array}{c}{\mathrm{wb}}_1^1\\ {\mathrm{wb}}_1^2\\ .Math.\\ {\mathrm{wb}}_1^m\end{array}\right]+2^0\left[\begin{array}{c}{\mathrm{wb}}_0^1\\ {\mathrm{wb}}_0^2\\ .Math.\\ {\mathrm{wb}}_0^m\end{array}\right]\right)$

(20) Where Y may have at most N.sub.x+N.sub.w+log 2(m) bits in its binary representation. The computation may further be simplified as:

(21) $Y=\underset{i=0}{\overset{\mathrm{Nx}-1}{.Math.}}\underset{j=0}{\overset{\mathrm{Nw}-1}{.Math.}}{2}^{i+j}\stackrel{A}{\stackrel{}{\left[\begin{array}{c}{\mathrm{xb}}_i^1\\ {\mathrm{xb}}_i^2\\ .Math.\\ {\mathrm{xb}}_i^m\end{array}\right].Math.\left[\begin{array}{c}{\mathrm{wb}}_j^1\\ {\mathrm{wb}}_j^2\\ .Math.\\ {\mathrm{wb}}_j^m\end{array}\right]}}=\underset{i=0}{\overset{\mathrm{Nx}-1}{.Math.}}\underset{j=0}{\overset{\mathrm{Nw}-1}{.Math.}}\underset{k=1}{\overset{m}{.Math.}}{2}^{i+j}{\mathrm{xb}}_i^k.Math.{\mathrm{wb}}_j^k=\underset{i=0}{\overset{\mathrm{Nx}-1}{.Math.}}\underset{j=0}{\overset{\mathrm{Nw}-1}{.Math.}}\underset{k=1}{\overset{m}{.Math.}}{2}^{i+j}\stackrel{B}{\stackrel{}{\mathrm{AND}\left({\mathrm{xb}}_i^k,{\mathrm{wb}}_j^k\right)}}$

(22) Where xb.sub.i.sup.k is the ith bits in the binary representation of the kth element of vector X, wb.sub.j.sup.k is the jth bits in the binary representation of the kth element of vector W, and AND is the logical AND function.

(23) In some embodiments, the precision of dot product result Y may be reduced from N.sub.x+N.sub.w+log 2(m) to N.sub.y using a scaling factor and a round(.) function as:

(24) $Y_{Ny}=\mathrm{round}\left(\frac{2^{Ny}}{2^{Nx+Nw+log2\left(m\right)}}{Y}_{Nx+Nw+log2\left(m\right)}\right)=\mathrm{round}\left(\underset{i=0}{\overset{\mathrm{Nx}-1}{.Math.}}\underset{j=0}{\overset{\mathrm{Nw}-1}{.Math.}}\stackrel{C_{\mathrm{ij}}}{\stackrel{}{\frac{2^{\mathrm{Ny}+i+j}}{2^{\mathrm{Nx}+\mathrm{Nw}+\log 2\left(m\right)}}\stackrel{A_{\mathrm{ij}}}{\stackrel{}{\left[\begin{array}{c}{\mathrm{xb}}_i^1\\ {\mathrm{xb}}_i^2\\ .Math.\\ {\mathrm{xb}}_i^m\end{array}\right].Math.\left[\begin{array}{c}{\mathrm{wb}}_j^1\\ {\mathrm{wb}}_j^2\\ .Math.\\ {\mathrm{wb}}_j^m\end{array}\right]}}}}\right)=\mathrm{round}\left(\underset{i=0}{\overset{\mathrm{Nx}-1}{.Math.}}\underset{j=0}{\overset{\mathrm{Nw}-1}{.Math.}}\underset{k=1}{\overset{m}{.Math.}}\frac{2^{\mathrm{Ny}+i+j}}{2^{\mathrm{Nx}+\mathrm{Nw}+\log 2\left(m\right)}}\stackrel{B_{\mathrm{ij}}}{\stackrel{}{\mathrm{AND}\left({\mathrm{xb}}_i^k,{\mathrm{wb}}_j^k\right)}}\right)$

(25) $\frac{2^{Ny}}{2^{Nx+Nw+log2\left(m\right)}},2^{Ny}$

(26) Where in the scaling factor is the maximum value of output Y and 2.sup.Nx+Nw+log2(m) is the maximum value of the result of the dot product.

(27) Since the maximum value of term A.sub.ij in the above equation may be equal to 2.sup.log2(m), the maximum amplitude of the term C.sub.ij may be equal to

(28) $G_{ij}=\frac{2^{\mathrm{Ny}+i+j}}{2^{Nx+Nw}}=2^{Ny-\left(Nx+Nw\right)+i+j},$
showing the importance of each A.sub.ij term in a given dot product computations. The higher the value of G.sub.ij, the higher the importance of the term A.sub.ij in the result of the dot product calculation.

(29) In some embodiments, the dot product between vectors X and W may be calculated approximately by just calculating (or implementing) the first L elements of C.sub.ij terms out of all N.sub.x*N.sub.y terms which has the highest G.sub.ij. Calculating more C.sub.ij terms with the highest G u s may improve the accuracy of the dot product result with the cost of performing more calculations and therefore burning more power in the underlying accelerator. On the other hand, less circuits with less power consumptions may be needed if a smaller number of C.sub.ij are calculated with the drawback of having less accurate dot product result.

(30) The maximum amount of error in the dot product result calculated approximately may be equal to the sum of the G.sub.ij terms not included in the calculation of the dot product. The exact amount of error may depend on the exact values of the vectors and may be equal to the sum of the C.sub.ij values not included in the calculation of the dot product.

(31) Any circuit with any configuration may be used to perform the calculations of A.sub.ij or C.sub.ij. Unimportant A.sub.ij or C.sub.ij terms with small G.sub.ij may be calculated imprecisely using imprecise digital circuits. Circuits used to calculate important C.sub.ij terms may also be configured to perform the calculations imprecisely.

(32) The dot product A.sub.ij happening between two 1-bit vectors may be implemented based on B.sub.ij which may be implemented using the digital AND gates.

(33) In some embodiments, the dot product may be calculated at any given precision based on the terms A.sub.ij, C.sub.ij or B.sub.ij to reach the minimum hardware while all the redundant internal computations have been avoided. The hardware may be implemented using just logic AND gate and adders.

(34) In some accelerators, all C.sub.ij terms may be implemented in the hardware and they may be turned on and off to change the precision of computation on the fly depending on the required accuracy and desired system power consumption.

(35) In some embodiments, there may be a single hardware inside the accelerator implementing all the A.sub.ij, C.sub.ij or B.sub.ij computations. In some other embodiments, multiple hardware may be working together executing these computations in parallel.

(36) In some embodiments, the same procedure may be repeated by breaking input binary vectors into vectors of binary numbers where this time each element of the vector has 2 bits instead of one like:

(37) $Y=\left(2^{\mathrm{Nx}-2}\left[\begin{array}{c}\left({\mathrm{xb}}_{\mathrm{Nx}-1}^1,{\mathrm{xb}}_{\mathrm{Nx}-2}^1\right)\\ \left({\mathrm{xb}}_{\mathrm{Nx}-1}^2,{\mathrm{xb}}_{\mathrm{Nx}-2}^2\right)\\ .Math.\\ \left({\mathrm{xb}}_{\mathrm{Nx}-1}^m,{\mathrm{xb}}_{\mathrm{Nx}-2}^m\right)\end{array}\right]+.Math.+2^0\left[\begin{array}{c}\left({\mathrm{xb}}_1^1,{\mathrm{xb}}_0^1\right)\\ \left({\mathrm{xb}}_1^2,{\mathrm{xb}}_0^2\right)\\ .Math.\\ \left({\mathrm{xb}}_1^m,{\mathrm{xb}}_0^m\right)\end{array}\right]\right).Math.\left(2^{\mathrm{Nw}-2}\left[\begin{array}{c}\left({\mathrm{wb}}_{\mathrm{Nw}-1}^1,{\mathrm{wb}}_{\mathrm{Nw}-2}^1\right)\\ \left({\mathrm{wb}}_{\mathrm{Nw}-1}^2,{\mathrm{wb}}_{\mathrm{Nw}-2}^2\right)\\ .Math.\\ \left({\mathrm{wb}}_{\mathrm{Nw}-1}^m,{\mathrm{wb}}_{\mathrm{Nw}-2}^m\right)\end{array}\right]+.Math.+2^0\left[\begin{array}{c}\left({\mathrm{wb}}_1^1,{\mathrm{wb}}_0^1\right)\\ \left({\mathrm{wb}}_1^2,{\mathrm{wb}}_0^2\right)\\ .Math.\\ \left({\mathrm{wb}}_1^m,{\mathrm{wb}}_0^m\right)\end{array}\right]\right)$$Y=\underset{i=0}{\overset{\mathrm{Nx}-2}{.Math.}}\underset{j=0}{\overset{\mathrm{Nw}-2}{.Math.}}{2}^{i+j}\left[\begin{array}{c}{\left({\mathrm{xb}}_{i+1}^1,{\mathrm{xb}}_i^1\right)}_2\\ {\left({\mathrm{xb}}_{i+1}^2,{\mathrm{xb}}_i^2\right)}_2\\ .Math.\\ {\left({\mathrm{xb}}_{i+1}^m,{\mathrm{xb}}_i^m\right)}_2\end{array}\right].Math.\left[\begin{array}{c}{\left({\mathrm{wb}}_{j+1}^1,{\mathrm{wb}}_j^1\right)}_2\\ {\left({\mathrm{wb}}_{j+1}^2,{\mathrm{wb}}_j^2\right)}_2\\ .Math.\\ {\left({\mathrm{wb}}_{j+1}^m,{\mathrm{wb}}_j^m\right)}_2\end{array}\right]$

(38) This may reduce the dot product operation between the two original vectors X and W into the dot-product operations between multiple vectors with 2-bit elements (operation PO. Similar to other embodiments, when computing output Y at N.sub.y-bit precision, unimportant P.sub.ij terms may be removed from the computation or be computed at lower precision to calculate the approximated output while having more efficient hardware implementation. Moreover, calculation of dot product between vectors with 2-bit elements may be faster and more efficient since they may be implemented without using any multiplication operation and just with adders/subtractors and shifters.

(39) In some embodiments, the elements of input vectors X and W may be represented as 2's complement. In this case, based on the binary representations of these 2's complement elements, the dot product output Y may be written as:

(40) $Y=\left(-2^{\mathrm{Nx}-1}\left[\begin{array}{c}{\mathrm{xb}}_{\mathrm{Nx}-1}^1\\ {\mathrm{xb}}_{\mathrm{Nx}-1}^2\\ .Math.\\ {\mathrm{xb}}_{\mathrm{Nx}-1}^m\end{array}\right]+.Math.+2^1\left[\begin{array}{c}{\mathrm{xb}}_1^1\\ {\mathrm{xb}}_1^2\\ .Math.\\ {\mathrm{xb}}_1^m\end{array}\right]+2^0\left[\begin{array}{c}{\mathrm{xb}}_0^1\\ {\mathrm{xb}}_0^2\\ .Math.\\ {\mathrm{xb}}_0^m\end{array}\right]\right).Math.\left(-2^{\mathrm{Nw}-1}\left[\begin{array}{c}{\mathrm{wb}}_{\mathrm{Nw}-1}^1\\ {\mathrm{wb}}_{\mathrm{Nw}-1}^2\\ .Math.\\ {\mathrm{wb}}_{\mathrm{Nw}-1}^m\end{array}\right]+.Math.+2^1\left[\begin{array}{c}{\mathrm{wb}}_1^1\\ {\mathrm{wb}}_1^2\\ .Math.\\ {\mathrm{wb}}_1^m\end{array}\right]+2^0\left[\begin{array}{c}{\mathrm{wb}}_0^1\\ {\mathrm{wb}}_0^2\\ .Math.\\ {\mathrm{wb}}_0^m\end{array}\right]\right)$
Which may be written as:

(41) $Y=\stackrel{D}{\stackrel{}{2^{\mathrm{Nx}+\mathrm{Nw}-2}\left[\begin{array}{c}{\mathrm{xb}}_{\mathrm{Nx}-1}^1\\ {\mathrm{xb}}_{\mathrm{Nx}-1}^2\\ .Math.\\ {\mathrm{xb}}_{\mathrm{Nx}-1}^m\end{array}\right].Math.\left[\begin{array}{c}{\mathrm{wb}}_{\mathrm{Ny}-1}^1\\ {\mathrm{wb}}_{\mathrm{Ny}-1}^2\\ .Math.\\ {\mathrm{wb}}_{\mathrm{Ny}-1}^m\end{array}\right]}}-\underset{j=0}{\overset{\mathrm{Nw}-2}{.Math.}}\stackrel{E_i}{\stackrel{}{2^{\mathrm{Nx}+j-1}\left[\begin{array}{c}{\mathrm{xb}}_{\mathrm{Nx}-1}^1\\ {\mathrm{xb}}_{\mathrm{Nx}-1}^2\\ .Math.\\ {\mathrm{xb}}_{\mathrm{Nx}-1}^m\end{array}\right].Math.\left[\begin{array}{c}{\mathrm{wb}}_j^1\\ {\mathrm{wb}}_j^2\\ .Math.\\ {\mathrm{wb}}_j^m\end{array}\right]}}-\underset{i=0}{\overset{\mathrm{Nx}-2}{.Math.}}\stackrel{F_j}{\stackrel{}{2^{\mathrm{Nw}+i-1}\left[\begin{array}{c}{\mathrm{xb}}_i^1\\ {\mathrm{xb}}_i^2\\ .Math.\\ {\mathrm{xb}}_i^m\end{array}\right].Math.\left[\begin{array}{c}{\mathrm{wb}}_{\mathrm{Nw}-1}^1\\ {\mathrm{wb}}_{\mathrm{Nw}-1}^2\\ .Math.\\ {\mathrm{wb}}_{\mathrm{Nw}-1}^m\end{array}\right]}}+\underset{i=0}{\overset{\mathrm{Nx}-2}{.Math.}}\underset{j=0}{\overset{\mathrm{Nw}-2}{.Math.}}{2}^{i+j}\stackrel{H_{\mathrm{ij}}}{\stackrel{}{\left[\begin{array}{c}{\mathrm{xb}}_i^1\\ {\mathrm{xb}}_i^2\\ .Math.\\ {\mathrm{xb}}_i^m\end{array}\right].Math.\left[\begin{array}{c}{\mathrm{wb}}_j^1\\ {\mathrm{wb}}_j^2\\ .Math.\\ {\mathrm{wb}}_j^m\end{array}\right]}}$
Its precision can be reduced to N.sub.y bits as:

(42) $y_{Ny}=\mathrm{round}\stackrel{D}{(\stackrel{}{\frac{2^{\mathrm{Nx}-\mathrm{Nw}-2}}{2^{\mathrm{Nx}+\mathrm{Nw}+\log 2\left(m\right)}}\left[\begin{array}{c}{\mathrm{xb}}_{\mathrm{Nx}-1}^1\\ {\mathrm{xb}}_{\mathrm{Nx}-1}^2\\ .Math.\\ {\mathrm{xb}}_{\mathrm{Nx}-1}^m\end{array}\right].Math.\left[\begin{array}{c}{\mathrm{wb}}_{\mathrm{Ny}-1}^1\\ {\mathrm{wb}}_{\mathrm{Ny}-1}^2\\ .Math.\\ {\mathrm{wb}}_{\mathrm{Ny}-1}^m\end{array}\right]}}-\underset{j=0}{\overset{\mathrm{Nw}-2}{.Math.}}\stackrel{E_i}{\stackrel{}{\frac{2^{\mathrm{Nx}+j-1}}{2^{\mathrm{Nx}+\mathrm{Nw}+\log 2\left(m\right)}}\left[\begin{array}{c}{\mathrm{xb}}_{\mathrm{Nx}-1}^1\\ {\mathrm{xb}}_{\mathrm{Nx}-1}^2\\ .Math.\\ {\mathrm{xb}}_{\mathrm{Nx}-1}^m\end{array}\right].Math.\left[\begin{array}{c}{\mathrm{wb}}_j^1\\ {\mathrm{wb}}_j^2\\ .Math.\\ {\mathrm{wb}}_j^m\end{array}\right]}}-\underset{i=0}{\overset{\mathrm{Nx}-2}{.Math.}}\stackrel{F_j}{\stackrel{}{\frac{2^{\mathrm{Nw}+i-1}}{2^{\mathrm{Nx}+\mathrm{Nw}+\log 2\left(m\right)}}\left[\begin{array}{c}{\mathrm{xb}}_i^1\\ {\mathrm{xb}}_i^2\\ .Math.\\ {\mathrm{xb}}_i^m\end{array}\right].Math.\left[\begin{array}{c}{\mathrm{wb}}_{\mathrm{Nw}-1}^1\\ {\mathrm{wb}}_{\mathrm{Nw}-1}^2\\ .Math.\\ {\mathrm{wb}}_{\mathrm{Nw}-1}^m\end{array}\right]}}+\underset{i=0}{\overset{\mathrm{Nx}-2}{.Math.}}\underset{j=0}{\overset{\mathrm{Nw}-2}{.Math.}}\stackrel{H_{\mathrm{ij}}}{\stackrel{}{\frac{2^{i+j}}{2^{\mathrm{Nx}+\mathrm{Nw}+\log 2\left(m\right)}}\left[\begin{array}{c}{\mathrm{xb}}_i^1\\ {\mathrm{xb}}_i^2\\ .Math.\\ {\mathrm{xb}}_i^m\end{array}\right].Math.\left[\begin{array}{c}{\mathrm{wb}}_j^1\\ {\mathrm{wb}}_j^2\\ .Math.\\ {\mathrm{wb}}_j^m\end{array}\right]}}$

(43) In some embodiments, the dot product between two vectors X and W with elements represented as 2's complement may be implemented approximately by just calculating those F) and/or H.sub.ij elements which has the highest impacts on the dot product results. More or less elements may be included in the computation to reach higher or lower precision respectively. The exact number of terms included in the computation may depend on the required precision, existing resources on the hardware, power budget and the distribution of signals X and W.

(44) The importance of each E.sub.i element may be equal to

(45) 0$\frac{2^{Nx+j-1}}{2^{Nx+NW}},$
the importance of element F.sub.j may be equal to

(46) $\frac{2^{\mathrm{Nw}+i-1}}{2^{Nx+Nw}},$
and the importance of each H.sub.ij element may be equal to

(47) $\frac{2^{i+j}}{2^{Nx+Nw}}$
on the final dot product result. Different numbers of elements may be removed from E.sub.j, F.sub.j, or H.sub.ij to reduce the amount of computation required for the calculation of the dot product without a remarkable impact on the result accuracy.

(48) The error on the calculated dot product may be computed by adding up the omitted terms per each given set of input signals.

(49) Each term of D, E.sub.i, F.sub.j, H.sub.ij themselves may be calculated with imprecise hardware at lower precisions or may be calculated precisely. These terms may also be implemented using the AND gates similar to the computations performed for dot product between unsigned vectors.

(50) The term D may be calculated at its highest precision since it does computation on MSB bits of vectors X and W.

(51) Any other operation which can be expressed as a set of dot product operations may be implemented approximately using the method explained in these embodiments.

(52) Operations like convolution, vector-by-matrix, or matrix-by-matrix multiplication in applications like deep neural networks and machine learning algorithms which can tolerate imprecise computations can be expressed as dot products and implemented approximately as explained in this disclosure.

(53) Deciding which terms to include in the computation and which terms to omit may depend on the statistics of the data in the X and W vectors and the precision (number of bits) at which these vectors are represented at. For example, if X elements has 4 bits and W elements has 8 bits, it may be better to omit only those terms which do computations on LSB bits of the signal W which has been represented with a higher number of bits.

(54) FIG. 2 illustrates an example of a computing system and methodology for performing a dot product between two vectors X and W each with 1-bit elements. Element-wise multiplications between two single bit elements of x and w may be implemented using a logic AND gate 201. The results of multiplication which are also single bits may then be added together using an adder 202. The adder 202 may be an accurate adder producing the result 203 with log 2(m) bit precision or it may be an approximate adder calculating LSB bits of the summation results with less precision. In some other embodiments, the adder may not calculate the LSB bits of the summation results at all since they may be thrown away later when calculating the dot products between original multi-bit vectors.

(55) FIG. 3 illustrates an example of a computing system and methodology for performing a dot product between two vectors X and W each with 2-bit elements without using any multiplication operation. Element-wise multiplications between two 2-bit numbers may be implemented by first generating two signals from one of the input elements, where one of the signals is the input itself 301 and the other one is twice the input element, 302, which can be implemented using shifters. Then both the signals may be given to the adder/subtractor module 304 where the other element 303 would determine how the two inputs 301 and 302 may be combined together to generate the result of multiplication between two input elements. The results of multiplication, which may then be added together using an adder 305. The adder 305 may be an accurate adder producing the result 306 with log 2(m)+4 bit precision or it may be an approximate adder calculating LSB bits of the summation results with less precision. In some other embodiments, the adder may not calculate the LSB bits of the summation results at all since they may be thrown away later when calculating the dot products between original multi-bit vectors at lower precision.

(56) In some embodiments, multiple of modules shown in FIG. 2 an/or FIG. 3 may be implemented and work together to implement more complex computations like convolution or vector-by-matrix, matrix-by-matrix, or tensor-by-tensor multiplications.

(57) In some embodiments, the approximate adder may be implemented by keeping the maximum number of bits the summation result may have fixed and smaller than the maximum number of bits the maximum summation result may have. Whenever the summation result becomes larger than what can be represented by the adder, only the MSBs of the result may be kept while LSB bits may be discarded.

(58) In accordance with common practice, the various features illustrated in the drawings may not be drawn to scale. The illustrations presented in the present disclosure are not meant to be actual views of any particular apparatus (e.g., device, system, etc.) or method, but are merely example representations that are employed to describe various embodiments of the disclosure. Accordingly, the dimensions of the various features may be arbitrarily expanded or reduced for clarity. In addition, some of the drawings may be simplified for clarity. Thus, the drawings may not depict all of the components of a given apparatus (e.g., device) or all operations of a particular method.

(59) Terms used herein and especially in the appended claims (e.g., bodies of the appended claims) are generally intended as open terms (e.g., the term including should be interpreted as including, but not limited to, the term having should be interpreted as having at least, the term includes should be interpreted as includes, but is not limited to, etc.).

(60) Additionally, if a specific number of an introduced claim recitation is intended, such an intent will be explicitly recited in the claim, and in the absence of such recitation no such intent is present. For example, as an aid to understanding, the following appended claims may contain usage of the introductory phrases at least one and one or more to introduce claim recitations. However, the use of such phrases should not be construed to imply that the introduction of a claim recitation by the indefinite articles a or an limits any particular claim containing such introduced claim recitation to embodiments containing only one such recitation, even when the same claim includes the introductory phrases one or more or at least one and indefinite articles such as a or an (e.g., a and/or an should be interpreted to mean at least one or one or more); the same holds true for the use of definite articles used to introduce claim recitations.

(61) In addition, even if a specific number of an introduced claim recitation is explicitly recited, it is understood that such recitation should be interpreted to mean at least the recited number (e.g., the bare recitation of two recitations, without other modifiers, means at least two recitations, or two or more recitations). Furthermore, in those instances where a convention analogous to at least one of A, B, and C, etc. or one or more of A, B, and C, etc. is used, in general such a construction is intended to include A alone, B alone, C alone, A and B together, A and C together, B and C together, or A, B, and C together, etc. For example, the use of the term and/or is intended to be construed in this manner.

(62) Further, any disjunctive word or phrase presenting two or more alternative terms, whether in the summary, detailed description, claims, or drawings, should be understood to contemplate the possibilities of including one of the terms, either of the terms, or both terms. For example, the phrase A or B should be understood to include the possibilities of A or B or A and B.

(63) Additionally, the use of the terms first, second, third, etc., are not necessarily used herein to connote a specific order or number of elements. Generally, the terms first, second, third, etc., are used to distinguish between different elements as generic identifiers. Absence a showing that the terms first, second, third, etc., connote a specific order, these terms should not be understood to connote a specific order. Furthermore, absence a showing that the terms first, second, third, etc., connote a specific number of elements, these terms should not be understood to connote a specific number of elements. For example, a first widget may be described as having a first side and a second widget may be described as having a second side. The use of the term second side with respect to the second widget may be to distinguish such side of the second widget from the first side of the first widget and not to connote that the second widget has two sides.

(64) The foregoing description, for purpose of explanation, has been described with reference to specific embodiments. However, the illustrative discussions above are not intended to be exhaustive or to limit the invention as claimed to the precise forms disclosed. Many modifications and variations are possible in view of the above teachings. The embodiments were chosen and described to explain practical applications, to thereby enable others skilled in the art to utilize the invention as claimed and various embodiments with various modifications as may be suited to the particular use contemplated.