Reduced dot product computation circuit
Some embodiments provide an IC for implementing a machine-trained network with multiple layers. The IC includes a set of circuits to compute a dot product of (i) a first number of input values computed by other circuits of the IC and (ii) a set of predefined weight values, several of which are zero, with a weight value for each of the input values. The set of circuits includes (i) a dot product computation circuit to compute the dot product based on a second number of inputs and (ii) for each input value, at least two sets of wires for providing the input value to at least two of the dot product computation circuit inputs. The second number is less than the first number. Each input value with a corresponding weight value that is not equal to zero is provided to a different one of the dot product computation circuit inputs.
1. A method for implementing a machine-trained (MT) network that comprises a plurality of processing nodes, the method comprising:
at a dot product circuit performing a dot product computation for a particular node of the MT network:
receiving (i) a first plurality of input values that are output values of a set of previous nodes of the MT network and (ii) data representing a set of weight values associated with the first plurality of input values;
from the first plurality of input values, selecting a second, smaller plurality of input values, said second plurality of input values comprising all input values from the first plurality of input values that are associated with non-zero weight values; and
computing a dot product of (i) the selected second plurality of input values and (ii) the weight values associated with the second plurality of input values.
2. The method of claim 1 , wherein the second plurality of input values comprises at least one input value associated with a weight value equal to zero.
3. The method of claim 1 , wherein each of the weight values is one of zero, a positive value, and a negation of the positive value.
4. The method of claim 1 , wherein each of the weight values is one of zero, one, and negative one.
5. The method of claim 1 , wherein selecting the second plurality of input values further comprises using a plurality of multiplexers (i) to receive the first plurality of input values and a set of selection signals, (ii) to select the second plurality of input values based on the set of selection signals, and (iii) to provide the selected second plurality of input values to a set of computation circuits.
6. The method of claim 1 , wherein the weight values are trained to ensure that a number of non-zero weight values associated with the first plurality of input values is equal to or less than a number of input values in the second plurality of input values.
7. The method of claim 1 , wherein the particular dot product circuit comprises (i) a set of input selection circuits and (ii) a set of dot product computation circuits.
8. The method of claim 7 , wherein the set of input selection circuits receive the first plurality of input values and select the second plurality of input values from the first plurality of input values.
9. The method of claim 8 , wherein the set of dot product computation circuits receives (i) the second plurality of input values and (ii) at least a subset of the data representing the set of weight values and performs the dot product computation.
10. The method of claim 8 , wherein receiving the first plurality of input values comprises receiving each input value of the first plurality of input values at two or more of the input selection circuits.
11. The method of claim 10 , wherein each input value is selected by at most one of the input selection circuits.
12. The method of claim 10 , wherein a cuckoo hashing algorithm is used to map the first plurality of input values to the input selection circuits.
13. The method of claim 1 , wherein the particular dot product circuit is a first dot product circuit and the dot product computation is a first partial dot product computation that is part of a complete dot product computation for the particular node, the method further comprising:
at one or more additional dot product circuits, performing additional partial dot product computations for the particular node of the MT network; and
combining results of the first partial dot product computation and the additional partial dot product computations to compute the complete dot product computation for the particular node of the MT network.
14. The method of claim 13 , wherein the set of previous nodes is a first set of previous nodes and the set of weight values is a first set of weight values, the method further comprising:
at a second one of the dot product circuits:
receiving (i) a third plurality of input values that are output values of a second set of previous nodes of the MT network and (ii) data representing a second set of weight values associated with the third plurality of input values;
from the third plurality of input values, selecting a fourth plurality of input values, said fourth plurality of input values comprising all input values from the third plurality of input values that are associated with non-zero weight values; and
computing a dot product of (i) the selected fourth plurality of input values and (ii) the weight values associated with the fourth plurality of input values.
15. The method of claim 14 , wherein:
the third plurality of input values comprises a same number of input values as the first plurality of input values;
the fourth plurality of input values comprises a same number of input values as the second plurality of input values; and
a number of input values in the third plurality of input values that are associated with non-zero weight values is different than a number of input values in the first plurality of input values that are associated with non-zero weight values.
16. The method of claim 13 further comprising computing an output for the particular node by applying a non-linear activation function to the complete dot product for the particular node.
17. The method of claim 16 further comprising, prior to computing the output for the particular node:
adding a bias value to the complete dot product to compute a first result; and
multiplying the first result by a scaling value to compute a second result,
wherein the non-linear activation function is applied to the second result to compute the output for the particular node.
18. The method of claim 17 , wherein the scaling value is based on a weight scaling value, wherein each of the weight values is one of zero, the weight scaling value, and a negation of the weight scaling value.
19. The method of claim 1 , wherein the set of previous nodes that output the first plurality of input values are nodes of a previous layer of the MT network.
20. The method of claim 1 , wherein receiving the first plurality of input values and the data representing the set of weight values comprises reading the first plurality of input values and the data representing the set of weight values from a memory.