Automatic operator fusion method for computational graph and related product
View Patent ↗This disclosure discloses a method for automatic fusion of operators in a computational graph, a computing device, and related products. The computing device may be included in a combination processing device, which may also include an interface device and other processing devices. The computing device interacts with other processing devices to jointly complete computing operations specified by the user. The combined processing devices may also include a storage device, which is connected to the computing device and other processing devices respectively, for storing data of the computing device and other processing devices. The solution disclosed herein provides a solution for automatic fusion of operators in a computational graph, which may automatically search for optimized operator fusion solutions without the need for manual analysis, thereby improving the efficiency of fusion analysis.
1 . A method for automatic fusion of operators in a computational graph implemented by a processing device, comprising:
determining, by the processing device, control data that affects fusion performance of the operators;
generating different control data samples according to the control data for hardware information of a computing device to execute the computational graph by the processing device;
applying the control data samples to compute fusion benefits of candidate fusion subgraphs corresponding to the different control data samples by the processing device; and
determining an optimal fusion way according to the fusion benefits, compiling and optimizing the computational graph based on the optimal fusion way to obtain a corresponding binary instruction sequence, and allocating the corresponding binary instruction sequence to the computing device to execute a task corresponding to the computational graph by the processing device.
2 . The method according to claim 1 , wherein the hardware information comprises a processor cluster, a processor core, a L1 storage level, and a L2 storage level.
3 . The method according to claim 2 , wherein intermediate results of fusion operators in the computational graph reside at the L2 storage level, intermediate results of fusion sub-operators in the fusion operators reside at the L1 storage level, and fusion way comprises a fusion of the L1 storage level and a fusion of the L2 storage level, the method further comprises: searching to determine an optimal L1 fusion way for the fusion of the L1 storage level; and based on the optimal L1 fusion way, further searching to determine an optimal L2 fusion way for the fusion of the L2 storage level.
4 . The method according to claim 3 , wherein searching to determine the optimal L1 fusion way comprises:
determining L1 fusion control data of the L1 storage level, wherein the L1 fusion control data comprises one or more of the following:
a parallel splitting way of fusion operators among a plurality of L2 storage levels;
a serial splitting way of fusion operators in a single L2 storage level;
a parallel pipeline way of IO and computation of fusion operators;
a parallel splitting way of fusion sub-operators among a plurality of L1 storage levels; and
a parallel pipeline way of IO and computation of fusion sub-operators.
5 . The method according to claim 4 , wherein searching to determine the optimal L2 fusion way comprises:
determining L2 fusion control data of the L2 storage level, wherein the L2 fusion control data comprises one or more of the following:
a parallel splitting way of fusion operators among a plurality of L2 storage levels;
a serial splitting way of fusion operators in a single L2 storage level;
a parallel pipeline way of IO and computation of fusion operators;
whether to enable weight preloading; and
whether to enable weight residence.
6 . The method according to claim 5 , wherein searching to determine the optimal L1 fusion way or the optimal L2 fusion way further comprises:
searching for potential fusion operators; and
for each potential fusion operator, applying a fusion control data sample generated based on corresponding fusion control data to compute a fusion benefit of a fusion way corresponding to the fusion control data sample.
7 . The method according to claim 5 , wherein searching to determine the optimal L1 fusion way or the optimal L2 fusion way further comprises combining one or more of the following to perform a fusion search on the operators in the computational graph:
a fusion search of adjacent operators; and
a fusion search of a block structure.
8 . The method according to claim 7 , wherein the fusion search of the adjacent operators comprises:
backtracking from an output operator of the computational graph to an input operator;
fusing the current operator with its front and back adjacent operators in the backtracking direction respectively to find the first operator with the largest and positive fusion benefit;
fusing the first operator with its front and back adjacent operators in the backtracking direction respectively to find a second operator with the maximum and positive fusion benefit;
fusing the current operator with the first operator when the second operator is consistent with the current operator; and
repeating the above steps until no operator is able to be fused.
9 . The method according to claim 7 , wherein the fusion search of the block structure comprises:
performing the fusion search in an order of priority that branches with short execution time in the block structure are fused first when searching to determine the optimal L1 fusion way; or
performing the fusion search in an order of priority that branches with large batch numbers in the block structure are fused first, and branches that occupy less L2 storage space when the batch numbers are the same are fused first when searching to determine the optimal L2 fusion way.
10 . The method according to claim 9 , wherein the fusion search of the block structure further comprises:
sorting each branch in the block structure according to the order of priority; and
traversing each branch according to the order of priority for fusion, and finding a branch fusion way with a successful fusion and a positive fusion benefit.
11 . The method according to claim 5 , wherein searching to determine the optimal L2 fusion way further comprises:
judging whether a weight storage space meets a weight preloading requirement in response to determining to enable weight preloading; and
splitting sub-operators in the computational graph when the weight storage space does not meet the weight preloading requirement, until the weight preloading requirement is met or the splitting is not able to be performed.
12 . The method according to claim 11 , wherein judging whether the weight storage space meets the weight preloading requirement comprises:
judging whether a maximum value among weight accumulation storage requirements of any adjacent sub-operators in the computational graph exceeds the weight storage space, and if does not exceed, determining that the weight storage space meets the weight preloading requirement.
13 . The method according to claim 5 , wherein searching to determine the optimal L2 fusion way further comprises:
determining the best residence solution of a weight at the L1 storage level and the best residence solution of the weight at the L2 storage level in turn in response to determining to enable weight residence.
14 . The method according to claim 13 , wherein determining the best residence solution of the weight at the L1 storage level or the best residence solution of the weight at the L2 storage level comprises:
arranging candidate weights in a descending order of storage space;
traversing the candidate weights in sequence in the order, and solving optimal residence ways for each candidate weight when a current candidate weight does not reside according to the knapsack problem; and
selecting the best one from the optimal residence ways solved as the best residence solution.
15 . The method according to claim 14 , wherein the size of the backpack in the backpack problem is a current available resident storage space minus a storage space required by the candidate weight currently traversed, a weight that is able to be placed in the backpack is a candidate weight arranged after the candidate weight currently traversed, and a value of each weight is a corresponding resident benefit.
16 . The method according to claim 1 , wherein generating different control data samples according to the control data comprises:
generating control data samples according to a fixed mode, wherein the fixed mode comprises any of the following: a large graph mode, a small image mode and a mode without a shared memory, and each mode defines different policies in one or more of the following aspects:
pipeline level splitting, parallel splitting, serial splitting, and data residence.
17 . The method according to claim 1 , wherein applying the control data samples comprises:
performing one or more of the following according to each control parameter in the control data samples for a candidate fusion subgraph: address derivation, memory allocation, and runtime estimation.
18 . The method according to claim 17 , wherein when performing address derivation, address derivation is performed on the candidate fusion subgraph based on predefined operator information.
19 . The method according to claim 18 , wherein the predefined operator information comprises a dimension derivation way, and the dimension derivation way comprises one or more of the following categories: sliding window, add pad, elementwise, broadcast, and no split.
20 . The method according to claim 1 , wherein the fusion benefit is determined based at least on the difference between the accumulated value of the shortest execution time of each operator before fusion and the shortest execution time of the operator after fusion.