KR20180122021A - How to operate a digital computer to reduce computational complexity associated with dot products between large vectors - Google Patents

Abstract

The present invention includes a method of operating a data processing system to calculate an approximation to a scalar product between a first vector and a second vector, wherein each vector is characterized by N components. The method includes the steps of replacing the first vector with a third vector, which is a pyramidal integer vector characterized by an integer K, which is the sum of the N components and the N component excerpt values, and a scalar multiplication between the first vector and the second vector And computing a scalar product of the second vector and the third vector to provide an approximation for the second vector. The step of calculating the scalar product of the second vector and the third vector may be performed by K addition and 1 floating point multiplication.

Description

How to operate a digital computer to reduce computational complexity associated with dot products between large vectors

This application claims priority to U.S. Provisional Application No. 2016901146, filed on March 29, 2016, incorporated herein by reference.

Digital signal processing is becoming common. For example, signal filters such as low pass filters, band pass filters, and high pass filters are implemented by digitizing an analog signal to generate a sequence of digital values. Here, the digital values are processed through a finite impulse filter, where the scalar product or " dot " product of the vector of signal values and the vector of filter coefficients provides a digital value representing the hourly filtered signal.

The scalar product of two N component vectors, A and B, is defined as:

.

.

Where A _i and B _i are the i-th components of A and B, respectively, and N is the number of components in each vector. The computational workload inherent in performing these operations is N multiplications and N-1 additions. The operation load for multiplication is considerably larger than the operation load for addition. In simple cases such as integer multiplication and addition, the multiplication is performed by N additions and N-1 shifts. In more complex cases such as floating point numbers, the computational load is much larger. Therefore, when an application requires a scalar multiplication of two large vectors, the computational workload can place practical constraints on the underlying filter or other models.

For example, the quality of a digital filter typically increases with the size of the associated vector. A bandpass filter with 50 filter coefficients has significantly less out-of-band rejection than a filter with 500 filter coefficients. Coincidentally, the computational workload inherent in larger filters can make these superior filters less attractive. Similarly, pattern recognition systems that utilize algorithms based on neural networks are faced with the problem of performing multiple scalar multiplications.

The present invention includes a method of operating a data processing system to calculate an approximation to a scalar product between a first vector and a second vector, wherein each vector is characterized by N components. The method includes the steps of replacing the first vector with a third vector, which is a pyramidal integer vector characterized by an integer K, which is the sum of the N components and the N component excerpt values, and a scalar multiplication between the first vector and the second vector And computing a scalar product of the second vector and the third vector to provide an approximation for the second vector.

In one aspect of the present invention, computing the scalar product of the second vector and the third vector comprises computing a scalar multiplication of a second vector by a third vector, which is specified by a corresponding one of the components in the third vector to provide a scalar multiplication of the second vector and the third vector. And adding each component of the second vector to the register a number of times.

In another aspect of the invention, the second vector is characterized by a second vector length, wherein the third vector is characterized by a third vector length, and the scalar product of the second vector and the third vector is a second vector length and The difference in three vector lengths is corrected to provide an approximation to the scalar multiplication of the first vector and the second vector.

In another aspect of the invention, the approximate value for the scalar multiplication of the first vector and the second vector is characterized by the tolerance in the scalar multiplication of the first vector and the second vector, and the scalar multiplication of the second vector and the third vector, K is selected such that the product has a minimum value that is less than the tolerance and the scalar product of the first vector and the second vector. In one aspect, K < N.

In another aspect of the invention, the components of the first vector are characterized by a numerical expression requiring a predetermined number of bits (n), where K < nN.

According to an embodiment of the present invention, the filter coefficient vector can be approximated by a pyramidal integer component vector of the type, and the computational complexity can be reduced.

FIG. 1 illustrates conventional computing hardware for computing a scalar product between A and S. FIG.
Figure 2 illustrates hardware for computing the scalar product of an integer component vector and S;
Figure 3 illustrates the distribution of integer values.
Figure 4 illustrates the frequency distribution of the components of an approximation vector.
Figure 5 illustrates the attenuation of each of the filters.

The manner in which the invention provides its advantages is based on the fact that in an arithmetic engine that produces a scalar product of a vector of the same length and a filter coefficient vector derived from a digitized signal to provide a sequence of digital values representing the signal strength as a function of time, Can be more easily understood with reference to a simple band pass filter implemented as a filter. The filter coefficient vector is denoted by A = [A ₁ , A ₂ , ..., A _N ]. Generally, the signal is composed of a sequence of digital values D _i , where i is 1 to N _D and N _D >> N. The signal may appear to be shifted into a register that is N cell lengths. The values of this register correspond to the signal vector S = [S ₁ , S ₂ ,?, S _N ]. After each scalar multiplication between A and S is computed, the contents of the register are shifted by a predetermined number of cells and the new values of D _i are shifted into the registers. The sequence of scalar products generated in this manner forms the output digital signal from the filter.

In real-time applications, the scalar product must be computed in less time than is needed to shift to a register to produce the next set of signal values that shift the register. Although time constraints can be mitigated by parallel processing, the cost of additional hardware can limit the extent to which such an option for speed improvement can be used.

The present invention is based on the observation that in some cases of interest the vector A can be replaced by an approximation vector A 'of the same length with two interesting properties. First, the scalar product of A 'and S is the approximate approximation to the scalar multiplication of A and S. Second, the scalar multiplication of A 'and S requires significantly less computational resources than the scalar multiplication of A and S.

The degree of tolerance that can be tolerated when approximating A depends on the particular application in which the scalar multiplication is being used. Consider a conventional digital filter implemented as a finite impulse response that operates on a digital sequence generated by digitizing the output of some sensors. Constant level of the noise resulting from the noise in the digitized noise and sensor coming to digital converter (ADC) - The signals are filtered analog that is used to convert the sensor analog output voltage as a function of time for the digital sequences (D _i) . The output signal from the filter is composed of another digital sequence (F _i). Each output sequence value is obtained by forming a scalar multiplication of A with the vector whose components are the subsequences of the input digital sequence. For example, the output signal value F _k is obtained by scalar multiplication of A [S _k , S _{k + 1} , ..., S _{k + N- 1} ] with A. The output signal will also have a certain level of noise resulting from the noise of the input signal. If A is replaced by A ', additional noise will be introduced into the output signal. If the additional noise is much less than the noise resulting from the noise in the input signal, the additional noise will not significantly change the accuracy of the output signal. For example, if A 'is selected and the additional noise introduced by the approximation to A is less than 25 percent of the noise introduced by the signal, then this approximation will have little effect on the output noise amplitude.

One way to reduce the computational load imposed on the scalar product is to use an approximation vector, where all of the vector components are integers. Such a vector will be referred to as an integer component vector in the following discussion. If the input data stream is a sequence of integers, the scalar product can be computed using integer multiplications and additions, which require significantly less computational resources than real multiplication and addition. If an input signal is generated by the ADC operating on a sensor output that does not have a very large voltage difference, the input data stream can be adjusted to be such an integer data stream.

One way to generate an integer component vector for A is to scale A so that the absolute value of the largest component in A is properly approximated by the desired maximum size integer. The components of the scaled vector are rounded up to integers. For purposes of this disclosure, this type of quantization scheme will be referred to as scalar quantization, in which the components are approximated one at a time without consideration of the other components of the vector. While this simple algorithm produces an integer component vector, the integer component vector does not necessarily have to be the best integer component vector in terms of reducing the noise introduced by the approximation or reducing the computational complexity. Moreover, even if the integer component vector is A ', the scalar product still requires N multiplications and N-1 additions. If the signal vector is a vector of real numbers, there is much less computation savings with multiplications involving one integer and one real number.

The present invention takes advantage of the observation that the coefficients of a vector to be approximated by an integer component vector in many real problems that require scalar multiplications have certain statistical properties. Consider the components of the vector as a set of numbers with a statistical distribution. If the statistical distribution is Laplacian, a more suitable integer component vector can be found. Further, a plurality of integer component vectors having different approximation errors may be generated, and one integer component vector that provides the best computational reduction for a given error may be determined. A number of problems of interest include vector A with statistical distributions in which the components are approximately laplacian.

For purposes of this disclosure, it is assumed that the components of A have a substantially Laplacian distribution. Consider a simple integer component vector (A ') that is generated by scaling A and rounding the above-mentioned components. The sum of the absolute values of the integer components of A 'is denoted by K. N and K define a set of integer component vectors in N-dimensional space. For purposes of this disclosure, these vectors will be referred to as pyramid vectors. A set of such vectors and methods for generating them are well known in the field of vector quantization and will not be described in detail here. For purposes of this disclosure, it is noted that if the statistical distribution of components is laplacian and the quantized components have extreme values summed to K, then such a set of vectors is suitable for representing vectors in N-dimensional space by integer component vectors Should be. Thus, for a given K, this set of integer component vectors with direction in the N-dimensional space closest to the direction of A provides the best choice for A 'with this particular K. [ It can also be seen that the scalar multiplication of A 'and some other vectors can be achieved using K additions. As K increases, the number of vectors in this set also increases. Therefore, by increasing K, a better approximation of A can be found. There is therefore a tradeoff between the error produced by approximating A by A 'and the computational workload.

The error introduced by the approximation of A by A 'can be measured in many cases. For example, in the case of a filter, the bandpass and out-of-band suppression of the filter may be determined for an approximation filter for each K value. A minimum K value that provides an acceptable passband and out-of-band suppression may be used. Once an error bound is known, an approximation of the present invention may be attempted for some samples of the predicted vectors S. If the error range is met, an approximation can be used.

Reference is now made to Fig. 1, which illustrates a conventional computing hardware for computing a scalar product between A and S. In order to simplify the drawing, the control network is omitted from the drawing. Generally, there is a register 14 initially set to zero. S _i and A _i are input to the multiplier 12 to which the output is inputted to the adder 13 which adds the multiplier output to the current contents of the register 14 every i of 1 to N. [ At the end of this process, the register 14 stores the scalar product.

As mentioned above, the computational workload for computing a scalar multiplication using an integer component vector characterized by K is K additions. Reference is now made to Fig. 2, which illustrates hardware for computing the scalar product of an integer component vector and S. To simplify the drawing again, the control network is omitted from the drawing. When the operation is started, the register 14 is again set to zero. The scalar product (A ') by the i-th component of A'_i* S_i) Of the contribution to the project. This contribution can be generated by adding a contribution to the contents of the register 14 following the multiplication. Alternatively, the contribution may be added to the contents of register 14 using adder 16,_iA '_i And the like. For purposes of this disclosure, a hardware component that performs a multiplication involving an integer (j) and a second number (x) by adding x to the accumulator j times is referred to in the following description as a repeated add multiplier Will be. If J is negative, the iterative additive multipliers subtract x from the accumulator. A '_iSince the sum of the absolute values of K is K, a total of K additions is required. x can be a floating-point number or an integer.

The scalar multiplication requires N multiplications. Assuming that the contribution of each component is provided by the iterative adder, the total number of additions is K, and the register is reset to zero. If the number of bits required to represent the mantissa of the components of A is n, each multiplication will require at least n additions and n-1 shift operations. In addition, there will be an additional N-1 addition operations. Therefore, the total workload will be larger than Nn + N-1 additions due to shift operations. Thus, if K is less than Nn + N-1, pure computational savings will be achieved by using pyramid vector approximation and iterative additive multiplication.

Even though scalar quantization of A is used, n will typically be at least 16, so the computational load generated by doing multiplications will require 16 additions and 15 shifts. Which method requires at least a computational workload depends on the size of the components in A '. Conversely, a scalar multiplication of S and A 'with a small number of small components, A' having an integer value between -15 and 15, can be implemented in a much less time by using a repeated adder multiplier for the multiplication operation. Therefore, it is advantageous to select A 'to have a large number of small components. If K <16 * N, net savings will be achieved.

It should be noted that the integer component vectors in the set of vectors defined for a particular N and K generally have some predetermined length different from the length of A. Y is the vector obtained from the set defined by N and K. Generally, Y will have a length different from A. therefore,

A '= cY.

Where c is the ratio of the length of A to the length of Y. therefore,

.

.

The scalar multiplication requires one multiplication as well as N multiplications that can be performed as K-1 addition, as described above.

While the computational workload performing the scalar multiplication using the integer component vectors described above is limited by the time for one real multiplication and K-1 addition, the actual workload may actually be less than this limit. As described above, if it is less than the value related to the number of bits required to 'the absolute value of _i max A' A stores the value of _i, and A 'in place of the conventional multiplication product of the component S _i corresponding to the _i A' _i Lt; / RTI &gt; can be performed in the iterative adder multiplier using &lt; RTI ID = 0.0 &gt; a &lt; / RTI &gt; The addition limit of K-1 is A ' _i * S _i contribution to the scalar multiplication by using an iterative adder to calculate the products using the accumulator initially set using the value of the S component other than the first zero Lt; / RTI &gt; If the accumulator of the iterative adder multiplier is set to 0 when starting the scalar multiplication, K additions are required. In some cases, however, A ' _i for some values of _i have larger cut-off values than these cutoffs. In these cases, performing the conventional multiplication is more efficient in terms of operation. In one aspect of the invention, the components of A 'are grouped so that components with small A' _i values and S _i are sent to the iterative adder and the components with larger offsets are sent to conventional multipliers.

If you perform scalar multiplication using unknown vectors and still provide sufficient accuracy in scalar multiplication, the computational load load to find the approximate vector that provides the lowest computational workload is less than the computational workload inherent in performing one scalar multiplication Much bigger. The method of the present invention is therefore most suitable for situations where multiple scalar multiplications using the same vector A are to be performed. Many examples of this type of situation are known in the art. Finite impulse response filters and neural network based pattern recognition are examples of situations in which the benefits of the present invention can provide significant savings in significant savings and / or results.

Hereinafter, an example of a finite impulse response filter not only has better filter characteristics but also implements a finite impulse response filter having the same computational workload as a conventional finite impulse response filter, Will be described in more detail with reference to a specific bandpass filter to illustrate the scheme. Consider a conventional finite impulse response bandpass filter with 57 " taps ", i.e. N = 57 passbands between 220 Hz and 400 Hz. In a conventional implementation, the finite impulse response filter requires 57 floating-point multiplications and 56 floating-point additions to generate one sample of the output signal stream. Floating point multiplications can be eliminated by scaling the floating-point coefficients and rounding the coefficients to the nearest integer and then replacing the real filter coefficients with integers. The distribution of integer values is shown in FIG. Note that the coefficients require a 16-bit integer to represent each coefficient, and essentially all filter coefficients are too large for all multiplications in the scalar products so that they can not be replaced by iterative addition multipliers. Thus, each multiplication in the scalar multiplication requires 16 additions and 15 shifts. Additionally, there are 56 additions required to sum the multiplication results. Therefore, the computational workload to perform the scalar multiplication to produce one filtered component is 968 (= 16 * 57 + 56) times of addition and 855 (= 15 * 57) shift operations.

A 197-tap filter for the same passband replaced with the closest pyramid vector from the set of pyramid vectors whose original filter coefficients are characterized by N = 197 and K = 999 to reach the approximation vector to be used to compute the scalar products . Such a filter will be referred to as an approximation filter in the following description. Figure 4 shows the frequency distribution of the components of the approximation vector. In contrast to the distribution of the weights for the 57-tap filter, all but 13 of the coefficients have an exemption of less than 20. Hence, the multiplications needed to compute the scalar multiplication can be achieved using a repetitive addition multiplier. If all of the multiplications are performed by the iterative adder, the total work load is 999 additions. Therefore, the approximation filter has slightly less computational workload than the 57-tap filter without pyramid vector approximation.

Reference is now made to Fig. 5 which illustrates the attenuation of each of the filters. The 197-tap approximation filter is shown at 54 and the 57-tap filter is shown at 52. The approximation filter has a more steep reduction than the 57-tap filter outside the passband. In addition, the out-of-band signal suppression for the approximation filter is approximately 20 dB better.

The above-described example assumes that all the multiplications in the approximation filter are performed by the iterative addition multiplier. However, as described above, it is also possible that the multiplications for the larger filter coefficients are performed in the conventional adder and shift multipliers, while the remaining multiplications are performed in the iterative adder. The components of the approximation filter can be represented by sign bits and 7 bits. Therefore, conventional multiplication requires 7 additions and 6 shifts. If all of the components whose offset values are greater than 16 utilize conventional multiplication, the workload can be reduced to approximately 500 additions.

In the preceding example, K > N. However, embodiments where K < N are also possible. As described above, the larger the K value, the smaller the difference between the direction of the source vector A and the pyramid vector A 'for A. However, if a particular application allows a difference between A and A ', the computational savings can be very large. If K < N, at least the N-K components of A 'will be zero. If K = N-1, the number of additions is with the number of additions in the conventional scalar multiplication, but the multiplications do not require any time. Therefore, the time computation load savings can be up to 16 times that of the usual method for computing scalar multiplications.

The present invention is particularly useful for neural networks. In a neural network, each layer comprises a plurality of neural nodes or processors. Each neural node is essentially a filter with an output that is processed by a nonlinear function to provide an output that is delivered to the next layer of the neural network. The first layer receives a plurality of sensor inputs similar to the signal being processed by the filters. Each layer operates on a vector comprising a subset of the sensor inputs. The filter coefficients are determined during the training period " shown " as a variety of items in which the neural network is distinct from each other, and the filter coefficients are adjusted until the final layer correctly identifies the various classes. The present invention is based on the observation that the statistical distribution of the final filter coefficients for many neural network implementation pattern recognition problems is approximately laplacian. These filter coefficient vectors can therefore be approximated by a pyramidal integer component vector of the type described above and the computational complexity can be reduced as described above. The optimal K value can be determined by reducing the initial K value to the point at which errors are observed in classifying the learning set.

The scalar product approximation of the present invention may be implemented in any data processing system capable of providing an accumulator and a repeated adder multiplier. The present invention is particularly well suited for a data processor having multiple processors that may be executed in parallel, such as graphics processors, wherein each processor can generate a term of a scalar multiplication in parallel with other processors. Further, due to the simple hardware required to implement scalar multiplication in accordance with the present invention, the present invention can be implemented in field programmable gate arrays and special processing chips.

The foregoing embodiments of the invention have been presented to illustrate various aspects of the invention. It should be understood, however, that the different aspects of the invention illustrated in the different specific embodiments may be combined to provide other embodiments of the invention. In addition, various modifications to the present invention will become apparent from the foregoing description and the accompanying drawings. Accordingly, the invention should be limited only by the scope of the following claims.

Claims (6)

CLAIMS What is claimed is: 1. A method of operating a data processing system for computing an approximation to a scalar product between a first vector and a second vector characterized by N components, each characterized by an absolute value,
Replacing the first vector with a third vector, which is a pyramidal integer vector characterized by N components, wherein each component of the pyramidal integer vector is multiplied by an integer K, which is a sum of absolute values and an absolute value of the N components, Characterized step; And
And computing a scalar product of the second vector and the third vector to provide the approximation for the scalar product between the first vector and the second vector. 2. The method of claim 1, wherein computing the scalar product of the second vector and the third vector comprises computing a scalar product of a corresponding one of the components in the third vector to provide a scalar multiplication of the second vector and the third vector. &Lt; And adding each component of the second vector to a register a number of times specified by a component of the second vector. 3. The method of claim 2, wherein the second vector is characterized by a second vector length, the third vector characterized by a third vector length, and the scalar product of the second vector and the third vector is characterized by the second Wherein a difference between the vector length and the third vector length is corrected to provide the approximate value for the scalar multiplication of the first vector and the second vector. 2. The method of claim 1 wherein the approximation of the scalar product of the first vector and the second vector is characterized by a tolerance in the scalar product of the first vector and the second vector, And K is chosen so that the scalar multiplication of the third vector has a different minimum value than the scalar product of the first vector and the second vector less than the tolerance. 2. The method of claim 1 wherein K < N. 2. The method of claim 1, wherein the components of the first vector are characterized by a numerical representation requiring a predetermined number of bits (n), wherein K < nN.

Images