DynaTune: Dynamic Tensor Program Optimization in Deep Neural Network Compilation
Authors: Minjia Zhang
Menghao Li
Chi Wang
Mingqin Li
Venue: ICLR 2021 Poster (2021)
Keywords: Efficient Deep Learning Inference
Scalability
Code Compilation
Bayesian Inference

Abstract: Recently, the DL compiler, together with Learning to Compile has proven to be a powerful technique for optimizing deep learning models. However, existing methods focus on accelerating the convergence speed of the individual tensor operator rather than the convergence speed of the entire model, which results in long optimization time to obtain a desired latency.

In this paper, we present a new method called DynaTune, which provides significantly faster convergence speed to optimize a DNN model. In particular, we consider a Multi-Armed Bandit (MAB) model for the tensor program optimization problem. We use UCB to handle the decision-making of time-slot-based optimization, and we devise a Bayesian belief model that allows predicting the potential performance gain of each operator with uncertainty quantification, which guides the optimization process. We evaluate and compare DynaTune with the state-of-the-art DL compiler. The experiment results show that DynaTune is 1.2--2.4 times faster to achieve the same optimization quality for a range of models across different hardware architectures. 

Published as a conference paper at ICLR 2021
DYNATUNE: DYNAMIC TENSOR PROGRAM OPTI- MIZATION IN DEEP NEURAL NETWORK COMPILATION
Minjia Zhang, Menghao Li*, Chi Wang & Minggin Li Microsoft Corporation
(minjiaze t-meli, wang chi, mi ngql i @mi crosoft.com
ABSTRACT
Recently, the DL compiler, together with Learning to Compile has proven to be a powerful technique for optimizing deep learning models. However, existing meth- ods focus on accelerating the convergence speed of the individual tensor operator rather than the convergence speed of the entire model, which results in long opti- mization time to obtain desired latency. In this paper, we present new method called DynaTune, which provides significantly faster convergence speed to op- timize DNN model. In particular, we consider Multi-Armed Bandit (MAB) model for the tensor program optimization problem. We use UCB to handle the docision-making of time-slot-based optimization, and we devise Bayesian belief model that allows predicting the potential performance gain of each operator with uncertainty quantification, which guides the optimization process. We evaluate and compare DynaTune with the sfate-of-the-art DL compiler. The experiment re- sults show that Dyna' is 1.2-2.4 times faster to achieve the same optimization quality for a range of models across different hardware architectures.
INTRODUCTION
The enormous computational intensity of Deep Neural Network (DNN) models has attracted great interest in optimizing their performance. Popular deep learning (DL) frameworks such as Py- Torch (Paszke et al., 2019) and TensorFlow (Abadi et al., 2016) adopt custom optimized kernels such Intel MKL-DNN or Nvidia cuDNN (Chetlur al., 2014) back-end. However, given the increasing complexity of tensor operations in DNNs and the volatility of DL. algorithms, calls for developing fast and automated compilation frameworks handle the unprecedented amount of innovations. To imitate or even exceed the success of hand-optimized libraries, recent research has developed neural network compilers, such as XLA (Leary Wang, 2017), Glow (Rotem al., 2018), Tensor Comprehension (Vasilache et al., 2018), 8), and TVM (Chen et al., 8a). Among them, TVM has shown superior performance improvements using technique called Learning Compile (VutoTVM) (Chen et al., 2018b). AutoTVV optimizes the code by generating many versions of tensor operator and chooses the best through a learned cost model and search over a large space of code transformation choices.
While the Learning to Compile approach produces highly optimized code of DNN models, it suffers from excessively long optimization time. As example, although Aut is able to demonstrate close to 2x performance improvement over TensorFlow on ResNet-18, the optimization time can take several hours the turnaround time and even puts the practical utility of the current compiler- basee solutions into question. Recent works strive reduce the optimization time by improving the search strategy for the code transformation plan and lowering the hardware measurement cost (Ahn et al., 2020; Adams al., 2019). However, these approaches mostly focus on accelerating the convergence speed of optimization at the individual tensor operator level (c.g., Conv2D, batched GEMM), which do not necessarily solve the issue of slow convergence and long optimization time of the entire model, often containing tens of tensor operators.
tens of hours (Chen al., 2018b). The long optimization time hinders
Different from existing methods, we introduce DynaTune, DL code optimization algorithm that minimizes the sum of the execution time of all operators in model as much as possible and as
Both authors contributed equally. Order of appearance random.

---

Published as a conference paper at ICLR 2021
quickly possible. Specifically, the contributions of paper consist of (1) preliminary anal- ysis that reveals the challenges and opportunities from existing DL code optimization strategies, (2) a time-slot-based optimization scheme, which simultancously explores different operators and learns in an online manner that allows to dynamically switch to optimizing more promising tensors operators. (3) Bayesian belief model that predicts future performance gains of operators, which helps make better decisions and expedites the convergence speed. (4) detailed evaluation of the proposed algorithm with modern DNNs (ResNet-18, VGG, SqueezeNet, Transformer) on both CPU and GPU. Compared with the leading framework, AutoTVM, DynaTune is 1.2-2.4x times faster to obtain the same levels of optimization.
2 BACKGROUND
DL compilation pipeline. A typical DL compiler contains multiple passes to optimize model trained by popular DL frameworks such as TensorFlow (Abadi et al., 2016), PyTorch (Paszke et al., 2019), or MXNET (Chen et al., 2015), as shown in Fig. 1. In the first pass (box with dotted line), the compiler frontend applies buget-independent and white-box turget-dependent optimizations that do not include measure of actual execution time. The uugettinddeennent passes perform optimiza- tions such as operator fusion and data layout transformation, and the white-box target-dependent optimizations apply heuristic rules for code transformation based domain knowledge. Recent work such as Au (Chen et al., 8b) extends the pipeline with another pass, a black-box target-dependent pass, which uses learning machinery to perform optimizations.
PyTorch mxnet DRKX
Target-independent
Learning to Compile
Passes
Tvt
opt_conv2D
High-level DNN Description
Dagge--eepndent
conv2D
DynaTune
Passes
Code Transformation
Hardware mecsurement
Frontend
Figure Compilation pipeline.
Black-box target-dependent pass. In this pass, the compiler converts code transformation deci- sions as code templates. template contains knobs that control various aspects of the optimization (e.g., memory tiling, loop transformations. vectorization) and determines whether the code (1) fully utilizes the internal parallelism within processors, (2) uses the shared memory wisely, and (3) max- imizes data locality. Due to the large transformation space, the compiler makes use of an auto-tuner (with an optimization algorithm) and real hardware measurements to find the best transformation on target hardware (e.g.. CPU, GPU, ARM, or IoT devices) (Chen et al., 2018b).
3 CHALLENGES AND MOTIVATIONS
This section presents several studies that reveal the challenges of existing DL compilation that guided our design in Section 4.
Challenge 1. Existing DL compilation focuses on accelerating the convergence speed of in- dividual tensor operator instead of the entire model, resulting in slow convergence and long optimization time. Prior work (Chen et al., 2018a;b; Vasilache et al., 2018; Ahn et al., 2020) opti- mizes one tensor operator
time in predefined order (e.g., in declaration order). However, such an optimization strategy is not always appropriate in practice. For example, there is often an extreme performance difference (c.g., an order of magnitude) between optimized and unoptimized operators. If we optimize operators sequentially, the overall model inference time stays high as long as there are still unoptimized operators. have finished optimization to get the desired latency, which results in long optimization time. With the active research that has been pushing the model size to millions or even billion-scale parameters with a training time of only a few hours or less than one hour (Yamazaki et al., 2019; Goyal et al., 2017: You et al., 2017; 7; Lin et al., 2019; Shocybi et al., 2019; You et al., 2019), it becomes even more prominent to reduce the inference optimization cost of the current solution. Furthermore, since ma- jor players the industry have adopted many of these DL compilers (Wu et al., 201 2019a;b; Lattner al., 2020; Liu et al., 2019), fast convergence is desirable for many users of these pipelines have
result, practitioners may need wait until all tensor operators
2

---

Published as a conference paper at ICLR 2021
Optimization CentiNi
23
Optimization nCS)
10%
6000
21 GPLOPS
5320
FLOPS (1e9)
2%
GFLOPS
4320
3.5
6%
3220
2200
1000
bile
blee Jc
68
200
450
035
1001
1900 1486
lasks
Iterations
Figure Inproportional optimiza-
Figure
DL
optimization
Figure 3: space.
Code
transformation curves.
tion gain/cost.
better control of the optimization cost and good performance. For example, deployment engineers may want to obtain an optimized model sooner or quickly get a latency upper-bound estimate of model in development.
Challenge 2. Static scheduling has only a limited view of the tensor program and has difficulty taking advantage of the actual optimization behavior. We note that from execution point of view, the optimization of tensor operators is independent of each other, so that we may optimize them in any order and even non-consecutively. As result, dynamic optimization has big advantage for iterative DL. compilation: We can intelligently order the optimization sequence of operators (i.e., scheduling) to accelerate the convergence of the optimization significantly. For example, it would be better to switch to optimizing another operator if we convincingly identify that the other operator has higher potential. That being said, is it realistic to assume that all the information concerning optimizing the operators is available before the optimization even starts so that we can decide the schedule from the very beginning? Our preliminary analysis indicates that the amount of computation of an operator (known priori) has a very disproportionate impact on the optimization time and latency reduction. Fig. shows that although operator 17 of VGG (Simonyan & Zisserman, 2015) takes the longest time to optimize, it yields the least amount of latency reduction's Our further investigation shows that the underlying code transformation space is non-linear, as shown in Fig. 3 As result, the optimization behavior tends to change over time, which is hard to recognize and predict with static knowledge only.
Challenge 3. Even with dynamic information, it is not clear how to best extrapolate esti- mated performance. Given the optimization results, there is an incentive to adopt a "predict-then= optimize" paradigm that builds model to learn the correlation between the optimization cost and the observed optimization performance the model can be used to make predictions for potential per- formance gains. To identify the characteristics of the optimization behavior, we plot 16 optimization curves of best-found GFLOPS (Giga Floating Point Operations Per Second) in Fig. 4 to find patterns that can be used for designing prediction model. We find that most curves (1) roughly follow an increasing curve with diminishing return, (2) saturate towards an unknown final value, and (3) oc- casionally exhibit sudden jumps. The curve saturates an unknown value because the performance cannot exceed the hardware peak GFLOPSS, which is 9.7-TFL.OPS in our case. The curve has sudden jumps because the code transformation space has change points, as shown in Fig. By taking into account the curve information, we believe it has more opportunity to dynamically optimize operators that likely lead to greater performance improvements.
'The orange bar shows the of computation of each operator measured as the floating-point oper- ations (FLOPs), which can calculated statically before the optimization starts, as described in Molchanoy et al. (2017). The "optimization gain") is calculated as the reduction of wall-clock time from each operator after optimization. and the "optimization cost" is calculated the wall-clock time spent to obtain the optimized latency. both of which normalized by the total latency reduction and optimization time.
"The tigure shows the code transformation space of a Conv2D operator in ResNet-18. In this case, the performance of this operator varies based on the tiling size along the input channel and output channel while having other knobs fixed. The knohs control various aspects of the optimization and its performance. A summary of the knobs can he found in Ahn al. (2020).
3

---

Published as a conference paper at ICLR 2021
4 METHOD
In this section, we present our design for DunaTune. We illustrate the difference between the existing DL optimization (Fig. 5) and the high-level design of DynaTune (Fig. 6).
Opo
0p2
Figure 5: Conventional DL optimization sequence.
Operator
Opt
Scheduler
vellst
Onz
Observation
predictioo
Bayesian
Bellief Model
Figure 6: DunaTune execution with dynamic optimization and Bayesian belief model.
4.1 DYNAMIC TEI-----ESORRRREEEEE OPTIMIZATION PROBLEM
In this paper, take view of accelerating the convergence speed of multi-tensso-opperator opti- mization by first considering a Pallt- Bandits model for the problem. In particular, we par- tition time into some fixed-lengti time slots {1, ..., Similar MAB, define operator scheduler that operates in discrete time steps. At the beginning of any time slot E {1, V.....,,, T). the scheduler needs to choose operator h; E [K] for tuning in that slot. The scheduler then obtains list observations (i.e., best-found performance measured in GFLOPS) Perfx(t T, (t+ +++17 1) T&)) of k. where La the number of iterations an operator has been optimized. The remaining unchosen operators stay the same unless it is selected (i.e., rested arms).
op(k) The latency reduction for k at time slot t is rka) Perfalt-Lu fe where op(k) represents the number of floating point operations of k. We further define optimal schedule,i.e.. n ( ki. k.. where k is the operator at step one could have taken in hindsight (after seeing all performance realizations) that would yield the maximum latency reduction. The cumu- lative regret is then defined as: R(T) = Σ (rr(k) rr (ke)), where kü is the operator at step t one could have taken in hindsight (after seeing all performance realizations) that would yield the maximum latency reduction. The goal therefore to design the scheduler, such that the cumulative regret is minimized. We call this dynamic coalii-tennor-opertoorr optimization problem.
op(k)
4.2 TIME-SLOT-BASED SCHEDULING
To select which operator to optimize in a time slot, we consider deterministic selection policies that belong to the class of index-based MAB policies (Gittins et al., 2011). Among many options, we choose upper confidence bound (UCB) as our action function to represent the exploration and exploitation tradeoff (Auer al., 2002). In particular, assume [e]kk be the number of times that operator & E [K] has been selected for optimization up to slot l. If ot-11 [b] >> O, we denote yn (I) to be the estimated performance of operator l: at the end of l. The UCB for operator k at is defined op(k) cc-1 AJ Perfa[[f-I)-Aa
un (t) Tx (t) + C Ing
op(k)
cC log,t for q-ilk] 0
ce-1[K]
and (1) = 7 (constant) for c-- [k] 0. The scheduler then computes UCB for each operator and selects the next one that maximizes UCB.
Our definition of UCB measures the potential latency reduction from operator & compared to other operators' expected performances. The first term is point estimate of the future latency re- duction 3, converted from GFLOPS improvement. The second term is related to the size (according to Chernoff-Hoeffihe lows the true expected performance falls within with overwhelming probability. In the evaluation section, we evaluate several other action functions, including e-greedy and softmax sampling. We
bounds (Hoeffding, 1994)) of the one-sided confidence interval, which al-
'In practice, an operator may appear multiple times in a network. Depending on the implementation, the compiler may reuse the same transformation plan for operators that have the same shape. In that situation, multiply the point estimate of the future latency reduction in the reward function with weight factor that represents the times of the corresponding operator that appears in the network.

---

Published as a conference paper at ICLR 2021
observe that these methods, in general, offer very similar performance. We choose UCB since some recent theoretical studies show that the growth rate of the regret from UCB sublinear and long-run oon-rrum average optimal in the non-stationary bandit setting (Cortes et al., 2017).
4.3 BAYESIAN BELIEF MODELS FOR EXPECTED PERFORMANCE IMPROVEMENTS
To obtain an optimal solution, ki requires perfect information, hence infeasible achieve in prac- tice. Since we identify some patterns (in Sec. 3) that indicate that there is functional relationship between the expected performance and the already observed performance, we propose a Bayesian belief model (t), enabled by Markov Chain Monte Carlo (MCMC), to capture our current knowl- edge of the optimization results predict future performance and get updated as new observations become available. In particular, we choose parametric curve models whose shape coincides with our knowledge about the form of optimization curves: increasing, saturating functions such as those from the power-law (pow2. pow4, log power) or the logarithmic familyy (loglinear, logloglinear). Among these functions, we choose log power function as it works well in our case.
To handle breakpoints as mentioned in Sec. 3, we employ a piece-wise parameterization to improve the approximation to the shape the underlying relationship: since the abrupt jumps often happen observation into segments if a jump leads more than relative A% (i.e.,
just few times, 20% higher GFL.OPS) improvement and model segments with different curve parameters.
Algorithm
DynaTune: Dynamic Multi Multi-Teensr--Operaatee Optimization
Input: A model & with a list of [K] = {I.....K] operators
2: Output: An optimized model o"
3: Init: c= (0, O.....O)
4: for t= 1....TT do
5: for I do
6: Observe history performance of operator is and predict future performance using the belief model in Section 4.3
7:
Update the UCB value (t) using the equation in Section 4.2
8:
kis 4 arg max un
9:
Allocate time slot L to k, for actual optimization
10:
c[k] < c[k] +1
11:
if f.finsshed then
12:
Exclude 1: from [K]
13:
Collect new data observed GFLOPS from optimizing and update the belief model
Data normalization. Before feeding the observations to the model, since the observed GFLOPS of different operators has different ranges, we normalize the GFLOPPS of all operators to a com- mon scale. Given that the maximum GFLOPS of any operator is bounded by the theoretical peak performance
the target deployment hardware (e.g.. 9.3TTeraFLOPS GPU), we apply the following formula to normalize observation x as follows: Normalized r = x/ (aakkttarge.harduuuek headwarrd which transfers the observation's values to new range 0 to 1. We convert the normalized r back to GFLOPS when calculating UCB.
Nvidia P100
Modeling uncertainty. Since goal aims at allocating time optimize tensor operators that are highly likely to bring performance improvement, we need to model uncertainty as truthfully as possible. To model uncertainty, we perform MCMC sampling from the posterior p(0x) Per fa t Lx)) x O(PerfxlL : t- Lu] Lx](O))p(On) of model parameters 0g of the curve function fa(() given the observed performance Per LR]. A sample approximation for Perfull with t' >> can then be formed as
[MPe] Per : I&]] R (t((
(1)
Among many options to do MCMC sampling, we choose Goodman & Weare's Affine Invariant MCMC Ensemble sampler (Goodman & Weare, 2010), which significantly outperforms standard M-H methods and produces independent samples (which takes O(N) likelihood evaluations) with much shorter autocorrelation time. We initialize the ensemble samplers in tight N-dimensional Gaussian ball in parameter space around the maximum likelihood result, which obtained through non-linear least-squares fit. We set uniform prior for 0 and make the prediction is non-
5

---

Published as a conference paper at ICLR 2021
decreasing, i.e., the predicted performance is not worse than the more recently observed best-found performance, by also explicitly encoding this knowledge into the prior. We obtain the predictive mean rl and standard deviation of the posterior parameter distribution using 200 MCMC samples. We then compute the expected positive improvement EI (Brochu et al., 2010) over the best known measured performance, while taking into account the possible uncertainty in that prediction.
5 EVALUATION
In this section, evaluate DynaTune experimentally, seeking answers to how DynaTune helps accelerate the convergence of optimizing all operators a model. We integrate DynaTune with AutoTVM (Chen et al., 2018b) and use as AutoTTV our baseline for comparison. We implement DynaTune in Python, and we leverage emcee (Foreman-Mackeyy et al., 2013) to implement the MCMC sampling. We do a warmup to find the first non-zero GFLOPS as starting point for all operators. We use the default hyperparameters provided by AutoTVM for the underlying code optimization. To obtain the parameter posterior, we run the ensemble MCMC with 10 walkers and 500 sampling steps. A convergence diagnostics of MCMC is presented in Appendix B. All the free parameters in the curve model are taken care of by MCMC sampling. For UCB, we choose a default value of C' 2 suggested by the theory in Auer et al. (2002), which we find to be robust to different range of latencies. When the initial latency is < Ims, we empirically find that C=0.2 leads to increased performance, which report. We perform 5 independent runs of each configuration with different random seeds and report the median together with a 95% confidence interval.
5.1 COMPARISON AUTOTVM AND DYNATUNE FOR OPTIMIZING MODELS WITH MULTIPLE TENSOR OPERATORS
In the previous approach (Chen et al., 2018b), authors optimize one operator at a time until all op- erators in a model have been optimized. We compare the performance of AuM and DynaTune on how much optimization speedup we obtain as a function of the wall-clock time. Due to space limitations, we include four tasks, covering both CPU and GPU hardware: ResNet-18 18 (He et al., 2016) and SqueezeNet (landola et al., 2016) on CPU (Intel Xeon CPU E5-2690 v3 @ 2.60GHz 2600 MHz), VGG (Simonyan & Zisserman, 2015) Transformer Encoder (landola al., 2016) on GPUs (Nvidia Tesla P100), which have K = 12, 18, 18, and tunable operators, respectively.
AutoTVM
Nes-eb-28
Squarsattet
VGG
Taandomer
50
432
30
230
10
8333
$2330
B053
1000 2007 <EC0 5000 SAAAI 7002
10000 2000 2000 93823 S0EGE SCEEO Time
2010
0233
costis)
Time
Time
Figure 7: Comparison of the convergence speed and quality among DynaTune, AutoTVM, and Oracle on both CPU and GPUs.
Fig. 7 visualizes the results. The x-axis denotes the wall-clock time of optimizing the model. The y-axis denotes the lowest model latency obtained as time moves on. Overall, the observation is that Dyna'Tune's 's dynamic optimization converges significantly faster than the baseline most of the time and is 1.2-2.4 times faster than the baseline to achieve the lowest latency. The baseline has much slower convergence, because it tries to find optimal transformation plan for one operator before starting optimizing another one. Since there can be an order of magnitude difference between the optimized and unoptimized code, the model latency remains high until the last operator has been optimized. In contrast, DynaTunne able to expedite the optimization significantly by reordering the optimization sequence of operators and dynamically pick promising operators to optimize. As result, Tune obtains the same optimization quality as the baseline but a much faster speed. Furthermore, we also plot the optimization by assuming having access to the oracle information. For ResNet- 18 and VGG, DynaTTuee gets optimization results close to the oracle. For SqueezeNet and Transformer, DynaTune converges slower than the oracle in the beginning but quickly catches up around one third of the optimization time, presumably because it is more difficult for the Bayesian model to predict performance in the beginning then later, indicating room for improvement. These

---

Published as a conference paper at ICLR 2021
results confirm that dynamic approach like DynaTune is capable of performing model-level code optimization in a much more efficient way than the existing approach.
5.2 COMPARISON OF DYNATUNE WITH STATIC SCHEDULES
In this section, we compare the effectiveness DynaTune with static allocation schemes. In par- ticular, we compare with three mechanisms: (1) Random, which randomly assign time slots to operators, (2) Round-robin, which assigns time slots in circular order, and (3) Linear, which allocate time linearly with respect to the number of floating-pore pointt operations each operator has. Fig. 8 shows that DynaTTune consistently outperforms other static schemes and achieves 1. 1.1-2.4 times speedup to obtain the lowest latency. As mentioned in Sec. 3, static knowledge alone is insufficient for making well-suited schedule decisions. In contrast, the improvement in DynaTune comes from constantly making decisions and replaning the allocation strategy based on new observations.
DynaTine
Random
Round-rohin
Linear
Reskitt 30
SqueeneNet
VSS
Thansformer
20
28
4330 Time costis)
Time costisl
Time costis)
Time costisl
Figure &: Comparison convergence speed and quality between DynaTune and static schemes.
5.3 COMPARISON OF DYNATUNE WITH ALTERNATIVE DYNAMIC SCHEMES
We also compare the effectiveness of our approach by comparing the following dynamic schemes: (1) Dynamic allocation (DA) Random selection (Rand): Randomly assigns time slots to operators and reallocates time slot if the chosen operator has been early terminated. (2) Dynamic allocation (DA) + Round-robin selection (RR): Assigns time slots in circular order, and keep other settings the same as the "DA+ + Rand" configuration. For all schemes, we use the same early termination condition, e.g., operator is considered finished if it has not seen any GFLOPS improvement for a given number of iterations (c.g.. 200). Fig. shows that, when not equipped with the Bayesian model (e.g., Rand and RR), the optimization converges relatively slower than with the model to obtain a lower latency. In contrast, DynaTTune achieves 1-1.4 times speedup to obtain the lowest latency, presumably because the prediction helps identify operators that potentially bring high latency reduction. We also evaluated DunaTune with two alternative action functions: e-greedy and softmax sampling. As Fig. 14 shown, while UCB offers marginal gains in some cases, the performance of all three action functions are very similar (more results can be found in Appendix A), indicating that potentially all three action functions can be used for operator selection.
Dyna Tune
DW+Rand
DA-RR
SquecseNet
330
20
10000000000000000 Time costts)
Time costts)
Time coslls)
Time coslls)
Figure 9: Comparison of convergence speed and quality between Dyna and alternative dynamic schemes.
5.4 COMPARISON WITH CHIMMELENN
Chameleon (Ahn et al., 2020) is a recent work that uses reinforcement learning and adaptive sam- pling to efficiently explore the code transformation space of a tensor operator. In this part, we compare Dyna'Tune with the open-sourced version of Chameleon". We follow the provided instruc- tions and evaluate Chameleon on the same set of models: ResNet- 18 and SqueezeNet CPU, VGG and Transformer on GPU. Figure 10c and Figure 10d show that although Chameleon is faster than
hhttps://gg thub. com/ aaaaannonnyysyae sub/ chameleo

---

Published as a conference paper at ICLR 2021
the baseline AutoTVM on VGG and Transformer on GPU, it is slower than DynaTume to converge to the lowest latency. This is because although the optimization speed of each operator has been improved by Chamelcon, it still sequentially optimizes operator at time. Therefore, the overall convergence speed is still bounded by the least optimized tensor operators. In contrast, DynaTTne focuses improving the convergence speed of multi-tenoor-pperanne and dynamically allocates time to improve the overall convergence speed.
We also evaluate Chameleon on CPU, given that model inference is not uncommon on CPU (Wu et al., 2019a; Zhang et al., 2019; 2018). When running on CPU, a bit surprisingly, we observe that Chameleon is slower than the baseline AutOTVM on ResNet- 18 (Figure 10a) and SqueezeNet (Figure 10b). We analyze the performance and find that the RL optimizer in Chameleon adds non-trivial amount of overhead than the default optimizer (SA + XGBoost) used in AutoTVM on CPU. As result, although Chameleon reduces the hardware measurement cost and the number of iterations to find the best configuration, its optimization time on CPU is longer than the baseline AutoTVM because of this extra overhead and is therefore also slower than DynaTune CPU. Overall, Tune is 1.44.77 times faster than Chameleon to reach the same latency. Although DynaTune is faster than Chameleon, want to point out that DynaTune be combined with Chameleon to achieve better performance, at least on GPU.
DynaTune
DynaTune
DynaTune Auto Chameleon
DynaTune Auto TVM
AutoTVM
Autol Chameleon
Latencythar
Chareeeen
Lenencyiinn
Chameleon
Time costls)
Timee costist
Time covtls)
Time coslis)
(a) R8
(b) SqueezeNet
(c) VGG
(d) Transformer
Figure 10: Comparison with AutoTVM, Chameleon, and DynaTune.
5.5 MORE ANALYSIS RESULTS
Iieerpoe Timeline
AunoTVM Dynoiliee
TVM
200
2.44
300
Dyne Tune
greecy Softmax--smplin
g
Latoncylins)
Por
3000
8
2
Tuning Schelalng
Resl ourve
Rewnet
AnotVM
Dynotume Randem
DA
Bellef curve
Time coctrl
banaiona
Figure 14: Comparison
Figure 11: Inference time Figure 12: Cost break- Figure 13: DynaTuuee
with e-greedy and softmax sampling (VGG).
comparison.
down.
curve fitting.
Inference time comparison Fig. 11 compares the final inference time optimized by TVM, Au- toTVM, and DynaTune respectively. Overall, DynaTune achieves up to 26.7% faster inference speed over TVM and similar code performance as AutoTVM. AutoT'VM and DynaTune achieve much higher speedup on ResNet-18 and Transformer, presumably because the heuristic-based opti- mizations in TVM are sub-optimal. While achieving comparable optimization quality as AVtoTVM. DynaTune significantly reduces the lengthy optimization time.
Segment curve fitting, Fig. 13 gives example the curve fitting. It is easy to that the data between I and 80 could be approximated well by one segment, and the data between 80 and 260 could be approximated by another segment.
Cost breakdown. Fig. 12 shows the breakdown in the average time required scheduling a time slot (averaged across four models), which involves the optimization time (e.g., 100s) and the scheduling cost. Overall, baseline (sequential), random, and round-robin incur almost no overhead in schedul- ing. Our Bayesian belief model takes time do fitting (MLE and MCMC) and inference. However,
8

---

Published as a conference paper at ICLR 2021
it only adds 1.44s, which adds 1.4% overhead and can be easily compensated by the time saved from picking a promising operator to optimize.
RELATED WORK
Dyna'Tune uniquely offers a solution that exclusively enables (i) Multi-Armed Bandits based dy- namic multi-tensor-operator optimization and (ii) extrapolation of optimization performance by Bayesian inference in the context of (iii) optimizing DL compilers. As such, we discuss the re- lated work from each of the three independent research directions.
Optimizing compilers. TVM (Chen et al., 2018a) and TensorCooprehensioon (Vasilache et al., 2018) use simulated annealing and genetic algorithm to search the best code transformation plan for neural networks. Subsequently. AutoTVM (Chen et al., 201800 8b) incorporates boosted decision trees as a surrogate model to reduce the number of real hardware measurements. CHAMELEON (Ahn et al., 2020) proposes to use reinforcement learning for efficient search space exploration. AdaTune (Li et al., 2020) cuts the cost of hardware measurement through adaptive evaluator and allows to better adapt optimizations against hardware and model heterogeneity. However, while existing approaches study how to accelerate the convergence of individual operators, DynaTune focuses improving the convergence speed of the entire model using Multi-Armed Bandit learn- ing for dynamic optimization cross all tensor operators. DynaTune can be combined with other approaches that speed up the convergence of individual operators maximize gains. Program au- totuning has also been studied in the context of generic programming, where black box optimiza- tion (Ansel et al.. 2014) and runtime information (Novillo, 2014) are utilized generate optimized code. Rather than ad advancing the generic problem of program auto-tuning, our technique is designed and validated specifically for the DL model compilation problem.
Multi-Armed Bandits. The Multi- Armed Bandits (MAB), first introduced by Robbins (Robbins, 1952), with various modifications have been used model a plethora of dynamic optimization problems under uncertainty (Zelen, 1969; Bergemann & Välimäki, 1996; Kleinberg & Leighton, 2003; Awerbuch Kleinberg, 2004; Bergemann Hege, 2005; Caro Gallien, 2007; Pandey al., 2007). To the best of our knowledge, our work exclusively explores different problem, which is optimizing DL compilers using MAB. Furthermore, our problem can be viewed as an instance of rested, non-stationary MAB, which is complicated process depends on the choices made by the algorithm. We are able to design new UCB-style algorithms that improve the DL compilation in this specific non-stationary rested bandit scenario.
solve since the evolution of the stochastic
broad field and has been widely used in statistical analysis (Box & Tiao, 2011). For example, Bayesian inference has been used in hyperparameter tuning (Domhan et al., 2015; Lu et al., 2019). DynaTTune shares similarities with these methods in building Bayesian model for prediction, but it differs in its context and has its unique chal- lenges. The Bayesian belief model we design is to predict operators that may lead to greater latency reduction whilst performing an optimization accelerate the process.
Bayesian Inference. Bayesian inference
CONCLUSION
Although highly optimized code can be achieved through existing DL compilers, an obvious draw- back is that they optimize operators one at time, leading to slow convergence of optimization speed when the model has multiple operators. In this paper we have introduced method, called DynaTune, which treats the optimization of multiple operators in model whole and dynam- ically optimizes all operators to expedite convergence. Combined with a Bayesian belief model, the dynamic optimization prioritizes operators that have larger latency reduction. As result, Dy- naTuu naTune achieves much faster convergence speed in getting optimized models, outperforming the ffat--o-thhe-ae art approaches.
ACKNOWLEDGEMENT
The authors appreciate the anonymous ICLR reviewers for providing constructive feedback for im- proving the quality of this paper. All authors are not funded by any other agency.

---

Published as a conference paper at ICLR 2021
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, 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 the 12th USENIX Conference on Operating Systems Design and Implementation, OSDI 16, pp. 265-283, 2016. ISBN 978-1-931971-33-1. URL cfm? d= 302 3026899.
http:/ httt:://dl.ee acm. owg. httr//iitee
Andrew Adams, Karima Ma, Luke Anderson, Riyadh Baghdadi, Tzu-Mao Li, Michaël Gharbi, Benoit Steiner, Steven Johnson, Kayvon Fatahalian, Frédo Durand, and Jonathan Ragan-Kelley. Learning optimize halide with tree search and random programs. ACM Trans. Graph., 38(4): 121:1-121:12, 2019.
Byung Hoon Ahn, Prannoy Pilligundla, Amir Yazdanbakhsh, and Hadi Esmaeilzadeh. Chameleon: Adaptive code optimization for expedited deep neural network compilation. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020. URL https: www.opeeeeveeeeee ww..eeeeeeeeeee..eee.ee........e forum? www.ridrrrggggyVygr.
Jason Ansel, Shoaib Kamil, Kalyan Veeramachaneni, Jonathan Ragan-Kelley, Jeffrey Bosboom, Una-May O'Reilly, and Saman P. Amarasinghe. Opentuner: an extensible framework for pro- gram autotuning. In José Nelson Amaral and Josep Torrellas (eds.), International Conference Parallel Architectures and Compilation, PACT 14, Edmonton, AB, Canada, August 24-27, 2014, pp. 303-316 ACM, 2014.
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Mach. Learn., 47(2-3):235-255 2002.
Baruch Awerbuch and Robert D Kleinberg. Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. pp. 45-53, 2004.
Dirk Bergemann and UIrich Hege. The financing of innovation: Learning and stopping. RAND Journal of Economics, pp. 719-752, 2005.
Dirk Bergemann and Juuso Välimäki. Learning and strategic pricing. Econometrica: Journal of the Econometric Society, pp. 1125-1149, 1996.
George EP Box and George Tiao. Bayesian inference in statistical analysis, volume 40. John Wiley& & Sons, 2011.
Eric Brochu, Vlad M. Cora, and Nando de Freitas. A tutorial on bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning. CoRR, abs/1012.2599, 2010. URL http: //arxivaavvv.////////a//eaaaaaaa org/ alos /1022.11112 2599.
Felipe Caro and Jérémie Gallien. Dynamic assortment with demand learning for seasonal consumer goods. Management Science, 53(2):276-292. 2007.
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 Heterogeneous Distributed Systems. arXiv preprint arXiv.1512.01274, 2015. URL http:
1112. 01274.
Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Q. Yan, Haichen Shen, Meghan Cowan, Leyuan Wang, Yuwei Hu, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. TVM: an automated end-to-end optimizing compiler for deep learning. In 13th USENIX Symposiun on Operating Systems Design and Implementation, OSDI 2018, Carlsbad, CA, USA, October 8-10, 2018, pp. 5785594, 2018a. URL https: www. usenix. wwt.conferenceeeeeooooooooeeeeee osdi18/ presentat i on chen.
10

---

Published as a conference paper at ICLR 2021
Tianqi Chen, Lianmin Zheng, Eddie Q. Yan, Ziheng Jiang, Thierry Moreau, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. Learning to optimize tensor pro- grams. In Advances in Neural Information Processing Systems 31: Annual Confer- ence on Neural Information Processing Systems 2018, NewrlPS 2018, 3-8 December 2018, Montréal, Canada, pp. 3393 3993-3404, 2018b. URL http::/papers: nips. cc/paper/
tensor--eeeer-eeeee 1ers9--earning-ttoe oet--ptiimii oes- progergrsssssoosssss..s. programs.
Sharan Chetlur, Cliff Woolley, Philippe Vandermersch, Jonathan Cohen, John Tran, Bryan Catan- zaro, and Evan Shelhamer. cuDNN: Efficient Primitives for Deep Learning. arXiv preprint arXiv:1410.0753 2014. URL http::::/axxvv..g////oo
07599
Corinna Cortes, Giulia DeSalvo, Vitaly Kuznetsov, Mehryar Mohri, and Scott Yang. Discrepancy- based algorithms for non-stationary rested bandits. arXiv preprint arXiv: 10657, 2017.
Tobias Domhan, Jost Tobias Springenberg, and Frank Hutter. Speeding up automatic hyperparame- ter optimization of deep neural networks by extrapolation of learning curves. In Qiang Yang and Michael J. Wooldridge (eds.), Proceedings of the Twenty-Fourts International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, pp. 3460-3468 AAAI Press, 2015.
Daniel Foreman- David W Hogg, Dustin Lang, and Jonathan Goodman, emcee: the meme hammer. Publications of the Astronomical Society of the Pacific, 125(925):306, 2013.
John Gittins, Kevin Glazebrook, and Richard Weber. Hulti-armed bandit allocation indices. John Wiley Sons, 2011.
Jonathan Goodman and Jonathan Weare. Ensemble samplers with affine invariance. Communica- tions in applied mathematics and computational science, 5(1):65-80) (0)0)600000000 2010.
Priya Goyal, Piotr Dollár, Ross B. Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: training im- agenet in 1 hour. CoRR, abs/1 706.02677, 2017. URL http::/aaxiv..oo org. abs///abs//0 02677.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. The Collected Works of Wassily Hoeffding, pp. 409-426 Springer, 1994.
Forrest N. landola, Matthew W. Moskewicz, Khalid Ashraf, Song Han, William J. Dally, and Kurt Keutzer. SqueezeNet: AlexNet-level Aceuracy with 50x Fewer Parameters and <1MB Model Size. arXiv preprint urXiv:1602.07360, 2016. URL 07360.
Robert Kleinberg and Tom Leighton. The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In 44th Annual IEEE Symposium Foundations of Computer Science, 2003. Proceedings. pp. 594-605. IEEE, 2003.
Chris Lattner, Jacques Pienaar, Mehdi Amini, Uday Bondhugula, River Riddle, Albert Cohen, Ta- tiana Shpeisman, Andy Davis, Nicolas Vasilache, and Oleksandr Zinenko. Mlir: A compiler infrastructure for the end of moore's 's law. arXiv preprint arXiv:2002.11054 2020.
Chris Leary and Todd Wang. Xla: Tensorflow, compiled. TensorFlow Dev Summit, 2017.
Menghao Li, Minjia Zhang, Chi Wang, and Mingqin Li. Adatune: Adaptive tensor program com- pilation made efficient. In Hugo Larochelle, Mare' Aurelio Ranzato. Raia Hadsell, Maria- Balcan, and Hsuan- Tien Lin (eds.), Advances in Neural Information Processing Systems 33: An- nual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual, 2020.
Lin, Chuang Gan, and Song Han. Training kinetics in 15 minutes: Large-scale distributed training videos. arXiv preprint arviv: 19:::99/00 10.00332, 2019.

---

Published as a conference paper at ICLR 2021
Changxi Liu, Hailong Yang, Rujun Sun, Zhongzhi Luan, Lin Gan, Guangwen Yang, and Depei Qian. Swtvm: exploring the automated compilation for deep learning on sunway architecture. arXiv preprint 19X1::190.007000 2019.
Zhiyun Lu, Liyu Chen, Chao-Kat Chiang, and Fei Sha. Hyper-paramen parameter tuning under a budget con- straint. In Sarit Kraus (ed.), Proceedings of the Twenty-Eight International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pp. -7500. ijeai.org. 2019.
Pavlo Molchanov, Stephen Tyree, Tero Karras, Timo Aila, and Jan Kautz. Pruning Convolutional Neural Networks for Resource Efficient Inference. In 5th International Conference on Learning Representations, ICLR 2017, 2017.
Diego Novillo. Samplepgo: the power of profile guided optimizations without the usability burden. In Hal Finkel and Jeff R. Hammond (eds.), Proceedings of the 2014 LLVM Compiler Infras- fructure in HPC, L.VM 2014, New Orleans, LA, USA, November 17, 2014, pp. 22-28. IEFE Computer Society, 2014.
Sandeep Pandey, Deepak Agarwal, Deepayan Chakrabarti, and Vanja Josifovski. Bandits for tax- onomies: A model-based approach. In Proceedings of the 2007 SIAM International Conference on Data Mining, pp. 216-227. SIAM, 2007.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang. Zachary Vito,o, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, per--performnnce deep learning library. In Advances in Neural Information Processing Systems 32: Annual Con- ference on Neural Information Processing Systems 2019, NeurlPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 8024 8035, 2019. URL httpttt:::ppppeeeeeeeeepppt/atte nips cc cc/paper/ ho15-pytorch-an-iiee
Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5)5277-335 1952.
Nadav Rotem, Jordan Fix, Saleem Abdulrasool, Summer Deng, Roman Dzhabarov, James Hege- man, Roman Levenstein, Bert Maher, Nadathur Satish, Jakob Olesen, Jongsoo Park, Artem Rakhov, and Misha Smelyanskiy. Glow: Graph lowering compiler techniques for neural net- works. CoRR, 0tbs/1805.00000 2018. URL http: http://aaxvvvvvo org/ www.baaaa. 00907.
Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro. Megatron-Im: Training multi-billion parameter language models using model par- allelism. CoRR, abs//909.000 190000809,,...... 2019.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale im- age recognition. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http: //arxiv.org aabs/1409 1556.
Nicolas Vasilache, Oleksandr Zinenko, Theodoros Theodoridis, Priya Goyal, Zachary DeVito, William S. Moses, Sven Verdoolaege, Andrew Adams, and Albert Cohen. Tensor com- prehensions: Framework-agnostie highhperformance machine learning abstractions. CoRR, abs/1802.04730, 2018 URL http: / /wtxxvivvv....///////...///aaavv .rgg abs /1022 04730.
Carole-Jean Wu, David Brooks, Kevin Chen, Douglas Chen, Sy Choudhury, Marat Dukhan, Kim Hazelwood, Eldad Isaac, Yangqing Jia, Bill Jia, al. Machine learning at facebook: Understand- ing inference at the edge. In 2019 JEEE International Symposium on High Performance Computer Architecture (HPCA), pp. 331-344, IEEE, 2019a.
Carole-Jean Wu, David Brooks, Kevin Chen, Douglas Chen, Sy Choudhury, Marat Dukhan, Kim Hazelwood, Eldad Isaac, Yangqing Jia, Bill Jia, et al. Machine learning at facebook: Understand- ing inference at the edge. In 2019 JEEE International Symposium on High Performance Computer Architecture (HPCA). pp. 331-344. IEFE, 2019b.
12

---

Published as a conference paper at ICLR 2021
Masafumi Yamazaki, Akihiko Kasagi, Akihiro Tabuchi, Takumi Honda, Masahiro Miwa, Naoto Fukumoto, Tsuguchika Tabaru, Atsushi Ike, and Kohta Nakashima. Yet another accelerated SGD: resnet-50 training imagenet in 74.7 seconds. CoRR, abs/1903.12650, 2019. URL http:
//arxiv.ore org/ www.//////////oo//////.///eeeee/ abs 1 903 12650.
Yang You, Igor Gitman, and Boris Ginsburg. Large batch training of convolutional networks. arXiv preprint arviv: 1000 708.7388.88 03888, 2017.
Yang You, Jing Li, Jonathan Hseu, Xiaodan Song, James Demmel, and Cho-Jui Hsich. Reducing
BERT pre-training time from 3 days 76 minutes. CoRR, abs/1904.00962 2019.
Marvin Zelen. Play the winner rule and the controlled clinical trial. Journal of the American Statistical Association, 64(325):131-146 1969.
Minjia Zhang. Samyam Rajbhandari, Wenhan Wang, and Yuxiong He. Deepepu: Serving rnn-based deep learning models 10x faster. In Haryadi S. Gunawi and Benjamin Reed (eds.), 2018 USENIX Annual Technical Conference, USENIX ATC 2018, Boston, MA, USA, July 1 11-13, 2018, pp. 951- 965. USENIX Association, 2018.
Minjia Zhang, Samyam Rajbhandari, Wenhan Wang, Elton Zheng, Olatunji Ruwase, Jeff Rasley, Jason Li, Junhua Wang, and Yuxiong He. Accelerating large scale deep learning inference through deepepu microsoft. In 2019 USENIX Conference on Operational Machine Learning, OpML 2019, Santa Clara, CA, USA, May 20, 2019, pp. 5-7, 2019. URL hwtpttttt//..om //ww://wwwww///.//////////./wt usenix. org/ confereecee/omll 1tt11/9/eee/aaaeeeeeee on wwwng-aanngmm-
-esaag--mii mim minjjia.
Lianmin Zheng, Chengfan Jia, Minmin Sun, Zhao Wu, Cody Hao Yu, Ameer Haj-Ali, Yida Wang, Jun Yang, Danyang Zhuo, Koushik Sen, Joseph E. Gonzalez, and lon Stoica. Ansor Generat- ing nigh-performance tensor programs for deep learning. CoRR, abs/2006.06762, 2020. URL https: /tss://axxivi org/ wttgg/bb//eee 200..
A COMPARISON WITH E-GREEDY AND SOFTMAX SAMPLING
We compare DynaTune with two alternative operator selection methods: (1) e-greedy: Like our approach, but UCB is replaced with e-greedy, which select the operator with the highest expected latency reduction based on El with probability 1 (e.g., c=0.55) and randomly select an operator with e to ensure exploration. (2) Softmax: Like our approach but UCB is replaced with softmax sampling, which stochastically samples operators to optimize based on expected latency reduction at each step. Fig. 15- 18 show the comparison results. With the Bayesian model enabled in cases, we observe that softmax sampling, e-greedy, and UCB work very similarly across multiple models. We choose UCB in our design because it has been theoretically studied that UCB has sublinear regret growth rate.
DynaTune
DynaTune
DynaTune
DyneTune greedy Softmaa--amping
E-greddy Seftrax-sampling
groedy Soltman-sampping
E-groddy
Latency(nd)
Latenoy (m))
Softman-sampiing
2+1
costia)
2000
300
2000
costia
6030
300C
13006
3000
45300
2000
Time cocttol
9003
Figure 15: ResNet-18.
Figure 16: SqueezeNet.
Figure 17: VGG.
Figure 18: Transformer.
B MCMC ANALYSIS
Fig. 19 plots the time series (i.e., trace) of the parameters in the Markov chains to assess the behavior of our MCMC sampling. It shows the positions of each walker (10) as a function of the number of steps in the chain. The walkers start in small distributions around the maximum likelihood values and then quickly wander and start exploring the full posterior distribution. In fact, after about 100 steps, the MCMC appear to have converged stationarity (i.e., self-replicating) We also examine
13

---

Published as a conference paper at ICLR 2021
the mean acceptance fraction of the ensemble, which is 0.54 by average, and it indicates that the MCMC sampler has generated a sufficient number of parameter samples that have also gained good information about the underlying distribution.
0.7
2.0
1000
2000
3000
400D
5000
Step number
Figure 19: Ensemble MCMC trace for (a.b.c).
C COMPARISON WITH ANSOR SCHEDULER
In this section, we compare our approach with concurrent work called Ansor (Zheng et al., 2020). We use the default hyperparameters a 0.2, 3 2, backward window size=3 in the open-sourced implementation for the evaluation. We use the same evaluation methodology as ours by performing five independent runs of each configuratinn with different random seeds and reporting the median together with a 95% confidence interval. Figure 20a-20d show that both DynaTune and the Ansor scheduler outperform the baseline AuMOTVM by large margin. This is expected, because both approaches accelerate the convergence of model optimization through dynamic optimization. Fig- ure 2la-21d show more detailed comparison between Dyna Tune and Ansor. Overall, Ansor seems to reduce the latency faster in the beginning. but DynaTune always catches up and often quicker to reach the lowest latency. For example, DynaTune achieves faster convergence reach the lowest latency than Ansor on ResNet-18, 18, VGG, and Transformer.
Although Zheng et al. (2020) and our approach share similar high-level idea of dynamically allo- cating time resources to different tasks, the exact mechanisms on how to allocate resources are very different. The tasks scheduler from Zheng et al. (2020) decides which task to optimize based on a heuristic score, which is a weighted sum between the latency reduction rate of a task in a recent small time window and an expected latency reduction in the future based on task similarity infor- mation. The estimation of the score not only requires defining and heuristically adjusting similarity groups but also requires two hyperparameters a and B to control the weight to decide which esti- mations to trust more. However, it is not immediately clear how such weights should be set and how to adapt them to different models. For example, the default hyperparameter settings may cause the scheduling to be overly greedy (i.e., getting stuck at a local optimum), which may explain why Ansor converges faster in the beginning but is slower to reach the best latency towards the end. In contrast, we use Bayesian belief model to predict how much expected latency reduction from each task in the next time slot, and all the free parameters in our belief model are taken care of by MCMC sampling. Furthermore, presumably helps the search escape from local optimum.
approach takes uncertainty quantification into account, which
DynaTune
25.0
DynaTune
DynaTune AutoTVM Ansor
DynaTune
AutoTVM Ansor
630
Latenoy
Anvor
Ansor
2003
A663
6630
2200
9003
20003
49006
60600
2003
4000 Time costis)
costis)
coctisl
costis)
(a) ResNet-18 18
(b) SqueezeNet
(c) VGG
(d) Transformer
Figure 20: Comparison with V and Ansor scheduler.
htttp://wh.....oaaaaeeaaaaaatttp schedule Sthedulerr/takkscchhee
14

---

Published as a conference paper at ICLR 2021
Dyna Ansor
DynaTTune
DynaTime
Dyna Tune
Ansor
Ansor
Ansor
Latenc mmmii
Sono/saue 8
Time costis)
Time costisl
Time contis)
Time costis)
(a) ResNet-18
(b) SqueezeNet
(c) VGG
(d) Transformer
Figure 21: Comparison with Au and Ansor scheduler.
15


Reviews:
[{"review_id": "udcIN0vsQF7", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\n\nThe paper proposes an algorithm to optimize the auto-tuning time for compiling neural networks.\n It dynamically allocates time to different operators with a multi-armed bandit algorithm and a Bayesian belief model.\nThe evaluation results show the proposed method can achieve significant speedup.\n\n##########################################################################\n\nReasons for score: \n\nI lean to rejection because of some flaws in the paper.\n1. It does not mention a highly related paper that follows the same high-level idea (i.e., dynamically allocating time resource). The section 6 task scheduler in this paper (https://arxiv.org/abs/2006.06762) proposes a heuristic-based algorithm for dynamically allocating time resource. It also predicts room for improvement of each task. It supports user-defined objective functions and utilizes similarity between tasks. The authors should at least include a comparison with this method. The code of this method is merged into the TVM project (https://github.com/apache/incubator-tvm/blob/main/python/tvm/auto_scheduler/task_scheduler.py), which is the baseline of DynaTune.\n2. The formulation of reward can be improved\nIn section 4.1, the authors define the reward as the latency reduction of one operator. However, an operator can appear multiple times in a network. So a weight should be multiplied to the reduction. The weight of an operator is the number of the appearance of it in the network.\n3. Some assumptions can be improved\nIn challenge 2 of section 3, the authors claim \"We note that the optimization of tensor operators is independent of each other\". This is not true because different operators can share a cost model. They can contribute training data to the shared cost model. The shared cost model then influences the search of all operators. By using a shared cost model and transfer learning, the search time can be greatly reduced (as shown in AutoTVM and Ansor), so we cannot say the optimization of different operators is independent. How to model this effect is very challenging.\n\n\n##########################################################################\n\nPros:\n\n- Overall, the observations and ideas are correct. The paper is well-written with necessary background information.\n- The proposed methods are all reasonable\n- The evaluation results are satisfactory and well structured. It correctly evaluates all aspects that I want to know.\n\n##########################################################################\n\nSuggestion for improvement:\n\nThe authors can improve their formulation and add a comparison with the related paper I mentioned.", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZIMVPPjMoK-", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors develop DynaTune which achieves faster convergence speed to optimize a DNN model when compared to the state-of-the-art DL compiler, AutoTVM. The key idea is a time-slot-based scheduling method based on UCB-type multi-armed bandit policy. At each time, the scheduler chooses an action to maximize the latency reduction. In practice, A Bayesian belief model via MCMC is used to capture current knowledge of the optimization results to predict future performance, which helps make better decisions and expedites the convergence speed. The idea of using MAB in DL compiler is very interesting. The numerical experiments also demonstrate clear advantage of the proposed DynaTune. My concerns are as follows. \n\n1. In the experiments, it would be more convincing to numerically compare with more advanced DL compiler, e.g., Adams et al. (2019); Chameleon in Ahn et al. (2020). The Chameleon is also a RL based approach for DL compiler.\n\n2. The authors used $C=0.2$ when initial latency of an operator is <1ms, and $C=2$ for all the other cases. Can authors provide more justification on the choice of $C$? Some sensitivity analysis could be helpful. \n\n3. In the end of the first paragraph in Section 5 (line 8 on page 6), the sentence is not finished. \n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "W2Eo_6827zB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper tackles the optimization speed of the deep neural networks. The paper models the operator optimization scheduling as a Multi-Armed Bandit problem. DynaTune first selects the operation to optimize in a discrete slot of time using a Bayesian Belief Model, then optimizes the model given the slot of time.\n\nThis interesting paper may help expedite the compilation time of the deep neural networks. As such, this paper tackles on a very important problem. I view this paper as a lineage of papers on \"Expedited Compilation\" and I believe this fresh view of the problem will open up more possibilities for exploration.\n\nModeling uncertainty to understand the gains of optimizing a particular operator is very interesting, and the way it leverages this to schedule the optimization process itself is novel.\n\nIt seems that the approach can be generically combined with different optimization frameworks such as genetic algorithms. It would be nice to have such discussion and would provide interesting insights.\n\nAs a side note, however, there was a paper the tackled the optimization of the inference speed of the end-to-end network [1] which is also applied to TVM. It would be interesting to see how the overall latency achieved by DynaTune compares to this approach.\n\nQuestions:\n1. How does the end-to-end latency compare to [1]?\n2. How are the results affected when put together with GA and Random Search for the actual optimization (line 6, 9 of Algorithm 1)\n\n[1] \"Optimizing CNN Model Inference on CPUs\", ATC 2019", "extra_scores": {}, "extra_text": {}}, {"review_id": "PD9kK6AM66M", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper investigates the use of online optimization to improve the performance in Deep Neural Network (DNN) compilation. \nThe three drawbacks of the existing approach/challenges in DNN compilation highlighted in the paper are (1) optimizing individual tensor operator performance instead of that of the entire model, (2) Static scheduling is oblivious to the optimization behavior, (3) extrapolating estimated performance while tuning.  \n\nThe authors model the model as scheduling in a time-slotted system, where they model the average performance (mean reward) of each operator using some performance curve obtained empirically. These curves capture the variability of operators across training duration, which helps with (1) and (2). For tackling (3),  the variability of the performance (noise) of each operator is estimated using some MCMC sampling techniques. Finally, using the mean reward and noise they cast the problem as finding the expected optimal schedule - a sequence of operators to be chosen during the training, as a Multi-armed bandit problem. The authors then design the DynaTune Algorithm base on a well-known UCB algorithm to solve this problem. \n\nThe experiments show DynaTune outperforms AutoTVM (Chen et al., 2018b) the apparent state-of-the-art (see, disclaimer below) in many important DL architectures. \n\n\nPros:\nThe problem of optimizing DL architectures is an important problem, as they are ubiquitous. The three challenges mentioned here sound credible (to an outsider), and in gains of dynamic scheduling is well known. Overall, the problem is well-motivated, and the solution proposed is justified. The experiments seem to give DynaTune an edge over an existing method. \n\n\n\nCons:\n* How Fig 2,3,4 are obtained is not clear to me. Some pointers to empirical studies or the methodology used are necessary. \n\n* The details behind the variability estimation using the MCMC method is also not clearly written. \n\n* The baseline AutoTVM (Chen et al., 2018b) is somewhat old. However, I am not sure if a better baseline is available. \n\n\n\n\n\n\n\nDisclaimer: Although I am familiar with works on Bandits, I am a complete outsider to the topic of DNN compilation.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper applies multi-armed bandits to tuning deep learning code optimization. All reviewers agreed that this is an exploratory paper that opens up a new research area. My main criticism is algorithmic. In particular, the paper applies a 20-year old algorithm to a problem with a small number of arms. It is definitely not as impressive as

https://papers.nips.cc/paper/2018/file/f33ba15effa5c10e873bf3842afb46a6-Paper.pdf

who studied a different (but related) problem. The tuning problem in this paper also seems non-stochastic and contextual, while the authors apply a stochastic non-contextual bandit algorithm.

I shared these concerns with the reviewers, who insisted that the application is important enough to justify the acceptance of the paper. I respect their opinion and therefore suggest an acceptance. I encourage the authors to take my comments into account when revising the paper.
Decision: Accept (Poster)