Patent Description:
Modern neural network architectures utilize non-linear activation functions such as the sigmoid function, the hyperbolic tangent function (tanh), the gaussian error linear unit (GELU) function, the exponential linear unit (ELU) function, the scaled exponential linear unit (SELU) function, the rectified linear unit (ReLU) function, etc. In many cases, piecewise linear functions are used to approximate these non-linear activation functions.

In <NPL>, Sun proposes a general piecewise linear (PWL) approximation method with controllable maximum absolute error for transcendental functions. The method has the self-adaptive capability to choose the smallest number of segments under the constraint of a controllable maximum absolute error. It can approximate any transcendental function and does not rely on any properties of the target function.

A system designed with the objective of reduced chip area is discussed herein for evaluating piecewise linear functions. In accordance with one embodiment of the invention, a system for evaluating a piecewise linear function PWL(x) at an input value x* may include a first look-up table (LUT) with N entries, and a second LUT with M entries, with M being less than N. Each of the N entries may contain parameters that define a corresponding linear segment of the piecewise linear function. The system may further include a controller configured to load parameters defining one or more of the linear segments from the first LUT into the second LUT. The system may further include a classifier for receiving the input value x* and classifying the input value x* in one of a plurality of segments of a number line. A total number of the segments may be equal to M, and the segments may be non-overlapping and contiguous. The system may further include a multiplexor for selecting one of the M entries of the second LUT based on the classification of the input value x* into one of the plurality of segments. The system may further include a multiplier for multiplying the input value x* with a slope value retrieved from the second LUT to form a product. The system may further include an adder for summing the product with an intercept value retrieved from the second LUT to arrive at an intermediate value. This procedure may be repeatedly iterated after parameters defining other ones of the linear segments are loaded from the first LUT into the second LUT. The system may further include an accumulator to accumulate the intermediate values over a plurality of iterations to arrive at PWL(x) evaluated at the input value x*.

In accordance with one embodiment of the invention, a system for evaluating a piecewise linear function PWL(x) at an input value x* may include a first LUT with N entries, and a second LUT with M entries, with M being less than N. N may be greater than or equal to four and M may be greater than or equal to three. Each of the N entries may contain parameters that define a corresponding linear segment of the piecewise linear function. The system may further include a controller configured to store values in the second LUT that are based on parameters in the first LUT defining one or more of the linear segments. The system may further include a classifier configured to receive an intermediate value and classify the intermediate value in one of a plurality of segments of a number line. A total number of the segments may equal to M, and the segments may be non-overlapping and contiguous. The system may further include a multiplexor for selecting one of the M entries of the second LUT based on the classification of the intermediate value into one of the plurality of segments. The system may further include a multiplier for multiplying the intermediate value with a slope value retrieved from the second LUT to form a product. The system may further include an adder for summing the product with an intercept value retrieved from the second LUT to arrive at a feedback value or the output value PWL(x*). The system may further include a second multiplexor for selecting either the input value x* or the feedback value as the intermediate value. This procedure may be repeatedly iterated after values in the second LUT are updated based on parameters in the first LUT defining one or more of the linear segments.

These and other embodiments of the invention are more fully described in association with the drawings below.

In the following detailed description of the preferred embodiments, reference is made to the accompanying drawings that form a part hereof, and in which are shown by way of illustration specific embodiments in which the invention may be practiced. It is understood that other embodiments may be utilized and structural changes may be made without departing from the scope of the present invention. Descriptions associated with any one of the figures may be applied to different figures containing like or similar components/steps.

<FIG> depicts a plot of a non-linear function f(x) and a piecewise linear function PWL(x) that approximates f(x). PWL(x) may be formed by N linear segments, with each of the segments expressed in the form mix + bi in which i indexes the N linear segments, index i ∈ {<NUM>,. Each linear segment may be parameterized by a first x value, xi-<NUM> and a second x value xi, with xi-<NUM> < xi. The interval [xi-<NUM>, xi) may form the domain of the linear segment. Each linear segment may also be parameterized by a slope mi and an intercept bi, (e.g., a y-intercept).

More specifically, PWL(x) may be expressed as follows: <MAT> where <MAT> <MAT> <MAT> PWL(x) may be parameterized by {xj} for j ∈ {<NUM>,. N} and {mi, hi} for i ∈ {<NUM>,. In one embodiment, x<NUM> is chosen as a very large negative number (or negative infinity) and xN is chosen as a very large positive number (or positive infinity). In one embodiment, the domain of PWL(x) are x values between x<NUM> and xN, inclusive of the endpoints (i.e., x ∈ [x<NUM>, xN]).

<FIG> depicts a plot of a rectangle function recta,b(x). recta,b(x) may be parameterized by the two variables a and b, which define the respective locations of the two discontinuities of the rectangle function.

More specifically, recta,b(x) may be expressed as follows: <MAT>.

Based on the rectangle function, PWL(x) may be rewritten as follows: <MAT> To motivate a hardware implementation of the system depicted in <FIG> and <FIG> to evaluate PWL(x), PWL(x) may further be rewritten as follows: <MAT> The sum of the first two terms can be computed during a first iteration of an algorithm for evaluating PWL(x) at an input value x*; the third term can be computed during the intermediate iterations of the algorithm; and the sum of the last two terms can be computed during the last iteration of the algorithm. Since the algorithm includes a total of N-<NUM> iterations, the intermediate iterations may more precisely be referred to as the N-<NUM> intermediate iterations, since the intermediate iterations necessarily exclude the first and the last iterations.

<FIG> depicts a system <NUM> for evaluating PWL(x) at an input value x*. System <NUM> may include a full look-up table (LUT) <NUM> (or more generally, a first LUT) with N rows (or more generally N entries), each row storing parameters that define each of the N linear segments. For example, the first row of full LUT <NUM> may store m<NUM> (the slope of the first linear segment), b<NUM> (the intercept of the first linear segment) and the pair of x values, x<NUM> & x<NUM>, which collectively define the domain of the first linear segment. It is noted that for ease of explanation, some redundancy is present in the example full LUT <NUM> of <FIG>, as there are two copies of x<NUM>, two copies of x<NUM> and so on. In other embodiments (see, e.g., the full LUT <NUM> depicted in <FIG>), the full LUT <NUM> may omit these duplicate copies and store only the minimum number of parameters necessary to parameterize PWL(x).

Partial mapper <NUM> may generate an intermediate value y from the input value x* during each iteration of an algorithm for computing PWL(x*). The particulars of the partial mapper <NUM> are depicted in <FIG>. As a brief introduction to the operation of the partial mapper <NUM>, controller <NUM> may be configured to periodically store a subset of the N rows from the full LUT <NUM> in a partial LUT <NUM> of partial mapper <NUM>. Accumulator <NUM> may accumulate the intermediate values y generated over several iterations of the algorithm in order to arrive at PWL(x*). The partial mapper <NUM> and accumulator <NUM> may collectively form an activation function circuit <NUM>. For ease of depiction, full LUT <NUM> is depicted as being directly coupled to the partial mapper <NUM>. However, it should be understood that in a more complete depiction, full LUT <NUM> may be coupled to partial mapper <NUM> via controller <NUM> to more closely match the description of controller <NUM> being used to periodically store a subset of the N rows from the full LUT <NUM> in the partial LUT <NUM> of the partial mapper <NUM>.

<FIG> depicts a logic level schematic of the partial mapper <NUM> depicted in <FIG>, and the state of the partial mapper <NUM> during the first iteration of an algorithm for evaluating PWL(x) at an input value x*. At the outset of the first iteration, certain parameters are loaded from the first two rows of the full LUT <NUM> into the partial mapper <NUM>. These parameters include x<NUM> which is provided to one of the inputs of the comparator 12a, and x<NUM> which is provided to one of the inputs of the comparator 12b. These parameters also include m<NUM>, b<NUM> which are loaded from the first row of the full LUT <NUM> into the first row of the partial LUT <NUM>, and m<NUM>, b<NUM> which are loaded from the second row of the full LUT <NUM> into the second row of the partial LUT <NUM>. After the loading of the parameters, the operation of the partial mapper <NUM> may proceed as follows.

The classifier <NUM> may receive input value x* and classify the input value x* in one of a plurality of segments of a number line. The total number of the segments may be equal to M, in which the segments are non-overlapping and contiguous, and partial LUT <NUM> may have M rows (or entries). Therefore, classifier <NUM> may be used to select one of the rows (or entries) of the partial LUT <NUM>.

In the example of <FIG>, the classifier <NUM> is configured to classify the input value x* into one of three segments of a number line. The classifier <NUM> may be implemented using two comparators 12a, 12b. Comparator 12a may determine whether the input value x* is less than x<NUM>, and comparator 12b may determine whether the input value x* is less than x<NUM>. By the definition of PWL(x), x<NUM> < x<NUM>, so the output of the comparator 12a being equal to logical <NUM> or TRUE indicates that the input value x* has been classified into a first segment of the number line with values less than x<NUM>; the output of the comparator 12b being equal to logical <NUM> or TRUE indicates that the input value x* has been classified into a second segment of the number line with values greater than or equal to x<NUM> but less than x<NUM>; and the output of both comparators 12a, 12b being equal to logical <NUM> or FALSE indicates that the that the input value x* has been classified into a third segment of the number line with values greater than or equal to x<NUM>.

The respective outputs of the comparators 12a, 12b may be used as selector signals of a multiplexor <NUM>. In the example of <FIG>, the output of the comparators 12a, 12b are connected to selectors s<NUM>, s<NUM>, respectively. Selector s<NUM> receiving logical <NUM> causes the multiplexor <NUM> to output the first row of the partial LUT <NUM>; selector s<NUM> receiving logical <NUM> causes the multiplexor <NUM> to output the second row of the partial LUT <NUM>; and selectors s<NUM> and s<NUM> both receiving logical <NUM> causes the multiplexor <NUM> to output the third row of the partial LUT <NUM>.

The multiplier <NUM> may be configured to multiply the input value x* with a slope value, m, retrieved from the partial LUT <NUM> to form a product, p. The adder <NUM> is configured to sum the product, p, with an intercept value, b, retrieved from the partial LUT <NUM>. The output of the adder <NUM> may be output from the partial mapper <NUM> as the previously discussed intermediate value y. To connect back with the earlier discussion, intermediate value y is set equal to rectx<NUM>,x<NUM>(x*)(m<NUM>x* + b<NUM>) + rectx<NUM>,x<NUM>(x*)(m<NUM>x* + b<NUM>) during the first iteration depicted in <FIG>.

<FIG> depicts the state of the partial mapper <NUM> during any one of the N-<NUM> intermediate iterations of the algorithm for evaluating PWL(x) at an input value x*. At the outset of one of these intermediate iteration, certain parameters are loaded from the full LUT <NUM> into the partial mapper <NUM>. These parameters include xi-<NUM> which is provided to one of the inputs of the comparator 12a, and xi which is provided to one of the inputs of the comparator 12b. These parameters also include mi, bi which are loaded from the full LUT <NUM> into the second row of the partial LUT <NUM>. i equals <NUM> for the second iteration and equals N - <NUM> for the (N - <NUM>)th iteration. Therefore, i ∈ {<NUM>,. , N - <NUM>}. For any one of the intermediate iterations, the first and last rows of the partial LUT <NUM> may be set to zero values. There is no change to the operation of the partial mapper <NUM> in <FIG> other than the configuration of the parameter values; therefore, the operation of the partial mapper <NUM> in <FIG> will not be explained in detail. To connect back with the earlier discussion, intermediate value y is set equal to rectxi-<NUM>,xi(x*)(mix* + bi) during each of the intermediate iterations depicted <FIG> for i ∈ {<NUM>,. , N - <NUM>}.

<FIG> depicts the state of the partial mapper <NUM> during the last iteration of an algorithm for evaluating PWL(x) at an input value x*. At the outset of the last iteration, certain parameters are loaded from the full LUT <NUM> into the partial mapper <NUM>. These parameters include xN-<NUM> which is loaded into one of the inputs of the comparator 12a, and xN-<NUM> which is loaded into one of the inputs of the comparator 12b. These parameters also include mN-<NUM>, bN-<NUM> which are loaded from the full LUT <NUM> into the second row of the partial LUT <NUM>, and mN, bN which are loaded from the full LUT <NUM> into the third row of the partial LUT <NUM>. The first row of the partial LUT <NUM> may be set to zero values. There is no change to the operation of the partial mapper <NUM> in <FIG> other than the configuration of the parameter values; therefore, the operation of the partial mapper <NUM> in <FIG> will not be explained in detail. To connect back with the earlier discussion, intermediate value y is set equal to rectxN-<NUM>,xN-<NUM>(x*)(mN-<NUM>x* + bN-<NUM>) + rectxN-<NUM>,xN(x*)(mNx* + bN) during the last iteration depicted in <FIG>. It should be apparent that the accumulation of these intermediate values y yields PWL(x*) based on the earlier presented decomposition of PWL(x) in Equation <NUM>.

Some motivation is now provided for system <NUM>. In a typical implementation, system <NUM> includes one copy of full LUT <NUM>, one controller <NUM>, but many instances of activation function circuit <NUM> (i.e., one for each convolver unit of a convolver array). As chip area is a limiting resource on an application specific integrated circuit (ASIC), it is desired to reduce the number of hardware components of the activation function circuit <NUM>. The present design effectively trades off computational efficiency for a reduced hardware complexity implementation of the activation function circuit <NUM>. While it would certainly be possible to evaluate PWL(x*) in a single iteration, such a design would require a much more complex classifier that is capable of performing an N-way classification. Rather than such hardware intensive design, the present activation function circuit <NUM> only requires two comparators 12a, 12b for classifying the input value x* into one out of three segments.

The following discussion in <FIG> concerns a design that seeks to take a more "middle ground" approach (increasing the computational efficiency by a certain degree at the expense of increased hardware complexity). The partial mapper <NUM> depicted in <FIG> includes three comparators 12a, 12b, 12c instead of the two comparators 12a, 12b in <FIG>, allowing the partial mapper <NUM> to evaluate more linear segments of the piecewise linear function PWL(x) during each iteration.

To motivate the discussion in <FIG>, PWL(x) can further be rewritten as follows: <MAT>.

The sum of the first three terms can be computed during a first iteration of an alternative algorithm for evaluating PWL(x) at an input value x*, the fourth term can be computed during the intermediate iterations of the algorithm, and the sum of the last three terms can be computed during the last iteration of the algorithm. Since the alternative algorithm includes a total of N/<NUM>-<NUM> iterations (assuming that N is an even number for the ease of explanation), these intermediate iterations may more precisely be referred to as the N/<NUM>-<NUM> intermediate iterations, since the intermediate iterations necessarily exclude the first and the last iterations.

<FIG> depicts an alternative logic level schematic of the partial mapper <NUM> depicted in <FIG>, and the state of the partial mapper <NUM> during the first iteration of the alternative algorithm for evaluating PWL(x) at an input value x*. At the outset of the first iteration, certain parameters are loaded from the first three rows of the full LUT <NUM> into the partial mapper <NUM>. These parameters include x<NUM> which is loaded into one of the inputs of the comparator 12a, x<NUM> which is loaded into one of the inputs of the comparator 12b, and x<NUM> which is loaded into one of the inputs of the comparator 12c. These parameters also include m<NUM>, b<NUM> which are loaded from the first row of the full LUT <NUM> into the first row of the partial LUT <NUM>; m<NUM>, b<NUM> which are loaded from the second row of the full LUT <NUM> into the second row of the partial LUT <NUM>; and m<NUM>, b<NUM> which are loaded from the third row of the full LUT <NUM> into the third row of the partial LUT <NUM>. The fourth row of the partial LUT <NUM> may be populated with zeros.

In the example of <FIG>, the classifier <NUM> is configured to classify the input value x* into one of four segments of a number line. The classifier <NUM> may be implemented using three comparators 12a, 12b, 12c. Comparator 12a may determine whether the input value x* is less than x<NUM>; comparator 12b may determine whether the input value x* is less than x<NUM>; and comparator 12c may determine whether the input value x* is less than x<NUM>. By the definition of PWL(x), x<NUM> < x<NUM> < x<NUM>, so the output of the comparator 12a being equal to logical <NUM> or TRUE indicates that the input value x* has been classified into a first segment of the number line with values less than x<NUM>; the output of the comparator 12b being equal to logical <NUM> or TRUE indicates that the input value x* has been classified into a second segment of the number line with values greater than or equal to x<NUM> but less than x<NUM>; the output of the comparator 12c being equal to logical <NUM> or TRUE indicates that the input value x* has been classified into a third segment of the number line with values greater than or equal to x<NUM> but less than x<NUM>; and the output of all the comparators 12a, 12b, 12c being equal to logical <NUM> or FALSE indicates that the input value x* has been classified into a fourth segment of the number line with values greater than or equal to x<NUM>.

The respective outputs of the comparators 12a, 12b, 12c may be used as selector inputs of a multiplexor <NUM>. In the example of <FIG>, the outputs of comparator 12a, 12b, 12c are connected to selectors s<NUM>, s<NUM>, s<NUM>, respectively. Selector s<NUM> receiving logical <NUM> causes the multiplexor <NUM> to output the first row of the partial LUT <NUM>; selector s<NUM> receiving logical <NUM> causes the multiplexor <NUM> to output the second row of the partial LUT <NUM>; selector s<NUM> receiving logical <NUM> causes the multiplexor <NUM> to output the third row of the partial LUT <NUM>; and selectors s<NUM>, s<NUM>, s<NUM> all receiving logical <NUM> cause the multiplexor <NUM> to output the fourth row of the partial LUT <NUM>.

The multiplier <NUM> may be configured to multiply the input value x* with a slope value, m, retrieved from the partial LUT <NUM> to form a product, p. The adder <NUM> is configured to sum the product, p, with an intercept value, b, retrieved from the partial LUT <NUM>. The output of the adder <NUM> may be output from the partial mapper <NUM> as the previously discussed intermediate value y. To connect back with the earlier discussion, intermediate value y is set equal to rectx<NUM>,x<NUM>(x*)(m<NUM>x* + b<NUM>) + rectx<NUM>,x<NUM>(x*)(m<NUM>x* + b<NUM>) + rectx<NUM>,x<NUM>(x*)(m<NUM>x* + b<NUM>) during the first iteration depicted in <FIG>.

<FIG> depicts the state of the partial mapper <NUM> during any one of the N/<NUM>-<NUM> intermediate iterations of the alternative algorithm for evaluating PWL(x) at an input value x*. At the outset of any one of these intermediate iteration, certain parameters are loaded from the full LUT <NUM> into the partial mapper <NUM>. These parameters include xi-<NUM> which is loaded into one of the inputs of the comparator 12a; xi which is loaded into one of the inputs of the comparator 12b; and xi+<NUM> which is loaded into one of the inputs of the comparator 12c. These parameters also include mi, bi which are loaded from the full LUT <NUM> into the second row of the partial LUT <NUM>; and mi+<NUM>, bi+<NUM> which are loaded from the full LUT <NUM> into the third row of the partial LUT <NUM>. i equals <NUM> for the second iteration and equals N - <NUM> for the (N/<NUM> - <NUM>)th iteration. Further, i increments by <NUM> during the intermediate iterations. Therefore, i ∈ {<NUM>, <NUM>,. N - <NUM>, N - <NUM>}. For any one of the intermediate iterations, the first and last rows of the partial LUT <NUM> may be set to zero values. There is no change to the operation of the partial mapper <NUM> in <FIG> other than the configuration of the parameter values; therefore, the operation of the partial mapper <NUM> in <FIG> will not be explained in detail. To connect back with the earlier discussion, intermediate value y is set equal to rectxi-<NUM>,xi(x*)(mix* + bi) + rectxi,xi+<NUM>(x*)(mi+<NUM>x* + bi+<NUM>) during each of the intermediate iterations depicted <FIG> for i E {<NUM>, <NUM>,. N - <NUM>, N - <NUM>}.

<FIG> depicts the state of the partial mapper <NUM> during the last iteration of the alternative algorithm for evaluating PWL(x) at an input value x*. At the outset of the last iteration, certain parameters are loaded from the full LUT <NUM> into the partial mapper <NUM>. These parameters include xN-<NUM> which is loaded into one of the inputs of the comparator 12a; xN-<NUM> which is loaded into one of the inputs of the comparator 12b; and xN-<NUM> which is loaded into one of the inputs of the comparator 12c. These parameters also include mN-<NUM>, bN-<NUM> which are loaded from the full LUT <NUM> into the second row of the partial LUT <NUM>; mN-<NUM>, bN-<NUM> which are loaded from the full LUT <NUM> into the third row of the partial LUT <NUM>; mN, bN which are loaded from the full LUT <NUM> into the fourth row of the partial LUT <NUM>. The first row of the partial LUT <NUM> may be set to zero values. There is no change to the operation of the partial mapper <NUM> in <FIG> other than the configuration of the parameter values; therefore, the operation of the partial mapper <NUM> in <FIG> will not be explained in detail. To connect back with the earlier discussion, intermediate value y is set equal to rectxN-<NUM>,xN-<NUM>(x*)(mN-<NUM>x* + bN-<NUM>) + rectxN-<NUM>,xN-<NUM>(x*)(mN-<NUM>x* + bN-<NUM>) + rectxN-<NUM>,xN(x*)(mNx* + bN) during the last iteration depicted in <FIG>. It should be apparent that the accumulation of these intermediate values y yields PWL(x*) based on the earlier presented decomposition of PWL(x) in Equation <NUM>.

To note, in the alternative embodiment of the partial mapper <NUM>, the number of rows (or entries) of the partial LUT <NUM> has increased from three to four. It is understood that further modification could arrive at designs with an even higher number of rows (or entries) of the partial LUT <NUM>. However, the partial LUT <NUM> must have a number of rows (or entries) that is less than N, the total number of rows of the full LUT <NUM>. Otherwise, the partial LUT <NUM> would no longer be "partial," and the partial mapper <NUM> would no longer have a reduced hardware complexity.

<FIG> depicts a system <NUM> for evaluating PWL(x) at an input value x*. In contrast to the previously described activation function circuits, activation function circuit <NUM> is not formed by a partial mapper and an accumulator. The function of controller <NUM> and full LUT <NUM> are similar in that the controller <NUM> periodically loads one or more rows of the full LUT <NUM> into a partial LUT <NUM> of the activation function circuit <NUM>. Again, for ease of depiction, full LUT <NUM> is depicted as being directly coupled to the activation function circuit <NUM>. However, it should be understood that in a more complete depiction, full LUT <NUM> may be coupled to the activation function circuit <NUM> via controller <NUM> to more closely match the description of controller <NUM> being used to periodically load one or more rows of the full LUT <NUM> into the partial LUT <NUM> of the activation function circuit <NUM>. The details of activation function circuit <NUM> are now explained with respect to <FIG>.

<FIG> depicts a logic level schematic of the activation function circuit <NUM> depicted in <FIG>, and the state of the activation function circuit <NUM> during the first iteration of an algorithm for evaluating PWL(x) at an input value x*. At the outset of the first iteration, certain parameters are loaded from the first two rows of the full LUT <NUM> into the activation function circuit <NUM>. These parameters include x<NUM> which is loaded into one of the inputs of the comparator <NUM>. These parameters also include m<NUM>, b<NUM> which are loaded from the first row of the full LUT <NUM> into the first row of the partial LUT <NUM>, and m<NUM>, b<NUM> which are loaded from the second row of the full LUT <NUM> into the second row of the partial LUT <NUM>. It is noted that each of the M entries of the partial LUT <NUM> further includes an enable signal for either enabling or disabling a storing operation associated with a gated memory <NUM>. In the case of the first iteration, the enable signal is enabled for both rows of the partial LUT <NUM>. After the loading of the parameters, the operation of the activation function circuit <NUM> may proceed as follows.

The classifier <NUM> (implemented with a single comparator <NUM>) determines whether the input value x* is less than x<NUM>. If so, the input value x* is mapped to an output value using the function of the first linear segment (i.e., m<NUM>x + b<NUM>). Specifically, such mapping is carried out by passing the logical <NUM> signal from the output of the comparator <NUM> to the selector input of the multiplexor <NUM>, retrieving the slope value m<NUM>, intercept value b<NUM>, and enable value <NUM>, from the partial LUT <NUM>, computing the product p of m<NUM> and x* using the multiplier <NUM>, computing the sum of the product p and the intercept b<NUM> using the adder <NUM>, and storing the resulting sum in a gated memory <NUM> while the enable signal, en, is asserted (i.e., is equal to logical <NUM>).

If, however, the classifier <NUM> determines that the input value x* is not less than x<NUM>, the activation function circuit <NUM> prospectively maps the input value x* to an output value using the function of the second linear segment (i.e., m<NUM>x + b<NUM>). Specifically, such mapping is carried out by passing the logical <NUM> signal from the output of the comparator <NUM> to the selector input of the multiplexor <NUM>, retrieving the slope m<NUM>, intercept b<NUM>, and enable value <NUM>, from the partial LUT <NUM>, computing the product p of m<NUM> and x* using the multiplier <NUM>, computing the sum of the product p with the intercept b<NUM> using the adder <NUM>, and storing the resulting sum in the gated memory <NUM> while the enable signal, en, is asserted (i.e., is equal to logical <NUM>). The term "prospectively" is used because such mapping may or may not be correct. Subsequent operations will either confirm that this mapping is correct, and leave the sum stored in the gated memory <NUM> unchanged, or will determine that this mapping is incorrect, and overwrite the sum stored in the gated memory <NUM>.

<FIG> depicts the state of the activation function circuit <NUM> during subsequent iterations of an algorithm for evaluating PWL(x) at an input value x*. At the outset of any one of the subsequent iterations, certain parameters are loaded from the full LUT <NUM> into the activation function circuit <NUM>. These parameters include xi which is loaded into one of the inputs of the comparator <NUM>. These parameters also include mi+<NUM>, bi+<NUM> which are loaded from the full LUT <NUM> into the second row of the partial LUT <NUM>. In the case of the intermediate iterations, the enable signal is disabled for the first row of the partial LUT <NUM>, and is enabled for the second row of the partial LUT <NUM>. After the loading of the parameters, the operation of the activation function circuit <NUM> may proceed as follows.

The classifier <NUM> (implemented with a single comparator <NUM>) determines whether the input value x* is less than xi. If so, this means that the input value has already been mapped to an output value, and the output value stored in the gated memory <NUM> is correct. As such, no updating of the gated memory <NUM> is performed (i.e., the enable signal is set to <NUM>).

If the input value x* is not less than xi, the activation function circuit <NUM> again prospectively maps the input value x* to an output value, this time using the function of the (i+<NUM>)th linear segment (i.e., mi+<NUM>x + bi+<NUM>). Specifically, such mapping is carried out by passing the logical <NUM> signal from the output of the comparator <NUM> to the selector input of the multiplexor <NUM>, retrieving the slope mi+<NUM>, intercept bi+<NUM>, and enable value <NUM>, from the partial LUT <NUM>, computing the product p of mi+<NUM> and x* using the multiplier <NUM>, computing the sum of the product p and the intercept bi+<NUM> using the adder <NUM>, and storing the resulting sum in the gated memory <NUM> while the enable signal, en, is asserted (i.e., is equal to logical <NUM>).

The mapping is not prospective for i = N - <NUM>, since a logical zero output of the comparator <NUM> would indicate (with certainty) that the input value x* belongs to linear segment N (under the assumption that xN is set to positive infinity), and PWL(x*) is computed by mNx* + bN.

As may be apparent, the gated memory <NUM> essentially takes the place of the accumulator <NUM> of the previous embodiments in system <NUM>, so there is not much difference in terms of hardware complexity due to the absence of accumulator <NUM>. However, there is some reduced hardware complexity due to the use of only a single comparator <NUM> and a multiplexor <NUM> with only one selector signal, as well as a partial LUT <NUM> with only two rows.

<FIG> depicts a system <NUM> for evaluating the piecewise linear function PWL(x) at an input value x*. In contrast to the activation function circuit <NUM> depicted in <FIG>, activation function circuit <NUM> transmits a signal indicating the termination of the algorithm to the controller <NUM> (i.e., the "finished?" signal), at which point PWL(x*) may be read from the output of the activation function circuit <NUM>. The contents of the full LUT <NUM> may also be stored in a more compact manner, as each row only stores a single xi value without any redundant storing of the xi values. The details of activation function circuit <NUM> are now explained with respect to <FIG>.

<FIG> depicts a logic level schematic of the activation function circuit <NUM> depicted in <FIG>, and the state of the activation function circuit <NUM> during each iteration of an algorithm for evaluating PWL(x) at an input value x*. The algorithm is initialized by setting the index i equal to <NUM>. At the outset of each iteration, certain parameters are loaded from one row of the full LUT <NUM> into the activation function circuit <NUM>. These parameters include xi which is loaded into one of the inputs of the comparator <NUM>. These parameters also include mi, bi which are loaded from the full LUT <NUM> into the partial LUT <NUM>. After the loading of the parameters, the operation of the activation function circuit <NUM> may proceed as follows.

The classifier <NUM> (implemented with a single comparator <NUM>) determines whether the input value x* is less than xi. If so, the finished and enable signals (i.e., "enable" abbreviated as "en" in <FIG>) are asserted or set to logical <NUM>. At the same time the comparison is carried out, the input value x* is transformed by the function of the ith linear segment by using multiplier <NUM> to multiply mi and x* to generate the product p and using the adder <NUM> to compute the sum of the product p with the intercept bi. If the enable signal is asserted, the sum is stored in the gated memory <NUM> and the algorithm concludes. If the enable signal is not asserted, the index i is incremented, and the algorithm is repeated for the next linear segment (i.e., by loading new parameters from one row of the full LUT <NUM> into the activation function circuit <NUM>, and computing mix* + bi). The algorithm is repeated in a similar manner until either the index i is set equal to N+<NUM> or the finished signal is asserted (whichever occurs first).

To compare, activation function circuit <NUM> is more frugal in its hardware architecture than activation function circuit <NUM> in that it does not contain multiplexor <NUM>, and further its partial LUT <NUM> only includes a single row. However, such efficiencies in the design are offset by the additional complexity associated with communicating the finished signal to the controller <NUM>.

System <NUM> described in <FIG> departs from the above-described systems <NUM>, <NUM>, <NUM> in that it involves the use of transform functions. A discussion of the transform functions is first provided before providing the details of system <NUM>. One transform function is defined for each of the N linear segments of the piecewise linear function PWL(x). More specifically, if index i were used to index each of the linear segments, segment i would have a corresponding transform function Ti(x).

For i = <NUM>, the transform function Ti(x) may be expressed as follows: <MAT>.

For i ∈ {<NUM>,. , N - <NUM>}, the transform function Ti(x) may be expressed as follows: <MAT>.

For i = N, the transform function Ti(x) may be expressed as follows: <MAT> A plot of the transform functions is provided in <FIG>. Similar to PWL(x), the transform functions Ti(x) may be parameterized by {xj} for j ∈ {<NUM>,. N} and {mi, bi} for i ∈ {<NUM>,. However, Ti(x) contains one additional parameter L which must be chosen in a particular manner in order for the algorithm to work properly.

In order explain the procedure for selecting L, a flow chart of an algorithm <NUM> for evaluating PWL(x) at an input value x* is first explained. At step <NUM>, the variable v is set to x* and index i is set to <NUM>. At step <NUM>, the variable v is set equal to Ti(v) and the index i is incremented by <NUM>. At step <NUM>, the algorithm determines whether the index i is less than or equal to N (i.e., the total number of linear segments of the piecewise linear function PWL(x)). If so (yes branch of step <NUM>), the algorithm returns to step <NUM>. If not (no branch of step <NUM>), the output y is set equal to the variable v (step <NUM>), which actually equals PWL(x*) as will become more apparent after the discussion below.

The main idea of algorithm <NUM> is that if the input value x* falls within the domain of linear segment i (i.e., for i ∈ {<NUM>,. , N - <NUM>}), application of Ti(x) in step <NUM> will map the input value x* to an output value using the linear function of the ith segment (i.e., mix + bi). If the input value x* falls outside of the domain of segment i, application of Ti(x) in step <NUM> will return x* (i.e., will essentially be the identity function). The complication is that step <NUM> is repeatedly executed, so there is a chance that the mapped input value (i.e., mix* + bi) will be remapped, which would lead to an incorrect value. To prevent remapping, the strategy is to subtract a large offset from the mapped input value (i.e., mix* + bi - L) to shift the mapped input value to a portion of the domain of the subsequent transform function Ti+<NUM>(x) that corresponds to the identity function. During the application of the last transform function, TN(x) (which corresponds to the evaluation of the last segment), the offset is added back to the previously mapped input value to recover the mapped input value (i.e., mix* + bi - L + L). If, however, the input value x* falls within the domain of the last segment (i.e., segment N), the input value x* will not yet have been mapped. In this instance, the last transform function, TN(x) simply applies the linear function of the last segment to the input value (i.e., mNx* + bN) to arrive at PWL(x*).

The bounding of L is first explained in the context of the first segment of PWL(x), and then the analysis can be extended to the remaining segments other than segment N. No bounding of L is necessary for segment N, as segment N is the last segment without any possibility for remapping. The critical observation is that if the input value x* falls within the domain of the first linear segment (i.e., x<NUM> ≤ x < x<NUM>), the output of the transform function T<NUM>(x) must be less than x<NUM> to prevent that output from being remapped. If such condition were violated, there is a chance that the output of the transform function could be remapped by T<NUM>(x) = m<NUM>x + b<NUM> - L for x ≥ x<NUM>. Such condition may be written as follows: <MAT>.

Since T<NUM>(x) is a linear function for x<NUM> ≤ x < x<NUM>, its maximum must be the y-value of one of its endpoints, so the above condition is equivalent to: <MAT> After some algebraic manipulation, this expression simplifies to: <MAT> Hence, the bound on L has been provided for the first segment of PWL(x). Such analysis can be extended to segments <NUM>. N-<NUM> as follows. Recasting the above critical observation, if the input value x* falls within the domain of the ith linear segment (i.e., xi-<NUM> ≤ x < xi), the output of the transform function Ti(x) must be less than xi to prevent that output from being remapped. Such condition may be written as follows: <MAT>.

Since Ti(x) is a linear function for xi-<NUM> ≤ x < xi, its maximum must be the y-value of one of its endpoints, so the above condition is equivalent to: <MAT> After some algebraic manipulation, this expression simplifies to: <MAT> Which further simplifies to: <MAT> Hence, the bound on L has been provided for PWL(x). Pseudo-code is included in the Appendix for computing the expression: <MAT> Once the bound has been calculated, L may be determined as the bound + ε, where ε is a small positive value, such as the smallest representable positive value. For the corner case where the input value x* is less than x<NUM>, a choice was made to set PWL(x*) = m<NUM>x<NUM> + b<NUM>, as reflected in the construction of T<NUM>(x). For the corner case where the input value x* > xN, a choice was made to set PWL(x*) = mNxN + bN, as reflected in the construction of TN(x).

<FIG> depicts a system <NUM> for evaluating PWL(x) at an input value x* in accordance with algorithm <NUM>. The components of system <NUM> are similar to the components of system <NUM>, except for the activation function circuit <NUM>. The full LUT <NUM> of system <NUM> also stores the constant L in contrast to the earlier discussed full LUTs. Again, for ease of depiction, full LUT <NUM> is depicted as being directly coupled to the activation function circuit <NUM>. However, it should be understood that in a more complete depiction, full LUT <NUM> may be coupled to the activation function circuit <NUM> via controller <NUM>. The details of one embodiment of activation function circuit <NUM> are provided in <FIG> below.

<FIG> depicts a logic level schematic of a conceptual implementation of the activation function circuit <NUM> depicted in <FIG>, and the state of the activation function circuit <NUM> during the first iteration of algorithm <NUM> for evaluating PWL(x) at an input value x*. At the outset of the first iteration, certain parameters are loaded from the full LUT <NUM> into the activation function circuit <NUM>. These parameters include x<NUM> which is provided to one of the inputs of the comparator 12a and x<NUM> which is provided to one of the inputs of the comparator 12b. These parameters also include m<NUM>, b<NUM>, x<NUM> and L which may be transformed by a combinatorial circuit (not depicted) or controller <NUM> before the values [<NUM>, m<NUM>x<NUM> + b<NUM>, -L] are stored in the first row of the partial LUT <NUM>, the values [m<NUM>, b<NUM>, -L] are stored in the second row of the partial LUT <NUM>, and the values [<NUM>, <NUM>, <NUM>] are stored in the third row of the partial LUT <NUM>. The operation of the activation function circuit <NUM> may proceed as follows.

The input value x* is received by multiplexor <NUM>. Conceptually, multiplexor <NUM> passes the input value x* if the index i equals <NUM> and passes a feedback value, v (i.e., the output of adder 20b), if the index i ∈ {<NUM>. In the first iteration depicted in <FIG>, index i equals <NUM>, so the selector input to the multiplexor <NUM> is set to <NUM> in order to pass the input value x*. It is noted that the particular choice of values for the selector input of the multiplexor <NUM> is provided as an example only. Accordingly, it is possible that the selector input value of <NUM> could be designated to pass the input value x* and the selector input value of <NUM> could be designated to pass the input value v.

The classifier <NUM> may receive the input value x* and classify the input value x* in one of three segments of a number line. The classifier <NUM> may be implemented using two comparators 12a, 12b. Comparator 12a may determine whether the input value x* is less than x<NUM>, and comparator 12b may determine whether the input value x* is less than x<NUM>.

The respective outputs of the comparators 12a, 12b may be used as selector signals of a multiplexor <NUM>. Specifically, the output of comparators 12a and 12b may be connected to selectors s<NUM> and s<NUM>, respectively. Selector s<NUM> receiving logical <NUM> causes the multiplexor <NUM> to output the first row of the partial LUT <NUM>; selector s<NUM> receiving logical <NUM> causes the multiplexor <NUM> to output the second row of the partial LUT <NUM>; and selectors s<NUM> and s<NUM> both receiving logical <NUM> causes the multiplexor <NUM> to output the third row of the partial LUT <NUM>.

The multiplier <NUM> may be configured to multiply the input value x* with a slope value, m, retrieved from the partial LUT <NUM> to form a product, p. The adder 20a is configured to sum the product, p, with an intercept value, b, retrieved from the partial LUT <NUM>. The adder 20b is configured to sum the output of adder 20a with the offset value, l, received from the partial LUT <NUM> to generate the feedback value, v. Based on the above discussion, it should be apparent that the evaluation of step <NUM>, specifically v = T<NUM>(x*), is carried out in <FIG>.

<FIG> depicts the state of the activation function circuit <NUM> during the intermediate iterations of algorithm <NUM> for index i ∈ {<NUM>. N - <NUM>}. At the outset of any of the intermediate iterations, certain parameters are loaded from the full LUT <NUM> into the activation function circuit <NUM>. These parameters include xi-<NUM> which is provided to one of the inputs of the comparator 12a and xi which is provided to one of the inputs of the comparator 12b. These parameters also include mi, bi and -L which may be loaded into the partial LUT <NUM>. More specifically, through the control of the controller <NUM>, the values [<NUM>, <NUM>, <NUM>] may be stored in the first row of the partial LUT <NUM>, the values [mi, bi, -L] may be stored in the second row of the partial LUT <NUM>, and the values [<NUM>, <NUM>, <NUM>] may be stored in the third row of the partial LUT <NUM>. The operation of the activation function circuit <NUM> may proceed as follows.

Multiplexor <NUM> passes the input value x* if the index i equals <NUM> and passes a feedback value, v (i.e., the output of adder 20b), if the index i ∈ {<NUM>. In any of the intermediate iterations depicted in <FIG>, index i ∈ {<NUM>. N - <NUM>}, so the selector input to the multiplexor <NUM> is set to <NUM> in order to pass the feedback value, v.

The classifier <NUM> may receive the feedback value, v, and classify the feedback value, v, in one of three segments of a number line. The classifier <NUM> may be implemented using two comparators 12a, 12b. Comparator 12a may determine whether the feedback value, v, is less than xi-<NUM>, and comparator 12b may determine whether the feedback value, v, is less than xi.

The multiplier <NUM> may be configured to multiply the feedback value, v, with a slope value, m, retrieved from the partial LUT <NUM> to form a product, p. The adder 20a is configured to sum the product, p, with an intercept value, b, retrieved from the partial LUT <NUM>. The adder 20b is configured to sum the output of adder 20a with the offset value, l, received from the partial LUT <NUM> to generate the feedback value, v. Based on the above discussion, it should be apparent that the evaluation of step <NUM>, specifically v = Ti(v) for i ∈ {<NUM>. N - <NUM>} is carried out in <FIG>.

<FIG> depicts the state of the activation function circuit <NUM> during the final iteration of algorithm <NUM> for index i = N. At the outset of the final iteration, certain parameters are loaded from the full LUT <NUM> into the activation function circuit <NUM>. These parameters include xN-<NUM> which is provided to one of the inputs of the comparator 12a, and xN which is provided to one of the inputs of the comparator 12b. These parameters also include mN, bN, xN and L which may be transformed by a combinatorial circuit (not depicted) or controller <NUM> before the values [<NUM>, <NUM>, L] are stored in the first row of the partial LUT <NUM>, the values [mN, bN, <NUM>] are stored in the second row of the partial LUT <NUM>, and the values [<NUM>, mNxN + bN, <NUM>] are stored in the third row of the partial LUT <NUM>. The operation of the activation function circuit <NUM> may proceed as follows.

Multiplexor <NUM> passes the input value x* if the index i equals <NUM> and passes a feedback value, v (i.e., the output of adder 20b), if the index i ∈ {<NUM>. In the final iteration depicted in <FIG>, index i = N, so the selector input of the multiplexor <NUM> is set to <NUM> in order to pass the feedback value, v.

The classifier <NUM> may receive the feedback value, v, and classify the feedback value, v, in one of three segments of a number line. The classifier <NUM> may be implemented using two comparators 12a, 12b. Comparator 12a may determine whether the feedback value, v, is less than xN-<NUM>, and comparator 12b may determine whether the feedback value, v, is less than xN.

The multiplier <NUM> may be configured to multiply the feedback value, v, with a slope value, m, retrieved from the partial LUT <NUM> to form a product, p. The adder 20a is configured to sum the product, p, with an intercept value, b, retrieved from the partial LUT <NUM>. The adder 20b is configured to sum the output of adder 20a with the offset value, l, received from the partial LUT <NUM> to generate PWL(x*). Based on the above discussion, it should be apparent that the evaluation of step <NUM>, specifically v = TN(v) is carried out in <FIG>.

<FIG> depict a logic level schematic of a more efficient implementation of the activation function circuit <NUM> depicted in <FIG>, and the state of the activation function circuit <NUM> during various iterations of an algorithm for evaluating PWL(x) at an input value x*. The implementation of <FIG> differs from that of <FIG> by summing (i.e., across each row) intercepts and offset values of the partial LUT <NUM>, to form new intercept values. With such change, only a single adder <NUM> is needed to sum the intercept value, b, with the product, p. As all other aspects of the <FIG> are identical to <FIG>, the description of <FIG> will not be provided in further detail.

It is noted that the above-described extension in <FIG> can be applied to the embodiments of <FIG> and <FIG>. In that extension, the classifier <NUM> was implemented with a greater number of comparators, allowing the classifier <NUM> to classify the input value x* to a greater number of segments per iteration. It should be apparent that the classifier <NUM> of activation function circuit <NUM> could also be implemented with a greater number of comparators, allowing the classifier <NUM> to classify the input value x* or feedback value v to a greater number of segments per iteration. In such case, the partial LUT <NUM> would also need to be modified to include additional rows to store the parameters of the additional segments classified per iteration. Accordingly, in other embodiments, the partial LUT <NUM> may include three or more rows (or entries).

It is further noted that the minimum number of rows (or entries) of the partial LUT <NUM> in the embodiment of <FIG> and <FIG> was three, corresponding to the minimum number of segments present in each of the transform functions. Again, for the activation function circuit to provide hardware savings, the number of rows of the partial LUT <NUM> must be less than the number of rows of the full LUT <NUM>. Therefore, it follows that in the embodiments of interest, the full LUT <NUM> should have four or more rows (or entries) (i.e., at least one more row than the partial LUT <NUM>).

As is apparent from the foregoing discussion, aspects of the present invention involve the use of various computer systems and computer readable storage media having computer-readable instructions stored thereon. <FIG> provides an example of a system <NUM> that may be representative of any of the computing systems (e.g., controller <NUM>) discussed herein. Examples of system <NUM> may include a microcontroller, an embedded system, etc. Note, not all of the various computer systems have all of the features of system <NUM>. For example, certain ones of the computer systems discussed above may not include a display inasmuch as the display function may be provided by a client computer communicatively coupled to the computer system or a display function may be unnecessary. Such details are not critical to the present invention.

System <NUM> includes a bus <NUM> or other communication mechanism for communicating information, and a processor <NUM> coupled with the bus <NUM> for processing information. Computer system <NUM> also includes a main memory <NUM>, such as a random access memory (RAM) or other dynamic storage device, coupled to the bus <NUM> for storing information and instructions to be executed by processor <NUM>. Computer system <NUM> further includes a read only memory (ROM) <NUM> or other static storage device coupled to the bus <NUM> for storing static information and instructions for the processor <NUM>. A storage device <NUM>, for example a hard disk, flash memory-based storage medium, or other storage medium from which processor <NUM> can read, is provided and coupled to the bus <NUM> for storing information and instructions (e.g., operating systems, applications programs and the like).

Computer system <NUM> may be coupled via the bus <NUM> to a display <NUM>, such as a flat panel display, for displaying information to a computer user. An input device <NUM>, such as a keyboard including alphanumeric and other keys, may be coupled to the bus <NUM> for communicating information and command selections to the processor <NUM>. Another type of user input device is cursor control device <NUM>, such as a mouse, a trackpad, or similar input device for communicating direction information and command selections to processor <NUM> and for controlling cursor movement on the display <NUM>. Other user interface devices, such as microphones, speakers, etc. are not shown in detail but may be involved with the receipt of user input and/or presentation of output.

The processes referred to herein may be implemented by processor <NUM> executing appropriate sequences of computer-readable instructions contained in main memory <NUM>. Such instructions may be read into main memory <NUM> from another computer-readable medium, such as storage device <NUM>, and execution of the sequences of instructions contained in the main memory <NUM> causes the processor <NUM> to perform the associated actions. In alternative embodiments, hard-wired circuitry or firmware-controlled processing units may be used in place of or in combination with processor <NUM> and its associated computer software instructions to implement the invention. The computer-readable instructions may be rendered in any computer language.

In general, all of the above process descriptions are meant to encompass any series of logical steps performed in a sequence to accomplish a given purpose, which is the hallmark of any computer-executable application. Unless specifically stated otherwise, it should be appreciated that throughout the description of the present invention, use of terms such as "processing", "computing", "calculating", "determining", "displaying", "receiving", "transmitting" or the like, refer to the action and processes of an appropriately programmed computer system, such as computer system <NUM> or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within its registers and memories into other data similarly represented as physical quantities within its memories or registers or other such information storage, transmission or display devices.

Computer system <NUM> also includes a communication interface <NUM> coupled to the bus <NUM>. Communication interface <NUM> may provide a two-way data communication channel with a computer network, which provides connectivity to and among the various computer systems discussed above. For example, communication interface <NUM> may be a local area network (LAN) card to provide a data communication connection to a compatible LAN, which itself is communicatively coupled to the Internet through one or more Internet service provider networks. The precise details of such communication paths are not critical to the present invention. What is important is that computer system <NUM> can send and receive messages and data through the communication interface <NUM> and in that way communicate with hosts accessible via the Internet. It is noted that the components of system <NUM> may be located in a single device or located in a plurality of physically and/or geographically distributed devices.

Claim 1:
A system (<NUM>), comprising:
a first LUT (<NUM>) with N entries, wherein each of the N entries contains parameters that define a corresponding linear segment;
a second LUT (<NUM>) with M entries, wherein M is less than N;
a controller (<NUM>) configured to store a subset of the N entries from the first LUT (<NUM>) in the second LUT (<NUM>);
a classifier (<NUM>) configured to receive an input value and classify the input value in one of a plurality of segments of a number line, wherein a total number of the segments is equal to M, and wherein the segments are non-overlapping and contiguous; and
a multiplexor (<NUM>) for selecting one of the M entries of the second LUT (<NUM>) based on the classification of the input value into one of the plurality of segments
wherein the controller is further configured to successively update the second LUT (<NUM>) to store non-overlapping subsets of the N entries from the first LUT (<NUM>).