Matrix multiplication packing with instruction reordering
A technique for packing matrix multiplications for concurrent execution in an integrated circuit device may include obtaining a description of a neural network model, and generating an intermediate representation of the neural network model. Matrix multiplication instructions in the intermediate representation of the neural network model can then be vectorized for concurrent execution on an integrated circuit device, and machine instructions can be generated for the integrated circuit device based on the vectorized matrix multiplication instructions.
1 . A computer-implemented method for compiling a neural network model, the method comprising:
obtaining a description of the neural network model;
generating a representation of a data dependency graph of the neural network model;
identifying accumulation groups (AGs) having one or more matrix multiplication instructions in the data dependency graph;
initializing an AG pack from each AG, the AG pack being a data structure representing AGs to be reordered into a consecutive sequence of matrix multiplication instructions;
identifying AG pack pairs that are within a search window distance in the data dependency graph;
forming a set of packing candidates from AG pack pairs that fits in a tile arrangement of a processing engine array, each packing candidate containing an AG pack pair;
selecting packing candidates based on a similarity metric;
combining the AG packs in each of the selected packing candidates to form new AG packs;
reordering the data dependency graph to place the AGs in each new AG pack together for concurrent execution on an integrated circuit device; and
generating machine instructions based on the reordered data dependency graph for execution on the integrated circuit device to implement the neural network model.
2 . The computer-implemented method of claim 1 , wherein the AG packs of each packing candidate are unreachable to each other in the data dependency graph, and have an identical weight tensor shape.
3 . The computer-implemented method of claim 1 , wherein the similarity metric is a prioritized list of attributes of the AG packs of the packing candidate in which an instruction proximity measurement in the data dependency graph has a highest priority.
4 . The computer-implemented method of claim 1 , wherein the tile arrangement of the processing engine array includes at least 4 row groups in a tile arrangement.
5 . A computer-implemented method comprising:
obtaining a representation of a data dependency graph of a neural network model;
identifying accumulation groups (AGs) having one or more matrix multiplication instructions in the data dependency graph;
initializing AG packs each including one of the AGs;
combining the AG packs in the data dependency graph to form new AG packs;
reordering the data dependency graph to place the AGs in each new AG pack together for concurrent execution on an integrated circuit device; and
generating machine instructions based on the reordered data dependency graph for execution on the integrated circuit device.
6 . The computer-implemented method of claim 5 , further comprising:
combining AG packs in the reordered data dependency graph based on a set of packing criteria and similarity metric.
7 . The computer-implemented method of claim 5 , wherein combining the AG packs in the data dependency graph includes:
identifying AG pack pairs that are within a search window distance in the data dependency graph;
forming a set of packing candidates from AG pack pairs that satisfy a set of packing criteria, each packing candidate containing an AG pack pair; and
iteratively performing operations on the packing candidates until all packing candidates are pruned from the set of packing candidates, the operations including:
selecting a packing candidate having an AG pack pair whose members are most similar to each other;
forming a new AG pack by grouping the AG packs in the selected packing candidate together; and
pruning packing candidates from the set of packing candidates having at least one of the AG packs in the selected packing candidate.
8 . The computer-implemented method of claim 5 , wherein the AG packs are combined based on a criterion of the AG packs of a packing candidate being unreachable in the data dependency graph.
9 . The computer-implemented method of claim 5 , wherein the AG packs are combined based on a criterion of the AG packs of a packing candidate being able to fit in a tile arrangement of a processing engine array.
10 . The computer-implemented method of claim 5 , wherein the AG packs are combined based on a criterion of the AG packs of a packing candidate having a tensor size that is larger than an instruction fetch latency threshold.
11 . The computer-implemented method of claim 5 , wherein the AG packs are combined based on a criterion of the AG packs of a packing candidate having an identical weight tensor shape.
12 . The computer-implemented method of claim 5 , wherein the AG packs are combined based on a prioritized list of attributes of the AG packs of a packing candidate.
13 . The computer-implemented method of claim 5 , wherein the AG packs are combined based on an instruction proximity measurement between the AG packs of a packing candidate in an intermediate representation of the neural network model.
14 . The computer-implemented method of claim 13 , wherein the instruction proximity measurement is a Hausdorff distance.
15 . The computer-implemented method of claim 5 , wherein the AG packs are combined based on a comparison of feature map sizes of the AG packs of a packing candidate.
16 . The computer-implemented method of claim 5 , wherein the AG packs are combined based on a comparison of a number of matrix multiplications in the AG packs of a packing candidate.
17 . The computer-implemented method of claim 5 , wherein the AG packs are combined based on a comparison of an innermost loop identifiers of the AG packs of a packing candidate.
18 . A non-transitory computer-readable medium having stored therein instructions that, when executed by one or more processors, cause the one or more processors to execute a compiler, the compiler performing operations including:
obtaining a representation of a data dependency graph of a neural network model;
identifying accumulation groups (AGs) having one or more matrix multiplication instructions in the data dependency graph;
initializing AG packs each including one of the AGs;
combining the AG packs in the data dependency graph to form new AG packs;
reordering the data dependency graph according to the new AG packs to place the AGs in each new AG pack together for concurrent execution on an integrated circuit device; and
generating machine instructions based on the reordered data dependency graph for execution on the integrated circuit device.
19 . The non-transitory computer-readable medium of claim 18 , wherein the AG packs are combined based on a set of packing criteria that includes:
a first criterion of the AG packs of a packing candidate being able to fit in a tile arrangement of a processing engine array; and
a second criterion of the AG packs of the packing candidate being unreachable in the data dependency graph.
20 . The non-transitory computer-readable medium of claim 18 , wherein the AG packs are combined based on prioritizing an instruction proximity measurement in the data dependency graph of the AG packs of a packing candidate.
21 . The non-transitory computer-readable medium of claim 18 , assigning the AGs in each new AG pack to a tile arrangement of a processing engine array.
22 . The non-transitory computer-readable medium of claim 18 , wherein the AG packs are combined based on a comparison of feature map sizes or a number of matrix multiplications in the AG packs of a packing candidate.