Runtime predictors for computation reduction in dependent computations
Methods and systems relating to reducing the number of computations required to execute an artificial neural network (ANN) are disclosed herein. A disclosed method includes: generating a summary of a set of data which is an input for a composite computation; executing a simplified composite computation, using the summary, to produce a simplified output; and executing a second simplified composite computation, using the simplified output, to produce a second simplified output which is a predictor. The second simplified composite computation is a simplification of a second composite computation. The composite computations are both part of a complex computation for the directed graph. The second composite computation depends on the composite computation in the directed graph. The method further includes suppressing, while executing the complex computation, a set of component computations from the second composite computation. The set of component computations are selected for suppression based on the predictor.
1 . A computer-implemented method, conducted during an execution of a neural network, comprising:
generating a first summary of a first set of data, wherein the first set of data is an input for a first composite computation;
executing a first simplified composite computation, using the first summary, to produce a first simplified output, wherein the first simplified composite computation is a simplification of the first composite computation;
executing a second simplified composite computation, using the first simplified output, to produce a second simplified output, wherein the second simplified output is a predictor, wherein the second simplified composite computation is a simplification of a second composite computation; wherein the first composite computation and the second composite computation are both part of a complex computation for the neural network; and wherein the second composite computation depends on the first composite computation in the neural network; and
suppressing, while executing the complex computation, a set of component computations from the second composite computation, wherein the set of component computations from the second composite computation are selected for suppression based on the predictor;
wherein the execution of the neural network uses a processing pipeline; and
wherein the suppressing of the set of component computations uses logic and registers incorporated into the processing pipeline that suppress the set of component computations using control data provided orthogonally to a main computational flow of the processing pipeline.
2 . The computer-implemented method of claim 1 , further comprising:
generating, a third summary of a third set of data, wherein the third set of data is an input for a third composite computation; and
executing a third simplified composite computation, using the third summary, to produce a third simplified output, wherein the third simplified composite computation is a simplification of the third composite computation;
wherein executing the second simplified composite computation uses the third simplified output;
wherein the first composite computation, the third composite computation, and the second composite computation are all part of the complex computation for the neural network; and
wherein the second composite computation depends on the third composite computation in the neural network.
3 . The computer-implemented method of claim 2 , wherein:
the first composite computation is a first matrix multiplication;
the third composite computation is a third matrix multiplication;
the second composite computation is a second matrix multiplication; and
the second composite computation depends on the first composite computation and the third composite computation because a first output of the first composite computation and a third output of the third composite computation are both inputs to the second composite computation.
4 . The computer-implemented method of claim 3 , wherein:
the first matrix multiplication is a multiplication of a first set of neural network data and a first set of execution data to produce a first output matrix;
the third matrix multiplication is a multiplication of a third set of neural network data and a third set of execution data to produce a third output matrix; and
the second matrix multiplication is a multiplication of the first output matrix and the third output matrix.
5 . The computer-implemented method of claim 2 , wherein:
the generating of the first summary of the first set of data uses an average pooling operation on the first set of data; and
the generating of the third summary of the third set of data uses the average pooling operation on the third set of data.
6 . The computer-implemented method of claim 2 , wherein:
the first summary is less than or equal to one quarter of a size of the first set of data; and
the third summary is less than or equal to one quarter of a size of the third set of data.
7 . The computer-implemented method of claim 2 , wherein:
the neural network is an attention network;
the first set of data is one of a right key matrix and a left key matrix;
the third set of data is one of a right query matrix and a left query matrix;
the first composite computation is a key matrix multiplication; and
the third composite computation is a query matrix multiplication.
8 . The computer-implemented method of claim 2 , further comprising:
generating a second summary of a second set of data, wherein the second set of data is a third input for the first composite computation, and wherein executing the first simplified composite computation uses the second summary; and
generating a fourth summary of a fourth set of data, wherein the fourth set of data is a third input for the third composite computation, and wherein executing the third simplified composite computation uses the fourth summary.
9 . The computer-implemented method of claim 8 , wherein:
the generating of the first summary of the first set of data uses an average pooling operation on the first set of data;
the generating of the third summary of the third set of data uses the average pooling operation on the third set of data;
the generating of the second summary of the second set of data uses a second average pooling operation on the second set of data; and
the generating of the fourth summary of the third set of data uses the second average pooling operation on the fourth set of data.
10 . The computer-implemented method of claim 2 , further comprising:
executing a fourth simplified composite computation, using the second simplified output, to produce a fourth simplified output, wherein the fourth simplified output is a third predictor, wherein the fourth simplified composite computation is a simplification of a fourth composite computation, wherein the fourth composite computation is part of the complex computation for the neural network, and wherein the fourth composite computation depends on the second composite computation in the neural network; and
suppressing, while conditionally executing the complex computation, a set of component computations from the fourth composite computation, wherein the set of component computations from the fourth composite computation are selected for suppression based on the third predictor.
11 . The computer-implemented method of claim 10 , further comprising:
suppressing, while executing the complex computation, the first composite computation, wherein the first composite computation is selected for suppression based on the predictor and the third predictor.
12 . The computer-implemented method of claim 1 , further comprising:
suppressing, while executing the complex computation, a set of component computations from the first composite computation, wherein the set of component computations from the first composite computation are selected for suppression based on the predictor.
13 . The computer-implemented method of claim 1 , wherein:
suppressing, while executing the complex computation, the first composite computation, wherein the first composite computation is selected for suppression based on the predictor.
14 . The computer-implemented method of claim 1 , further comprising:
analyzing the predictor to find a set of salient portions;
wherein the set of component computations from the second composite computation are selected based on a distribution of the set of salient portions.
15 . The computer-implemented method of claim 14 , wherein:
the analyzing of the predictor uses a top-k operation on a set of portions of the predictor to find the set of salient portions.
16 . The computer-implemented method of claim 15 , wherein:
the first composite computation is a first matrix multiplication;
the set of salient portions are in one half of the predictor; and
the computer-implemented method further comprises suppressing, while conditionally executing the complex computation, at least half of the component computations from the first composite computation, wherein the set of component computations from the first composite computation are selected for suppression based on the predictor.
17 . The computer-implemented method of claim 1 , wherein:
the neural network is an attention network;
the first set of data is one of a key matrix and a query matrix; and
the second simplified composite computation uses a simplified values matrix.
18 . A processing core comprising:
a processor;
a processing pipeline;
logic and registers incorporated into the processing pipeline; and
one or more computer readable media storing instructions which, when executed by the processor, cause the processing core to:
generate a first summary of a first set of data, wherein the first set of data is an input for a first composite computation;
execute a first simplified composite computation, using the first summary, to produce a first simplified output, wherein the first simplified composite computation is a simplification of the first composite computation;
execute a second simplified composite computation, using the first simplified output, to produce a second simplified output, wherein the second simplified output is a predictor, wherein the second simplified composite computation is a simplification of a second composite computation; wherein the first composite computation and the second composite computation are both part of a complex computation for a neural network; and wherein the second composite computation depends on the first composite computation in the neural network; and
suppress, while executing the complex computation, a set of component computations from the second composite computation, wherein the set of component computations from the second composite computation are selected for suppression based on the predictor;
wherein: (i) the execution of the neural network uses the processing pipeline; and (ii) the suppressing of the set of component computations uses the logic and registers incorporated into the processing pipeline to suppress the set of component computations using control data provided orthogonally to a main computational flow of the processing pipeline.
19 . A system comprising:
a means for generating a first summary of a first set of data, wherein the first set of data is an input for a first composite computation;
a means for executing a first simplified composite computation using the first summary to produce a first simplified output, wherein the first simplified composite computation is a simplification of the first composite computation;
a means for executing a second simplified composite computation, using the first simplified output, to produce a second simplified output, wherein the second simplified output is a predictor, wherein the second simplified composite computation is a simplification of a second composite computation; wherein the first composite computation and the second composite computation are all part of a complex computation for a neural network; and wherein the second composite computation depends on the first composite computation in the neural network; and
a means for suppressing, while executing the complex computation, a set of component computations from the second composite computation, wherein the set of component computations from the second composite computation are selected for suppression based on the predictor.
20 . The system of claim 19 , further comprising:
a means for generating a third summary of a third set of data, wherein the third set of data is an input for a third composite computation;
a means for executing a third simplified composite computation using the third summary to produce a third simplified output, wherein the third simplified composite computation is a simplification of the third composite computation;
wherein executing the second simplified composite computation uses the third simplified output;
wherein the first composite computation, the third composite computation, and the second composite computation are all part of the complex computation for the neural network; and
wherein the second composite computation depends on the third composite computation in the neural network.
21 . The system of claim 20 , wherein:
the first composite computation is a first matrix multiplication;
the third composite computation is a third matrix multiplication;
the second composite computation is a second matrix multiplication; and
the second composite computation depends on the first composite computation and the third composite computation because a first output of the first composite computation and a third output of the third composite computation are both inputs to the second composite computation.
22 . The system of claim 21 , wherein:
the first matrix multiplication is a multiplication of a first set of neural network data and a first set of execution data to produce a first output matrix;
the third matrix multiplication is a multiplication of a third set of neural network data and a third set of execution data to produce a third output matrix; and
the second matrix multiplication is a multiplication of the first output matrix and the third output matrix.
23 . The system of claim 20 , wherein:
generating the first summary of the first set of data uses an average pooling operation on the first set of data; and
generating the third summary of the third set of data uses the average pooling operation on the third set of data.
24 . The system of claim 20 , wherein:
the first summary is less than or equal to one quarter of a size of the first set of data; and
the third summary is less than or equal to one quarter of a size of the third set of data.
25 . The system of claim 20 , wherein:
the neural network is an attention network;
the first set of data is one of a right key matrix and a left key matrix;
the third set of data is one of a right query matrix and a left query matrix;
the first composite computation is a key matrix multiplication; and
the third composite computation is a query matrix multiplication.
26 . The system of claim 20 , further comprising:
a means for generating a second summary of a second set of data, wherein the second set of data is a third input for the first composite computation, and wherein executing the first simplified composite computation uses the second summary; and
a means for generating a fourth summary of a fourth set of data, wherein the fourth set of data is a third input for the third composite computation, and wherein executing the third simplified composite computation uses the fourth summary.
27 . The system of claim 26 , wherein:
the means for generating the first summary of the first set of data uses an average pooling operation on the first set of data;
the means for generating the third summary of the third set of data uses the average pooling operation on the third set of data;
the means for generating the second summary of the second set of data uses a third average pooling operation on the second set of data; and
the means for generating the fourth summary of the third set of data uses the third average pooling operation on the fourth set of data.
28 . The system of claim 20 , further comprising:
a means for executing a fourth simplified composite computation, using the second simplified output, to produce a fourth simplified output, wherein the fourth simplified output is a third predictor, wherein the fourth simplified composite computation is a simplification of a fourth composite computation, wherein the fourth composite computation is part of the complex computation for the neural network, and wherein the fourth composite computation depends on the second composite computation in the neural network; and
a means for suppressing, while conditionally executing the complex computation, a set of component computations from the fourth composite computation, wherein the set of component computations from the fourth composite computation are selected for suppression based on the third predictor.
29 . The system of claim 28 , further comprising:
a means for suppressing, while executing the complex computation, the first composite computation, wherein the first composite computation is selected for suppression based on the predictor and the third predictor.
30 . The system of claim 19 , further comprising:
a means for suppressing, while executing the complex computation, a set of component computations from the first composite computation, wherein the set of component computations from the first composite computation are selected for suppression based on the predictor.
31 . The system of claim 19 , further comprising:
a means for suppressing, while executing the complex computation, the first composite computation, wherein the first composite computation is selected for suppression based on the predictor.
32 . The system of claim 20 , further comprising:
a means for analyzing the predictor to find a set of salient portions;
wherein the set of component computations from the second composite computation are selected based on the set of salient portions.
33 . The system of claim 32 , wherein:
the first composite computation is a first matrix multiplication;
the set of salient portions are in one half of the predictor; and
the system further comprises means for suppressing, while conditionally executing the complex computation, at least half of the component computations from the first composite computation, wherein the set of component computations from the first composite computation are selected for suppression based on the predictor.
34 . The system of claim 19 , wherein:
the neural network is an attention network;
the first set of data is one of a key matrix and a query matrix; and
the second simplified composite computation uses a simplified values matrix.
35 . The computer-implemented method of claim 1 , wherein:
the execution of the neural network uses a set of processing cores; and
the suppressing of the set of component computations is conducted by a hierarchical level responsible for distributing computations among the set of processing cores.
36 . The processing core of claim 18 , wherein:
the execution of the neural network uses a set of processing cores, including the processing core; and
the suppressing of the set of component computations is conducted by a hierarchical level responsible for distributing computations among the set of processing cores.
37 . The system of claim 19 , wherein:
the execution of the neural network uses a processing pipeline; and
the means for suppressing includes logic and registers incorporated into the processing pipeline that suppress the set of component computations using control data provided orthogonally to a main computational flow of the processing pipeline.
38 . The system of claim 19 ,
wherein:
the execution of the neural network uses a set of processing cores; and
the means for suppressing includes a hierarchical level responsible for distributing computations among the processing cores.