On the Impact of Graph Embedding on Device Placement

Abstract: Modern neural network (NN) models require more data and parameters in or- der to perform ever more complex tasks. When an NN model becomes too massive to fit on a single machine, it may need to be distributed across multi- ple machines. What policies should be used when distributing an NN model, and more concretely how different parts of the model should be disseminated across the various machines is called the device placement problem. Tackling the matter is the focus of this thesis.Previous approaches have required the placement policies to be created manually by human experts. Since that method does not scale well, the cur- rent efforts to tackling the device placement problem focus on automating the process using reinforcement learning (RL). Most of the RL systems contain different kinds of graph embedding modules.Our work tries to increase the knowledge about how to tackle the device placement problem by measuring and assessing the impact of graph embed- dings on the quality of the device placement policies. We compare the dif- ferent approaches in two main ways: runtime improvement and computation time. The former is a metric of how much faster is the new placement policy compared to a baseline. The latter describes how much time is required by the system to achieve that runtime improvement. In this thesis, we build on previous efforts in the device placement field in order to explore how different state-of-the-art graph embedding architectures affect device placement poli- cies. The graph embedding architectures we compare are Placeto (used as a baseline), GraphSAGE and P-GNN.In terms of runtime improvement, we achieve an increase of 23.967% when using P-GNN compared to Placeto, and 31.164% absolute improvement from the initial placement. GraphSAGE produces 1.165% better results than Placeto with the same setup. Regarding computation time, GraphSAGE has a gain of 11.560% compared to Placeto, whereas P-GNN is 6.950% slower than the baseline.Given our results, we can confirm that graph embedding architecture can have a significant impact on device placement policies and their performance. More complex graph embedding architectures that capture more data about the graph and its topology provide better runtime improvements. However, that complexity may come at the cost of the computation time required to train the placement system.