DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
This office action is in responsive to communication(s): original application filed on 05/01/2024, said application claims a priority filing date of 05/02/2023. Claims pending. Claims independent.
Drawings
The drawings are objected to as failing to comply with 37 CFR 1.84(p)(4) because reference character “108” has been used to designate both "first registers" in with ¶¶ [0023], [0029], [0034], [0047], and [0055] with FIG. 1 and ". Corrected drawing sheets in compliance with 37 CFR 1.121(d) are required in reply to the Office action to avoid abandonment of the application. Any amended replacement drawing sheet should include all of the figures appearing on the immediate prior version of the sheet, even if only one figure is being amended. Each drawing sheet submitted after the filing date of an application must be labeled in the top margin as either “Replacement Sheet” or “New Sheet” pursuant to 37 CFR 1.121(d). If the changes are not accepted by the examiner, the applicant will be notified and informed of any required corrective action in the next Office action. The objection to the drawings will not be held in abeyance.
The drawings are objected to as failing to comply with 37 CFR 1.84(p)(4) because reference characters "108" in ¶¶ [0049] and [0057] and "110" in ¶¶ [0023] and [0029] with FIG. 1 1have both been used to designate "second registers". Corrected drawing sheets in compliance with 37 CFR 1.121(d) are required in reply to the Office action to avoid abandonment of the application. Any amended replacement drawing sheet should include all of the figures appearing on the immediate prior version of the sheet, even if only one figure is being amended. Each drawing sheet submitted after the filing date of an application must be labeled in the top margin as either “Replacement Sheet” or “New Sheet” pursuant to 37 CFR 1.121(d). If the changes are not accepted by the examiner, the applicant will be notified and informed of any required corrective action in the next Office action. The objection to the drawings will not be held in abeyance.
The drawings are objected to as failing to comply with 37 CFR 1.84(p)(5) because they include the following reference character(s) not mentioned in the description: 406, 408, 410, and 412 in FIG. 4. Corrected drawing sheets in compliance with 37 CFR 1.121(d), or amendment to the specification to add the reference character(s) in the description in compliance with 37 CFR 1.121(b) are required in reply to the Office action to avoid abandonment of the application. Any amended replacement drawing sheet should include all of the figures appearing on the immediate prior version of the sheet, even if only one figure is being amended. Each drawing sheet submitted after the filing date of an application must be labeled in the top margin as either “Replacement Sheet” or “New Sheet” pursuant to 37 CFR 1.121(d). If the changes are not accepted by the examiner, the applicant will be notified and informed of any required corrective action in the next Office action. The objection to the drawings will not be held in abeyance.
Specification
The disclosure is objected to because of the following informalities:
in ¶ [0007], "… nor is it intended to deter-mine the scope of the claimed subject matter" appears to be "… nor is it intended to determine the scope of the claimed subject matter";
in ¶ [0022], "… the processor 102 may exe-cute the instructions in the CRM 104 …" appears to be "… the processor 102 may execute the instructions in the CRM 104 …".
Appropriate correction is required.
The use of the term "ZigBee" and "Bluetooth" in ¶ [0106], which is a trade name or a mark used in commerce, has been noted in this application. The term should be accompanied by the generic terminology; furthermore the term should be capitalized wherever it appears or, where appropriate, include a proper symbol indicating use in commerce such as ™, SM , or ® following the term.
Although the use of trade names and marks used in commerce (i.e., trademarks, service marks, certification marks, and collective marks) are permissible in patent applications, the proprietary nature of the marks should be respected and every effort made to prevent their use in any manner which might adversely affect their validity as commercial marks.
Claim Objections
Claims 1-12 and 14-15 are objected to because of the following informalities:
in Claim 1, lines 6-7, "… each input number being an offset of a respective classification output of the neural network …" appears to be "… said each input number yi being an offset of a respective classification output of the neural network …" (see also 112 Rejections to Claim 1);
in Claim 1, line 8, "… for each input number yi, determining a normalized probability pi …" appears to be "… for said each input number yi, determining a normalized probability pi …";
in Claim 2, line 3, "… for each input number yi, determining an element number zi by multiplying …" appears to be "… for said each input number yi, determining an element number zi by multiplying …";
in Claim 3, lines 1-3, "… calculating a linear approximation or a quadratic approximation of two raised to the power of the negation of the fractional part fraci …" appears to be "… calculating a linear approximation or a quadratic approximation of said two raised to the power of the negation of the fractional part fraci …";
in Claim 4, lines 4-5, "… multiplying each result register by an inverse of the sum register or dividing each result register by the sum register …" appears to be "… multiplying each result register by an inverse of the sum register or dividing said ach result register by the sum register …";
in Claim 5, line 4, "… storing the corresponding fraction component fc,i into the respective result register …" appears to be "… storing the fraction component fc,i into the respective result register …";
in Claim 6, lines 1-2, "… wherein each input number yi is scaled by an input scaling factor Sin …" appear to be "… wherein said each input number yi is scaled by an input scaling factor Sin …";
in Claim 7, lines 1-3, "… wherein the input scaling factor Sin is determined based on expected smallest and largest values of the input numbers yi and …" appears to be "… wherein the input scaling factor Sin is determined based on expected smallest and largest values of the input numbers y and …" (see also 112 Rejections to Claim 7);
in Claim 8, line 4, "… storing each input number yi in binary form into a first N-bit register …" appears to be "… storing said each input number yi in binary form into a first N-bit register …";
in Claim 8, lines 8-12, "… in response to the input number yi, after right shifting by N/2-1, not overflowing the second N/2-bit register … or in response to the input number yi, after right shifting by N/2-1, overflowing the second N/2-bit register …" appears to be "… in response to the input number yi, after the right shifting by N/2-1, not overflowing the second N/2-bit register … or in response to the input number yi, after the right shifting by N/2-1, overflowing the second N/2-bit register …";
in Claim 8, line 13, "… providing a constant value in binary form into a third N/2-bit register …" appears to be "… providing a constant value in the binary form into a third N/2-bit register …";
in Claim 9, lines 4-5, "… rounding the right-shifted input number yi,T by adding 2N/2-2 to the input number yi before right shifting by N/2-1" appears to be "… rounding the right-shifted input number yi,T by adding 2N/2-2 to the input number yi before the right shifting by N/2-1";
in Claim 10, line 4, "… storing each input number yi in binary form into a first N-bit register …" appears to be , "… storing said each input number yi in binary form into a first N-bit register …";
in Claim 10, lines 8-9, "… providing a constant value in binary form scaled by 2N/2-2 into a third N-bit register …" appears to be "… providing a constant value in the binary form scaled by 2N/2-2 into a third N-bit register …";
in Claim 11, lines 4-5, "… rounding the right-shifted input number yi,T by adding 2N/2-3 to the input number yi before right shifting by N/2-2" appears to be "… rounding the right-shifted input number yi,T by adding 2N/2-3 to the input number yi before the right shifting by N/2-2";
in Claim 12, lines 4-5, "… the value V100 obtained by setting to 1 all bits in each result register … applying the normalization factor fn to each result register with …" appears to be "… the value V100 obtained by setting to 1 all bits in said each result register … applying the normalization factor fn to said each result register with …" (see also 112 Rejections to Claim 12);
in Claim 14, lines 2-3, "… deriving each input number yi from a corresponding original input number xi by …" appears to be "… deriving said each input number yi from a corresponding original input number xi by …";
in Claim14, lines 6-10, "… for each original input number xi: subtracting xmax from xi so as to obtain a negative or zero input number yi; or subtracting xi from xmax so as to obtain a zero or positive input number yi" appears to be "… for each original input number xi: subtracting the xmax from the xi so as to obtain a negative or zero input number yi; or subtracting the xi from the xmax so as to obtain a zero or positive input number yi";
in Claim 15, lines 8-9, "… each input number being an offset of a respective classification output of a neural network …" appears to be "… said each input number yi being an offset of a respective classification output of a neural network …";
in Claim 15, line 10, "… for each input number yi, determining a normalized probability pi …" appears to be "… for said each input number yi, determining a normalized probability pi …".
Appropriate correction is required.
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitation(s) is/are: "processing hardware" in Claim 15.
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, it/they is/are being interpreted to cover the corresponding structure described in the specification (e.g., processing device 100 described in ¶ [0022] of the specification, such as an integer-based digital signal processor, controller, microprocessor, or system-on-chip) as performing the claimed function, and equivalents thereof.
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-14 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Claim 1 recites the limitation "… processing " in lines 1-7, which rendering the claim indefinite because ".
Claims 2-14 are rejected for fully incorporating the deficiency of their respective base claims.
Claim 7 recites the limitation "… the input scaling factor Sin is determined based on expected smallest and largest values of the input numbers yi and a size N of the first registers" in lines 1-3, which rendering the claim indefinite because ".
Claim 12 recites the limitation "... summing the result registers into a sum register ..." in line 3, which rendering the claim indefinite because ".
Claim 12 recites the limitation "… obtaining a normalization factor fn by scaling a value V100, the value V100 obtained by setting to 1 all bits in each result register, by a normalization scaling factor Sn …" in lines 4-6, which rendering the claim indefinite because it is unclear how to obtain.
Claim 13 recites the limitation "… wherein the binary number qi is generated in the result register in a form of an IEEE 754 floating-point number …" in lines 1-3, which rendering the claim indefinite because ".
Claim 14 recites the limitation "... the original input numbers x being the classification output of the neural network ..." in lines 4-5, which rendering the claim indefinite because ".
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefore, subject to the conditions and requirements of this title.
Claims 1-15 are rejected under 35 U.S.C. 101 because the claimed invention is directed to abstract idea without significantly more.
Independent Claims 1 and 15
Step 1: Claim 1 is a process claim and Claim 15 is a system claim. These claims fall within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) recite(s) ".
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) recite(s) additional elements/limitations of ".
Step 2B: The claim(s) does/do not include additional elements that are sufficient to amount to significantly more than the judicial exception because the additional limitation/element of .
Claim 2
Step 1: Claim 2 is a process claim which falls within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) further recite(s) ".
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) does/do not further recite(s) additional elements/limitations.
Step 2B: The claim(s) does/do not further include additional elements that are sufficient to amount to significantly more than the judicial exception. Thus, none of the additional limitations, taken either alone or combined, amount to significantly more than the abstract idea.
Claim 3
Step 1: Claim 3 is a process claim which falls within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) further recite(s) ".
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) does/do not further recite(s) additional elements/limitations.
Step 2B: The claim(s) does/do not further include additional elements that are sufficient to amount to significantly more than the judicial exception. Thus, none of the additional limitations, taken either alone or combined, amount to significantly more than the abstract idea.
Claim 4
Step 1: Claim 4 is a process claim which falls within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) further recite(s) ".
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) .
Step 2B: The claim(s) does/do not further include additional elements that are sufficient to amount to significantly more than the judicial exception because the additional limitation.
Claim 5
Step 1: Claim 5 is a process claim which falls within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) further recite(s) ".
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) .
Step 2B: The claim(s) does/do not further include additional elements that are sufficient to amount to significantly more than the judicial exception because the additional limitation.
Claim 6
Step 1: Claim 6 is a process claim which falls within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) further recite(s) ".
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) .
Step 2B: The claim(s) does/do not further include additional elements that are sufficient to amount to significantly more than the judicial exception because the additional limitation/element of .
Claim 7
Step 1: Claim 7 is a process claim which falls within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) further recite(s) ".
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) does/do not further recite(s) additional elements/limitations.
Step 2B: The claim(s) does/do not further include additional elements that are sufficient to amount to significantly more than the judicial exception. Thus, none of the additional limitations, taken either alone or combined, amount to significantly more than the abstract idea.
Claim 8
Step 1: Claim 8 is a process claim which falls within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) further recite(s) ".
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) .
Step 2B: The claim(s) does/do not further include additional elements that are sufficient to amount to significantly more than the judicial exception because the additional limitation.
Claim 9
Step 1: Claim 9 is a process claim which falls within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) further recite(s) ".
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) does/do not further recite(s) additional elements/limitations.
Step 2B: The claim(s) does/do not further include additional elements that are sufficient to amount to significantly more than the judicial exception. Thus, none of the additional limitations, taken either alone or combined, amount to significantly more than the abstract idea.
Claim 10
Step 1: Claim 10 is a process claim which falls within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) further recite(s) ".
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) .
Step 2B: The claim(s) does/do not further include additional elements that are sufficient to amount to significantly more than the judicial exception because the additional limitation.
Claim 11
Step 1: Claim 11 is a process claim which falls within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) further recite(s) ".
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) does/do not further recite(s) additional elements/limitations.
Step 2B: The claim(s) does/do not further include additional elements that are sufficient to amount to significantly more than the judicial exception. Thus, none of the additional limitations, taken either alone or combined, amount to significantly more than the abstract idea.
Claim 12
Step 1: Claim 12 is a process claim which falls within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) further recite(s) ".
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) .
Step 2B: The claim(s) does/do not further include additional elements that are sufficient to amount to significantly more than the judicial exception because the additional limitation.
Claim 13
Step 1: Claim 13 is a process claim which falls within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) further recite(s) ".
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) .
Step 2B: The claim(s) does/do not further include additional elements that are sufficient to amount to significantly more than the judicial exception because the additional limitation/element of .
Claim 14
Step 1: Claim 14 is a process claim which falls within at least one of the four categories of patent eligible subject matter.
Step 2A Prong 1: The claim(s) further recite(s) ".
Step 2A Prong 2: This judicial exception is not integrated into a practical application because the claim(s) does/do not further recite(s) additional elements/limitations.
Step 2B: The claim(s) does/do not further include additional elements that are sufficient to amount to significantly more than the judicial exception. Thus, none of the additional limitations, taken either alone or combined, amount to significantly more than the abstract idea.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1 and 14-15 are rejected under 35 U.S.C. 103 as being unpatentable over Cardarilli et al. ("A pseudo-softmax function for hardware-based high speed image classification", Scientific Reports, 11:15307, July 28, 2021, pp. 1-10), hereinafter Cardarilli in view of Chen et al. ("Approximate Softmax Functions for Energy-Efficient Deep Neural Networks", IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, VOL. 31, NO. 1, Dec. 28, 2022, pp. 4-16), hereinafter Chen.
Independent Claims 1 and 15
Cardarilli discloses a computer-implemented method of processing a classification output of a neural network (Cardarilli, ABSTRCT in Page 1: in this work a novel architecture, named pseudo-softmax, to compute an approximated form of the softmax function is presented; this architecture can be fruitfully used in the last layer of Neural Networks and Convolutional Neural Networks for classification tasks, and in Reinforcement Learning hardware accelerators to compute the Boltzmann action-selection policy; 1st – 2nd paragraphs of Page 1 with FIG. 1 in Page 2: the softmax function is one of the most important operators in the field of Machine Learning; it is used in the last layer in classification Neural Networks (NN) and also in Convolutional Neural Networks (CNN) to normalize the raw output of such systems; the outputs of the network
x
i
are processed to represent the probability of the inference output
p
i
to belong to a certain class (Fig. 1)), the method comprising:
for each input number yi, determining, using an approximation of a SoftMax function that uses integer-based operations without using an exponential operation, a binary number qi that represents a probability distribution of the input number yi, (Cardarilli, ABSTRACT of Page 1: the proposed pseudo-softmax design, intended for efficient hardware implementation, exploits the typical integer quantization of hardware-based Neural Networks obtaining an accurate approximation of the result; Before Section "Pseudo‑softmax function" in Pages 1-2: the softmax function equation is:
p
i
=
e
x
i
∑
k
=
1
N
e
x
k
(1), where
x
i
are the outputs of a machine learning network and
i
=
1
,
…
,
N
; the optimization in the hardware architectures is obtained both by the use of approximation algorithms and by the integer quantization of the arithmetic, usually by using 8 bits integers (INT8); introduce the pseudo-softmax architecture with the aim to allow for an efficient hardware implementation of the softmax layer in hardware implemented NNs and CNNs; Yuan11 proposed an implementation that uses a logarithmic transformation to avoid the division; the exponential operations are simply carried out via Look Up Tables (LUT); Geng et al.12 proposed two architectures that compute the exponential function both via LUT and linear approximation; the division is carried out by finding the closest power of 2, thus only shift operations are needed; Li et al.13 proved that LUT implementations for the exponential function are the best trade-off between precision and speed, if compared to Taylor’s series and CORDIC14 implementations; the division is performed by bit-shifting; Baptista et al.15 proposed a High Level Synthesis (HLS) FPGA implementation for a specific CNN application; the exponents of the softmax formula are split into integer and fractional parts; the integer parts are evaluated by using a ROM approach, while polynomial approximation is used for the fractional parts; Wang et al.16 proposed an interesting architecture that exploits the fact that every number can be split in integer and fractional part; the implementation avoids any straightforward division or exponential operation by using Leading One Detectors (LOD), bit shifters, and constant multipliers; Sun et al.17 proposed a FPGA serial implementation that splits every exponential operation in more operations to reduce the size of each ROM; the division is carried out via bit-shifting; Hu et al.18 proposed their Integral Stochastic Computation (ISC) to evaluate the exponent operator; the division is avoided by a logarithmic transformation; Du et al.19 proposed a tunable precision block for the exponentiation based on a variable number of LUTs; Kouretas and Paliouras20 implemented an approximated equation that takes into account only the exponents of the softmax formula and that replaces the summation with the highest input value; Di Franco et al.22 proposed a straightforward FPGA implementation of the softmax by using a linear interpolating LUT for the exponential function; Kouretas and Paliouras23 extended their previous work20 by improving the accuracy analysis by using real-world CNNs and by adding information about the ASIC implementation; Section "Pseudo‑softmax function" in Pages 2-3: in order to simplify the computation of the softmax function in Eq. (1), we introduce a new approximated expression named pseudo-softmax:
p
~
i
=
2
x
i
∑
k
=
1
N
2
x
k
(2), in which the exponent base e is replaced by 2; as in the case of the softmax function, the summation of the pseudo-softmax outputs is always equal to one; consequently, the values-
p
i
can be interpreted as probabilities; as stated in the Introduction, the hardware implementations of NN systems make use of the integer quantization, typically 8-bit integers (INT8); the reason of using powers of two
2
x
i
in Eq. (2) is that the integer numbers
x
i
can be interpreted as the exponent of floating-point (FLP) numbers, allowing for an efficient hardware implementation; according to the conventional base-2 FLP representation, a positive number
a
is represented as:
a
=
2
b
∙
1
∙
c
(3), where
b
is the integer exponent and
c
is the fractional mantissa; consequently, the pseudo-softmax function can be rewritten as
p
~
i
=
2
x
i
-
exp
s
u
m
∙
1
1
∙
mant
s
u
m
(7); the expression Eq. (7) of the pseudo-softmax function shows that the output -
p
~
i
is a FLP number with exponent
x
i
-
exp
s
u
m
, and with mantissa
1
/
1
∙
mant
s
u
m
, i.e., the reciprocal of the mantissa of the summation; the mantissa is common (constant) for all -
p
~
i
s, and it is only computed once; Section "Hardware architecture" with FIGS. 2-4 in Pages 3-5: the pseudo-softmax function in Eq. (7) is implemented by using the hardware architecture shown in Fig. 2; as stated in the Introduction, the 8-bit integers inputs
x
i
with range [−128, 127] are interpreted as the exponents of FLP numbers; the denominator of Eq. (7) is the mantissa of the FLP number sum; the outputs are unsigned FLP numbers
p
~
i
=
2
exp
o
u
t
i
∙
1
∙
mant
o
u
t
(8) represented by using 17 bits: 9-bit exponent, and 8-bit fractional mantissa with implicit integer bit (always 1); the 9-bit exponent (unbiased) guarantees for overflows for maximum values
x
i
= 127 and number of inputs N < 128; there is no representation for zero, that can be determined by comparing -pi to a sufficiently small threshold value; the negative exponent makes the floating-point number smaller than 1.0, but all output numbers are positive; therefore, the sign bit is not necessary; the unit in Fig. 2 is composed of three main blocks: a tree of FLP adders to compute
s
u
m
=
2
exp
s
u
m
∙
1
∙
mant
s
u
m
; a piece-wise linear (PWL) interpolation block to compute the reciprocal, and an array of integers subtractors computing
(
x
i
-
exp
s
u
m
)
; we opted for a binary tree of FLP adders, that is modular and easy to design; if delay (for throughput) is problematic, the binary tree can be easily pipelined, after each adder, to meet the timing constraints; the architecture of the FLP adder tree for N = 6 is shown in Fig. 3a; the
x
i
of Eq. (2) are the exponents of FLP numbers and their mantissas is 1.0; the architecture of the FLP adder24 is shown in Fig. 3b; since it operates on positive FLP numbers, its architecture is simplified; first, the exponents difference
d
is computed to find the amount of shifting necessary for the alignment of the mantissas; the largest exponent is selected as the exponent of the result; the alignment is performed by a barrel shifter (block ≫ in Fig. 3b) by shifting
d
positions to the right the mantissa of the smallest number; if
d
≥
8
, the mantissa of the smallest number is flushed to zero, and no actual addition is performed; when
d
=
0
, same exponent, the addition of the normalized mantissas results in an overflow (mant ≥ 2.0) and the result must be normalized by incrementing by one the exponent, and by dividing the mantissa by two, i.e., right-shifting the result 1 position (block ≫ 1); an additional simplification is done for the FLP adder in the first level of the adder tree (Fig. 3c); since, the input values
x
i
are power of two’s numbers and their mantissas is 1.0, there is no need to swap the mantissas (identical) according to
d
; the barrel shifter is also simplified because its input is the constant 1.0; when
d
=
0
, i.e.,
x
i
=
x
j
, the result of the addition of the two mantissas is mant = 2.0 (overflow); however, since the fractional bits are all zero, right-shifting is not necessary, and the normalization is done by incrementing the exponent of the result only; the computation of the probabilities -
p
~
i
, the mantissa is common to all -
p
~
i
s, and consequently, a single reciprocal operation is sufficient; moreover, because of the normalization, the mantissa is in the range [1, 2); for the reciprocal y = 1/x , we opted for a piece-wise linear (PWL) polynomial approximation in two intervals
y
~
=
1.59375
-
0.625
∙
x
i
f
x
<
1.5
1.125
-
0.3125
∙
x
i
f
x
≥
1.5
(9); the coefficients of the polynomials were chosen, by incremental refinements, as the closest to powers of two to simplify the hardware; by expressing in binary the coefficients of (9) and as powers of two, we have
y
~
=
1.10011
|
2
-
x
2
-
1
+
2
-
3
i
f
x
<
1.5
1.00100
|
2
-
x
2
-
2
+
2
-
4
i
f
x
≥
1.5
(10); the resulting reciprocal approximation unit is shown Fig. 4a; since the intervals in Eq. (10) are determined by
mant
s
u
m
being greater or smaller than 1.5, the MSB of the fractional part of the mantissa, bit with weight 2−1, is used to select the interpolating polynomial; Figure 4b shows the plots of
y
=
1
/
x
and of the interpolating polynomials in [1.0, 2.0)); and
for each input number yi, determining a normalized probability pi from the binary numbers qi (Cardarilli, 1st paragraph of Page 1: the softmax function is used in the last layer in classification Neural Networks (NN) and also in Convolutional Neural Networks (CNN) to normalize the raw output of such systems; Subsection "Floating‑point adder tree" with FIGS. 3(b)-3(c) in Page 4: the architecture of the FLP adder24 is shown in Fig. 3b; when
d
=
0
, same exponent, the addition of the normalized mantissas results in an overflow (mant ≥ 2.0) and the result must be normalized by incrementing by one the exponent, and by dividing the mantissa by two, i.e., right-shifting the result 1 position (block ≫ 1); an additional simplification is done for the FLP adder in the first level of the adder tree (Fig. 3c); when
d
=
0
, i.e.,
x
i
=
x
j
, the result of the addition of the two mantissas is mant = 2.0 (overflow); however, since the fractional bits are all zero, right-shifting is not necessary, and the normalization is done by incrementing the exponent of the result only; Subsection "Piece‑wise linear reciprocal block" in Pages 4-5: the computation of the probabilities -
p
~
i
, the mantissa is common to all -
p
~
i
s, and consequently, a single reciprocal operation is sufficient; moreover, because of the normalization, the mantissa is in the range [1, 2)).
Cardarilli further discloses a system comprising: memory hardware configured to store instructions; and processing hardware configured to execute the instructions, wherein the instructions include the operations described above (Cardarilli, ABSTRACT in Page 1: inherited in a computer to compute an approximated form of the softmax function; Section "Implementation results" with FIG. 8 in Pages 7-8: we implemented the pseudo-softmax architecture by using a 90 nm 1.0 V CMOS standard-cell library; the synthesis was performed by using Synopsis Design Compiler; the first implementation of the pseudo-softmax unit is for a INT8 input and N = 10 architecture; the results are reported in Fig. 8a; the power dissipation is evaluated at the maximum operating frequency of 310 MHz; he second implementation is a pseudo-softmax unit with 3-bit inputs; the result of the comparison are displayed in Fig. 8b; the power dissipation was evaluated at 300 MHz; in Fig. 8c,d we provide the area and power dissipation for different INT8 and INT3 implementations, varying the number of inputs; we set the synthesis tool to a timing constraint of 100 MHz, which is the maximum achievable frequency of the larger architecture (INT8, 32 inputs); the power dissipations were evaluated considering this frequency; except for the PWL reciprocal block, the hardware resources are strictly related to the number of inputs and the quantization; moreover, it can be observed how the area required for the I/O registers, the FLP adder tree, and the array of subtractors, doubles when we double the number of inputs; Section "Discussion" in Page 8: the pseudo-softmax architecture has been implemented in VHDL and synthesized in standard-cells).
Cardarilli fails to explicitly disclose each input number being an offset of a respective classification output of the neural network.
Chen teaches a system and a method for approximating Softmax Functions (Chen, Title/Abstract in Page 4), wherein each input number being an offset of a respective classification output of the neural network (Chen, Abstract in Page 4: approximate computing has emerged as a new paradigm that provides power-efficient and high-performance arithmetic designs by relaxing the stringent requirement of accuracy; nonlinear functions (such as softmax, rectified linear unit (ReLU), Tanh, and Sigmoid) are extensively used in deep neural networks (DNNs); however, they incur significant power dissipation due to the high circuit complexity; as DNNs are error-tolerant, the design of approximation-linear functions is possible and desired; in this article, the design of an approximate softmax function (AxSF) is proposed; AxSF is based on a double hybrid structure (DHS); AxSF divides the input of the softmax function into two parts for different processing methods; the most significant bits (MSBs) are processed with lookup tables (LUTs) and an exact restoring array divider (EXDr); Taylor’s expansion and a logarithmic divider are used for the less significant bits (LSBs); an improved DHS (IDHS) is also proposed to reduce the hardware complexity; in IDHS, a novel Booth multiplier is utilized for the hybrid scheme to improve the partial product generation and compression, while the truncated implementation is applied to the divider unit; the proposed DHS and IDHS are compared with existing softmax designs; the results show that the proposed approximate softmax design reduces hardware by 48% and delay by 54% while retaining a high accuracy; Section II.A with FIG.1 in Page 6: the softmax function is always placed after the fully connected layer in DNNs due to the ability to perform classification operations to the probability distributions from large amounts of features; as shown in Fig. 1, the multichannel feature map (processed by the convolutional and the pooling layers) is expanded into a 1-D vector at the fully connected layer; the dot product is then performed with the corresponding weight vector in the fully connected layer; finally, the input data of the softmax function are formed by using the bias; after passing through the softmax layer, the output data are delivered to the softmax loss layer; Section III in Pages 7-8: most of the approximate designs for nonlinear functions in DNNs represented by softmax functions are based on LUTs or segmented product sums; this article integrates these schemes, using a high-precision design to operate on the most significant bits (MSBs) of the input operands and an approximate design to reduce the hardware for the less significant bits (LSBs); based on this arrangement, this section utilizes a configurable approximation design scheme with a dual structural hybrid accuracy for the softmax: the implementation of the exponential multiplication unit uses a combination of LUTs and a segmented approximate design; moreover, the divider consists of an EXDr and an approximate logarithmic divider; the proposed scheme approximately computes using different bit-width allocations to meet the requirement of reconfigurable accuracy; an appropriate configuration scheme can be chosen to achieve the needed accuracy and hardware performance (so by considering power consumption, latency, and area); Section III.A in Page 8: as the range of the exponent is [0,+∞], a data overflow may likely occur by performing an exponent operation on the original input data, and causing a precision loss; to avoid this issue, preprocessing of the input data is then required for this implementation; the purpose of preprocessing is to unify the symbols of the input data and limit the operand range; the original input data are traversed to find the largest value, then the processed input data (PID) is found by subtracting the largest input value from each original input data; the preprocess transforms the original softmax function into the following form:
S
i
=
e
x
i
-
x
m
a
x
∑
j
=
1
C
e
x
j
-
x
m
a
x
(7); the PID has two characteristics: 1) all symbols of PID are negative, so possibly ignoring the sign and 2) the range of the PID is within (0, 1); therefore, the unnecessary data overflow and a possibly severe accuracy loss due to the characteristics of the exponent function are avoided).
Cardarilli and Chen are analogous art because they are from the same field of endeavor, a system and a method for approximating Softmax Functions. Therefore, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to apply the teaching of Chen to Cardarilli. Motivation for doing so would avoid t.
Claim 14
Cardarilli in view of Chen discloses all the elements as stated in Claim 1 and further discloses deriving each input number yi from a corresponding original input number xi by selecting a maximum original input number xmax from among original input numbers x, the original input numbers x being the classification output of the neural network; and for each original input number xi: subtracting xmax from xi so as to obtain a negative or zero input number yi; or subtracting xi from xmax so as to obtain a zero or positive input number yi (Chen, Section I in Pages 4-5: the softmax function is often used in the last layer of a DNN. This function has been classified as a multinomial logistic regression in probability theory and related fields; it is a nonlinear function with a discrete random variable distribution that can take n possible values and normalizes them into a range of [0, 1]; the most complex modules in the softmax function are exponent and division; existing approximate designs for the softmax layer are based on improving these two nonlinear functions; this article is an extension of our previous conference paper [40]; the format of the input data is redefined so that a 16-bit fixed-point data format provides higher precision for the LUT; a new type of efficient approximate hybrid exponent unit (AHEU) is proposed by using a dedicated Booth multiplier without loss in accuracy; under the premise of ensuring accuracy, a truncation algorithm is utilized for the approximate hybrid division unit (AHDU); Section II.A with FIG.1 in Page 6: the softmax function is always placed after the fully connected layer in DNNs due to the ability to perform classification operations to the probability distributions from large amounts of features; as shown in Fig. 1, the multichannel feature map (processed by the convolutional and the pooling layers) is expanded into a 1-D vector at the fully connected layer; the dot product is then performed with the corresponding weight vector in the fully connected layer; finally, the input data of the softmax function are formed by using the bias; after passing through the softmax layer, the output data are delivered to the softmax loss layer; Section III.A in Page 8: as the range of the exponent is [0,+∞], a data overflow may likely occur by performing an exponent operation on the original input data, and causing a precision loss; to avoid this issue, preprocessing of the input data is then required for this implementation; the purpose of preprocessing is to unify the symbols of the input data and limit the operand range; the original input data are traversed to find the largest value, then the processed input data (PID) is found by subtracting the largest input value from each original input data; the preprocess transforms the original softmax function into the following form:
S
i
=
e
x
i
-
x
m
a
x
∑
j
=
1
C
e
x
j
-
x
m
a
x
(7); the PID has two characteristics: 1) all symbols of PID are negative, so possibly ignoring the sign and 2) the range of the PID is within (0, 1); therefore, the unnecessary data overflow and a possibly severe accuracy loss due to the characteristics of the exponent function are avoided)
Claims 2-5 and 8-13 are rejected under 35 U.S.C. 103 as being unpatentable over Cardarilli in view of Chen as applied to Claim 1 above, and further in view of Wang et al. (CN 108021537 A, pub. date: 05/11/2018), hereinafter Wang.
Claim 2
Cardarilli in view of Chen discloses all the elements as stated in Claim 1 and further discloses wherein determining the binary number qi includes: for each input number yi, determining an element number zi by i i, separating the element number zi into an integral part inti and a fractional part fraci; for each fractional part fraci, determining a fraction component fc,i using a piecewise approximation of two raised to a power of a negation of the fractional part fraci; and generating the binary number qi using the fraction component fc,i and the integral part inti, the binary number qi corresponding to the input number yi and further representing an exponential value of the input number yi (Cardarilli, Before Section "Pseudo‑softmax function" in Pages 1-2: the softmax function equation is:
p
i
=
e
x
i
∑
k
=
1
N
e
x
k
(1), where
x
i
are the outputs of a machine learning network and
i
=
1
,
…
,
N
; the optimization in the hardware architectures is obtained both by the use of approximation algorithms and by the integer quantization of the arithmetic, usually by using 8 bits integers (INT8); introduce the pseudo-softmax architecture with the aim to allow for an efficient hardware implementation of the softmax layer in hardware implemented NNs and CNNs; Yuan11 proposed an implementation that uses a logarithmic transformation to avoid the division; the exponential operations are simply carried out via Look Up Tables (LUT); Geng et al.12 proposed two architectures that compute the exponential function both via LUT and linear approximation; the division is carried out by finding the closest power of 2, thus only shift operations are needed; Li et al.13 proved that LUT implementations for the exponential function are the best trade-off between precision and speed, if compared to Taylor’s series and CORDIC14 implementations; the division is performed by bit-shifting; Baptista et al.15 proposed a High Level Synthesis (HLS) FPGA implementation for a specific CNN application; the exponents of the softmax formula are split into integer and fractional parts; the integer parts are evaluated by using a ROM approach, while polynomial approximation is used for the fractional parts; Wang et al.16 proposed an interesting architecture that exploits the fact that every number can be split in integer and fractional part; the implementation avoids any straightforward division or exponential operation by using Leading One Detectors (LOD), bit shifters, and constant multipliers; Sun et al.17 proposed a FPGA serial implementation that splits every exponential operation in more operations to reduce the size of each ROM; the division is carried out via bit-shifting; Hu et al.18 proposed their Integral Stochastic Computation (ISC) to evaluate the exponent operator; the division is avoided by a logarithmic transformation; Du et al.19 proposed a tunable precision block for the exponentiation based on a variable number of LUTs; Kouretas and Paliouras20 implemented an approximated equation that takes into account only the exponents of the softmax formula and that replaces the summation with the highest input value; Di Franco et al.22 proposed a straightforward FPGA implementation of the softmax by using a linear interpolating LUT for the exponential function; Kouretas and Paliouras23 extended their previous work20 by improving the accuracy analysis by using real-world CNNs and by adding information about the ASIC implementation; Section "Pseudo‑softmax function" in Pages 2-3: in order to simplify the computation of the softmax function in Eq. (1), we introduce a new approximated expression named pseudo-softmax:
p
~
i
=
2
x
i
∑
k
=
1
N
2
x
k
(2), in which the exponent base e is replaced by 2; as in the case of the softmax function, the summation of the pseudo-softmax outputs is always equal to one; consequently, the values-
p
i
can be interpreted as probabilities; as stated in the Introduction, the hardware implementations of NN systems make use of the integer quantization, typically 8-bit integers (INT8); the reason of using powers of two
2
x
i
in Eq. (2) is that the integer numbers
x
i
can be interpreted as the exponent of floating-point (FLP) numbers, allowing for an efficient hardware implementation; according to the conventional base-2 FLP representation, a positive number
a
is represented as:
a
=
2
b
∙
1
∙
c
(3), where
b
is the integer exponent and
c
is the fractional mantissa; consequently, the pseudo-softmax function can be rewritten as
p
~
i
=
2
x
i
-
exp
s
u
m
∙
1
1
∙
mant
s
u
m
(7); the expression Eq. (7) of the pseudo-softmax function shows that the output -
p
~
i
is a FLP number with exponent
x
i
-
exp
s
u
m
, and with mantissa
1
/
1
∙
mant
s
u
m
, i.e., the reciprocal of the mantissa of the summation; the mantissa is common (constant) for all -
p
~
i
s, and it is only computed once; Section "Hardware architecture" with FIGS. 2-4 in Pages 3-5: the pseudo-softmax function in Eq. (7) is implemented by using the hardware architecture shown in Fig. 2; as stated in the Introduction, the 8-bit integers inputs
x
i
with range [−128, 127] are interpreted as the exponents of FLP numbers; the denominator of Eq. (7) is the mantissa of the FLP number sum; the outputs are unsigned FLP numbers
p
~
i
=
2
exp
o
u
t
i
∙
1
∙
mant
o
u
t
(8) represented by using 17 bits: 9-bit exponent, and 8-bit fractional mantissa with implicit integer bit (always 1); the 9-bit exponent (unbiased) guarantees for overflows for maximum values
x
i
= 127 and number of inputs N < 128; there is no representation for zero, that can be determined by comparing -pi to a sufficiently small threshold value; the negative exponent makes the floating-point number smaller than 1.0, but all output numbers are positive; therefore, the sign bit is not necessary; the unit in Fig. 2 is composed of three main blocks: a tree of FLP adders to compute
s
u
m
=
2
exp
s
u
m
∙
1
∙
mant
s
u
m
; a piece-wise linear (PWL) interpolation block to compute the reciprocal, and an array of integers subtractors computing
(
x
i
-
exp
s
u
m
)
; we opted for a binary tree of FLP adders, that is modular and easy to design; if delay (for throughput) is problematic, the binary tree can be easily pipelined, after each adder, to meet the timing constraints; the architecture of the FLP adder tree for N = 6 is shown in Fig. 3a; the
x
i
of Eq. (2) are the exponents of FLP numbers and their mantissas is 1.0; the architecture of the FLP adder24 is shown in Fig. 3b; since it operates on positive FLP numbers, its architecture is simplified; first, the exponents difference
d
is computed to find the amount of shifting necessary for the alignment of the mantissas; the largest exponent is selected as the exponent of the result; the alignment is performed by a barrel shifter (block ≫ in Fig. 3b) by shifting
d
positions to the right the mantissa of the smallest number; if
d
≥
8
, the mantissa of the smallest number is flushed to zero, and no actual addition is performed; when
d
=
0
, same exponent, the addition of the normalized mantissas results in an overflow (mant ≥ 2.0) and the result must be normalized by incrementing by one the exponent, and by dividing the mantissa by two, i.e., right-shifting the result 1 position (block ≫ 1); an additional simplification is done for the FLP adder in the first level of the adder tree (Fig. 3c); since, the input values
x
i
are power of two’s numbers and their mantissas is 1.0, there is no need to swap the mantissas (identical) according to
d
; the barrel shifter is also simplified because its input is the constant 1.0; when
d
=
0
, i.e.,
x
i
=
x
j
, the result of the addition of the two mantissas is mant = 2.0 (overflow); however, since the fractional bits are all zero, right-shifting is not necessary, and the normalization is done by incrementing the exponent of the result only; the computation of the probabilities -
p
~
i
, the mantissa is common to all -
p
~
i
s, and consequently, a single reciprocal operation is sufficient; moreover, because of the normalization, the mantissa is in the range [1, 2); for the reciprocal y = 1/x , we opted for a piece-wise linear (PWL) polynomial approximation in two intervals
y
~
=
1.59375
-
0.625
∙
x
i
f
x
<
1.5
1.125
-
0.3125
∙
x
i
f
x
≥
1.5
(9); the coefficients of the polynomials were chosen, by incremental refinements, as the closest to powers of two to simplify the hardware; by expressing in binary the coefficients of (9) and as powers of two, we have
y
~
=
1.10011
|
2
-
x
2
-
1
+
2
-
3
i
f
x
<
1.5
1.00100
|
2
-
x
2
-
2
+
2
-
4
i
f
x
≥
1.5
(10); the resulting reciprocal approximation unit is shown Fig. 4a; since the intervals in Eq. (10) are determined by
mant
s
u
m
being greater or smaller than 1.5, the MSB of the fractional part of the mantissa, bit with weight 2−1, is used to select the interpolating polynomial; Figure 4b shows the plots of
y
=
1
/
x
and of the interpolating polynomials in [1.0, 2.0)) (Chen, Section II.B in Page 6: the hardware implementation of the exponent part is usually based on an LUT to preserve the accuracy; the storage mode is generally divided into the direct storage of the exponent value (LUT-EXP) and polynomial linear function (LUT-PLF) [41], [42] (based on Taylor’s expansion); the input data provide the address of the LUT that stores the fixed-point number of
e
x
i
over a discrete subset of
x
i
; the size of LUT-EXP is determined by the number of bits in the fixed-point input
x
i
as well as its precision in the last bit; the advantage of LUT-EXP is that an approximate algorithm based on truncation can be utilized. LUT-PLF is based on Taylor’s expansion; by converting the nonlinear exponent into a small piece of a linear quadratic function in a variable and using the eigenvalue of the function as input to the LUT, it multiplies and accumulates the output to obtain the final result; Section II.C with FIG. 4 in Pages 6-7: the division can be implemented by exact restoring array dividers (EXDrs) [44]; however, the array divider requires extensive hardware due to the complexity of the exact divider cell (EXDCr) [each consisting of an exact subtractor (EXSC) and two transistors]; by simplifying multiplication and division into addition and subtraction, logarithms have been used to simplify the nonlinear function; consider two nonzero integers N1 and N2, S is the exponent, and F is the fractional part of the mantissa; then, the division can be transformed into subtraction and shifting operations as
log
2
N
1
N
2
=
S
1
-
S
2
+
log
2
F
1
-
log
2
F
2
5
; to compute
log
2
F
, linear fitting is used as
log
2
F
=
F
,
F
∈
[
1,2
]
;
log
2
F
1
-
log
2
F
2
are equivalent to (F1 − F2); the shift unit is then used to calculate the final results; the process is illustrated in Fig. 4; in the subsequent step of converting logarithm to binary, a shifter is required, and the error is then multiplied; this is then considered in the implementation of a logarithmic divider; Section III.B with FIG. 5 in Pages 8-9: the exponential function can be transformed into a product of a series of exponential values by dividing the exponential operation; the PID can be first divided into the following parts: 1) the integer part; 2) the fractional MSBs (f-MSBs); 3) the fractional LSBs (f-LSBs); in the proposed implementation of AHEU, the integer part and the f-MSB are further divided into sections; the exponential operation is implemented by an LUT; each part of the LUT stores the results of the exponential operation corresponding to a different PID part; the PID parts are used as address of the ROM, while the multiplier is used to finally calculate the value in the ROM to obtain the approximate result of the exponential operation; when implementing the AHEU, the number of bits of the f-LSB is given by I , while the total bit-width is denoted by N; therefore, the high N − I bits of the operand X calculate the exponential function values using the traditional LUT; finally, the approximate value of the exponential function part is found; PID X is given by 16-bit data, of which the first three bits are the decimal point positions, and the last 13 bits are the effective data bits. The fixed-point bit-width of this format is shown in Fig. 6)
Cardarilli in view of Chen fails to explicitly discloses determining an element number zi by multiplying the input number yi by an approximation of an inverse of a natural logarithm of two.
Wang teaches a system and a method for calculating a softmax function (Wang, Abstract), wherein determining an element number zi by multiplying the input number yi by an approximation of an inverse of a natural logarithm of two (Wang, Abstract: simplify the calculation of the exponent e by performing mathematical transformations on the function, reducing it to a constant multiplication, a 2-fold operation with a fixed input range, and a shift operation; reduce the n-fold division operation to a "highest non-zero bit detection operation", a reciprocal operation with a fixed input range, a shift operation, and n-fold multiplication; the binary exponentiation and reciprocal operations are implemented using a specially designed lookup table, which can achieve the same
precision with less storage space; significantly improve computational speed while reducing the consumption of computational and storage resources, with almost no loss of accuracy; ¶¶ [0004]-[0023] and [0043]-[0064] with FIGS. 2-3 and 5: the steps in basic digital circuits where logic units cannot directly perform operations are the exponentiation operation in step one and the division operation in step three for calculating the Softmax function; the first step of optimization considers simplifying exponentiation; simplify the calculation of the exponent e with input from negative infinity to positive infinity into one constant multiplication, one exponentiation of 2 with input range [0, 1), and one shift operation; the exponent e is transformed as follows:
e
x
=
2
log
2
e
x
=
2
x
log
2
e
; let
x
i
'
=
x
i
log
2
e
, then we have
y
i
=
2
x
i
'
; since the calculation of
x
i
'
is a multiplication with a constant (1/ln2＝1.4427), it can be replaced by a series of addition operations; next, split
x
i
'
into integer and decimal parts, such that
x
i
'
=
x
1
i
'
+
x
2
i
'
, where
x
1
i
'
is the integer part of
x
i
'
and
x
2
i
'
is the decimal part of
x
i
'
and
0
≤
x
2
i
'
<
1
; e.g., 5.75=5+0.75, -6.25=-7+0.75; the calculation of
y
i
can be expressed as
y
i
=
2
x
1
i
'
+
x
2
i
'
=
2
x
1
i
'
2
x
2
i
'
,
1
≤
i
≤
n
; due to the special nature of exponentiation by two,
2
x
1
i
'
is simply a left and right shift operation on 1, while
2
x
2
i
'
can be calculated using a lookup table; the input range is [0, 1), and the output range is [1, 2); therefore, to calculate
y
i
, first look up the value of
2
x
2
i
'
in the table, and then shift the lookup result to the left or right according to the value of
x
1
i
'
; using this method to calculate the exponent e, compared to directly calculating the exponent e, greatly reduces the range of input and output values for table lookup; step 2, as shown in Figure 3, involves performing a constant multiplication on
x
i
, multiplied by the constant log2e, resulting in
x
i
'
=
x
i
log
2
e
; this constant multiplication is equivalent to performing a series of shift and addition operations, as shown in Figure 5; step 3 is shown in Figure 3; first, determine the sign of
x
i
'
′, and then assign values to
x
1
i
'
and
x
2
i
'
; step 4, as shown in Figure 3, requires a lookup table to calculate
y
1
i
=
2
x
i
'
; after inputting the value of
x
i
'
into the lookup table, the output D1 (a four-bit binary number) is obtained; step 5 is shown in Figure 3; calculate yi, yi ≥0, with a bit width of 28 bits; its format is 21 integer bits and 7 decimal bits).
Cardarilli in view of Chen, and Wang are analogous art because they are from the same field of endeavor, a system and a method for calculating a softmax function. Therefore, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to apply the teaching of Wang to Cardarilli in view of Chen. Motivation for doing so would simplify the calculation of the exponent e (Wang, ¶¶ [0016]-[0019]).
Claim 3
Cardarilli in view of Chen and Wang discloses all the elements as stated in Claim 2 and further discloses wherein determining the fraction component fc,i includes calculating a linear approximation or a quadratic approximation of two raised to the power of the negation of the fractional part fraci by: approximating the fraction component fc,i by adding a first constant A to a first product of a second constant Band the fractional part fraci; or approximating the fraction component fc,i by adding a third constant C to a second product of a fourth constant Dand the fractional part fraci and a third product of a fifth constant E and a square of the fractional part fraci (Cardarilli, Before Section "Pseudo‑softmax function" in Pages 1-2: the softmax function equation is:
p
i
=
e
x
i
∑
k
=
1
N
e
x
k
(1), where
x
i
are the outputs of a machine learning network and
i
=
1
,
…
,
N
; the optimization in the hardware architectures is obtained both by the use of approximation algorithms and by the integer quantization of the arithmetic, usually by using 8 bits integers (INT8); introduce the pseudo-softmax architecture with the aim to allow for an efficient hardware implementation of the softmax layer in hardware implemented NNs and CNNs; Yuan11 proposed an implementation that uses a logarithmic transformation to avoid the division; the exponential operations are simply carried out via Look Up Tables (LUT); Geng et al.12 proposed two architectures that compute the exponential function both via LUT and linear approximation; the division is carried out by finding the closest power of 2, thus only shift operations are needed; Li et al.13 proved that LUT implementations for the exponential function are the best trade-off between precision and speed, if compared to Taylor’s series and CORDIC14 implementations; the division is performed by bit-shifting; Baptista et al.15 proposed a High Level Synthesis (HLS) FPGA implementation for a specific CNN application; the exponents of the softmax formula are split into integer and fractional parts; the integer parts are evaluated by using a ROM approach, while polynomial approximation is used for the fractional parts; Wang et al.16 proposed an interesting architecture that exploits the fact that every number can be split in integer and fractional part; the implementation avoids any straightforward division or exponential operation by using Leading One Detectors (LOD), bit shifters, and constant multipliers; Sun et al.17 proposed a FPGA serial implementation that splits every exponential operation in more operations to reduce the size of each ROM; the division is carried out via bit-shifting; Hu et al.18 proposed their Integral Stochastic Computation (ISC) to evaluate the exponent operator; the division is avoided by a logarithmic transformation; Du et al.19 proposed a tunable precision block for the exponentiation based on a variable number of LUTs; Kouretas and Paliouras20 implemented an approximated equation that takes into account only the exponents of the softmax formula and that replaces the summation with the highest input value; Di Franco et al.22 proposed a straightforward FPGA implementation of the softmax by using a linear interpolating LUT for the exponential function; Kouretas and Paliouras23 extended their previous work20 by improving the accuracy analysis by using real-world CNNs and by adding information about the ASIC implementation; Section "Pseudo‑softmax function" in Pages 2-3: in order to simplify the computation of the softmax function in Eq. (1), we introduce a new approximated expression named pseudo-softmax:
p
~
i
=
2
x
i
∑
k
=
1
N
2
x
k
(2), in which the exponent base e is replaced by 2; as in the case of the softmax function, the summation of the pseudo-softmax outputs is always equal to one; consequently, the values-
p
i
can be interpreted as probabilities; as stated in the Introduction, the hardware implementations of NN systems make use of the integer quantization, typically 8-bit integers (INT8); the reason of using powers of two
2
x
i
in Eq. (2) is that the integer numbers
x
i
can be interpreted as the exponent of floating-point (FLP) numbers, allowing for an efficient hardware implementation; according to the conventional base-2 FLP representation, a positive number
a
is represented as:
a
=
2
b
∙
1
∙
c
(3), where
b
is the integer exponent and
c
is the fractional mantissa; consequently, the pseudo-softmax function can be rewritten as
p
~
i
=
2
x
i
-
exp
s
u
m
∙
1
1
∙
mant
s
u
m
(7); the expression Eq. (7) of the pseudo-softmax function shows that the output -
p
~
i
is a FLP number with exponent
x
i
-
exp
s
u
m
, and with mantissa
1
/
1
∙
mant
s
u
m
, i.e., the reciprocal of the mantissa of the summation; the mantissa is common (constant) for all -
p
~
i
s, and it is only computed once; Section "Hardware architecture" with FIGS. 2-4 in Pages 3-5: the pseudo-softmax function in Eq. (7) is implemented by using the hardware architecture shown in Fig. 2; as stated in the Introduction, the 8-bit integers inputs
x
i
with range [−128, 127] are interpreted as the exponents of FLP numbers; the denominator of Eq. (7) is the mantissa of the FLP number sum; the outputs are unsigned FLP numbers
p
~
i
=
2
exp
o
u
t
i
∙
1
∙
mant
o
u
t
(8) represented by using 17 bits: 9-bit exponent, and 8-bit fractional mantissa with implicit integer bit (always 1); the 9-bit exponent (unbiased) guarantees for overflows for maximum values
x
i
= 127 and number of inputs N < 128; there is no representation for zero, that can be determined by comparing -pi to a sufficiently small threshold value; the negative exponent makes the floating-point number smaller than 1.0, but all output numbers are positive; therefore, the sign bit is not necessary; the unit in Fig. 2 is composed of three main blocks: a tree of FLP adders to compute
s
u
m
=
2
exp
s
u
m
∙
1
∙
mant
s
u
m
; a piece-wise linear (PWL) interpolation block to compute the reciprocal, and an array of integers subtractors computing
(
x
i
-
exp
s
u
m
)
; we opted for a binary tree of FLP adders, that is modular and easy to design; if delay (for throughput) is problematic, the binary tree can be easily pipelined, after each adder, to meet the timing constraints; the architecture of the FLP adder tree for N = 6 is shown in Fig. 3a; the
x
i
of Eq. (2) are the exponents of FLP numbers and their mantissas is 1.0; the architecture of the FLP adder24 is shown in Fig. 3b; since it operates on positive FLP numbers, its architecture is simplified; first, the exponents difference
d
is computed to find the amount of shifting necessary for the alignment of the mantissas; the largest exponent is selected as the exponent of the result; the alignment is performed by a barrel shifter (block ≫ in Fig. 3b) by shifting
d
positions to the right the mantissa of the smallest number; if
d
≥
8
, the mantissa of the smallest number is flushed to zero, and no actual addition is performed; when
d
=
0
, same exponent, the addition of the normalized mantissas results in an overflow (mant ≥ 2.0) and the result must be normalized by incrementing by one the exponent, and by dividing the mantissa by two, i.e., right-shifting the result 1 position (block ≫ 1); an additional simplification is done for the FLP adder in the first level of the adder tree (Fig. 3c); since, the input values
x
i
are power of two’s numbers and their mantissas is 1.0, there is no need to swap the mantissas (identical) according to
d
; the barrel shifter is also simplified because its input is the constant 1.0; when
d
=
0
, i.e.,
x
i
=
x
j
, the result of the addition of the two mantissas is mant = 2.0 (overflow); however, since the fractional bits are all zero, right-shifting is not necessary, and the normalization is done by incrementing the exponent of the result only; the computation of the probabilities -
p
~
i
, the mantissa is common to all -
p
~
i
s, and consequently, a single reciprocal operation is sufficient; moreover, because of the normalization, the mantissa is in the range [1, 2); for the reciprocal y = 1/x , we opted for a piece-wise linear (PWL) polynomial approximation in two intervals
y
~
=
1.59375
-
0.625
∙
x
i
f
x
<
1.5
1.125
-
0.3125
∙
x
i
f
x
≥
1.5
(9); the coefficients of the polynomials were chosen, by incremental refinements, as the closest to powers of two to simplify the hardware; by expressing in binary the coefficients of (9) and as powers of two, we have
y
~
=
1.10011
|
2
-
x
2
-
1
+
2
-
3
i
f
x
<
1.5
1.00100
|
2
-
x
2
-
2
+
2
-
4
i
f
x
≥
1.5
(10); the resulting reciprocal approximation unit is shown Fig. 4a; since the intervals in Eq. (10) are determined by
mant
s
u
m
being greater or smaller than 1.5, the MSB of the fractional part of the mantissa, bit with weight 2−1, is used to select the interpolating polynomial; Figure 4b shows the plots of
y
=
1
/
x
and of the interpolating polynomials in [1.0, 2.0)) (Chen, Section II.B in Page 6: the hardware implementation of the exponent part is usually based on an LUT to preserve the accuracy; the storage mode is generally divided into the direct storage of the exponent value (LUT-EXP) and polynomial linear function (LUT-PLF) [41], [42] (based on Taylor’s expansion); the input data provide the address of the LUT that stores the fixed-point number of
e
x
i
over a discrete subset of
x
i
; the size of LUT-EXP is determined by the number of bits in the fixed-point input
x
i
as well as its precision in the last bit; the advantage of LUT-EXP is that an approximate algorithm based on truncation can be utilized. LUT-PLF is based on Taylor’s expansion; by converting the nonlinear exponent into a small piece of a linear quadratic function in a variable and using the eigenvalue of the function as input to the LUT, it multiplies and accumulates the output to obtain the final result; Section II.C with FIG. 4 in Pages 6-7: the division can be implemented by exact restoring array dividers (EXDrs) [44]; however, the array divider requires extensive hardware due to the complexity of the exact divider cell (EXDCr) [each consisting of an exact subtractor (EXSC) and two transistors]; by simplifying multiplication and division into addition and subtraction, logarithms have been used to simplify the nonlinear function; consider two nonzero integers N1 and N2, S is the exponent, and F is the fractional part of the mantissa; then, the division can be transformed into subtraction and shifting operations as
log
2
N
1
N
2
=
S
1
-
S
2
+
log
2
F
1
-
log
2
F
2
5
; to compute
log
2
F
, linear fitting is used as
log
2
F
=
F
,
F
∈
[
1,2
]
;
log
2
F
1
-
log
2
F
2
are equivalent to (F1 − F2); the shift unit is then used to calculate the final results; the process is illustrated in Fig. 4; in the subsequent step of converting logarithm to binary, a shifter is required, and the error is then multiplied; this is then considered in the implementation of a logarithmic divider; Section III.B with FIG. 5 in Pages 8-9: the exponential function can be transformed into a product of a series of exponential values by dividing the exponential operation; the PID can be first divided into the following parts: 1) the integer part; 2) the fractional MSBs (f-MSBs); 3) the fractional LSBs (f-LSBs); in the proposed implementation of AHEU, the integer part and the f-MSB are further divided into sections; the exponential operation is implemented by an LUT; each part of the LUT stores the results of the exponential operation corresponding to a different PID part; the PID parts are used as address of the ROM, while the multiplier is used to finally calculate the value in the ROM to obtain the approximate result of the exponential operation; when implementing the AHEU, the number of bits of the f-LSB is given by I , while the total bit-width is denoted by N; therefore, the high N − I bits of the operand X calculate the exponential function values using the traditional LUT; finally, the approximate value of the exponential function part is found; PID X is given by 16-bit data, of which the first three bits are the decimal point positions, and the last 13 bits are the effective data bits. The fixed-point bit-width of this format is shown in Fig. 6).
Claim 4
Cardarilli in view of Chen and Wang discloses all the elements as stated in Claim 3 and further discloses wherein determining the normalized probability pi from the binary numbers qi includes: placing each binary number qi into a respective result register; summing a quantity K of result registers into a sum register; and multiplying each result register by an inverse of the sum register or dividing each result register by the sum register (Cardarilli, 1st paragraph of Page 1: the softmax function is used in the last layer in classification Neural Networks (NN) and also in Convolutional Neural Networks (CNN) to normalize the raw output of such systems; Subsection "Floating‑point adder tree" with FIGS. 3(b)-3(c) in Page 4: the architecture of the FLP adder24 is shown in Fig. 3b; when
d
=
0
, same exponent, the addition of the normalized mantissas results in an overflow (mant ≥ 2.0) and the result must be normalized by incrementing by one the exponent, and by dividing the mantissa by two, i.e., right-shifting the result 1 position (block ≫ 1); an additional simplification is done for the FLP adder in the first level of the adder tree (Fig. 3c); when
d
=
0
, i.e.,
x
i
=
x
j
, the result of the addition of the two mantissas is mant = 2.0 (overflow); however, since the fractional bits are all zero, right-shifting is not necessary, and the normalization is done by incrementing the exponent of the result only; Subsection "Piece‑wise linear reciprocal block" in Pages 4-5: the computation of the probabilities -
p
~
i
, the mantissa is common to all -
p
~
i
s, and consequently, a single reciprocal operation is sufficient; moreover, because of the normalization, the mantissa is in the range [1, 2); Section "Implementation results" with FIG. 8 in Pages 7-8: except for the PWL reciprocal block, the hardware resources are strictly related to the number of inputs and the quantization. Moreover, it can be observed how the area required for the I/O registers, the FLP adder tree, and the array of subtractors, doubles when we double the number of inputs) (Chen, Section II.A in Page 6: The softmax function can be expressed as Ean. (1), where
x
i
represents the input of real number vectors, the number of classes is represented by C, and Si represents the result of normalizing the input to a probability distribution (that remains positive due to the characteristic of the exponent)) (Wang, ¶¶ [0024]-[0033] and [0065]-[0079] with FIGS. 1 and 4: the second step of optimization considers the optimization of division operations; here we simplify n division operations into one operation to find the position of the first 1 from left to right of a fixed-point binary number excluding the sign bit, one reciprocal operation with an input value range of [0.5, 1), one shift operation, and n multiplication operations; since the divisor is the same in all n division operations, we can first find the reciprocal of F, and then calculate the product of
y
i
and this reciprocal each time; drawing on the idea of simplifying the exponent e, the reciprocal operation is considered as follows:
1
F
=
1
2
2
∙
1
k
; according to the properties of fraction calculation,
F
=
2
w
∙
k
, where w is an integer,
0.5
≤
k
≤
1
; e.g., 6.25 = 8 ´ 0.7815, -3.5 = -4 ´ 0.875, -4.3 = -0.5 ´ 0.86; if k can take any real number in [0.5, 1), theoretically all non-zero real numbers can be represented in this way, which is similar to the representation of floating-point numbers; for binary fixed-point numbers, w and k can be quickly calculated by finding the first non-zero bit from left to right, excluding the sign bit; the calculation of the reciprocal of F is exactly the same as the calculation of the exponent e: first look up the value of 1/k in the table, and then shift the value to the left or right according to the value of w; the range of input values for the lookup table here is [0.5, 1), and the range of output values is (1, 2]; similarly, the ranges of both input and output values have been greatly reduced; the third step is to optimize the range of output values for the lookup table by adopting an improved lookup table strategy for further optimization; the first two optimization steps have already greatly reduced the range of output values from the lookup table; this step further reduces its range: In the process of storing the lookup table y = g(x), the common method is to map the value of x to a memory address and use g(x) as the data stored at that address; borrowing the idea of linear fitting, here we do not store g(x), but instead store g(x) - (kx + b); Each time we access the data, we add kx + b to get the value of g(x); clearly, if the straight line y = kx + b and the curve y = g(x) are very close, the range of the output values of the lookup table will be greatly reduced, at the cost of further processing of the returned data; while compared to directly using the idea of fitting for calculation, this method can flexibly improve accuracy, at the cost of requiring more storage space; due to the special nature of the functions corresponding to the lookup table, this strategy has great advantages: the functions that need to be looked up and calculated are y1=2x, 0<x<1 and y2=1/x, 0.5≤x<1; as can be seen from the graph, curve y1 is very close to the line y = x + 1, and curve y2 is also very close to the line y = -2x + 3; the expressions of these two lines are very simple, and there is no need to perform the operation of k multiplied by x after returning the value; therefore, this operation is very simple in this solution; therefore, the function stored in lookup table one can be changed to y1=2x-x-1, with a value range of [0, 0.08607], which corresponds to [0, 0.001] in binary; the function stored in lookup table two can be changed to y2＝1/x+2x-3, with a value range of [-0.17157, 0], which corresponds to (-0.01, 0) in binary; i.e., if the same precision is used for storage and operation, this scheme reduces the bit width of data stored in lookup table one by 3 bits and the bit width of data stored in lookup table two by 1 bit; step 7, as shown in Figure 4, calculates w based on the position of the first non-zero bit in F from left to right; if the position is the nth place before the decimal point, w = n; if the position is the nth place after the decimal point, w = n-1; step 8, as shown in Figure 4, involves extracting 6 significant digits starting from the position taken in Step 7 and assigning them to k; the range of k is 000000 to 111111; step 9, as shown in Figure 4, uses lookup table 2 to calculate 1/k; step 10: k is compared with two constants to determine whether it is in the interval [001100, 101110]; if it is in the interval [001100, 101110], D2′ is D2 with a 1 added in front of it; otherwise, D(k) is D2 with a 0 added in front of it; step 11, as shown in Figure 4, assigns 1/k to 1/F; then, depending on the sign of w, perform a shift operation on 1/F: if w > 0, 1/F = 1/F < w; if w < 0, 1/F = 1/F > |w|; step 12, as shown in Figure 1, involves multiplication
f
x
i
=
1
F
*
y
i
=
1
F
*
e
x
i
).
Claim 5
Cardarilli in view of Chen and Wang discloses all the elements as stated in Claim 4 and further discloses wherein generating the binary number qi includes right shifting the fraction component fc,i by a value of the integral part inti by: storing the corresponding fraction component fc,i into the respective result register and right shifting the fraction component fc,i by the value of the integral part inti into the respective result register (Cardarilli, Before Section "Pseudo‑softmax function" in Pages 1-2: the softmax function equation is:
p
i
=
e
x
i
∑
k
=
1
N
e
x
k
(1), where
x
i
are the outputs of a machine learning network and
i
=
1
,
…
,
N
; the optimization in the hardware architectures is obtained both by the use of approximation algorithms and by the integer quantization of the arithmetic, usually by using 8 bits integers (INT8); introduce the pseudo-softmax architecture with the aim to allow for an efficient hardware implementation of the softmax layer in hardware implemented NNs and CNNs; Section "Pseudo‑softmax function" in Pages 2-3: in order to simplify the computation of the softmax function in Eq. (1), we introduce a new approximated expression named pseudo-softmax:
p
~
i
=
2
x
i
∑
k
=
1
N
2
x
k
(2), in which the exponent base e is replaced by 2; as in the case of the softmax function, the summation of the pseudo-softmax outputs is always equal to one; consequently, the values-
p
i
can be interpreted as probabilities; as stated in the Introduction, the hardware implementations of NN systems make use of the integer quantization, typically 8-bit integers (INT8); the reason of using powers of two
2
x
i
in Eq. (2) is that the integer numbers
x
i
can be interpreted as the exponent of floating-point (FLP) numbers, allowing for an efficient hardware implementation; according to the conventional base-2 FLP representation, a positive number
a
is represented as:
a
=
2
b
∙
1
∙
c
(3), where
b
is the integer exponent and
c
is the fractional mantissa; consequently, the pseudo-softmax function can be rewritten as
p
~
i
=
2
x
i
-
exp
s
u
m
∙
1
1
∙
mant
s
u
m
(7); the expression Eq. (7) of the pseudo-softmax function shows that the output -
p
~
i
is a FLP number with exponent
x
i
-
exp
s
u
m
, and with mantissa
1
/
1
∙
mant
s
u
m
, i.e., the reciprocal of the mantissa of the summation; the mantissa is common (constant) for all -
p
~
i
s, and it is only computed once; Section "Hardware architecture" with FIGS. 2-4 in Pages 3-5: the pseudo-softmax function in Eq. (7) is implemented by using the hardware architecture shown in Fig. 2; as stated in the Introduction, the 8-bit integers inputs
x
i
with range [−128, 127] are interpreted as the exponents of FLP numbers; the denominator of Eq. (7) is the mantissa of the FLP number sum; the outputs are unsigned FLP numbers
p
~
i
=
2
exp
o
u
t
i
∙
1
∙
mant
o
u
t
(8) represented by using 17 bits: 9-bit exponent, and 8-bit fractional mantissa with implicit integer bit (always 1); the 9-bit exponent (unbiased) guarantees for overflows for maximum values
x
i
= 127 and number of inputs N < 128; there is no representation for zero, that can be determined by comparing -pi to a sufficiently small threshold value; the negative exponent makes the floating-point number smaller than 1.0, but all output numbers are positive; therefore, the sign bit is not necessary; the unit in Fig. 2 is composed of three main blocks: a tree of FLP adders to compute
s
u
m
=
2
exp
s
u
m
∙
1
∙
mant
s
u
m
; a piece-wise linear (PWL) interpolation block to compute the reciprocal, and an array of integers subtractors computing
(
x
i
-
exp
s
u
m
)
; we opted for a binary tree of FLP adders, that is modular and easy to design; if delay (for throughput) is problematic, the binary tree can be easily pipelined, after each adder, to meet the timing constraints; the architecture of the FLP adder tree for N = 6 is shown in Fig. 3a; the
x
i
of Eq. (2) are the exponents of FLP numbers and their mantissas is 1.0; the architecture of the FLP adder24 is shown in Fig. 3b; since it operates on positive FLP numbers, its architecture is simplified; first, the exponents difference
d
is computed to find the amount of shifting necessary for the alignment of the mantissas; the largest exponent is selected as the exponent of the result; the alignment is performed by a barrel shifter (block ≫ in Fig. 3b) by shifting
d
positions to the right the mantissa of the smallest number; if
d
≥
8
, the mantissa of the smallest number is flushed to zero, and no actual addition is performed; when
d
=
0
, same exponent, the addition of the normalized mantissas results in an overflow (mant ≥ 2.0) and the result must be normalized by incrementing by one the exponent, and by dividing the mantissa by two, i.e., right-shifting the result 1 position (block ≫ 1); an additional simplification is done for the FLP adder in the first level of the adder tree (Fig. 3c); since, the input values
x
i
are power of two’s numbers and their mantissas is 1.0, there is no need to swap the mantissas (identical) according to
d
; the barrel shifter is also simplified because its input is the constant 1.0; when
d
=
0
, i.e.,
x
i
=
x
j
, the result of the addition of the two mantissas is mant = 2.0 (overflow); however, since the fractional bits are all zero, right-shifting is not necessary, and the normalization is done by incrementing the exponent of the result only; the computation of the probabilities -
p
~
i
, the mantissa is common to all -
p
~
i
s, and consequently, a single reciprocal operation is sufficient; moreover, because of the normalization, the mantissa is in the range [1, 2); for the reciprocal y = 1/x , we opted for a piece-wise linear (PWL) polynomial approximation in two intervals
y
~
=
1.59375
-
0.625
∙
x
i
f
x
<
1.5
1.125
-
0.3125
∙
x
i
f
x
≥
1.5
(9); the coefficients of the polynomials were chosen, by incremental refinements, as the closest to powers of two to simplify the hardware; by expressing in binary the coefficients of (9) and as powers of two, we have
y
~
=
1.10011
|
2
-
x
2
-
1
+
2
-
3
i
f
x
<
1.5
1.00100
|
2
-
x
2
-
2
+
2
-
4
i
f
x
≥
1.5
(10); the resulting reciprocal approximation unit is shown Fig. 4a; since the intervals in Eq. (10) are determined by
mant
s
u
m
being greater or smaller than 1.5, the MSB of the fractional part of the mantissa, bit with weight 2−1, is used to select the interpolating polynomial; Figure 4b shows the plots of
y
=
1
/
x
and of the interpolating polynomials in [1.0, 2.0)); Section "Implementation results" with FIG. 8 in Pages 7-8: except for the PWL reciprocal block, the hardware resources are strictly related to the number of inputs and the quantization. Moreover, it can be observed how the area required for the I/O registers, the FLP adder tree, and the array of subtractors, doubles when we double the number of inputs) (Wang, ¶¶ [0004]-[0023] and [0043]-[0064] with FIGS. 2-3 and 5: the steps in basic digital circuits where logic units cannot directly perform operations are the exponentiation operation in step one and the division operation in step three for calculating the Softmax function; the first step of optimization considers simplifying exponentiation; simplify the calculation of the exponent e with input from negative infinity to positive infinity into one constant multiplication, one exponentiation of 2 with input range [0, 1), and one shift operation; the exponent e is transformed as follows:
e
x
=
2
log
2
e
x
=
2
x
log
2
e
; let
x
i
'
=
x
i
log
2
e
, then we have
y
i
=
2
x
i
'
; since the calculation of
x
i
'
is a multiplication with a constant (1/ln2＝1.4427), it can be replaced by a series of addition operations; next, split
x
i
'
into integer and decimal parts, such that
x
i
'
=
x
1
i
'
+
x
2
i
'
, where
x
1
i
'
is the integer part of
x
i
'
and
x
2
i
'
is the decimal part of
x
i
'
and
0
≤
x
2
i
'
<
1
; e.g., 5.75=5+0.75, -6.25=-7+0.75; the calculation of
y
i
can be expressed as
y
i
=
2
x
1
i
'
+
x
2
i
'
=
2
x
1
i
'
2
x
2
i
'
,
1
≤
i
≤
n
; due to the special nature of exponentiation by two,
2
x
1
i
'
is simply a left and right shift operation on 1, while
2
x
2
i
'
can be calculated using a lookup table; the input range is [0, 1), and the output range is [1, 2); therefore, to calculate
y
i
, first look up the value of
2
x
2
i
'
in the table, and then shift the lookup result to the left or right according to the value of
x
1
i
'
; using this method to calculate the exponent e, compared to directly calculating the exponent e, greatly reduces the range of input and output values for table lookup; step 2, as shown in Figure 3, involves performing a constant multiplication on
x
i
, multiplied by the constant log2e, resulting in
x
i
'
=
x
i
log
2
e
; this constant multiplication is equivalent to performing a series of shift and addition operations, as shown in Figure 5; step 3 is shown in Figure 3; first, determine the sign of
x
i
'
′, and then assign values to
x
1
i
'
and
x
2
i
'
; step 4, as shown in Figure 3, requires a lookup table to calculate
y
1
i
=
2
x
i
'
; after inputting the value of
x
i
'
into the lookup table, the output D1 (a four-bit binary number) is obtained; step 5 is shown in Figure 3; calculate yi, yi ≥0, with a bit width of 28 bits; its format is 21 integer bits and 7 decimal bits).
Claim 8
Cardarilli in view of Chen and Wang discloses all the elements as stated in Claim 4 and further discloses wherein determining the element number zi by multiplying the input number yi by the approximation of the inverse of the natural logarithm of two includes: storing each input number yi in binary form into a first N-bit register; right shifting the input number yi by N/2-1 creating a right-shifted input number yi,T and storing the right-shifted input number yi,T into a second N/2-bit register according to: in response to the input number yi, after right shifting by N/2-1, not overflowing the second N/2-bit register, fitting the right-shifted input number yi,T into the second N/2-bit register, or in response to the input number yi, after right shifting by N/2-1, overflowing the second N/2-bit register, saturating the second N/2-bit register; providing a constant value in binary form into a third N/2-bit register, the constant value being approximately equal to the inverse of the natural logarithm of two minus one scaled by 2N/2-1; calculating a product of the second N/2-bit register and the third N/2-bit register and storing the product into a fourth N-bit register; and determining a sum of the first N-bit register and the fourth N-bit register by implementing a saturating addition to obtain the element number zi and storing the sum in a fifth N-bit register (Cardarilli, Before Section "Pseudo‑softmax function" in Pages 1-2: the softmax function equation is:
p
i
=
e
x
i
∑
k
=
1
N
e
x
k
(1), where
x
i
are the outputs of a machine learning network and
i
=
1
,
…
,
N
; the optimization in the hardware architectures is obtained both by the use of approximation algorithms and by the integer quantization of the arithmetic, usually by using 8 bits integers (INT8); introduce the pseudo-softmax architecture with the aim to allow for an efficient hardware implementation of the softmax layer in hardware implemented NNs and CNNs; Section "Pseudo‑softmax function" in Pages 2-3: in order to simplify the computation of the softmax function in Eq. (1), we introduce a new approximated expression named pseudo-softmax:
p
~
i
=
2
x
i
∑
k
=
1
N
2
x
k
(2), in which the exponent base e is replaced by 2; as in the case of the softmax function, the summation of the pseudo-softmax outputs is always equal to one; consequently, the values-
p
i
can be interpreted as probabilities; as stated in the Introduction, the hardware implementations of NN systems make use of the integer quantization, typically 8-bit integers (INT8); the reason of using powers of two
2
x
i
in Eq. (2) is that the integer numbers
x
i
can be interpreted as the exponent of floating-point (FLP) numbers, allowing for an efficient hardware implementation; according to the conventional base-2 FLP representation, a positive number
a
is represented as:
a
=
2
b
∙
1
∙
c
(3), where
b
is the integer exponent and
c
is the fractional mantissa; consequently, the pseudo-softmax function can be rewritten as
p
~
i
=
2
x
i
-
exp
s
u
m
∙
1
1
∙
mant
s
u
m
(7); the expression Eq. (7) of the pseudo-softmax function shows that the output -
p
~
i
is a FLP number with exponent
x
i
-
exp
s
u
m
, and with mantissa
1
/
1
∙
mant
s
u
m
, i.e., the reciprocal of the mantissa of the summation; the mantissa is common (constant) for all -
p
~
i
s, and it is only computed once; Section "Hardware architecture" with FIGS. 2-4 in Pages 3-5: the pseudo-softmax function in Eq. (7) is implemented by using the hardware architecture shown in Fig. 2; as stated in the Introduction, the 8-bit integers inputs
x
i
with range [−128, 127] are interpreted as the exponents of FLP numbers; the denominator of Eq. (7) is the mantissa of the FLP number sum; the outputs are unsigned FLP numbers
p
~
i
=
2
exp
o
u
t
i
∙
1
∙
mant
o
u
t
(8) represented by using 17 bits: 9-bit exponent, and 8-bit fractional mantissa with implicit integer bit (always 1); the 9-bit exponent (unbiased) guarantees for overflows for maximum values
x
i
= 127 and number of inputs N < 128; there is no representation for zero, that can be determined by comparing -pi to a sufficiently small threshold value; the negative exponent makes the floating-point number smaller than 1.0, but all output numbers are positive; therefore, the sign bit is not necessary; the unit in Fig. 2 is composed of three main blocks: a tree of FLP adders to compute
s
u
m
=
2
exp
s
u
m
∙
1
∙
mant
s
u
m
; a piece-wise linear (PWL) interpolation block to compute the reciprocal, and an array of integers subtractors computing
(
x
i
-
exp
s
u
m
)
; we opted for a binary tree of FLP adders, that is modular and easy to design; if delay (for throughput) is problematic, the binary tree can be easily pipelined, after each adder, to meet the timing constraints; the architecture of the FLP adder tree for N = 6 is shown in Fig. 3a; the
x
i
of Eq. (2) are the exponents of FLP numbers and their mantissas is 1.0; the architecture of the FLP adder24 is shown in Fig. 3b; since it operates on positive FLP numbers, its architecture is simplified; first, the exponents difference
d
is computed to find the amount of shifting necessary for the alignment of the mantissas; the largest exponent is selected as the exponent of the result; the alignment is performed by a barrel shifter (block ≫ in Fig. 3b) by shifting
d
positions to the right the mantissa of the smallest number; if
d
≥
8
, the mantissa of the smallest number is flushed to zero, and no actual addition is performed; when
d
=
0
, same exponent, the addition of the normalized mantissas results in an overflow (mant ≥ 2.0) and the result must be normalized by incrementing by one the exponent, and by dividing the mantissa by two, i.e., right-shifting the result 1 position (block ≫ 1); an additional simplification is done for the FLP adder in the first level of the adder tree (Fig. 3c); since, the input values
x
i
are power of two’s numbers and their mantissas is 1.0, there is no need to swap the mantissas (identical) according to
d
; the barrel shifter is also simplified because its input is the constant 1.0; when
d
=
0
, i.e.,
x
i
=
x
j
, the result of the addition of the two mantissas is mant = 2.0 (overflow); however, since the fractional bits are all zero, right-shifting is not necessary, and the normalization is done by incrementing the exponent of the result only; the computation of the probabilities -
p
~
i
, the mantissa is common to all -
p
~
i
s, and consequently, a single reciprocal operation is sufficient; moreover, because of the normalization, the mantissa is in the range [1, 2); for the reciprocal y = 1/x , we opted for a piece-wise linear (PWL) polynomial approximation in two intervals
y
~
=
1.59375
-
0.625
∙
x
i
f
x
<
1.5
1.125
-
0.3125
∙
x
i
f
x
≥
1.5
(9); the coefficients of the polynomials were chosen, by incremental refinements, as the closest to powers of two to simplify the hardware; by expressing in binary the coefficients of (9) and as powers of two, we have
y
~
=
1.10011
|
2
-
x
2
-
1
+
2
-
3
i
f
x
<
1.5
1.00100
|
2
-
x
2
-
2
+
2
-
4
i
f
x
≥
1.5
(10); the resulting reciprocal approximation unit is shown Fig. 4a; since the intervals in Eq. (10) are determined by
mant
s
u
m
being greater or smaller than 1.5, the MSB of the fractional part of the mantissa, bit with weight 2−1, is used to select the interpolating polynomial; Figure 4b shows the plots of
y
=
1
/
x
and of the interpolating polynomials in [1.0, 2.0)); Section "Implementation results" with FIG. 8 in Pages 7-8: except for the PWL reciprocal block, the hardware resources are strictly related to the number of inputs and the quantization. Moreover, it can be observed how the area required for the I/O registers, the FLP adder tree, and the array of subtractors, doubles when we double the number of inputs) (Wang, ¶¶ [0004]-[0023] and [0043]-[0064] with FIGS. 2-3 and 5: the steps in basic digital circuits where logic units cannot directly perform operations are the exponentiation operation in step one and the division operation in step three for calculating the Softmax function; the first step of optimization considers simplifying exponentiation; simplify the calculation of the exponent e with input from negative infinity to positive infinity into one constant multiplication, one exponentiation of 2 with input range [0, 1), and one shift operation; the exponent e is transformed as follows:
e
x
=
2
log
2
e
x
=
2
x
log
2
e
; let
x
i
'
=
x
i
log
2
e
, then we have
y
i
=
2
x
i
'
; since the calculation of
x
i
'
is a multiplication with a constant (1/ln2＝1.4427), it can be replaced by a series of addition operations; next, split
x
i
'
into integer and decimal parts, such that
x
i
'
=
x
1
i
'
+
x
2
i
'
, where
x
1
i
'
is the integer part of
x
i
'
and
x
2
i
'
is the decimal part of
x
i
'
and
0
≤
x
2
i
'
<
1
; e.g., 5.75=5+0.75, -6.25=-7+0.75; the calculation of
y
i
can be expressed as
y
i
=
2
x
1
i
'
+
x
2
i
'
=
2
x
1
i
'
2
x
2
i
'
,
1
≤
i
≤
n
; due to the special nature of exponentiation by two,
2
x
1
i
'
is simply a left and right shift operation on 1, while
2
x
2
i
'
can be calculated using a lookup table; the input range is [0, 1), and the output range is [1, 2); therefore, to calculate
y
i
, first look up the value of
2
x
2
i
'
in the table, and then shift the lookup result to the left or right according to the value of
x
1
i
'
; using this method to calculate the exponent e, compared to directly calculating the exponent e, greatly reduces the range of input and output values for table lookup; step 2, as shown in Figure 3, involves performing a constant multiplication on
x
i
, multiplied by the constant log2e, resulting in
x
i
'
=
x
i
log
2
e
; this constant multiplication is equivalent to performing a series of shift and addition operations, as shown in Figure 5; step 3 is shown in Figure 3; first, determine the sign of
x
i
'
′, and then assign values to
x
1
i
'
and
x
2
i
'
; step 4, as shown in Figure 3, requires a lookup table to calculate
y
1
i
=
2
x
i
'
; after inputting the value of
x
i
'
into the lookup table, the output D1 (a four-bit binary number) is obtained; step 5 is shown in Figure 3; calculate yi, yi ≥0, with a bit width of 28 bits; its format is 21 integer bits and 7 decimal bits).
Claim 9
Cardarilli in view of Chen and Wang discloses all the elements as stated in Claim 8 and further discloses wherein determining the element number zi by multiplying the input number yi by the approximation of the inverse of the natural logarithm of two further includes: rounding the right-shifted input number yi,T by adding 2N/2-2 to the input number yi before right shifting by N/2-1 (Cardarilli, Before Section "Pseudo‑softmax function" in Pages 1-2: the softmax function equation is:
p
i
=
e
x
i
∑
k
=
1
N
e
x
k
(1), where
x
i
are the outputs of a machine learning network and
i
=
1
,
…
,
N
; the optimization in the hardware architectures is obtained both by the use of approximation algorithms and by the integer quantization of the arithmetic, usually by using 8 bits integers (INT8); introduce the pseudo-softmax architecture with the aim to allow for an efficient hardware implementation of the softmax layer in hardware implemented NNs and CNNs; Section "Pseudo‑softmax function" in Pages 2-3: in order to simplify the computation of the softmax function in Eq. (1), we introduce a new approximated expression named pseudo-softmax:
p
~
i
=
2
x
i
∑
k
=
1
N
2
x
k
(2), in which the exponent base e is replaced by 2; as in the case of the softmax function, the summation of the pseudo-softmax outputs is always equal to one; consequently, the values-
p
i
can be interpreted as probabilities; as stated in the Introduction, the hardware implementations of NN systems make use of the integer quantization, typically 8-bit integers (INT8); the reason of using powers of two
2
x
i
in Eq. (2) is that the integer numbers
x
i
can be interpreted as the exponent of floating-point (FLP) numbers, allowing for an efficient hardware implementation; according to the conventional base-2 FLP representation, a positive number
a
is represented as:
a
=
2
b
∙
1
∙
c
(3), where
b
is the integer exponent and
c
is the fractional mantissa; consequently, the pseudo-softmax function can be rewritten as
p
~
i
=
2
x
i
-
exp
s
u
m
∙
1
1
∙
mant
s
u
m
(7); the expression Eq. (7) of the pseudo-softmax function shows that the output -
p
~
i
is a FLP number with exponent
x
i
-
exp
s
u
m
, and with mantissa
1
/
1
∙
mant
s
u
m
, i.e., the reciprocal of the mantissa of the summation; the mantissa is common (constant) for all -
p
~
i
s, and it is only computed once; Section "Hardware architecture" with FIGS. 2-4 in Pages 3-5: the pseudo-softmax function in Eq. (7) is implemented by using the hardware architecture shown in Fig. 2; as stated in the Introduction, the 8-bit integers inputs
x
i
with range [−128, 127] are interpreted as the exponents of FLP numbers; the denominator of Eq. (7) is the mantissa of the FLP number sum; the outputs are unsigned FLP numbers
p
~
i
=
2
exp
o
u
t
i
∙
1
∙
mant
o
u
t
(8) represented by using 17 bits: 9-bit exponent, and 8-bit fractional mantissa with implicit integer bit (always 1); the 9-bit exponent (unbiased) guarantees for overflows for maximum values
x
i
= 127 and number of inputs N < 128; there is no representation for zero, that can be determined by comparing -pi to a sufficiently small threshold value; the negative exponent makes the floating-point number smaller than 1.0, but all output numbers are positive; therefore, the sign bit is not necessary; the unit in Fig. 2 is composed of three main blocks: a tree of FLP adders to compute
s
u
m
=
2
exp
s
u
m
∙
1
∙
mant
s
u
m
; a piece-wise linear (PWL) interpolation block to compute the reciprocal, and an array of integers subtractors computing
(
x
i
-
exp
s
u
m
)
; we opted for a binary tree of FLP adders, that is modular and easy to design; if delay (for throughput) is problematic, the binary tree can be easily pipelined, after each adder, to meet the timing constraints; the architecture of the FLP adder tree for N = 6 is shown in Fig. 3a; the
x
i
of Eq. (2) are the exponents of FLP numbers and their mantissas is 1.0; the architecture of the FLP adder24 is shown in Fig. 3b; since it operates on positive FLP numbers, its architecture is simplified; first, the exponents difference
d
is computed to find the amount of shifting necessary for the alignment of the mantissas; the largest exponent is selected as the exponent of the result; the alignment is performed by a barrel shifter (block ≫ in Fig. 3b) by shifting
d
positions to the right the mantissa of the smallest number; if
d
≥
8
, the mantissa of the smallest number is flushed to zero, and no actual addition is performed; when
d
=
0
, same exponent, the addition of the normalized mantissas results in an overflow (mant ≥ 2.0) and the result must be normalized by incrementing by one the exponent, and by dividing the mantissa by two, i.e., right-shifting the result 1 position (block ≫ 1); an additional simplification is done for the FLP adder in the first level of the adder tree (Fig. 3c); since, the input values
x
i
are power of two’s numbers and their mantissas is 1.0, there is no need to swap the mantissas (identical) according to
d
; the barrel shifter is also simplified because its input is the constant 1.0; when
d
=
0
, i.e.,
x
i
=
x
j
, the result of the addition of the two mantissas is mant = 2.0 (overflow); however, since the fractional bits are all zero, right-shifting is not necessary, and the normalization is done by incrementing the exponent of the result only; the computation of the probabilities -
p
~
i
, the mantissa is common to all -
p
~
i
s, and consequently, a single reciprocal operation is sufficient; moreover, because of the normalization, the mantissa is in the range [1, 2); for the reciprocal y = 1/x , we opted for a piece-wise linear (PWL) polynomial approximation in two intervals
y
~
=
1.59375
-
0.625
∙
x
i
f
x
<
1.5
1.125
-
0.3125
∙
x
i
f
x
≥
1.5
(9); the coefficients of the polynomials were chosen, by incremental refinements, as the closest to powers of two to simplify the hardware; by expressing in binary the coefficients of (9) and as powers of two, we have
y
~
=
1.10011
|
2
-
x
2
-
1
+
2
-
3
i
f
x
<
1.5
1.00100
|
2
-
x
2
-
2
+
2
-
4
i
f
x
≥
1.5
(10); the resulting reciprocal approximation unit is shown Fig. 4a; since the intervals in Eq. (10) are determined by
mant
s
u
m
being greater or smaller than 1.5, the MSB of the fractional part of the mantissa, bit with weight 2−1, is used to select the interpolating polynomial; Figure 4b shows the plots of
y
=
1
/
x
and of the interpolating polynomials in [1.0, 2.0)) (Chen, Abstract in Page 4: in IDHS, a novel Booth multiplier is utilized for the hybrid scheme to improve the partial product generation and compression, while the truncated implementation is applied to the divider unit; Section I in Pages 4-5: under the premise of ensuring accuracy, a truncation algorithm is utilized for the approximate hybrid division unit (AHDU); Section II.B in Page 6: the advantage of LUT-EXP is that an approximate algorithm based on truncation can be utilized. LUT-PLF is based on Taylor’s expansion; Section II.C in Pages 6-7: Chen et al. [44] have proposed replacement schemes with different shapes (vertical, horizontal square truncation, and triangular replacement); another approximation method is based on structure truncation [46]; truncation includes the complete deletion/removal of at least one unit; like approximate replacement schemes, truncation can also utilize configurations with four different shapes; this type of approximate solution has the advantages of low hardware and power consumption; however, it also incurs a significant loss of accuracy for the overall design; Section III.B with FIGS. 5-7 in Pages 8-10: prior to further multiplying with the output from ROM3, the product is truncated by taking the most significant 16 bits; finally, the product of the LUTs and the first-order Taylor’s expansion of the exponent based on the LSB are multiplied; the result is given by 32 bits; this is then stored in the accumulator and truncated to 16 bits (and stored in the register for AHDU); Section III.C with FIGS. 8 in Pages 9-11: so even if the entire module is truncated, the computational accuracy of the restored remainder array divider module is not affected; therefore, if the divisor can be truncated, the hardware can be significantly reduced; then, the all-zero array on the left half can be turned into a (40 − 32) × (40 − 32 + 1) array; Fig. 10(b) shows the results of truncated EXDr; this requires implementing the truncation of the 40 − 32 + 1 significant bits of the divisor; the LOD module is used to check the MSB and assign nine effective bits to the divisor of the EXDr; this not only effectively saves the number of subtractors in the array divider, but it also saves unnecessary hardware by multiplexing the LOD; the improved AHDU is shown in Fig. 11) (Wang, ¶¶ [0004]-[0023] and [0043]-[0064] with FIGS. 2-3 and 5: the steps in basic digital circuits where logic units cannot directly perform operations are the exponentiation operation in step one and the division operation in step three for calculating the Softmax function; the first step of optimization considers simplifying exponentiation; simplify the calculation of the exponent e with input from negative infinity to positive infinity into one constant multiplication, one exponentiation of 2 with input range [0, 1), and one shift operation; the exponent e is transformed as follows:
e
x
=
2
log
2
e
x
=
2
x
log
2
e
; let
x
i
'
=
x
i
log
2
e
, then we have
y
i
=
2
x
i
'
; since the calculation of
x
i
'
is a multiplication with a constant (1/ln2＝1.4427), it can be replaced by a series of addition operations; next, split
x
i
'
into integer and decimal parts, such that
x
i
'
=
x
1
i
'
+
x
2
i
'
, where
x
1
i
'
is the integer part of
x
i
'
and
x
2
i
'
is the decimal part of
x
i
'
and
0
≤
x
2
i
'
<
1
; e.g., 5.75=5+0.75, -6.25=-7+0.75; the calculation of
y
i
can be expressed as
y
i
=
2
x
1
i
'
+
x
2
i
'
=
2
x
1
i
'
2
x
2
i
'
,
1
≤
i
≤
n
; due to the special nature of exponentiation by two,
2
x
1
i
'
is simply a left and right shift operation on 1, while
2
x
2
i
'
can be calculated using a lookup table; the input range is [0, 1), and the output range is [1, 2); therefore, to calculate
y
i
, first look up the value of
2
x
2
i
'
in the table, and then shift the lookup result to the left or right according to the value of
x
1
i
'
; using this method to calculate the exponent e, compared to directly calculating the exponent e, greatly reduces the range of input and output values for table lookup; step 2, as shown in Figure 3, involves performing a constant multiplication on
x
i
, multiplied by the constant log2e, resulting in
x
i
'
=
x
i
log
2
e
; this constant multiplication is equivalent to performing a series of shift and addition operations, as shown in Figure 5; step 3 is shown in Figure 3; first, determine the sign of
x
i
'
′, and then assign values to
x
1
i
'
and
x
2
i
'
; step 4, as shown in Figure 3, requires a lookup table to calculate
y
1
i
=
2
x
i
'
; after inputting the value of
x
i
'
into the lookup table, the output D1 (a four-bit binary number) is obtained; step 5 is shown in Figure 3; calculate yi, yi ≥0, with a bit width of 28 bits; its format is 21 integer bits and 7 decimal bits).
Claim 10
Cardarilli in view of Chen and Wang discloses all the elements as stated in Claim 2 and further discloses wherein determining the element number zi by multiplying the input number yi by the approximation of the inverse of the natural logarithm of two includes: storing each input number yi in binary form into a first N-bit register; right shifting the input number yi by N/2-2 creating a right-shifted input number yi,T and storing the right-shifted input number yi,T into a second N-bit register; providing a constant value in binary form scaled by 2N/2-2 into a third N-bit register, the constant value being approximately equal to the inverse of the natural logarithm of two minus one; calculating a product of the second N-bit register and the third N-bit register and storing the product into a fourth N-bit register; and determining a sum of the first N-bit register and the fourth N-bit register by implementing a saturating addition to obtain the element number zi scaled by an input scaling factor Sin and storing the sum in a fifth N-bit register (Cardarilli, Before Section "Pseudo‑softmax function" in Pages 1-2: the softmax function equation is:
p
i
=
e
x
i
∑
k
=
1
N
e
x
k
(1), where
x
i
are the outputs of a machine learning network and
i
=
1
,
…
,
N
; the optimization in the hardware architectures is obtained both by the use of approximation algorithms and by the integer quantization of the arithmetic, usually by using 8 bits integers (INT8); introduce the pseudo-softmax architecture with the aim to allow for an efficient hardware implementation of the softmax layer in hardware implemented NNs and CNNs; Section "Pseudo‑softmax function" in Pages 2-3: in order to simplify the computation of the softmax function in Eq. (1), we introduce a new approximated expression named pseudo-softmax:
p
~
i
=
2
x
i
∑
k
=
1
N
2
x
k
(2), in which the exponent base e is replaced by 2; as in the case of the softmax function, the summation of the pseudo-softmax outputs is always equal to one; consequently, the values-
p
i
can be interpreted as probabilities; as stated in the Introduction, the hardware implementations of NN systems make use of the integer quantization, typically 8-bit integers (INT8); the reason of using powers of two
2
x
i
in Eq. (2) is that the integer numbers
x
i
can be interpreted as the exponent of floating-point (FLP) numbers, allowing for an efficient hardware implementation; according to the conventional base-2 FLP representation, a positive number
a
is represented as:
a
=
2
b
∙
1
∙
c
(3), where
b
is the integer exponent and
c
is the fractional mantissa; consequently, the pseudo-softmax function can be rewritten as
p
~
i
=
2
x
i
-
exp
s
u
m
∙
1
1
∙
mant
s
u
m
(7); the expression Eq. (7) of the pseudo-softmax function shows that the output -
p
~
i
is a FLP number with exponent
x
i
-
exp
s
u
m
, and with mantissa
1
/
1
∙
mant
s
u
m
, i.e., the reciprocal of the mantissa of the summation; the mantissa is common (constant) for all -
p
~
i
s, and it is only computed once; Section "Hardware architecture" with FIGS. 2-4 in Pages 3-5: the pseudo-softmax function in Eq. (7) is implemented by using the hardware architecture shown in Fig. 2; as stated in the Introduction, the 8-bit integers inputs
x
i
with range [−128, 127] are interpreted as the exponents of FLP numbers; the denominator of Eq. (7) is the mantissa of the FLP number sum; the outputs are unsigned FLP numbers
p
~
i
=
2
exp
o
u
t
i
∙
1
∙
mant
o
u
t
(8) represented by using 17 bits: 9-bit exponent, and 8-bit fractional mantissa with implicit integer bit (always 1); the 9-bit exponent (unbiased) guarantees for overflows for maximum values
x
i
= 127 and number of inputs N < 128; there is no representation for zero, that can be determined by comparing -pi to a sufficiently small threshold value; the negative exponent makes the floating-point number smaller than 1.0, but all output numbers are positive; therefore, the sign bit is not necessary; the unit in Fig. 2 is composed of three main blocks: a tree of FLP adders to compute
s
u
m
=
2
exp
s
u
m
∙
1
∙
mant
s
u
m
; a piece-wise linear (PWL) interpolation block to compute the reciprocal, and an array of integers subtractors computing
(
x
i
-
exp
s
u
m
)
; we opted for a binary tree of FLP adders, that is modular and easy to design; if delay (for throughput) is problematic, the binary tree can be easily pipelined, after each adder, to meet the timing constraints; the architecture of the FLP adder tree for N = 6 is shown in Fig. 3a; the
x
i
of Eq. (2) are the exponents of FLP numbers and their mantissas is 1.0; the architecture of the FLP adder24 is shown in Fig. 3b; since it operates on positive FLP numbers, its architecture is simplified; first, the exponents difference
d
is computed to find the amount of shifting necessary for the alignment of the mantissas; the largest exponent is selected as the exponent of the result; the alignment is performed by a barrel shifter (block ≫ in Fig. 3b) by shifting
d
positions to the right the mantissa of the smallest number; if
d
≥
8
, the mantissa of the smallest number is flushed to zero, and no actual addition is performed; when
d
=
0
, same exponent, the addition of the normalized mantissas results in an overflow (mant ≥ 2.0) and the result must be normalized by incrementing by one the exponent, and by dividing the mantissa by two, i.e., right-shifting the result 1 position (block ≫ 1); an additional simplification is done for the FLP adder in the first level of the adder tree (Fig. 3c); since, the input values
x
i
are power of two’s numbers and their mantissas is 1.0, there is no need to swap the mantissas (identical) according to
d
; the barrel shifter is also simplified because its input is the constant 1.0; when
d
=
0
, i.e.,
x
i
=
x
j
, the result of the addition of the two mantissas is mant = 2.0 (overflow); however, since the fractional bits are all zero, right-shifting is not necessary, and the normalization is done by incrementing the exponent of the result only; the computation of the probabilities -
p
~
i
, the mantissa is common to all -
p
~
i
s, and consequently, a single reciprocal operation is sufficient; moreover, because of the normalization, the mantissa is in the range [1, 2); for the reciprocal y = 1/x , we opted for a piece-wise linear (PWL) polynomial approximation in two intervals
y
~
=
1.59375
-
0.625
∙
x
i
f
x
<
1.5
1.125
-
0.3125
∙
x
i
f
x
≥
1.5
(9); the coefficients of the polynomials were chosen, by incremental refinements, as the closest to powers of two to simplify the hardware; by expressing in binary the coefficients of (9) and as powers of two, we have
y
~
=
1.10011
|
2
-
x
2
-
1
+
2
-
3
i
f
x
<
1.5
1.00100
|
2
-
x
2
-
2
+
2
-
4
i
f
x
≥
1.5
(10); the resulting reciprocal approximation unit is shown Fig. 4a; since the intervals in Eq. (10) are determined by
mant
s
u
m
being greater or smaller than 1.5, the MSB of the fractional part of the mantissa, bit with weight 2−1, is used to select the interpolating polynomial; Figure 4b shows the plots of
y
=
1
/
x
and of the interpolating polynomials in [1.0, 2.0)); Section "Implementation results" with FIG. 8 in Pages 7-8: except for the PWL reciprocal block, the hardware resources are strictly related to the number of inputs and the quantization. Moreover, it can be observed how the area required for the I/O registers, the FLP adder tree, and the array of subtractors, doubles when we double the number of inputs) (Wang, ¶¶ [0004]-[0023] and [0043]-[0064] with FIGS. 2-3 and 5: the steps in basic digital circuits where logic units cannot directly perform operations are the exponentiation operation in step one and the division operation in step three for calculating the Softmax function; the first step of optimization considers simplifying exponentiation; simplify the calculation of the exponent e with input from negative infinity to positive infinity into one constant multiplication, one exponentiation of 2 with input range [0, 1), and one shift operation; the exponent e is transformed as follows:
e
x
=
2
log
2
e
x
=
2
x
log
2
e
; let
x
i
'
=
x
i
log
2
e
, then we have
y
i
=
2
x
i
'
; since the calculation of
x
i
'
is a multiplication with a constant (1/ln2＝1.4427), it can be replaced by a series of addition operations; next, split
x
i
'
into integer and decimal parts, such that
x
i
'
=
x
1
i
'
+
x
2
i
'
, where
x
1
i
'
is the integer part of
x
i
'
and
x
2
i
'
is the decimal part of
x
i
'
and
0
≤
x
2
i
'
<
1
; e.g., 5.75=5+0.75, -6.25=-7+0.75; the calculation of
y
i
can be expressed as
y
i
=
2
x
1
i
'
+
x
2
i
'
=
2
x
1
i
'
2
x
2
i
'
,
1
≤
i
≤
n
; due to the special nature of exponentiation by two,
2
x
1
i
'
is simply a left and right shift operation on 1, while
2
x
2
i
'
can be calculated using a lookup table; the input range is [0, 1), and the output range is [1, 2); therefore, to calculate
y
i
, first look up the value of
2
x
2
i
'
in the table, and then shift the lookup result to the left or right according to the value of
x
1
i
'
; using this method to calculate the exponent e, compared to directly calculating the exponent e, greatly reduces the range of input and output values for table lookup; step 2, as shown in Figure 3, involves performing a constant multiplication on
x
i
, multiplied by the constant log2e, resulting in
x
i
'
=
x
i
log
2
e
; this constant multiplication is equivalent to performing a series of shift and addition operations, as shown in Figure 5; step 3 is shown in Figure 3; first, determine the sign of
x
i
'
′, and then assign values to
x
1
i
'
and
x
2
i
'
; step 4, as shown in Figure 3, requires a lookup table to calculate
y
1
i
=
2
x
i
'
; after inputting the value of
x
i
'
into the lookup table, the output D1 (a four-bit binary number) is obtained; step 5 is shown in Figure 3; calculate yi, yi ≥0, with a bit width of 28 bits; its format is 21 integer bits and 7 decimal bits).
Claim 11
Cardarilli in view of Chen and Wang discloses all the elements as stated in Claim 10 and further discloses wherein determining the element number zi by multiplying the input number yi by the approximation of the inverse of the natural logarithm of two further includes: rounding the right-shifted input number yi,T by adding 2N/2-3 to the input number yi before right shifting by N/2-2 (Cardarilli, Before Section "Pseudo‑softmax function" in Pages 1-2: the softmax function equation is:
p
i
=
e
x
i
∑
k
=
1
N
e
x
k
(1), where
x
i
are the outputs of a machine learning network and
i
=
1
,
…
,
N
; the optimization in the hardware architectures is obtained both by the use of approximation algorithms and by the integer quantization of the arithmetic, usually by using 8 bits integers (INT8); introduce the pseudo-softmax architecture with the aim to allow for an efficient hardware implementation of the softmax layer in hardware implemented NNs and CNNs; Section "Pseudo‑softmax function" in Pages 2-3: in order to simplify the computation of the softmax function in Eq. (1), we introduce a new approximated expression named pseudo-softmax:
p
~
i
=
2
x
i
∑
k
=
1
N
2
x
k
(2), in which the exponent base e is replaced by 2; as in the case of the softmax function, the summation of the pseudo-softmax outputs is always equal to one; consequently, the values-
p
i
can be interpreted as probabilities; as stated in the Introduction, the hardware implementations of NN systems make use of the integer quantization, typically 8-bit integers (INT8); the reason of using powers of two
2
x
i
in Eq. (2) is that the integer numbers
x
i
can be interpreted as the exponent of floating-point (FLP) numbers, allowing for an efficient hardware implementation; according to the conventional base-2 FLP representation, a positive number
a
is represented as:
a
=
2
b
∙
1
∙
c
(3), where
b
is the integer exponent and
c
is the fractional mantissa; consequently, the pseudo-softmax function can be rewritten as
p
~
i
=
2
x
i
-
exp
s
u
m
∙
1
1
∙
mant
s
u
m
(7); the expression Eq. (7) of the pseudo-softmax function shows that the output -
p
~
i
is a FLP number with exponent
x
i
-
exp
s
u
m
, and with mantissa
1
/
1
∙
mant
s
u
m
, i.e., the reciprocal of the mantissa of the summation; the mantissa is common (constant) for all -
p
~
i
s, and it is only computed once; Section "Hardware architecture" with FIGS. 2-4 in Pages 3-5: the pseudo-softmax function in Eq. (7) is implemented by using the hardware architecture shown in Fig. 2; as stated in the Introduction, the 8-bit integers inputs
x
i
with range [−128, 127] are interpreted as the exponents of FLP numbers; the denominator of Eq. (7) is the mantissa of the FLP number sum; the outputs are unsigned FLP numbers
p
~
i
=
2
exp
o
u
t
i
∙
1
∙
mant
o
u
t
(8) represented by using 17 bits: 9-bit exponent, and 8-bit fractional mantissa with implicit integer bit (always 1); the 9-bit exponent (unbiased) guarantees for overflows for maximum values
x
i
= 127 and number of inputs N < 128; there is no representation for zero, that can be determined by comparing -pi to a sufficiently small threshold value; the negative exponent makes the floating-point number smaller than 1.0, but all output numbers are positive; therefore, the sign bit is not necessary; the unit in Fig. 2 is composed of three main blocks: a tree of FLP adders to compute
s
u
m
=
2
exp
s
u
m
∙
1
∙
mant
s
u
m
; a piece-wise linear (PWL) interpolation block to compute the reciprocal, and an array of integers subtractors computing
(
x
i
-
exp
s
u
m
)
; we opted for a binary tree of FLP adders, that is modular and easy to design; if delay (for throughput) is problematic, the binary tree can be easily pipelined, after each adder, to meet the timing constraints; the architecture of the FLP adder tree for N = 6 is shown in Fig. 3a; the
x
i
of Eq. (2) are the exponents of FLP numbers and their mantissas is 1.0; the architecture of the FLP adder24 is shown in Fig. 3b; since it operates on positive FLP numbers, its architecture is simplified; first, the exponents difference
d
is computed to find the amount of shifting necessary for the alignment of the mantissas; the largest exponent is selected as the exponent of the result; the alignment is performed by a barrel shifter (block ≫ in Fig. 3b) by shifting
d
positions to the right the mantissa of the smallest number; if
d
≥
8
, the mantissa of the smallest number is flushed to zero, and no actual addition is performed; when
d
=
0
, same exponent, the addition of the normalized mantissas results in an overflow (mant ≥ 2.0) and the result must be normalized by incrementing by one the exponent, and by dividing the mantissa by two, i.e., right-shifting the result 1 position (block ≫ 1); an additional simplification is done for the FLP adder in the first level of the adder tree (Fig. 3c); since, the input values
x
i
are power of two’s numbers and their mantissas is 1.0, there is no need to swap the mantissas (identical) according to
d
; the barrel shifter is also simplified because its input is the constant 1.0; when
d
=
0
, i.e.,
x
i
=
x
j
, the result of the addition of the two mantissas is mant = 2.0 (overflow); however, since the fractional bits are all zero, right-shifting is not necessary, and the normalization is done by incrementing the exponent of the result only; the computation of the probabilities -
p
~
i
, the mantissa is common to all -
p
~
i
s, and consequently, a single reciprocal operation is sufficient; moreover, because of the normalization, the mantissa is in the range [1, 2); for the reciprocal y = 1/x , we opted for a piece-wise linear (PWL) polynomial approximation in two intervals
y
~
=
1.59375
-
0.625
∙
x
i
f
x
<
1.5
1.125
-
0.3125
∙
x
i
f
x
≥
1.5
(9); the coefficients of the polynomials were chosen, by incremental refinements, as the closest to powers of two to simplify the hardware; by expressing in binary the coefficients of (9) and as powers of two, we have
y
~
=
1.10011
|
2
-
x
2
-
1
+
2
-
3
i
f
x
<
1.5
1.00100
|
2
-
x
2
-
2
+
2
-
4
i
f
x
≥
1.5
(10); the resulting reciprocal approximation unit is shown Fig. 4a; since the intervals in Eq. (10) are determined by
mant
s
u
m
being greater or smaller than 1.5, the MSB of the fractional part of the mantissa, bit with weight 2−1, is used to select the interpolating polynomial; Figure 4b shows the plots of
y
=
1
/
x
and of the interpolating polynomials in [1.0, 2.0)) (Chen, Abstract in Page 4: in IDHS, a novel Booth multiplier is utilized for the hybrid scheme to improve the partial product generation and compression, while the truncated implementation is applied to the divider unit; Section I in Pages 4-5: under the premise of ensuring accuracy, a truncation algorithm is utilized for the approximate hybrid division unit (AHDU); Section II.B in Page 6: the advantage of LUT-EXP is that an approximate algorithm based on truncation can be utilized. LUT-PLF is based on Taylor’s expansion; Section II.C in Pages 6-7: Chen et al. [44] have proposed replacement schemes with different shapes (vertical, horizontal square truncation, and triangular replacement); another approximation method is based on structure truncation [46]; truncation includes the complete deletion/removal of at least one unit; like approximate replacement schemes, truncation can also utilize configurations with four different shapes; this type of approximate solution has the advantages of low hardware and power consumption; however, it also incurs a significant loss of accuracy for the overall design; Section III.B with FIGS. 5-7 in Pages 8-10: prior to further multiplying with the output from ROM3, the product is truncated by taking the most significant 16 bits; finally, the product of the LUTs and the first-order Taylor’s expansion of the exponent based on the LSB are multiplied; the result is given by 32 bits; this is then stored in the accumulator and truncated to 16 bits (and stored in the register for AHDU); Section III.C with FIGS. 8 in Pages 9-11: so even if the entire module is truncated, the computational accuracy of the restored remainder array divider module is not affected; therefore, if the divisor can be truncated, the hardware can be significantly reduced; then, the all-zero array on the left half can be turned into a (40 − 32) × (40 − 32 + 1) array; Fig. 10(b) shows the results of truncated EXDr; this requires implementing the truncation of the 40 − 32 + 1 significant bits of the divisor; the LOD module is used to check the MSB and assign nine effective bits to the divisor of the EXDr; this not only effectively saves the number of subtractors in the array divider, but it also saves unnecessary hardware by multiplexing the LOD; the improved AHDU is shown in Fig. 11) (Wang, ¶¶ [0004]-[0023] and [0043]-[0064] with FIGS. 2-3 and 5: the steps in basic digital circuits where logic units cannot directly perform operations are the exponentiation operation in step one and the division operation in step three for calculating the Softmax function; the first step of optimization considers simplifying exponentiation; simplify the calculation of the exponent e with input from negative infinity to positive infinity into one constant multiplication, one exponentiation of 2 with input range [0, 1), and one shift operation; the exponent e is transformed as follows:
e
x
=
2
log
2
e
x
=
2
x
log
2
e
; let
x
i
'
=
x
i
log
2
e
, then we have
y
i
=
2
x
i
'
; since the calculation of
x
i
'
is a multiplication with a constant (1/ln2＝1.4427), it can be replaced by a series of addition operations; next, split
x
i
'
into integer and decimal parts, such that
x
i
'
=
x
1
i
'
+
x
2
i
'
, where
x
1
i
'
is the integer part of
x
i
'
and
x
2
i
'
is the decimal part of
x
i
'
and
0
≤
x
2
i
'
<
1
; e.g., 5.75=5+0.75, -6.25=-7+0.75; the calculation of
y
i
can be expressed as
y
i
=
2
x
1
i
'
+
x
2
i
'
=
2
x
1
i
'
2
x
2
i
'
,
1
≤
i
≤
n
; due to the special nature of exponentiation by two,
2
x
1
i
'
is simply a left and right shift operation on 1, while
2
x
2
i
'
can be calculated using a lookup table; the input range is [0, 1), and the output range is [1, 2); therefore, to calculate
y
i
, first look up the value of
2
x
2
i
'
in the table, and then shift the lookup result to the left or right according to the value of
x
1
i
'
; using this method to calculate the exponent e, compared to directly calculating the exponent e, greatly reduces the range of input and output values for table lookup; step 2, as shown in Figure 3, involves performing a constant multiplication on
x
i
, multiplied by the constant log2e, resulting in
x
i
'
=
x
i
log
2
e
; this constant multiplication is equivalent to performing a series of shift and addition operations, as shown in Figure 5; step 3 is shown in Figure 3; first, determine the sign of
x
i
'
′, and then assign values to
x
1
i
'
and
x
2
i
'
; step 4, as shown in Figure 3, requires a lookup table to calculate
y
1
i
=
2
x
i
'
; after inputting the value of
x
i
'
into the lookup table, the output D1 (a four-bit binary number) is obtained; step 5 is shown in Figure 3; calculate yi, yi ≥0, with a bit width of 28 bits; its format is 21 integer bits and 7 decimal bits)..
Claim 12
Cardarilli in view of Chen and Wang discloses all the elements as stated in Claim 9 and further discloses wherein determining the normalized probability pi includes: summing the result registers into a sum register; obtaining a normalization factor fn by scaling a value V100, the value V100 obtained by setting to 1 all bits in each result register, by a normalization scaling factor Sn; and applying the normalization factor fn to each result register with an inverse scaling by the normalization scaling factor Sn to obtain a normalized binary number qi_n (Cardarilli, 1st paragraph of Page 1: the softmax function is used in the last layer in classification Neural Networks (NN) and also in Convolutional Neural Networks (CNN) to normalize the raw output of such systems; Subsection "Floating‑point adder tree" with FIGS. 3(b)-3(c) in Page 4: the architecture of the FLP adder24 is shown in Fig. 3b; when
d
=
0
, same exponent, the addition of the normalized mantissas results in an overflow (mant ≥ 2.0) and the result must be normalized by incrementing by one the exponent, and by dividing the mantissa by two, i.e., right-shifting the result 1 position (block ≫ 1); an additional simplification is done for the FLP adder in the first level of the adder tree (Fig. 3c); when
d
=
0
, i.e.,
x
i
=
x
j
, the result of the addition of the two mantissas is mant = 2.0 (overflow); however, since the fractional bits are all zero, right-shifting is not necessary, and the normalization is done by incrementing the exponent of the result only; Subsection "Piece‑wise linear reciprocal block" in Pages 4-5: the computation of the probabilities -
p
~
i
, the mantissa is common to all -
p
~
i
s, and consequently, a single reciprocal operation is sufficient; moreover, because of the normalization, the mantissa is in the range [1, 2); Section "Implementation results" with FIG. 8 in Pages 7-8: except for the PWL reciprocal block, the hardware resources are strictly related to the number of inputs and the quantization. Moreover, it can be observed how the area required for the I/O registers, the FLP adder tree, and the array of subtractors, doubles when we double the number of inputs) (Chen, Section II.A in Page 6: The softmax function can be expressed as Ean. (1), where
x
i
represents the input of real number vectors, the number of classes is represented by C, and Si represents the result of normalizing the input to a probability distribution (that remains positive due to the characteristic of the exponent)) (Wang, ¶¶ [0024]-[0033] and [0065]-[0079] with FIGS. 1 and 4: the second step of optimization considers the optimization of division operations; here we simplify n division operations into one operation to find the position of the first 1 from left to right of a fixed-point binary number excluding the sign bit, one reciprocal operation with an input value range of [0.5, 1), one shift operation, and n multiplication operations; since the divisor is the same in all n division operations, we can first find the reciprocal of F, and then calculate the product of
y
i
and this reciprocal each time; drawing on the idea of simplifying the exponent e, the reciprocal operation is considered as follows:
1
F
=
1
2
2
∙
1
k
; according to the properties of fraction calculation,
F
=
2
w
∙
k
, where w is an integer,
0.5
≤
k
≤
1
; e.g., 6.25 = 8 ´ 0.7815, -3.5 = -4 ´ 0.875, -4.3 = -0.5 ´ 0.86; if k can take any real number in [0.5, 1), theoretically all non-zero real numbers can be represented in this way, which is similar to the representation of floating-point numbers; for binary fixed-point numbers, w and k can be quickly calculated by finding the first non-zero bit from left to right, excluding the sign bit; the calculation of the reciprocal of F is exactly the same as the calculation of the exponent e: first look up the value of 1/k in the table, and then shift the value to the left or right according to the value of w; the range of input values for the lookup table here is [0.5, 1), and the range of output values is (1, 2]; similarly, the ranges of both input and output values have been greatly reduced; the third step is to optimize the range of output values for the lookup table by adopting an improved lookup table strategy for further optimization; the first two optimization steps have already greatly reduced the range of output values from the lookup table; this step further reduces its range: In the process of storing the lookup table y = g(x), the common method is to map the value of x to a memory address and use g(x) as the data stored at that address; borrowing the idea of linear fitting, here we do not store g(x), but instead store g(x) - (kx + b); Each time we access the data, we add kx + b to get the value of g(x); clearly, if the straight line y = kx + b and the curve y = g(x) are very close, the range of the output values of the lookup table will be greatly reduced, at the cost of further processing of the returned data; while compared to directly using the idea of fitting for calculation, this method can flexibly improve accuracy, at the cost of requiring more storage space; due to the special nature of the functions corresponding to the lookup table, this strategy has great advantages: the functions that need to be looked up and calculated are y1=2x, 0<x<1 and y2=1/x, 0.5≤x<1; as can be seen from the graph, curve y1 is very close to the line y = x + 1, and curve y2 is also very close to the line y = -2x + 3; the expressions of these two lines are very simple, and there is no need to perform the operation of k multiplied by x after returning the value; therefore, this operation is very simple in this solution; therefore, the function stored in lookup table one can be changed to y1=2x-x-1, with a value range of [0, 0.08607], which corresponds to [0, 0.001] in binary; the function stored in lookup table two can be changed to y2＝1/x+2x-3, with a value range of [-0.17157, 0], which corresponds to (-0.01, 0) in binary; i.e., if the same precision is used for storage and operation, this scheme reduces the bit width of data stored in lookup table one by 3 bits and the bit width of data stored in lookup table two by 1 bit; step 7, as shown in Figure 4, calculates w based on the position of the first non-zero bit in F from left to right; if the position is the nth place before the decimal point, w = n; if the position is the nth place after the decimal point, w = n-1; step 8, as shown in Figure 4, involves extracting 6 significant digits starting from the position taken in Step 7 and assigning them to k; the range of k is 000000 to 111111; step 9, as shown in Figure 4, uses lookup table 2 to calculate 1/k; step 10: k is compared with two constants to determine whether it is in the interval [001100, 101110]; if it is in the interval [001100, 101110], D2′ is D2 with a 1 added in front of it; otherwise, D(k) is D2 with a 0 added in front of it; step 11, as shown in Figure 4, assigns 1/k to 1/F; then, depending on the sign of w, perform a shift operation on 1/F: if w > 0, 1/F = 1/F < w; if w < 0, 1/F = 1/F > |w|; step 12, as shown in Figure 1, involves multiplication
f
x
i
=
1
F
*
y
i
=
1
F
*
e
x
i
)
Claim 13
Cardarilli in view of Chen and Wang discloses all the elements as stated in Claim 4 and further discloses wherein the binary number qi is generated in the result register in a form of an IEEE 754 floating-point number including an exponent and a mantissa, wherein the exponent is a combination of the integral part inti in binary form and IEEE 754 exponent bias and the mantissa is derived from the fraction component fc,i (Cardarilli, Before Section "Pseudo‑softmax function" in Pages 1-2: the softmax function equation is:
p
i
=
e
x
i
∑
k
=
1
N
e
x
k
(1), where
x
i
are the outputs of a machine learning network and
i
=
1
,
…
,
N
; the optimization in the hardware architectures is obtained both by the use of approximation algorithms and by the integer quantization of the arithmetic, usually by using 8 bits integers (INT8); introduce the pseudo-softmax architecture with the aim to allow for an efficient hardware implementation of the softmax layer in hardware implemented NNs and CNNs; Section "Pseudo‑softmax function" in Pages 2-3: in order to simplify the computation of the softmax function in Eq. (1), we introduce a new approximated expression named pseudo-softmax:
p
~
i
=
2
x
i
∑
k
=
1
N
2
x
k
(2), in which the exponent base e is replaced by 2; as in the case of the softmax function, the summation of the pseudo-softmax outputs is always equal to one; consequently, the values-
p
i
can be interpreted as probabilities; as stated in the Introduction, the hardware implementations of NN systems make use of the integer quantization, typically 8-bit integers (INT8); the reason of using powers of two
2
x
i
in Eq. (2) is that the integer numbers
x
i
can be interpreted as the exponent of floating-point (FLP) numbers, allowing for an efficient hardware implementation; according to the conventional base-2 FLP representation, a positive number
a
is represented as:
a
=
2
b
∙
1
∙
c
(3), where
b
is the integer exponent and
c
is the fractional mantissa; consequently, the pseudo-softmax function can be rewritten as
p
~
i
=
2
x
i
-
exp
s
u
m
∙
1
1
∙
mant
s
u
m
(7); the expression Eq. (7) of the pseudo-softmax function shows that the output -
p
~
i
is a FLP number with exponent
x
i
-
exp
s
u
m
, and with mantissa
1
/
1
∙
mant
s
u
m
, i.e., the reciprocal of the mantissa of the summation; the mantissa is common (constant) for all -
p
~
i
s, and it is only computed once; Section "Hardware architecture" with FIGS. 2-4 in Pages 3-5: the pseudo-softmax function in Eq. (7) is implemented by using the hardware architecture shown in Fig. 2; as stated in the Introduction, the 8-bit integers inputs
x
i
with range [−128, 127] are interpreted as the exponents of FLP numbers; the denominator of Eq. (7) is the mantissa of the FLP number sum; the outputs are unsigned FLP numbers
p
~
i
=
2
exp
o
u
t
i
∙
1
∙
mant
o
u
t
(8) represented by using 17 bits: 9-bit exponent, and 8-bit fractional mantissa with implicit integer bit (always 1); the 9-bit exponent (unbiased) guarantees for overflows for maximum values
x
i
= 127 and number of inputs N < 128; there is no representation for zero, that can be determined by comparing -pi to a sufficiently small threshold value; the negative exponent makes the floating-point number smaller than 1.0, but all output numbers are positive; therefore, the sign bit is not necessary; the unit in Fig. 2 is composed of three main blocks: a tree of FLP adders to compute
s
u
m
=
2
exp
s
u
m
∙
1
∙
mant
s
u
m
; a piece-wise linear (PWL) interpolation block to compute the reciprocal, and an array of integers subtractors computing
(
x
i
-
exp
s
u
m
)
; we opted for a binary tree of FLP adders, that is modular and easy to design; if delay (for throughput) is problematic, the binary tree can be easily pipelined, after each adder, to meet the timing constraints; the architecture of the FLP adder tree for N = 6 is shown in Fig. 3a; the
x
i
of Eq. (2) are the exponents of FLP numbers and their mantissas is 1.0; the architecture of the FLP adder24 is shown in Fig. 3b; since it operates on positive FLP numbers, its architecture is simplified; first, the exponents difference
d
is computed to find the amount of shifting necessary for the alignment of the mantissas; the largest exponent is selected as the exponent of the result; the alignment is performed by a barrel shifter (block ≫ in Fig. 3b) by shifting
d
positions to the right the mantissa of the smallest number; if
d
≥
8
, the mantissa of the smallest number is flushed to zero, and no actual addition is performed; when
d
=
0
, same exponent, the addition of the normalized mantissas results in an overflow (mant ≥ 2.0) and the result must be normalized by incrementing by one the exponent, and by dividing the mantissa by two, i.e., right-shifting the result 1 position (block ≫ 1); an additional simplification is done for the FLP adder in the first level of the adder tree (Fig. 3c); since, the input values
x
i
are power of two’s numbers and their mantissas is 1.0, there is no need to swap the mantissas (identical) according to
d
; the barrel shifter is also simplified because its input is the constant 1.0; when
d
=
0
, i.e.,
x
i
=
x
j
, the result of the addition of the two mantissas is mant = 2.0 (overflow); however, since the fractional bits are all zero, right-shifting is not necessary, and the normalization is done by incrementing the exponent of the result only; the computation of the probabilities -
p
~
i
, the mantissa is common to all -
p
~
i
s, and consequently, a single reciprocal operation is sufficient; moreover, because of the normalization, the mantissa is in the range [1, 2); for the reciprocal y = 1/x , we opted for a piece-wise linear (PWL) polynomial approximation in two intervals
y
~
=
1.59375
-
0.625
∙
x
i
f
x
<
1.5
1.125
-
0.3125
∙
x
i
f
x
≥
1.5
(9); the coefficients of the polynomials were chosen, by incremental refinements, as the closest to powers of two to simplify the hardware; by expressing in binary the coefficients of (9) and as powers of two, we have
y
~
=
1.10011
|
2
-
x
2
-
1
+
2
-
3
i
f
x
<
1.5
1.00100
|
2
-
x
2
-
2
+
2
-
4
i
f
x
≥
1.5
(10); the resulting reciprocal approximation unit is shown Fig. 4a; since the intervals in Eq. (10) are determined by
mant
s
u
m
being greater or smaller than 1.5, the MSB of the fractional part of the mantissa, bit with weight 2−1, is used to select the interpolating polynomial; Figure 4b shows the plots of
y
=
1
/
x
and of the interpolating polynomials in [1.0, 2.0)).
Claims 6-7 are rejected under 35 U.S.C. 103 as being unpatentable over Cardarilli in view of Chen as applied to Claim 1 above, and further in view of Gao et al. ("Design and Implementation of an Approximate Softmax Layer for Deep Neural Networks", 2020 IEEE International Symposium on Circuits and Systems (ISCAS), Oct 12-14, 2020, pp. 1-5), hereinafter Gao.
Claim 6
Cardarilli in view of Chen discloses all the elements as stated in Claim 1 except failing to explicitly disclose wherein each input number yi is scaled by an input scaling factor Sin and stored in a first N-bit register.
Gao teaches a system and a method to approximate Softmax Layer for DNN (Gao, Title and Abstract), wherein each input number yi is scaled by an input scaling factor Sin and stored in a first N-bit register (Gao, Abstract in Page 1: propose new approximate hardware architectures for both the exponent and the division units; compared with the state-of-the-art designs, the proposed approximate softmax design consumes significantly less resources and also achieves high performance while maintaining a very high accuracy; Section I in Page 1: the convolution layer is used to extract features from the input; the pooling layer compresses the scale of features to simplify the network computational complexity and extract the main features; the full connection layer performs a one-dimensional operation on the input; the classifier is used to classify the overall feature values; among neural network structures, the softmax function is widely used due to its unique characteristics; the softmax function is usually used in the last layer of a DNN; it is a function of the distribution of discrete random variables that can take n possible values and normalizes the distribution; approximate computing is introduced into the design methodology to achieve the goals of high performance and low power by relaxing the requirement of accuracy; propose an efficient approximate softmax architecture and also implement it on FPGA; a new hardware architecture for the exponent unit is proposed by using approximate LUTs; the proposed exponent unit is divided into several parts that are implemented by RAMs; it uses the Taylor series expansion to perform approximate calculations in the least significant bit data; the division is transformed as simple shifting and subtraction operations and an approximate result is generated by simplifying the remainder operation; the hardware implementation of the proposed approximate softmax function is provided and compared with the state-of-the-art designs; Section III with FIGS. 1-2 in Page 2: the proposed overall architecture for the softmax function is shown in Fig 1; it consists of EXPUs, DIVUs and accumulator modules, new designs for EXPU and DIVU are proposed; a comparison of accuracy among different fixed point schemes is presented; the results are shown in Table I, we choose the 16-bits width in the proposed design; the output of the accumulator and the input data width of DIVU have been set to 8 bits; the other parts of the implementation are set to 16 bits (including 1 sign bit, 4 integer bits, 11 fractional bits). The fixed-point bit-width of this work is shown in Fig. 2; in most popular DNNs, the softmax layer is the last layer of the network, so the inputs of the softmax layer must be scaled to make sure that the distribution of the input data can be mapped to an appropriate processing range; by subtracting the largest input value, the range of the EXPU should be set to avoid overflow and possibly a severe accuracy loss; to implement this step in the hardware implementation, we obtain all input data prior to find the largest value; Section III with FIGS. 3-4 in Pages 3-4: divide the input of the EXPU into several parts: integer part, fractional most significant bits (MSB), and fractional least significant bits (LSB); instead of using LUTs to implement the whole EXPU, the polynomial approximation based on the Taylor-Maclaurin expansion method is utilized in the proposed design; as the fractional LSB is small, so we can use the following approximation:
e
x
≈
1
+
x
(6); this process is illustrated in Fig. 3; compared with the conventional LUT based design, the proposed design reduces area while retaining a high accuracy; a pipeline version for the EXPU can also be designed, so that it can have a shorter critical path and increase the operating frequency of the architecture; for the multiplier of the EXPU, a RADIX-8 based 32-bit pipelined multiplier using carry-look ahead (CLA) [22] is selected; the division and multiplication are inverse operations; multiplication can be implemented by a shifter and an adder, while division can be implemented by a shifter and a subtractor; to replace the DIVU with a shifter and a subtractor, we first need to employ a leading one detector (LOD) for the divisor and dividend; examples are shown in TABLE II; after LOD, a logarithm operation is performed on the division; then the division can be transformed into subtraction and shifting operations as in Eqn. (8); to compute log2F, linear fitting is used as in Eqn. (9); so log2(F1) – log2(F2) can be changed to (F1 – F2); the shift unit is then used to get the final results; this process is illustrated in Fig 4 as an example; in the proposed design, the divisor data width has been set to 8-bits, while the dividend is 16-bits; therefore, the remainder is omitted in the logarithmic conversion, and added to the final results to achieve an approximate operation).
Cardarilli in view of Chen, and Gao are analogous art because they are from the same field of endeavor, a system and a method to approximate Softmax Layer for DNN. Therefore, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to apply the teaching of Gao to Cardarilli in view of Chen. Motivation for doing so would map input data to an appropriate processing range so that overflow and possibly a severe accuracy loss are avoided (Gao, Section III.B in Page 2).
Claim 7
Cardarilli in view of Chen and Gao discloses all the elements as stated in Claim 6 and further discloses wherein the input scaling factor Sin is determined based on expected smallest and largest values of the input numbers yi and a size N of the first registers (Gao, Abstract in Page 1: propose new approximate hardware architectures for both the exponent and the division units; compared with the state-of-the-art designs, the proposed approximate softmax design consumes significantly less resources and also achieves high performance while maintaining a very high accuracy; Section I in Page 1: the convolution layer is used to extract features from the input; the pooling layer compresses the scale of features to simplify the network computational complexity and extract the main features; the full connection layer performs a one-dimensional operation on the input; the classifier is used to classify the overall feature values; among neural network structures, the softmax function is widely used due to its unique characteristics; the softmax function is usually used in the last layer of a DNN; it is a function of the distribution of discrete random variables that can take n possible values and normalizes the distribution; approximate computing is introduced into the design methodology to achieve the goals of high performance and low power by relaxing the requirement of accuracy; propose an efficient approximate softmax architecture and also implement it on FPGA; a new hardware architecture for the exponent unit is proposed by using approximate LUTs; the proposed exponent unit is divided into several parts that are implemented by RAMs; it uses the Taylor series expansion to perform approximate calculations in the least significant bit data; the division is transformed as simple shifting and subtraction operations and an approximate result is generated by simplifying the remainder operation; the hardware implementation of the proposed approximate softmax function is provided and compared with the state-of-the-art designs; Section III with FIGS. 1-2 in Page 2: the proposed overall architecture for the softmax function is shown in Fig 1; it consists of EXPUs, DIVUs and accumulator modules, new designs for EXPU and DIVU are proposed; a comparison of accuracy among different fixed point schemes is presented; the results are shown in Table I, we choose the 16-bits width in the proposed design; the output of the accumulator and the input data width of DIVU have been set to 8 bits; the other parts of the implementation are set to 16 bits (including 1 sign bit, 4 integer bits, 11 fractional bits). The fixed-point bit-width of this work is shown in Fig. 2; in most popular DNNs, the softmax layer is the last layer of the network, so the inputs of the softmax layer must be scaled to make sure that the distribution of the input data can be mapped to an appropriate processing range; by subtracting the largest input value, the range of the EXPU should be set to avoid overflow and possibly a severe accuracy loss; to implement this step in the hardware implementation, we obtain all input data prior to find the largest value; Section III with FIGS. 3-4 in Pages 3-4: divide the input of the EXPU into several parts: integer part, fractional most significant bits (MSB), and fractional least significant bits (LSB); instead of using LUTs to implement the whole EXPU, the polynomial approximation based on the Taylor-Maclaurin expansion method is utilized in the proposed design; as the fractional LSB is small, so we can use the following approximation:
e
x
≈
1
+
x
(6); this process is illustrated in Fig. 3; compared with the conventional LUT based design, the proposed design reduces area while retaining a high accuracy; a pipeline version for the EXPU can also be designed, so that it can have a shorter critical path and increase the operating frequency of the architecture; for the multiplier of the EXPU, a RADIX-8 based 32-bit pipelined multiplier using carry-look ahead (CLA) [22] is selected; the division and multiplication are inverse operations; multiplication can be implemented by a shifter and an adder, while division can be implemented by a shifter and a subtractor; to replace the DIVU with a shifter and a subtractor, we first need to employ a leading one detector (LOD) for the divisor and dividend; examples are shown in TABLE II; after LOD, a logarithm operation is performed on the division; then the division can be transformed into subtraction and shifting operations as in Eqn. (8); to compute log2F, linear fitting is used as in Eqn. (9); so log2(F1) – log2(F2) can be changed to (F1 – F2); the shift unit is then used to get the final results; this process is illustrated in Fig 4 as an example; in the proposed design, the divisor data width has been set to 8-bits, while the dividend is 16-bits; therefore, the remainder is omitted in the logarithmic conversion, and added to the final results to achieve an approximate operation).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
YAMANO et al. (US 2024/0104166 A1, filed on 01/19/2022) discloses in ABSTRACT that a maximum value of an input value obtained by a comparison circuit 403 is subtracted from each input value by a subtraction circuit 404, an approximate value of an exponential function value corresponding to divided values a1, a2, and a3 obtained by slicing the obtained difference value a for each bit range is read from look up tables table1, table2, and table3 by a look up table reference circuit 406, and is multiplied by a multiplication circuit 408 to calculate an approximate value of the exponential function value having the difference value a as an exponent; at the time of multiplication, a fraction is rounded off, and the number of bits is equalized by a right shift operation; using a total value of the approximate values obtained by a summing circuit 409, each approximate value is divided by the divider circuit 410 to obtain an approximate value of the softmax function value; and in this way, a look up table size used for approximation calculation of the exponential function value of the softmax function can be suppressed without extremely deviating a sign of an error using a fixed-point number or an integer as the input value. YAMANO further discloses in ¶¶ [0053]-[0089] with FIGS. 4-6, 7A-B, and 8A-B that the softmax layer 318 calculates the probability for each class from the output data of the fully-connected layer 317 using the softmax function; the input data output by the fully-connected layer 317 and received by the softmax function approximation calculation device 200 is a floating-point number, and a quantization circuit 402 executes quantization processing for converting the input data of the floating-point number into data of a fixed-point number; next, the comparison circuit 403 compares the data of the fixed-point number output from the quantization circuit 402 with each other, and specifies the data of the maximum fixed-point number (data of the maximum value); a subtraction circuit 404 subtracts the maximum value from each data; the softmax function is a nonlinear function represented using an exponential function having Napier's constant e as a base as in the following Formula (1); therefore, even if a common bias value k is subtracted from all variables x1, x2 , …, and xN to obtain (x1-k), (x2-k), …, and (xN-k), the function value of the softmax function does not change as illustrated in the following Formula (2); therefore, even if the subtraction circuit 404 calculates the function value of the softmax function using the difference value obtained by subtracting the maximum value from each data, the calculated function value is the same as the function value of the softmax function calculated using the original data without subtracting the maximum value; a data division circuit 405 slices a difference value obtained by subtracting the maximum value from each data to a predetermined bit width; the exponential function can also rewrite the exponential function of the sum of the exponents to the product of the exponential functions according to the exponential law; a look up table (LUT) reference circuit 406 reads the values of the bit fields of the upper 4 bits, the middle 4 bits, and the lower 3 bits by replacing them with bit fields each representing an integer; the look up table 407 is divided into look up tables table1, table2, and table3 for each of the divided values a1, a2, and a3, and stores an approximate value of the exponential function value (hereinafter, the "approximate value of the exponential function value" is simply referred to as an "exponential function value") having the divided values a1, a2, and a3 as exponential values; when the look up table reference circuit 406 reads, from the look up tables table1, table2, and table3, exponential function values b1, b2, and b3 having exponential values obtained by adding negative signs to the divided values a1, a2, and a3, respectively, a multiplication circuit 408 multiplies the exponential function values b1, b2, and b3; in a case where the exponential function value stored in the look up table 407 is 8-bit data, the number of bits required to represent the multiplication value of the exponential function values b2 and b3 increases to be 16-bit data; when the number of bits increases in this manner, a processing load and a storage capacity required for calculation increase, which is not preferable; therefore, a right shift operation is performed every time the multiplication is performed; a summing circuit 409 adds the multiplication value calculated for each piece of input data to calculate a total value; a divider circuit 410 calculates an approximate value of the softmax function value by dividing the multiplication value calculated for each piece of input data by the total value calculated by the summing circuit 409; the approximate value of the calculated softmax function value corresponds to the probability 319 for each class output by the softmax layer 318; in the above, description has been made to the case where the maximum value specified by the comparison circuit 403 from the data output by the quantization circuit 402 is used as the bias value k to be subtracted from each data in Formula (2); however, it goes without saying that the present disclosure is not limited to such a case, and a value other than the maximum value may be used as the bias value k;
Any inquiry concerning this communication or earlier communications from the examiner should be directed to HWEI-MIN LU whose telephone number is (313)446-4913. The examiner can normally be reached Mon - Fri: 9:00 AM - 6:00 PM EST.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Mariela D. Reyes can be reached at (571) 270-1006. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/HWEI-MIN LU/Primary Examiner, Art Unit 2142
Prosecution Insights