1

# Cello: Efficient Computer Systems Optimization with Predictive Early
Termination and Censored Regression

Yi Ding  MIT CSAILCambridge, MAUSA<EMAIL_ADDRESS>,  Alex Renda  MIT
CSAILCambridge, MAUSA<EMAIL_ADDRESS>,  Ahsan Pervaiz  University of
ChicagoChicago, ILUSA<EMAIL_ADDRESS>,  Michael Carbin  MIT
CSAILCambridge, MAUSA<EMAIL_ADDRESS>and  Henry Hoffmann  University of
ChicagoChicago, ILUSA<EMAIL_ADDRESS>
###### Abstract.

Sample-efficient machine learning (SEML) has been widely applied to find
optimal latency and power tradeoffs for configurable computer systems. Instead
of randomly sampling from the configuration space, SEML reduces the search
cost by dramatically reducing the number of configurations that must be
sampled to optimize system goals (e.g., low latency or energy). Nevertheless,
SEML only reduces one component of cost—the total number of samples
collected—but does not decrease the cost of collecting each sample.
Critically, not all samples are equal; some take much longer to collect
because they correspond to slow system configurations. This paper present
Cello, a computer systems optimization framework that reduces sample
collection costs—especially those that come from the slowest configurations.
The key insight is to predict ahead of time whether samples will have poor
system behavior (e.g., long latency or high energy) and terminate these
samples early before their measured system behavior surpasses the termination
threshold, which we call it _predictive early termination_. To predict the
future system behavior accurately before it manifests as high runtime or
energy, Cello uses censored regression to produces accurate predictions for
running samples. We evaluate Cello by optimizing latency and energy for Apache
Spark workloads. We give Cello a fixed amount of time to search a combined
space of hardware and software configuration parameters. Our evaluation shows
that compared to the state-of-the-art SEML approach in computer systems
optimization, Cello improves latency by 1.19$\times$ for minimizing latency
under a power constraint, and improves energy by 1.18$\times$ for minimizing
energy under a latency constraint.

††copyright: none

##  1\. Introduction

Optimizing latency and power tradeoffs (e.g., minimizing latency while meeting
a power constraint) is crucial to modern computer systems. To achieve these
goals, hardware and software configuration parameters—e.g., number of cores,
core frequency, memory management, etc.—are exposed to users such that both
the underlying system and application can be configured to operate at an
optimal point in the latency-power tradeoff space (Xu et al., 2015; Colin et
al., 2018; Blöcher et al., 2021). Selecting an optimal configuration, however,
is a challenging problem as the size and complexity of the configuration space
require intelligent methods to avoid local optima (Mishra et al., 2015, 2018).

Sample Efficiency. Machine learning techniques have proven effective solutions
to optimizing computer system configurations (Herodotou et al., 2020; Penney
and Chen, 2019; Zhang and Huang, 2019). While a variety of such methods have
been applied, they require a large sampling effort; i.e., generating a
candidate configuration, running it to measure its high-level _system
behavior_ (e.g., latency and energy), and then building a model to predict the
system behavior of unsampled configurations. Among these techniques, an
appealing direction is sample-efficient machine learning (SEML), which reduces
the number of samples required to find the optimal configuration (Ïpek et al.,
2006; Alipourfard et al., 2017; Ding et al., 2019; Nardi et al., 2019; Patel
and Tiwari, 2020). A powerful example of SEML is Bayesian optimization
(Alipourfard et al., 2017; Nardi et al., 2019; Patel and Tiwari, 2020).
Bayesian optimization intelligently selects samples that provide the most
information for the model updates, and this intelligence reduces the number of
samples required to find the configuration that produces optimal systems
behavior. Besides Bayesian optimization, other sample-efficient optimizers
have been proposed for specific systems problems (Ïpek et al., 2006; Petrica
et al., 2013; Venkataraman et al., 2016; Ding et al., 2019).

Cost of Samples. SEML reduces the cost for computer systems optimization by
reducing the number of samples to find the optimal configuration. There is,
however, a significant additional cost: the time to collect each sample.
Critically in computer systems optimization, the samples corresponding to the
worst configurations take a much longer time to collect than others. For
instance, a slow configuration can take 10$\times$ the execution time of the
optimal configuration on the same Apache Spark workload (Yu et al., 2018).
Thus, there is a need for reducing the cost of individual sample collection
and not just the total number of samples.

Compute Efficiency. We note that achieving _compute efficiency_ for SEML
should reduce both the number of samples and the cost of collecting each
sample. To reduce the cost of collecting each sample, prior work replies on
_measured early termination_ that terminates samples when the measured system
behavior surpasses a given _termination threshold_ (e.g., a target latency)
(Hutter et al., 2013; Eggensperger et al., 2020); and this threshold typically
distinguishes between good and poor system behavior. For instance, if the
termination threshold is 40 seconds and the true latency of the workload
running at a particular configuration is 60 seconds, measured early
termination techniques will terminate samples when their runtime surpasses 40
seconds. However, this approach still pays the cost of waiting for the sample
to hit the termination threshold, which is compute-inefficient.

###  1.1. Compute Efficiency with Cello

In contrast to prior work based on measured early termination, we introduce
_predictive early termination_. This approach monitors running samples,
predicts whether the sample will surpass the threshold, and terminates such
unpromising samples before they are measured to be poor (e.g., long latency or
high energy).

To apply this insight, we present Cello, an efficient computer systems
optimization framework that augments Bayesian optimization with predictive
early termination. To enable predictive early termination, Cello must predict,
both early and accurately, whether a running sample will perform poorly; i.e.,
eventually exceed the termination threshold, which Cello sets as the best
measured behavior. To do so, Cello applies _censored regression_ , a
prediction approach that is designed to model missing data (i.e., samples that
are measured but not finish running) more accurately than techniques that do
not account for the missing data (Miller and Halpern, 1982; Portnoy, 2003).
Formally, _censoring_ is a condition where a measurement is only partially
observable due to a given censoring threshold (Powell, 1986). Instead of
observing the true measurement, in censored regression we only know that it
exceeded the censoring threshold. For example, if the censoring threshold is
30 seconds, the true latency of a sample that keeps running after 30 seconds
is not observed at this moment because it is censored. Although its true
latency is unknown at this moment, we know that it must be at least 30
seconds. The intuition behind censored regression is to model the censored and
uncensored data (in our case, the samples that are still running and finished
running before the termination threshold) differently, and then combine these
models in a way that produces more accurate predictions than standard
regression that does not account for censoring (section 5.3).

###  1.2. Summary of Results

We implement Cello and test it on twelve Apache Spark workloads from HiBench
(Huang et al., 2010). We compare Cello to state-of-the-art Bayesian
optimization techniques and different variants of early termination (including
both measured and predictive). We give each method a fixed time to search a
combined space of hardware and software configuration parameters and find
solutions for two systems optimization problems: (1) minimizing latency under
a power constraint (Latency-Under-Power) and (2) minimizing energy under a
latency constraint (Energy-Under-Latency). Our evaluation shows a complete
breakdown of results for different constraints and workloads for Cello and
prior approaches to SEML. Compared to the prior work, we find that on average
Cello (section 5.1):

  * •

improves latency by 1.19$\times$ for Latency-Under-Power and energy by
1.18$\times$ for Energy-Under-Latency compared to Bliss (Roy et al., 2021),
the state of the art SEML approach for computer systems optimizations;

  * •

improves latency by 1.24–1.61$\times$ for Latency-Under-Power and energy by
1.24–1.34$\times$ for Energy-Under-Latency compared to other SEML approaches
that use measured early termination;

  * •

improves latency by 1.90$\times$ for Latency-Under-Power and energy by
2.35$\times$ for Energy-Under-Latency compared to the SEML approach that uses
predictive early termination based on standard regression, rather than Cello’s
censored regression.

###  1.3. Contributions

This paper presents the following contributions:

  * •

Introducing predictive early termination, based on predicted—rather than
measured—behavior which allows SEML to terminate samples much earlier than
prior work.

  * •

Introducing censored regression to predict the system behavior of samples and
enable predictive early termination. To the best of our knowledge this is the
first demonstration of the benefits of censored regression for computer
systems optimization.

  * •

Presenting Cello, an efficient computer system optimization framework that
combines predictive early termination and censored regression to reduce the
cost of applying machine learning methods for systems optimization while still
improving systems outcomes.

Incomplete data are often prevalent in computer systems optimization. To the
best of our knowledge, Cello is the first framework that reduces the time cost
per sample by intelligently taking advantages of incomplete data via censored
regression and predictive early termination. Our work provides a foundation on
which the computer systems community can build new efficient frameworks that
process incomplete data in computer systems research.

##  2\. Background and Related Work

This section discusses related work on machine learning for configuration
optimization (section 2.1), early termination (section 2.2), and machine
learning for prediction (section 2.3).

###  2.1. Computer Systems Configuration Optimization

Modern computer systems are increasingly configurable (Vishwanath and
Nagappan, 2010; Xu et al., 2015). These configuration parameters have a large
effect on high-level systems behavior including throughput (Belay et al.,
2014), latency (Van Aken et al., 2017), and energy (Mishra et al., 2015; Ding
et al., 2019). Furthermore, the number of parameters and their complex
interactions create a large search space with many local optima (Deng et al.,
2017; Mishra et al., 2018), which present challenges for heuristics (Mishra et
al., 2015, 2018). To optimize systems behavior, machine learning techniques
have been applied to search this configuration space for high-performing
configurations.

Sample-efficient machine learning (SEML) represents a class of machine
learning techniques that reduce the number of samples required to find the
optimal configuration (Settles, 2011). SEML approaches work iteratively, using
their current predictions to determine which new configuration to sample and
then update their model based on the observed behavior of that sample.
Bayesian optimization is a typical SEML approach that has been applied in
various domains (Frazier, 2018). For example, Cherrypick uses Bayesian
optimization to find optimal cloud configurations (Alipourfard et al., 2017).
CLITE uses Bayesian optimization to schedule workloads for datacenters (Patel
and Tiwari, 2020). HyperMapper applies Bayesian optimization to tune compilers
(Nardi et al., 2019). Bliss uses Bayesian optimization to tune parallel
applications on large-scale systems (Roy et al., 2021). Additional works
propose problem-specific SEML approaches, including multi-phase sampling (Ding
et al., 2019), optimal experiment design in Ernest (Venkataraman et al.,
2016), and fractional factorial design in Flicker (Petrica et al., 2013).

An example of cost per sample. The SEML approaches above reduce the cost of
computer systems optimization by reducing the number of samples. However,
there is also the opportunity to reduce the cost of each sample itself. To
demonstrate this, we compare the number of samples and cost per sample between
random sampling (not a SEML approach), Bayesian optimization, and Cello. We
run the Apache Spark workload als from HiBench on a cloud computing system
(details in section 4.2) with the goal of finding the configuration with the
lowest latency. Figure 1 compares the time cost per sample between random
sampling, Bayesian optimization, and Cello. We observe that the time costs per
sample from random sampling and Bayesian optimization approaches are roughly
the same, which validates that Bayesian optimization does not reduce the time
cost of collecting samples Cello, however, focuses on reducing the cost of
each sample. For achieving the same optimal latency, Cello only needs 7.12s
per sample, which is a 44% reduction in the time cost per sample compared to
Bayesian optimization.

Figure 1. Comparing cost per sample between random sampling (RS), Bayesian
optimization (BO), and Cello on the als workload.

###  2.2. Early Termination

_Early termination_ aborts poor performing configurations before they finish,
leaving time and resources to sample more promising configurations. This
approach has been applied to speed up hyperparameter optimization and deep
neural network (DNN) training. For hyperparameter optimization, HyperBand (Li
et al., 2017) and HyperDrive (Rasley et al., 2017) randomly generate a large
number of configurations at one time rather than intelligently sampling a
small number of configurations iteratively, which is much more compute-
intensive than SEML approaches. For DNN training, prior work predicts future
behavior using learning curves—i.e., the learning accuracy of an algorithm as
a function of its training time (Swersky et al., 2014; Domhan et al., 2015;
Klein et al., 2017). However, Bayesian optimization does not have an analogous
structure to learning curves, so we need a different mechanism for predicting
future behavior and in this work we demonstrate the use of censored regression
for this prediction problem.

For Bayesian optimization, Hutter et al. (2013) and Eggensperger et al. (2020)
apply measured early termination to terminate samples when their measured
behavior reaches the termination threshold. Cello, however, uses predictive
early termination to terminate samples when their predicted behavior—obtained
from censored regression—reaches the termination threshold. This prediction
step enables much earlier termination and thus saves more time for Cello to
explore more samples compared to prior work (section 5.1,section 5.4).

###  2.3. Machine Learning for Behavior Prediction

A large body of machine learning techniques have been applied to predict high-
level system behavior for resource management (Ponomarev et al., 2001; Choi
and Yeung, 2006; Lee et al., 2007, 2008; Martinez and Ipek, 2009; Snowdon et
al., 2009; Cochran et al., 2011; Zhang et al., 2012; Sridharan et al., 2013;
Petrica et al., 2013; Oliner et al., 2013; Zhu and Reddi, 2013; Mishra et al.,
2015, 2018; Ding et al., 2019; Zhang et al., 2020; Shi et al., 2019, 2021) and
scheduling (Tesauro, 2007; Winter et al., 2010; Van Craeynest et al., 2012;
Delimitrou and Kozyrakis, 2014, 2013). The general strategy is to use low-
level, readily-available metrics (e.g., branch miss rates, IPC) to predict
high-level behavior (e.g., throughput or latency) (Lee and Brooks, 2006; Ipek
et al., 2008; Bitirgen et al., 2008; Snowdon et al., 2009; Dubach et al.,
2010; Zhu and Reddi, 2013; Teran et al., 2016; Peled et al., 2019; Ding et
al., 2019; Bhatia et al., 2019; Garza et al., 2019; Bera et al., 2021; Peled
et al., 2015). For example, Lee and Brooks (2006, 2010) apply linear
regression to predict performance and power. Delimitrou and Kozyrakis (2013,
2014) use collaborative filtering to predict job performance for datacenter
workloads. Mishra et al. (2015, 2018) use hierarchical Bayesian models to
predict latency and energy. Garza et al. (2019) and Bhatia et al. (2019) use
perceptrons to predict branch and prefetcher behavior.

Figure 2. Comparing prediction accuracy between standard regression (SR) and
censored regression (CR) in terms of mean squared error (MSE) on als. Figure
3. Cello workflow. White Box A is Bayesian optimization, and shaded Boxes B to
D are unique to Cello.

Most prior work achieves high prediction accuracy relying on a training set
that includes samples in a wide range of behavior. Bayesian optimization,
however, accumulates samples as more iterations finish. Thus, there are
insufficient samples as training data in the early stage of Bayesian
optimization, and these samples are likely to lie in the range of poor values
(Rasley et al., 2017). Directly training models on these samples will predict
running samples to be poor, which leads to a increasing number of predictions
of poor values and thus inaccurate sample selection for the next round (Roy et
al., 2021). To overcome this inaccuracy, Cello utilizes knowledge of the
current elapsed latency and energy at each time interval to generate more
accurate predictions through censored regression.

An example of prediction accuracy. To demonstrate the benefits of censored
regression, we run Bayesian optimization on the als workload and predict each
new configuration’s latency with different predictors: standard and censored
regression. We use gradient boosting trees as our standard regression model
due to its high predictive accuracy (Chen and Guestrin, 2016). We monitor the
workload execution and predict its latency at each time interval (see section
4.4). The censoring threshold for censored regression is the elapsed latency
observed at each time interval. We compute the mean squared error (MSE)
between predicted latency and true latency. Figure 2 shows the results, where
the y-axis represents the average MSE over all time intervals, lower is
better. Censored regression has 2.84$\times$ lower MSE than standard
regression. This example illustrates that censored regression is effective at
improving prediction accuracy when training on samples collected from Bayesian
optimization. The accurate prediction from censored regression is fundamental
to predictive early termination in Cello, as we describe next.

##  3\. Cello Design

Cello is an efficient computer systems optimization framework that reduces the
cost of samples by predictive early termination which we enable with censored
regression. Figure 3 illustrates the Cello design. After a configuration is
selected from Bayesian optimization ( A), Cello starts monitoring it ( B), and
records the current latency and energy at regular time intervals. At each
interval, Cello checks if the configuration has finished running (Branch 1).
If so, Cello goes back to Bayesian Optimization ( A) for the next round.
Otherwise, Cello predicts the final latency or energy using the Censored
Regressor ( C). Then, Cello sends the predictions to Predictive Early
Termination ( D) to determine whether the configuration should be terminated
based on its prediction (Branch 2). If the prediction is worse than the
existing best from the collected samples, Cello terminates this sample
collection and goes to the next round. Otherwise, the configuration continues
running until the next time interval. When the configuration finishes, Cello
records the data for this sample and goes to the next Bayesian optimization
round ( A).

The remainder of this section first provides a brief set of definitions to
establish the core concepts, and then describe Cello’s design, and concludes
with the Cello’s application to computer systems optimization problems.

###  3.1. Definitions

Cello’s input includes a workload and a list of configuration parameters over
which to optimize. The goal is to find a configuration that meets the goal of
systems optimization—e.g., the configuration that minimizes latency under a
power constraint. We assume that Cello can measure high-level systems behavior
including latency, power, and energy at different time intervals, which is
reasonable since many software frameworks (e.g., Apache Spark (spa, ),
MapReduce (map, ), Cassandra (cas, ), HBase (hba, ), etc) already have this
capability as they log systems behavior at regular time intervals.

Workload.:

A program that runs on a computer system.

Configuration.:

A configuration ${\mathbf{x}}_{i}$ is a $p$-dimensional vector where $p$ is
the number of configuration parameters:

(1) $\displaystyle{\mathbf{x}}_{i}=[x_{i1},x_{i2},\cdots,x_{ip}],$

As SEML sequentially explores configurations, we use index $i$ to refer to the
sequence of configurations explored; ${\mathbf{x}}_{i}$ is the $i$-th
configuration. $x_{ij}$ refers to an individual parameter setting, the $j$-th
parameter, $j\in[p]$. A configuration parameter can either be a hardware
feature such as the number of cores, core frequency, etc, or a software
feature such as execution behavior, networking, scheduling, etc. A complete
list of configuration parameters studied in this paper is in Table 1.

System behavior.:

The high-level system behavior that Cello monitors and optimizes. In this
paper, we use latency (i.e., execution time of a workload), power, and energy
consumption as system behavior, depending on the specific problem.

Sample.:

Given the above, a sample is the pair of a configuration along with its system
behavior.

Termination threshold.:

The termination threshold is a latency or energy value that is used to
determine whether to terminate a sample early or not. Unlike prior approaches
(Hutter et al., 2013; Eggensperger et al., 2020), Cello dynamically updates
this threshold based on the best latency or energy seen so far.

Next, we will describe each labeled box in Figure 3.

###  3.2. Bayesian Optimization

Cello uses Bayesian optimization ( A) to select the configuration at each
round (Settles, 2011). Formally,

(2)
$\displaystyle{\mathbf{x}}^{\star}=\operatorname*{arg\,min}_{{\mathbf{x}}\in\mathbb{R}^{p}}f({\mathbf{x}}),$

where $f(\cdot)$ is the unknown underlying function which is being optimized.
There are two main components in Bayesian optimization: the surrogate model
and the acquisition function. The surrogate model learns the unknown
underlying function $f(\cdot)$. The acquisition function selects the most
informative configuration at each round. We describe these two components as
follows.

####  3.2.1. Surrogate Model

Bayesian optimization requires a surrogate model that produces uncertainty
estimates, and Cello requires the surrogate model that can handle different
variable modalities (continuous, discrete, etc.) that exist in configuration
space. In this paper, we use random forest as our surrogate model as it
satisfies both of these requirements (Hutter et al., 2011; Nardi et al.,
2019). As an ensemble learning method, random forest constructs a multitude of
decision trees, where its predictions are the average of the output from its
component trees. The uncertainty, therefore, can be obtained by taking the
standard deviation from the predictions of each tree (Breiman, 2001). For
configuration ${\mathbf{x}}_{i}$, we denote $\mu_{i}(\cdot)$ and
$\sigma_{i}(\cdot)$ as its predictive mean and uncertainty from the surrogate
model.

####  3.2.2. Acquisition Function

After the surrogate model outputs predictive mean and uncertainty for the
unseen configurations, Cello needs an acquisition function to select the best
configuration to sample. A good acquisition function should balance the
tradeoffs between exploration and exploitation. For Cello, we chose the
expected improvement (EI) acquisition function, which has been demonstrated to
perform well in configuration search (Alipourfard et al., 2017; Patel and
Tiwari, 2020; Roy et al., 2021). EI selects the configuration that would have
the highest expected improvement over the best observed system behavior so
far. Assuming $m_{i}$ is the best observed system behavior at the $i$-th
round, we have

$\displaystyle{\mathbf{x}}_{i}=\operatorname*{arg\,max}_{{\mathbf{x}}\in\mathbb{R}^{p}}\begin{cases}\left(\mu_{i}({\mathbf{x}})-m_{i}\right)\Phi(Z)+\sigma_{i}({\mathbf{x}})\phi(Z),&\text{if
}\sigma_{i}({\mathbf{x}})>0\\\ 0,&\text{if
}\sigma_{i}({\mathbf{x}})=0\end{cases}$

where $Z=\frac{\mu_{i}({\mathbf{x}})-m_{i}}{\sigma_{i}({\mathbf{x}})}$,
$\Phi(\cdot)$ is the cumulative distribution function and $\phi(\cdot)$ is the
probability density function, both assuming normal distributions. In
particular, $\left(\mu_{i}({\mathbf{x}})-m_{i}\right)\Phi(Z)$ indicates the
improvement in favor of exploitation, and $\sigma_{i}({\mathbf{x}})\phi(Z)$
indicates the uncertainty in favor of exploration. The unseen configuration
with the highest expected improvement will be selected.

###  3.3. System Monitor

When a configuration is selected, Cello runs the workload in this
configuration and monitors its status. The System Monitor ( B) records
behavior (i.e., latency and energy) at regular time intervals to check if the
configuration has finished running ( 1). If the configuration finishes, Cello
reports the latency and energy back to Bayesian Optimization ( A) for the next
round. If the configuration is still running, the System Monitor reports the
current latency and energy to the next module.

###  3.4. Censored Regressor

Cello’s Censored Regressor ( C) takes the information from the System Monitor
( B) and predicts the current configuration’s final latency and energy. The
key idea of censored regression is to use the system behavior at the current
time interval to accurately predict whether the current configuration will
exceed the termination threshold. In particular, censored regression
categorizes the training samples as follows:

  * •

1

Samples that finish running; i.e., those which have terminated normally and
thus have known latency and energy.

  * •

2

Samples that do not finish running; i.e., those which are terminated early and
their latency and energy are censored at the current elapsed latency and
energy.

Next, we describe how censored regression models these two categories of
training data. We will use the problem of minimizing latency under a power
constraint as an example, in which we will predict latency.

Let $z_{i}$ be the observed latency associated with ${\mathbf{x}}_{i}$ at the
$i$-th round, and $g(\cdot)$ be the output from censored regression. Then the
formal definition of censored regression model (Barnwal et al., 2020) is:

(3) $\displaystyle\log z_{i}=g({\mathbf{x}}_{i})+\varsigma\epsilon_{i},$

where $\varsigma$ is a constant and $\epsilon_{i}$ is the measurement noise.
The $\log$-scale of the response simplifies modeling different types of
exponential distributions. The goal of censored regression is to estimate
$g(\cdot)$. When ${\mathbf{x}}_{i}$ is running and the System Monitor returns
the current latency at the $t$-th time interval, the current latency $y_{it}$
is a censored value of $z_{i}$ such that

(4) $\displaystyle
y_{it}=\begin{cases}z_{i},&z_{i}<\tau_{it}\quad(\leavevmode\hbox to8.4pt{\vbox
to9.84pt{\pgfpicture\makeatletter\hbox{\hskip 4.2pt\lower-4.92221pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}}
{{}\pgfsys@rect{-4.0pt}{-4.72221pt}{8.0pt}{9.44443pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}})\\\
\tau_{it},&z_{i}\geq\tau_{it}\quad(\leavevmode\hbox to8.4pt{\vbox
to9.84pt{\pgfpicture\makeatletter\hbox{\hskip 4.2pt\lower-4.92221pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}}
{{}\pgfsys@rect{-4.0pt}{-4.72221pt}{8.0pt}{9.44443pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}})\end{cases}$

where $\tau_{it}$ is the current latency at the $t$-th time interval (i.e.,
the amount of time that has elapsed during the execution of the sample). In
eq. 4:

  * •

If the observed latency is less than the current latency $z_{i}<\tau_{it}$,
Cello observes the latency when the configuration finishes running; i.e.,
$y_{i\cdot}=z_{i}$, where $y_{i\cdot}$ is the observed latency of a sample
that terminated normally. Cello treats these uncensored (finished) samples by
fitting them with regression, corresponding to 1.

  * •

If the observed latency is greater than or equal to the current latency
$z_{i}\geq\tau_{it}$, Cello observes the current latency censored at the
$t$-th time interval, and $\tau_{it}$ is the current elapsed latency. Cello
treats this censored (running) sample by estimating its probability of $z_{i}$
exceeding $\tau_{it}$ given the configuration, corresponding to 2.

Censored regression treats the uncensored (finished) samples and the censored
(running) sample differently, and solves them together by minimizing the total
negative log-likelihood (NLL) loss function. The NLL loss function at the
$t$-th time interval in the $i$-th round is:

$\displaystyle\rho\left(g;({\mathbf{x}}_{j},y_{j\cdot})_{j=1}^{i-1},({\mathbf{x}}_{i},\tau_{it})\right)$
$\displaystyle=-\sum_{j=1}^{i-1}\mathbbm{1}_{[z_{j}=y_{j\cdot}]}\log\frac{1}{y_{j\cdot}\sigma}\phi\left(\frac{\log
y_{j\cdot}-g({\mathbf{x}}_{j})}{\sigma}\right)$ (5)
$\displaystyle-\log\left(1-\Phi\left(\frac{\log\tau_{it}-g({\mathbf{x}}_{i})}{\sigma}\right)\right),$

where $\phi(\cdot)$ and $\Phi(\cdot)$ are the probability density and
cumulative distribution functions of the noise $\epsilon_{i}$ in eq. 3,
respectively. The first term is the log-likelihood function for the uncensored
(finished) samples that measures the discrepancy between $\log y_{j\cdot}$ and
$g({\mathbf{x}}_{j})$ where $j\in[1,i-1]$, corresponding to 1. The second term
is the log-likelihood function for the censored (running) sample of the
current $i$-th round that encourages $g({\mathbf{x}}_{i})>\log\tau_{it}$ when
$y_{it}=\tau_{it}$, corresponding to 2. To fit this loss function, Cello uses
gradient boosting trees due to its high fitting power in various predictive
tasks (Chen and Guestrin, 2016). Because, all else equal, the loss function in
section 3.4 is lower when $g({\mathbf{x}}_{j})$ is higher, we regularize the
predictor by training with early stopping (Bishop, 2006, Chapter 5.5.2).

###  3.5. Predictive Early Termination

Cello’s Predictive Early Termination Module ( D) will terminate the current
configuration based on the predictions from the Censored Regressor ( C). If
the prediction is better than the existing best from the collected samples,
Cello lets the configuration keep running until the next time interval, when
Cello will make another prediction to check if the configuration should be
terminated. If the prediction is worse than the existing best from the
collected samples, Cello will terminate the running process, drop this
configuration, and begin the next round of Bayesian Optimization ( A). In this
case, the surrogate model does not change since no new samples are added to
the training set. To avoid selecting the same configuration as the previous
rounds, Cello only selects the configuration that maximizes the acquisition
function from the unsampled configurations. With this module, Cello reduces
the time cost of each sample by dynamically determining whether predictive
early termination should happen and when it will happen.

1:$T_{\rm budget}$ $\triangleright$ Time budget.

2:$C$ $\triangleright$ Target constraint in power or latency.

3:Randomly sample a configuration ${\mathbf{x}}_{0}$ to construct
$X_{\mathrm{train}}$ and obtain its system behavior $y_{0}$ to construct
$Y_{\mathrm{train}}$.

4:$i=1$

5:while $T_{\rm budget}>0$ do

6: Train surrogate model using $X_{\mathrm{train}}$ and $Y_{\mathrm{train}}$.

7: Select configuration ${\mathbf{x}}_{i}$ based on acquisition function.

8: Run experiment at ${\mathbf{x}}_{i}$ and monitor its system behavior.

9: $\gamma_{i}\leftarrow\min Y_{\mathrm{train}}$. $\triangleright$ Update the
existing best.

10: for each interval $t=1,\ldots,$ do

11: if sample not finished then

12: Get current system behavior $y_{it}$.

13: Build censored regressor on $X_{\mathrm{train}}$, $Y_{\mathrm{train}}$,
${\mathbf{x}}_{i}$, $y_{it}$.

14: Get predicted latency $\hat{y}_{it}$ for ${\mathbf{x}}_{i}$.

15: if $\hat{y}_{it}\geq\gamma_{i}$ then

16: Early terminate experiment.

17: Get current running time $t_{it}$.

18: $T_{\rm budget}\leftarrow T_{\rm budget}-t_{it}$.

19: else

20: Get system behavior $y_{i\cdot}$ and constraint $c_{i}$ for
${\mathbf{x}}_{i}$.

21: if $c_{i}\leq C$ then

22: $X_{\mathrm{train}}\leftarrow X_{\mathrm{train}}\bigcup{\mathbf{x}}_{i}$,
$Y_{\mathrm{train}}\leftarrow Y_{\mathrm{train}}\bigcup y_{i\cdot}$.

23: else

24: $X_{\mathrm{train}}\leftarrow X_{\mathrm{train}}\bigcup{\mathbf{x}}_{i}$,
$Y_{\mathrm{train}}\leftarrow Y_{\mathrm{train}}\bigcup\mathrm{inf}$.

25: Get current running time $t_{it}$.

26: $T_{\rm budget}\leftarrow T_{\rm budget}-t_{it}$.

27: $i\leftarrow i+1$.

28:return ${\mathbf{x}}^{\star}$ with the best system behavior from
$X_{\mathrm{train}}$ that meets the target constraint.

Algorithm 1 Cello for systems optimization.

###  3.6. Applying Cello to Optimization Problems

Cello is a general framework that can augment existing SEML approaches by
reducing the time cost per sample. We apply Cello to solve the following two
optimization problems: (1) Latency-Under-Power: minimizing latency under a
power constraint; and (2) Energy-Under-Latency: minimizing energy under a
latency constraint.

Algorithm 1 summarizes the procedure. In 6 and 7, Cello conducts Bayesian
Optimization to select the configuration to run ( A). In 8, Cello’s System
Monitor observes the running configuration ( B). In 9, Cello updates the
existing best system behavior (latency for Latency-Under-Power, energy for
Energy-Under-Latency) from the collected samples. At each time interval, if
the sample has not finished (11), Cello’s Censored Regressor ( C) predicts
future behavior (12, 13 and 14). If the predicted behavior is worse than the
existing best (15), Cello terminates the configuration ( D, 16), and updates
the time budget (18). If the experiment has terminated normally, Cello
determines how to update the training set. If the configuration meets the
target constraint—in either latency or power—(21), Cello adds this
configuration and its true behavior to the training set for the next round
(22). Otherwise, Cello adds this configuration and uses a extremely high value
to replace its true behavior (24), which incorporates the knowledge that this
configuration violates the target constraint by adding a discontinuous sample
to the training set. Meanwhile, Cello updates the time budget (26) to make
sure that there is enough time to go to the next round. Finally, Cello outputs
the best configuration that meets the target constraint (28). We implement
Cello in Python with libraries including numpy (Harris et al., 2020), pandas
(pandas development team, 2020), and scikit-learn (Pedregosa et al., 2011).
For censored regression, we use an implementation from the Accelerated Failure
Time model in XGBoost library, which is a state-of-the-art implementation of
censored regression fitted with the gradient boosting trees (Barnwal et al.,
2020). The code is released in https://anonymous.4open.science/r/cello-
code-8512.

Table 1. Hardware and software configuration parameters tuned in the experiments. Category | Configuration parameter | Range | Description
---|---|---|---
Hardware | cpu.freq | 1.0–3.7 | CPU frequency, in GHz.
uncore.freq | 1.0–2.4 | Uncore frequency, in GHz.
hyperthreading | on, off | Hyperthreading.
n.sockets | 1, 2 | Number of sockets.
n.cores | 1–12 | Number of cores per socket.
Software | spark.reducer.maxSizeInFlight | 24–128 | Max size of map outputs to fetch from each reduce task, in MB.
spark.shuffle.file.buffer | 24–128 | Size of the in-memory buffer for each shuffle file output stream, in KB.
spark.shuffle.sort.bypassMergeThreshold | 100–1000 | Avoid merge-sorting data if there is no map-side aggregation.
spark.speculation.interval | 100–1000 | How often Spark will check for tasks to speculate, in millisecond.
spark.speculation.multiplier | 1–5 | How many times slower a task is than median considered for speculation.
spark.speculation.quantile | 0–1 | Percentage of tasks to be complete before speculation is enabled.
spark.broadcast.blockSize | 2–128 | Size of each piece of a block for TorrentBroadcastFactory, in MB.
spark.io.compression.snappy.blockSize | 24–128 | Block size used in snappy, in KB.
spark.kryoserializer.buffer.max | 24-128 | Maximum allowable size of Kryo serialization buffer, in MB.
spark.kryoserializer.buffer | 24–128 | Initial size of Kryo’s serialization buffer, in KB.
spark.driver.memory | 6–12 | Amount of memory to use for the driver process, in GB.
spark.executor.memory | 6–16 | Amount of memory to use per executor process, in GB.
spark.network.timeout | 20–500 | Default timeout for all network interactions, in second.
spark.locality.wait | 1–10 | How long to launch a data-local task before giving up, in second.
spark.task.maxFailures | 1–8 | Number of task failures before giving up on the job.
spark.shuffle.compress | false, true | Whether to compress map output files.
spark.memory.fraction | 0–1 | Fraction of (heap space–300 MB) used for execution and storage.
spark.shuffle.spill.compress | false, true | Whether to compress data spilled during shuffles.
spark.broadcast.compress | false, true | Whether to compress broadcast variables before sending them.
spark.memory.storageFraction | 0.5–1 | Amount of storage memory immune to eviction.

##  4\. Experimental Setup

###  4.1. Software Systems

We use Apache Spark as our software system (spa, ). Each experiment has a
master node and four worker nodes. We use a wide range of configuration
parameters that reflect significant properties categorized by shuffle
behavior, data compression and serialization, memory management, execution
behavior, networking, and scheduling (details in the software category of
Table 1). We use the same set of parameters as prior work (Yu et al., 2018)
slightly modified for the current version of HiBench Spark.

We use 12 workloads (Table 2) from HiBench’s big data benchmark suite (Huang
et al., 2010)—a benchmark suite that is widely used in prior work (Yu et al.,
2018; Wang et al., 2019; Banerjee et al., 2021; Ding et al., 2021). The
workloads cover various domains including microbenchmarks, machine learning,
websearch, and graph analytics.

Table 2. HiBench workloads. Workload | Data size | Workload | Data size
---|---|---|---
als | 0.6 GB | bayes | 19 GB
gbt | 2 GB | kmeans | 20 GB
linear | 48 GB | lr | 8 GB
nweight | 0.9 GB | pagerank | 1.5 GB
pca | 4 GB | rf | 0.8 GB
terasort | 3.2 GB | wordcount | 32 GB

###  4.2. Hardware Systems

We run experiments on the Chameleon configurable cloud computing systems
(Keahey et al., 2020), where each node is a dual-socket system running Ubuntu
18.04 (GNU/Linux 5.4) with 2 Intel(R) Xeon(R) Gold 6126 processors, 192 GB of
RAM, hyperthreads and TurboBoost. Each socket has 12 cores/24 hyperthreads and
a 20 MB last-level cache. The hardware parameters we optimize are in the
hardware category of Table 1, which have been shown to have a significant
affect on latency and power tradeoffs (Zhang and Hoffmann, 2016).

###  4.3. Points of Comparison

We compare a spectrum of approaches including random sampling (RS), Bayesian
optimization (BO), Bayesian optimization with measured early termination (BO-
ST, BO-TC, BO-IM, BO-NN) and predictive early termination (BO-GB), and
ensemble Bayesian optimization (Bliss).

  * •

RS: randomly sample configurations and select the best configuration that
meets the constraint.

  * •

BO: Bayesian optimization using random forest as the surrogate model and
expected improvement as the acquisition function (Alipourfard et al., 2017;
Nardi et al., 2019; Patel and Tiwari, 2020; Chen et al., 2021). We also use
the same setting for the following approaches.

  * •

BO-ST: Bayesian optimization with measured early termination using the static
termination threshold; i.e., terminate the experiment when the measured
latency or energy is observed to reach the static termination threshold, and
then drop the sample. The static threshold is the latency or energy of the
initial sample because it is the only prior knowledge we have to set this
threshold.

  * •

BO-TC: Bayesian optimization with measured early termination by truncation;
i.e., terminate the experiment when the measured latency or energy is observed
to be worse than the existing best, and then drop the configuration.

  * •

BO-IM: Bayesian optimization with measured early termination by imputation
(Hutter et al., 2013); i.e., terminate the experiment when the measured
latency or energy is observed to be worse than the existing best, and then
impute—i.e., replace missing data with predicted values—the unfinished
configuration.

  * •

BO-NN: Neural model-based Bayesian optimization with measured early
termination and censored observations (Eggensperger et al., 2020); i.e., train
the neural network with the Tobit loss function for the censored training
data. The same neural network architecture and hyperparameter settings are
used in (Eggensperger et al., 2020). We use the same static threshold setting
as the experiments in (Eggensperger et al., 2020). The threshold is the
latency or energy of the initial sample because it is the only prior knowledge
we have to set this threshold.

  * •

BO-GB: Bayesian optimization with predictive early termination by predicting
with standard regression; i.e., terminate the experiment when the predicted
latency or energy is worse than the existing best, and drop the configuration.
We use gradient boosting trees as the standard regressor due to its high
accuracy (Chen and Guestrin, 2016). This approach is novel to this paper, we
include it to show the importance of using censored regression rather than
standard regression for predicted early termination.

  * •

Bliss: ensemble Bayesian optimization (Roy et al., 2021). Bliss reduces sample
collection time by determining when to update its surrogate model using
predictions from that same surrogate. To the best of our knowledge, Bliss is
the state-of-the-art of Bayesian optimization in configuration search for
computer systems.

  * •

Cello: Bayesian optimization with predictive early termination by predicting
with censored regression.

###  4.4. Evaluation Methodology

Following a methodology established in prior work on investigating Apache
Spark systems (Yu et al., 2018), we create a set of 2000 configurations per
workload, randomly sampled from both hardware and software configuration
parameters. We run these configurations to record their latency and energy
consumption. For reference, we used more than 50000 CPU hours to record this
test dataset (and we will include it as part of our open source release). We
then give each of the above approaches a fixed amount of time to search a
combined space of hardware and software configuration parameters and find
solutions for two optimization problems: (1) Latency-Under-Power: minimizing
latency under a power constraint; and (2) Energy-Under-Latency: minimizing
energy under a latency constraint.

We evaluate on a wide range of search time budgets such that at least one of
the above approaches converges to the optimal solution. We set a range of
constraints: the power and latency constraints are set as
$[10,20,30,40,50,60,70,80,90]$-th percentiles of the distributions. For all
approaches that measure progress of running samples, we set a time interval of
5 seconds; i.e., the system behavior is monitored every 5 seconds. The
reported results are averaged over different constraints over 10 runs with
different random seeds.

For censored regression from the XGBoost library, we choose the extreme
distribution for the loss function. We set num_boost_round, the parameter that
controls the number of steps to fit gradient boosting trees in section 3.4 to
minimize the loss (i.e., the point at which to early stop) to 20. We tune this
parameter by generating predictions that are generally above the current
elapsed latency and energy on one workload als dataset, and use this same
value on all other datasets without additional tuning. For each distinct trial
on each dataset, we run cross validation for distribution_scale with the value
range of $[0.2,0.3,0.4]$ and learning_rate with the value range of
$[0.2,0.25,0.3]$ and report the best results.

###  4.5. Evaluation Metric

RE. We use relative error (RE) between the result from each approach and the
optimal for evaluation:

(6) $\displaystyle\text{RE}=\frac{|Y_{\rm pred}-Y_{\rm opt}|}{|Y_{\rm opt}|},$

where $Y_{\rm pred}$ is the best value found by the approach, and $Y_{\rm
opt}$ is the optimal measured value. Lower RE is better.

##  5\. Experimental Evaluation

We evaluate the following research questions (RQs):

  * •

RQ1: How well does Cello perform? Cello reduces latency by 1.19–1.90$\times$
for Latency-Under-Power (Figure 4 and 5) and energy by 1.18–2.35$\times$ for
Energy-Under-Latency (Figure 6 and 7).

  * •

RQ2: Is prediction or measurement better for early termination? Cello’s
predictive early termination outperforms measured early termination approaches
by terminating much earlier while producing more accurate predictions (section
5.2).

  * •

RQ3: How is censored regression beneficial to Cello? Cello’s censored
regression reduces prediction error (as mean squared error) for latency and
energy by 60% and 82% over standard regression for Latency-Under-Power and
Energy-Under-Latency (Figure 8).

  * •

RQ4: How many samples are explored? By combining censored regression and
predictive early termination, Cello both explores more samples and improves
search results compared to other baselines (section 5.4).

  * •

RQ5: What is the overhead? Within the same amount of search time (learning
overhead included), Cello produces the best results by both predicting
accurately (section 5.3) and updating quickly (0.3 seconds per sample, section
5.5).

Figure 4. Latency results averaged over all power constraints for Latency-
Under-Power (lower is better). Figure 5. Latency results averaged over all
search time budgets for Latency-Under-Power (lower is better). Figure 6.
Energy results averaged over all latency constraints for Energy-Under-Latencys
(lower is better). Figure 7. Energy results averaged over all search time
budgets for Energy-Under-Latency (lower is better).

###  5.1. RQ1: How well does Cello perform?

Figure 4 and 6 show the latency and energy results of different approaches as
a function of different search time budgets for Latency-Under-Power and
Energy-Under-Latency, respectively, where the x-axis is the search time, and
the y-axis is the latency or energy (lower is better). We compare the
summarized results averaged over all search times in Figure 5 and 7, and
compute the relative error (RE) by comparing to the optimal value (Optimal) in
Table 3, where Optimal is the best value found through brute force search. We
can see that compared to other approaches, Cello finds the configuration with
the lowest latency and energy at almost all search times for almost all
workloads. The major exceptions are lr and rf in Latency-Under-Power, and als
and bayes in Energy-Under-Latency, where Bliss outperforms Cello at some
points. It is not surprising since with numerous local optima in the
tremendous search space, no single method will dominate. Despite that, Cello
still outperforms prior work in the majority of cases and gets much better
results on average. In particular, we find that on average:

Table 3. Summarized results averaged over all workloads for each approach. Lower RE is better. | Latency-Under-Power | Energy-Under-Latency
---|---|---
| RE (%) | # samples | RE (%) | # samples
RS | 55 | 23 | 46 | 25
BO | 52 | 24 | 36 | 28
BO-ST | 51 | 26 | 31 | 32
BO-TC | 48 | 30 | 32 | 41
BO-IM | 51 | 91 | 31 | 69
BO-NN | 94 | 19 | 54 | 21
BO-GB | 127 | 385 | 72 | 378
Bliss | 42 | 36 | 31 | 31
Cello | 20 | 44 | 16 | 50

  * •

Cello achieves 20% and 16% REs for Latency-Under-Power and Energy-Under-
Latency respectively (Table 3), which represent 1.19$\times$ and 1.18$\times$
speedups compared to the best baseline Bliss, and 1.90$\times$ and
2.35$\times$ speedups compared to the weakest baseline BO-GB.

  * •

BO underperforms all approaches with early termination except BO-GB, which
indicates the benefits of early terminations in SEML. The reasons that BO-GB
performs poorly will be discussed in section 5.3.

  * •

As the state-of-the-art Bayesian optimization approach for configuration
optimization, Bliss under-performs Cello in most workloads for several
reasons. First, Bliss does not incorporate early termination; it runs a few
rounds as BO in the beginning and then starts using predictions to update the
surrogate model, which means that it does not reduce the cost of collecting
samples during early rounds. Second, Bliss uses its surrogate model—i.e.,
standard regression—to predict, which leads to less accurate prediction
compared to censored regression (more details in section 5.3). Finally, Bliss
updates its surrogate alternating between using predictions and measured
system behavior, which produces less accurate model updates. In contrast,
Cello combines censored regression and early termination based on predicted
behavior to reduce search costs. When running for a fixed time budget, Cello
explores more configurations than Bliss (# sample columns in Table 3), and
thus generally achieves better results.

###  5.2. RQ2: Is prediction or measurement better for early termination?

Here, we focus on comparing predictive early termination (Cello) to measured
early termination (BO-ST, BO-TC, BO-IM and BO-NN) to determine if the former
significantly improves early termination methods. In Figure 5 and 7 , Cello
has 1.24–1.61$\times$ and 1.24–1.34$\times$ speedups over BO-ST, BO-TC, BO-IM
and BO-NN for Latency-Under-Power and Energy-Under-Latency respectively. Cello
outperforms other measured early termination approaches because it terminates
poor samples much earlier using the accurate predictions from censored
regression. Therefore, given the same amount of the search time budget, Cello
also evaluate more samples than BO-ST, BO-TC, and BO-NN from Table 3, which
reflects the fact that Cello terminates more samples earlier. Although BO-IM
evaluates more samples than Cello, it underperforms Cello, which suggests that
it is terminating both early and accurately that improve results, not just
terminating early. These results demonstrate the benefits of predictive early
termination over measured early termination; however, the next section shows
that achieving these benefits requires an appropriate predictive model.

(a)

(b)

Figure 8. MSEs for Latency-Under-Power (left) and Energy-Under-Latency
(right). Lower is better. Figure 9. Overhead of processing each sample for
Latency-Under-Power. Lower is better. Figure 10. Overhead of processing each
sample for Energy-Under-Latency. Lower is better.

###  5.3. RQ3: How is censored regression beneficial to Cello?

Here, we analyze the results of BO-GB to Cello. BO-GB uses early termination,
but based on a standard regression model rather than Cello’s censored
regression. Although BO-GB has predictive early termination, it achieves the
worst results. This poor result is due to the low prediction accuracy from
standard regression when training on censored data. To illustrate this, we
compare the prediction accuracy of each selected sample between BO-GB’s
standard regression (gradient boosting trees) and Cello’s censored regression.

We monitor workload execution and predict its latency at each time interval
(section 4.4). The censoring threshold for censored regression is thus the
elapsed latency observed at each time interval. We compute the mean squared
error (MSE) between predicted latency and true latency. Figure 8 shows the
average MSE over all time intervals, where the x-axis is the workload, the
y-axis is MSE (lower is better), and the last column, Mean, is the arithmetic
mean over all workloads. Censored regression almost always has much lower MSE
than standard regression, with 60% and 82% reductions for Latency-Under-Power
and Energy-Under-Latency respectively. Standard regression has worse
prediction accuracy because BO-GB terminates all samples throughout the
execution and thus does not update the surrogate model at all. These results
suggest that it is important to make accurate predictions so that the poor
configurations can be quickly identified. Censored regression achieves high
accuracy by considering both uncensored (finished) and censored (running)
samples, while standard regression only takes uncensored (finished) samples
into account.

###  5.4. RQ4: How many samples are explored?

Table 3 summarizes the average number of samples selected for each approach.
Note that since all approaches are given the same time to explore, exploring
more samples is generally better, provided those samples produce useful
information for updating the model. We find that:

  * •

Within the same time budgets, BO selects fewer samples than others (except BO-
NN) as BO does not use early termination to save extra time for more samples.

  * •

BO-NN selects the fewest samples compared to others; 19 and 21 on average for
for Latency-Under-Power and Energy-Under-Latency respectively. The reason is
that BO-NN has a surprisingly high overhead for model updates–over 11 seconds
per sample (section 5.5)—and thus a significant portion of its time is spent
on surrogate updates instead of searching new configurations.

  * •

BO-GB selects the most samples; in Table 3, BO-GB selects 385 and 378 samples
for Latency-Under-Power and Energy-Under-Latency respectively. It is because
BO-GB terminates all samples in the first time interval based on its
predictions, and does not update the surrogate model at all. More results can
be found in section 5.3.

  * •

Cello selects 44 and 50 samples for Latency-Under-Power and Energy-Under-
Latency respectively, which are more than RS, BO, BO-ST, BO-TC, BO-NN, and
Bliss, while fewer than BO-IM and BO-GB. It indicates that increasing the
number of samples is not the key to achieving the best results, but selecting
more useful samples matters. Cello is such an example that combines early
termination and censored regression to search more high-quality samples.

###  5.5. RQ5: What is the overhead?

We report the learning overhead of processing each sample, including
predicting future behavior and updating the surrogate. Figure 9 and 10 show
the overhead of processing each sample for different approaches for Latency-
Under-Power and Energy-Under-Latency respectively, where the x-axis is the
workload, the y-axis is the overhead, and the last column Mean is the
arithmetic mean over all workloads. We use the same setting for neural network
training as in (Eggensperger et al., 2020) for BO-NN, and BO-NN has the
highest overhead; i.e., over 11 seconds on average. To better visualize other
methods properly, we cap the y-axis at 1 second. BO-IM has the second largest
overhead due to the high overhead of imputing samples using the Expected-
maximization algorithm (Hutter et al., 2013). The Expected-maximization
algorithm is an iterative method and thus needs numerous steps to converge
(Moon, 1996). Cello has the third largest overhead because it uses the
gradient boosting trees—which is an ensemble method—to fit the loss function
of censored regression. Nevertheless, Cello’s overhead (0.3 seconds on
average) is negligible compared to the cost of collecting each sample (22.3
seconds on average), which is key for its applicability to the efficient
computer systems optimization problems. All results in this section include
learning overhead for all approaches, and Cello still produces the best
results, showing that the overhead can be negligible compared to making good
decisions about early termination to explore more high-quality samples in the
same amount of time.

##  6\. Discussion

To understand the impact of each configuration parameter on system design, we
visualize the SHAP values of the parameters with the best energy under 50-th
latency constraint for Energy-Under-Latency selected by Cello on als and bayes
workloads in Figure 11 and 12, respectively. SHAP (SHapley Additive
exPlanations) is a state-of-the-art approach to interpret the output of
machine learning models (Lundberg and Lee, 2017), which visualizes parameters
contributing to push the model output from the base value (i.e., the average
model output over the training data we passed) to the model output.

For als in Figure 11, n.socket and cpu.freq have the largest effects (with
contributing value $-41.87$ and $-37.46$) that push the energy prediction
lower from the base value to the predictive value. The other high-influence
parameters are shuffle.sort.bypassMergeThreshold, uncore.freq, hyperthreading.
For bayes in Figure 12, uncore.freq and n.sockets have the largest effects
(with contributing value $-27.69$ and $-23.53$) that push the energy
prediction lower from the base value to the predictive value. The other high-
influence parameters are cpu.freq, n.cores, shuffle.file.buffer, etc..

Two key points can be seen from these examples. First, both hardware (e.g.,
uncore.freq) and software (e.g., shuffle.sort.bypassMergeThreshold) parameters
influence the system behavior, and thus both types of parameters should be
tuned to meet the optimization goal. Second, same parameters have different
effects on different workloads, which suggests that the optimal configuration
is workload dependent. Therefore, we should be careful about the prior
knowledge obtained from the existing workloads since information learned for
one workload might not transfer directly to a new workload.

Figure 11. SHAP values for the als workload.  Figure 12. SHAP values for the
bayes workload.

##  7\. Limitations

We recognize the limitations of this work as follows:

  * •

The outcome of predictive early termination and censored regression from Cello
depends on the SEML framework. We chose to implement Cello by adding these
components to Bayesian optimization because it has proven to provide high-
quality samples. Future work can explore how Cello can be generalized to other
learning frameworks.

  * •

It is challenging to determine the search time budget in advance to make sure
that the search results converge to the optimal. There has been work
investigating this topic in the machine learning community (Lorenz et al.,
2015; Nguyen et al., 2017). Although it is out of scope in this paper, it is
interesting to explore the combination of Cello and this direction.

  * •

The improper setting of num_boost_round, the parameter that controls the
number of training steps can result in poor prediction accuracy. Future work
can explore more systematic ways to set this parameter, or incorporate its
regularizing effect into the loss function.

##  8\. Conclusion

This paper presents Cello, a systematic approach to reduce the cost of samples
through predictive early termination and censored regression. Evaluations show
that Cello improves the system outcomes compared to a wide range of existing
SEML and early termination techniques. Finally, we hope that Cello can inspire
future research directions on reducing time cost of sample collection rather
than the number of samples, and other applications of censored regression in
computer systems research.

## References

  * Xu et al. [2015] Tianyin Xu, Long Jin, Xuepeng Fan, Yuanyuan Zhou, Shankar Pasupathy, and Rukma Talwadker.  Hey, you have given me too many knobs!: understanding and dealing with over-designed configuration in system software.  In _Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering_ , pages 307–319, 2015.
  * Colin et al. [2018] Alexei Colin, Emily Ruppel, and Brandon Lucia.  A reconfigurable energy storage architecture for energy-harvesting devices.  In _Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems_ , pages 767–781, 2018.
  * Blöcher et al. [2021] Marcel Blöcher, Lin Wang, Patrick Eugster, and Max Schmidt.  Switches for hire: resource scheduling for data center in-network computing.  In _Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems_ , pages 268–285, 2021.
  * Mishra et al. [2015] Nikita Mishra, Huazhe Zhang, John D. Lafferty, and Henry Hoffmann.  A probabilistic graphical model-based approach for minimizing energy under performance constraints.  In _Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems_ , ASPLOS’15, pages 267–281, New York, NY, USA, 2015.  ISBN 9781450328357.
  * Mishra et al. [2018] Nikita Mishra, Connor Imes, John D. Lafferty, and Henry Hoffmann.  Caloree: Learning control for predictable latency and low energy.  In _Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems_ , ASPLOS’18, pages 184–198, New York, NY, USA, 2018.  ISBN 9781450349116.
  * Herodotou et al. [2020] Herodotos Herodotou, Yuxing Chen, and Jiaheng Lu.  A survey on automatic parameter tuning for big data processing systems.  _ACM Comput. Surv._ , 53(2), April 2020.  ISSN 0360-0300.
  * Penney and Chen [2019] Drew D Penney and Lizhong Chen.  A survey of machine learning applied to computer architecture design.  _arXiv preprint arXiv:1909.12373_ , 2019.
  * Zhang and Huang [2019] Yiying Zhang and Yutong Huang.  ”learned”: Operating systems.  _Operating Systems Review_ , 53(1):40–45, 2019\.
  * Ïpek et al. [2006] Engin Ïpek, Sally A McKee, Rich Caruana, Bronis R de Supinski, and Martin Schulz.  Efficiently exploring architectural design spaces via predictive modeling.  _ACM SIGOPS Operating Systems Review_ , 40(5):195–206, 2006.
  * Alipourfard et al. [2017] Omid Alipourfard, Hongqiang Harry Liu, Jianshu Chen, Shivaram Venkataraman, Minlan Yu, and Ming Zhang.  Cherrypick: Adaptively unearthing the best cloud configurations for big data analytics.  In _Proceedings of the 14th USENIX Conference on Networked Systems Design and Implementation_ , NSDI’17, page 469–482, USA, 2017. USENIX Association.  ISBN 9781931971379.
  * Ding et al. [2019] Yi Ding, Nikita Mishra, and Henry Hoffmann.  Generative and multi-phase learning for computer systems optimization.  In _Proceedings of the 46th International Symposium on Computer Architecture_ , pages 39–52, 2019.
  * Nardi et al. [2019] Luigi Nardi, David Koeplinger, and Kunle Olukotun.  Practical design space exploration.  In _2019 IEEE 27th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS)_ , pages 347–358. IEEE, 2019.
  * Patel and Tiwari [2020] Tirthak Patel and Devesh Tiwari.  Clite: Efficient and qos-aware co-location of multiple latency-critical jobs for warehouse scale computers.  In _2020 IEEE International Symposium on High Performance Computer Architecture (HPCA)_ , pages 193–206, 2020.  doi: 10.1109/HPCA47549.2020.00025.
  * Petrica et al. [2013] Paula Petrica, Adam M Izraelevitz, David H Albonesi, and Christine A Shoemaker.  Flicker: A dynamically adaptive architecture for power limited multicore systems.  In _Proceedings of the 40th Annual International Symposium on Computer Architecture_ , pages 13–23, 2013.
  * Venkataraman et al. [2016] Shivaram Venkataraman, Zongheng Yang, Michael Franklin, Benjamin Recht, and Ion Stoica.  Ernest: Efficient performance prediction for large-scale advanced analytics.  In _13th USENIX Symposium on Networked Systems Design and Implementation (NSDI 16)_ , pages 363–378, 2016.
  * Yu et al. [2018] Zhibin Yu, Zhendong Bei, and Xuehai Qian.  Datasize-aware high dimensional configurations auto-tuning of in-memory cluster computing.  In _Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems_ , pages 564–577, 2018.
  * Hutter et al. [2013] Frank Hutter, Holger Hoos, and Kevin Leyton-Brown.  Bayesian optimization with censored response data.  _arXiv preprint arXiv:1310.1947_ , 2013.
  * Eggensperger et al. [2020] Katharina Eggensperger, Kai Haase, Philip Müller, M. Lindauer, and F. Hutter.  Neural model-based optimization with right-censored observations.  _ArXiv_ , abs/2009.13828, 2020.
  * Powell [1986] James L Powell.  Censored regression quantiles.  _Journal of econometrics_ , 32(1):143–155, 1986\.
  * Miller and Halpern [1982] Rupert Miller and Jerry Halpern.  Regression with censored data.  _Biometrika_ , 69(3):521–531, 1982.
  * Portnoy [2003] Stephen Portnoy.  Censored regression quantiles.  _Journal of the American Statistical Association_ , 98(464):1001–1012, 2003.
  * Huang et al. [2010] Shengsheng Huang, Jie Huang, Yan Liu, Lan Yi, and Jinquan Dai.  Hibench: A representative and comprehensive hadoop benchmark suite.  In _Proc. ICDE Workshops_ , pages 41–51, 2010.
  * Vishwanath and Nagappan [2010] Kashi Venkatesh Vishwanath and Nachiappan Nagappan.  Characterizing cloud computing hardware reliability.  In _Proceedings of the 1st ACM symposium on Cloud computing_ , pages 193–204, 2010.
  * Belay et al. [2014] Adam Belay, George Prekas, Ana Klimovic, Samuel Grossman, Christos Kozyrakis, and Edouard Bugnion.  Ix: A protected dataplane operating system for high throughput and low latency.  In _11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14)_ , pages 49–65, 2014.  doi: 10.1145/2997641.
  * Van Aken et al. [2017] Dana Van Aken, Andrew Pavlo, Geoffrey J Gordon, and Bohan Zhang.  Automatic database management system tuning through large-scale machine learning.  In _Proceedings of the 2017 ACM International Conference on Management of Data_ , pages 1009–1024, 2017.
  * Deng et al. [2017] Zhaoxia Deng, Lunkai Zhang, Nikita Mishra, Henry Hoffmann, and Frederic T Chong.  Memory cocktail therapy: a general learning-based framework to optimize dynamic tradeoffs in nvms.  In _Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture_ , pages 232–244, 2017.
  * Settles [2011] Burr Settles.  From theories to queries: Active learning in practice.  In _Active Learning and Experimental Design workshop In conjunction with AISTATS 2010_ , pages 1–18, 2011.
  * Frazier [2018] Peter I Frazier.  A tutorial on bayesian optimization.  _arXiv preprint arXiv:1807.02811_ , 2018.
  * Roy et al. [2021] Rohan Basu Roy, Tirthak Patel, Vijay Gadepally, and Devesh Tiwari.  Bliss: auto-tuning complex applications using a pool of diverse lightweight learning models.  In _Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation_ , pages 1280–1295, 2021.
  * Li et al. [2017] Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar.  Hyperband: A novel bandit-based approach to hyperparameter optimization.  _The Journal of Machine Learning Research_ , 18(1):6765–6816, 2017.
  * Rasley et al. [2017] Jeff Rasley, Yuxiong He, Feng Yan, Olatunji Ruwase, and Rodrigo Fonseca.  Hyperdrive: Exploring hyperparameters with pop scheduling.  In _Proceedings of the 18th ACM/IFIP/USENIX Middleware Conference_ , pages 1–13, 2017.
  * Swersky et al. [2014] Kevin Swersky, Jasper Snoek, and Ryan Prescott Adams.  Freeze-thaw bayesian optimization.  _arXiv preprint arXiv:1406.3896_ , 2014.
  * Domhan et al. [2015] Tobias Domhan, Jost Tobias Springenberg, and Frank Hutter.  Speeding up automatic hyperparameter optimization of deep neural networks by extrapolation of learning curves.  In _Twenty-fourth international joint conference on artificial intelligence_ , 2015.
  * Klein et al. [2017] Aaron Klein, Stefan Falkner, Jost Tobias Springenberg, and Frank Hutter.  Learning curve prediction with bayesian neural networks.  In _ICLR_ , 2017.
  * Ponomarev et al. [2001] Dmitry Ponomarev, Gurhan Kucuk, and Kanad Ghose.  Reducing power requirements of instruction scheduling through dynamic allocation of multiple datapath resources.  In _Proceedings. 34th ACM/IEEE International Symposium on Microarchitecture. MICRO-34_ , pages 90–101. IEEE, 2001.
  * Choi and Yeung [2006] Seungryul Choi and Donald Yeung.  Learning-based smt processor resource distribution via hill-climbing.  In _33rd International Symposium on Computer Architecture (ISCA’06)_ , pages 239–251. IEEE, 2006.
  * Lee et al. [2007] Benjamin C Lee, David M Brooks, Bronis R de Supinski, Martin Schulz, Karan Singh, and Sally A McKee.  Methods of inference and learning for performance modeling of parallel applications.  In _Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming_ , pages 249–258, 2007.
  * Lee et al. [2008] Benjamin C Lee, Jamison Collins, Hong Wang, and David Brooks.  Cpr: Composable performance regression for scalable multiprocessor models.  In _2008 41st IEEE/ACM International Symposium on Microarchitecture_ , pages 270–281. IEEE, 2008.
  * Martinez and Ipek [2009] Jose F Martinez and Engin Ipek.  Dynamic multicore resource management: A machine learning approach.  _IEEE micro_ , 29(5):8–17, 2009.
  * Snowdon et al. [2009] David C Snowdon, Etienne Le Sueur, Stefan M Petters, and Gernot Heiser.  Koala: A platform for os-level power management.  In _Proceedings of the 4th ACM European conference on Computer systems_ , pages 289–302, 2009.
  * Cochran et al. [2011] Ryan Cochran, Can Hankendi, Ayse K Coskun, and Sherief Reda.  Pack & cap: adaptive dvfs and thread packing under power caps.  In _2011 44th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_ , pages 175–185. IEEE, 2011.
  * Zhang et al. [2012] Xiao Zhang, Rongrong Zhong, Sandhya Dwarkadas, and Kai Shen.  A flexible framework for throttling-enabled multicore management (temm).  In _2012 41st International Conference on Parallel Processing_ , pages 389–398. IEEE, 2012.
  * Sridharan et al. [2013] Srinath Sridharan, Gagan Gupta, and Gurindar S Sohi.  Holistic run-time parallelism management for time and energy efficiency.  In _Proceedings of the 27th international ACM conference on International conference on supercomputing_ , pages 337–348, 2013.
  * Oliner et al. [2013] Adam J Oliner, Anand P Iyer, Ion Stoica, Eemil Lagerspetz, and Sasu Tarkoma.  Carat: Collaborative energy diagnosis for mobile devices.  In _Proceedings of the 11th ACM Conference on Embedded Networked Sensor Systems_ , pages 1–14, 2013.
  * Zhu and Reddi [2013] Yuhao Zhu and Vijay Janapa Reddi.  High-performance and energy-efficient mobile web browsing on big/little systems.  In _2013 IEEE 19th International Symposium on High Performance Computer Architecture (HPCA)_ , 2013.
  * Zhang et al. [2020] Yanqi Zhang, Weizhe Hua, Zhuangzhuang Zhou, Ed Suh, and Christina Delimitrou.  Sinan: Data-driven resource management for interactive microservices.  In _Workshop on ML for Computer Architecture and Systems (MLArchSys)_ , June 2020.
  * Shi et al. [2019] Zhan Shi, Xiangru Huang, Akanksha Jain, and Calvin Lin.  Applying deep learning to the cache replacement problem.  In _Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture_ , pages 413–425, 2019.
  * Shi et al. [2021] Zhan Shi, Akanksha Jain, Kevin Swersky, Milad Hashemi, Parthasarathy Ranganathan, and Calvin Lin.  A hierarchical neural model of data prefetching.  In _Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems_ , pages 861–873, 2021.
  * Tesauro [2007] Gerald Tesauro.  Reinforcement learning in autonomic computing: A manifesto and case studies.  _IEEE Internet Computing_ , 11(1):22–30, 2007\.
  * Winter et al. [2010] Jonathan A Winter, David H Albonesi, and Christine A Shoemaker.  Scalable thread scheduling and global power management for heterogeneous many-core architectures.  In _2010 19th International Conference on Parallel Architectures and Compilation Techniques (PACT)_ , pages 29–39. IEEE, 2010.
  * Van Craeynest et al. [2012] Kenzo Van Craeynest, Aamer Jaleel, Lieven Eeckhout, Paolo Narvaez, and Joel Emer.  Scheduling heterogeneous multi-cores through performance impact estimation (pie).  In _2012 39th Annual International Symposium on Computer Architecture (ISCA)_ , pages 213–224. IEEE, 2012.
  * Lee and Brooks [2006] Benjamin C Lee and David M Brooks.  Accurate and efficient regression modeling for microarchitectural performance and power prediction.  _ACM SIGOPS operating systems review_ , 40(5):185–194, 2006.
  * Ipek et al. [2008] Engin Ipek, Onur Mutlu, José F. Martínez, and Rich Caruana.  Self-optimizing memory controllers: A reinforcement learning approach.  In _Proceedings of the 35th Annual International Symposium on Computer Architecture_ , ISCA’08, pages 39–50, USA, 2008.  ISBN 9780769531748.
  * Bitirgen et al. [2008] Ramazan Bitirgen, Engin Ipek, and Jose F Martinez.  Coordinated management of multiple interacting resources in chip multiprocessors: A machine learning approach.  In _2008 41st IEEE/ACM International Symposium on Microarchitecture_ , pages 318–329. IEEE, 2008.
  * Dubach et al. [2010] Christophe Dubach, Timothy M Jones, Edwin V Bonilla, and Michael FP O’Boyle.  A predictive model for dynamic microarchitectural adaptivity control.  In _2010 43rd Annual IEEE/ACM International Symposium on Microarchitecture_ , pages 485–496. IEEE, 2010.
  * Delimitrou and Kozyrakis [2014] Christina Delimitrou and Christos Kozyrakis.  Quasar: Resource-efficient and qos-aware cluster management.  In _Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems_ , ASPLOS’14, pages 127–144, New York, NY, USA, 2014.  ISBN 9781450323055.
  * Delimitrou and Kozyrakis [2013] Christina Delimitrou and Christos Kozyrakis.  Paragon: Qos-aware scheduling for heterogeneous datacenters.  In _Proceedings of the Eighteenth International Conference on Architectural Support for Programming Languages and Operating Systems_ , ASPLOS’13, pages 77–88, New York, NY, USA, 2013.  ISBN 9781450318709.
  * Teran et al. [2016] Elvira Teran, Zhe Wang, and Daniel A Jiménez.  Perceptron learning for reuse prediction.  In _2016 49th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_ , pages 1–12. IEEE, 2016.
  * Peled et al. [2019] Leeor Peled, Uri Weiser, and Yoav Etsion.  A neural network prefetcher for arbitrary memory access patterns.  _ACM Transactions on Architecture and Code Optimization (TACO)_ , 16(4):1–27, 2019.
  * Bhatia et al. [2019] Eshan Bhatia, Gino Chacon, Seth Pugsley, Elvira Teran, Paul V Gratz, and Daniel A Jiménez.  Perceptron-based prefetch filtering.  In _2019 ACM/IEEE 46th Annual International Symposium on Computer Architecture (ISCA)_ , pages 1–13. IEEE, 2019.
  * Garza et al. [2019] Elba Garza, Samira Mirbagher-Ajorpaz, Tahsin Ahmad Khan, and Daniel A Jiménez.  Bit-level perceptron prediction for indirect branches.  In _2019 ACM/IEEE 46th Annual International Symposium on Computer Architecture (ISCA)_ , pages 27–38. IEEE, 2019.
  * Bera et al. [2021] Rahul Bera, Konstantinos Kanellopoulos, Anant Nori, Taha Shahroodi, Sreenivas Subramoney, and Onur Mutlu.  Pythia: A customizable hardware prefetching framework using online reinforcement learning.  In _MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture_ , pages 1121–1137, 2021.
  * Peled et al. [2015] Leeor Peled, Shie Mannor, Uri Weiser, and Yoav Etsion.  Semantic locality and context-based prefetching using reinforcement learning.  In _2015 ACM/IEEE 42nd Annual International Symposium on Computer Architecture (ISCA)_ , pages 285–297. IEEE, 2015.
  * Lee and Brooks [2010] Benjamin C Lee and David Brooks.  Applied inference: Case studies in microarchitectural design.  _ACM Transactions on Architecture and Code Optimization (TACO)_ , 7(2):1–37, 2010.
  * Chen and Guestrin [2016] Tianqi Chen and Carlos Guestrin.  Xgboost: A scalable tree boosting system.  In _Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining_ , pages 785–794, 2016.  doi: 10.1145/2939672.2939785.
  * [66] Apache spark.  https://spark.apache.org/docs/2.2.3/configuration.html.
  * [67] Mapreduce.  https://hadoop.apache.org/docs/r1.2.1/mapred_tutorial.html.
  * [68] Cassandra.  hhttps://cassandra.apache.org/_/index.html.
  * [69] Hbase.  https://hbase.apache.org/.
  * Hutter et al. [2011] Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown.  Sequential model-based optimization for general algorithm configuration.  In _International conference on learning and intelligent optimization_ , pages 507–523. Springer, 2011.
  * Breiman [2001] Leo Breiman.  Random forests.  _Machine learning_ , 45(1):5–32, 2001.
  * Barnwal et al. [2020] Avinash Barnwal, Hyunsu Cho, and Toby Hocking.  Survival regression with accelerated failure time model in xgboost.  _ArXiv_ , abs/2006.04920, 2020.
  * McCulloch and Rossi [1994] Robert McCulloch and Peter E Rossi.  An exact likelihood analysis of the multinomial probit model.  _Journal of Econometrics_ , 64(1-2):207–240, 1994\.
  * Bishop [2006] Christopher M Bishop.  Pattern recognition.  _Machine learning_ , 128(9), 2006.
  * Harris et al. [2020] Charles R. Harris, K. Jarrod Millman, Stéfan J van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant.  Array programming with numpy.  _Nature_ , 585:357–362, 2020.
  * pandas development team [2020] The pandas development team.  pandas-dev/pandas: Pandas, February 2020.
  * Pedregosa et al. [2011] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine learning in Python.  _Journal of Machine Learning Research_ , 12:2825–2830, 2011\.
  * Wang et al. [2019] Yuzhao Wang, Lele Li, You Wu, Junqing Yu, Zhibin Yu, and Xuehai Qian.  Tpshare: a time-space sharing scheduling abstraction for shared cloud via vertical labels.  In _2019 ACM/IEEE 46th Annual International Symposium on Computer Architecture (ISCA)_ , pages 499–512. IEEE, 2019.
  * Banerjee et al. [2021] Subho S Banerjee, Saurabh Jha, Zbigniew Kalbarczyk, and Ravishankar K Iyer.  Bayesperf: minimizing performance monitoring errors using bayesian statistics.  In _Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems_ , pages 832–844, 2021.
  * Ding et al. [2021] Yi Ding, Ahsan Pervaiz, Michael Carbin, and Henry Hoffmann.  Generalizable and interpretable learning for configuration extrapolation.  In _Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_ , pages 728–740, 2021.
  * Keahey et al. [2020] Kate Keahey, Jason Anderson, Zhuo Zhen, Pierre Riteau, Paul Ruth, Dan Stanzione, Mert Cevik, Jacob Colleran, Haryadi S. Gunawi, Cody Hammock, Joe Mambretti, Alexander Barnes, François Halbach, Alex Rocha, and Joe Stubbs.  Lessons learned from the chameleon testbed.  In _Proceedings of the 2020 USENIX Annual Technical Conference (USENIX ATC ’20)_. USENIX Association, July 2020.
  * Zhang and Hoffmann [2016] Huazhe Zhang and Henry Hoffmann.  Maximizing performance under a power cap: A comparison of hardware, software, and hybrid techniques.  _ACM SIGPLAN Notices_ , 51(4):545–559, 2016.
  * Chen et al. [2021] Junjie Chen, Ningxin Xu, Peiqi Chen, and Hongyu Zhang.  Efficient compiler autotuning via bayesian optimization.  In _2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE)_ , pages 1198–1209. IEEE, 2021.
  * Moon [1996] Todd K Moon.  The expectation-maximization algorithm.  _IEEE Signal processing magazine_ , 13(6):47–60, 1996.
  * Lundberg and Lee [2017] Scott M Lundberg and Su-In Lee.  A unified approach to interpreting model predictions.  _Advances in neural information processing systems_ , 30, 2017.
  * Lorenz et al. [2015] Romy Lorenz, Ricardo P Monti, Ines R Violante, Aldo A Faisal, Christoforos Anagnostopoulos, Robert Leech, and Giovanni Montana.  Stopping criteria for boosting automatic experimental design using real-time fmri with bayesian optimization.  _arXiv preprint arXiv:1511.07827_ , 2015.
  * Nguyen et al. [2017] Vu Nguyen, Sunil Gupta, Santu Rana, Cheng Li, and Svetha Venkatesh.  Regret for expected improvement over the best-observed value and stopping condition.  In _Asian Conference on Machine Learning_ , pages 279–294. PMLR, 2017\.