Terra: Imperative-Symbolic Co-Execution of Imperative Deep Learning Programs
Authors: Taebum Kim
Eunji Jeong
Geon-Woo Kim
Yunmo Koo
Sehoon Kim
Gyeong-In Yu
Byung-Gon Chun
Venue: NeurIPS 2021 Poster (2021)
Keywords: machine learning system

Abstract: Imperative programming allows users to implement their deep neural networks (DNNs) easily and has become an essential part of recent deep learning (DL) frameworks. Recently, several systems have been proposed to combine the usability of imperative programming with the optimized performance of symbolic graph execution. Such systems convert imperative Python DL programs to optimized symbolic graphs and execute them. However, they cannot fully support the usability of imperative programming. For example, if an imperative DL program contains a Python feature with no corresponding symbolic representation (e.g., third-party library calls or unsupported dynamic control flows) they fail to execute the program. To overcome this limitation, we propose Terra, an imperative-symbolic co-execution system that can handle any imperative DL programs while achieving the optimized performance of symbolic graph execution. To achieve this, Terra builds a symbolic graph by decoupling DL operations from Python features. Then, Terra conducts the imperative execution to support all Python features, while delegating the decoupled operations to the symbolic execution. We evaluated Terra’s performance improvement and coverage with ten imperative DL programs for several DNN architectures. The results show that Terra can speed up the execution of all ten imperative DL programs, whereas AutoGraph, one of the state-of-the-art systems, fails to execute five of them.

Terra: Imperative-Symbolic Co-Execution of Imperative Deep Learning Programs
Taebum Kim
Eunji Jeong" Samsung Research eun-ji, e samsung com
Seoul National University, FriendliAl
x taebum@ snu ac kr, friendll.iieeni.... iendliidii
Geon-Woo Kim
Yunmo Koo
Scoul National University, FriendliAI
Scoul National University, FriendliAl mpbio03@snu. ac.kr, yumornaingefrienni
gwsshs22@snu. aac.uuacc. ac.kr, kr, @wsshs22efriendli.
Sehoon Kim University of California, Berkeley sehoonkinmberkeley. edu
Gyeong-In Yu Seoul National University gyeonginEsnu. ac.
Byung-Gon Chun
Scoul National University, FriendliAl bgchun& snu. ac. kr, b friendlirridddi...mm
Abstract
Imperative programming allows users to implement their deep neural networks (DNNs) easily and has become an essential part of recent deep learning (DL) frame- works. Recently, several systems have been proposed to combine the usability of imperative programming with the optimized performance of symbolic graph execu- tion. Such systems convert imperative Python DL programs to optimized symbolic graphs and execute them. However, they cannot fully support the usability of imper- ative programming. For example, if an imperative DL program contains a Python feature with no corresponding symbolic representation (e.g., third-party library calls or unsupported dynamic control flows) they fail to execute the program. To co-execution
overcome this limitation, we propose Terra, an imperative-symbort system that can handle any imperative DL programs while achieving the optimized performance of symbolic graph execution. To achieve this, Terra builds a symbolic graph by decoupling DL operations from Python features. Then, Terra conducts the imperative execution to support all Python features, while delegating the decoupled operations the symbolic execution. We evaluated Terra's 's performance improve- ment and coverage with ten imperative DL programs for several DNN architectures. The results show that Terra can speed up the execution of all ten imperative DL programs, whereas AutoGraph, one the ttat-oofthe--an systems, fails to execute five of them.
Work done at Scoul National University 1 Correspon author
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Introduction
The rapid evolution of deep neural networks (DNNs) has been fueled by the support of deep learning (DL) frameworks 66 32]. Such frameworks provide users with programming layer to build and execute DNNs, commonly adopting Python as their host language. Typically, they execute DL programs with one of the execution models: imperative or symbolic execution. In the former, the Python interpreter executes a DL program as a normal program, invoking DL operations on-the-fly. The invoked DL operations are executed separate DL accelerator asynchronously, and the Python interpreter continues running the program. The dynamic control flows of the DL operations are naturally expressed by the interpretation of the program, and users can utilize any functionalities of Python (e.g., dynamic typing and third-party libraries [6) while executing DL operations. On the other hand, in the latter model, the Python interpreter embeds DL operations into a symbolic graph that represents the entire dataflow of a DNN. Thus, users should define their DL programs only with existing symbolic operations that DI. frameworks support. In other words, the dynamic control flows of DNN should be explicitly represented by control flow operations (e.g., tf cond and tf. while e of TensorFlow). However, the symbolic execution can take advantages of various optimization techniques because the symbolic graph contains whole computation lineage of a DNN architecture.
Although symbolic execution achieves higher performance compared to imperative execution, imper- ative execution has been preferred because its usability. Several systems 3 4
[5
19
20
39
have been proposed to match the speed of symbolic execution while enjoying the benefit of imperative execution. These systems attempt to generate symbolic graph that represents an entire imperative
program and execute the graph instead of imperatively running the program. Methods for generating the symbolic graph can be broadly classified into two approaches: single path tracing and static compilation. The former approach generates symbolic graph by imperatively executing a single iteration of a program and recording the executed DL operations. Systems that adopt the latter approach translate the abstract syntax tree (AST) of program into a symbolic graph.
Unfortunately, both approaches can correctly handle only subset of imperative DL programs. For example, dynamic control flows in an imperative program are not captured by the single path tracing approach. On the other hand, the static compilation approach cannot correctly generate a symbolic graph if target program contains an AST node that does not have a corresponding symbolic operation such as try-excepts, generators, Python object nutations, and third-party library calls. As result, is up to the users to clearly understand the limited usability of these systems.
In this paper, we propose Terra, an imperative-symbeet tations. While the previous approaches replace the imperative execution with the symbolic execution, Terra maintains the imperative execution support all Python features where DL operations are delegated to the symbolic execution. Also, Terra generates a symbolic graph by utilizing multiple traces of an imperative program. To be specifie, Terra imperatively runs an imperative DL program for several iterations and collects traces, each of which is a linear chain of DL operations sorted by the exccution order. The collected traces are merged into a TraceGraph, directed acyclic graph (DAG) that encapsulates the captured DL operations along with their diverse execution orders. Terra stops collecting traces when the trace of the latest iteration is already embedded in the TraceGraph. To generate an executable symbolic graph from the TraceGraph, Terra adds additional information to the TraceGraph. First of all, Terra annotates the TraceGraph to enable communication between the imperative execution and the symbolic execution. In addition, Terra further analyzes the TraceGraph to insert control flow operations explicitly, so that a symbolic graph can be executed with the DL operations in a certain trace. After generating a symbolic graph from the TraceGraph, Terra starts the co-cxecution of a skelcton imperative program, in which DL operations are not performed, and the symbolic graph that represents the DL operations. Here, Terra continually checks whether the current trace is being expressed by the TraceGraph. If Terra detects a new trace, Terra discards the symbolic graph and collects more traces by running the original program imperatively. Terra then re- generateee the symbolic graph and restarts the co-execution. Consequently, Terra is able to run any imperative DL programs correctly and efficiently even if it contains the Python features that the previous approaches cannot handle.
co-execution system that addresses the limi-
We have implemented Terra on TensorFlow v and compared Terra with TensorFlow's imperative execution (7) and AutoGraph (29). Our evaluation shows that Terra can train ten imperative DI. programs including convolutional neural networks, wansformer-basee networks, and generative

---

def train_step(x):
def generator():
1 Dropper()
library_call10
for in range yield arrandom.oomaal..
2 dr.drop daddropprrbbbbop 0.8
loss model(x, y)
def train_step(step, x):
library_cal12(
if step 100:
loss.numpy()
def train_step(x):
dr, un..dro_prodd 0.8
for y in generatorO: x + return
6
uf..n.droooutt
7
x, dn.drop__robb) return
third-party library call & tensor materialization
(a)
(b) dynamic control flow
(c) Python object mutation
Figure 1: Simple examples that the static compilation approach cannot deal with. Note that AutoGraph could silently produce an incorrect result in the Python object mutation case.
adversarial networks up to 1.73x faster than the original imperative execution. However, AutoGraph fails to support five programs for three reasons: third-party party library call, Python object mutation, and tensor materialization during conversion, which we describe in $2.2
2 Background & Related Works
2.1 Imperative and Symbolic Execution
The imperative execution (a.k.a. a. define-by-runi
treats DL, program entirely typical Python program. Whenever the Python interpreter encounters a statement that declares a DL operation (e.g.. = torch. matmul (x, y)), the interpreter asynchronously invokes a corresponding compu- tation kernel DL accelerator (typically GPU or TPU). The imperative execution highly improves the programmability of DL programs because users can fully utilize the convenient language features and rich ecosystem Python, including built-in functions, dynamic control flows, dynamic typing, and third-party libraries. However, since the imperative execution cannot obtain whole view of DNN computation, misses optimization opportunities that the symbolic execution explained below carry out.
30
32 43
The symbolic execution (a.k.a. define-and-run) 6 executes a pre-built symbolic graph. In the symbolic execution, users should express their DNN architectures symbolic graphs using the three kinds of symbolic operations: DL operations, control flow operations, and auxiliary operations. The DL operations conventional compute-intensive operations (c.g., matrix multiplication or convolutional layer), and the control flow operations determine which DL operations to be executed based tensor value within the graph. Finally, to mitigate the limited usability of the symbolic execution, supports auxiliary operations (c.g., tf print and tf. _p_____fug vy_function of TensorFlow). After the symbolic graph is constructed, graph optimizations could be applied such operation fusion [T]
20
26
31 35|
[4
46
47 48 parallelized execution [3 31
33 device placement (27
28
48
layout optimization 20
25 and memory optimization 8 17 18 Then, optimized
graph executor such as TVM 11. TensorRT 31. TFRT 40 and XLA undertakes the actual execution of the symbolic graph.
2.2
Imperative Program with Symbolic Execution
There are approaches gain the usability of imperative execution and the performance of symbolic execution simultaneously. They attempt to convert an imperative DL program to a symbolic graph and exploit the symbolic execution with the converted graph. The single path tracing approach (e.g., torch. trace (3). JAX (15), and tf. function (39]) executes an imperative DL program once and records all DL operations that were executed. A single linear chain of the executed DL operations, which is called trace, becomes symbolic graph of the imperative program. The symbolic graph is executed instead of the imperative program for subsequent iterations. Although the single path tracing approach looks very simple and intuitive, it is hard to capture dynamic control flows the imperative program with this approach. declare the control flow operations for all dynamic control flows in their imperative programs, which undermines the programmability of the imperative program. Moreover, Python features that do not have corresponding symbolic operations (e.g., mutation of Python objects, use of third-party libraries)
reflect them correctly, users need to explicitly

---

are neither captured by the trace. It can yield an incorrect result since, in the following iterations, a graph executor executes a symbolic graph, which does not contain the Python features.
The static compilation approach (e.g. TorchSeript 4 and JANUS 19) is proposed to resolve the problem of the single path tracing approach. In contrast the single path tracing approach, the static compilation approach does not extract a trace to generate a symbolic graph. Instead, it traverses an abstract syntax tree (AST) of the imperative program and directly converts each AST node to a corresponding symbolic operation. Even if it guarantees the correctness of the program, it fails to convert a program to a symbolic graph if the program contains a Python feature with no corresponding symbolic operation. We classify the representative failure cases into four categories: third-party library call, tensor materialization during conversion, dynamic control flow, and Python presents simple examples of the cases. The static compilation approach cannot convert the third-party library calls of Figure [Ta and fails when it attempts to materialize the tensor data (loss. numpy()) during the conversion. Figure [b] shows the generator in Python that the static compilation approach cannot convert. For Figure [c] only JANUS handles it by implementing custom auxiliary operations (i.e., GetAttr and SetAstr operations) that access the Python heap during the symbolic execution.
object mutation. Figure !
To increase the practicality of the previous approaches, AutoGraph (2) combines the static compila- tion approach with the single path tracing approach. AutoGraph converts AST nodes that correspond to dynamic control flow such as if-else. and while to new AST nodes representing proper control flow operations such as tf. cond and tf. while. e. Then, AutoGraph generates a symbolic graph by applying the single path tracing approach to the converted AST. Unfortunately. it cannot fully support various kinds of dynamic control flows such as generator and try-except of Python. Hence, AutoGraph also entails the same correctness problem of the single path tracing approach when the imperative DL program employs the features described in Figure]
When the static compilation approach detects unsupported features, it just raises an error and aborts the program execution. To avoid this, users have to write their programs using only the supported features or put in additional efforts such as annotating types and refactoring functions to use tensor objects for their inputs and outputs. In this regard, AutoGraph (29] and TorchScript 4 provide the official language references [T [5] that users should be aware of before writing a target imperative program. However, those references usually require expert knowledge to understand, imposing a steep learning curve for new users. For example, the language document of AutoGraph [1] spans roughly twelve pages and divides features that AutoGraph does not support into four categories and ten subcategories. TorchScript provides official language specification [5] by enumerating supported features over eleven pages.
TezyTensor (36] is a concurrent work related to ours. It uses the lazy evaluation approach, in which the Python interpreter and symbolic graph executor run altermately. The Python interpreter executes an imperative DL program as it is and extracts a linear trace of operations. Lazy Tensor then checks whether the extracted trace is already cached or not. If cached, Lazy directly executes the cached graph. If not, it compiles and executes the new graph, then stores the graph for further executions. With the lazy evaluation, LazyTensor could support all Python features while executing the symbolic graph Terra does. However, it has an unavoidable performance overhead due to the alternate execution. In other words, the graph executor progresses only when the Python interpreter finishes checking the existence of the cached graph. Similarly, the Python interpreter progresses after finishing the graph execution. Moreover, if an imperative program has a dynamic control flow that is not determined by tensor value, LazyTensor Tensor fails to capture the control flow transparently. In this case, LazyTensor would work inefficiently because the traces could be different for each iteration.
3 Our Approach: Imperative-Symbolii Co-Execution
To the best of our knowledge, no existing DL framework can completely convert an arbitrary imperative DL program into symbolic graph. We believe that a one-to-one mapping from all Python features to corresponding symbolic operations should exist to support all imperative programs with the approaches. In other words, building such a mapping is the same covering all Python syntax with symbolic operations. Moreover, the mapping should be updated as a new feature of Python (c.g., pattern matching of Python 3.10 (3) is introduced. Eventually, it is equal to building new

---

Tracing Phase
Co-Execution Phase
GraphGenerator
PythonRunner
GraphRunner
sumbolic gruph generated
f-foo if
y-foo if x>> 0:.
frace vulidotion
X- (K)
merging fruces
X= X=O(x) (x)
new trace detected
w= (x,y)
O=xx,
Imperative Program
Collected Traces
TruceGraph
Skeletoo
TracoGraph
Optimized Symbolic Graph
Imperative Program
Figure 2: An overview of Terra. Each dotted arrow denotes a) the PythonRunner fetches a ten- sor value from the GraphRunner, b) the PythonRunner informs the Graph Runner of the path that the Rython takes, and c) the PythonRunner feeds external tensor to the GraphRunner. Rectangle in the optimized symbolic graph denotes the control flow operation.
Python execution engine for symbolic graph representing Python program itself, which requires tremendous amount of time and effort.
Therefore, we take different approach that does not replace the entire imperative execution with the symbolic execution as the previous approaches do. Instead, we let the Python interpreter run an imperative program to support all Python features naturally while separating only DL operations from the imperative execution. As the Python interpreter executes the program except performing DL operations, the decoupled DL operations the co-execution, we generate a symbolic graph representing DL operations that would have been launched by the Python interpreter. While the previous approaches have to build complete symbolic graph that encapsulates all semantics of the DL. program for correctness, we construct a symbolic graph solely based collected traces of DL operations. Although we do not embed all semantics of the DL program in the symbolic graph, it can handle any DL program by the co-execution of the skeleton program complementing the symbolic execution. Within the skeleton program, DL operations are not performed but all other Python features are preserved as the original imperative program. Executing the symbolic graph in parallel with the skeleton program, fully achieve the usability of the imperative execution along with the optimized performance of the symbolic execution.
executed by graph executor simultancously. To enable
4 System Design
Terra is a system that realizes our imperative-symbort co-execution approach. In this section, we describe how Terra implements the co-execution of a skeleton imperative program and a symbolic graph in detail. There are two requirements to seamlessly maintain the imperative execution along with executing the symbolic graph. First of all, Terra should allow exchanging tensor values between the imperative execution and the symbolic execution when there exists data dependency between each other (e.g., Figure Tap. Furthermore, the imperative execution should inform the symbolic execution of the correct choice of path to follow because the execution flow of the program is determined by the Python interpreter. To achieve these, Terra implements new symbolic operations for such communication and inserts them into the symbolic graph. In the following, entire process the imperative-symboll collected traces into the TraceGraph and generates symbolic graph from it in detail ($ 4.2
first describe the co-execution ($ 4.T.. Next, we explain how Terra merges
4.1 Imperative-Symbolic Co-Execution
The co-execution of Terra consists the following two phases: the tracing phase and the co-execution phase. Terra begins execution in the tracing phase, as shown in Figure In this phase, the conventional imperative execution is carried out with the given imperative DL program. At the same time, the GraphGenerator collects traces of each iteration. The GraphGenerator incrementally merges the traces into the TraceGraph, a directed acyelic graph (DAG) that encapsulates all the collected traces. Since the number of possible traces during the imperative execution cannot be determined, the GraphGenerator collects traces until the trace of the latest iteration fully covered in the TraceGraph. In such case, the GraphGenerator generates symbolic graph from the TraceGraph.
5

---

feed point
0p
0:4
scort
func(inp, cand, N):
Fetch polint
Op@
rvall random()
x0 opecinp)
0p1
Op2
if
op1(x0, rval)
op2(inp)
0p2
Loop
else:
Op3
Op4
op2(inp)
10
x2 - op3(x1, 2)
Op3
11
print(x2)
OP4
12
for in (N);
13
x2 op4(x2)
Loop
return
end
First Trace
Second Trace
(a) Imperative DL. Program
(b) Collected Traces
(c) Merged TraceGraph
Figure 3: Illustration of how the TraceGraph is merged from the imperative DL program.
With the generated symbolic graph, Terra enters the co-execution phase. In this phase, Terra uses the RythonRunner and the GraphRunner. The PythonRunner executes a skeleton imperative program that does not launch DL operations anymore. The GraphRunner executes the generated symbolic graph with separate graph executor. For each DL operation, the Rython skips the actual computation and creates an empty tensor object(s) as an output(s) of the operation. If the Python- Runner has materialize an empty tensor (e.g., print a loss value), it fetches the actual data from the GraphRunner. Similarly. the GraphRunner might need an external tensor (c.g., an input data, Python primitive value) from the Rython Terra implements new symbolic operations to establish the communication. For each communication, Runner that needs the data from the other waits until the required data becomes ready.
For every iteration in the co-execution phase, the PythonRunner keeps a trace being made by the DL operations in the current iteration. The RythonRunner continuously compares the trace with the TraceGraph to notify the GraphRunner of the current control flow and check the validity of the symbolic graph in the GraphRunner. If the latest DL operation in the trace indicates that the PythonRunner takes a specific path, it informs the GraphRunner of the path with new symbolic operation, which sets conditional input of a corresponding control flow operation in the symbolic graph. For example, if the PythonRunner takes the true path of the skeleton imperative program of (i.., if executes the operation of the true path. Furthermore, if the latest DL operation is not expressed in the TraceGraph, Terra considers the current trace as new trace that the existing symbolic graph cannot handle. Terra then cancels the execution of the GraphRunner and falls back to the tracing phase. Thereafter, the GraphGenerator collects more traces and generates a new symbolic graph covering more traces than before to continue the co-execution.
0:), the GraphRunner receives such information from the PythonRunner and
4.2 Symbolic Graph Generation
In this section, we describe how the GraphGenerator merges the collected traces into the TraceGraph and then generates a symbolic graph from the TraceGraph.
TraceGraph. Each node of the TraceGraph corresponds to DL operation, and each edge denotes an execution order between two nodes. For example, if a Conv2D operation followed by another ReLU operation in single trace, the TraceGraph has a directed edge from a Conv2D node to ReL. node. For the first trace, the TraceGraph contains a single linear chain of nodes that have two extra nodes; the start node and the end node. Those nodes do not correspond to DL operations but for indicating the start point and the end point of the merging.
For subsequent traces, the GraphGenerator attempts to match each operation of the trace with an existing node of the TraceGraph. The GraphGenerator uses pointer that points to the latest matched node of the TraceGraph, which initially points to the start node. For each operation, the GraphGenerator checks whether there exists an equal node among the children of the latest matched node. To check the equality, the GraphGenerator compares the type of operation (e.g., Conv2D and MatMul), attributes of operation (e-g., filter size and kernel size of convolution), and whether two operations were executed at the same location of the program. If the GraphGenerator finds the

---

Switch-Case
Case Select
case
Loop Cond
Input Feeding
While
Op1
Qp2
Opd
Op4
cuse
0p2
Output Fetching
Figure 4: Generated symbolic graph from the TraceGraph of Figure 3c
child node of the latest matched node which satisfies all criteria, the GraphGenerator updates the latest matched node that child node, not creating new node. It then continues merging the next operation of the trace. If all the operations are matched, the GraphGenerator sets the latest matched node to the end node, denoting that the current trace is already captured by the TraceGraph. The definition of the equality criteria is in Appendix A.
When the GraphGenerator fails to match the operation with the existing nodes, it denotes that new trace is detected. A new node is created by creating a new branch from the latest matched node. While expanding the TraceGraph for the new trace, the expanded branch could be merged back into the pre-existing branch there is a node that is not a child of the latest matched node but satisfies all criteria of equality. For example, Figure 3c depicts the TraceGraph built from the program of Figure 3al which first took the true path (line 5-6) and took the false path (line 8-9) at the second execution. From the program, the GraphGenerator collects two different traces as shown in Figure 3b When the GraphGenerator attempts to merge the second trace into the TraceGraph that contains the first trace, 0p2 of the second trace cannot be matched with Op/ and cannot be merged back into Op2 of the first trace because two Op2s were executed in different locations. Thus, the node for Op2 is created the right branch Figure 3c and the branch is merged when the GraphGenerator succeeds to match Op3.
As shown in Figure 3c the GraphGenerator merges the nodes that exccuted in the same loop of the program. The GraphGenerator is aware of the loop because it compares the program location where DL operations were executed. It then groups those nodes within extra loop node and conducts merging the nodes separately. For example, Loop in Figure[3cjia is the loop node for the loop of Figure 3a (line 12-13). The GraphGenerator merges the second Op4 of the first trace with the first Op4 of the first trace because they were executed in the same loop. Also, Op4 of the second trace is merged to the same node.
To create the symbolic operations for data communication between the Rynhon and the GraphRunner, the GraphGenerator captures communication points and an- notates such points in the TraceGraph. Those points are classified into feed points and fetch points. The feed point is where the operation gets an input from the Python interpreter such as training data and Python primitive values. Similarly, the fetch point is where the Python interpreter needs a value of the DL tensor. For example, Op/ in Figure 3a receives rval as an input (line 5), and the Python interpreter needs the value of x2 (line 11) to print it out. The GraphGenerator captures those points and annotates them in the corresponding nodes of the TraceGraph.
Communication Point.
converts the nodes in the TraceGraph to the corresponding DL operations and creates additional Input Feeding and Oulput Fetching operations to establish data communication during the co-execution. The Inpul Feeding operation corresponds to the feed point of the TraceGraph, enabling the PythonRunner to feed an external tensor to the GraphRunner. Similarly, the Output Fetching operation corresponds to the fetch point of the TraceGraph, allowing the PythonRunner to fetch materialized DL tensor from the GraphRunner. As a result, the GraphGenerator represents the entire computation lineage in the single graph with the communication operations. Without those operations, the GraphGenerator should split the symbolic graph into smaller subgraphs at every feed-fetch point, which cannot efficiently apply additional optimizations.
Symbolic Graph Generation. The
To handle the diverse control flows the TraceGraph, GraphGenerator utilizes the Switch-Casse operation (e.g.. tf. case of TensorFlow), which allows executing only a single case that depends on particular condition. For the conditional input that informs the Switch-Case operation of which case to execute, the GraphGenerator creates the Case Select operation along with the Switch-Car operation,
7

---

Program
Reason of the failure
DropBlock [2]
Python object mutation
Music Transferrrerrrmer 21
Python object mutation Python object mutation third-party library call tensor materialization during conversion
SDPoint 22
BERT-CLS 24
FasterRCNN
Table 1: The programs that AutoGiraph fails to execute and the reason for the failures. Note that Terra can execute all of them.
as shown in Figure When the PythonRunner takes a certain path, it notifies the GraphRunner via the Case Select operation. Here, the GraphGenerator uses our case assignment algorithm that takes the TraceGraph as input, traverses the TraceGraph, and returns the Switch-Cass operations representing the control flows correctly. The formal description of the algorithm and the proof that the algorithm can handle any DAGs are described in Appendix B.
Finally, the GraphGenerator creates the While operation (e.g.. tf wff. e of TensorFlow) for a loop node of the TraceGraph. As the Case Select operation, the GraphGenerator creates the Loop Cond operation along with the While operation. The PythonRunner informs the GraphRunner of whether the PythonRunner goes to the next iteration of the loop exits the loop via the Loop Cond operation. As an optimization, GraphGenerator unrolls the While operation if the loop node took the same number of iterations in the collected traces.
5 Evaluation
In this section, we evaluate Terra in the following two aspects:
Can Terra exploit symbolic execution from imperative DL programs that AutoGraph, the itatic-compilation-aneee aidoon--nnd-ttiiinn approach, cannot? ($...2
How much does Terra speed up imperative DL programs? 5.3
5.1 Implementation and Experiment Setup
Frameworks. We use TensorFlow 6 v2.4.1 as our baseline DL framework. We have built Terra on TensorFlow 12.4.1, and our approach is applicable to other DI. frameworks if they support both imperative and symbolic execution (e.g.. MXNet [1O] and PyToorch (32). More details about the implementation of Terra are described in Appendix C. All evaluated imperative DL programs are implemented with the imperative API of TensorFlow, which has become the standard interface since TensorFlow v2.0. We compare Terra with TensorFlow imperative execution and with Auto- Graph [29]. tote--of-the-art system that combines the static compilation approach with the single path tracing approach. We compile a single training step function each imperative DL program (i.e., @tf
True)).
Environments. We conduct all the experiments on a single machine that is equipped with 8-core AMD Ryzen 2700X 3.7GHz and an NVIDIA TITAN Xp GPU, We use Ubuntu 18.04, CUDA 11.0, cuDNN 8.0, and Python 3.8.8.
Imperative DL Programs. For the experiments, we use ten imperative DL programs collected
from open-source GitHub repositories: DropBlock [12), BERT-Q&A [3] Music'Transfie Tusseerrannformer (1],
SDPoint 22]. BERT-CLS (24), GPT2 34 DCGAN 37 ResNer50 38 FasterRCNN (44). and
YOLOv3
45
5.2 Imperative Program Coverage
Terra handles all the benchmark programs successfully with the imperative-symbolic co-execution. However, since AutoGraph does not support the entire set of Python features, it fails to execute five out of ten programs. Table shows why AutoGraph fails handle the programs and the detailed code snippets are described in Appendix D.

---

Artstrnghh AuseCough XIA
Tenn XIA
Tossosllew Inperotire Esccution
1.52-
3138
1:23
4.00
Relative
6:75
0.22
X
XXX PoletiON
X Male
0.80
VOLOND
DOGAN
GIT2
BERT
Dropitacs
5072m1
Program
Figure 5: The training speed-up results of Terra, AutoGraph, and when applying XLA 141 to both systems relative to TensorFlow imperative execution. The dotted line presents the training throughput of the imperative execution. Note that Terra and AutoGraph share the same upper bound of performance improvement from the symbolic execution of TensorFlow.
According the AutoGraph language document more failures could exist if an imperative DL program contains unsupported Python features such as the use of Python generator, try-except, and None type values. To resolve all the limitations in AutoGraph, new functions handle each failure should be implemented and it requires huge engineering effort. Terra simply avoids the conversion-related problems by the imperative-symbolic co-execution.
5.3 Training Throughput
Figureeppresent the training speed-up of Terra compared to TensorFlow imperative execution. For all programs, we measure the average training throughputs from 100 to 200 steps, and each experiment conducted ten times. Terra achieves higher performance than the imperative execution for every program. To estimate whether Terra fully achieves the optimized performance of symbolic execution, we also compare the performance Terra with AutoGraph, which shares the same graph executor of TensorFlow with Terra. AutoGraph closely follows the performance of the symbolic exccution because it totally replaces the imperative execution with the symbolic execution. For the five programs that AutoGraph can execute, the performance improvements of Terra are on with AutoGraph, which shows that Terra highly achieves the symbolic execution's 's optimized performance. Experiment settings such as batch size and the dataset are included in Appendix E.
Since Terra generates a symbolic graph and utilizes the symbolic execution, we evaluate the perfor- mance of Terra by applying XLA [41] as shown in Figure 5 Compared to the imperative execution, Terra improves the performance of seven programs by up to 1.73x when applying XLA. XLA not applicable to GPT2 and FasterRCNN due to the dynamic shape of the input data. For each training iteration, the shapes of input data the models can change. However, XLA cannot efficiently handle dynamic shapes because it assumes static shapes. For YOLOv3, we profile the execution and find that the current XLA fails efficiently cluster operations for YOLOv3. To be more specific, YOLOv3 includes some DL operations such as ResizeNeerrstNNeighbob and Where, which are not supported by XLA. Thus, XLA cannot efficiently fuse DL operations. In addition, we observe that Terra's performance decreases more than that of AutoGraph for YOLOv3 because the schedules of some Output Fetching operations are reordered because XLA kernels, causing a longer stall in PythonRunner. However, this problem can be addressed by extending XLA to support our custom operations.
We profilc the execution of both PythonRunner and GraphRunner to analyze the performance of Terra. We focus on the performance analysis in the co-execution phase because Terra's execution is mostly in this phase. The number of transitions between the two phases and the overhead analysis for the tracing phase are included in Appendix F. Figure the performance breakdown of the two Runners in single training step. PPythonRunner Exec denotes the Python interpreter's 's active running time, such as executing user code or validating the symbolic graph. Both 'PythonRunnes Stall' and "GraphRuna Rnner Stall' indicate the stall time in which the PythonRunner waits for the GraphRunner to fetch the materialized tensor or vice versa. Finally, we measure GPU's s active time to run the CUDA kernels along with the overhead of TensorFlow's graph executor as "GraphRunner Exec'. For all

---

Terra
Program
Terra
873
PyllasBuusee Bees
PyllanBuuseer Stal
GoaphBtsaer Esse GrgplBusser Stall
LazyEval
ResNet50
x1.25
x1.13
Time
BERT Q&A
x1.23
x0,94
DCGAN
x1.56
x1.34
VOL.w1
DOSAN
OPTT
HIST
Dreplick StPeed PoleRRtM Medko
Table 2: Comparison of the training speed-up between Terra and Terra with lazy evaluation. The results are relative speed-up TensorFlow imperative ex- ecution as Figure S
Program
Figure 6: Performance breakdown within single training step for both the Rynhon and the GraphRunner.
programs except for FasterRCNN, the GraphRunner is not stalled, implying that the GraphRunner fully exploits the optimized performance of the symbolic execution. In FasterRCNN, the stall of the GraphRunner occurs when the PythonRunner receives a materialized tensor from the GraphRunner and feeds it back the GraphRunner. For YOLOv3, the RythonRunner's execution time is longer than that of the GraphRunner, which yields the slightly larger performance gap between Terra and AutoGraph in Figure 5
Moreover, Figure shows that the Graph takes a longer time than the Rython in most cases. The result implies the reason why the performance improvements of Terra are comparable to the performance improvements concealed by the execution of the GraphRunner with the co-execution. To demonstrate the effect of the co-execution, we serialize the execution of the Python and the GraphRunner then evaluate the performance for the simple programs among our benchmarks. Within the serialized execution, the GraphRunner does not start the execution along with the PythonRunner. Instead, starts the execution when the PythonRunner requires tensor data through the Output Fetching operation. Eventually, the serialized execution is the same as the lazy evaluation that Lazy Tensor [36] does. Our results Table Sbble show that the lazy evaluation cannot fully achieve high performance of the symbolic execution. Even worse, it could become slower than the imperative execution when the execution time of the GraphRunner is not much longer than the execution time of the PythonRunner.
AutoGraph. The execution the PythonRunner efficiently
Conclusion
We propose Terra, novel approach to execute imperative Python DL programs. Terra performs imperative-symbolle co-execution, which addresses the problem of converting an imperative program symbolic graph completely. Terra generates symbolic graph only from the DL operations of an imperative DL program. It then carries out the imperative execution, simultaneously executing the symbolic graph. Therefore, Terra achieves optimized performance while maintaining all Python features of the imperative program. Our evaluation shows that Terra can speed all imperative DL programs, even for the programs that AutoGraph cannot handle.
Broader Impact
Our work aims to accelerate the execution of imperative DL programs while maintaining programma- bility. Our work is not associated with a specific application because our approach applicable for any imperative DL programs. Thus, believe work does not have significant impact any audience from either an ethical or societal perspective, at the application level.
Acknowledgements
We thank the reviewers for their valuable comments. We also thank Haeyoon Cho, ne-Won Chung, Jeongyoon Eo, Wonwook Song, Gyewon Lee, Soojeong Kim, Hokwen Joung, and Taegyun Kim for their constructive feedback. This work was partly supported by Google Research Award and Institute of Information & communications Technology Planning & Evaluation (ITTP) grant funded by the Korea government (MSIT) 1N0.2021-0-01143, Artificial Intelligence Graduate School Program (Scoul National University)).
10

---

References
Autograph Limitation Document.
r2. wwt.hh/t..ppppitoooooo//////aaaa
[2] Gluon. http://gluon.nnnel
torch.jit.trace. html
[4] TorchSeript. http:///pptttee.....oo///s/tt/tt
[5] TorchScript Language Reference. httppp///yoooo..oooo//oosssttttt Janguagge
reference.
referee
[6] Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Ghemawat, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: A System for Large-scale Machine Learning- In Proceedings of USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2016.
[7] Akshay Agrawal, Akshay Naresh Modi, Alexandre Passos, Allen Lavoie, Ashish Agarwal, Asim Shankar, Igor Ganichev, Josh Levenberg, Mingsheng Hong. Rajat Monga, and Shanqing Cai. TensorFlow Eager: Multi-Stage, Eemeeddd DSL for Machine Learning. In Proceedings of Conference on Systems and Machine Learning (SysML), 2019.
[8] Byung Hoon Ahn, Jinwon Lee, Jamie Menjay Lin, Hsin-Pai Cheng, Jilei Hou, and Hadi Esmaeilzadeh. Ordering Chaos: Memory-Aware Scheduling of Irregularly Wired Neural Networks for Edge Devices. In Proceedings of Conference on Machine Learning and Systems (MLSys), 2020.
[9] Lars Buitinek, Gilles Louppe, Mathicu Blondel, Fabian Pedregosa, Andreas Mueleer, Olivier Grisel, Vlad Niculae, Peter Prettenhofer, Alexandre Gramfort, Jaques Grobler, Robert Layton, Jake VanderPlas, Arnaud Joly, Brian Holt, and Gaël Varoquaux. API design for machine learning software: experiences from the scikit-learn project. In ECML PKDD Workshop: Languages for Data Mining and Machine Learning, pages 108-122, 2013.
[10] Tianqi Chen, Mu Li, Yutian Li, Min Lin, Naiyan Wang. Minjie Wang, Tianjun Xiao, Bing Xu, Chiyuan Zhang, and Zheng Zhang. MXNet: A Flexible and Efficient Machine Learning Library for Heteroggeneou Distributed Systems. In Workshop on Machine Learning Systems in NIPS, 2015.
[11] Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Haichen Shen, Meghan Cowan, Leyuan Wang, Yuwei Hu, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. TVM: An Automated End-to-Fnd Optimizing Compiler for Deep I Learning. In Proceedings of USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2018.
[12] DHZS. tf-dropblock. httppp//ggttub..oooo///////deeee
[13] Hugging Face. Transformers. http://www...............//o/ans http:///wuuuu..cooo/uuugggggggg/
[14] Facebook. Caffe2. httts://ccafe2..a
[15] Roy Frostig, Matthew James Johnson, and Chris Leary. Compiling Machine Learning Programs via High-Levve Tracing. In Proceedings of Conference on Systems and Machine Learning (SysMI.), 2018.
[16] Charles R. Harris, K. Jarrod Millman, Stéfan
der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor. Sebastian Berg, Nathaniel Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard Marchant, Kevin Sheppard, Tyler Reddy, Warren Weekesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Arry programming with numpy. Nature, 585(7825):357 362, 2020.
[17] Chienchin Huang, Gu Jin, and Jinyang Li. SwapAdvisor: Pushing Deep Learning Beyond the GPU Memory Limit via Smart Swapping. In Proceedings of ACM International Conference on Architectrral Support for Programming Languages and Operating Systems (ASPLOS), 2019.
[18] Paras Jain, Ajay Jain, Aniruddha Nrusimha, Amir Gholami, Pieter Abbeel, Joseph Gonzalez, Kurt Keutzer, and lon Stoica. Checkmate: Breaking the Memory Wall with Optimal Tensor Rematerialization. In Proceedings of Conference Machine Learning and Systems (MLSys), 2020.
11

---

[19] Eunji Jeong. Sungwoo Cho, Gyeong-In Yu, Joo Seong Jeong, Dong-Jin Shin, and Byung-Gon Chun. JANUS: Fast and Flexible Deep Learning via Symbolic Graph Execution of Imperative Programs. In Proceedings of USENIX Symposium on Networked Systems Design and Implementation (NSDI). 2019.
[20] Zhihao Jia, Oded Padon, James Thomas, Todd Warszawski, Matei Zaharia, and Alex Aiken. TASO: Optimizing Deep Learning Computation with Automatic Generation of Graph Substitutions. In Proceedings of ACM Symposium on Operating Systems Principles (SOSP), 2019.
[21]
Kevin- Yang.
httpa://githui. com/ cttp:/ccccccaca33.......
Mus i wwransoorrerrrrreerrerrrrrrreeer tew.orrooo..to......
[22] Jason Kuen. Stochastic Downsampling for Cost-Adjustable Inference and Improved Regularization in Convolutional Networks (SDPoint).
[23] Woosuk Kwon, Gycong-In Yu, Eunji Jeong, and Byung-Gon Chun. Nimble: Lightweight and Parallel GPU Task Scheduling for Deep Learning. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), 2020.
[24] kyzhoubzau. NLPGNN. https://giis http////....oo/yycccaauuu/u/u/ue
[25] Yizhi Liu, Yao Wang. Ruofei Yu. Mu Li. Vin Sharma, and Yida Wang. Optimizing CNN Model Inference on CPUs. In Proceedings of USENIX Annual Technical Conference (ATC), 2019.
[26] Lingxiao Ma, Zhiqiang Xie, Zhi Yang. Jilong Xue, Youshan Miao, Wei Cui, Wenxiang Hu, Fan Yang. Lintao Zhang, and Lidong Zhou. Rammer: Enabling Holistic Deep Learning Compiler Optimizations with rTasks. In Proceedings of USENIX Symposiun on Operating Systems Design and Implementation (OSDI), 2020.
[27] Azalia Mirhoseini, Anna Goldie, Hieu Pham, Benoit Steiner. Quoe V. Le, and Jeff Dean. A Hierarchical Model for Device Placement. In Proceedings of International Conference on Learning Representations (ICLR), 2018.
[28] Azalia Mirhoseini, Hieu Pham, Quoe V. Le, Benoit Steiner, Rasmus Larsen, Yuefeng Zhou, Naveen Kumar, Mohammad Norouzi. Samy Bengio, and Jeff Dean. Device Placement Optimization with Reinforcement Learning. In Proceedings of International Conference Machine Learning (ICML), 2017.
[29] Dan Moldovan, James M. Decker, Fei Wang, Andrew A. Johnson, Brian K. Lee. Zachary Nado, D. Sculley, Tiark Rompf, and Alexander B. Wiltschko. AutoGraph: Imperative-style Coding with Graph-based Performance. In Proceedings of Conference on Systems and Machine Learning (SysML), 2019.
[30] Graham Neubig, Chris Dyer. Yoav Goldberg, Austin Matthews, Waleed Ammar, Antonios Anastasopoulos, Miguel Ballesteros, David Chiang. Daniel Clothiaux, Trevor Cohn, Kevin Duh, Manaal Faruqui, Cynthia Gan, Dan Garrette, Yangfeng Ji, Lingpeng Kong, Adhiguna Kuncoro, Gaurav Kumar, Chaitanya Malaviya, Paul Michel, Yusuke Oda, Matthew Richardson, Naomi Saphra, Swahha Swayamdipta, and Pengcheng Yin. DyNet: The Dynamic Neural Network Toolkit. orXiv preprint arXiv: 1701.03980, 2017.
[31] NVIDIA, NVIDIA TensorRT: Programmable Inference Accelcrator. https: cwtpeerrrviiidi nvidia
com/t tenntensorrt
[32] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, High-Performance Deep learning Library. In Proceedings of Advances in Neural Information Processing Systems (NewrIPS),001) 2019.
[33] Python Software Foundation. Pep 634: Structural pattern matching, hctps://docs http://doc.....tttt.co www.ssyyhhhhhh...o.eee hon. /rg/
3. www./waattee////t 10. htm
[34] Abhay Singh. gpt-2-tenxorflow2.00
[35] Muthian Sivathanu, Tapan Chugh, Sanjay Singapuram, and Lidong Zhou. Astra: Exploiting Predictability to Optimize Deep Learning. In Proceedings of ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2019.
[36] Alex Suhan, Davide Libenzi, Ailing Zhang, Parker Schuh, Brennan Saeta, Jie Young Sohn, and Denys Shabalin. Lazytensor: combining eager execution with domain compilers. 1326, 2021.
12

---

[37] TensorFlow.
Deep Convolutional Generative Adversarial Network Tutorial.
https: /ww www
tensorflow http:////.......a///////a//////.
[38]
TensorFlow. TensorFlow Model Garden. http:///gttt....c////osorrroro.t
[39]
TensorFlow.
tf.function.
Function
[40]
TensorFlow. TFRT: A New TensorFlow Runtime, httpa/////gggaaaaooooo////oooooa
[41]
TensorFlow. XLA: Optimizing Compiler for TensorFlow. httper//www.tnnnoffloooor/..../
[42]
Theano Development Team. Theano: Python framework for computation of mathematical expres-
sions. arXiv preprint arXiv: 1605.02688, 2016.
[43] Seiya Tokui, Ryosuke Okuta, Takuya Akiba, Yusuke Niitani, Toru Ogawa, Shunta Saito. Shuji Suzuki, Kota Uenishi, Brian Vogel, and Hiroyuki Yamazaki Vincent. Chainer: A Deep Learning Framework for Accelerating the Research Cycle. In Proceedings of ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2019.
[44] Viredery, fasteren-
[45] Zihao Zhang, http:///ht.a.a..........////////
[46] Zhao, Bojie Li, Wang Nie, Zhen Geng, Renwei Zhang. Xiong Gao, Bin Cheng, Chen Wu, Yun Cheng, Zheng Li, Peng Di, Kun Zhang, and Xuefeng Jin. AKG: Automatic Kernel Generation for Neural Processing Units using Polyhedral Transformations. In Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2021.
[47] Zhen Zheng, Pengzhan Zhao, Guoping Long, Feiwen Zhu, Wenyi Zhao Kai Zhu, Lansong Diao, Jun Yang. and Wei Lin. FusionStitching: Boosting Memory Intensive Computations for Deep Learning Workloads. arXiv preprint arXiv: 2009. 10924, 2020.
[48] Yanqi Zhou, Sudip Roy. Amirali Abdolrashidi, Daniel Wong, Peter Ma. Qiumin Xu, Hanxiao Liu, Mangpo Phitchaya Phothilimtha, Shen Wang, Anna Goldie, Azalia Mirhoseini, and James Laudon. Trans- ferable Graph Optimizers for MI. Compilers, Proceedings of Advances Neural Information Processing Systems (NewrIPS), 2020.
13


Reviews:
[{"review_id": "w5F3YsnEw94", "reviewer": "Reviewer_JQgH", "summary": "This paper proposes a combined approach based on both imperative and symbolic co-execution  of a program that can handle any imperative Deep Learning program while achieving the performance of symbolic graph execution. They evaluated on real-world models for imagenet and demonstrate their improvement.  ", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Originality: \n- In the context of DL program context, combinations of automatically building the symbolic graph from program traces seems new and interesting. I actually learned a lot from the paper.\n\nQuality: \n- The lazy construction of the graph makes sense in this context.\n- The evaluation is solid on 10 large models and the gain is significant. \n- The only problem is there is no formal argument of the correctness of the approach. However, it intuitively makes sense. \n- Authors also should consider providing ablation studies showing how much time is required to build the graph.\n\nClarity:  Well written paper.\n\nSignificance: This kind of optimization has the potential to significantly improve the DL models. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "jzLQRm740Xw", "reviewer": "Reviewer_FiWe", "summary": "This work proposes an approach for achieving optimized performance of symbolic graph execution for any imperative DL program. The approach is implemented in a system called Terra. The proposed approach involves decoupling symbolic operations and building a symbolic graph. The skeleton python program is executed using the Python interpreter whereas the symbolic operations are delegated to the optimized symbolic execution. Terra is evaluated on ten imperative DL programs and the performance is compared with AutoGraph. Terra can successfully execute all the ten programs whereas AutoGraph fails to execute five of them. The speed up achieved by Terra is comparable to AutoGraph. The main appeal of the method is that it does not have any Python feature coverage limitations. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "### Originality: \nThe work tries to combine the \"imperative execution\" and \"symbolic execution\" paradigms to get the best of both worlds. Instead of trying to convert the whole program to a symbolic graph, it just decouples the symbolic operations into a symbolic graph. The control flow is governed by the skeleton Python program executed in an imperative way whereas the symbolic graph is executed by a Symbolic Runner. Although the idea of speculative generation of symbolic graphs has been explored in earlier works, the idea of co-execution is novel. Co-execution is crucial for ensuring support for all the host language features.\n\n### Quality: \n\nThe paper is technically sound.\n\n* The work has done a good job of carefully designing the constructs for communicating data and managing control flow across the two runners. \n* The proof that the graph generation algorithm can handle any DAG is described in the supplementary material.\n* To support the claim that Terra performs comparably with Autograph on the programs on which AutoGraph works, it would be preferable to see the numbers on the benchmarks from the AutoGraph paper. The rationale for selecting the 10 programs is not discussed. It would be nice if the authors could discuss different dimensions they tried to cover( architectures, type of input data, etc.)\n* The paper compares Terra with a single competing method(AutoGraph). I would have liked to see comparisons with other methods from the \"single path tracing\" and \"static compilation paradigms\".\n\n\n### Clarity\nThe paper is well written and easier to follow along. \n\nSome minor issues.\n* I do not understand when \"GraphGenerator\" stops collecting the traces (line 190). A little elaboration would be helpful.\n* When Terra cancels the execution of the GraphRunner and falls back to the tracing phase (line 212), is the computation done so far lost?\n* In section 4.2 (TraceGraph), in almost all the sentences, the word \"GraphGenerator\" is repeated. \"GraphGenerator attempts ...\", \"GraphGenerator compares...\", etc. Since the whole section is about GraphGenerator, I found the repeated usage a bit distracting. It is a style issue; authors may want to improve it.\n* Spelling mistake. Line 307. \"publicy\" and \"opended\"\n* Line 190, \"lastest\"\n\n### Significance\n\nThe paper is trying to address a very important problem. The main appeal of the \"define-by-run\" imperative programs is the flexibility. The prevalent approaches which try to optimize the performance of imperative programs end up putting restrictions on the program features that can be used. Terra's approach of co-execution allows it to support all the host language features without sacrificing the performance. This paper will inspire more work in this direction. \n\nAlthough this is not discussed in the paper, I believe that since the control flow is governed by the python interpreter, this approach will have better debuggability than the approaches that try to convert the whole program to a symbolic graph.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I believe that more discussion is needed on limitations or possible pain points of the proposed approach. For example, one can ask:\n- Does the method put any limitations on the kind of graphs that can be generated? Does it miss out on certain optimization opportunities due to the nature of the graph generation.\n- Are there use cases where AutoGraph will perform significantly better than Terra?\n- For the programs where AutoGraph works, does it make sense to use Terra considering that the performance on Terra would be slightly worse than AutoGraph?\n- Does the way the program is implemented have any impact on the performance of Terra? (Possibly due to excessive switching between the two running modes.)\n\nThe answers to these questions will either bolster the claims or warn the readers about possible limitations.\n\nI do not believe that there is any potential negative societal impact of the work.", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "LMkGHHj2E84", "reviewer": "Reviewer_UnHn", "summary": "The paper describes a framework based on imperative symbolic co-execution to execute deep learning programs. The main idea is to build a symbolic trace of DL operators while executing imperatively until the current iteration's trace is fully captured in its trace graph. At this point the imperative code and the symbolic code is run asynchronously with necessary communication inserted to guarantee correctness. The results show improved performance compared to AutoGraph (a one time trace only system).", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "# Strengths\n\n* The system uses the concept of trace graph to gradually build a symbolic graph of multiple traces. These ideas are exploited in the JIT compilation and dynamic binary instrumentation field (Code Caches) and it is commendable it is being utilized in the context of a DL framework.\n* Comparison against other tracing imperative systems such as Autograph\n\n# Weaknesses\n\n* The authors completely overlook statically compiled DL backends such as XLA or TVM. These build symbolic data flow graphs and statically compile them to machine code and exploits better optimizations compared to TensorRT and other runtimes. The authors do not compare the performance of their system against such compiled approaches, which is a significant omission. In Tensorflow, you can easily invoke the XLA compiler by using tf.function regions.\n* Related work missing on compiled approaches such as XLA or TVM. Please add them. XLA is only mentioned as a citation for operator fusion, but in fact is a fully featured compiler that does many other optimizations.\n* Evaluation mentions it outperforms AutoGraph by upto 1.61x. A breakdown of results per benchmark would give a wholistic picture to appreciate this result in full. It's surprising why a graph is not included for this result.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I have listed the technical limitations in the above section. I do not see any major negative societal impact arising from this work.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not see any major ethical concern arising from this work.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "6Si6jYOiQoJ", "reviewer": "Reviewer_4LTS", "summary": "This paper proposes a method for obtaining a symbolic (graph) representation of a model, given the imperative Python code. It distinguishes itself from (most) other methods by co-executing the symbolic as well as the imperative representation, as well as merging multiple traces into a single symbolic representation. This allows it to obtain arbitrary representations of \n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Overall, I think this paper tackles a very relevant problem, and some parts of the approach are novel (to my knowledge) and quite interesting. Before I talk about this paper's strengths, I want to note some very related work that this paper should definitely have compared to. Specifically, that it is the LazyTensor approach (https://arxiv.org/abs/2102.13267), which does something similar, in that it builds up a symbolic graph while executing, and will recompile if that symbolic graph doesn't match. In this way, LazyTensor is also able to guarantee that it executes all code correctly.\n\nBack to this paper, I am fairly impressed with the built system as well as the approach. AFAIK, I haven't seen this kind of \"trace out program and merge traces into a single graph\" approach before. Their results show that their approach is successful on a wide variety of models, including some models with a significant amount of dynamism. \n\nMy primary concern with this approach is quite complicated, and the co-execution of the symbolic and the imperative models seems to me to impair debuggability and UX. This isn't a fatal flaw by any means - if it can execute user code reliably enough then this isn't a problem - but is something to keep in mind with these kinds of approaches.\n\nAnother question I had was how the symbolic graph was actually being executed. In TF/PyTorch, one of the primary reasons to create a symbolic graph is to pass it to a compiler like XLA. However, it seems to me like this co-execution structure/python fallbacks in order to resolve control flow may 1. not allow you to use such compilers, 2. inhibit possible optimizations. Could you clarify whether this understanding is correct and whether the baseline AutoGraph was then lowered to XLA?\n\nOverall, I find the approach interesting + think it tackles an important problem. However, I think lack of proper comparison to relevant work are somewhat problematic.\n\n\nEDIT: Primarily based off of the new results presented with XLA, as well as the preliminary LazyTensor comparisons, I have raised my score from 5 to 7.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers appreciated the novel techniques presented in the paper for co-executing the symbolic and imperative representations of a model program. During discussions, one major concern that came up was regarding experimental evaluation and comparisons to other related approaches. The additional experiments of applying XLA to Terra, and comparison with LazyTensor emulation helped clarify some of the advantages of Terra's approach and the corresponding benefits. It would be great if authors can incorporate the detailed feedback from reviews, the additional experiments and results, as well as discussions about limitations and clarifications from the author response in the final version of the paper. 
Decision: Accept (Poster)