shapes.geometric

# Sonic: A Sampling-based Online Controller for
Streaming Applications

Yan Pei<EMAIL_ADDRESS>University of Texas at AustinAustinTXUSA and
Keshav Pingali<EMAIL_ADDRESS>University of Texas at AustinAustinTXUSA

###### Abstract.

Many applications in important problem domains such as machine learning and
computer vision are streaming applications that take a sequence of inputs over
time. It is challenging to find knob settings that optimize the run-time
performance of such applications because the optimal knob settings are usually
functions of inputs, computing platforms, time as well as user’s requirements,
which can be very diverse.

Most prior works address this problem by offline profiling followed by
training models for control. However, profiling-based approaches incur large
overhead before execution; it is also difficult to redeploy them in other run-
time configurations.

In this paper, we propose Sonic, a sampling-based online controller for
streaming applications that does not require profiling ahead of time. Within
each phase of a streaming application’s execution, Sonic utilizes the
beginning portion to sample the knob space strategically and aims to pick the
optimal knob setting for the rest of the phase, given a user-specified
constrained optimization problem. A hybrid approach of machine learning
regressors and Bayesian optimization are used for better sampling choices.

Sonic is implemented independent of application, device, input, performance
objective and constraints. We evaluate Sonic on traditional parallel
benchmarks as well as on deep learning inference benchmarks across multiple
platforms. Our experiments show that when using Sonic to control knob
settings, application run-time performance is only 5.3% less than if optimal
knob settings were used, demonstrating that Sonic is able to find near-optimal
knob settings under diverse run-time configurations without prior knowledge.

Online control, Bayesian optimization, resource management

##  1\. Introduction

Streaming applications are ubiquitous in important domains such as deep
learning, computer vision and media processing. Those applications are
typically long-running applications with inputs supplied incrementally over
time, assuming that the run-time behavior of the application for successive
inputs is stationary. For instance, augmented reality (AR) applications take
in a series of frames to enhance real-world scenes by computer-generated
perceptual information. Optimizing streaming application’s run-time
performance is important but challenging because it depends on multiple
factors including inputs, computing devices, time as well as user’s
requirements.

Most streaming applications have a set of tunable parameters, usually referred
to as _knobs_ , that can be adjusted to optimize their performance; as long as
knob values are within certain limits, the correctness of the application is
not compromised. Many streaming applications are executed on parallel
platforms, so their performance is also affected by characteristics of the
device such as the number of cores allocated and their clock frequency.
Finding the optimal device knob setting is challenging because modern compute
devices have more and more non-trivial parallelism.

In addition, applications are usually optimized subject to various constraints
such as computation accuracy, power/energy consumption, _etc_. For instance,
energy consumption is an important factor in lowering the operation cost of
data centers as well as lengthen battery life for resource-constrained
devices. Given different combinations of performance objectives and
constraints, the system needs to find different optimal knob settings
accordingly.

Furthermore, application’s performance is also sensitive to inputs. For
instance, both image size and image content may affect image/video related
tasks’ performance. Unlike problems such as n-body simulation (Aarseth and
Aarseth, 2003) and graph partitioner (Bader et al., 2013) whose inputs are
available at the beginning of the computation for inspection, streaming
application’s inputs are usually not known before execution and are supplied
over time.

The cross-product of applications, devices, inputs, performance objective and
constraints makes it very challenging to decipher the optimal application and
device knob settings of any run-time configuration. Prior works usually
address such problem through offline executions of a set of run-time
configurations, or offline profiling, followed by constructing models to
predict application’s run-time behavior (Sui et al., 2016; Biswas et al.,
2017; Imes et al., 2015; Haj-Ali et al., 2020; Mururu et al., 2021; Khudia et
al., 2015; Baek and Chilimbi, 2010; Mishra et al., 2018, 2015; Ding et al.,
2019). Models are then used to perform _offline control_ or _reactive online
control_. For example, _Capri_ builds proxy models for both quality and
running time of a program through offline profiling. These models together
with input features are then used to perform proactive control of
approximation (Sui et al., 2016); _CALOREE_ performs online control using
estimated performance-energy pareto frontier of one application by matching
its behavior with models that have been already profiled on the same machine
(Mishra et al., 2018).

However, there are several drawbacks for such profiling-based approaches.

  * $\bullet$

_Overhead_. Profiling incurs large overhead, including compilation, data
collection (execution), model training and so on. On embedded platforms,
profiling takes long time due to limited computation resource while it can be
very costly to get profiling data on larger servers. Profiling even becomes
inapplicable when single execution of an application is expensive, e.g.
chemical material design (Griffiths and Hernández-Lobato, 2017).

  * $\bullet$

_Scope_. Due to the overhead of profiling, only a specific subset of the whole
run-time configuration space can be profiled. For example, prior works usually
profile on a small subset of inputs and assume it is representative (Sui et
al., 2016; Khudia et al., 2015); Capri (Sui et al., 2016) and Rumba (Khudia et
al., 2015) focus on optimizing performance under accuracy constraint while
_POET_ (Imes et al., 2015) and CALOREE (Mishra et al., 2018) only target on
minimizing energy given a performance requirement. Users may be interested in
other reasonable constrained optimization problems such as “Least resource
allocation given a performance requirement” on super computers.

  * $\bullet$

_Portability_. Models built on profiling data are difficult to be ported to
other unseen run-time configurations. For instance, the relationship between
application’s performance and power on one device may not hold on new device
with distinct hardware architectures.

While profiling-based approaches tries to anticipate application’s run-time
behavior through offline data, we propose to solve such control problem from a
pure online control perspective, in which the optimal knob setting is searched
during run time, given the nature of streaming applications that the run-time
behavior for successive inputs is stationary.

Due to complex run-time configuration space, we formulate the control problem
as a _global optimization_ process that searches the optimal knob setting by
sampling, rather than a _traditional feedback control loop_ that adjusts knob
settings by comparing quantities of interest with reference values. In this
paper, we propose _Sonic_ , a sampling-based online controller that does not
require profiling ahead of time. Sonic consists of two key components: a
sampler and a phase detector.

##### Sampler.

Within each phase of a streaming application’s execution, the sampler utilizes
the beginning portion of that phase to sample the knob space and collect the
statistics of each sampled knob setting. After the sampling phase, the
controller picks the best knob setting among the sampled ones based on the
performance objective & constraint of the current run-time configuration. The
picked knob setting will then be used for the following execution. Since it is
challenging to capture and optimize application’s run-time behavior with only
limited samples of knob settings, we incorporate combinations of machine
learning regressors and sequential design strategy for global optimization
such as Bayesian optimization (Pelikan et al., 1999; Frazier, 2018; Shahriari
et al., 2015) for better sample choices.

##### Phase Detector.

Streaming application may have distinct phases during one run due to various
reasons such as algorithmic phases, launch of another program on the same
device, inputs change, _etc_. In Sonic, a phase detector is activated after
the sampling period and monitors the difference between application’s current
behavior with the recorded behavior of the picked knob setting during the
sampling phase. If the difference is large, a new sampling period will be
activated. In this paper, we assume that each phase is long enough for the
sampling-based online control strategy to be beneficial.

We evaluate Sonic on the PARSEC parallel benchmark suite (Bienia et al., 2008)
and a modified MLPerf inference benchmark suite (Mattson et al., 2020) across
multiple platforms. The primary contributions of this paper are listed as
follows:

  * •

To the best of our knowledge, Sonic is the first sampling-based online
controller targeting general streaming applications without dependencies on
offline profiling.

  * •

Sonic incorporates a hybrid control approach that consists of sequential
design strategies and machine learning regressors to improve the choice of
samples.

  * •

Sonic is implemneted independent of applications, devices, inputs, objectives
and constraints, so it can be easily ported to different run-time
configurations. It is also orthogonal to other types of optimizations such as
algorithmic improvement, new accelerator and so on.

  * •

Sonic is easy to use. The only extra code needed for application and device is
an interface to report their performance at run time. No need for algorithmic
changes such as annotating code, enabling re-computation (Baek and Chilimbi,
2010; Khudia et al., 2015), _etc_.

  * •

By evaluating on traditional and deep learning benchmarks, our experiments
show that when using Sonic, application performance is only 5.3% less than if
optimal knob settings were used, showing that Sonic is able to find near-
optimal knob settings under diverse run-time configurations.

Sonic can be very useful in situations when run-time configurations changes
frequently. For example, devices may be unknown and undeterministic when using
cloud service; user changes input, performance objective/constraint
frequently.

##  2\. Background and Motivation

Streaming applications takes a sequence of inputs such as an audio/image
sequence, a series of transformations, _etc_. These inputs are usually not
available before application starts, and will be supplied over time. In this
paper, we will focus on streaming applications that run on CPUs due to CPU’s
advantages such as flexibility and availability over other devices such as
GPUS, ASICs, _etc_.

###  2.1. Baseline Performance

In the default run-time setting, application’s knobs are set to a default
value, chosen by the programmers during implementation. The _race-to-idle_
strategy is applied by default on devices, so all the computing resource will
be allocated with their highest operation condition. We use the term DEFAULT
to refer to this default application and device knob setting.

The most common performance metric of a streaming application is the rate of
processing inputs, or _FPS_. We demonstrate how DEFAULT performs by
inferencing various deep neural network models on a dual-socket desktop
workstation with 64 cores. All the models are implemented within _TensorFlow_
(Abadi et al., 2016). For simplicity, all the application knobs are fixed and
only the number of cores to which an application is deployed is controlled in
this experiment.

Since DEFAULT may not yield the best performance, we use term ORACLE to refer
to the optimal knob setting given by exhaustive profiling. The comparison
between DEFAULT and ORACLE as well as the optimal number of cores to use are
shown in Table 1. While DEFAULT should yield the best performance in many
cases, surprisingly, no model has the best performance when uses all the 64
cores in this experiment. There is a geometric mean performance loss of 40%
when using DEFAULT, and different models have different ORACLE settings. The
primary cause is that the communication overhead between cores grows with the
number of cores being used. The ORACLE setting achieves better balance between
communication and the amount of work allocated to each core. Also worth to
notice that using DEFAULT results in unnecessary recourse occupation. Though
DEFAULT is easy to use, this experiment shows that DEFAULT may underutilize
modern computer systems that have more and more non-trivial parallelism.

Applications | DEFAULT | ORACLE | Cores | Speedup
---|---|---|---|---
ResNet8 | 1409.01 | 1769.18 | 4 | 1.25x
ResNet50 | 53.46 | 60.88 | 46 | 1.14x
MobileNet_V2 | 124.57 | 139.02 | 15 | 1.12x
Visual wake words | 245.11 | 267.25 | 4 | 1.09x
Speech recognition | 2.06 | 4.26 | 2 | 2.07x
Text classification | 124.92 | 257.85 | 7 | 2.06x
Table 1. Model inference performance comparison between DEFAULT and ORACLE on
a dual-socket 64-core desktop workstation with TensorFlow.

This experiment involves optimizing different applications on one device
without imposing constraints. It becomes more difficult to find the optimal
knob setting when having more dimensions of complexity: devices, inputs, user-
specified performance objective and constraints (Section 2.2 \- Section 2.4).

###  2.2. Device Diversity

We demonstrate device diversity by running the same application on two popular
embedded platforms: i) Odroid XU4, ii) Jetson TX2. Both devices are
heterogeneous platforms with two types of cores. The application used is Vips,
a parallel image transformer for large uncompressed images.

Figure 1 shows the normalized performance of Vips on two platforms when using
different core combinations. Vips’s performance is neither linear nor convex,
and has very different patterns between two boards. First of all, neither
boards yield the best performance when using DEFAULT. Second, the optimal knob
setting is three big cores and four little cores on Odroid XU4 while two
Denver cores and two Arm cores on Jetson TX2. It is not trivial to obtain the
optimal knob setting due to the complexity in application’s implementation
(e.g. load balancing, data exchange & sharing) and device’s architecture (e.g.
compute capacity of/between cores).

###  2.3. Input Sensitivity

The next layer of complexity comes from inputs. The most straightforward
factor is input size. Video encoder X264 encodes 720p videos $\sim$4$\times$
faster than 1080p videos. More unnoticeable factors involve input content. As
shown in Figure 2, though both videos are of 720p, encoding rendered content
(14.3 FPS) is almost 2$\times$ faster than encoding photographic content (8.3
FPS) on an Odroid XU4 board. The potential reason is that rendered content is
relatively ‘easier’ because it is generated with algorithms. Input sensitivity
of such leads to distinct optimal knob settings when having a fixed
performance requirement, e.g. minimum FPS requirement.

(a) Odroid XU4

(b) Jetson TX2

Figure 1. Performance of Vips on Odroid XU4 and Jetson TX2 with different
combination of cores.

(a) Rendered content

(b) Photographic content

Figure 2. Example of content difference of X264 inputs.

###  2.4. Objectives and Constraints

(a) FPS Vs. Power

(b) FPS Vs. Energy

Figure 3. Example pareto frontiers of X264 on Odroid XU4. Each point
represents one knob setting.

User-specified run-time objective and constraint also affect the optimal knob
setting. An objective is defined as a metric to optimize; a constraint is
represented by a metric and a set point. Meeting a constraint means the metric
value is lower ( or higher) than the set point per user request. Note that
constraint is optional and there can be more than one constraints.

In Figure 3, we display _pareto frontiers_ of two constrained optimization
problems of X264 running on Odroid XU4. It is clear that given different
constraint metrics, their pareto frontiers are significantly unalike; given
one constraint such as power, different set points result in distinct knob
settings on the pareto frontier. It also worth to notice that there are plenty
of “good enough” knob settings near the pareto frontier that yield similar
performance.

Most prior works (Sui et al., 2016; Mishra et al., 2018) focus on solving only
one type of objective and constraint combination, such as “Optimize
performance given an accuracy bound” or “Least energy under a performance
cap”. However, objective and constraint can be any meaningful combinations
depending on actual use cases. Other common (constrained) optimization
problems includes “ _Maximize FPS_ ”, “ _Maximize FPS under a power/energy
cap_ ”, ” _Minimize resource usage given an FPS requirement_ ”, _etc_.

###  2.5. Summary

In addition to the factors mentioned above, there can be other factors that
have non-trivial run-time impact, such as extreme core temperature (self-
protection mechanism), running multiple streaming applications. Those
situations make the run-time behavior even more unpredictable.

In this section, we show that:

  * $\bullet$

In optimization problems (without constraint), DEFAULT may deliver sub-optimal
performance and cause unnecessary resource occupation.

  * $\bullet$

The cross product of all the factors makes it difficult if not impossible to
derive closed-form analytical expressions for various metrics. Approaches that
rely on offline profiling are not feasible (overhead, scope, portability) for
solving such control problem.

The goal of this paper is to explore the idea of online control and develop a
generic methodology to control streaming applications at run time in a
principled fashion so that the objective is optimized while the constraint is
also met.

##  3\. Problem Formulation

In this section, we describe the formulation of the constrained optimization
problem we target to solve. We target general streaming applications but will
focus on those long-running ones. Applications might have distinct phases with
different optimal knob solutions, but the run-time behavior for successive
inputs within one phase is relatively stationary. We assume that each phase is
long enough ($>$ 1 minute) so that the knob setting provided by the sampling-
based online controller can be beneficial.

To keep the notation simple, since a minimization/maximization problem can be
easily converted to its opposite problem by multiplying a “-1”, we assume that
the objective metric is maximized and the constraint metric is kept under a
set point for demonstration purpose in this paper. We also assume that only
one constraint is used, and this can be easily extended to using no constraint
or more than one constraints.

Informally, the target control problem can be formulated as the following: for
each experiment, a user specifies a _run-time configuration_ , including an
application, its input(s), a device, a objective and a constraint. Within each
phase of the application’s execution, find the knob setting at run time in the
combined knob space of application and device, so that the objective is
maximized and the constraint is met. This can be formulated as the following
constrained optimization problem.

######  Problem Formulation 1.

Given a run-time configuration,

  * •

A streaming application $A$ with knob space $\kappa_{A}$

  * •

A device $D$ with knob space $\kappa_{D}$

  * •

An objective metric $f_{o}$

  * •

An constraint metric $f_{c}$ and set point $\epsilon$

  * •

An input $I$

Within each phase of the execution, find $k\in\kappa_{A}\times\kappa_{D}$ such
that

  * •

$o=f_{o}(A,D,I,k)$ is maximized

  * •

$c=f_{c}(A,D,I,k)<\epsilon$

##  4\. Sampling-based Online Controller

###  4.1. Choice of Online Control Strategy

####  4.1.1. Traditional Online Control

A traditional online control system can be represented as a _supervised_
feedback loop where the system monitors certain quantities of interest and
compares them to their reference values. Base on the difference, the
controller tunes knob settings in the direction of reducing the gap. Cruise
control is a typical online control system that adjusts acceleration by
looking at the difference between vehicle’s current speed and a reference
speed. Traditional control systems have already been used to adjust knob
settings in computer systems (Baek and Chilimbi, 2010; Khudia et al., 2015;
Pothukuchi et al., 2016; Rahmani et al., 2018; Ma et al., 2011; Fu et al.,
2011; Pei et al., 2020).

Though traditional methods have the advantage of formal reasoning (Levine,
1996), a function for updating knob settings based on the quantity gap is
needed. These functions typically rely on strong structural assumptions of
being linear, convex or deterministic. However, as discussed in Section 2.2,
the relationship between knob settings and performance can be nonlinear or
non-convex, with unknown function form. Plus the diversity in run-time
configurations, it is difficult to come up with a general tuning function.
Additionally, traditional online control requires a reference value to react.

####  4.1.2. Sampling-based Method

Sampling is a popular alternative approach when analytic methods aren’t
options. Instead of depending on gaps towards reference values, sampling is an
_unsupervised_ approach to pick knob settings only based on the performance
patterns of the already sampled points. During one sampling phase, a sequence
of knob settings are picked incrementally and strategically, of which each
knob setting is decided based on the statistics of all previous sampled
points. Unlike traditional control loop, sampling-based approach does not
require to know the behavior pattern of the whole knob spaces ahead of time in
order to pick a knob setting, so that it can adapt to any run-time
configuration. Therefore in this paper, sampling approach is chosen as our
basic online control strategy.

###  4.2. Controller Overview

The control flow of Sonic is presented Algorithm 1. The main idea of Sonic is
to utilize the beginning portion of each phase for sampling, aiming to find
the optimal knob setting for the remaining of that phase. An experiment starts
with initializing the target device and application (line 1 \- 2). Both the
application and the device report run-time statistics regarding the user-
specified objective and constraint.

Algorithm 1 Sampling-based online control loop for application $A$ executing
on device $D$, given input $i$, application knob space $\kappa_{A}$, device
knob space $\kappa_{D}$, objective metric $f_{o}$, constraint metric $f_{c}$
and set point $\epsilon$.

1:$D.\mathit{init()}$ $\triangleright$ Initialize device

2:$A.\mathit{start(D)}$ $\triangleright$ Start application on device

3:

4:$\mathit{new\\_phase}$ $\leftarrow$ True $\triangleright$ Start with a new
phase

5:while not $A.\mathit{finished()}$ do

6: if $\mathit{new\\_phase}$ then

7: $o,c,k_{best}$ $\leftarrow$
$\mathit{sampler}(\kappa_{A}\times\kappa_{D},f_{o},f_{c},\epsilon)$

8: $\mathit{setKnob(A,D,k_{best})}$

9: $\mathit{new\\_phase}$ $\leftarrow$ False

10: end if

11:

12: $o^{\prime},c^{\prime}$ $\leftarrow$ $\mathit{monitor}()$

13: if $\mathit{distance}(o,o^{\prime},c,c^{\prime})>\delta$ then

14: $\mathit{new\\_phase}$ $\leftarrow$ True

15: end if

16:end while

The main control loop consists of two components: 1) a _sampler_ , 2) a _phase
detector_. For each new phase, the sampler samples knob settings from the
Cartesian product of the application and the device knob space. Each sampled
knob setting is evaluated against the user-specified objective and constraint
metrics. At the end of one sampling phase, the knob setting that maximizes the
objective and meets the constraint is chosen and set for the following
execution (line 7 \- 8). The phase detector determines whether a new sampling
phase is needed by checking the difference between the current run-time
performance with the reference performance of the picked knob recorded during
the sampling phase (line 12 \- line 14). The design of the sampler and the
phase detector are described in Section 4.3 and Section 4.5.

###  4.3. Sampler

The flow of one sampling phase with $N$ rounds is shown in Figure 4. In order
not to add disturbance to application’s run-time behavior, the target
application and the sampler are deployed separately onto a client (target
device) and a server. The client and the server communicate by network
connections.

A new sampling phase is activated when a new experiment begins or the phase
detector identifies a new phase. Upon start, the client sets up a connection
with the server by sending the objective ($f_{o}$), the constraint
($f_{c},\epsilon$) and the knob space ($\kappa_{A}\times\kappa_{D}$) of the
current run-time configuration to the server. The first round of the sampling
phase starts by picking the first knob ($k_{1}$) on the server and sending it
back to the client. Upon receiving $k_{1}$, the client sets $k_{1}$ for the
application and the device, and measures its run-time statistics during one
measurement interval ($\sim$3 seconds in our experiments). After measuring
$k_{1}$, its objective and constraint metric values $o_{1}$ and $c_{1}$ are
sent back to the server. The streaming application keeps running with $k_{1}$
before it hears back from the server again. The server then calculates the
second knob setting and repeats the above procedure. After the $N^{th}$ knob
setting is measured, the knob setting that maximizes the objective and meets
the constraint will be picked and set for the remaining execution until a new
execution phase is detected.

ExecutingSet $k_{best}\in\\{k_{1},...,k_{n}\\}$$N^{th}$
intervalWaiting$k_{n}\in\kappa_{A}\times\kappa_{D}$Set $k_{n}$Pick $k_{n}$Pick
$k_{3}$$o_{2},c_{2}$$2^{nd}$ interval$k_{2}\in\kappa_{A}\times\kappa_{D}$Set
$k_{2}$Pick $k_{2}$$o_{1},c_{1}$$1^{st}$
interval$k_{1}\in\kappa_{A}\times\kappa_{D}$Set $k_{1}$Pick $k_{1}${$f_{o}$,
$f_{c}$, $\epsilon$, $\kappa_{A}\times\kappa_{D}$}Set up
connectionnew_phase?ExecutingWaitingApplicationSamplerClientServer Figure 4.
Sampling process

The strategy to sample the knob space is the key to find a competitive knob
setting. More number of samples generally means better knob setting selection,
but evaluating samples take time, and cause negative impact when evaluating
sub-optimal samples. More samples also lead to less time for the chosen knob
setting to be beneficial because applications have finite execution duration.
In this paper, only limited number of samples is allowed to be drawn
($N\ll|\kappa_{A}\times\kappa_{D}|$). $N$ is chosen to be between 8 and 12
given application’s overall execution duration and knob space size.

In order to get a good grasp of the target knob space with small number of
samples, we use _global optimization_ techniques to design the sampling
process. The key is to utilize the knowledge given by all previous samples,
while balancing the dilemma of _exploration_ and _exploitation_. Exploration
generally means probing under-sampled portions of the knob space, for the
purpose of getting out of local optimums and finding promising regions are yet
to be sampled. Exploitation, on the other hand, searches a known promising
region hoping to find a better sample than the samples already drawn from this
region. By leveraging exploitation and exploration trade-off, the sampler can
quickly identify unpromising regions and focus on promising regions only.
Prior works usually attempt to build the performance model of the whole knob
space, which is neither necessary nor cheap (Mishra et al., 2015, 2018).
Locating promising regions quickly is also beneficial to at least get a near
optimal solution because there can be plenty of knob settings near the pareto
frontier that yield similar performance (_e.g._ Figure 3).

Following the spirit of balancing exploration and exploitation, the whole
sampling phase of Sonic is divided into two stages: 1) _initialization_ ; 2)
_searching_.

####  4.3.1. Initialization

The initialization stage consists of the first $M$ of the total $N$ samples.
In this stage, Sonic aims to learn the knob space at a coarse scale, so all
sample choices follow the principle of exploration. Too few samples may cause
exploitation in wrong regions while too many initial samples may leads to
insufficient exploitation during the searching stage. Common choices of
sampling strategy for the initialization stage includes _random_ sampling and
_Latin hypercube_ sampling (LHS) (Helton and Davis, 2003). Taking a 2$D$ knob
space as example, each sample by LHS marks in which row and column the sample
was taken and subsequent samples avoids those marked rows and columns. In
contrast to naïve random sampling, LHS ensures that the set of picked knob
settings is representative of the real variability.

####  4.3.2. Searching

The remaining $M-N$ samples all belongs to the searching stage. The goal of
this stage is to find the knob setting that maximizes the objective while
meeting the constraint through exploration and exploitation. The searching
stage can be implemented in multiple ways, discussed in the following section.
The arrangement of initialization and searching in a sampling phase is shown
in Figure 5.

$0$$M$$N$InitializationSearching Figure 5. Sampling stages

###  4.4. Searching Strategies

####  4.4.1. Random sampling & LHS

Random sampling and LHS can also be used in the searching stage. However,
neither of them utilizes the history of sampled knob settings since their
samples can be generated given only random seed and knob space. These two
sampling strategies are not helpful to find the optimal knob setting because
no exploitation but only exploration is involved.

####  4.4.2. Regressors

The second searching strategy is built on machine learning regressors
(models). Popular types of regressors includes _linear regressors_ (Groß,
2012), _ensemble regressors_ (Svetnik et al., 2003; Friedman, 2002), and
_Gaussian process regressors_ (Williams and Rasmussen, 1996), _etc_. In a
sampling phase, a regressor is initialized on the data of all the sampled knob
settings of the initialization stage and is updated after each newly sampled
knob setting gets evaluated.

For each next knob setting in the searching stage, it is decided by first
predicting every unsampled knob setting’s objective and constraint value with
the most recently updated regressor, and then pick the one that maximizes the
objective metric while staying under the constraint. After this sampled
setting get evaluated, the regressor will get updated or rebuilt based on its
type. Since the number of samples is small, rebuilding the regressor does not
introduce noticeable overhead on a server. This process repeats for all $N-M$
samples.

In contrast to random sampling and LHS, regressors does utilize history
information. However, this strategy only has exploitation because it takes the
sample that maxes out the prediction at every round. When a new sample’s
performance aligns well with the regressor’s prediction, this new sample won’t
provide new information to update the regressor, causing the following sample
to be very close to this one. This leads to difficulty in getting out of local
minimums. Extra exploration is needed for better knob choices in the searching
stage.

####  4.4.3. Bayesian optimization (with unknown constraint)

Another searching strategy that fits our control problem well is Bayesian
optimization (Pelikan et al., 1999; Frazier, 2018; Shahriari et al., 2015).
Bayesian optimization is a sequential design strategy for derivative-free
global optimization of black-box functions that are expensive or lengthy to
evaluate (_e.g._ hyperparameter tuning for machine learning models (Feurer et
al., 2019; Snoek et al., 2012; Snoek et al., 2015)).

Abstractly, Bayesian optimization aims to solve the problem of maximizing a
target function $f:\mathbb{R}^{n}\to\mathbb{R}$ (_i.e._ objective metric
$f_{o}$) over a feasible set $X$ (_i.e._ knob space
$\kappa_{A}\times\kappa_{D}$). Bayesian optimization consists of two main
components: a probabilistic surrogate model –most commonly, a Gaussian process
regression (GP) –that models the objective function, and an acquisition
function (_e.g. Expected Improvement_ (Frazier, 2018)) for deciding where to
sample next.

After the initialization phase, Bayesian optimization construct a GP model
based the initial samples. Given a point $x$ in $X$, GP models $f(x)$ as a
normal distribution with mean $\mu_{x}$ and variance $\sigma^{2}_{x}$. The
more samples taken in one region, the smaller variance the points of this
region tends to have. When determining the next sample, the acquisition
function takes both the mean and the variance into consideration, in order to
tradeoff exploration (large variance) and exploitation (large mean). The GP
model is incrementally updated as new samples are evaluated.

Constraints can be incorporated into Bayesian optimization by scaling the
acquisition function at each $x$ with its probability of meeting the
constraint (Gelbart et al., 2014). For each constraint, a separate GP model is
built. The estimated probability of one point $x$ to meet a certain
constraint, $P(f_{c}(x)<\epsilon)$, is done by evaluating the _cumulative
distribution function_ at $x$ on that GP model.

####  4.4.4. Hybrid approach

Though Bayesian optimization fits the control challenge very well, our
experiments shows that it often requires a considerable number of samples to
converge to a good solution. For example, Bayesian optimization tends to focus
too much on exploration when taking 12 samples in a knob space that consists
of more than 1200 knob settings.

In order to encourage exploitation in Bayesian optimization, Sonic leverages a
hybrid strategy of combining regressors into Bayesian optimization to enforce
exploitation during the searching stage. We choose GP regressor because
Bayesian optimization’s underlying model is also GP.

$0$$M$$N$LHSGPBayesian optimizationGP Figure 6. Hybrid approach

The design of the hybrid approach is shown in Figure 6. The sampler starts
with Latin hypercube sampling (LHS) to perform the initial exploration of the
knob space. At the beginning of the searching stage, a GP regressor is built
on the initial samples and one next sample is generated using this GP
regressor. This sample can potentially boost the sampling quality of Bayesian
optimization because it provides an “okay” solution so that unpromising
regions are much easier to identify, leading to less exploration needed. For
the last sample, Bayesian optimization may still bias to exploration based on
its acquisition function but exploration is not beneficial at the last step.
In Sonic, we enforce exploitation by building a GP regressor based on all the
previous samples to generate the final knob setting sample.

####  4.4.5. Discussion

The primary reason to choose Bayesian optimization over other global
optimization techniques is that it construct a surrogate model incrementally
with very limited number of samples. Instead of assuming strong structural
assumptions of being linear and convex, Bayesian optimization assumes that
closer knob settings should have more similar performance by defining a
covariance function (_e.g. RBF kernel_
111https://en.wikipedia.org/wiki/Radial_basis_function, _Matérn kernel_
222https://en.wikipedia.org/wiki/Matérn_covariance_function). Global
optimization techniques such as simulated annealing (Van Laarhoven and Aarts,
1987), evolutionary algorithm (Back, 1996) assume no functional structure at
all. However, those techniques require much more samples to converge to a good
solution, which is not feasible for the control problem in this paper.

In the domain of reinforcement learning, upper confidence bound (UCB) and
Thompson sampling (Russo et al., 2017) are two popular heuristics to deal with
the “exploration Vs. exploitation” dilemma for problems like the multi-armed
bandit 333https://en.wikipedia.org/wiki/Multi-armed_bandit. However, those
techniques usually require multiple visits to every knob setting in order to
be effective, which far exceeds the number of samples allowed in this paper.

###  4.5. Phase Detection

After the sampling phase, the best knob setting among all the sampled ones
according to the user-specified objective and constraint is set for the
application and the device. In order to detect new phase, the client keeps
reporting run-time statistics to the server. For each measuring interval, the
phase detector compares the received run-time performance with the recorded
performance of the chosen knob setting during the sampling phase. If the
different is larger than 10% and lasts for two consecutive intervals, a new
sampling phase will be activated to search for a new solution.

###  4.6. Implementation Details

##### Standalone implementation

Sonic is designed and implemented independent of any application, device,
input, objective and constraints. Other than reporting performance at run
time, no change is needed for the target application and device.

##### Avoid duplicated samples

While it is rare to see duplicated samples in continuous knob space, it’s
common in discrete knob space because knob values are rounded to the nearest
discrete value. Duplicated samples waste precious attempts of drawing samples.
A nearby knob setting that has the highest acquisition value will be selected
when duplication happens.

##### Avoid system instability

In order to avoid the instability caused by turning on/off cores, we change
application’s core allocation only by setting its thread affinity. Since
changing thread affinity has delays and introduce extra noise into
measurements, knob settings are ordered so that the total distance between
successive knob settings are minimized (i.e. gray code encoding) during the
initialization stage. Furthermore, we also make the default knob setting be
the first sample point. In this way, it is possible to tackle minimization
problems with requirements represented by ratios.

##  5\. Experimental Evaluation

###  5.1. Experiment Setup

####  5.1.1. Benchmarks and Inputs.

In this work, Sonic is evaluated on two benchmark suites. The first one is the
PARSEC benchmark suite (Bienia et al., 2008), an open-source parallel
benchmark suite for emerging applications for evaluating parallel systems.
Benchmarks in PARSEC cover popular application domains including financial,
computer vision, physical modeling, future media, _etc_. All the applications
are implemented in C/C++. Inputs for different applications are included
respectively in this benchmark suite. Here is the list of parallel
applications that are regarded as streaming applications:

  * $\bullet$

_Bodytrack._ Bodytrack is a computer vision application that tracks a
markerless human body. It helps machines interact with environment better with
no aid provided. The inputs to Bodytrack are four sequences of frames fed from
4 cameras.

  * $\bullet$

_FaceSim._ FaceSim is a computer graphic application that simulates motions of
a human face for visualization purposes. It is used in video games and other
interactive animations require visualization of realistic faces in real time.
FaceSim takes a series of muscle activation as inputs and simulates on a face
model.

  * $\bullet$

_FluidAnimate._ FluidAnimate is a computer animation application that
simulates the underlying physics of fluid motion for real-time animation
purposes with smoothed particle hydrodynamics algorithm(Monaghan, 2005). It is
a highly demanded feature that allows significantly more realistic animations
in games and other media productions. The inputs to FluidAnimate is a list of
particles.

  * $\bullet$

_StreamCluster._ StreamCluster is a data mining application that computes an
approximation for the optimal clustering of a stream of data points. It is a
common problem in many fields like network security or pattern recognition.
StreamCluster takes a stream of multidimensional points as inputs.

  * $\bullet$

_Vips._ Vips is a image processing that applies a series of transformations to
an uncompressed image. Vips primarily targets huge professional images that
needs to be handled quickly.

  * $\bullet$

_X264._ X264 is a video encoder that encodes a sequence of images into the
H.264/MPEG-4 AVC compression format. It is widely used nowadays because
encoded videos are more network bandwidth and storage friendly.

The second set of benchmarks evaluated is a modified version of MLPerf
inference benchmark suite (Mattson et al., 2020) that covers the deep learning
aspect of streaming applications. In order to fit and execute on resource-
constrained devices, some of the applications are replaced with simpler
versions and smaller inputs. The selected applications include _ResNet8_ &
_ResNet50_ (He et al., 2016) (image classification), _MobileNet V2_ (Sandler
et al., 2018) (object detection), _visual wake words_ (_MobileNet V1_ (Howard
et al., 2017)), _speech recognition_ (convolutional neural network) and _text
classification_ (recurrent neural network). All the applications are
implemented and inferenced using Tensorflow (Abadi et al., 2016).

Due to the limitation of tuning application knobs due to their availability
(Section 5.6), application knobs are not controlled by default otherwise
explicitly mentioned.

####  5.1.2. Device and knob space.

We evaluate Sonic extensively on multiple platforms with different
architectures.

  * $\bullet$

_Odroid XU4_ is a 32-bit embedded platform with heterogeneous big.LITTLE core
architecture. Odroid XU4 is equipped with four Cortex-A15 cores and four
Cortex-A7 cores with frequency ranging from 0.2 to 2 GHz and 0.2 to 1.5 GHz
(0.1GHz steps) respectively. The power dissipation of the whole board is
measured by an external SmartPower2 device. The total knob space consists of
6384 knob settings (4 knobs).

  * $\bullet$

_Jetson TX2_ is a 64-bit embedded AI computing device that has four Cortex-A57
cores and two Denver2 cores that both operate from 0.345 to 2 GHz (0.15GHz
steps). The power dissipation of different components of these board is
measured through its internal i2C interface. Jetson’s knob space has 1694 knob
settings (4 knobs).

  * $\bullet$

_Intel Xeon Gold_ is a modern desktop system with two sockets and 32 physical
cores (64 thread cores). The power dissipation of this platform is measured by
pyRAPL, a software toolkit that uses the "Running Average Power Limit"
technology to measure the energy footprint of a host machine along
application’s execution. Only one knob with 64 settings are tuned on this
platform.

####  5.1.3. Metric.

The goal of an online controller is to find the best knob setting possible to
optimize a user-specified objective while staying under constraints if
specified. Due to the randomness and uncertainty involved in the sampling
process and measurement, we evaluate the effectiveness of an online controller
by calculating the expectation of the objective when the constraint is met
across independent runs.

$QoS$ (_Quality of service_) is defined as the ratio of the expected objective
between using an online controller and the optimal knob setting. $QoS$
expressions for maximization and minimization problems are given in Equation 1
and 2 respectively.

(1) $\displaystyle
QoS_{max}=\frac{E_{ctrl}[o|c<\epsilon]}{E_{op}[o|c<\epsilon]}\times 100\%$

(2) $\displaystyle
QoS_{min}=\frac{E_{op}[o|c<\epsilon]}{E_{ctrl}[o|c<\epsilon]}\times 100\%$

####  5.1.4. Experiment Design.

We compare Sonic with six other control settings. The implementation of SGD
regressor and random forest regressor are from the scikit-learn package
444https://scikit-learn.org/. Bayesian optimization’s implementation comes
from package Emukit555https://github.com/EmuKit/emukit(Paleyes et al., 2019).

  * $\bullet$

Race-to-Idle (DEFAULT)

  * $\bullet$

Random sampling

  * $\bullet$

Linear regressor: SGD

  * $\bullet$

Ensemble regressor: random forest

  * $\bullet$

Bayesian optimization

  * $\bullet$

Sonic: Bayesian optimization + GP regressor

  * $\bullet$

Optimal knob setting (ORACLE)

The length of one sampling phase is set to be 12 rounds on Odroid XU4, 10 on
Jetson TX2 and 8 on the desktop system according to their knob space size.
Discussions on the impact of the number of samples are discussed in Section
5.8. During the sampling phase, due to the fact that command taskset needs
time (0.5$\sim$1s) to stabilize, we set the measurement interval to 3 seconds,
in order to balance the length of one sampling interval and the measurement
noise. For fair comparison, the length of the sampling phase is normalized to
be 10% of the total execution time. $QoS$ is averaged over 40 independent runs
for each run-time configuration.

###  5.2. QoS on Odroid XU4

(a) $QoS$

(b) Power consumption

Figure 7. Application’s objective and constraint performance on Odroid XU4.

In this section, we show how Sonic is able to solve a commonly seen
constrained optimization problem: “Best performance under a power cap of 7 W”
on Odroid XU4 for all the applications with their provided inputs in the
benchmark suite.

####  5.2.1. Optimal knob settings.

Given this constrained optimization problem, online control would be
unnecessary if all applications’ optimal knob settings are the same on one
device. In Table 2, we display the optimal knob setting for each application.
For a total of 12 applications, almost every application has a unique optimal
knob setting on Odroid XU4, showing that learning the device alone is not
sufficient in solving such constrained optimization problems.

| Optimal knob setting (ORACLE)
---|---
_Platform_ | Odroid XU4 | Jetson TX2
_Objective_ |  Perf. $\uparrow$ |  Power $\downarrow$
_Constraint_ |  Power $<$ 7W | Perf. > 60% Default
Bodytrack | (4, 0, 1500, 200) | (4, 2, 1263, 1263)
FaceSim | (4, 2, 1400, 1500) | (4, 2, 961, 1263)
FluidAnimate | (4, 4, 1400, 1500) | (4, 2, 1263, 1263)
StreamCluster | (4, 4, 1200, 1500) | (4, 2, 961, 1152)
Vips | (2, 4, 1600, 900) | (2, 0, 1263, 345)
X264 | (3, 4, 1100, 1500) | (3, 2, 1263, 1416)
ResNet8 | (4, 4, 1400, 1500) | (3, 2, 1416, 1263)
ResNet50 | (4, 4, 1800, 1500) | (3, 2, 1263, 1263)
MobileNet V2 | (4, 2, 1800, 1500) | (3, 2, 1263, 1263)
Visual wake words | (4, 2, 1900, 1200) | (3, 0, 1722, 345)
Speech recognition | (4, 2, 1300, 1500) | (2, 2, 1263, 1263)
Text classification | (3, 0, 1800, 200) | (4, 0, 1722, 345)
Table 2. The optimal knob setting of each application on two platforms given
different objective and constraint. The first two numbers in the tuple
represents core numbers, and the last two represents core’s frequency.

####  5.2.2. Controller Comparison.

The $QoS$ and power dissipation of different controllers are shown in Figure
7a and 7b. For DEFAULT, all the applications have better performance than
ORACLE’s. However, the power dissipation of DEFAULT violate the 7 Watt
constraint for every application. Note that the power dissipation of DEFAULT
is different among applications, indicating different optimal knob settings
given a fixed power constraint.

When applying sampling-based online controllers, all are able to provide knob
settings that meet the 7-Watt constraint. The reason is that only knob
settings that meet constraint are considered at the end of each sampling
phase. As expected, random sampling has the worst performance because it does
not learn from previous samples. Regressor-based approach performs much better
than random sampling due to their aggressive exploitation. SGD regressor does
explore regions of interest effectively for many applications, but not
accurate enough due to its underline linear model because the relationship
between performance and knob settings may not be linear. Random forest
regressor is an ensemble regressor that fits a number of decision trees on
various subset of the samples and uses voting to improve the predictive
accuracy and control over-fitting. Since no assumption on linearity or
convexity, it performs better than the SGD regressor. In terms of the Bayesian
optimization controller, it does trade off exploitation and exploration during
the searching stage, but the knob space is relatively large comparing to the
number of samples, it fails provide enough exploitation to refine the
solutions from exploration.

Finally, after manually adding exploitation at the beginning and the end of
searching stage, Sonic is able to provide near-optimal results with only 12
samples in a knob space of 6384. It outperforms regressor-based approaches
because they lack exploration in the searching stage. Comparing with ORACLE,
using Sonic for streaming applications only incurs $\sim$4.8% $QoS$ loss.
Sonic achieves this without any prior knowledge of the run-time configuration.
This 4.8% $QoS$ loss is accounted by two parts: 1) knob settings evaluated
during the sampling phase are suboptimal; 2) the knob setting given by the
sampler may not be the global optimal.

####  5.2.3. Individual Experiments.

In Figure 8, we show the objective and constraint performance of each
individual run for all the applications. The average objective and constraint
performance of DEFAULT and ORACLE is represented by blue and green stars.
Blues dots and red dots represent independent experiments with Sonic and
random sampling respectively. Using Sonic significantly improves the objective
while still staying under the constraint. In addition, Sonic helps reduce the
performance variance of individual runs. Note that uncertainty is involved
throughout each experiment due to randomness and noise. Though Sonic can
generally boost performance, it is still possible to yield performance that is
worse than other baseline sampling methods in a single run.

In this experiment, we also observe that Sonic is not able to find the exact
global optimal knob settings all the time given large knob space, limited
number of samples and uncertainty. However, Sonic can still reach near-optimal
$QoS$ because there exist plenty of “good enough” knob settings near the
pareto frontier that have similar performance (_e.g._ Figure 3). In other
words, Sonic is an approximate run-time solution to the optimal knob setting
given any run-time configuration.

Figure 8. Performance distributions of 40 independent experiments.

###  5.3. QoS on Jetson TX2

In order to evaluate the ability to solve various constrained optimization
problems, we experiment with a different problem on Jetson TX2: “Least energy
consumption over a performance requirement of 60% DEFAULT’s performance”.

Due to lack of space, we cannot include figures in this submission. For this
problem, DEFAULT can easily meet the performance requirement but its $QoS$
(minimization problem) of energy is only 0.73. The $QoS$ for random sampling,
SGD regressor, random forest regressor and Bayesian optimization are 0.81,
0.89, 0.91 and 0.86 respectively. Finally, Sonic’s $QoS$ of energy is 0.94.
The corresponding optimal knob settings of this problem are included in Table
2.

###  5.4. QoS on Intel Xeon Gold

In Section 2.1, we motivate that DEFAULT, which occupies all the cores
automatically, are sub-optimal in terms of performance on a desktop platform
for deep learning frameworks. DEFAULT also results in unnecessary compute
resource waste.

After applying Sonic to those applications, a geometric mean of 1.32$\times$
speed up is achieved “for free” because no extra optimization or profiling is
applied to those models. What changed is just the run-time core number
selection. In addition, Sonic helps reduce resource utilization on this
desktop system by 78% on average, providing chances for other applications to
run on the same device. When comparing to ORACLE, the average $QoS$ loss is
5.5%.

Applications | DEFAULT | Sonic | Speedup | $QoS$
---|---|---|---|---
ResNet8 | 1409.01 | 1686.35 | 1.20x | 0.95
ResNet50 | 53.46 | 58.64 | 1.10x | 0.96
MobileNet_V2 | 124.57 | 134.46 | 1.08x | 0.97
Visual wake words | 245.11 | 255.26 | 1.04x | 0.96
Speech recognition | 2.06 | 3.73 | 1.81x | 0.87
Text classification | 124.92 | 246.95 | 1.98x | 0.96
Avg. $QoS$ Loss | - | - | 1.32x | 0.94
Table 3. Model inference FPS comparison between the DEFAULT and Sonic on a
2-socket 64-core machine.

###  5.5. Phase Detection

Some streaming applications may have different phases in one run. It can be
another streaming application entering the system, input change and so on. For
experimental purpose, we concatenate the “Big Buck Bunny” and the “Ducks take
off” video mentioned in Section 2.3. They have different performance patterns
due to their content difference. The run-time configuration can be described
as “Given certain input, run X264 on Odroid XU4 and find the knob setting that
optimizes power dissipation while keeping FPS over 2”.

The run-time FPS and power data in chronological order is shown in Figure 9.
Sonic starts with an sampling phase and one knob setting is picked after 10
samples evaluated. However, at round 30, input video changes to “Ducks take
off”. It contains photographic content so it needs more computation to encode.
The FPS suddenly drops under 2 and the phase detector activates a new sampling
phase after two measuring intervals. In the new phase, a knob setting with
much higher computation capacity and power is picked in order to meet the
constraint. This shows that X264 is able to minimize its power dissipation
while meeting the constraint despite the phase change occurs during the
execution when using Sonic.

(a) FPS

(b) Power dissipation

Figure 9. Executing X264 with input that contains phases on Odroid XU4 given a
constrained optimization problem: least power over a FPS requirement of 2.

###  5.6. Application & Device Knob Space

Application knobs are typically programmed to be set before an application
starts instead of changing adaptively. Though tuning application knobs are
shown to be beneficial in many prior works (Baek and Chilimbi, 2010; Khudia et
al., 2015; Pei et al., 2019; Sui et al., 2016), additional code change are
often required if application knobs need optimization in Sonic.

In this section, we test the impact of tuning application and device knobs
together for application text classification. We observe that batch size has
interesting impact on this application’s performance. Its default batch size
is 128 and the optimal knob setting on the desktop system is 7 cores. However,
if the batch size is set to 64 (256), the optimal performance is increased by
11% (7%) and only uses 3 (6) cores.

After incorporating batch size ($[32,64,128,256,512]$) as an additional knob
to the number of cores, the performance of text classification is furthur
improved by 8% (246.95 $\rightarrow$ 265.2), showing Sonic can tune both
application and device knobs.

###  5.7. Reuse previous samples

It is common to run the same run-time configuration for multiple time in
practice (_e.g._ debugging). In this paper, we also evaluate Sonic’s
effectiveness when previous experiments of the same run-time configuration are
available. In this case, sampling history of previous experiments are utilized
to construct a more accurate surrogate model for Bayesian optimization and
Gaussian process regressor. For the run-time configuration discussed in
Section 5.2, the average $QoS$ loss drops from 4.8% to 3.6% when one previous
experiment is available. When more than three previous runs are available, the
average $QoS$ loss drops below 3%.

###  5.8. Discussion

##### Controller Overhead.

Since the sample size is small in our experiments, model building or update
only takes $\sim$0.2s on the server. As application’s execution does not stall
during model building or update, this duration has no impact on system’s
performance.

##### Number of Samples.

In this paper, we normalize application’s total execution time to be $\sim$10x
of a sampling phase. In general, if the amount of workload is fixed, the more
samples, the better knob setting choice after a sampling phase, but there are
two concerns: 1) increased overhead by sampling and evaluating more sub-
optimal knobs; 2) less time for the picked knob to benefit the whole
execution. In this paper, we try to make it as small as possible for it to be
more practical while yielding reasonable results.

##### Granularity of Sampling Interval.

Given a fixed sampling phase duration, the shorter the sampling interval is,
the more samples can be evaluated but more noise is involved in each sample as
a cost. On the other hand, less samples can be taken when using a longer
interval, leading to less chance in finding a good solution.

##### Non-streaming applications.

Sonic may not be useful for non-streaming applications. If the target
application’s duration is short, there won’t be enough time for the sampling
strategy to be beneficial. If the application is long-running but contains
multiple small phases, sampling can be misleading.

##  6\. Related Work

##### Profiling-based approaches

Many systems have been proposed for solving constrained optimization problems
such as trading off program accuracy and performance (Baek and Chilimbi, 2010;
Ding et al., 2019; Haj-Ali et al., 2020; Hoffmann, 2015; Imes et al., 2015;
Khudia et al., 2015; Mishra et al., 2018, 2015; Mururu et al., 2021;
Pothukuchi et al., 2016; Rahmani et al., 2018; Sui et al., 2016). Most of them
rely on profiling data to construct models for control. For example, Rumba
(Khudia et al., 2015) applies lightweight error checks during application’s
execution to detect large approximation errors based on an offline error
predictor, and then fixes these errors by re-computation. Green (Baek and
Chilimbi, 2010) periodically execute the exact version of the target program
in parallel with a pre-defined approximate version and tunes knobs based on
their $QoS$ difference. NeuralVector (Haj-Ali et al., 2020) trains embeddings
for loop code snippets and tries to find the best parameters for openmp
_pragmas_ before execution. POET (Imes et al., 2015) collects power and
performance data exhaustively offline and use them during online control with
a PID-like controller. MIMO (Pothukuchi et al., 2016) trains offline multi-
input multi-output models and uses them in a traditional control loop.
Profiling-based approaches are infeasible to adapt to diverse run-time
configuration space.

##### Online approaches

Online approaches only utilize the information of the target application at
run time to tune knob settings (Ansel et al., 2012; Fang et al., 2014; Li and
Martinez, 2006; Pei et al., 2019, 2020; Petrica et al., 2013; Ponomarev et
al., 2001; Sridharan et al., 2013). For example, SiblingRivalry (Ansel et al.,
2012) and Flicker (Petrica et al., 2013) use evolutionary algorithms to find
the optimal hardware allocation for applications. Work (Fang et al., 2014)
utilizes simulated annealing to tune knobs. However, evolutionary algorithm
and simulated annealing take much more samples than Bayesian optimization does
to converge to a near-optimal result. SLAMbooster (Pei et al., 2019) applies
PID controller to hot domains such as Simultaneous Localization and Mapping.
However, such approach requires insights into application’s knob space ahead
of time.

##### Sampling-based control

Sampling-based control are primarily used in certain domains such as robotic
motion planning (Karaman and Frazzoli, 2011; Kingston et al., 2018; Liu et
al., 2010), where robots with many degrees of freedom try to find feasible
motion sequences autonomously under constraints for operations in realistic
tasks such as spacecraft logistics, health care, _etc_.

##### Bayesian optimization use cases

Bayesian optimization gets increasingly popular in solving sampling-
constrained problems such as hyperparameter tuning for machine (deep) learning
models (Feurer et al., 2019; Snoek et al., 2012; Snoek et al., 2015), neural
architecture search (Elsken et al., 2019; Kandasamy et al., 2018), robotic
control (Antonova et al., 2017; Calandra et al., 2016), chemical material
design (Griffiths and Hernández-Lobato, 2017; Li et al., 2017), _etc_.
Bayesian optimization also gets more attention in designing specific control
problems in recent years, including finding the best controller to certain
industrial process (Neumann-Brosig et al., 2019); tuning PID controllers for
HVAC systems (Fiducioso et al., 2019); modeling aircraft maneuver control
system (Kim et al., 2019), _etc_.

##  7\. Conclusion

In the paper, we propose an online controller to optimize streaming
applications entirely at run time. At the beginning of each phase of an
experiment, Sonic samples and evaluates knob settings sequentially to
determine a good one for the remaining execution according to a user-defined
constrained optimization problem. Sonic applies a hybrid approach of machine
learning regressors and Bayesian optimization to improve the choices of
samples. We demonstrate Sonic’s effectiveness by evaluating multiple
applications across multiple devices, and showing Sonic is able to find near-
optimal knob settings at run time.

## References

  * (1)
  * Aarseth and Aarseth (2003) Sverre J Aarseth and Sverre Johannes Aarseth. 2003.  _Gravitational N-body simulations: tools and algorithms_.  Cambridge University Press.
  * Abadi et al. (2016) Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. 2016\.  Tensorflow: A system for large-scale machine learning. In _12th $\\{$USENIX$\\}$ symposium on operating systems design and implementation ($\\{$OSDI$\\}$ 16)_. 265–283.
  * Ansel et al. (2012) Jason Ansel, Maciej Pacula, Yee Lok Wong, Cy Chan, Marek Olszewski, Una-May O’Reilly, and Saman Amarasinghe. 2012.  Siblingrivalry: online autotuning through local competitions. In _Proceedings of the 2012 international conference on Compilers, architectures and synthesis for embedded systems_. 91–100.
  * Antonova et al. (2017) Rika Antonova, Akshara Rai, and Christopher G Atkeson. 2017\.  Deep kernels for optimizing locomotion controllers. In _Conference on Robot Learning_. PMLR, 47–56.
  * Back (1996) Thomas Back. 1996\.  _Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms_.  Oxford university press.
  * Bader et al. (2013) David A Bader, Henning Meyerhenke, Peter Sanders, and Dorothea Wagner. 2013.  _Graph partitioning and graph clustering_. Vol. 588.  American Mathematical Society Providence, RI.
  * Baek and Chilimbi (2010) Woongki Baek and Trishul M Chilimbi. 2010.  Green: A framework for supporting energy-conscious programming using controlled approximation. In _Proceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation_. 198–209.
  * Bienia et al. (2008) Christian Bienia, Sanjeev Kumar, Jaswinder Pal Singh, and Kai Li. 2008.  The PARSEC benchmark suite: Characterization and architectural implications. In _Proceedings of the 17th international conference on Parallel architectures and compilation techniques_. 72–81.
  * Biswas et al. (2017) Swarnendu Biswas, Yan Pei, Donald S Fussell, and Keshav Pingali. 2017.  Capri: A Control System for Approximate Programs.  _arXiv preprint arXiv:1706.00767_ (2017).
  * Calandra et al. (2016) Roberto Calandra, André Seyfarth, Jan Peters, and Marc Peter Deisenroth. 2016.  Bayesian optimization for learning gaits under uncertainty.  _Annals of Mathematics and Artificial Intelligence_ 76, 1 (2016), 5–23.
  * Ding et al. (2019) Yi Ding, Nikita Mishra, and Henry Hoffmann. 2019.  Generative and multi-phase learning for computer systems optimization. In _Proceedings of the 46th International Symposium on Computer Architecture_. 39–52.
  * Elsken et al. (2019) Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. 2019\.  Neural architecture search: A survey.  _The Journal of Machine Learning Research_ 20, 1 (2019), 1997–2017.
  * Fang et al. (2014) Shuangde Fang, Zidong Du, Yuntan Fang, Yuanjie Huang, Yang Chen, Lieven Eeckhout, Olivier Temam, Huawei Li, Yunji Chen, and Chengyong Wu. 2014\.  Performance portability across heterogeneous socs using a generalized library-based approach.  _ACM Transactions on Architecture and Code Optimization (TACO)_ 11, 2 (2014), 1–25.
  * Feurer et al. (2019) Matthias Feurer, Aaron Klein, Katharina Eggensperger, Jost Tobias Springenberg, Manuel Blum, and Frank Hutter. 2019.  Auto-sklearn: efficient and robust automated machine learning.  In _Automated Machine Learning_. Springer, Cham, 113–134.
  * Fiducioso et al. (2019) Marcello Fiducioso, Sebastian Curi, Benedikt Schumacher, Markus Gwerder, and Andreas Krause. 2019\.  Safe contextual Bayesian optimization for sustainable room temperature PID control tuning.  _arXiv preprint arXiv:1906.12086_ (2019).
  * Frazier (2018) Peter I Frazier. 2018\.  A tutorial on Bayesian optimization.  _arXiv preprint arXiv:1807.02811_ (2018).
  * Friedman (2002) Jerome H Friedman. 2002\.  Stochastic gradient boosting.  _Computational statistics & data analysis_ 38, 4 (2002), 367–378.
  * Fu et al. (2011) Xing Fu, Khairul Kabir, and Xiaorui Wang. 2011.  Cache-aware utilization control for energy efficiency in multi-core real-time systems. In _2011 23rd Euromicro Conference on Real-Time Systems_. IEEE, 102–111.
  * Gelbart et al. (2014) Michael A Gelbart, Jasper Snoek, and Ryan P Adams. 2014\.  Bayesian optimization with unknown constraints.  _arXiv preprint arXiv:1403.5607_ (2014).
  * Griffiths and Hernández-Lobato (2017) Ryan-Rhys Griffiths and José Miguel Hernández-Lobato. 2017\.  Constrained bayesian optimization for automatic chemical design.  _arXiv preprint arXiv:1709.05501_ (2017).
  * Groß (2012) Jürgen Groß. 2012\.  _Linear regression_. Vol. 175.  Springer Science & Business Media.
  * Haj-Ali et al. (2020) Ameer Haj-Ali, Nesreen K Ahmed, Ted Willke, Yakun Sophia Shao, Krste Asanovic, and Ion Stoica. 2020\.  NeuroVectorizer: End-to-end vectorization with deep reinforcement learning. In _Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization_. 242–255.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016\.  Deep residual learning for image recognition. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 770–778.
  * Helton and Davis (2003) Jon C Helton and Freddie Joe Davis. 2003.  Latin hypercube sampling and the propagation of uncertainty in analyses of complex systems.  _Reliability Engineering & System Safety_ 81, 1 (2003), 23–69.
  * Hoffmann (2015) Henry Hoffmann. 2015\.  Jouleguard: Energy guarantees for approximate applications. In _Proceedings of the 25th Symposium on Operating Systems Principles_. 198–214.
  * Howard et al. (2017) Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. 2017\.  Mobilenets: Efficient convolutional neural networks for mobile vision applications.  _arXiv preprint arXiv:1704.04861_ (2017).
  * Imes et al. (2015) Connor Imes, David HK Kim, Martina Maggio, and Henry Hoffmann. 2015.  POET: a portable approach to minimizing energy under soft real-time constraints. In _21st IEEE Real-Time and Embedded Technology and Applications Symposium_. IEEE, 75–86.
  * Kandasamy et al. (2018) Kirthevasan Kandasamy, Willie Neiswanger, Jeff Schneider, Barnabas Poczos, and Eric Xing. 2018\.  Neural architecture search with bayesian optimisation and optimal transport.  _arXiv preprint arXiv:1802.07191_ (2018).
  * Karaman and Frazzoli (2011) Sertac Karaman and Emilio Frazzoli. 2011.  Sampling-based algorithms for optimal motion planning.  _The international journal of robotics research_ 30, 7 (2011), 846–894.
  * Khudia et al. (2015) Daya S Khudia, Babak Zamirai, Mehrzad Samadi, and Scott Mahlke. 2015.  Rumba: An online quality management system for approximate computing. In _Proceedings of the 42nd Annual International Symposium on Computer Architecture_. 554–566.
  * Kim et al. (2019) Dohyung Kim, Hyun-Shik Oh, and Il-Chul Moon. 2019.  Black-box modeling for aircraft maneuver control with bayesian optimization.  _International Journal of Control, Automation and Systems_ 17, 6 (2019), 1558–1568.
  * Kingston et al. (2018) Zachary Kingston, Mark Moll, and Lydia E Kavraki. 2018\.  Sampling-based methods for motion planning with constraints.  _Annual review of control, robotics, and autonomous systems_ 1 (2018), 159–185.
  * Levine (1996) William S Levine. 1996\.  _The control handbook_.  CRC press.
  * Li et al. (2017) Cheng Li, David Rubín de Celis Leal, Santu Rana, Sunil Gupta, Alessandra Sutti, Stewart Greenhill, Teo Slezak, Murray Height, and Svetha Venkatesh. 2017.  Rapid Bayesian optimisation for synthesis of short polymer fiber materials.  _Scientific reports_ 7, 1 (2017), 1–10.
  * Li and Martinez (2006) Jian Li and Jose F Martinez. 2006.  Dynamic power-performance adaptation of parallel computation on chip multiprocessors. In _The Twelfth International Symposium on High-Performance Computer Architecture, 2006._ IEEE, 77–87.
  * Liu et al. (2010) Libin Liu, KangKang Yin, Michiel van de Panne, Tianjia Shao, and Weiwei Xu. 2010.  Sampling-based contact-rich motion control.  In _ACM SIGGRAPH 2010 papers_. 1–10.
  * Ma et al. (2011) Kai Ma, Xue Li, Ming Chen, and Xiaorui Wang. 2011\.  Scalable power control for many-core architectures running multi-threaded applications. In _2011 38th Annual International Symposium on Computer Architecture (ISCA)_. IEEE, 449–460.
  * Mattson et al. (2020) Peter Mattson, Vijay Janapa Reddi, Christine Cheng, Cody Coleman, Greg Diamos, David Kanter, Paulius Micikevicius, David Patterson, Guenther Schmuelling, Hanlin Tang, et al. 2020\.  MLPerf: An industry standard benchmark suite for machine learning performance.  _IEEE Micro_ 40, 2 (2020), 8–16.
  * Mishra et al. (2018) Nikita Mishra, Connor Imes, John D Lafferty, and Henry Hoffmann. 2018.  Caloree: Learning control for predictable latency and low energy.  _ACM SIGPLAN Notices_ 53, 2 (2018), 184–198.
  * Mishra et al. (2015) Nikita Mishra, Huazhe Zhang, John D Lafferty, and Henry Hoffmann. 2015.  A probabilistic graphical model-based approach for minimizing energy under performance constraints.  _ACM SIGARCH Computer Architecture News_ 43, 1 (2015), 267–281.
  * Monaghan (2005) Joe J Monaghan. 2005\.  Smoothed particle hydrodynamics.  _Reports on progress in physics_ 68, 8 (2005), 1703\.
  * Mururu et al. (2021) Girish Mururu, Chao Chen, Chris Porter, Santosh Pande, and Ada Gavrilovska. 2021.  Compiler-Guided Throughput Scheduling for Many-core Machines.  _arXiv preprint arXiv:2103.06647_ (2021).
  * Neumann-Brosig et al. (2019) Matthias Neumann-Brosig, Alonso Marco, Dieter Schwarzmann, and Sebastian Trimpe. 2019.  Data-efficient autotuning with bayesian optimization: An industrial control study.  _IEEE Transactions on Control Systems Technology_ 28, 3 (2019), 730–740.
  * Paleyes et al. (2019) Andrei Paleyes, Mark Pullin, Maren Mahsereci, Neil Lawrence, and Javier González. 2019.  Emulation of physical processes with Emukit. In _Second Workshop on Machine Learning and the Physical Sciences, NeurIPS_.
  * Pei et al. (2019) Yan Pei, Swarnendu Biswas, Donald S Fussell, and Keshav Pingali. 2019.  SLAMBooster: An Application-Aware Online Controller for Approximation in Dense SLAM. In _2019 28th International Conference on Parallel Architectures and Compilation Techniques (PACT)_. IEEE, 296–310.
  * Pei et al. (2020) Yan Pei, Swarnendu Biswas, Donald S Fussell, and Keshav Pingali. 2020.  A Methodology for Principled Approximation in Visual SLAM. In _Proceedings of the ACM International Conference on Parallel Architectures and Compilation Techniques_. 373–386.
  * Pelikan et al. (1999) Martin Pelikan, David E Goldberg, Erick Cantú-Paz, et al. 1999\.  BOA: The Bayesian optimization algorithm. In _Proceedings of the genetic and evolutionary computation conference GECCO-99_ , Vol. 1. Citeseer, 525–532.
  * Petrica et al. (2013) Paula Petrica, Adam M Izraelevitz, David H Albonesi, and Christine A Shoemaker. 2013.  Flicker: A dynamically adaptive architecture for power limited multicore systems. In _Proceedings of the 40th Annual International Symposium on Computer Architecture_. 13–23.
  * Ponomarev et al. (2001) Dmitry Ponomarev, Gurhan Kucuk, and Kanad Ghose. 2001\.  Reducing power requirements of instruction scheduling through dynamic allocation of multiple datapath resources. In _Proceedings. 34th ACM/IEEE International Symposium on Microarchitecture. MICRO-34_. IEEE, 90–101.
  * Pothukuchi et al. (2016) Raghavendra Pradyumna Pothukuchi, Amin Ansari, Petros Voulgaris, and Josep Torrellas. 2016.  Using multiple input, multiple output formal control to maximize resource efficiency in architectures. In _2016 ACM/IEEE 43rd Annual International Symposium on Computer Architecture (ISCA)_. IEEE, 658–670.
  * Rahmani et al. (2018) Amir M Rahmani, Bryan Donyanavard, Tiago Mück, Kasra Moazzemi, Axel Jantsch, Onur Mutlu, and Nikil Dutt. 2018.  SPECTR: Formal supervisory control and coordination for many-core systems resource management. In _Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems_. 169–183.
  * Russo et al. (2017) Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. 2017.  A tutorial on thompson sampling.  _arXiv preprint arXiv:1707.02038_ (2017).
  * Sandler et al. (2018) Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen. 2018.  Mobilenetv2: Inverted residuals and linear bottlenecks. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 4510–4520.
  * Shahriari et al. (2015) Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando De Freitas. 2015.  Taking the human out of the loop: A review of Bayesian optimization.  _Proc. IEEE_ 104, 1 (2015), 148–175.
  * Snoek et al. (2012) Jasper Snoek, Hugo Larochelle, and Ryan P Adams. 2012\.  Practical bayesian optimization of machine learning algorithms.  _Advances in neural information processing systems_ 25 (2012).
  * Snoek et al. (2015) Jasper Snoek, Oren Rippel, Kevin Swersky, Ryan Kiros, Nadathur Satish, Narayanan Sundaram, Mostofa Patwary, Mr Prabhat, and Ryan Adams. 2015.  Scalable bayesian optimization using deep neural networks. In _International conference on machine learning_. PMLR, 2171–2180.
  * Sridharan et al. (2013) Srinath Sridharan, Gagan Gupta, and Gurindar S Sohi. 2013\.  Holistic run-time parallelism management for time and energy efficiency. In _Proceedings of the 27th international ACM conference on International conference on supercomputing_. 337–348.
  * Sui et al. (2016) Xin Sui, Andrew Lenharth, Donald S Fussell, and Keshav Pingali. 2016\.  Proactive control of approximate programs.  _ACM SIGPLAN Notices_ 51, 4 (2016), 607–621.
  * Svetnik et al. (2003) Vladimir Svetnik, Andy Liaw, Christopher Tong, J Christopher Culberson, Robert P Sheridan, and Bradley P Feuston. 2003.  Random forest: a classification and regression tool for compound classification and QSAR modeling.  _Journal of chemical information and computer sciences_ 43, 6 (2003), 1947–1958.
  * Van Laarhoven and Aarts (1987) Peter JM Van Laarhoven and Emile HL Aarts. 1987.  Simulated annealing.  In _Simulated annealing: Theory and applications_. Springer, 7–15.
  * Williams and Rasmussen (1996) Christopher KI Williams and Carl Edward Rasmussen. 1996.  Gaussian processes for regression.  (1996).