Research On Dataflow Graph Partition Strategy Based On Graph Neural Network

Tasks are often modeled as dataflow graphs(e.g.,a neural network task graph,a task in a dataflow computer)in parallel and distributed computing.Parallel execution of tasks requires partitioning of dataflow graphs.The partitioning of dataflow graphs,however,has been proved to be NP-complete.A plethora of greedy and heuristic algorithms,such as list scheduling,clustering-based scheduling and ant colony algorithms.These algorithms only consider partial information of dataflow graphs,so the partitioning performance of these strategies is not stable.In order to tackle this issue,neural network based methods have been adopted,such as sequence-to-sequence neural network and reinforcement learning.Because of the spatial complexity,irregularity and disorder of the graph,the sequence-to-sequence neural network model is still unable to describe the characteristic information of the graph.Aiming at the above issues,in order to fully learn the characteristic information affecting the effect of dataflow graph partitioning,the dataflow graph partitioning model adopts two-layer graph convolutional neural network and the proximal policy optimization.And it adds the dataflow graph communication cost and processors' running states into the model,so as to produce the partitioning strategy.Then the execution of the dataflow graph under the partitioning strategy is simulated in the environment,and the runtime is used as a reward signal to train the model,so as to produce a better partitioning strategy over time.Experiment results show that the partitioning model based on the two-layer graph convolutional neural network reduces the running time of a task by 8% to 15% compared with the partitioning strategy of other graph neural network models(GAT,Graph SAGE),and 15% to 25% compared with the traditional(HEFT,LC,CPOP)algorithms and the sequence-to-sequence model.