Year: 2019

Abstract:
Runtime and scalability of large neural networks can be significantly affected by the placement of operations in their dataflow graphs on suitable devices. With increasingly complex neural network architectures and heterogeneous device characteristics, finding a reasonable placement is extremely challenging even for domain experts. Most existing automated device placement approaches are impractical due to the significant amount of compute required and their inability to generalize to new, previously held-out graphs. To address both limitations, we propose an efficient end-to-end method based on a scalable sequential attention mechanism over a graph neural network that is transferable to new graphs. On a diverse set of representative deep learning models, including Inception-v3, AmoebaNet, Transformer-XL, and WaveNet, our method on average achieves 16% improvement over human experts and 9.2% improvement over the prior art with 15× faster convergence. To further reduce the computation cost, we pre-train the policy network on a set of dataflow graphs and use a superposition network to fine-tune it on each individual graph, achieving state-of-the-art performance on large hold-out graphs with over 50k nodes, such as an 8-layer GNMT.

heading: 1 INTRODUCTION
text: Neural networks have demonstrated remarkable scalability–improved performance can usually be achieved by training a larger model on a larger dataset (Hestness et al., 2017; Shazeer et al., 2017; Jozefowicz et al., 2016; Mahajan et al., 2018; Radford et al.). Training such large models efficiently while meeting device constraints, like memory limitations, necessitate partitioning of the underlying dataflow graphs for the models across multiple devices. However, devising a good partitioning and placement of the dataflow graphs requires deep understanding of the model architecture, optimizations performed by domain-specific compilers, as well as the device characteristics, and is therefore extremely hard even for experts.
ML practitioners often rely on their understanding of model architecture to determine a reasonable partitioning and placement for graphs. However, relying solely on the model architecture while ignoring the effect of the partitioning on subsequent compiler optimizations like op-fusion can lead to sub-optimal placements and consequently under-utilization of available devices. The goal of automated device placement is to find the optimal assignment of operations to devices such that the end-to-end execution time for a single step is minimized and all device constraints like memory limitations are satisfied. Since this objective function is non-differentiable, prior approaches (Mirhoseini et al., 2017; 2018; Gao et al., 2018) have explored solutions based on reinforcement learning (RL). However, these RL policies are usually not transferable and require training a new policy from scratch for each individual graph. This makes such approaches impractical due to the significant amount of compute required for the policy search itself, at times offsetting gains made by the reduced step time.
In this paper, we propose an end-to-end deep RL method for device placement where the learned policy is generalizable to new graphs. Specifically, the policy network consists of a graph-embedding network that encodes operation features and dependencies into a trainable graph representation, followed by a scalable sequence-to-sequence placement network based on an improved Transformer (Vaswani et al., 2017; Dai et al., 2019). The placement network transforms the graph representations into a placement decision with soft attention, removing hard constraints such as hierarchical
grouping of operations (Mirhoseini et al., 2018) or co-location heuristics (to reduce the placement complexity) (Mirhoseini et al., 2017). Both of our graph-embedding network and placement network can be jointly trained in an end-to-end fashion using a supervised reward, without the need to manipulate the loss functions at multiple levels. We empirically show that the network learns flexible placement policies at a per-node granularity and can scale to problems over 50,000 nodes.
To generalize to arbitrary and held-out graphs, our policy is trained jointly over a set of dataflow graphs (instead of one at a time) and then fine-tuned on each graph individually. By transferring the learned graph embeddings and placement policies, we are able to achieve faster convergence and thus use less resources to obtain high-quality placements. We also use super-positioning, i.e., a feature conditioning mechanism based on the input graph embeddings, to effectively orchestrate the optimization dynamics of graphs with drastically different sizes in the same batch.
Our contributions can be summarized as follows:
1. An end-to-end device placement network that can generalize to arbitrary and held-out graphs. This is enabled by jointly learning a transferable graph neural network along with the placement network.
2. A scalable placement network with an efficient recurrent attention mechanism, which eliminates the need for an explicit grouping stage before placement. The proposed end-to-end network provides 15× faster convergence as compared to the hierarchical LSTM model used in earlier works (Mirhoseini et al., 2017; 2018).
3. A new batch pre-training and fine-tuning strategy based on network superposition, which leads to improved transferability, better placements especially for larger graphs, and 10× reduction in policy search time as compared to training individual graphs from scratch.
4. Superior performance over a wide set of workloads, including InceptionV3 (Szegedy et al., 2015), AmoebaNet (Real et al., 2018), RNNs, GNMT (Wu et al., 2016), Transformer-XL (Dai et al., 2019), WaveNet (van den Oord et al., 2016), and more.

heading: 2 RELATED WORK
text: Device Placement Reinforcement learning has been used for device placement of a given dataflow graph (Mirhoseini et al., 2017) and demonstrated run time reduction over human crafted placement and conventional heuristics. For improved scalability, a hierarchical device placement strategy (HDP) (Mirhoseini et al., 2018) has been proposed that clusters operations into groups before placing the operation groups onto devices. Spotlight (Gao et al., 2018) applies proximal policy optimization and cross-entropy minimization to lower training overhead. Both HDP and Spotlight rely on LSTM controllers that are difficult to train and struggle to capture very long-term dependencies over large graphs. In addition, both methods are restricted to process only a single graph at a time, and cannot generalize to arbitrary and held-out graphs. Placeto (Addanki et al., 2019) represents the first attempt to generalize device placement using a graph embedding network. But like HDP, Placeto also relies on hierarchical grouping and only generates placement for one node at each time step. Our approach (GDP) leverages a recurrent attention mechanism and generates the whole graph placement at once. This significantly reduces the training time for the controller. We also demonstrate the generalization ability of GDP over a wider set of important workloads.
Parallelization Strategy Mesh-TensorFlow is a language that provides a general class of distributed tensor computations. While data-parallelism can be viewed as splitting tensors and operations along the “batch” dimension, in Mesh-TensorFlow the user can specify any tensor-dimensions to be split across any dimensions of a multi-dimensional mesh of processors. FlexFlow (Jia et al., 2018) introduces SOAP, a more comprehensive search space of parallelization strategies for DNNs which allows parallelization of a DNN in the Sample, Operator, Attribute, and Parameter dimensions. It uses guided randomized search of the SOAP space to find a parallelization strategy for a specific parallel machine. GPipe (Huang et al., 2018) proposed pipeline parallelism, by partitioning a model across different accelerators and automatically splitting a mini-batch of training examples into smaller micro-batches. By pipelining the execution across micro-batches, accelerators can operate in parallel. Our GDP focuses on a general deep RL method for automating device placement on arbitrary graphs, and is therefore orthogonal to existing parallelization strategies.
Compiler Optimization REGAL (Paliwal et al., 2019) uses deep RL to optimize the execution cost of computation graphs in a static compiler. The method leverages the policy’s ability to transfer to new graphs to improve the quality of the genetic algorithm for the same objective budget. However, REGAL only targets peak memory minimization while GDP focuses on graph run time and scalability while also meeting the peak memory constraints of the devices. Specifically, we generalize graph partitioning and placement into a single end-to-end problem, with and without simulation, which can handle graphs with over 50,000 nodes.

heading: 3 END-TO-END PLACEMENT POLICY
text: Given a dataflow graph G(V,E) where V represents atomic computational operations (ops) and E represents the data dependency, our goal is to learn a policy π : G 7→ D that assigns a placement D ∈ D for all the ops in the given graph G ∈ G, to maximize the reward rG,D defined based on the run time. D is the allocated devices that can be a mixture of CPUs and GPUs. In this work, we represent policy πθ as a neural network parameterized by θ.
Unlike prior works that focus on a single graph only, the RL objective in GDP is defined to simultaneously reduce the expected runtime of the placements over a set of N dataflow graphs:
J(θ) = EG∼G,D∼πθ(G)[rG,D] ≈ 1
N ∑ G ED∼πθ(G)[rG,D] (1)
In the following, we refer to the case whenN = 1 as individual training and the case whenN > 1 as batch training. We optimize the objective above using Proximal Policy Optimization (PPO) (Schulman et al., 2017) for improved sample efficiency.
Figure 1 shows an overview of the proposed end-to-end device placement network. Our proposed policy network πθ consists a graph embedding network that learns the graphical representation of any dataflow graph, and a placement network that learns a placement strategy over the given graph embeddings. The two components are jointly trained in an end-to-end fashion. The policy p(a|G) is applied to make a set of decisions at each node. These decisions, denoted as av for each v ∈ V across all nodes, form one action a = {av∈V }. One decision corresponds to playing one arm of a multi-bandit problem, and specifying the entire a corresponds to playing several arms together in a single shot. Note the architecture is designed to be invariant over the underlying graph topology, enabling us to apply the same learned policy to a wide set of input graphs with different structures.

heading: 3.1 GRAPH EMBEDDING NETWORK
text: We leverage graph neural networks (GNNs) (Hamilton et al., 2017; Xu et al., 2019; You et al., 2018) to capture the topological information encoded in the dataflow graph. Most graph embedding frameworks are inherently transductive and can only generate embeddings for a given fixed graph. These transductive methods do not efficiently extrapolate to handle unseen nodes (e.g., in evolving graphs), and cannot learn to generalize to unseen graphs. GraphSAGE (Hamilton et al., 2017) is an inductive framework that leverages node attribute information to efficiently generate representations
on previously unseen data. While our proposed framework is generic, we adopt the feature aggregation scheme proposed in GraphSAGE to model the dependencies between the operations and build a general, end-to-end device placement method for a wide set of dataflow graphs.
In GDP, nodes and edges in the dataflow graph are represented as the concatenation of their meta features (e.g., operation type, output shape, adjacent node ids) and are further encoded by the graph embedding network into a trainable representation. The graph embedding process consists of multiple iterations, and the computation procedure for the l-th iteration can be outlined as follows:
First, each node v ∈ V aggregates the feature representations of its neighbors, {h(l)u ,∀u ∈ N (v)}, into a single vector h(l)N (v). This aggregation outcome is a function of all previously generated representations, including the initial representations defined based on the input node features. In this work, we use the following aggregation function with max pooling:
h (l) N (v) = max(σ(W (l)h(l)u + b (l)),∀u ∈ N (v)) (2)
where (W (l), b(l)) define an affine transform and σ stands for the sigmoid activation function. We then concatenate the node’s current representation, h(l)v , with the aggregated neighborhood vector, h (l) N (v), and feed this concatenated vector through a fully connected layer f (l+1)
h(l+1)v = f (l+1)(concat(h(l)v , h (l) N (v))) (3)
Different from GraphSAGE, parameters in our graph embedding network are trained jointly with a placement network via stochastic gradient descent with PPO, in a supervised fashion, as described in Section 3. That is, we replace the unsupervised loss with our task-specific objective.

heading: 3.2 PLACEMENT NETWORK
text: The graph neural network works as a feature aggregation network that learns a trainable feature representation for the computational graph, we still need a policy network that produces actions on a per node basis. Given hv’s, the policy network produces av’s through conditionally independent predictions, where the prediction for one node v does not depend on the prediction of other nodes.
p(a|G) = ∏ v p(av|G) = ∏ v p(av|f(hv)) (4)
While f can be represented using multilayer perceptrons (MLPs), where the MLPs is shared across all nodes for prediction the placement output distributions. However, MPLs lack a dependency tracking mechanism across nodes. In practise, the placement of one node can be determined by the placement of another node, where the placed node may consume a large size of data produced by the other node. Intuitively, an attention network can learn this dependency and the relative importance of dependencies across an entire graph. Therefore, we decide to use an attention-based placement network to better track inter-node placement-related dependencies.
Designing a scalable placement network that can generalize to graphs with thousands of nodes is challenging, as the conventional GNMT models proposed for language tasks usually target a shorter sequence length. Hierarchical placement (Mirhoseini et al., 2018) has been proposed to address this issue,however, the proposed grouper network comes with limited flexibility and generality. For example, the grouper network leverages an aggregated feature representation by averaging feature vectors for nodes within the same group. The non-differentiable grouping procedure prevents training the graph-embedding and placement networks end-to-end.
To remove the two-stage hierarchical workflow in HDP for improved scalability, we propose to use a Transformer-based attentive network to generate operation placements in an end-to-end fashion. As the graph embedding already contains spatial (topological) information for each node, we remove the positional embedding in the original transformer to prevent the model from overfitting node identifications. To capture long-term dependencies efficiently among a large set of nodes, we adopt segment-level recurrence introduced in Transformer-XL (Dai et al., 2019; Dai, 2019), where hidden states computed for the previous set of nodes are cached (with gradient flows disabled) and reused as an extended context during the training of the next segment. Besides achieving extra long context,
we empirically find the segment-level recurrent attention much faster than a conventional LSTMbased GNMT model. In our experimental evaluation, we compare both the performance and speed up of our placement network with that of the LSTM-based hierarchical device placement.

heading: 3.3 BATCH TRAINING WITH PARAMETER SUPERPOSITION
text: Since the parameterization for the architecture of the end-to-end policy is designed to be invariant over input graphs with different topologies, the same placement policy can be shared across a wide set of workloads. We therefore propose a batch training strategy, and further enhance the aforementioned architecture to handle such generalization across graphs.
Naı̈ve batch training is challenging in our context as different dataflow graphs contain different number of operations connected in different topologies. In addition, unlike previous device placement methods, GDP aims to handle graphs from potentially different application domains (e.g. computer vision, language, and speech), where the number of operations can range from a few thousand to one million. These graphs have drastically different network architecture, in terms of computational operations, data shape, and network topology. As an example, recurrent networks have completely different operation types and connections compared to multi-branch convolutional networks that are widely used in computer vision. It would be highly desirable to train a single shared network that maximizes information sharing across these heterogeneous tasks, without hurting the performance on each of them due to their distinct learning dynamics.
Along a similar direction of multi-task learning and few-shot learning (Oreshkin et al., 2018), we propose a feature conditioning mechanism similar to parameter superposition (Cheung et al., 2019). The idea is to train one shared policy, but condition its parameters based on the input features to mitigate the potentially undesirable interference among different input graphs. Since dense layers (affine transforms followed by nonlinearity) serve as the fundamental building blocks in all of our network components, we introduce an additional conditioning layer to enable superposition in all dense layers the placement network:
x(l+1) = g(l)(c(x(0)) x(l)) (5) where g(l) stands for a dense layer in our policy network, c stands for the feature conditioning layer, and x(0) denotes the feature representation of the input graph generated by the graph-embedding network. The feature conditioning layer is implemented with minimum overhead by adding an additional transformer layer to our placement network.

heading: 4 EXPERIMENT

heading: 4.1 EXPERIMENT SETUP
text: In this section, we evaluate our training strategy on widely used machine learning models in computer vision, natural language processing, and speech domains. We compare our approach to human expert placement, TensorFlow METIS placement, and hierarchical device placement (HDP) (Mirhoseini et al., 2018). Our experiments are run on machines with one Intel Broadwell CPU and up to eight Nvidia P100 GPUs. Note that the prior work (Mirhoseini et al., 2017; 2018; Gao et al., 2018) were evaluated on different GPU devices, preventing direct comparison of results. Therefore, we re-evaluate HDP on our own system environment and report those numbers.
The performance of a placement is evaluated by the resulted training step time (run time) of the neural network. We use the negative square root of the normalized run time as the reward, where the run time is normalized with the best run time from a baseline. We use the average reward of all the previous trials as a bias term. The advantage value is computed by subtracting the reward by the average reward. During the search, we apply a large negative reward (-10) for invalid placements (e.g. a violation of co-location constraint, out of memory, etc.). For operation scheduling, we rely on the Tensorflow default FIFO scheduling.

heading: 4.2 PERFORMANCE ON INDIVIDUAL GRAPHS
text: We evaluate GDP by training the model separately on six important graphs, including RNN Language Modeling, GNMT (Sutskever et al., 2014), Transformer-XL, Inception, AmoebaNet, and
WaveNet. We name this approach GDP-one. For all the tasks, GDP-one consistently outperforms human expert placement, TensorFlow METIS (Karypis & Kumar, 1998) placement, and HDP. For extremely large graphs, GDP-one is only 6% worse on 8-layer NMT (over 60k nodes), compared to human placement, but is 6.8% better than HDP. Overall, GDP-one achieves on average more than 16% run time reduction across the evaluated 12 graphs, compared to human expert placement. Compared to hierarchical device placement, GDP-one achieves an average 9.2% speed up, and scales better to large graphs such as 8-layer NMT and 4-layer RNNLM. Importantly, with the efficient end-to-end training and sample efficient reinforcement learning algorithm, GDP-one has a 15x speed up in convergence time of the placement network over HDP.

heading: 4.3 GENERALIZATION
text: GDP enables the training of multiple heterogeneous graphs in a single batch, sharing parameters in the graph-embedding network and the placement network. We name this training strategy GDPbatch. We empirically show that GDP-batch generates better placements for many workloads such as transformer-XL (7.6%), WaveNet (15%), and 8-layer GNMT (8%). Table 2 compares the run time of 11 tasks using GDP-batch, with the same end-to-end architecture as described in section 4.2. GDP-batch yields slightly better run time compared to GDP-one in majority of the tasks, while being only slightly worse on AmoebaNet. Compared to training graphs separately, GDP-batch reduces network parameters and enables transfer learning among different graphs.
We further evaluate the effect of transfer learning by mixing redundant tasks in a batch. We find that mixing different graphs such as RNNLM and GNMT models with different number of layers results in both faster and better learning for RNNLM and GNMT with large number of layers (8- layer). As a matter of fact, both Placeto (Addanki et al., 2019) and HDP had problems matching human placement performance for 8-layer GNMT or 8-layer RNNLM. With batch training, GDP is the first device placement work to match human expert performance for both 8-layer GNMT and 8-layer RNNLM. We also for the first time show that GDP-batch not only improves the search time (since we do not retrain the policy for every new graph), it can also improve the performance of the found placements. More detailed results are shown in Appendix Table 5.
Generalization to hold-out graphs: Here we show another set of experiments where we treat GDPbatch as a pre-training strategy and remove the target graph from the batch training dataset. We then fine-tune the pre-trained model on the hold-out graphs for fewer than 50 steps, which takes less than one minute. We name this GDP-generalization+finetune. Figure 2 shows that GDP fine-tuning for hold-out graphs outperforms human expert placement and HDP consistently on all six batch training datasets, and performs only slightly worse than GDP-one. 2-layer RNNLM and 2-stack WaveNet almost match the performance of GDP-one. We also run inference (generate placement) directly on the pre-trained model for the target hold-out graphs, and name this GDP-generalization-zeroshot. We find that GDP-generalization-zeroshot only marginally hurts performance as compared to GDPgeneralization+finetune, while being slightly better than human placement and HDP. This indicates that both graph embedding and the learned policies transfer and generalize to the unseen data.
Comparisons with other generalized placement approaches: Placeto (Addanki et al., 2019), to our knowledge, is the only other method beside GDP that shows true (and non-simulated) generalized device placement results. Direct comparison is not possible since Placeto uses a different hardware platform and different input graphs (Inception-V3, NMT, and NASNet). Placeto’s search time is on average 2.65x faster than HDP, while GDP is on average 15x faster than HDP on our larger set of graphs. Apart from search time speed up, Placeto on average reduces placed graph run time by 3% (for its different graphs and hardware) while GDP on average reduces placed graph run time by 9.2%, compared to HDP. One advantage of GDP over Placeto is that it does not rely on any initial feasible placement. Providing a reasonable initial placement is often non-trivial for domain experts, especially for larger graphs such as 8-layer GNMT. As such, we are the first to report superhuman results on 8-layer GNMT (with GDP-batch).

heading: 4.4 ABLATION STUDIES
text: Attention and Superposition. We did an ablation study on the attention and the superposition layer in the transformer-XL placer network. We find that attention improves placement run time by an average of 18% compared to a placer network with no attention, and superposition improves placement run time by an average of 6.5% where all the graphs are trained in a single batch as described in Section 4.3. Without superposition network, batch training fails for AmoebaNet and Inception when mixing with larger RNNLM or GNMT models (4-layer).
Pre-training graph embeddings. We also evaluate a fine-tuning strategy by pre-training the graph embedding and placement network and fine-tuning the network on the down stream tasks. The difference here compared to Section 4.3 is that we also include the target graphs in the pre-training
dataset. When GDP-batch is used as a pre-training strategy, the graph embedding and placement network assimilate meaningful graph representations and placement policies from a wide set of graphs, thus can be used as a strong baseline network for fine-tuning on downstream tasks. We compare the generated placement run time and the placement search time, normalized to GDP-one. We find that fine-tuning further reduces the the placed graph run time by an average of 5% and placement search time by an average of 86%, compared to GDP-one.

heading: 5 CONCLUSION
text: In this paper, we present a generalized device placement strategy that uses a graph neural network and super-positioning to generalize to arbitrary and held out graphs. Through experimental evaluation over a wide set of representative graphs from different domains including computer vision, speech, and NLP, we demonstrated over 15 times faster convergence while achieving a 16% and 9.2% reductions in step time over human expert placement and HDP, respectively.

heading: ACKNOWLEDGMENTS
text: TBD

heading: 6 APPENDIX

heading: 6.1 PROXIMAL POLICY OPTIMIZATION
text: In device placement, the objective is to minimize the training step time of a given computational graph or a batch of dataflow graphs for a target system configuration (e.g. a 8-GPU cluster or a TPU pod), by placing operations onto different devices to enable model-level parallelism. This process corresponds to maximizing the expected performance in the MDP. For better sample efficiency, we adopted a Proximal Policy Optimization (PPO) (Schulman et al., 2017) algorithm. The objective is to maximize a surrogate objective:
Lπ = Ea[0:n]∼π[ q′(an|sn) q(an|sn) Aπ(sn, an)]
Lπ = max π′
1
N N−1∑ n=0,an∼π [min( q′(an|sn) q(an|sn) (R−R), clip(q ′(an|sn) q(an|sn) , 1− , 1 + )(R−R))]
Within a loop, GDP PPO continuously samples placements from the distribution and evaluates their training times in real systems. For a rollout of K, we perform a minimatch of m stochastic gradient ascent steps with respective to the objective of proximal policy optimization, which makes incremental policy improvements. The rollout steps K and minibatch size m are hyper parameters for PPO. We find a set of optimized hyper parameters and keep them fixed for all the experiments presented. As the rewards are generated on-the-fly based on real system measurements, we no longer need to re-evaluate the placement solutions in a separate phase.

heading: 6.2 HYPERPARAMETERS
text: In this section, we list out all the selected hyperparameters in our experiments for reproducibility in Table 3 and Table 4.

heading: 6.3 INPUT GRAPHS
text: We used a variety of widely used workloads from computer vision, speech, and NLP. In this section, we give a detailed explanation on the selected models and hyperparameters.

heading: 6.3.1 INCEPTION-V3
text: Inception-V3 (Szegedy et al., 2015) is a multi-branch convolutional network used for a variery of computer vision tasks, including classification, recognition, or generation. The network consists of blocks made of multiple branches of concolutional and pooling operations. Within a block, the branches of ops can be executed in parallel. However, the model is mostly sequential as the outputs of each block are concatenated together to form the input to the next block. We use a batch size of 64. The Tensorflow graph of this model contains 24,713 operations.

heading: 6.3.2 AMOEBANET
text: AmoebaNet (Real et al., 2018) is an automatically designed neural network that yields SoTA performance on ImageNet. Similar to Inception-V3, it contains Inception-like blocks called cells, which receives a direct input from the previous cell and a skip input from the cell before it. The network is made of redundant cells stacked together, therefore is more modular than Inception-V3. We use a batch size of 64. The Tensorflow graphs contains 9,430 operations.

heading: 6.3.3 RNNLM
text: Recurrent Neural Network Language Model (Zaremba et al., 2014; Jozefowicz et al., 2016) is made of many LSTM cells organized in a grid structure. The processing of each LSTM cell only depends on the results of 2 other cells (from the previous layer, and from the previous time step), which make the concurrent execution of many LSTM cells possible given enough hardware resources. We use batch size 64 and a hidden size of 2048. The corresponding TensorFlow graph contains 9,021 operations for a 2-layer model. The number of ops grow roughly proportional with the number of layers.

heading: 6.3.4 GNMT
text: Neural Machine Translation with attention mechanism (Bahdanau et al., 2015; Wu et al., 2016) has an architecture similar to that of RNNLM, but its many hidden states make it far more computationally expensive than RNNLM. To reduce the training time, prior work (Wu et al., 2016) propose placing each LSTM layer, as well as the attention and the softmax layer, on a separate device. This strategy demonstrates early success in human placement, we show that GDP can find significantly better placements. We use batch size 64. The original 2-layer encoder-decoder consisting of 28,044 operations. An extended 4-layer version consisting of 46,600 operations, An even larger 8-layer version consisting of 83,712 operations.

heading: 6.3.5 TRANSFORMER-XL
text: Transformer-XL (Dai et al., 2019) is an modified version of Transformer (Vaswani et al., 2017) that supports segement-level recurrence and a novel positional encoding scheme. This innovation enables learning dependency that is 80% longer than RNNs, and 450% longer than vanilla Transformers. We use a transformer-XL with batch size of 64, sequence length of 256, segment length of 64, model hidden dimension of 500 and feed forward hidden dimension of 1000, 10 heads, and head dimension of 50. The 2-layer Transformer-XL contains 2,618 operations. The number of ops grow roughly proportional with the number of layers.

heading: 6.3.6 WAVENET
text: WaveNet (van den Oord et al., 2016) is a generative model for speech synthesis. The model is fully probabilistic and autoregressive, with the predictive ditribution for each audio sample conditioned on all previous ones. Architecturally, WaveNet uses causal convolutions with dilations, to obtain a large receptive field. We use a WaveNet model with batch size 64 and a receptive field size of 2048 (9-layers per stack). An 5-stack WaveNet contains 4,374 operations and a 10-stack WaveNet contains 8,516 operations.

Review summaries:
In this paper the authors propose an end-to-end policy for graph placement and partitioning of computational graphs produced "under-the-hood" by platforms like Tensorflow. As the sizes of the neural networks increase, using distributed deep learning is becoming more and more necessary. Primitives like the one suggested by the authors are very important in many ways, including improving the ability of the NN to process more data, reduce energy consumption etc. The authors compared to prior work propose a method that can take as input more than one data flow graphs, and learns a policy for graph partitioning/placement of the operations in a set of machines that minimizes the makespan. This problem in principle is NP-hard as it entails both graph partitioning and graph scheduling as its components. The authors propose a heuristic that composes of two existing methods: graph neural networks are used to produce an embedding of the computation/data flow graph, and then a seq-2-seq placement network. The method is able to generalize to unseen instances.

This work proposes to use a combination of graph neural networks (GNNs) and proximal policy optimization (PPO) to train policies for generalized device placement in dataflow graphs. Essentially, (1) a GNN is used to learn representations of a dataflow graph (in an inductive manner), (2) a transformer is used to output a device placement action for each node in the graph, and (3) the entire system is trained end-to-end via PPO. Extensive experimental results show very impressive results compared to strong baselines.