A Structure-Aware Framework for Learning Device Placements on Computation Graphs
Authors: Shukai Duan
Heng Ping
Nikos Kanakaris
Xiongye Xiao
Panagiotis Kyriakis
Nesreen K. Ahmed
Peiyu Zhang
Guixiang Ma
Mihai Capotă
Shahin Nazarian
Theodore L. Willke
Paul Bogdan
Venue: NeurIPS 2024 poster (2024)
Keywords: device placement
heterogeneous computing
computation graphs
graph pooling
Primary area: machine_learning_for_other_sciences_and_fields

Abstract: Computation graphs are Directed Acyclic Graphs (DAGs) where the nodes correspond to mathematical operations and are used widely as abstractions in optimizations of neural networks. The device placement problem aims to identify optimal allocations of those nodes to a set of (potentially heterogeneous) devices. Existing approaches rely on two types of architectures known as grouper-placer and encoder-placer, respectively. In this work, we bridge the gap between encoder-placer and grouper-placer techniques and propose a novel framework for the task of device placement, relying on smaller computation graphs extracted from the OpenVINO toolkit. The framework consists of five steps, including graph coarsening, node representation learning and policy optimization. It facilitates end-to-end training and takes into account the DAG nature of the computation graphs. We also propose a model variant, inspired by graph parsing networks and complex network analysis, enabling graph representation learning and jointed, personalized graph partitioning, using an unspecified number of groups. To train the entire framework, we use reinforcement learning using the execution time of the placement as a reward. We demonstrate the flexibility and effectiveness of our approach through multiple experiments with three benchmark models, namely Inception-V3, ResNet, and BERT. The robustness of the proposed framework is also highlighted through an ablation study. The suggested placements improve the inference speed for the benchmark models by up to $58.2\%$ over CPU execution and by up to $60.24\%$ compared to other commonly used baselines.

A Structure-Aware Framework for Learning Device Placements on Computation Graphs
Shukaí Duan"
Heng Ping" University of Southern California Los Angeles, USA hpingGusc.edi
Center for Complex Particle Systems University of Southern California Los Angeles, USA shukaidudusc.ed
Nikos Kanakaris*
Xiongye Xiao
University of Southern California Los Angeles, USA kanakari@usc.cm edu
Center for Complex Particle Systems University of Southern Californi Los Angeles, USA xiongyex@usc.edd
Panagiotis Kyriakis*
Nesreen K. Ahmed Cisco Outshift
Peiyu Zhang University of Southern California Los Angeles, USA pzhang65dusc. edu
Meta
pkyriakis@meta..cm
nesahmed@cisco.com com
Guixiang Ma
Mihai Capotă Intel Labs
Shahin Nazarian
Intel Labs guixiang- ma@intel.com com
University of Southern California
mihai.capota@ wawpalaccp@@@@ine.ccmom com
Los Angeles, USA
Theodore L. Willke
Paul Bogdan
Intel Labs
Center for Complex Particle Systems
ted. wed.vvillk@@ineel.coom
University of Southern California
Los Angeles, USA pbogdandusc.edu
Abstract
Computation graphs are Directed Acyelic Graphs (DAGs) where the nodes spond to mathematical operations and are used widely as abstractions in optimiza- tions of neural networks. The device placement problem aims to identify optimal allocations of those nodes to a set of (potentially heterogeneous) devices. Existing approaches rely
types of architectures known as grouper-placer and encoder- placer, respectively. In this work, we bridge the gap between encoder-placer and grouper-placer techniques and propose novel framework for the task of device placement, relying on smaller computation graphs extracted from the Open VINO toolkit. The framework consists of five steps, including graph coarsening, node representation learning and policy optimization. It facilitates end-to-end training and takes into account the DAG nature of the computation graphs. We also propose model variant, inspired by graph parsing networks and complex network analysis, enabling graph representation learning and jointed, personalized graph partitioning.
'Equal contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

using an unspecified number of groups. To train the entire framework, we use reinforcement learning using the execution time of the placement as reward. We demonstrate the flexibility and effectiveness of our approach through multiple ex- periments with three benchmark models, namely Inception- V3, ResNet, and BERT. The robustness of the proposed framework is also highlighted through an ablation study. The suggested placements improve the inference speed for the benchmark models by up to 58. 2% over CPU execution and by up to 60.24% compared to other commonly used baselines.
Introduction
The ability of intelligent agent systems (IASs) and syber-physical systems (CPSs) to perceive and accurately interpret complex environments is erucial for artificial intelligence (AI). Recently, there has been a remarkable progress in machine learning and AI, due to the wide adoption of the transformer architecture and foundation models (FMs) [26, 30J. FMs have allowed both academia and industry to perform several data data-demanding tasks, ranging from image and text analysis to multi-modal content generation and human-like visual perception [18, 20, 11, 4]. This is achievable due to the self- supervised nature of the FMs, their ability to easily generalize and the large amounts of data available online [29]. The aforementioned properties make FMs distinguishable in specific general pre-training tasks such next-word prediction, compared to traditional ML architectures that use supervised learning [2]. This recent surge in using large FMs has led to increased demand for computing power, which is projected to grow
more in the next few years [16]. This is due to the need for more advanced model training processes and the continuous expansion of model parameters [26, 6]. is clear that as FMs become increasingly complex, they demand vast computational resources not only for training but also for fine-tuning and inference tasks. This surge in computational demand underscores the necessity for managing the available hardware more effectively.
In light of this, the concept of device placement has gained popularity lately as a manner to speed up and improve the inference time of deep learning models, including FMs, in systems with mixture of heterogencous devices, such as CPUs, GPUs and NPUs [31, 1, 33, 15, 21]. With neural networks evolving towards larger models, heterogeneous and multi-device computing has played critical role in their implementation. Device placement emerges as a pivotal factor determining the performance of implementation of model. Strategically allocating neural networks across multiple devices can significantly reduce the runtime of a model and the overall energy consumption [9]. The current process of device placement typically involves converting a neural network into computation graph, where each node corresponds to an operation within the neural network. The computation graph is then partitioned and its nodes are allocated to the appropriate devices for processing. The effectiveness of device placement directly impacts the deployment performance of neural networks.
Early device placement has been the main responsibility of human experts [21]. Engineers with a substantial level of expertise and diligence were responsible for allocating each part of a model to the best-suited device. However, this rigorous task can be daunting, considering the rapid advancement in hardware, which leads to a serious increase in development time, bug fixing, and code optimization [3, 19, 23]. Deep reinforcement learning (DRL) has recently been proposed to provide effective device placements with full automation [31, 1, 21]. Two different DRL architectures for device placement currently exist in the literature: the prouper-placerr model that reduces the action space by merging operations into groups; and the 'encoder-placer" that encodes the features of the operations to capture the topological properties of the computational graph [15, 31].
Although existing approaches have been successful, there is still space for improvement. In particular, they demonstrate several shortcomings. To begin with, they disregard the directed and acyclic nature of computation graphs [22]. Furthermore, they either follow a grouper- placer or an encoder- placer architecture [22, 21J. In addition, most of them are not designed to train all of their components simultaneously in an end-to-end fashion and they fail to capture higher-order interactions among the operations of computation graph. Finally, they make use of large, fine- fine-nrained computation graphs, thereby exhibiting slow convergence and demanding a higher number of iterations during the learning process [15].
Considering the limitations mentioned above, this paper proposes a framework to optimize for device placement based on smaller, coarsened computation graphs produced by the VINO

---

toolkit. Our framework consists of five steps: First, the neural network model is converted into computation graph. Then, local and global structural features as well as positional, node-specific and fractal features are extracted to compose the initial node feature vectors. Following that, graph representation learning, graph partitioning and pooling are learned jointly, facilitating the fusion of the prouper-placer and encoder-placer models. Finally, we use the execution time of the suggested device placements as a reward to train the entire framework. In contrast with existing approaches, our framework allows for encoding and grouping operations of computation graph jointly in an end-to-end fashion. Along with the proposed framework, through one of the variant models, we introduce novel method tailored to computation graphs, for jointly learning node embeddings and performing personalized graph partitioning with an unspecified number of groups for further coarsening. The effectiveness and robustness of the proposed approach are demonstrated through multiple experiments with different benchmark models and a detailed ablation study.
Contributions. The main contributions of this paper are the following:
To the best of our knowledge, this is the first flexible framework for the task of device placement capable of learning graph and node representations as well as graph partitions and pooling jointly in an end-to-end fashion. Even more, we introduce the concept of learning personalized graph partitions using an unspecified number of groups
We propose structure-awer device placement framework that integrates graph coarsening. node representation learning, policy optimization and effectively combines the strengths of grouper-places and encoder-placer models.
Our framework is the first of its kind that encodes features from multifractal analysis, positional encodings, and node-specific features for the task of device placement through model variant, and discusses the impact of incorporating different properties on the model.
The proposed variant of the framework achieves a state-of-ther -otte-- performance improvement of up to 58.2% over CPU execution and 60.24% in comparison with other baseline models.
2 Proposed framework
In this section we introduce our framework titled Hierarchical Structure-Aware Device Assignment Graph (HSDAG). consists of five steps as shown in Figure 1. Briefly, we first convert neural network model into a computation graph. Then, we extract features for each node and edge of the computation graph. The next step enriches these features via graph representation learning techniques and simultaneously learns how to partition and pool the graphs. The learned features and groups of nodes are utilized to train a stochastic policy, which we use for assigning each node of graph to the most appropriate device. We train the entire pipeline end-to-end with the objective of minimizing the inference time of the proposed device placement.
2.1 Problem Formulation
Definition 2.1. (Computation graph). We denote a computation graph as G = (V, E). G labeled, unweighted, directed and acyelic with a of nodes V = {v1, u2..... ] representing operations and a set of edges E C V x V representing their connections. Each graph G is associated with a binary asymmetric adjacency matrix as A E {0, 1||V V1, Each node v of G represents an operation applied to the input data and is associated with an operation type to E T. In the context of this paper, the terms node and operation are used interchangeably. An edge = (v, u) E E represents the flow of data dependency among node and node u.
Definition 2.2. (Device placement). Given a list D of the available devices, a placement (PI.P2, .2, ................................ }n assigns each operation v of computation graph G to a device E D, where PE E (1,2.... DI).
Problem setup. We focus on the problem of device placement in heterogeneous computing system. Our goal is to assign each part of computation graph to the most suitable device, such that the overall execution time during the inference of the model is minimized. Formally, given a computation graph G, we learn policy G -> P that assigns placement p for all u E G such that
r T.P = maxr(G; P)
(I)
T.P
3

---

Neural network model
Graph construction
Feature extraction
O
Heteroganeous execution
Device placement
Learning embeddings and Jointly
graph
Original groph
Reward
aitulatioo
GNM(XA
Execution
MIP
B
CPU
Esecution
unvironment
CPU
end-to-end parameter update
Figure 1: Overview of the proposed framework, HSDAG. Graph construction. We first convert neural network model e into a computation graph G. repr: - G. Feature extraction. Then, we calculate the initial feature matrix (0) capturing local and global connectivity information, node-aware features, information about the order of the nodes as well as features from fractal analysis. Learning embeddings and groups jointly. We further enrich node features X (0) using GNN G Z model and learn how to pool a graph G jointly using a graph parsing network. In that way. we bridge the gap between coouper-places and encoder-plase paacerr methods for device assignment. Device placement. A learnable MI.P model classifies the nodes V' of the coarsened graph G' = (V", E') to the available devices D. Heterogencous execution. We map the device placement of V' based on the node assignment matrix X' and apply the placement of all the operations into the execution environment measure the execution time with the corresponding reward. End-to-end parameter update. update our policy и parameters 0, iee, the combination GNN and MLP, based on the reward and renew the node feature matrix Z with the current cluster information. The entire framework supports end-to-end parameter updates and training.
where "r E IR is the reward by following policy æ and placement We use a GNN (although any model can be employed) to learn the optimal policy denoted by œž and its set of parameters Let (p()) E R++ denote the execution time of the computation graph G' by following the placement P. Our goal to minimize execution time by learning the parameters
0" arg min (G; 0),
(2)
for the policy æ that yields the best results.
2.2 Graph construction
Given set of neural network models C' {Ca, .c.....)). the first step is to decide graph- based code representation repr that converts a structure neural network model c, into a graph GG repr C; G There is list of different graph-based representations of neural network models including abstract syntax trees, contextual flow, control, data flow and LLVM IR graphs [17]. Although such graphs may contain valuable information and capture the latent information flow of program, they tend to add unnecessary complexity to the overall process. Instead, for the experiments of this paper, we opt for representing the code of neural network model e; computation graph, due to its expressiveness, simplicity, and practicality. A computation graph is generally smaller than its counterparts and could be casily allocated to specific devices. For instance, one can use several popular libraries to produce the computation graph G; of a given neural network model c, In this paper, use the VINO toolkit to generate the computation graphs as it generates smaller, already coarsened graphs compared to those of TensorFlow or PyTorch. Further information about the Open VINO toolkit and examples of computation graphs are available in Appendix F. Even though it is optional, further coarsening can be performed using common co-locating operations or heuristics [22]. Such co-locating heuristics eliminate certain execution failures due to placement rule violations. In our experiments, we apply simple algorithm for co-location to further condense the model into smaller computation graph [22]. The graph construction step enables our approach to utilize graph representation learning techniques. Note that framework is flexible and can

---

be coupled with any type of graph code representation for neural networks capable of producing directed and acyclic graph G, similar to those of the computation graph representation.
2.3 Feature extraction
The proposed framework is also versatile as far as the initial node features are concerned. During our experimentation with various feature combinations (see Ablation studies in Section 3), we found that a mixture of features capturing local and global connectivity information, features from fractal analysis as well as node-specific features (e.g. topology, the order of a node and node type) leads to better results.
Local structural features. Specifically; the initial feature vector x of node incorporates information about the node (operation) type tv, in-degree 6 = [N | Ewey A(u, v) E N and out-degree 6out = (Woee()) (v)] Euev A(v, u) E N of u; here, Wi (v) and Noun represent the sets of -n-neighbors and out-neighbors of node u, respectively. Initially, we use one-hot encoding embed each unique operation type into tensor T; {0, 1) where [7] N+ is the number of unique operation types among all the input models C. Formally, for each operation type e (1...., [T]), the one-hot encoding is defined
if E (1....,,77) otherwise {
T =
(3)
Similarly, we one-hot encode each unique in-degree 6.nh and out-degree 65 values into the A {0, 1314"" and Aqu {0, 13 13
tensors, where |A 6n N+ and A out N+ is the number of
unique in-degree and out-degree values, respectively.
Global structural features. Relying solely on local features might miss capturing important global properties of the network. To capture the multi-scale structural properties of the network, we calculate the fractal dimension for each node E V. The fractal dimension D(v) [28, 30] of node is computed based on the mass distribution. Given the set of distances {r1, r2...., rm from node v to other nodes in the network, the fractal dimension D(v) is caleulated as follows:
(log(rx) log(r)) log(N((v,)))
D(v)=
m Σ (log(rx) log(r)))
where тs represents each distance in the set, (N, rk) is the number of nodes within the distance rk- and log(r), (oggN((,1)) r)) are the mean values of log(rk) and log(N(u, rx)), respectively.
Positional features. In an attempt to inject information about the order of the nodes, we associate each node v with an integer pos that encodes the topological order the graph. To do so, we use a bijective mapping function id V + {1, .l..... [V]]. Formally, if v; is the i-th node in the topological order, then id Us) This kind of feature can be further enhanced using a function for positional encoding PE=
R
x R
R:
sin
pos
if 2i
at 10000 dpax
d Aos
PE(pos, k)
i E [0,
(5)
2
COS
pos
if
dpoz
where dRos is the size of the embedding of feature pos.
Node-specific features. For each node v. we define the padded, fixed-size output shape tensor S, E Ri which is also provided as a piece of information in the original computation graph. Each digit of the output shape of node v is represented as a new dimension in the tensor S,.. We traverse the entire graph G and obtain the maximum data output shape |S| max,ev output_shape(t).
Finally, we concatenate all the information for each individual node e and form a node feature vector x Rdd, where d = T||SSA out D Building on top of the initial feature matrix x R Vlxd in the next steps, we extend the representation learning capabilities of our framework
5

---

with recent techniques from the field of GNNs. While GNNs offer powerful feature extraction methods, this step is crucial as it provides a model with information about the nodes and structure of the graph, thereby accelerating the convergence of the process.
2.4 Learning embedding and groups jointly
We further enrich node features X and learn how to partition given graph G into unspecified varying number of groups by employing the Graph Parsing Network (GPN) [24]. Existing grouper- placer methods typically operate with a predefined number of clusters during device placement exploration. They also employ non-trainable al algorithms for graph partitioning or pooling relying mostly on human intuition and heuristics to group the nodes of graph. This ad-hoc presetting of the group number leads to suboptimal solutions, which in turn inhibit the exploration and learning process of the overall framework. Instead, our framework treats both the number of node groups and the pooling algorithm as learnable parameters, which are trained in an end-to-end fashion. This step consists of three components: (1) graph and node encoding, (2) edge score matrix calculation and (3) graph partitioning and pooling.
Graph and node encoding. The graph and node encoding component is compatible with any neural network model and generates a node embedding Z TRdd for each node v, where d' is the dimension of the node feature vector. In practice, we use an embedding function GNN G + our main graph encoder; self-superviser techniques may also be employed to pre-train the embedding function GNN, which aids in the downstream task of device placement [32]. As a result of using a GNN as an encoder, the learnable feature matrix Z E TR. VIxd' captures both node- and structure- aware information about the graph G. As we mentioned before, our framework is model-agnostic and allows for utilizing different GNN functions. In the interest of clarity, we formulate the representation learning step using GCN [14] model with single graph convolutional layer:
| |xd'' as
Z = GNN(G, A) = (111 1/2 AD 1/2 x/2x (0) ()) E RR [V|''
(6)
where À A+IE E {0, 1)IVIKIV denotes the adjacency matrix with self-loops and D - Ej= A
is the corresponding diagonal degree matrix, W igxxd' is matrix of learnable parameters, (() E RlV is matrix with the input features of each node and ar-) denotes an activation function such as ReLU(.) = max(0, ))
Edge score matrix calculation. This component accepts any differentiable neural network model to calculate an edge score matrix S E [o. 1 Given an edge connecting two nodes v, u and their embeddings Zy Zu then the score S.,u S. is calculated as follows:
Su,u = ( @ z.)) E [0.1] s.t. S=S A
where (ar) sigmoid(a) Itel oj and & can be any differentiable neural network. During our experimentation, we found that setting é MLP yields good performance w.r.t. the task of device placement. The magnitude of an edge score Se quantifies the strength of the relationship between the connected nodes and u. A higher edge score S. implies a stronger relationship, increasing the probability for the nodes e and u to be grouped into the same partition P; E P. Formally, this can be expressed as:
P(e E PEAA x S., e= u)
(8)
As result, the higher the edge score Se, the higher the probability that nodes v and u will be grouped into the same partition, reflecting their relational affinity.
Graph partitioning and pooling. The graph partitioning and pooling component uses the computed edge scores S to partition the entire graph G. Specifically, it iterates through each node e in the graph G and identifies the edge with the highest score among all edges connected that node, In graph with V nodes, this process may identify up to |&| < [V] such edges. Only these |&] edges are retained and the remaining edges are discarded, automatically dividing the graph into multiple groups. The set of the remaining edges is then defined as:
È = [(v, w)lu E V, arg max S W'NN(.
This grouping method ensures that nodes within each group have stronger local connectivity and tighter relationships, making them more suitable for being assigned to the same device for execution.

---

The final step is to create node assignment matrix X' E R VIx|V" that maps each node v in the original graph G to a node o' in the coarsened graph G' = (V', .E). To construct the node assignment matrix X' we use the graph parsing algorithm A, as proposed in [24]:
X = A(E)
(10)
The adjacency matrix A' E (0. VIxVV of the pooled graph G' is then defined as:
A'= x A.X
(11)
2.5 Reinforcenment learning for node-based device assignment
In this step, we combine the GPN from the previous component and an MLP to learn policy G' G'->P' Aftter we obtain the device placement P', we use the node assignment matrix X' to map each node e' of the coarsened graph G' to a node e of the original graph G. that way, we manage to assign a device Pv, for each node v of the graph G. At each RL episode, we infer the machine learning model with the updated operation device placement P' and get the inference latency Ip (G"). Our ultimate goal is to choose reward function that maximizes the reward when the latency is low. Thus, we use the reward function r'p (G') [P.. To find the proper stochastic group detection and placement policy parameters 0, we maximize the objective function
((] Ep (r(P G')]
(12)
For each time step, we update the node embedding Zu of a node u by summing up the embedding Ze of its corresponding coarsened node v': Z. = Z, + Zu.. We then form new graph G' which can also be considered as the new state. We then run a new round of representation and group learning (Section 2.4) and device placement for the new graph G'. We update our policy parameter gradient by REINFORCE (27] using the Adam [13] optimizer producing:
[ = E Ep-a(Pl(r
G) Vo log G';
(13)
We record x steps in the buffer and compute the reward of each device placement. After x steps, we update the policy parameter with the cumulative reward and loss
V VoJ(O)
Ve P(P G): of G)P..G)
(14)
where y is the discount rate for the reward at the current time step to the previous time steps.
3 Experiments
3.1 Benchmarks
To evaluate our approach we use the computation graphs created from three popular benchmarks: (1) Inception-V3: The Inception-Ve V architecture [25] is extensively employed for image recognition and visual feature extraction [12]. This neural network consists of multiple blocks, each comprising various branches of convolutional and pooling layers. These branches are capable of parallel execution and are concatenated to form inputs for the subsequent block. However, the depth of the network limits this parallelism since later blocks must wait for the completion of carlier ones; (2) ResNet: ResNet [10] is a widely-used model for image classification. It consists of multiple convolutional layers and uses residual connections to reduce the effects of the vanishing gradient problem. We use the ResNet-50, which is a 50-layer convolutional neural network; (3) BERT: BERT [6] is language model relying the transformer architecture. It pre-trains deep bidirectional representations unlabeled data jointly. It can be used as the base to fine-tune models for list of tasks, including question answering and language inference. Several versions of the BERT model exist. In this paper, we use the base uncased version. Important statistics and a more detailed description of the benchmark models are available in Table and Appendix D.
3.2 Setup
We implement the variant of HSDAG and baseline models with the PyTorch Geometric framework [7]. The Adam [13] optimization algorithm is used for the optimization of the parameters of the models. We run our experiments on real hardware using the Open VINO toolkit version 2023.3.0 ?
7

---

Table 1: Statistics of computation graphs of the benchmarks used in our experiments, [V] the number of nodes, [E| the number of edges, d: the average degree.
BENCHMARK
[V]
E
d
INCEPTION-VS V3
728
764
1.05
RESNET
396
1.04
BERT
1009
1071
1.06
Devices. The available devices for our experiments are the following: (1) CPU: 12th Gen Intel(R) Core(TM) 19-12900K, (2) GPU.O: Intel(R) UHD Graphics 770 (iGPU) and (3) GPU.1: Intel(R) Data Center GPU Flex 170 (dGPU). Our server has 64GB of memory.
3.3 Baseline comparison
Aiming to test the performance of the proposed framework, evaluate the proposed variant against a list of sfatc-of-the-ar baseline methods. The selected baseline models may differ from the variant of our framework in many ways, in terms of their architecture and the algorithms they employ to implement their components. Furthermore, they may ignore parts of the proposed framework or implement them differently (e.g., learn node embeddings and clusters separately). The main purpose of the baselines is the evaluation our framework w.r.t. the task of device placement.
1. CPU-only. It assigns the entire computation graph to CPU. It does not include any part of the proposed approach, except for the device assignment component.
2. GPU-only. It assigns the entire computation graph GPU. Similar CPU-only, the device assignment part of our framework is the only one that is implemented.
3. OPeNVINO-CPU This baseline method lets the VINO optimization toolkit decide whether the entire computation graph should be assigned to CPU GPU, with CPU set as the first preference.
4. OpenVINO-GPU A baseline similar to Open VINO-CPU with GPU set as the first prefer- ence.
5. Placeto [1]. uses GNNs learn features for any computation graph as proposed in [1]. Therefore it enables the transfer of learned device placement policy to new computation graphs without further re-training.
6. RNN-based approach [22]. An RL framework trained to optimize device placement by utilizing sequence-fo-sequuenc LSTM model and content-based attention mechanism.
Table 2 shows the performance of the compared models as far the task of device placement and the reduction in execution (inference) time are concerned. On Inception- V3, our framework achieves 17.9% speedup over the CPU-only bascline, reducing the inference time from 0.0128 seconds to 0.0105 seconds. This performance surpasses other baselines, such as GPU-only (6.25% speedup) and Placeto (9.38% speedup). Similarly, ResNet, our framework delivers 52.1% speedup, reducing the inference time to 0.00766 seconds, which is significantly better than the GPU-only (51.2% speedup) and Open VINO--NOGPP (45.3% speedup) baselines. The most substantial improvement observed on the BERT benchmark, where our framework achieves a 58.2% speedup, reducing the inference time 0.00267 seconds, outperforming the GPU-only baseline sp6.5%)p.)d)))) These results highlight the efficiency and effectiveness of the proposed device placement approach, leveraging graph coarsening, node representation learning, and reinforcement learning to optimize computation graph execution on heterogeneous hardware environments.
3.4 Ablation studies
To understand the impact of the components, steps and configurations HSDAG, we conduct an ablation study. Various modifications to the framework were tested, such as removing graph structural features, output shape features, and node IDs. Overall, the results are shown Table indicate that each of these components plays significant role in achieving optimal performance.

---

Table 2: Evaluation results of different models on the device placement task. The best results for each baseline model across benchmarks are highlighted in bold. (G) denotes the execution time (in seconds) for each model. Speedup % denotes the speedup with respect to the CPU-only baseline. On the execution time (G) column, lower (4) scores are better. On the Speedup % column, higher (1) scores are better. To get accurate results, we measure the inference time with the same device displacement 10 times and take the average the last measurements. OOM: out of memory.
Inception-V2 V3
ResNet
BERT
[r(G)
Speedup %
[r(G)
Speedup %
[r(G]
Speedup %
CPU-only
0.0128
0
0.0160
0
0,00638
0
GPU-only
0.0120
6.25
0,00781
51.2
0.00277
56.5
OpenVINO-CEE CPU
0.0128
0
0.0234
-46.3
0.00657
-2.98
OpeNVINO-GPU
0.0138
-7.81
0.00876
45.3
0.00284
55.5
Placeto
0.0116
9.38
0.00932
41.8
0.00651
-2.04
RNN-based
0.0128
0
0.00875
45.3
OOM
OOM
HISDAG 0.0105
17.9
0.00766
52.1
0.00267
58.2
Table 3: Results of the framework variants of the ablation study on the device placement task. (G) denotes the execution time (in seconds) for each model. Speedup % denotes the speedup with respect to the CPU-only baseline. On the execution time (p())) column, lower (4) scores are better. On the Speedup % column, higher (t) scores are better. To get accurate results, we measure the inference time with the same device displacement 10 times and take the average of the last 5 measurements.
Inception-V3 V3
ResNet
BERT Speedup %
(p(G)
Speedup %
Ip(G)
Speedup %
[p(G)
CPU-only
0.0128
0.0160
0
0.00638
Original
0.0105
17.9
0.00766
52.1
0.00267
58,2
w/o output shape
0.0117
8.59
0.00768
52.0
0.00278
56.4
w/o node ID
0.0117
8.59
0.00768
52.0
0.00279
56.4
w/o graph structural features
0.0109
14.8
0.00766
52.1
0.00268
58.2
No graph structural features. For each node of in the computation graph G, we ignore features from fractal analysis, in-degree, and out-degree. Removing graph structural features clearly impacts the framework's 's ability capture the global and local structural information of the computation graph. The results from this ablation show a decrease in performance, although not as important as other feature removals. For example, the inference time speedup on Inception-Vas VV3 drops to 14.8% from 17.9% when these features are excluded. This indicates the importance of these features in capturing the hierarchical and interconnected nature of computation graphs.
No output shape features. We assume that the output data shape of each operation reflects the computation requirement for the corresponding operation. We do not include the output data shape in the node feature vector to test its effectiveness. We observe a significant decrease in performance. The speedup for Inception- V3 drops from 17.9% 8.59%. This suggests that the features related to the output shape are crucial for understanding the computational load associated with each node in the graph. Without this information, the framework's 's ability optimize device placement is compromised, leading to less efficient computation graph execution.
No node ID. In this case, we do not use the node ID to encode the topological sequence of the node v in a given computation graph G. Omitting information about the node ID results in a significant performance drop. The speedup for Inception- V 3 is reduced to 8.59%. This highlights the critical role of node IDs in preserving the order and dependencies within the computation graph. The framework lacks essential information about the execution order of operations, leading to sub-optimal device placement and reduced overall efficiency.
3.5 Downstream Model Performance and Runtime Complexity
As a sanity check for our method, we show the performance on downstream tasks not affected. Theoretically, since the end-to-end training pipeline itself does not change, we do not expect any

---

impact on the performance. Nonetheless, we show experimental results on 3 exemplar cases to empirically verify statement.
inception-V3. We performed image classification inference on images depicting Samoyed dogs. All the parameters directly derived from the torchvision pre-trained model. We did not change any configuration on the data type of the model. The classification accuracy of Inception-V3 using the best device placement is 82.77%. For the GPU-only experiments the classification accuracy 82.72%. For the CPU-only experiments the classification accuracy is 82.33%.
ResNet: Similarly, we performed image classification inference using the ResNet model on the same dataset. The classification accuracy with the best device placement is 45.37%. For the GPU-only experiments the classification accuracy is 45.37%. For the CPU-only experiments the classification accuracy is 45.44%
BERT: We evaluated the performance of the BERT model using the output embeddings from the different device placements. We calculated their mean squared error, cosine similarity and Euclidean distance (MSE: the lower the better, Cosine Similarity: the higher the better, euclidean distance: the lower the better). The results are shown on Table 4.
Table 4: BERT performance downstream tasks.
Table 5: Empirical runtime complexity comparison.
Comparison
MSE
CS
L2 norm
Model
Inception-V. V3
ResNet
BERT
CPU vs GPU
3.049c-05
0.999
0.432
Placeto
2808s
1162s
4512s
CPU vs HSDAG
6.819c-07
0.999
0.064
RNN-based
3706s
1212s
OOM
GPU HSDAG
3.174e-05
0.999
0.441
HSDAG
2454s
1047s
2765s
These experiments empirically demonstrate that HSDAG does not affect the performance of the model in the downstream tasks. All models have similar performance regardless of the running device (e.g. CPU, GPU or heterogencous device). Finally, we also conducted an empirical runtime complexity estimation in order to show HSDAG's superiority in terms of execution time. We compare against the Placeto and the RNN- device placement methods for the same 3 models. The results are shown Table 5.
4 Conclusion
We introduce flexible framework for the task of device placement. Our framework relies smaller computation graphs and is divided into five steps such as graph coarsening. node representation learning and policy optimization using reinforcement learning. It supports end-to-end model train- ing and is aware of the directed and acyclic nature of the computation graphs under consideration. Additionally, we propose model variant that facilitates graph representation learning and person- alized graph partitioning jointly with an unspecified number of node clusters. The experimental results highlighted that our framework is flexible, and robust and mitigates the shortcomings of the coouper-place, and encoder- placer models by capitalizing on the best aspects of the two worlds. The suggested placements improve the inference speed for the benchmark models compared widely used baselines. One interesting future work direction is to explore different RL problem formulations well different reward structures, such as the incremental rewards used in [1]. Another direction is to study the interplay of the reward and generalizability as well as potentially using reward models rather than measuring reward. This could unlock more efficient algorithm the current setup relies on measuring the inference latency, which has practical limitations.
Linitations. The latency measurements did not consider the temperature change of the environment of the system and surroundings. During our experiments, we allocate the CPU for both experiment and policy due to the limitation of the setup. At the same time, iGPU is not considered throughout the experiment because we consider it to be always slower than both CPU and GPU. We attempted to obtain the source code for the baseline methods, but they were not made available from the corresponding authors. As such, we implemented and reproduced the baseline methods with our best effort from their published papers.
10

---

Acknowledgements
The University of Southern California acknowledges the support by the U.S. Army Research Office (ARO) under Grant No. W911NF-23-1-0111, the National Science Foundation (NSF) under the Career Award CPS- 14538600 CCF-1837131, MCB-1936775, CNS-1932620 and the NSF award No. 2243 104 under the Center for Complex Particle Systems (COMPASS), the Defense Advanced Research Projects Agency (DARPA) Young Faculty Award and DARPA Director Award under Grant Number N66001-17-1-4044 National Institutes of Health (NIH) under grant R01 AG 079957, an Intel faculty award and a Northrop Grumman grant. The views, opinions, and/or findings this article are those of the authors and should not be interpreted as official views or policies of the Department of Defense, the National Institutes of Health, or the National Science Foundation.
References
[1] R. Addanki, S. Bojja Venkatakrishnan, S. Gupta, H. Mao, and M. Alizadeh. Learning generalizable device placement algorithms for distributed machine learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Gareett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[2] T. Brown, B. Mann. N. Ryder, M. Subbiah, D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert- Voss, G. Krueger. Henighan, R. Child, A. Ramesh, D. Ziegler. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler. M. Litwin, S. Gray. B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei. Language models are few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing
Systems, volume 33, pages 1877 1901. Curran Associates, Inc., 2020.
[3] L. Chen, A. Bhattacharjee, N. Ahmed, N. Hasabnis, G. Oren, V. Vo, and A. Jannesari. Ompgpt: A generative pre-trained transformer model for openmp. In Carretero, Shende, J. Garcia-Blas Brandic. K. Olcoz, and M. Schreiber, editors, Euro-Par 2024: Parallel Processing, pages 121-134, Cham, 2024. Springer Nature Switzerland.
[4] K. Cheng, N. K. Ahmed, T. Willke, and Y. Sun. Structure guided prompt: Instructing large language model in multi-step reasoning by exploring graph structure of the text, 2024.
[5] Z. Dai, Z. Yang, Y. Yang, J. G. Carbonell, Q. V. Le, and R. Salakhutdinov. Transformer-xl: Attentive language models beyond fixed-length context. In Annual Meeting of the Association for Computational Linguistics, 2019.
[6] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In North American Chapter of the Association for Computational Linguistics. 2019.
[7] M. Fey and J. E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR 2019 Workshop on Representation Learning on Graphs and Manifolds, 2019.
[8] W. Hamilton, Z. Ying, and J. Leskovee. Inductive representation learning on large graphs. I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[9] He, Y. Xiao, C. Bogdan, S. Nazarian, and P. Bogdan, A design methodology for energy-aware processing in unmanned acrial vehicles. ACM Trans. Des. Autom. Electron. Syst., 27(1), sep 2021.
[10] K. Hc, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770-778, 2016.
[11] U. Israel, M. Marks, R. Dilip, Q. Li, M. Schwartz, E. Pradhan, E. Pao, S. Li, A. Pearson-Goulart, P. Perona, et al. A foundation model for cell segmentation. bioRxiv. 2023.
[12] A. Khetan and S. Oh. Reliable crowdsourcing under the generalized dawid-skene model. CoRR, abs/1602.03481, 2016.
[13] D. Kingma and J. Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), San Diega, CA, USA, 2015.
[14] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
11

---

[15] H. Lan, L. Chen, and B. Li. Accelerated device placement optimization with contrastive learning. In Proceedings of the 50th International Conference on Parallel Processing, ICPP 221, New York, NY, USA, 2021. Association for Computing Machinery.
[16] J. Lee. M. Kim, S. Back, S. J. Hwang. W. Sung, and J. Choi. Enhancing computation efficiency in large language models through weight and activation quantization. The 2023 Conference on Empirical Methods in Natural Language Processing, 2023.
[17] H. Lin, M. Yan, X. Ye, D. Fan, Pan, W. Chen, and Y. Xie. A comprehensive survey on distributed training of graph neural networks. Proceedings of the IEEE, 111:1572 110117666666, 2022.
[18] L. Luceri, E. Boniardi, and Ferrara. Leveraging large language models to detect influence campaigns on social media. Companion Proceedings of the ACM on Web Conference 2024, 2023.
[19] G. Ma. Xiao, M. Capotà, L. Willke, S. Nazarian, Bogdan, and N. K. Ahmed. Learning code representations using multifractal- based graph networks. In 2021 IEEE International Conference on Big Data (Big Data), pages 1558-1866,12 2021.
[20] H. Mao, Z. Chen, W. Tang. J. Zhao, Y. Ma. T. Zhao, N. Shah, M. Galkin, and J. Tang. Position: Graph foundation models are already here. In International Conference on Machine Learning, 2024.
[21] A. Mirhoseini, A. Goldie, H. Pham, B. Steiner, Q. V. Le, and J. Dean. A hierarchical model for device placement. In International Conference on Learning Representations, 2018
[22] A. Mirhoseini, H. Pham, Q. V. Le, B. Steiner, R. Larsen, Y. Zhou, N. Kumar, M. Norouzi, S. Bengio, and J. Dean. Device placement optimization with reinforcement learning. In Proceedings of the 34th International Conference Machine Learning- Volume 70, ICML' 17, page 2430 2039.2239..2 Jogg.org, 2017.
[23] N. Schneider, N. Hasabnis. V. A. Vo. T. Kadosh, N. Krien, M. Capota, G. Tamir, T. L. Willke, N. Ahmed, Y. Pinter, T. Mattson, and G. Oren. Mpirigen: Mpi code generation through domain-speeific language models. In Proceedings of the 2024 Workshop on For Systems, A14Sys '24, page 6,, New York, NY, USA, 2024. Association for Computing Machinery.
[24] Y. Song, Huang, X. Wang. C. Zhou, and Z. Lin. Graph parsing networks. In The Twelfth International Conference on Learning Representations, 2024,
[25] C. Szegedy, V. Vanhoucke, S. loffe, J. Shlens, and Wojna. Rethinking the inception architecture for computer vision. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2818-2826, 2016.
[26] A. Vaswani, N. Shazcer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. u. Kaiser, and I. Polosukhin. At- tention is all you need, In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[27] R. J. Williams. Simple statistical gradient algorithms for connectionist reinforeement learning. Machine Learning, 8:229-25 2004.
[28] X. Xiao, H. Chen, and Bogdan. Deciphering the generating rules and functionalities of complex networks Scientific reports, 11(1):22964 2021.
[29] X. Xiao, G. Liu, G. Gupta, D. Cao, S. Li, Y. Li, T. Fang, M. Cheng, and P. Bogdan. Neuro-inspire information eroomation-thhoretiic hicrarchical perception for multimodal learning. The Twelfth International Conference on Learning Representations, 2024.
[30] X. Xiao, C. Zhou, H. Ping, D. Cao, Li, Y. Zhou, S. Li, and Bogdan. Exploring neuron interactions and emergence in 1mms: From the multifractal analysis perspective, 2024.
[31] Y. Xiao, Ma. N. Ahmed, M. Capotä, L. Willke, Nazarian, and P. Bogdan. End-to-end programmahle computing systems. Communications Engineering, 2(1):84, 2023.
[32] R. Ying, You, C. Morris, Ren, W. Hamilton, and Leskovee. Hicrarchical graph representation learning with differentiable pooling. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS 18, page 1805-4815 Red Hook, NY, USA, 2018, Curran Asso- ciates Inc.
[33] Y. Zhou, S. Roy, A. Ahdolrashidi, D. I. Wong, P. C. Ma, Q Xu, M. Zhong, H. Liu, A. Goldie, A. Mirhoseini, and J. Laudon. GDP: generalized device placement for dataflow graphs. CoRR, 1bs/1910.01578, 2019.
12

---

A Code availability
The source code is available at
B Related work
A plethora of methods have been developed to optimize device placement [21, 33, 1]. These methods can be categorized as (1) heuristic methods or (2) methods relying on RL techniques and deep learning. Heuristic methods are able to identify relatively optimal device placement solutions in short time, but they require ad-hoc adjustments on different devices. Furthermore, they often fail to achieve the best outcomes [21]. In contrast, using RL for device placement generates better placement schemes for various devices.
The work in [22] first proposed RL framework trained with the REINFORCE algorithm to optimize device placement, utilizing an attentional sequence-to-seqquene
model with LSTM and a content- based attention mechanism. Building on [22]. the authors in [21] introduced a feed-forward neural network as a 'grouper', transforming the simple sequence-to toreeeett--euuence model into a hierarchical model. This hierarchical model enhances the grouping ability of the RL framework, facilitating the rapid identification of more suitable placement solutions.
As opposed to using sequence-to-sequenee models the agent of the RL framework, Placeto [1] employed graph neural networks to extract and learn essential features of computation graphs, enabling the transfer of learned placement policy to unseen computation graphs without the need for retraining. The proposed approach used the structural information of the graph to better understand the interdependencies and communication costs, leading to more informed placement decisions. However, its node-by-node placement methodology might lead to longer training times and difficulties in scaling to very large computational graphs. The work in [33] combined graph neural networks and sequence-tee waweenceeto-sequeeee sequeeee models into an RL framework, initially encoding the computation graphs using GraphSAGE [8], then placing operations onto devices in one shot with the Transformer-Xx XL model [5]. Leveraging the combination of GNNs and
models, the authors in [15] adopted contrastive learning as a pretraining method for GNNs, potentially impacting the training process of the RI. framework. They introduced a GNN model that incorporates both the graph structure of the computation task and the characteristics of the hardware devices. Their model predicts the execution time of various operations across different devices, providing holistic view that guides the placement algorithm.
Relevance to our approach. According to [33], all device placement frameworks relying on RL can be split into two main categories: 'grouper-placer and macoder-placerr The former structure initially divides the entire computation graphs into multiple groups and then allocates devices for each group. The latter learns features of computation graphs the first phase and then predicts the device for each operation within the computation graphs based on the extracted features. The authors in [33] stated that the 'encoder-placer' structure offers more flexibility and generality than traditional 'grouper- placer' designs. The two structures share the same concept of grouping computation graphs with their main difference being that the "grouper-placer" structure explicitly defines group partitioning, whereas the 'encoder-placer" structure achieves the concept of grouping through feature grouping encoding. Therefore, previous works essentially employed the technique of grouping and achieved encouraging results. Following similar direction, our framework builds on the concept of grouping and utilizes a GNN as an agent learn policy for the device placement problem.
C Preliminaries
Graph. Consider a graph = (V, E) where V denotes the set of vertices and E C V x represents the edges connecting these vertices. Each vertex E V is associated with feature vector x,, Edges can also have feature vectors denoted by Xu. v) E E, representing the features of the edge from node to node v.
Neighborhood of node. The neighborhood of a node is defined follows:
((t) (v) UNNou((P) {u V (u,v) EV (v, E
(15)
13

---

C.1 Message-Passingg neural networks
The core operation of GNNs involves a message-passing mechanism where nodes communicate and update their states. The iterative update process involves several layers and can be formulated as follows.
Message function. For each edge (u, v)) a message min is computed at each layer t. This message a function of the features of the adjacent nodes and the edge itself:
(t)
( E
MESSAGE(h (0) h,, Xuv)
(16)
where h and h are the feature vectors of nodes u and e at layer t. Aggregation function. Each node aggregates messages from its neighborhood of nodes .V(v):
(1+1) = AGGREGATE (m ((()))
(17)
Update function. The feature vector of each node v is updated based on its previous state and the aggregated messages:
h ((+1) UPDATE(( a (++))
(18)
In all the cases above, UPDATE, AGGREGATE and MESSAGE can any arbitrary differentiable function (i.e., neural networks).
Layer and model configuration. A GNN consists of several layers, where each layer applies the message, aggregation and update functions iteratively. The output h(7) after layers can utilized for various tasks such classification, regression other predictive tasks relevant the nodes or the entire graph. In our case, we use the output h1²") for the device placement problem.
D Benchmark models
D.1 Inception- V3
is advanced convolutional neural network (CNN) that has significantly con- tributed to the field of image recognition. Building on the architecture of its predecessors, Inception- V3 incorporates several key innovations enhance both accuracy and computational efficiency. The model utilizes factorized convolutions, which decompose traditional convolutions into smaller, more efficient operations, effectively reducing the computational burden without compromising perfor- mance. Additionally, Inception-V3 employs auxiliary classifiers at intermediate layers to combat the vanishing gradient problem, thereby improving the training process. The model also extensively uses batch normalization to stabilize and accelerate convergence. These enhancements enable Inception- V3 achieve of-te-of-the-ar results on large-scale image datasets such ImageNet, making it a robust and efficient choice for variety of computer vision tasks, including image classification and object detection.
Inception-Ve V3 [25]
D.2 ResNet
ResNet (Residual Networks) [10] represents groundbreaking advancement in the field of deep learning, particularly in the domain image recognition. ResNet addresses the challenge of training very deep neural networks by incorporating residual learning. The key innovation lies in its use of residual blocks, which allow the network to learn residual functions with reference to the input layer. This approach helps mitigate the vanishing gradient problem, enabling the training of networks with hundreds or even thousands of layers without degrading performance. Each residual block contains skip connections or shortcuts, that bypass one or more layers, facilitating better gradient flow and making the optimization of deep networks more feasible. ResNet models have achieved remarkable success in various competitions, including the ImageNet Large Scale Visual Recognition Challenge, where they set new benchmarks for accuracy. The architecture's ' robustness and scalability have made ResNet preferred choice for numerous computer vision tasks, from image classification and object detection to semantic segmentation and beyond.
14

---

D.3 BERT
BERT (Bidirectional Encoder Representations from Transformers) [6] is a transformative model in NLP. Unlike traditional NLP models that process text either from left to right or right left, BERT utilizes bidirectional approach, allowing it to consider the full context of a word by looking at the words that come before and after it. This bidirectional capability is achieved through the use of Transformer encoders, which leverage self-attention mechanisms to weigh the importance of different words in sentence relative to each other. One of BERT's key innovations is its pre-training and fine-tuning approach. BERT is first pre-trained on a large corpus of text using two unsupervised tasks: Masked Language Modeling (MLM) and Next Sentence Prediction (NSP). MLM, some of the words in the input are masked at random, and the model is trained to predict these masked words based on their context. NSP, the model trained to predict two sentences are consecutive. After pre-training, BERT can be fine-tuned on variety of specific tasks such as question answering. sentiment analysis, and named entity recognition, by adding just a few additional output layers.
E Algorithm Pseudocode
In this section, we present the detailed pseudocode for our main method, HSDAG.
Algorithm Hierarchical Structure-Aware Device Assignment Graph (HSDAG)
1: Initialize computation graph G, coarsened graph G', node features F, and maximum iterations
maTinterrations-
2: Initialize parameters 0 of Graph Parsing Network (GPN) and Multi-Layer Perceptron (MLP).
3: Initialize node assignment matrix X, Adam optimizer, buffer size x, and discount factor 7/
4: for 1 to interattti do
5: Apply GPN: (C, F.) = GPN F), where are clusters and F. are cluster features.
6: Apply MLP: P' ML)(F.) get device placement for the coarsened graph.
7: Map P' to original graph G using assignment matrix X.
8:
Deploy 9 with device placement P' and measure inference latency b (G').
9:
Calculate reward: Ty (G') 1/4p (G").
Update embeddings: Z, Z, + Z.,' for each node e and its corresponding coarsened v'.
11:
Form new coarsened graph G' as the new state.
Run a new round of representation and group learning for new graph g'.
13:
Store step information (P, "'rrr'('") in buffer.
14:
if buffer reaches x steps then
15:
Compute gradient: (0) R ΣE ii=1 V Vologp(P(C':0)- - r(P:, G) Update policy parameters using Adam optimizer with the computed gradient. Clear buffer.
16:
17:
18:
end
19: if convergence criteria are met then
20: Break
21: end if
22:
end for
23:
return optimal device placement P opt-
The Graph Parsing Network algorithm is explained in detail in [24] and is reproduced in Algorithm 2 for convenience.
F Computation graph construction using the Open VINO toolkit
The Open (Open Visual Inference and Neural Network Optimization toolkit, developed by Intel, is a comprehensive toolkit designed to accelerate the development of applications involving deep learning inference and computer vision. It enables developers to deploy pre-trained models across variety of Intel hardware, including CPUs, integrated graphics, VPUs (Vision Processing Units), and FPGAs (Field Programmable Gate Arrays), thereby optimizing performance and efficiency.
15

---

Algorithm 2 Graph Parsing Network
1: Initialize input graph G with node features X and adjacency matrix A.
2: Initialize learnable parameters W for the GNN.
3: for each iteration do
Perform graph and node encoding: Z = GNN(N, A) -
4:
where
Á I, Ei
5:
Calculate edge score matrix:S,... = (6(20, zu)) where Φ is ML..
6:
Apply Graph Parsing Algorithm A:
Stage I: (()) + (O
7:
8:
Initialize: 8 + 0.p
9:
Stage 2: While sum sum(((() * 0:
idx + aarggaar (((k))
10:
q a |idx
(1, "d.dd') + (idr, ((K))
13:
idr & union[idr, idr')
14:
While |idx] = q:
15:
uniionss (i.p))i El)
6 + O, V(i,)) E idæ
16:
17:
p p+1
18:
Stage 3: Finalize clusters.
19:
Create node assignment matrix: X' A(E)
20:
Define adjacency matrix for pooled graph: A' = X X
21:
end for
22:
return pooled graph G' and node assignment matrix
F1 Key Features and Components
This component is cross- pross-platfomm command-line tool that facilitates the conversion of trained models from popular deep learning frameworks such as TensorFlow, Caffe, MXNet, Kaldi, and ONNX into an optimized Intermediate Representation (IR) format. This format consists of a pair of files (.xml and _bin) which describe the network structure and contain the binary weights, respectively. The Model Optimizer reduces the model size and increases inference speed by performing transformations such as batch normalization folding, constant folding, and layer fusion.
Model Optimizer:
The Inference Engine is high-performance, inference delivery library that provides an API to deploy the optimized models on various Intel hardware. abstracts the complexity of hardware-specific optimizations and provides unified API for different devices, allowing developers to write their code once and run across different Intel hardware without modification. The Inference Engine supports heterogeneous execution, enabling the distribution of computational workloads across multiple devices.
Inference Engine:
Pre-Traime Trained Models: OpenVINO includes Model Zoo that provides collection of optimized and pre-trained models for a wide range of applications, including image clas- sification, object detection, semantic segmentation, and more. These models can be used directly or fine-tuned for specific use cases, significantly reducing the time required to develop and deploy AI solutions.
This is graphical interface that helps developers visualize, fine-tune, and optimize models. The Deep Learning Workbench provides tools for accuracy validation, performance benchmarking, and deployment configuration, streamlining the model optimization process.
Deep Learning Workbench:
Support for Heterogencous Execution: VIeO supports the deployment of deep learning models across heterogeneous hardware environments, enabling simultaneous use of CPUs, GPUs, VPUs, and FPGAs. This flexibility allows developers to maximize resource utilization and achieve optimal performance for their applications.
Extensive Documentation and Community Support: Intel provides extensive documenta- tion, tutorials, and sample applications to assist developers in leveraging the full capabilities
16

---

of Open VINO, Additionally, an active community and support forum offer assistance and facilitate knowledge sharing among developers.
Applications and Use Cases
VPenVINO is widely used in various industries, including healthcare, retail, automotive, and industrial automation. enables applications such as medical imaging diagnostics, retail analytics, autonomous driving, and smart manufacturing. The toolkit's ' ability to optimize and deploy deep learning models on edge devices makes particularly suitable for real-time hal-time, low-latency applications where efficient resource utilization is critical.
F33 Computation graphs of the benchmark models
Incepetion- V3
Resnet50
BERT
Before Grouping
After
Grouping
Figure 2: The computation graph of each of the benchmark models before and after the graph partitioning and pooling.
G Co-location heuristic
Following the methodology outlined in [22], we implemented co-location heuristic to coarsen the graph. For each vertex v E V considered in topological order, we applied the following criteria: if U is the sole child neighbor of e, and simultaneously, nt is the sole parent neighbor of vy, then vs and by are grouped into the same co-location set C.. These co-location sets were used to form coarsened graph CG, with the operation type of each co-location set C₂ determined by the mean of the operation types of all u E C..
H Parameters and Hyper-parameter:
This section we provide some implementation details, namely several parameters and hyper- parameter choices, to aid in the reproducibility of our results. The meaning of each parameter is listed bellow as well.
Parameter Descriptions
num devices: Represents the number of processors used to run the model.
hidden hidden__chnnnl:: Represents the dimension the node embeddings generated by GNN encoding.
17

---

Table 6: Model Parameters
Parameter
Value
Parameter
Value
num devices
2
dropouttparring
0.0
hidden_channel
128
link lirk_iinor___sse self _oop
True
layer_trans
2
activation_ final
True
layer_gnn
2
learning_
0.0001
layer_pane everr_parinngee
2
max_ee episodes
100
gnn_mode
GCN
update_ teatettttettppppp
20
dropour_network
0.2
K_epochs
4
myee_trane Represents the number of MLP layers used to map the initial node embeddings in the GNN encoding part.
layer gmnr: Represents the number of GNN layers used in the GNN encoding part.
ayyr_parsingnet: Represents the number of layers in the parsing module.
gnn gnn_model: Represents the type of GNN layer used in the GNN encoding.
Represents the proportion of edges randomly dropped in the grouping
module.
dropout
dropout_pparing: parsing: Represents the proportion of edges randomly dropped in the parsing module.
Lakkiinore_scee self loop: Indicates whether to ignore self-loops in the network links.
act final: Indicates whether apply activation in the final layer.
learning rate: Represents the learning rate of the framework.
max _eeiseede Represents the number of learning episodes for the framework.
Represents the length of the timestep for exploration within each episode.
epochs: Represents the number of policy updates within each episode.
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have shown experiment result in Table 2 that our framework provides faster execution time in the Open VINO framework
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We mentioned our limitation in the conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
19

---

Justification:
is not applicable to our research.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced
statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
We have provided all the system, measurement, toolkit, inference model, and ppeer-parameter setups the best of our knowledge. All critical the result reprodueible in our own setup at least two times. Meanwhile, the source code of this framework is available to the public.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
20

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provided the README file our GitHub that will guide the viewer to run our framework in Appendix A.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ //nips. wwtpccccppccc.oec.cc...ccc..cttt g/guidggsss.// Cooeeuumiis wwwihbbmmsssooo wwwiissssssiieoeeeeiooiiiissisee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have all mentioned the hyperparameters setting of the model in the Appendix. The detail file of the model and the exact configuration is also uploaded to the GitHub repository.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We have measured the execution time in different setting for multiple times in the Appendix. According to the baseline and our own measurement experiment, we believe our measurement is accurate reflection of the execution time under given environment.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
21

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: We have provided all the devices/workers required for completing the research experiments in section 3.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that NeurlPS Code of Ethics https //nuurrrisp... http/p/bcc//ticcccieeeeeeeeeeeee
didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the
Answer: [Yes]
Justification:
We reviewed and followed the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discussed that our goal to improve the efficiency of the execution of the machine learning model in the introduction. We believe the proposed device placement policy will save computation power in order to face the increasingly complex and expensive Foundation Model.
22

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper has no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We have properly cited all the assets we used.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
23

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswithcee thcode com/ conddataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's ' creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We have provided anonymized URL for our new assets and documented the guideline of asset the URL.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer[[NA
Justification: Crowdsourcing and Research with Human Subjects is not applicable to research
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
25


Reviews:
[{"review_id": "xH6SaH2foL", "reviewer": "Reviewer_wsma", "summary": "The paper introduces a novel framework for device placement that leverages smaller computation graphs extracted from the OpenVINO toolkit using reinforcement learning. This framework bridges the gap between encoder-placer and grouper-placer techniques by incorporating graph coarsening, node representation learning, and policy optimization. It supports end-to-end training and considers the directed and acyclic nature of computation graphs. The framework also includes a model variant inspired by graph parsing networks and complex network analysis, enabling joint learning of graph representation and personalized graph partitioning. Experimental results demonstrate significant improvements in inference speed for benchmark models like Inception-V3, ResNet, and BERT.", "questions": "Please kindly refer to the Weaknesses.", "limitations": "The limitations are discussed after the conclusion.\n\nMinor: There is a typo in the limitation section: \"We attempted to obtain \\underline{the he} source codes for the baseline methods\".", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The framework effectively combines graph coarsening, node representation learning, and policy optimization, allowing for a comprehensive approach to device placement that captures both local and global structural features.\n* The ability to train all components of the framework in an end-to-end fashion ensures that the model can learn optimal device placements efficiently, improving overall performance.\n* The proposed framework demonstrates substantial improvements in inference speed, achieving up to 58.2% over CPU execution and up to 60.24% compared to other baselines, highlighting its effectiveness and robustness.", "weaknesses": "* Could the strategy that uses the execution time only of the suggested device placements as a reward to train the proposed framework hinder the generalization of it to other scenarios? Are there any other rewards that the authors attempt to incorporate into their framework?\n* Besides the inference latency, could the authors provide the results of different models on the standard benchmarks to reflect that HSDAG could not only accelerate the deployment but also not affect the performance of downstream tasks?\n* The complexity of the proposed framework and comparison of the running time for getting the final allocation strategy with baselines can further strengthen the manuscript.\n* While the authors elicit the challenges from the perspective of foundation models, could the authors showcase the potential ability of HSDAG in handling foundation models such as LLMs?\n* Minor: The title should follow the Research Paper Title Capitalization Rules. $n=|V\n|$ is the number of nodes that should be noted in Definition 2.2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for recognizing the novelty of our framework, and highlighting its effectiveness and robustness. Below we provide point-to-point responses to your questions/concerns. We hope that our response addresses your concerns.\n\n**Execution time as a reward.**  Thank you for this remark. Most of the existing work on device placement (including our baseline models) uses the execution time as a reward and as the most important evaluation metric since, ultimately, the goal is to speed up the inference time [1,2]. Hence, in this paper, we follow the same protocol. The experimental results (Table 2, page 8)  from both our approach and the baseline models demonstrate that the generalization **is not compromised** by following a strategy to minimize the execution time. Generalization would potentially come into play in the case of a **reward model**, which would make sense for this problem given the difficulty in measuring the reward. Another option for this problem would be to use **incremental rewards** like those mentioned in Section 2.1 of **“Placeto: Learning generalizable device placement algorithms for distributed machine learning”** which, however, do not quite fit our RL problem formulation (but which, interestingly enough, would benefit from a reward model). Exploring the reward model direction, potentially incorporating incremental rewards (the combination of which would allow us to leverage the low variance and faster convergence associated with less sparse rewards) and studying how it impacts generalization, is a very interesting direction for future work. We will briefly mention this in the conclusion.\n\n**Model performance in downstream tasks.** Thanks for your comment and for pointing this out. Theoretically, since the algorithm itself does not change, the performance of the model in downstream tasks will remain the same. For further verification, we conducted experiments using the **Inception-V3**, **ResNet** and **BERT** models and provide the results below:\n\n1. **Inception-V3:**  We performed image classification inference on images depicting Samoyed dogs. All the parameters are directly derived from the torchvision pre-trained model. We did not change any configuration on the data type of the model. The classification accuracy of Inception-V3 using the best device placement is **82.77%**. For the GPU-only experiments the classification accuracy is **82.72%**. For the CPU-only experiments the classification accuracy is **82.33%**. \n\n2. **ResNet:** Similarly, we performed image classification inference using the ResNet model on the same dataset. The classification accuracy with the best device placement is **45.37%**. For the GPU-only experiments the classification accuracy is **45.37%**. For the CPU-only experiments the classification accuracy is **45.44%**.\n\n3. **BERT:** We evaluated the performance of the BERT model using the output embeddings from the different device placements. We calculated their mean squared error, cosine similarity and Euclidean distance (MSE: the lower the better, cosine similarity: the higher the better, euclidean distance: the lower the better):\n\n| Comparison|Mean Squared Error (MSE)|Cosine Similarity|Euclidean Distance (L2 norm)|\n|------------------|---------------------------|-----------------------|------------------------------|\n|CPU vs GPU| 3.04970071738353e-05|0.9999468922615051|0.4328667223453522|\n|**CPU vs HSDAG**|**6.819997793172661e-07**|**0.9999988079071045**|**0.06473180651664734**|\n|GPU vs HSDAG|3.174534140271135e-05|0.9999447464942932|0.44163718819618225|\n\n**The conducted experiments demonstrate that HSDAG does not affect the performance of the model in the downstream tasks. All models have similar performance regardless of the running device (e.g. CPU, GPU or heterogeneous device).**\n\n**Framework’s complexity.**  Thank you very much for the suggestion on calculating the complexity of the proposed methods. We provide a table with the running time complexity in seconds of our method and the baseline methods. As it is shown, **HSDAG** is **significantly faster** in all cases. We agree that these additional experiments do indeed **strengthen our manuscript** and we will make sure to include them in the appendix.\n\n|             | Inception-V3 | ResNet | BERT  |\n|-------------|--------------|--------|-------|\n| Placeto| 2808s| 1162s  | 4512s |\n| RNN-based| 3706s| 1212s  | OOM|\n| **HSDAG**| **2454s**| **1047s**  | **2765s** |\n\n\n**HSDAG handles LLMs.** We indeed elicit the challenges from the perspective of foundation models. We believe that the ever-rising capacity requirements and cost associated with LLMs will make the problem of device placement even more important. Since: 1) our method is not strongly dependent on the architecture or scale of the underlying model, 2) we showcased the effectiveness in diverse architectures and 3) one of those architectures was a **transformer-based** model (BERT) which is the foundation of LLMs, we do believe that HSDAG is extensible and applicable to LLMs. Nonetheless, LLMs pose their own unique challenges and without a strong empirical evaluation on diverse LLM architectures (which would be extensive enough to produce another manuscript), we did not want to make any claim about the extensibility and scalability of our method. We will add 2 short sentences in the conclusion to highlight this future direction and as well as its unique challenges.\n\n**Typos, capitalization rules and missing notation.** We will update and fix it accordingly. Thank you.\n\n**References**\n1. Mirhoseini, Azalia, et al. **\"Device placement optimization with reinforcement learning.\"** International conference on machine learning. PMLR, 2017.\n2. Addanki, Ravichandra, et al. **\"Placeto: Learning generalizable device placement algorithms for distributed machine learning.\"** arXiv preprint arXiv:1906.08879 (2019).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JqfYHuY98N", "reviewer": "Reviewer_orCV", "summary": "This paper introduces an end-to-end framework utilizing policy optimization for device placement during the inference phase of deep learning models. The framework consists of multiple components, including computation graph construction, graph coarsening, node representation learning, and policy optimization. Evaluations using benchmark models such as Inception-V2, ResNet, and BERT demonstrate improved CPU execution speedup compared to several device placement methods.", "questions": "1)\tIn the abstract, the last sentence is confusing: “the suggested placements improve the inference speed for the benchmark models by up to 58.2% over CPU execution and by up to 60.24% compared to other commonly used baselines”.  What is the improvement of 60.24% measured on? Is this accuracy or CPU execution?\n\n2)\tSome notations in Definition 2.2 are not clear. What is the index n in a placement P? Is this equivalent to the number of nodes |V| or to the number of devices |D|?\n\n3)\tIn the problem setup, is there any order when assigning operations to a device? Why do we need to use policy learning?\n\n4)\tWhat does HSDAG stand for?", "limitations": "Some limitations are discussed in the conclusion section.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "+This paper presents a nice overview figure of the proposed framework with a detailed description of each step in the framework.\n\n+The paper has provided code and implementation details.", "weaknesses": "-After reading the paper, I do not think the motivation of the designed framework is strong. It is not clear to me what the rationale of each component and the choice of this policy optimization method is.\n\n-Some suggestions on paper presentation: In the abstract, it would be helpful to introduce the problem of device placement, and the concepts of “computation graphs” and “heuristic methods” in this problem. It is not clear to me why ignoring the topological features of computation graphs is an issue. \n\n-Some redundancy can be reduced. For instance, in definition 2.2, “a device p in D, where p in {1,2,…,|D|}.” \n-The problem setup is confusing. There are also some inconsistent notations between the text and the equations. It would be nice to have some descriptions of the device placement process.\n\n-It seems that graph structural features do not help that much in the speedup from Table 3.\n\n-It would be useful to include the complexity comparison of the proposed method with other baseline methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful comments. We hope our response addresses your concerns and highlights the framework’s motivation and rationale.\n\n**TL;DR:** Our high-level motivation is to address the ever-growing capacity requirements for efficient inference on heterogeneous devices. Please refer to the first two paragraphs of similar work **“Placeto: Learning Generalizable Device Placement Algorithms for Distributed Machine Learning”** where the motivation and the choice of RL for this problem are nicely consolidated. Admittedly, our motivation is not as well-presented. We will make some minor restructuring and make it more clear. \n\n**In the following text, we have prepared for you a detailed explanation of our rationale, which we hope addresses your concerns. We invite you to read it and please let us know if you think we should briefly mention/highlight any of these in the introduction.**\n\n**Limitations, motivation, rationale:**\n1. **Limitation:** Not capturing directed interactions among nodes. **Why is this a limitation?** The model runs poorly in graph coarsening. **Solution:** We use local/global structural features. Our ablation study verifies that such features increase the model’s performance.\n2. **Limitation:** Relying only on heuristics or simple methods (e.g. k-means) for graph partitioning. **Why is this a limitation?** Such methods require hyperparameter tuning for their components to obtain good performance. This ad-hoc presetting of the group number inhibits the exploration, generalization and learning process of a framework. **Solution:** We learn how to partition a given graph into an unspecified number of groups. Both the number of node groups and the pooling algorithm are end-to-end learnable parameters. Our framework facilitates “personalized” partitioning: the number of node groups is dynamically decided depending on the scale of the computation graph and a more sophisticated algorithm for pooling is learned.\n3. **Limitation:** Following either grouper- or encoder-placer architecture. **Why is this a limitation?** In both cases, end-to-end training is not allowed as the encoding and coarsening steps run sequentially and individually. Thus, their components are not trained based on the optimal device placements. **Solution:** We fuse encoder- and grouper-placer techniques and effectively combine their strengths to jointly optimize end-to-end representation learning and graph coarsening phases interdependently.\n4. **Limitation:** Not supporting simultaneously training all steps in an end-to-end fashion. **Why is this a limitation?** Supporting end-to-end training is necessary to ensure each step is tailored to the final device placement. **Solution:** We carefully designed our framework to enable end-to-end training, where all components are trained simultaneously.\n5. **Limitation: Ignoring topological features (also an answer to weakness 4)**. **Why is this a limitation?** Topological features allow frameworks to model the order of nodes. **Solution:** Our framework learns how to better partition a computation graph, leading to better performance. Our ablation study shows the benefits of topological features.\n\n**Introducing concepts, redundancy, inconsistent notations.** We have improved the abstract by introducing the device placement problem and mentioning the concepts of computation graphs and heuristic methods. We have removed redundancies and improved the notation.\n\n**Graph structural features.** The varying impact of graph structural features over different models correlates with the complexity of computation graphs. Inception-V3 has a complex computation graph and an architecture with multiple parallel branches leading to higher values in all metrics (see table below). For such complex graphs, GNN approaches struggle to extract all essential features. So, adding structural features enhances their ability to model important graph characteristics. Conversely, simpler graphs allow GNNs to extract relevant features without external support. So, graph structural features have less of an impact on their performance.\n\n|Metric|BERT|Inception-V3|ResNet|\n|--------|------|--------------|--------|\n|Graph Diameter|34|**49**|32|\n|Average Fractal Dimension|0.00412|**0.00427**|0.00392|\n|Degree of Heterogeneity|1.247|**1.367**|1.268|\n\n**Framework’s Complexity.** Please take a look at a similar response to **Reviewer wsma**.\n\n**Answers to questions:**\n\n**Q1.** Both values refer to execution runtime. As CPU-only execution is one of the most important baselines, we highlight our performance against it. 60.24% is the improvement of the execution speed against Placeto. We have slightly rephrased to avoid confusion.\n\n**Q2.** The index n in a placement $P$ is the number of nodes $|V|$. We included the missing notation.\n\n**Q3 Assigning order and policy learning.** We understand your concern about using policy methods for this problem as the use of RL might not be directly suggested. We invite you to have a quick look at similar studies below: \n1. Figure 2 and Section 2.1 - “MDP Formulation” of **“Placeto: Learning Generalizable Device Placement Algorithms for Distributed Machine Learning”**: The device placement is modeled as an iterative process where the algorithm inputs a current placement, picks a node and outputs a device for that node. \n2. Figure 1 in **“Accelerated Device Placement Optimization with Contrastive Learning”**: The state-space/observation is the entire computation graph and the input to the policy algorithm. The output is an assignment that maps each node to a device. Our problem formulation is similar to this one.  \nIn both cases, the order of assigning nodes to devices does not matter. This is not due to the RL problem formulation but rather due to the nature of the problem. The reward only depends on the final device placement.\n\n**Q4 HSDAG** = Hierarchical Structure-Aware Device Assignment Graph", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RHKspQPeke", "reviewer": "Reviewer_PWmk", "summary": "The authors have developed a model that automatically places neural network operations on the optimal devices (CPU and GPU) to accelerate model training. They optimize device placement using reinforcement learning and use execution time as the reward. The authors propose using the graph structure as information to choose the appropriate device for each operation. They evaluate their method based on execution time gains compared to several baselines and demonstrate significant improvements on three architectures.", "questions": "I did not understand how the computation graph of the neural network was retrieved. Could you please provide more details?\nIs there any impact of the chosen GNN architecture, such as GCN or GAT, for example?", "limitations": "I see no ethical limitations; the checklist is well completed, and clear justifications are provided.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The paper is very well written, and all the steps of the model are well detailed, making it easy to understand. \n- The experiments reflect the quality of their method compared to the state-of-the-art. \n- The ablation studies show the impact of each component of the model.", "weaknesses": "/", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for the kind words and we are glad that you liked our paper. We provide clarifications on details that may have been unclear.\n\n**Computation graph.** To convert a neural network model to an OpenVINO computation graph, we first design the model using a deep learning framework like PyTorch. Next, we convert and save the model to OpenVINO's Intermediate Representation (IR), which consists of an XML file representing the model's structure. By reading this XML file, we extract the necessary information to understand the model's layers and their connections. Finally, we use this information to build a directed acyclic graph that represents the computation process of the neural network, ensuring each layer is properly mapped and connected.\n\n**Impact of the chosen GNN architecture.** We would like to thank the reviewer for posing this interesting question. There is **no major impact** in choosing a different GNN architecture, such as GCN, GAT, GIN or GraphSAGE. We selected GCN since it is the **de-facto GNN** layer every baseline model uses and the one that was proposed by the paper on graph parsing networks [1]. To verify whether a GNN architecture critically affects the performance of our framework, we run more experiments with different GNN layers. We provide the results in the table below (execution time in seconds):\n\n|           | Inception-V3 | ResNet  | BERT   |\n|-----------|-------------|---------|--------|\n| GCN       | 0.0105      | 0.00766 | 0.00267|\n| GAT       | 0.0109      | 0.00772 | 0.00272|\n| GIN       | 0.0104      | 0.00770 | 0.00269|\n| GraphSAGE | 0.0102      | 0.00767 | 0.00266|\n\n\n**References**\n1. Song, Yunchong, et al. **\"Graph Parsing Networks.\"** arXiv preprint arXiv:2402.14393 (2024).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qBqLRYoy9R", "reviewer": "Reviewer_RMDa", "summary": "The paper is about computation graphs, which is an interesting topic. The authors propose a novel framework for the task of device placement, relying on smaller computation graphs extracted from the OpenVINO toolkit using reinforcement learning. The paper is well written and well organized. However, there are several concerns in the current version of the paper that addressing them will increase the quality of this paper.", "questions": "As above.", "limitations": "The authors provide a discussion of limitations, but it is uncertain whether this is comprehensive.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1 Novel ideas.\n\n2 Good writing.\n\n3 Sound experiments.", "weaknesses": "1 The author mentioned that concatenating features from different angles would bring benefits. So would concatenating or fusing these features at different dimensional sizes affect their effectiveness?\n\n2 This seems like an interesting research question, but the authors don’t seem to explain the methods used clearly in the main text. I think it is necessary to add an appendix to show the whole framework in the form of a flowchart or pseudocode and explain it in detail.\n\n3 Is a larger baseline model needed for comparison? Large models are popular at present. If it is not necessary, the author can explain the reasoning without adding corresponding experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to genuinely thank you for your thoughtful comments and your interest in the selected topic. Please find our response to your comments and suggestions below. We have also updated the manuscript in light of your suggestions towards increasing the quality of our paper.\n\n**1. Concatenating or fusing features at different dimensional sizes.** Concatenating or fusing the initial features at different dimensional sizes indeed affects the effectiveness of the framework. In fact, during our initial experiments, we found that a **well-balanced combination** of feature dimensions results in better model performance and robustness. Therefore, we decided to encode the initial features using equal-sized latent representations. We would like to highlight that the **flexibility** of our framework allows for different feature combination schemes, such as averaging the feature vectors, increasing or decreasing the dimensionality of the feature vectors, or even attending to each feature differently. This is an interesting area for future investigation. We hope that our answer clarifies your question.\n\n**2. Framework explanation and pseudocode.** We would like to thank you for pointing this out and we are pleased you found our research question interesting. Due to the fact that our framework is flexible and can be implemented using a wide range of different components (e.g. using a simple MLP instead of a GCN), the initial goal was to keep the main description of the framework as simple as possible, in an attempt to avoid **information overload** that may confuse and distract the readers. After taking into consideration your suggestion, we have prepared for you a **pseudocode** that describes the entire flow. We will add this pseudocode in the appendix:\n\n**Main Algorithm:** Hierarchical Structure-Aware Device Assignment Graph (HSDAG)\n--- \n1. Initialize computation graph $G$, coarsened graph $G'$, node features $F$, and maximum iterations $max\\_{iterations}$.\n2. Initialize parameters $\\theta$ of Graph Parsing Network (GPN) and Multi-Layer Perceptron (MLP).\n3. Initialize node assignment matrix $\\mathcal{X}$, Adam optimizer, buffer size $x$, and discount factor $\\gamma$.\n4. For $i = 1$ to $max\\_{iterations}$ do\n\n   a. Apply GPN: $(C, F_C) \\gets GPN(G, F)$, where $C$ are clusters and $F_C$ are cluster features.\n   \n   b. Apply MLP: $P' \\gets MLP(F_C)$ to get device placement for coarsened graph.\n   \n   c. Map $P'$ to original graph $G$ using assignment matrix $\\mathcal{X}$.\n   \n   d. Deploy $G$ with device placement $P'$ and measure inference latency $l_{P'}(G')$.\n   \n   e. Calculate reward: $r_{P'}(G') \\gets 1 / l_{P'}(G')$.\n   \n   f. Update node embeddings: $\\mathbf{Z_v} = \\mathbf{Z_v} + \\mathbf{Z_{v'}}$ for each node $v$ and its corresponding coarsened node $v'$.\n   \n   g. Form a new coarsened graph $G'$ as the new state.\n   \n   h. Run a new round of representation and group learning for a new graph $G'$.\n   \n   i. Store step information $(P, G', r_{P'}(G'))$ in buffer.\n   \n   j. If buffer reaches $x$ steps:\n      - Compute gradient:\n        $\\nabla_\\theta J(\\theta) \\approx -\\sum_{i=1}^x \\nabla_\\theta \\log p(P | G'; \\theta) \\cdot \\gamma^i \\cdot r(P_i, G)$\n      - Update policy parameters $\\theta$ using Adam optimizer with the computed gradient.\n      - Clear buffer.\n   \n   k. If convergence criteria are met, break the loop.\n\n5. Return optimal device placement $P_{opt}$.\n\n**Sub-Algorithm: Graph Parsing Network (GPN)**\n---\n1. Initialize input graph $G$ with node features $X^{(0)}$ and adjacency matrix $A$.\n\n2. Initialize learnable parameters $W$ for GNN.\n\n3. For each iteration:\n\n   a. Perform graph and node encoding:\n      $Z = GNN(X, A) = \\sigma(\\hat{D}^{-1/2}\\hat{A}\\hat{D}^{-1/2}X^{(0)}W)$ \n      where $\\hat{A} = A + I$, $\\hat{D_{ii}} = \\sum_{j=0} \\hat{A}_{ij}$\n\n   b. Calculate edge score matrix:\n      $S_{v,u} = \\sigma(\\phi(z_v, z_u))$, where $\\phi$ is MLP\n\n   c. Apply Graph Parsing Algorithm $\\mathcal{A}$:\n      - Stage 1: $\\hat{C}^{(k)} \\gets DOM(C^{(k)})$\n      - Initialize: $s \\gets \\emptyset$, $p \\gets 0$\n      - Stage 2: While $sum(\\hat{C}^{(k)}) \\neq 0$ do:\n        * $idx \\gets argmax(\\hat{C}^{(k)})$\n        * $q \\gets |idx|$\n        * $(l, idx') \\gets EXP(idx, \\hat{C}^{(k)})$\n        * $idx \\gets union(idx, idx')$\n        * While $|idx| = q$:\n          + $s \\gets union(s, \\{(i,p)|i \\in l\\})$\n          + $\\hat{C}^{(k)}_{i,j} \\gets 0, \\forall (i,j) \\in idx$\n          + $p \\gets p + 1$\n      - Stage 3: $S^{(k)} \\gets GEN(s)$\n\n   d. Create node assignment matrix:\n      $\\mathcal{X} = \\mathcal{A}(\\mathcal{E})$\n\n   e. Define adjacency matrix for pooled graph:\n      $A' = \\mathcal{X}^T \\cdot A \\cdot \\mathcal{X}$\n\n4. Return pooled graph $G'$ and node assignment matrix $\\mathcal{X}$\n\n\n**3. LLM comparison.** Thank you for the question. Experiments on LLMs would be beneficial to have although not strictly needed for demonstrating the effectiveness of our method. Given that our method is not strictly dependent on the model architecture, and that we showed its effectiveness on a diverse set of architectures, one of which was **transformer-based** (the foundation of LLMs), we do believe that our method would be scalable and effective for LLM as well. **Reviewer wsma** made a quite similar comment. We kindly ask you to have a look at this response as well, as it provides additional context. \n\n**Limitations.** Thank you for your comment. We kept the discussion of limitations section within the required space limits. We will elaborate more on this section and provide a revised version in the appendix.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their careful reading and thoughtful comments and suggestions on our paper. We find it encouraging that reviewers have found our work **interesting**, **novel** and **well-organized**! The suggestions have led us to further improve the clarity of the manuscript, improve minor issues as well as add some more technical details. We have addressed the individual reviewer’s comments below. Here, we **summarize** the proposed changes, which we hope are within the extent of **allowed modifications** and would not fundamentally alter the main method and results. 

**Changes:**

* Additional experiments: We will add the results of the auxiliary experiments conducted during the rebuttal period to the Appendix of the paper. These experiments: 
    1. Demonstrate that the performance of downstream tasks is indeed **not affected** by our framework (**Reviewer wsma**);
    2. Show the **complexity** of the framework (**Reviewer orCV**, **Reviewer wsma**);
    3. Demonstrate the **importance** of the graph structural features (**Reviewer orCV**).
* Fixing notation issues, typos, and briefly introducing the problem definition in the abstract (**Reviewer orCV**, **Reviewer wsma**).
* Slightly restructuring the introduction to make the **high-level motivation** more clear (**Reviewer orCV**).
* Summarize our entire flow in a **pseudocode** block to be added in the appendix (**Reviewer RMDa**).
* Add a few future research directions and limitations in the conclusion and appendix, respectively (**Reviewer RMDa**, **Reviewer wsma**).

Meta-review: This paper presents a novel structure-aware framework using reinforcement learning to optimize device placement in computation graphs, showing substantial improvements in inference speed for deep learning models. The approach effectively incorporates graph structural features, providing a robust solution that bridges existing gaps in device placement techniques. While initial concerns were raised regarding the clarity of motivation and theoretical contributions, the authors' detailed rebuttal successfully addressed these points, demonstrating the framework’s practical relevance and strong potential for real-world applications.
Decision: Accept (poster)