US2023334285A1PendingUtilityA1
Quantization for neural network computation
Assignee: GOVERNING COUNCIL UNIV TORONTOPriority: Sep 23, 2020Filed: Sep 21, 2021Published: Oct 19, 2023
Est. expirySep 23, 2040(~14.2 yrs left)· nominal 20-yr term from priority
G06N 3/0495G06N 3/0499G06N 3/04G06N 3/063G06N 3/045Y02D10/00G06F 7/5443G06F 40/40
52
PatentIndex Score
0
Cited by
0
References
0
Claims
Abstract
A method for memory storage including storing a neural network by storing values of the neural network each as a reference to a representative value; and, in some embodiments, storing additional values of the neural network. Each of the representative values can be generated by assigning each of the values of the neural network to a cluster; and for each cluster, selecting a centroid from the cluster. The method can include performing one or more multiply-accumulate operations A 1 B 1 + . . . +A n B n on input vectors A and input vectors B, by accumulating input vectors A to an accumulated sum of input vectors A per input vector B having the same representative value and subsequently multiplying each of the accumulated sums of input vectors A by the representative value of the input vector B. A system is also described, and a method for configuring memory according to a data structure.
Claims
exact text as granted — not AI-modifiedWhat is claimed is:
1 . A computer-implemented method for memory storage, comprising:
storing a neural network in memory by:
storing, in the memory, one or more values of the neural network each as a reference to a representative value; and
storing, in the memory, one or more additional values of the neural network.
2 . The computer-implemented method of claim 1 , the reference being the representative value.
3 . The computer-implemented method of claim 1 , each of the references being generated by quantizing one of the one or more values of the neural network.
4 . The computer-implemented method of claim 1 , further comprising storing, in the memory, a reconstruction table storing each representative value for each reference.
5 . The computer-implemented method of claim 1 , each of the one or more representative values being generated by:
assigning each of the one or more values of the neural network to a cluster; and for each cluster, selecting a selected value from the cluster as the representative value for each of the one or more values of the neural network of the cluster.
6 . The computer-implemented method of claim 5 , each selected value being a centroid, the centroid being an average of the one or more values of the neural network in the cluster that the selected value is selected from.
7 . The computer-implemented method of claim 5 , further comprising: minimizing a sum of each distance between a) each of the one or more values of the neural network and b) the selected value of the cluster that the value is assigned to by iteratively:
performing the assigning, the assigning further comprising reassigning a first value of the one or more values of the neural network from an original cluster of the clusters to a new cluster of the clusters where an original distance of the first value to the selected value of the original cluster is greater than a new distance of the first value to the selected value of the new cluster; and subsequently performing the selecting on at least the original cluster and the new cluster; wherein the first value is a different value of the one or more values of the neural network upon each iteration.
8 . The computer-implemented method of claim 1 , further comprising:
generating an output from performing one or more multiply-accumulate operations A 1 B 1 + . . . +A n B n on input vectors A and input vectors B, wherein n is the n-th input vector and wherein one or more of input vectors B are each one of the representative values, by accumulating input vectors A to an accumulated sum of input vectors A per input vector B having the same representative value and subsequently multiplying each of the accumulated sums of input vectors A by the representative value of the input vector B.
9 . The computer-implemented method of claim 8 , further comprising storing, in the memory, one or more additional values of the neural network wherein one or more of the input vectors B are each one of the additional values.
10 . The computer-implemented method of claim 1 , each of the additional values satisfying a criterion of a distribution, content, or value count of a component of the neural network.
11 . The computer-implemented method of claim 1 , each of the additional values being in a component of the neural network and having a probability density function (pdf) less than a threshold value, the pdf defined by
pdf
(
x
❘
μ
,
σ
2
)
=
1
2
π
σ
2
e
-
(
x
-
μ
)
2
2
σ
2
,
wherein x is the additional value, μ is a mean of one or more parameters in the component of the neural network having x, and σ is a standard deviation of one or more parameters in the component of the neural network having x.
12 . The computer-implemented method of claim 1 , each of the additional values being outside a threshold range from a distribution fit of both the values and the additional values in a component of the neural network.
13 . The computer-implemented method of claim 1 , at least one of the references being encoded using three bits or four bits.
14 . The computer-implemented method of claim 1 , at least one of the one or more values of the neural network being an embedding.
15 . The computer-implemented method of claim 1 , at least one of the one or more values of the neural network being a weight.
16 . A system for computation of layers in a neural network, comprising:
one or more processing elements each configured to accumulate one or more values of the neural network for each of one or more references to an identical representative value to generate an output for each accumulation; and a shared processing unit configured to, for each of the outputs from each processing element, multiply the output with the identical representative value respective to the output to generate a final output.
17 . The system of claim 16 , the shared processing unit further configured to accumulate one or more of the final outputs with one or more outlier values.
18 . A computer system for memory storage, comprising:
a memory; at least one processor in communication with the computer memory, the memory comprising instructions which, when executed by the at least one processor, carries out the steps of:
storing a neural network in memory by:
storing, in the memory, one or more values of the neural network each as a reference to a representative value; and
storing, in the memory, one or more additional values of the neural network.
19 . The computer system of claim 18 , each of the one or more representative values being generated by:
assigning each of the one or more values of the neural network to a cluster; and for each cluster, selecting a selected value from the cluster as the representative value for each of the one or more values of the neural network of the cluster.
20 . The computer system of claim 19 , the steps further comprising: minimizing a sum of each distance between a) each of the one or more values of the neural network and b) the selected value of the cluster that the value is assigned to by iteratively:
performing the assigning, the assigning further comprising reassigning a first value of the one or more values of the neural network from an original cluster of the clusters to a new cluster of the clusters where an original distance of the first value to the selected of the original cluster is greater than a new distance of the first value to the selected value of the new cluster; and subsequently performing the selecting on at least the original cluster and the new cluster; wherein the first value is a different value of the one or more values of the neural network upon each iteration.
21 . The computer system of claim 18 , the steps further comprising:
generating an output from performing one or more multiply-accumulate operations A 1 B 1 + . . . +A n B n on input vectors A and input vectors B, wherein n is the n-th input vector and wherein one or more of input vectors B are each one of the representative values, by accumulating input vectors A to an accumulated sum of input vectors A per input vector B having the same representative value and subsequently multiplying each of the accumulated sums of input vectors A by the representative value of the input vector B.
22 . A non-transient computer-readable medium containing computer-readable instructions which, when executed by a computer processor, perform a method of:
storing a neural network in memory by:
storing, in the memory, one or more values of the neural network each as a reference to a representative value; and
storing, in the memory, one or more additional values of the neural network.
23 . The non-transient computer-readable medium of claim 22 , each of the one or more representative values being generated by:
assigning each of the one or more values of the neural network to a cluster; and for each cluster, selecting a selected value from the cluster as the representative value for each of the one or more values of the neural network of the cluster.
24 . The non-transient computer-readable medium of claim 23 , each selected value being a centroid, the centroid being an average of the one or more values of the neural network in the cluster that the selected value is selected from.
25 . The non-transient computer-readable medium of claim 24 , the method further comprising: minimizing a sum of each distance between a) each of the one or more values of the neural network and b) the centroid of the cluster that the value is assigned to by iteratively:
performing the assigning, the assigning further comprising reassigning a first value of the one or more values of the neural network from an original cluster of the clusters to a new cluster of the clusters where an original distance of the first value to the centroid of the original cluster is greater than a new distance of the first value to the centroid of the new cluster; and subsequently performing the selecting on at least the original cluster and the new cluster; wherein the first value is a different value of the one or more values of the neural network upon each iteration.
26 . The non-transient computer-readable medium of claim 22 , the method further comprising:
generating an output from performing one or more multiply-accumulate operations A 1 B 1 + . . . +A n B n on input vectors A and input vectors B, wherein n is the n-th input vector and wherein one or more of input vectors B are each one of the representative values, by accumulating input vectors A to an accumulated sum of input vectors A per input vector B having the same representative value and subsequently multiplying each of the accumulated sums of input vectors A by the representative value of the input vector B.
27 . The non-transient computer-readable medium of claim 26 , the method further comprising storing, in the memory, one or more additional values of the neural network, wherein one or more of the input vectors B are each one of the additional values.
28 . A computer-implemented method for neural network computation, comprising:
generating a quantization dictionary for at least one of one or more layers of a neural network, each layer using GD×s+m, where GD is a Golden Dictionary, s is the standard deviation of the layer and m is the mean over each value in the layer.
29 . The computer-implemented method of claim 28 , wherein the Golden Dictionary is generated by quantizing a random Gaussian distribution having a mean of zero and standard deviation of one.
30 . The computer-implemented method of claim 28 , wherein the quantization dictionary stores values representative of non-outlier values in the layer and a second quantization dictionary stores values representative of outlier values in the layer.
31 . The computer-implemented method of claim 29 , wherein the quantization dictionary stores values representative of non-outlier values in the layer and a second quantization dictionary stores values representative of outlier values in the layer.
32 . The computer-implemented method of claim 29 , wherein the Golden Dictionary stores only magnitudes of Golden Dictionary values, wherein the Golden Dictionary values are symmetric around zero.
33 . The computer-implemented method of claim 32 , further comprising generating the magnitudes of Golden Dictionary values using an exponential approximation.
34 . The computer-implemented method of claim 33 , further comprising computing an output activation at an output neuron, wherein the output activation is defined by
=
s
A
.
s
W
∑
i
=
0
n
-
1
(
θ
A
t
θ
W
t
a
int
A
t
-
int
W
t
)
︸
SoI
+
s
A
∑
i
=
0
n
-
1
(
μ
W
t
θ
A
t
a
int
A
t
)
︸
SoA
+
s
W
∑
i
=
0
n
-
1
(
μ
A
t
θ
W
t
a
int
W
t
)
︸
SoW
+
∑
i
=
0
n
-
1
(
μ
A
t
·
μ
W
t
)
︸
PoM
where s A and s W are standard deviations for activations and weights of a layer respectively, θ A and θ W are signs for activations and weights respectively, α is a first fitted parameter, int A and int W are dictionary indexes for activations and weights respectively, μ A and μ W are shift parameters defined by μ A =θ A s A b+m A and μ W =θ W s W b+m W where b is a second fitted parameter and m A and m W are the average values for activations and weights respectively.
35 . The computer-implemented method of claim 32 , further comprising performing neural network computation using three-bit or more addition.
36 . The computer-implemented method of claim 31 , wherein the values representative of the outlier values in the layer are 16 or more unique values.
37 . The computer-implemented method of claim 31 , further comprising either only a), only b), or both a) and b), wherein:
a) is converting one or more values stored in the quantization dictionary each to 16-bit fixed-point values; and b) is converting one or more values stored in the second quantization dictionary each to 16-bit fixed-point values.
38 . The computer-implemented method of claim 31 , further comprising performing neural network computation using fixed-point computation on one or more of the values stored by the second quantization dictionary.
39 . A computer-implemented system for neural network computation, comprising:
a quantization dictionary stored in a memory, wherein the quantization dictionary is for at least one of one or more layers of a neural network and generated using GD×s+m, where GD is a Golden Dictionary, s is the standard deviation of the layer and m is the mean over each value in the layer; and one or more integer compute units for computing an output activation at a neuron.
40 . A non-transient computer-readable medium containing computer-readable instructions which, when executed by a computer processor, perform a method of:
computing an output activation at a neuron using a quantization dictionary for a layer of the neural network, the quantization dictionary generated using GD×s+m, where GD is a Golden Dictionary, s is the standard deviation of the layer and m is the mean over each value in the layer.Join the waitlist — get patent alerts
Track US2023334285A1 — get alerts on status changes and closely related new filings.
We store only your email — no account needed. See our privacy policy.