CN115115052A - An Adaptive Distributed Parallel Training Method of Neural Network Based on Genetic Algorithm - Google Patents

Abstract

The invention discloses a neural network self-adaptive distributed parallel training method based on a genetic algorithm. The method comprises the steps of firstly converting an operator placement problem in model parallel into an integer linear programming problem, constructing a solution space, and simplifying the scale of the solution space. And secondly, constructing a cost evaluation model, evaluating the quality of a linear programming problem solution, and guiding two groups of population to perform iterative updating between the two populations. And then converting the two sets of placing strategies into operator placing strategies of the data flow graph after the termination condition of the iterative updating is reached, and training the model by the operator placing strategies to select the optimal distributed scheduling strategy. And finally, performing distributed scheduling on the model to be trained by using the obtained distributed scheduling strategy, and inputting the data set into the neural network for distributed training. The invention accelerates the algorithm searching speed on the premise of ensuring the solution space quality, evaluates the execution performance of the operator placing strategy with fine granularity, and effectively avoids falling into the local optimal condition.

Description

An Adaptive Distributed Parallel Training Method of Neural Network Based on Genetic Algorithm

technical field

The invention belongs to the field of distributed machine learning, and mainly relates to a neural network adaptive distributed parallel training method based on genetic algorithm, which provides an optimal model for large-scale complex neural networks in artificial intelligence scenarios such as image recognition and natural language processing. Parallel training method.

technical background

In recent years, with the increase of the data scale, the deep learning model has become more and more complex, and the parameter scale of the deep learning model has increased from 10,000 to 100 million and 1 trillion. Deep learning large models have gradually developed into the next-generation AI technology due to their powerful capabilities in massive data mining and analysis, pre-training, and fast reasoning. However, the rapid growth of dataset size and model parameters makes AI model training limited by hardware devices, and the computing power and storage capacity of a single device are limited, which cannot cope with training such large models on large datasets. For example, Bert-Large has 400 million parameters and occupies more than 32GB of memory; GPT-3 has 175 billion parameters and occupies more than 350GB of memory. A common implementation of a 1000-layer residual network requires 48GB of memory, and even after further optimization to reduce memory costs, the DNN model still requires at least 7GB of memory. This makes it extremely difficult to run the entire model on a single device with limited memory and data-parallel training. At the same time, due to the increase in the scale of deep learning models, the required data and computing volume are also increasing, and the computing power of a single device is often unable to meet the needs. Therefore, the use of cross-device distributed parallel technology to train large deep learning models has become a key requirement for the development and application of deep learning in the industry.

The current mainstream distributed machine learning systems, such as TensorFlow, PyTorch, and MindSpore, mainly use data parallelism to speed up model training. However, data parallelism can usually only solve the problem of massive data training, and cannot solve the problem that large models cannot be trained due to the limitation of hardware resources. Therefore, in order to meet the training requirements of large-scale network models, the neural network must be segmented and scheduled across devices to achieve Model Parallel. In terms of model parallel strategy formulation, the neural network computing graph is usually divided horizontally by layers, vertically across layers or randomly divided and dispatched to different devices for execution. However, these methods rely heavily on expert experience, the segmentation method is unreasonable, and the cluster utilization rate low and usually has a large communication overhead.

The automatic search method of parallel strategy based on machine learning is to extract the characteristics of neural network model and equipment topology, and use machine learning modeling to guide the search of parallel strategy to obtain the optimal distributed parallel strategy. The Google team proposed the automatic policy search framework ColorRL and Hierarchical, by extracting neural network model and device features and using reinforcement learning to guide the search of parallel policies. However, the above methods require frequent sampling, which makes the policy search process expensive. Gao et al. proposed Spotlight, which for the first time modeled the neural network operator scheduling problem as a Markov decision process (MDP), and then proposed POST to further improve it, introducing cross-entropy into the sampling process to improve search efficiency. Ravichandra of MIT proposed Placeto, which introduced a graph embedding method (GraphEmbedding) so that the neural network can learn the structural features of the model and enable it to have the ability to quickly transfer strategies. Hao et al. proposed the AutoSync adaptive framework, which uses machine learning methods to predict the execution time of data-parallel strategies based on data-parallel scenarios, thereby guiding the search for synchronous-parallel strategies. Ding and Zhou et al. designed a full-scale search method based on reinforcement learning, which can generate an entire graph placement strategy at one time, and support the rapid transfer of strategies between models with similar structures. Lan et al. captured the structural information of the neural network by building a self-supervised graph neural network, and used the Seq2Seq (Sequence-to-Sequence) network to segment and schedule the deep learning model. Although the above-mentioned methods based on machine learning can search for parallel strategies with excellent execution performance, they are usually limited to small and medium-sized neural network models and rely on hardware resources. The search process often takes dozens of hours, which is not suitable for rapid deployment or training of models. scene.

The automatic strategy search method based on graph algorithm is another mainstream method at present. Compared with the parallel automatic strategy search method based on machine learning, it has a faster search speed. Jia et al. proposed that OptCNN uses dynamic programming to search for the optimal strategy in the entire search space by abstracting the parallel strategy into tensor segmentation, but its coarse-grained model division and coarse cost evaluation model make the searched The policy improves performance is limited. Subsequently, Jia et al. improved and proposed the FlexFlow framework on the basis of OptCNN, introduced the idea of SOAP (Sample, Operator, Attribute, Parameter) to establish a high-dimensional search space, and used the Markov decision process to quickly search in the search space. The optimal solution, but its complex implementation is only suitable for a small number of neural network models, and the cost evaluation does not consider the parallel execution of operators. In order to search for strategies faster and apply more models, Yi et al. proposed the FastT algorithm based on DAG scheduling, which places and schedules operators by setting fine-grained operator priorities and using critical paths. Consider the dynamic memory ratio during device training, and dynamic RNN is not applicable. Beomyeol et al. proposed the Beachi framework, and proposed three graph algorithms based on topological sorting, earliest start time and minimum traffic to search for strategies. The model parallel strategy can be searched in tens of seconds at the fastest, and supports most of the However, depending on specific conditions, the strategies searched on different neural network models have different effects. Although the search speed of the above method is fast, it usually relies on the specified search idea, and the dimensions considered in the search direction of the strategy are not comprehensive, and there is a lack of a comprehensive cost evaluation model, which makes the method easy to search for sub-optimal solutions.

SUMMARY OF THE INVENTION

In order to solve the above deficiencies and speed up the training speed of the AI model, the present invention designs and implements a neural network adaptive distributed parallel training method based on genetic algorithm.

A neural network adaptive distributed parallel training method based on genetic algorithm, the steps can be summarized as follows:

Step 1: Transform the operator placement problem in the neural network model into an integer linear programming problem, construct a solution space based on the data flow graph and device topology graph of the neural network model, and simplify the scale of the solution space by setting assumption constraints and operator grouping constraints .

1-1, extract the neural network model structure and set up a device resource group, and abstractly obtain a computational graph G(O, E) and a device topology graph D. In the computation graph G(O, E), the vertex O represents the operator set of the neural network model, E represents the directed edge set between the vertices, and the device topology graph D is composed of M computing devices.

1-2, given the calculation graph G(O, E) and the device topology graph D, on the premise of satisfying the device memory constraints, find a set of placement strategies to minimize the execution cost, so that the operators of the neural network model are placed on the device. The placement problem is further transformed into an integer linear programming problem, and a solution space is constructed based on the data flow graph and device topology graph.

1-3, by analyzing the device characteristics in the homogeneous cluster and the execution characteristics of the neural network model, two assumptions are put forward: the computing and communication performance of the homogeneous devices are the same; the execution end time of the operator is only related to the operator that has a direct dependency relationship. related.

Based on the above assumptions, the placement of two operators with data dependencies is constrained to two, one of which is that the two operators are placed on the same device, and the other is that the two operators are placed on different devices. Among them, when two operators are placed on the same device, it indicates that the communication cost of the two operators is greater than the computational cost; when the two operators are placed on different devices, it indicates that the computational cost of the two operators is greater than the communication cost cost.

1-4, the operator grouping constraints are further proposed. Among the two operators with data dependencies, if one of the operators satisfies the condition that the out-degree or in-degree is 1, the two operators are constrained to be the same. group, and the operators in the group are regarded as a whole for scheduling, which simplifies the structure of the computational graph and reduces the size of the solution space. The above assumption constraints and operator grouping constraints are used to simplify the search space to speed up the search speed of the algorithm.

Step 2: Construct a cost evaluation model integrating computing cost, communication cost and load cost to comprehensively evaluate the pros and cons of the solution of the integer linear programming problem, that is, the execution performance of the operator placement strategy, and guide the dual population genetic algorithm in the two populations (placement strategy). ) between the two groups of placement strategies were iteratively updated by gene mutation and gene exchange.

2-1, build a cost evaluation model that integrates computing cost, communication cost and load cost.

Firstly, the key factors affecting the execution performance of the neural network model are analyzed, and the real execution time of the operators in the neural network model on the device is used to establish the calculation cost _Li ; the total tensor size of the cross-device communication between operators in the neural network model is used. , establish the communication cost W; use the sum of the ratio of the memory load offset and the average load of each device to establish the load cost f.

Secondly, by comprehensively considering the characteristics of the calculation cost, communication cost, load cost and the actual training process of the model, a cost evaluation model integrating the calculation cost, communication cost and load cost is established.

π _θ =(∑L _i +λ×Ω(W))×(1+f)

Among them, π _θ represents the execution cost of the placement strategy; λ represents the weight ratio, simulating the parallel situation of computing and communication; Ω is the linear fitting model of tensor size and communication time.

2-2, iteratively update the placement strategy based on the dual population genetic algorithm.

First, using the initialization method of placement strategy, two sets of placement strategies with initial operator placement information are generated in the solution space. The initialization methods of the placement strategy include random initialization and specified strategy initialization. The random initialization method refers to assigning the operators in the calculation graph G(O, E) to the device topology graph D in a random manner. The specified strategy initialization method refers to using The placement strategy searched by the existing parallel strategy search method is used as the initial state, and an initialization method is selected to initialize the placement strategy.

Secondly, based on the cost evaluation model, the gene mutation and gene exchange methods of the dual population genetic algorithm are guided, and the placement information of the operators in the two placement strategies is updated iteratively, so as to quickly search for the placement strategy with the least cost in the solution space.

Step 3: When the termination condition of the iterative update of the placement strategy is reached, the two sets of placement strategies are respectively transformed into the operator placement strategies of the data flow graph, and the neural network model is trained according to the iteratively obtained operator placement strategies in the real environment. , select the strategy with the shortest execution time as the optimal distributed scheduling strategy of the neural network model.

The conditions for the termination of the iteration include that the total number of iterations reaches a specified threshold and the placement strategy does not change within a certain number of iterations. The iteration is terminated when the iterative process of the dual-population genetic algorithm satisfies one of the above two conditions.

Step 4: Using the distributed scheduling strategy obtained in Step 3, perform distributed scheduling of the neural network model to be trained, and input the data sets required by the image recognition, natural language processing and other models into the neural network model for distributed training .

The invention has the beneficial effects of: transforming the operator placement problem in the neural network model into an integer linear programming problem, intuitively describing the problem to be solved, and constructing the solution space of the integer linear programming problem based on the data flow diagram and the equipment topology diagram , and then introduce assumption constraints and operator grouping constraints to simplify the solution space and speed up the algorithm search speed on the premise of ensuring the quality of the solution space; analyze the key factors that affect the performance of the neural network model, build a cost evaluation model, and evaluate with fine-grained The execution performance of the operator placement strategy; the proposal of the dual population genetic algorithm, the use of gene mutation and gene exchange methods to speed up the iteration speed of the genetic algorithm, effectively avoid falling into the local optimal situation, and help the algorithm to approach the global optimal solution.

Description of drawings

Figure 1 is a schematic diagram of searching for an optimal parallel strategy based on a genetic algorithm;

Fig. 2 is a schematic diagram of an operator pair;

Figure 3 is a schematic diagram of gene mutation in the gene mutation method;

Fig. 4 is a schematic diagram of iterative update in gene mutation and gene exchange method;

Figure 5 is a schematic diagram of cross-exchange of high-quality operator pairs in the gene exchange method.

Detailed ways

The present invention will be further described below in conjunction with the accompanying drawings and specific implementation steps:

A neural network adaptive distributed parallel training method based on genetic algorithm, the overall flow chart is shown in Figure 1, including the following specific steps:

Step 1: Convert the operator placement problem in the neural network model into an integer linear programming problem, build a solution space based on the data flow graph and device topology graph of the neural network model, and simplify the scale of the solution space by setting assumption constraints and operator grouping constraints :

1-1, according to the neural network data flow graph, define the computation graph G(O, E), where O represents the set of operators, node o _i ∈ O represents a single operator (such as matrix multiplication, convolution, etc.), and E represents the node The set of directed edges between them indicates the data dependency between operators; according to the cluster device topology information, the device topology graph D is defined, and the device topology graph D is composed of M computing devices, in which the node d∈D represents a certain computing device. device (e.g. CPU or GPU).

1-2, given the calculation graph G(O, E) and the device topology graph D, on the premise of satisfying the device memory constraints, find a set of placement strategies to minimize the execution cost, and connect the operators of the neural network model to the device. The placement problem is further transformed into an integer linear programming problem, and the solution space of the integer linear programming problem is constructed by using the computational graph G(O, E) and the device topology graph D abstracted from the data flow graph of the neural network model, as shown in Eq. (1 ) as shown:

表示算子o_i的放置策略产生的内存开销，M(d)表示计算设备d的最大内存。Among them, P represents the placement strategy of the operator, F represents the computation graph F(O, E), D represents the device topology map, and π _θ represents the cost of the strategy P under the current computation graph G and device topology map D. where o _i represents the operator in the operator set O, d represents the computing device in the device topology diagram D,

Represents the memory overhead generated by the placement strategy of the operator _oi , and M(d) represents the maximum memory of the computing device d.

1-3, set assumption constraints and operator grouping constraints to simplify the solution space scale. Because the performance difference between homogeneous devices is small and the operator's predecessor node directly affects the start time of the operator's execution. Therefore, based on the above characteristics, the following two assumptions are put forward: the computing and communication performance of isomorphic devices are the same; the execution end time of operators is only related to operators with direct dependencies. And based on the above assumptions, the scope of the solution space is constrained, and the constraints are assumed as shown in formula (2):

和

表示同构设备的性能，≡表示恒等于，o_i,o_j表示算子集合O中的算子，p_oi表示算子o的放置策略，Succ(o_i)方法表示获取o_i算子的所有后续节点，σ表示算子运算结束时间，

表示算子o_i的放置不直接影响o_j的执行结束时间。Among them, d _i , d _j represent the computing devices in the device topology diagram D,

and

Represents the performance of the homogeneous device, ≡ represents equality, o _i , o _j represent the operators in the operator set O, p _oi represents the placement strategy of the operator o, and the Succ(o _i ) method represents the acquisition of the o _i operator. For all subsequent nodes, σ represents the end time of the operator operation,

Indicates that the placement of operator o _i does not directly affect the execution end time of o _j .

Based on the above assumptions, the placement of two operators with data dependencies is constrained to two, one of which is that the two operators are placed on the same device, and the other is that the two operators are placed on different devices. Among them, when two operators are placed on the same device, it indicates that the communication cost of the two operators is greater than the computational cost; when the two operators are placed on different devices, it indicates that the computational cost of the two operators is greater than the communication cost cost.

1-4, put forward operator grouping constraints for the large number of operators and connected edges in neural networks. Based on the operator fusion method, the operators in the calculation graph are grouped, and the operators in the group are regarded as a whole for scheduling. , which simplifies the size of the computational graph and further reduces the scope of the solution space. In order to maintain the directed acyclic feature of the computational graph and reduce the cost of detecting loops, the operator grouping constraint adopts a conservative grouping method, that is, one of the two operators with data dependencies satisfies the out-degree or in-degree is 1, the two operators are constrained to the same group, and the operators in the group are regarded as a whole for scheduling, which simplifies the structure of the calculation graph, reduces the scale of the solution space, and ensures that the two operators There is only one data link between the two operators, so as to ensure that the ablation of the two operators will not make the calculation graph loop. That is, only when the operator o _i and the operator o _j satisfy the following formula 3, they are constrained to be the same group:

Among them, succ(o _i ) represents the successor node set of operator o _i , outdegree(o _i ) represents the out-degree of operator o _i , and indegree(o _j ) represents the in-degree of operator o _j .

Step 2: Evaluate the execution performance of the operator placement strategy based on the cost evaluation model of the fusion calculation cost, communication cost and load cost, and guide the dual population genetic algorithm to iteratively update the gene mutation and gene exchange between the two populations (placement strategies). Two sets of placement strategies.

2-1, build a cost evaluation model that integrates computing cost, communication cost and load cost

First, analyze the key factors that affect the performance of neural network model execution, that is, the characteristics of the device's computing performance, communication performance, and memory load. Use the real execution time of the operator on the device in the neural network model to establish the calculation cost Li; use the total tensor size of the cross-device communication between operators in the neural network model to establish the communication cost _W ; use the memory load offset of each device The sum of the proportions of the average load to establish the load cost f. , where the computation cost L _i , the communication cost W and the establishment load cost f are defined as follows:

Calculate the cost by subtracting the start time from the end time of the actual execution of the operator on the device. Then the calculation cost of the operator is shown in formula (4):

和

分别为算子o_i在设备d上的开始执行时间和结束时间。in,

and

are the start time and end time of operator o _i on device d, respectively.

Communication cost, using the total tensor size of the operator in the neural network for cross-GPU communication. Then the communication cost of the model is shown in formula (5):

where S _i,j is the size of the tensor transmitted between operator o _i and operator o _j , μ _i,j is whether operator o _i and operator o _j need to transmit tensors across devices, when operator o When _oi and operator o _j are placed on the same device, if μ _i,j is 0, it means that there is no need for cross-device transmission; otherwise, if μ _i,j is 1, it means that cross-device transmission is required.

The load cost is the sum of the ratio of the memory load offset and the average load of each device. Then the load balancing cost of the model is shown in formula (6):

Among them, A is the average memory size of each device in the current model, W _d represents the total size of tensors that the operator needs to communicate across devices on the d-th device, and Δ _d represents the parameter size of the operator on the d-th device.

Then, a cost evaluation model is constructed based on the calculation cost, communication cost and load cost defined above, and its specific definition is as follows:

A cost evaluation model that integrates computing cost, communication cost and load cost, characterizes the performance of the model parallel strategy from the three dimensions of computing cost, communication cost and load cost, and builds a comprehensive cost evaluation model to guide the automatic search and tuning of operator placement strategies , as shown in formula (7):

π _θ =∑L _i +λ×Ω(W)×(1+f) (7)

Among them, π _θ represents the execution cost of the placement strategy; the weight ratio λ is obtained based on empirical parameter adjustment; Ω is the linear fitting model of tensor size and communication time; since part of the calculation and communication time often overlap in the actual environment, Therefore, the weight ratio λ is used to simulate the parallel situation of computing and communication.

2-2. Iteratively update placement strategy based on dual population genetic algorithm

First, use random or specified strategies to generate two sets of initial solutions in the solution space, that is, to generate two sets of initial placement strategies for operators in the calculation graph. In this method, each set of operator placement strategies is regarded as a population; The cost evaluation model integrating cost, communication cost and load cost guides the gene mutation method and gene exchange method of the dual-population genetic algorithm, iteratively updates the placement information of the two sets of placement strategy operators, and realizes the fast search in the solution space with the smallest execution cost placement strategy.

Use random initialization or specified strategy initialization to generate initial placement strategies for operators.

1) The random initialization method is to randomly place the operators in the calculation graph into the device cluster to obtain the initial placement strategy. The implementation method is shown in Algorithm 1, where random_device(D) means to randomly select a device d from the available devices. placement(P,o,d) means to place operator o on device d, and record the placement information of the operator in policy P.

2) The initialization method based on the specified strategy uses the existing distributed parallel strategy search methods such as the m_topo method based on topological sorting placement in the Beachi framework, the m_etf method based on the earliest start time placement, and the m_sct method based on minimum communication placement for initialization. The implementation method is shown in Algorithm 2, where initial_method(G ^* ,D,T) indicates that the specified distributed parallel strategy search method T is used to search for the calculation graph G ^* in the device cluster described by the device topology diagram D. placement strategy. G' represents the computation graph with operator placement information obtained after searching by existing methods, and get_device(o) represents the target placement device for obtaining operator o in the computation graph. placement(P,o,d) means to place operator o on device d, and record the placement information of the operator in policy P.

The gene mutation method consists of three steps: operator pair selection, gene mutation and iterative update.

The gene mutation method selects the operator to be mutated according to the overall cost of the operator pair and iteratively updates the placement strategy by changing the placement information of the operator to optimize the strategy.

1) Based on the principle of maximum cost priority, the operator pair with the largest overall cost is selected in each group of placement strategies as the gene mutation operator.

The gene mutation method refers to two operators with data dependencies in the calculation graph as an operator pair, as shown in Figure 2. The overall cost of the operator pair is obtained by using the calculation cost and communication cost of the operator on the gene, and the operator pair that needs to be mutated is selected according to the overall cost. The calculation method of the overall cost of the operator pair is shown in formula (8):

表示算子对R_ij被选择过的次数，decay表示动态衰减率，L_i和L_j分别表示算子o_i和算子o_j的计算代价，S_i,j表示算子o_i和算子o_j之间的传输张量大小，Ω表示张量大小和通信时间的线性拟合模型，

表示算子对R_ij的整体代价。in,

Represents the number of times the operator pair R _ij has been selected, decay represents the dynamic decay rate, Li and L _j represent the computational cost of the operator o _i and the operator o _j respectively, S _{i,j represent} the operator o _i and the operator o is the size of the transmission tensor between _j , Ω represents the linear fitting model of the size of the tensor and the communication time,

Represents the overall cost of the operator to R _ij .

Since the operator pair R can be repeatedly selected during the execution of the algorithm, in order to increase the probability that the operator pair with the small overall cost is selected, the dynamic decay rate decay is used to dynamically attenuate the overall cost of the selected operator pair, and calculate The specific implementation of sub-pair selection is shown in Algorithm 3:

where get_all_op_pair(G,P) means to obtain all operator pairs according to the calculation graph G and placement strategy P, caculate_cost(R) means the overall cost of calculating operator pair R; sort_by_cost(op_pair_list) means to calculate all operator pairs according to the overall cost of the operator pair The operator pairs are sorted in descending order; p is the selection threshold.

2) Using the gene mutation method to generate a new placement strategy by changing the placement information of the gene mutation operator.

This method uses the following rules to mutate the selected operator:

(1) If the two operators in the currently selected operator pair are placed on different devices, randomly select an available device and place the two operators on the device.

(2) If the currently selected operator is placed on the same device, then randomly select two available devices and place the two operators on these two different devices.

Using the above two rules, a new placement strategy can be generated on the basis of the original placement strategy. Rule (1) As shown in Figure 3, if the operator pair selection method selects the operator pair to be mutated R ₂₄ , first randomly select an available new device 0, and then mutate R ₂₄ ={0,1} to R ₂₄ = {2, 2}, which means that the o ₂ operator and the o ₄ operator are changed from the original device 0 and device 1 respectively to the operator o ₂ and the operator o ₄ are placed on the device 2 at the same time, so that Get new placement strategies. Similarly, the rule (2) is shown in Fig. 3. If the operator pair selection method selects the operator pair R ₃₅ , it first randomly selects two available new devices, Device 2 and Device 1, and then sets R ₃₅ ={ 1,1} is mutated to R ₃₅ ={2,0}, which means that the o ₃ operator and the o ₅ operator are placed on the device 1 at the same time, and the operator o ₃ and the operator o ₅ are placed on the device respectively. 2 and device 0 to get a new placement strategy.

3) Guided by the cost evaluation model evaluation of the fusion of computing cost, communication cost, and load cost, iteratively update the placement strategy

As shown in Figure 4, the cost of the original placement strategy and the new placement strategy are calculated separately by using the cost evaluation model of the fusion of computing cost, communication cost and load cost; then the cost of the two groups of placement strategies is compared, and the placement with the lower cost is selected. The strategy is used as the initial placement strategy of the next round of iteration; finally, the operator pair R selected in the current round of gene mutation is used as a high-quality operator pair of the current placement strategy, indicating that the current placement information of the operator on the operator pair can make The cost of the strategy becomes smaller.

The overall flow of the gene mutation method is shown in Algorithm 4:

Among them, choose_gene means to select a gene from the population; genes_info means the operator placement information on the specified gene; add_good_gene means to use the gene as a high-quality gene; target_device means to select the target placement device; update_population means to update the gene information of the specified population; cost_model means calculation and communication , the cost evaluation model of load fusion calculates the comfort degree π _θ of the specified population.

The gene swap method consists of two steps: high-quality operator pair cross swap method and iterative update.

1) Based on the high-quality operator pair cross-exchange method, the genetic information of the two groups of placement strategies is exchanged.

The high-quality operator pair cross-exchange method is to assign the respective high-quality operator pairs in the two sets of placement strategies to each other, that is, update the respective high-quality operator placement information to the same operator of the other party, so as to generate two sets with each other. New placement strategy for operator placement information.

As shown in FIG. 5 , the high-quality operator pairs of the first placement strategy retain the high-quality operator pairs R ₁₂ ={1,0} and R ₃₅ ={2,0} obtained during the gene mutation process. The high-quality operator pairs R ₂₄ ={2,1} and R ₁₃ ={1,0} remain in the high-quality operator pair group of the second set of placement strategies. The high-quality operator pair cross-exchange method updates the high-quality operator pairs R ₁₂ and R ₃₅ of the first set of placement strategies to the second set of placement strategies, which means that operator o ₁ and operator o ₂ in the second set of placement strategies are updated They are placed on device 1 and device 0, respectively, and operator o ₃ and operator o ₅ are placed on device 2 and device 0, respectively. Similarly, the second set of placement strategies will also update its own high-quality operator pairs R ₂₄ and R ₁₃ to the first set of placement strategies, which means that operators o ₂ and o ₄ of the first set of placement strategies are placed respectively. On device 2 and device 1, operator o ₁ and operator o ₃ are placed on device 1 and device 0, respectively. Through the above-mentioned high-quality operator pair cross-exchange method, two new placement strategies with placement information of each other's operators are generated.

2) Iteratively update the placement strategy under the guidance of the cost evaluation model evaluation of the fusion of computing cost, communication cost, and load cost.

Consistent with the iterative update in the gene mutation method, the survival of the fittest in the gene swap method also uses a cost evaluation model that integrates computing cost, communication cost and load cost to judge the pros and cons of the old and new populations generated by genome crossover and retain the relative quality species. In addition, in order to maintain the diversity of genes in the sibling populations and prevent the genetic information of the sibling populations from converging during the iteration process, the high-quality genomes of both populations will be cleared after each gene exchange occurs.

The overall flow of the gene swap method is shown in Algorithm 5:

Step 3: When the iteration termination condition is reached, the two sets of placement strategies are respectively transformed into the operator placement strategies of the data flow graph, and the model is trained according to the operator placement strategies obtained by iteration in the real environment, so as to select the shortest execution time. The strategy is used as the optimal distributed scheduling strategy of the model.

The conditions for the termination of the iteration include that the total number of iterations reaches a specified threshold and the placement strategy does not change within a certain number of iterations. The iteration is terminated when the iterative process of the dual-population genetic algorithm satisfies one of the above two conditions.

Step 4: Using the obtained distributed scheduling strategy, perform distributed scheduling of the AI model to be trained, and input the data sets required by the image recognition, natural language processing and other models into the neural network for distributed training.

According to the above steps to construct the solution space and the method based on the dual population genetic algorithm, the specific process of the deep learning adaptive training method based on the genetic algorithm proposed in this paper is as follows:

(1) First, the solution space of integer linear programming problem is constructed based on the computation graph and device topology graph, and the scale of the solution space is simplified by using assumption constraints and operator grouping constraints.

(2) Secondly, the method based on random and specified strategy initializes two sets of initial placement strategies required by the dual population genetic algorithm. The two groups of placement strategies are iteratively updated based on the cost evaluation model of the fusion of computational cost, communication cost and load cost to guide the gene mutation method and gene exchange method.

(3) Then, when the iteration termination condition is reached, the placement strategies obtained by the two sets of iterations are converted into the operator placement strategies of the data flow graph, and the model is trained in the real environment, and the execution time of the two sets of placement strategies is selected. The shorter policy is used as the optimal distributed scheduling policy for the model.

(4) Finally, use the obtained distributed scheduling strategy to perform distributed scheduling of the AI model to be trained, and input the data sets required by the image recognition, natural language processing and other models into the neural network for distributed training.

The specific description of this method is shown in Algorithm 6:

Among them, rows 1-2 extract the computational graph of the model, and simplify the computational graph based on the ablation method constrained by operator grouping.

The third behavior uses the placement strategy initialization method described in Algorithm 1 and Algorithm 2 to generate two sets of initial placement strategies P1 and P2 in the solution space.

Lines 4-11 use the dual population genetic algorithm to iteratively update the two groups of placement strategies, where op_pair_swap represents the iterative method based on gene swap described in Algorithm 5, op_pair_variation represents the iterative method based on gene mutation described in Algorithm 4, and finish_condition represents the end of the iteration conditions, such as when the two sets of initial placement strategies no longer change over multiple iterations. Therefore, when the specified number of iterations is reached or the iteration end condition is met, the search process of the dual-population genetic algorithm is terminated.

Line 12 transforms the two sets of placement strategies after iteration into the operator placement strategies of the data flow graph.

Lines 13-20 execute the two sets of operator placement strategies in the real execution environment, and use the set of placement strategies with short execution time as the optimal strategy for model-parallel operator placement.

Lines 21-22 use the obtained distributed scheduling strategy to perform distributed scheduling of the model, input the dataset into the model for distributed training, and return the trained model.

Based on the method in this paper, the training speed of neural network models in artificial intelligence fields such as image recognition and natural language processing can be accelerated.

Table 1 Performance comparison of single-GPU, Beachi and dual-population genetic algorithm strategies

The experimental results of the present invention and the m_topo, m_etf, m_sct methods of the single GPU and Beachi framework are shown in Table 1. The random of GA (random/m_topo/m_etf/m_sct) in the table indicates that the random initialization method is used to initialize two groups of placement strategies and m_topo , m_etf and m_sct represent initialization using a specified strategy, that is, one of the two groups of initial placement strategies required by the present invention selects m_topo or m_etf or m_sct for initialization, and another group of experimental random initialization methods are initialized. GA is the experimental result of the present invention. It can be seen from Table 1 that the strategy searched by the present invention is generally better than the three strategy search algorithms of Baechi. Compared with the m_topo algorithm, it can be improved by up to 8.9%; It can be improved by 42.2%; compared with m_sct, it can be improved by up to 40.4%. The genetic algorithm uses the specified strategy initialization method to initialize the placement strategy, and iteratively updates the strategy based on it. Compared with the original strategy, the single-step execution time of the obtained strategy can be improved by up to 9%. In addition, Baechi will encounter OOM (out-of-memory) when the batch size is large, which makes the strategy impossible to execute, while the dual-population genetic algorithm can control the load balancing of devices in the cluster to prevent OOM.

Claims (8)

1. a neural network adaptive distributed parallel training method based on genetic algorithm, is characterized in that comprising the following steps: Step 1: Transform the operator placement problem in the neural network model into an integer linear programming problem; build a solution space based on the data flow graph and device topology graph of the neural network model, and simplify the scale of the solution space by setting assumption constraints and operator grouping constraints : 1-1. Extract the structure of the neural network model and set up a device resource group, and abstractly obtain the computation graph G(O, E) and the device topology graph D. In the computation graph G(O, E), the vertex O represents the computation of the neural network model. Subset, E represents the set of directed edges between vertices, and the device topology graph D is composed of M computing devices; 1-2, given the calculation graph G(O, E) and the device topology graph D, on the premise of satisfying the device memory constraints, find a set of placement strategies to minimize the execution cost, so that the operators of the neural network model are placed on the device. The placement problem is transformed into an integer linear programming problem, and the solution space is constructed based on the data flow graph and device topology graph; 1-3, by analyzing the device characteristics in the homogeneous cluster and the execution characteristics of the neural network model, two assumptions are made: the computing and communication performance of homogeneous devices are the same; the execution end time of operators is only related to operators with direct dependencies. ; Through the above assumptions, the placement of two operators with data dependencies is constrained to two: one is that the two operators are placed on the same device, and the other is that the two operators are placed on different devices; 1-4, the operator grouping constraint is then proposed. If there are two operators with data dependencies, if one of the operators satisfies the condition that the out-degree or in-degree is 1, the two operators are constrained to the same group, and Scheduling the operators in the group as a whole; Step 2: Build a cost evaluation model that integrates computing cost, communication cost and load cost, comprehensively evaluates the pros and cons of the solution of the integer linear programming problem, that is, the execution performance of the operator placement strategy, and guides the dual population genetic algorithm in the two placement strategies. During the period, gene mutation and gene exchange are performed iteratively to update two sets of placement strategies: 2-1, build a cost evaluation model that integrates computing cost, communication cost and load cost Firstly, the key factors affecting the execution performance of the neural network model are analyzed, and the real execution time of the operators in the neural network model on the device is used to establish the calculation cost _Li ; the total tensor size of the cross-device communication between operators in the neural network model is used. , establish the communication cost W; use the sum of the ratio of the memory load offset and the average load of each device to establish the load cost f; Secondly, by comprehensively considering the characteristics of the calculation cost, communication cost, load cost and the actual training process of the model, a cost evaluation model integrating the calculation cost, communication cost and load cost is established: π _θ =(∑L _i +λ×Ω(W))×(1+f) Among them, π _θ represents the execution cost of the placement strategy, λ represents the weight ratio, and Ω represents the linear fitting model of tensor size and communication time; 2-2. Iteratively update placement strategy based on dual population genetic algorithm First, using the initialization method of the placement strategy, two sets of placement strategies with initial operator placement information are generated in the solution space; Secondly, based on the cost evaluation model, the gene mutation and gene exchange methods of the dual population genetic algorithm are guided, and the placement information of the operators in the two placement strategies is updated iteratively; Step 3: When the termination condition of the iterative update of the placement strategy is reached, the two sets of placement strategies are respectively transformed into the operator placement strategies of the data flow graph, and the neural network model is trained according to the iteratively obtained operator placement strategies in the real environment. , select the strategy with the shortest execution time as the optimal distributed scheduling strategy of the neural network model; Step 4: Use the optimal distributed scheduling strategy obtained in Step 3 to perform distributed scheduling of the neural network model to be trained, and input the data set required by the neural network model into the neural network model for distributed training. 2. a kind of neural network adaptive distributed parallel training method based on genetic algorithm according to claim 1, is characterized in that: the computation graph G (O, E) described in step 1-1 is by the neural network model Data flow graph abstraction is obtained. 3. a kind of neural network adaptive distributed parallel training method based on genetic algorithm according to claim 1, is characterized in that: the key factor described in step 2-1 is computing performance, communication performance and memory load of equipment Characteristics. 4. a kind of neural network adaptive distributed parallel training method based on genetic algorithm according to claim 1, is characterized in that: initialization method described in step 2-2 comprises random initialization method and specified strategy initialization method; The random initialization method refers to assigning the operators in the calculation graph G(O, E) to the device topology graph D in a random manner; The specified strategy initialization method refers to the placement strategy searched by the existing parallel strategy search method as the initial state; Choose an initialization method to initialize the placement strategy. 5. a kind of neural network self-adaptive distributed parallel training method based on genetic algorithm according to claim 1, is characterized in that: the termination condition of iterative update described in step 3 comprises that total number of iterations reaches specified threshold and placement strategy No change will occur within a certain number of iterations; When the iterative process of the dual population genetic algorithm satisfies one of the above two conditions, the iteration is terminated. 6. a kind of neural network adaptive distributed parallel training method based on genetic algorithm according to claim 1 is characterized in that: the gene mutation method described in step 2-2 comprises three steps: (1) Based on the principle of maximum cost priority, select the operator pair with the largest overall cost in each group of placement strategies as the gene mutation operator; (2) Using the gene mutation method to generate a new placement strategy by changing the placement information of the gene mutation operator; (3) Guided by the evaluation of the cost evaluation model, iteratively update the placement strategy; The gene swap method consists of two steps: (1) Based on the cross-exchange method of high-quality operator pairs, the genetic information of the two groups of placement strategies is exchanged; (2) Guided by the evaluation of the cost evaluation model, the placement strategy is updated iteratively. 7. a kind of neural network adaptive distributed parallel training method based on genetic algorithm according to claim 6, is characterized in that: described overall cost is calculated as follows:

in,

Represents the number of times the operator pair R _ij has been selected, decay represents the dynamic decay rate, Li and L _j represent the computational cost of the operator o _i and the operator o _j respectively, S _{i,j represent} the operator o _i and the operator o transfer tensor size between _j ,

Represents the overall cost of the operator to R _ij . 8. a kind of neural network adaptive distributed parallel training method based on genetic algorithm according to claim 6, is characterized in that: the rule of described gene variation is as follows: (1) If the two operators in the currently selected operator pair are placed on different devices, then randomly select an available device and place the two operators on the device; (2) If the currently selected operator is placed on the same device, then randomly select two available devices and place the two operators on these two different devices.

Images