#  Llama: A Heterogeneous & Serverless Framework for Auto-Tuning Video
Analytics Pipelines

Francisco Romero  Stanford University ,  Mark Zhao* Stanford University ,
Neeraja J. Yadwadkar  Stanford University and  Christos Kozyrakis  Stanford
University

###### Abstract.

The proliferation of camera-enabled devices and large video repositories has
led to a diverse set of video analytics applications. These applications rely
on video pipelines, represented as DAGs of operations, to transform videos,
process extracted metadata, and answer questions like, “Is this intersection
congested?” The latency and resource efficiency of pipelines can be optimized
using configurable knobs for each operation (e.g., sampling rate, batch size,
or type of hardware used). However, determining efficient configurations is
challenging because (a) the configuration search space is exponentially large,
and (b) the optimal configuration depends on users’ desired latency and cost
targets, (c) input video contents may exercise different paths in the DAG and
produce a variable amount intermediate results. Existing video analytics and
processing systems leave it to the users to manually configure operations and
select hardware resources.

We present Llama: a heterogeneous and serverless framework for auto-tuning
video pipelines. Given an end-to-end latency target, Llama optimizes for cost
efficiency by (a) calculating a latency target for each operation invocation,
and (b) dynamically running a cost-based optimizer to assign configurations
across heterogeneous hardware that best meet the calculated per-invocation
latency target. This makes the problem of auto-tuning large video pipelines
tractable and allows us to handle input-dependent behavior, conditional
branches in the DAG, and execution variability. We describe the algorithms in
Llama and evaluate it on a cloud platform using serverless CPU and GPU
resources. We show that compared to state-of-the-art cluster and serverless
video analytics and processing systems, Llama achieves 7.8$\times$ lower
latency and 16$\times$ cost reduction on average.

††copyright: none

##  1\. Introduction

Video traffic is exploding in scale, predicted to account for over 82% of all
internet traffic by 2022 (cisco-internet-whitepaper, ). A myriad of domains
use video pipelines, with tens of video analytics and processing operations,
to extract meaningful information from raw videos. For example, an AMBER Alert
application can leverage traffic cameras across a city to pinpoint specific
individuals and cars (amber-alerts, ). To do so, the application uses a
pipeline to first detect frames with people and/or cars, and then match them
to specific individuals’ faces and car descriptions, respectively. As video
analytics research continues to flourish, we expect a perpetual proliferation
of emerging domains that depend on video pipelines, such as smart cities
(nsdi17-videostorm, ; sigcomm18-chameleon, ; osdi18-focus, ; computer17-video-
analytics, ), surveillance analytics (surveillance, ), healthcare (healthcare,
), and retail (amazongo, ).

The pervasive use of video analytics applications has led to significant
challenges. Video pipelines must meet a wide range of latency, throughput, and
cost targets to be practical across applications. For example, a pipeline to
detect cars and people in a traffic feed should be tuned to be more cost
efficient for city traffic planners with relaxed latency targets, while the
same pipeline must be tuned to meet strict latency targets for AMBER Alert
responders (amber-alerts, ). Video analytics and processing frameworks must
tune pipeline operation knobs (e.g., sampling rate, batch size, hardware
target, and resource allocation) to meet the unique latency or cost
requirements of diverse applications. However, automatically tuning these
knobs is difficult for the following reasons.

Operations exhibit performance variation across heterogeneous hardware.
Hardware accelerators (e.g., GPUs (hotchips-gpu, ), FPGAs (hotchips-fpgaintel,
; hotchips-fpgaxilinx, ), TPUs (isca17-tpu, ), and vision chips (ambarella, ))
provide significant performance benefits for many pipeline operations. Tuning
knobs across these heterogeneous accelerators can have a huge impact in the
performance and efficiency of video pipelines. We observed a 3.7$\times$
latency variation by tuning CPU cores, GPU memory, and batch size for
operations in a representative AMBER Alert pipeline processed using Scanner
(siggraph18-scanner, ). While recent research has proposed mechanisms to tune
operation knobs based on resource usage (sigcomm18-chameleon, ; osdi18-focus,
; atc18-videochef, ), they are limited to simple pipelines and homogeneous
hardware platforms. Furthermore, they rely on hours to days of profiling for
_each_ new pipeline, video, and latency target (nsdi17-videostorm, ;
nsdi17-cherrypick, ).

Pipelines can have input-dependent execution flow.  An input video’s contents
influence the execution flow of a pipeline in two ways. First, the number of
intermediate outputs for an operation may depend on the frame being processed.
For the AMBER Alert pipeline, the object detector operation will output a
variable number of cropped people and/or car images to be processed by
subsequent operations. Second, downstream operations may be conditionally
executed based on the intermediate output. For example, if there are only
people in a frame, no car classification is needed. Consequently, tuning
configuration knobs and resource allocations dynamically based on video
content is critical for performance and efficiency. We found the static
configurations made by gg (atc19-gg, ), a general purpose serverless
framework, degraded performance by as much as 57% for the AMBER Alert
pipeline. Some systems, such as VideoStorm (nsdi17-videostorm, ) and GrandSLAm
(eurosys19-grandslam, ), only support simple sequential pipelines with
deterministic flow.

Systems that use serverless platforms as their backend (e.g., ExCamera
(nsdi17-excamera, ), gg (atc19-gg, ), PyWren (socc17-pywren, ), and Sprocket
(socc18-sprocket, )) execute applications by using thousands of short-lived
functions (awslambda, ; gcf, ; azurefunctions, ). The function-level resource
allocation offered by serverless platforms makes them an attractive option for
processing video pipelines, as they enable dynamic tuning for each operation
invoked. However, existing serverless offerings lack support for heterogeneous
hardware accelerators and application constraints such as latency targets.
Users must still manually, and perhaps exhaustively, explore operation knobs
and resource allocation options.

We present Llama, a video analytics and processing framework that supports
heterogenous hardware and automatically tunes each operation invocation to
meet diverse latency targets for the overall pipeline. Llama is a full-fledged
serverless framework that provides a serverless experience to its users, who
do not need to express the resources or operation knob configurations needed
to meet their latency targets.

Llama is divided into two parts: an offline specification phase, and an online
optimizaiton phase. The offline specification phase allows users to specify
their pipeline, and performs a one-time, per-operation profiling that allows
Llama to automatically tune operation invocations as the pipeline runs. Unlike
existing systems (socc20-inferline, ), this profiling does not need to be
repeated as the pipeline or input video changes.

During the online phase, Llama leverages two key ideas to meet diverse latency
targets. First, Llama _dynamically_ computes how much time can be spent on
each invocation to meet the pipeline latency target (i.e., per-invocation
latency targets). By computing a per-invocation latency target, Llama can
dynamically explore the configuration space for each invocation and adapt to
performance volatility and input-dependent execution flows. Second, Llama
dynamically runs a cost-based optimizer that determines the most efficient
operation configuration that meets the per-invocation target. To do so, Llama
(a) uses _early speculation and late commit_ : a technique for choosing an
initial operation knob configuration during pipeline processing, and
revisiting the configuration right before execution, (b) leverages _priority-
based commit_ to prioritize operations based on hardware affinity and DAG
dependencies, and (c) employs _safe delayed batching_ to batch operations for
efficiency as long as doing so does not violate per-invocation targets.

We deploy Llama on Google Cloud Platform with serverless CPU and GPU backends
and evaluate its efficiency and ability to meet latency targets for five video
analytics and processing pipelines. By dynamically configuring operations for
both CPU and GPU based on pipeline latency targets, Llama achieves on average
7.8$\times$ latency improvement and 16$\times$ cost reduction compared to four
state-of-the-art cluster and serverless video analytics and processing
systems: Nexus (sosp19-nexus, ), Scanner (siggraph18-scanner, ), gg (atc19-gg,
), and GrandSLAm (eurosys19-grandslam, ).

##  2\. Background and Motivation

Figure 1. Simple DAGs that can be used to compose complex video pipelines.

Figure 2. An AMBER Alert pipeline that finds faces and cars in a video.

|  |  | InferLine
---
(socc20-inferline, )
| GrandSLAm
---
(eurosys19-grandslam, )
| VideoStorm
---
(nsdi17-videostorm, )
| Focus
---
(osdi18-focus, )
| Nexus
---
(sosp19-nexus, )
| Scanner
---
(siggraph18-scanner, )
| gg
---
(atc19-gg, )
| Sprocket
---
(socc18-sprocket, )
Llama
| Performance targets | Yes | Yes | Yes | Yes | Yes | No | No | No | Yes
Features | General operations | No | No | Yes | No | No | Yes | Yes | No | Yes
| Traverse large configuration space | Limited$\mathparagraph$ | Limited$\mathparagraph$ | Limited$\dagger$ | Limited$\mathparagraph$ | Limited$\mathparagraph$ | No | No | No | Yes
| Handle input-dependent exec. flow | No | No | No | No | Yes | No | Limited$\ddagger$ | No | Yes
Challenges | Dynamically adjust resource alloc. | Yes | No | Limited$\mathsection$ | No | Limited$\mathsection$ | No | Yes | Yes | Yes

Table 1. Comparison of existing video processing systems with Llama based on
whether they (a) support performance targets and general operations, and (b)
address the challenges of meeting performance targets for general video
pipelines. $\mathparagraph$Limited to domain-specific knobs. $\dagger$Large
profiling overhead. $\ddagger$Cannot handle branching. $\mathsection$Limited
to single hardware platform.

Applications define _video pipelines_ as directed acyclic graphs (DAGs), where
vertices represent video analytics and processing operations, while edges
represent dataflow.

As described in literature (aws-step-functions, ; eurosys19-grandslam, ;
sec18-costless, ), video pipelines can be composed from three basic DAG
patterns shown in Figure 2: (a) sequential, where each vertex has at most one
input and one output, (b) parallel, where multiple vertices execute in
parallel, and (c) branching, where the output of a vertex, called branching
vertex, conditionally determines the next vertex to execute. For example, the
AMBER Alert pipeline (nsdi17-videostorm, ; sosp19-nexus, ) for face and car
recognition in Figure 2 begins with a sequential path of decoding and
preprocessing operations, followed by a branching object detection operation.
Depending on the output, people or cars are sent to parallel face and car
recognition operations, respectively.

Table 1 categorizes video analytics and processing systems based on two key
features: (a) Their ability to specify and meet performance targets. User-
facing systems typically require that the video pipeline meet a latency
target, ideally while minimizing resource usage (cost). For example, the AMBER
Alert pipeline needs to meet a strict latency target so that responders can
take timely action. (b) Support for general video operations. To compose video
pipelines, a user combines video operations (e.g., inference models, video
encoders, and image filters) with analytics operations that process extracted
metadata. For example, the AMBER Alert pipeline will contain video decoding,
object detection, face recognition, and car model recognition. Some systems,
such as Scanner (siggraph18-scanner, ), VideoStorm (nsdi17-videostorm, ), and
gg (atc19-gg, ), support general video operations. Others, such as Focus
(osdi18-focus, ), Nexus (sosp19-nexus, ), GrandSLAm (eurosys19-grandslam, ),
and InferLine (socc20-inferline, ) focus on one facet of video pipelines
(e.g., deep learning inference) and rely on external services for other
operations.

###  2.1. Challenges

Large configuration space.  Pipeline operations offer a variety of knobs that
can be tuned to improve latency and resource use. For example, many operations
have knobs such as batch size, sampling rate, and resolution. Other knobs
select the hardware platform (e.g., CPU, GPU, TPU, etc.) and set the resource
allocation (e.g., CPU cores or GPU memory). Determining configurations is
challenging due to the exponential growth in the configuration space with the
number of operations, knobs, and hardware platforms available.

As shown in Table 1, Scanner, gg, and Sprocket do not auto-tune configurations
knobs, putting the burden on the user to statically specify good operation
configurations. Focus, Nexus, GrandSLAm, and InferLine are domain-specific to
deep learning inference and are limited to configuring the inference models
used and the batch size. VideoStorm supports general knob configurations;
however, it takes tens of CPU hours to profile pipelines and requires re-
profiling when the pipeline, input video, or latency targets change
(nsdi17-videostorm, ).

Input-dependent execution flow.

Figure 3. Execution latency on CPU (left) and GPU (right) for a face detection
pipeline that identifies unique faces in a frame (dlib09, ). Latency varies up
to 17.2$\times$ and 4$\times$ on CPU and GPU, respectively.

Input-dependent execution flow occurs in two cases: First, inputs determine
the conditional path in branching pipelines. In the AMBER Alert pipeline of
Figure 2, a frame will only take the face recognition path if object/detection
finds a person in it. Since a conditional path is not resolved until the
branching operation finishes, provisioning resources and selecting
configurations to meet a pipeline’s latency target is challenging. Existing
systems either treat branching pipelines as parallel ones (i.e., by executing
all conditional branches) (siggraph18-scanner, ; eurosys12-jockey, ;
socc20-inferline, ) or do not support non-sequential pipelines
(eurosys19-grandslam, ; nsdi17-videostorm, ; socc18-sprocket, ).

Second, operations can produce a variable number of outputs, and thus a
variable load for downstream operations. If the number of intermediate outputs
is unknown until the operation is executed, determining the parallelism or
resources needed downstream to meet latency targets is difficult, especially
if these operations are computationally expensive. Figure 3 shows the latency
for a pipeline that identifies the unique faces in a frame depends on the
number of unique faces: 17.2$\times$ and 4$\times$ difference between 60 faces
versus no faces on a CPU and a GPU, respectively. Thus, the nondeterminism
introduced by input-dependent behavior requires systems to dynamically adapt
to meet a pipeline’s latency target (eurosys12-jockey, ). Most existing video
analytics and processing systems do not account for input-dependent execution
flow.

Dynamically adjusting resource allocation of operation invocations.  As a
pipeline executes, the degree of available parallelism depends on the various
knob settings (e.g., batching) and the number of intermediate outputs. Many
existing systems require users to statically provision a cluster, which limits
the resources available to exploit parallelism (eurosys19-grandslam, ;
eurosys12-jockey, ) or leads to over-allocation and higher costs when
parallelism is low. Some systems periodically adjust resources and bin pack
requests as the load changes, but are limited by how quickly hardware (e.g.,
GPUs) and VMs can be loaded/unloaded (sosp19-nexus, ). Systems like gg
(atc19-gg, ) and Sprocket (socc18-sprocket, ) leverage serverless platforms
(awslambda, ; azurefunctions, ; gcf, ) to dynamically allocate resources for
each operation invocation. However, serverless platforms still require users
to manually select hardware types and configure knobs to meet latency targets.

##  3\. Llama Design

Llama is a heterogeneous and serverless framework for auto-tuning video
analytics and processing pipelines. Llama’s objective is to meet the overall
pipeline latency target, while minimizing cost (resource usage). As noted in
Section 2, input-dependent execution flow and resource volatility preclude the
use of static tuning approaches (eurosys12-jockey, ). They also preclude
designing and calculating a globally-optimal solution a-priori or dynamically.
Instead, Llama optimizes the overall pipeline execution by iteratively and
dynamically optimizing each operation invocation using the most up-to-date
information about the state of execution flow and resource availability.
Specifically, Llama (a) dynamically reduces the pipeline target latency to
per-operation invocation latency targets, values that we call _slack_ , and
(b) continuously configures each operation invocation to meet the slack at
minimal cost. Dynamically allotting slack ensures the pipeline latency target
is met without having to statically account for all possible conditional paths
or sources of resource volatility in serverless environments. It also allows
Llama to revisit configuration decisions as the resource environment evolves
or as input-dependent operations are run. Llama finds the set of cost-
efficient configurations for the entire pipeline because it minimizes cost at
each configuration assignment subject to the overall latency target.

We address the challenges outlined in Section 2 as follows:

Traversing the large configuration space.  Llama profiles and makes
configuration decisions on a per-operation, not per-pipeline basis. New
operations undergo a short (seconds to minutes), one-time profiling step
independent of the pipelines that include the operation. Operations are not
re-profiled as the pipeline composition, video, or latency targets change. As
the pipeline executes, Llama makes configuration decisions for one operation
invocation at a time, reducing the exponential configuration space of an
entire pipeline to that of an individual operation.

Handling input-dependent execution flow.  Llama uses three techniques to meet
latency targets despite the nondeterminism that stems from input-dependent
behavior and resource volatility (e.g., resource contention): (a) _early
speculation and late commit_ selects an initial configuration decision as soon
as an invocation is available, then revisits the configuration right before
execution, (b) _priority-based commit_ prioritizes operations based on their
affinity to hardware and their depth in the pipeline, and (c) _safe delayed
batching_ waits for additional inputs for batching, as long as doing so does
not violate the invocation’s allotted slack.

Dynamically adjusting resource allocations.  Making per-invocation
configuration decisions also allows Llama to dynamically right-size resource
allocations across heterogeneous serverless backends. Llama decides the
hardware type and resource sizing (e.g., GPU with 2GB of memory) during
dynamic configuration based on what is necessary to meet the slack. Early
speculation and late commit, as well as priority-based commit, also allow
Llama to balance resources between operations.

###  3.1. Architecture

Figure 4. Llama’s architecture diagram.

Llama uses an offline specification phase and an online optimization phase
(Figure 4). The specification phase has two purposes. First, it allows the
user to specify a pipeline with multiple, general operations using a SDK.
Second, it extracts the following information: a set of all possible
sequential paths through the pipeline, and the latency and resource footprint
of each unique operation across possible knob configurations. The pipeline
specification and the extracted metadata are stored for use during the online
phase.

The online phase is triggered when users submit an input video and a latency
target to Llama. Llama executes the pipeline by continuously generating and
executing a set of invocations for each operation as their input dependencies
are resolved. For example, if object-detection outputs a frame tagged with a
person, a new invocation is generated for the preprocess operation in the
AMBER Alert pipeline (Figure 2). The online phase configures each invocation
by first estimating its slack. It then uses the respective operation’s
profiling data to determine the most efficient configuration for completing
the invocation within the allotted slack. The process repeats until all
pipeline invocations are executed.

###  3.2. Specification phase

Application Interface.  Users specify pipeline operations, dependencies
between operations, and conditional flow using the Llama SDK. Llama provides a
library of operations (e.g., decode and face recognition). Each operation
consists of a binary executable, indexed by its SHA256 hash, and a
configuration specification file that contains configuration options and
performance statistics for the operation. Users can optionally bring their own
operations by providing an executable and a configuration template that
specifies tunable knobs (e.g., hardware type, batch size, or number of
filters), the ranges for each knob, and the granularity of this range (e.g.,
batch size increasing by powers of 2). The Operation-Profiler uses these
inputs in a one-time profiling step to generate a configuration specification.
The operation and configuration specification are then added into the Metadata
Store and re-used across pipelines without further profiling.

Operation-Profiler.  The Operation-Profiler collects performance and resource
statistics for each operation. Using the operation executable and
configuration template as inputs, it first enumerates all possible
configurations specified by the template, then executes a short profiling step
using one or more sample frames for each configuration (depending on the batch
size). Statistics such as latency and resource footprint (e.g., peak memory
utilization) are collected and stored as configuration specification file
entries. The frame content does not affect these statistics (recall that
input-dependent execution flow manifests between operations). Since slack
calculation (Section 4.1) is only dependent on the _relative_ performance of
operation invocations across the pipeline, the Operation-Profiler designates a
_reference configuration_ for each operation to provide a measure of relative
performance. We chose the smallest CPU configuration (1-core, batch-1) for
each operation’s reference configuration. During runtime, operation invocation
performance that differs from its profiled value, due to resource contention
or profiling inaccuracy, is managed by leveraging feedback (Section 3.3).

The configuration specification is structured so arbitrary operation- and
hardware-specific configuration knobs can be described by users, and
dynamically configured during runtime. This enables Llama to support general
operations and arbitrary video pipelines for a myriad of applications.

Pipeline-Decomposer.  To enable the online phase to dynamically compute slack,
the Pipeline/Decomposer performs a one-time _decomposition_ of the pipeline
into all possible sequential paths in the pipeline. To do so, it performs a
modified depth-first search on the pipeline DAG to enumerate all paths from
the input operation (i.e., operation with no upstream dependencies) to an
output operation (i.e., an operation with no downstream dependencies). It then
emits an intermediate representation of the decomposed paths into the Metadata
Store. For example, the AMBER Alert pipeline in Figure 2 is decomposed into
the two sequential paths ending in face/recognition and car/recognition,
respectively.

###  3.3. Online phase

Manager.  Llama’s Manager takes video inputs and latency targets and
orchestrates the entire pipeline execution, maintaining execution state and
generating new invocations. Whenever an invocation completes, the Manager
records the invocation’s runtime statistics (i.e., latency, cost, and
configuration) and the location of intermediate outputs. The runtime
statistics are used to update the configuration profiles obtained from the
Operation-Profiler via a feedback loop. We use an exponential smoothing
algorithm to update the profiling; other algorithms can be incorporated as
well. The intermediate outputs are then used to resolve any conditional
branches. The Manager then spawns invocations for downstream operations once
all dependencies have been resolved. These invocations are then sent to the
Configurator.

Configurator.  To meet the overall pipeline latency target, the Configurator
(Figure 5) decides (a) how much slack to allot to an operation invocation, and
(b) what the most efficient configuration is to meet the slack. The
Configurator works with the Scheduler to keep track of available resources at
a serverless backend as it makes configuration decisions.

Scheduler.  After the Configurator has configured an invocation’s knobs, the
invocation is sent to the Scheduler for execution. The Scheduler executes the
configured invocations on the hardware platform specified by the Configurator.
This includes creating and managing the necessary backend connections,
mitigating stragglers, and handling invocation failures (Section 4.5). When an
invocation successfully returns, the Scheduler provides the Manager with the
invocation metadata and output results.

Figure 5. Configurator diagram.

##  4\. Target Latency-Aware Configuration

Input-dependent execution flow and backend resource volatility require the
Configurator to dynamically determine each operation invocation’s most
efficient knob configurations. The Configurator is divided into two parts. The
Logic Plane (a) determines how much slack can be spent on its invocation, and
(b) uses a cost-based optimizer to select a configuration to meet that slack.
The Data Plane manages configured operations in queues prior to their
execution.

Algorithm 1 Operation invocation slack allotment

1:$paths\leftarrow$ A set of all sequential paths in the pipeline

2:$t\leftarrow$ elapsed time

3:$target\leftarrow$ pipeline latency target

4:procedure ComputeSlack($op,\lambda$)

5: $slacks=\\{\\}$

6: for all {$path\in paths\mid op\in path$} do

7: $pLat=\textsc{RemainingPathLatency}(op,path)$

8: $remainingTime=(target-t-queueingTime(\lambda))$

9: $pSlack=(op.ReferenceLat()/pLat)\times remainingTime$

10: $slacks.append(pSlack)$

11: return $min(slack\in slacks)$

###  4.1. Determining an invocation’s slack

Given a user-specified pipeline latency target, the Configurator first needs
to compute a slack for each operation invocation. Existing systems (e.g.,
GrandSLAm (eurosys12-jockey, ) and Fifer (middleware20-fifer, )) statically
determine each operation invocation’s slack by assuming a linear pipeline with
predictable invocations and latencies (i.e., no nondeterminism). Our insight
is to instead _dynamically_ calculate each operation invocation’s slack, which
we subsequently use to select the best invocation configuration (Section 4.2).
Doing so across invocations efficiently meets the pipeline latency target.

Llama calculates an operation invocation’s slack using Algorithm 1. Given an
invocation of operation $op$ and a configuration’s backend $\lambda$,
ComputeSlack begins by finding every sequential path through the DAG
containing $op$ (Line 6). It then estimates the latency to complete the path,
starting at $op$, using the reference configuration for each operation
(Section 3.2). By using the reference configuration’s latency, Llama avoids a
causal dilemma of needing a configuration to compute slack, and needing a
slack to select a configuration. The operation invocation’s slack for that
path is then determined based on the remaining time (Line 8), factoring in
estimated queueing time at $\lambda$, weighted by the relative latency of $op$
to the remaining path (Line 9). The final slack for an invocation of $op$ on
$\lambda$ is then the minimum slack value over all possible execution paths of
$op$, which accounts for all input-dependent branch resolutions (Line 11). We
discuss how Llama reclaims overly-conservative slack next.

###  4.2. Navigating the configuration space

Since slack is calculated for each operation invocation, Llama can quickly
evaluate configurations in a smaller per-operation, not per-pipeline,
configuration space. After calculating the invocation’s slack for each
available serverless backend $\lambda$ (Algorithm 1), Llama applies the
objective function shown in Equation 1 for all possible configurations $x$ of
$op$ using the invocation slack corresponding to the serverless hardware
backend $\lambda(x)$ targeted by $x$. $C(x)$ and $L(x)$ are the estimated cost
and latency respectively to run configuration $x$. $R(x)$ is the resources
requested by $x$ (e.g., amount of memory), and $R_{total}(\lambda(x))$ is the
resource limit of $\lambda(x)$. $B(x)$ is the batch size of configuration $x$,
and $\alpha$ is a tunable weight.

(1) $\small obj(x,slack)=\begin{cases}C(x)/B(x)&L(x)<slack\\\
\frac{C(x)}{B(x)}+\alpha\frac{(L(x)*R(x))}{(B(x)*R_{total}(\lambda(x))}&otherwise\end{cases}$

Intuitively, this objective function evaluates the monetary cost to run $x$
when there is a feasible slack. If slack cannot be met (e.g., if the user
submits an unachievably low target), the cost function weighs in favor of
potentially more expensive configurations that achieve a higher throughput.
$\alpha$ sets the balance between cost and throughput, with high values of
$\alpha$ set to meet the slack at all costs, while lower values of $\alpha$
may leverage more cost-efficient configurations potentially at the expense of
exceeding slack. The configuration objective function is independent of the
input video or overall pipeline.

Users who wish to optimize for a different metric (e.g., minimal latency
subject to a cost budget) can add their own objective function to Llama.
Furthermore, since $R$ is specific to each backend (e.g., concurrent
invocation limits, GPU memory, or CPU cores), Llama can support other
heterogeneous backends (e.g., serverless GPUs or on-premise clusters).

Since conditional flow will not always resolve to the worst-case path, the
allotted slack may result in a configuration with a lower-than-necessary
latency. However, since each invocation is configured separately and
dynamically, future invocations will recover efficiency from earlier mis-
predictions.

###  4.3. Revisiting configuration decisions

To manage invocations that cannot be run concurrently due to limited backend
parallelism, Llama locally queues invocations and accounts for the queueing
time when allotting slack (Line 9 in Algorithm 1). The queueing time depends
on $x_{i}$: the selected configuration of each queued invocation $i$ (i.e., it
is not sufficient to use the number of queued operation invocations as a
measure of wait time (eurosys12-jockey, ; eurosys16-tetrisched, )). Thus,
invocations need to be assigned a configuration before they are queued.
However, the initial configuration $x_{i}$ is often made many seconds before
it is actually invoked, leading to sub-optimal configurations for three
reasons. (a) Invocations queued in front of $i$ may experience execution times
that vary from the profiled values. This can occur due to resource contention
or input-dependent execution flow. (b) The estimated latency for $x_{i}$ may
be updated via feedback while it is queued. (c) The number of invocations
queued behind $i$ may quickly grow (e.g., many completed object/detection
invocations may output a large number of car/recognition and face/recognition
invocations); thus, $x_{i}$ should be chosen to ensure upstream invocations
can meet their slack. Hence, by the time a queued invocation is ready to run,
its selected configuration needs to be revisited to determine if it is still
the right configuration.

To solve this, Llama leverages a novel technique inspired by late binding
(nsdi20-sol, ; sosp13-sparrow, ; eurosys18-bindschaedler, ; osdi18-qoop, ;
osdi14-venkataraman, ) that we call early speculation and late commit. With
early speculation and late commit, Llama maintains two queues per serverless
backend $\lambda$: an unbounded speculative queue ($SQ[\lambda]$) and a small,
bounded commit queue ($CQ[\lambda]$) set to hold enough invocations to
saturate $\lambda$. Once an invocation $i$ is ready to execute, the
Configurator uses Algorithm 1 to assign it a slack, and uses Equation 1 to
select a _speculative configuration_. The configured invocation is then put
into the appropriate speculative queue, thus enabling Llama to estimate the
queueing time at each backend. Once $i$ reaches the head of the speculative
queue, as prior invocations are executed, Llama revisits the configuration of
$i$ by using Algorithm 1 and Equation 1 again. It then _commits_ the
configuration into the appropriate commit queue. Doing so mitigates the
queueing challenges we noted above by delaying binding an invocation to a
final configuration for as long as possible. This provides Llama with maximum
flexibility and the most up-to-date state about pipeline dataflow and
performance at each backend.

With early speculation and late commit, Llama can estimate the queueing time
using Equation 2 for each serverless backend $\lambda$ based on each
configured invocation $i$ in its queues. $L(x_{i})$ and $R(x_{i})$ are the
estimated latency of, and resources requested by $x_{i}$, respectively.
$R_{total}(\lambda(x_{i}))$ is the total amount of resources or concurrency
limit at the serverless backend specified by the configuration $x_{i}$.

(2) $\small
Q_{SQ[\lambda],CQ[\lambda]}=\sum_{i\in\\{SQ[\lambda],CQ[\lambda]\\}}L(x_{i})\frac{R(x_{i})}{R_{total}(\lambda(x_{i}))}$

Intuitively, the queueing time is the sum of each $x_{i}$’s profiled
configuration latency, weighted by $x_{i}$’s requested resources (to account
for parallel execution). The cumulative queueing time over $SQ[\lambda]$ and
$CQ[\lambda]$ is then used in ComputeSlack. $SQ[\lambda]$ is included when
committing configured invocations to account for invocations queued behind
$i$. We do not incorporate future operations’ queueing time, since dynamicity
and the need to assign a configuration to each downstream operation can result
in inaccurate estimates.

###  4.4. Inter-operation prioritization

####  4.4.1. Challenges

The Configurator’s decisions described in Section 4.2 assume per-operation
invocation decisions can be made independently of each other. However, Llama
also needs to reason about the relationship between operations and their
invocations for the following reasons:

When to batch invocations.  As pipeline dataflow progresses, there can be
moments when an operation may have fewer invocations available than the most
efficient configuration’s batch size. For example, if a pipeline contains a
slower face detection operation followed by a faster blurring operation, the
blur operation’s invocations will likely drain the speculative queue faster
than it can build up. In such cases, executing upstream operations first
yields a larger batch size, amortizing RPC and I/O overheads. However, waiting
for upstream operation invocations to complete their execution may result in a
slack violation.

Under-allotting slack due to incorrect profiling.  As described in Section
4.1, slack allotted to an invocation is a function of the reference
configuration’s profiled latency for downstream operations. Furthermore, a
configuration’s latency is updated using a feedback loop after execution
(Section 3.3). However, slack can be under-allotted to operation invocations
if the reference configuration latency is significantly shorter than its
actual latency, and the feedback loop is not closed early on during pipeline
execution. This is especially problematic for longer pipelines, and for
pipelines with the last operation’s invocations needing a longer slack than
the rest. Thus, it is beneficial to prioritize invocations by pipeline depth
early in the pipeline’s execution so that feedback can update all reference
configurations.

Affinity of operations to heterogeneous hardware.  While prioritizing
invocations by pipeline depth can help prevent under-allotting slack, the
issue of prioritizing operation invocations on particular hardware platforms
still remains. For example, consider the case in which both an
object/detection and face/recognition invocation must be configured. Assume
that while both operations run faster on a GPU, face/recognition benefits more
from acceleration and observes a larger latency reduction. Resource limits
force the two invocations to split their decision between $\lambda_{CPU}$ and
$\lambda_{GPU}$. Committing object/detection’s invocation first forces
face/recognition’s invocation to choose $\lambda_{CPU}$. However, the better
decision is to assign the CPU to object/detection and the GPU to
face/recognition. The relative benefit of running operation invocations on a
particular hardware platform (i.e., its hardware affinity) must be
incorporated into configuration decisions.

####  4.4.2. Our solution

Llama addresses these challenges using safe delayed batching and priority-
based commit, implemented in conjunction with early speculation and late
commit.

Safe delayed batching.  Safe delayed batching addresses the challenge of
waiting for additional invocations to batch. During both early speculation and
late commit, if Llama determines the most cost-efficient configuration that
meets slack has a batch size larger than the number of invocations available
for a given operation (using Equation 1), it waits until more invocations
arrive to assign a configuration. It does so _safely_ — only if there are
enough upstream invocations and slack will not be violated. Otherwise, it uses
the best feasible configuration.

Priority-based commit.  Priority-based commit addresses the challenges of
under-allotting slack and operations’ affinity to heterogeneous hardware.
First, to address the challenge of under-allotting slack, the Configurator
prioritizes invoking a certain number of reference invocations for each
operation, favoring deeper operations in the pipeline. This ensures the
feedback loop for all reference configurations is closed as fast as possible
to minimize under-allotted slack.

Second, to compute an operation’s affinity to heterogeneous hardware, Llama
compares the benefits an operation invocation receives from running on a
specific backend to other available backends. It computes the _affinity_ of an
invocation’s operation $op$ to hardware backend $\lambda$ using Equation 3,
where $X_{op,\lambda}$ is the subset of configurations for $op$ that run on
$\lambda$ and $X_{op,\lambda}^{\mathsf{c}}$ is the complementary set (i.e.,
all other configurations for $op$).

(3) $affinity(op,\lambda)=\frac{\min_{\forall x\in
X_{op,\lambda}^{\mathsf{c}}}\\{obj(x,slack)\\}}{\min_{\forall x\in
X_{op,\lambda}}\\{obj(x,slack)\\}}$

Intuitively, Equation 3 determines if a hardware backend provides more benefit
(via Equation 1) to an invocation than other backends. Llama prioritizes
invocations from operations with a higher affinity to a hardware backend
$\lambda$ when committing them to each $CQ[\lambda]$. This ensures each
backend achieves its highest utility.

###  4.5. Handling stragglers and invocation failures

During execution, operation invocations may straggle or fail to execute
(nsdi13-dolly, ; socc14-wrangler, ; osdi04-mapreduce, ). The Scheduler keeps
track of each invocation’s execution time. If it exceeds a configurable time-
out (discussed in Section 5) or the Scheduler receives an error, the Scheduler
notifies the Manager to create a duplicate invocation. This duplicated
invocation is then passed to the Configurator to begin the slack allotment and
configuration process anew. The allotted slack will now be reduced,
potentially resulting in a different configuration to still meet the pipeline
latency target (evaluated in Section 6.4).

##  5\. Implementation

We implemented Llama as an extension to gg in $\sim$4K lines of C++ code. We
modified gg’s C++ and Python SDK to support complex pipelines and general knob
configurations. Llama supports operations from any framework or library; we
implemented non-deep learning pipeline operations (e.g., blur and meanshift)
using OpenCV (opencv_library, ) and FFmpeg (ffmpeg, ), and deep learning
pipeline operations with TensorFlow (tensorflow, ). Llama’s source code will
be available upon publication.

We implemented the online phase on top of gg’s dispatcher and backend resource
manager. The online phase is single-threaded, but can scale out to multiple
threads as needed. For straggler mitigation, we set each invocation’s time-out
value to 1.5$\times$ the invocation’s profiled latency. Larger values wait too
long to spawn a duplicate invocation, which may violate the pipeline latency
target, while smaller values unnecessarily overload the speculation queues.
For depth-first priority, we observed that 10 invocations of the reference
configuration were sufficient to obtain enough feedback values to converge on
a latency measurement. Smaller values do not collect enough feedback values to
prevent under-allotted slack, while larger values unnecessarily prioritize
invocations with configurations that may not be efficient.

For the offline specification phase, we implemented the Operation-Profiler as
a client to the online phase that collects and stores the profiled metadata
into configuration specifications. Configuration specifications are
implemented as JSON files. The Metadata Store is implemented in an object
store (e.g., Google Cloud Storage).

We deployed Llama with serverless CPUs and serverless GPUs as compute
backends. For serverless CPUs, we provision and manage a cluster of CPUs
similar to existing serverless offerings (atc18-peeking, ). Each invocation
requests a specific number of cores (up to 4). Llama also supports running on
serverless computing services such as AWS Lambda (awslambda, ) or Google Cloud
Functions (gcf, ), where the invocation resources requested would be an amount
of DRAM.

Since there exists no serverless GPU services or frameworks at the time of
writing, we built our own implementation ($\sim$1K lines of C++ code) that we
believe is representative of a future production offering (hotchips-gpu, ).
Similar to CPU serverless offerings, an invocation requests an amount of GPU
memory (in MB) per invocation. Our serverless GPU scheduler then allocates a
proportional amount of GPU threads using Nvidia MPS (mps, ), allowing for
multiple invocations to execute concurrently. Invocations are executed on a
first-come, first-served basis. Llama is also compatible with GPUs that
support concurrent job execution in hardware (a100, ).

##  6\. Evaluation

Pipeline | Description | Length (Form) | Operations (# of total configurations) | Video input
---|---|---|---|---
AMBER Alert | detect cars and people | 5 (branching) |  decode$\dagger$, preprocess$\dagger$, object detect., face recog., car recog. (646) |  traffic camera (traffic, ), 10 min, 1080p
Face Blurring | detect indiv. face and blur from all frames | 5 (branching) |  decode$\dagger$, preprocess$\dagger$, face recog., template match$\dagger$, blur$\dagger$ (600) |  rally (bernie, ), 10 min, 720p
Denoising | detect indiv. face and denoise/segment | 5 (branching) |  decode$\dagger$, preprocess$\dagger$, face recog., template match$\dagger$, meanshift$\dagger$ (600) |  rally (bernie, ), 10 min, 720p
Toonify | apply cartoon effect to video | 4 (parallel) |  decode$\dagger$, edge detect.$\dagger$, bilateral filter$\dagger$, merge edge-filter$\dagger$, encode$\dagger$ (989) |  tears of steel (tears-steel, ), 10 min, 720p
Synthetic | synthetic pipeline for sensitivity analysis | 7 (sequential) |  decode$\dagger$, blur$\dagger$, preprocess$\dagger$, face recog. (596) |  rally (bernie, ), 10 min, 720p

Table 2. Video pipelines used for evaluating Llama, their operations, and
video inputs. $\dagger$ are non-deep learning pipeline operations.

We answer the following questions: (a) How does Llama compare to state-of-the-
art systems (Scanner, Nexus, gg, and GrandSLAm)? (b) How effective is Llama in
meeting diverse latency targets? (c) How does each technique employed by
Llama, such as early speculation and late commit and safe delayed batching,
contribute to its ability to meet the latency target? (d) What is the impact
of profiling errors and failures on Llama’s ability to meet latency targets?
(e) What are the overheads of various decisions Llama makes?

Metrics.  Unless otherwise noted, we use pipeline processing latency and cost
as metrics for success (similar to (eurosys19-grandslam, ; socc18-sprocket, ;
socc20-inferline, )). For each experiment, we report the mean of three runs.

Experimental setup.  We deployed Llama on Google Cloud Platform (GCP) (gcp, ).
The Llama runtime ran on a n1-standard-8 instance (8 vCPUs, 30 GB of DRAM). We
used the following setup unless otherwise noted. For the serverless CPU
backends, we used 10 n1-standard-64 (64 vCPUs, 240GB of DRAM). For the
serverless GPU backends, we used 2 custom-12-46080 (1 V100 GPU, 12 vCPUs, 45
GB of DRAM). All instances feature Intel Xeon Platinum E5-2620 CPUs operating
at 2.20GHz, Ubuntu 16.04 with 5.3.0 kernel, and up to 32 Gbps networking
speed.

Baseline systems.  We compared Llama with three sets of systems: (a) cluster
systems (Scanner and Nexus), (b) serverless systems (gg), and (c) target-aware
systems (GrandSLAm). Scanner is used by Facebook for processing 360∘ videos
(scanner-website, ). Nexus accelerates deep learning-based video analysis on
GPUs. gg is a general purpose serverless framework. GrandSLAm estimates slack
to meet pipeline latency targets for sequential, DNN-only pipelines. We
evaluated two common Scanner setups: one in which a user only provisions a
cluster with CPUs (sc-cpu), and one in which, similar to Nexus, a user runs
all operations on a GPU (sc-gpu). For gg, we also compared against a version
augmented with Llama’s branching support (gg-branch). sc-cpu, gg, and gg-
branch do not support heterogeneous accelerators, while Nexus and sc-gpu
require GPU VMs. Since GrandSLAm does not natively support non-sequential
pipelines, and does not account for input-dependent execution flow, we
implement it with Llama by disabling early speculation and late commit,
feedback, and depth-first priority. However, GrandSLAm still has access to
Llama’s branching support, safe delayed batching, priority-based commit, and
dynamic resource allocation across heterogeneous backends (GrandSLAm++). To
equalize compute resources provided to all systems, we observe that
custom-12-46080 and n1-standard-64 VMs are effectively priced the same on GCP
(a difference of 1% at the time of writing). (This price-equivalency is also
true for equivalent instances on AWS.) Thus, we provisioned sc-cpu, gg, gg-
branch, and GrandSLAm++ with 12 n1-standard-64, and Nexus and sc-gpu with 12
custom-12-46080.

Resource requests and cost model.  For Llama, gg, and GrandSLAm++, each
invocation requests a set amount of resources (GPU memory or CPU cores) as is
done in commercial serverless offerings. The respective backend then
provisions the invocation with the requested resources, and charges a price
based on the amount of requested resources and invocation latency. We
calculate the price (in $/(resource-second)) by dividing the cost per second
charged by GCP by the VM’s total resources. For example, the price of a V100
GPU invocation is calculated by dividing the price of custom-12-46080 by
$16GB$. Since Scanner and Nexus are cluster-based frameworks, we compute cost
using the time to rent the cluster for the duration of the execution; we do
not include the cost of starting and maintaining a warm cluster.

Video pipeline.  Table 2 shows the pipelines, operations, and videos that we
used. For branching pipelines, only invocations satisfying the branching
condition are executed. For AMBER Alert, only frames with faces and cars
execute their respective recognition paths. For Face Blurring and Denoising,
frames with faces proceed to a template match operation where the frame is
compared against a pre-determined face. If a match is found, the face in the
frame is then blurred, or denoised using meanshift. The Toonify pipeline
executes the bilateral filtering and edge operations in parallel before
merging and encoding the frames. Finally, the synthetic pipeline is a chain of
5 image blurring operations followed by a face recognition operation. The face
recognition operation is the most compute-intensive operation of this
pipeline, which allows us to evaluate Llama’s ability to meet diverse pipeline
latency targets, even when configurations were mis-profiled (Section 6.4).
Since sc-cpu, sc-gpu, and gg do not support branches, they execute the three
branching pipelines as parallel ones (i.e., both branches are executed).

Figure 6. Latency of baselines to execute each pipeline. Nexus only supports
the AMBER Alert pipeline (unsupported pipelines are denoted by $\times$).
Llama’s fastest execution is faster than all baselines. Figure 7. Cost
incurred by baselines for each pipeline. Nexus only supports the AMBER Alert
pipeline (unsupported pipelines denoted by $\times$). Llama’s cheapest
execution is cheaper than all baselines.

###  6.1. Comparing Llama to existing systems

We first show how Llama’s ability to dynamically reconfigure operation
invocations enables it to outperform existing systems, both in terms of
latency and cost.

Experimental setup.  For Nexus, we set the pipeline latency target to be 2
seconds per frame, which we found to be the strictest latency that does not
drop any requests (sosp19-nexus, ). Nexus then automatically configures the
batch size and number of instances for each model. For sc-cpu and sc-gpu, we
swept each operation’s batch size from 1 to 64 (by powers of 2) and set each
value based on the lowest pipeline execution latency (reported in Figure 6).
For gg and gg-branch, we set each invocation’s configuration based on the
lowest, most cost-effective CPU latency reported by the Operation-Profiler. We
configured Llama and GrandSLAm++ with two pipeline latency targets: an
unachievable low target that forced both to minimize pipeline execution
latency at the expense of cost: llama-fast and GrandSLAm++-fast, and an
overly-loose target that allowed Llama to minimize the overall cost: llama-
cheap and GrandSLAm++-cheap.

Results and discussion.  Figures 6 and 7 show the processing latency and total
cost, respectively, to execute each of the four non-synthetic pipelines. Llama
achieves lower latency, higher throughput, and lower cost than existing
systems.

Even when the cost of starting and maintaining a warm cluster are not
considered, Llama is faster (up to 65$\times$ and 28$\times$ on average) and
cheaper (up to 110$\times$ and 55$\times$ on average) than sc-cpu. Compared to
sc-gpu, Llama is up to 11$\times$ faster (6$\times$ on average) and up to
27$\times$ cheaper (18$\times$ on average). Scanner cannot dynamically adjust
and right-size invocation configurations, and thus cannot address performance
degradation caused by resource contention for compute-intensive operations
(e.g., deep learning inference and meanshift) or memory-intensive operations
(e.g., bilateral filtering).

Next, since Nexus focuses on inference-serving pipelines, we are only able to
run the AMBER Alert pipeline (other pipelines denoted by $\times$ in Figures 6
and 7). While we provide Nexus with 12 GPUs, Nexus’s bin-packing algorithm
(sosp19-nexus, ) utilizes only 8; thus we report cost for 8 GPUs. By
dynamically choosing CPU versus GPU configurations, Llama achieves 1.3$\times$
speedup and 2.8$\times$ lower cost compared to Nexus.

Compared to gg, Llama is up to 3.1$\times$ faster (2.2$\times$ on average) and
up to 8.2$\times$ cheaper (5.7$\times$ on average). Compared to gg-branch,
Llama is up to 2.9$\times$ faster (1.8$\times$ on average) and up to
6.8$\times$ cheaper (4.7$\times$ on average). While gg-branch can reason about
conditional flow, it cannot make dynamic invocation configuration decisions or
adjust to resource volatility, resulting in a higher latency and cost compared
to Llama.

Finally, Llama is up to 1.7$\times$ faster (1.2$\times$ on average) than
GrandSLAm++-fast and 1.4$\times$ cheaper (1.1$\times$ on average) than
GrandSLAm++-cheap. Since GrandSLAm++ allots slack and selects configurations
based on profiled values, it cannot dynamically adjust to nondeterminism,
which can result in slower performance or higher cost (e.g., Denoising).

By making dynamic invocation configurations, Llama is able to determine how
well operations perform across heterogeneous backends and right-size resources
depending on the pipeline latency target.

General applicability.  While Llama was designed to address the challenges of
running video analytics and processing pipelines (Section 2), its operation
configuration specification (Section 3.2) supports arbitrary operation- and
hardware-specific configuration knobs. To demonstrate this, we built a four-
stage natural language processing pipeline for applications like therapy
session analysis for at-risk youth (affcomp2019-behavior, ). The pipeline has
six models (language identification, two language translation, sentiment
analysis, text generation, and summarization) and features branching,
parallel, and sequential patterns. For a 256-line transcript, llama-fast takes
275s ($1.22) while llama-cheap takes 573s ($0.44). Thus, Llama can be used for
meeting latency targets for general domains.

Figure 8. Evaluating Llama given varied latency targets. 50%: mean of the
measured latencies of llama-fast and llama-cheap, 25%: mean of llama-fast and
50%, and 75%: mean of llama-cheap and 50%. The execution latency is normalized
to the pipeline target ($\leq$1 means target was met). Cost is in dollars.
Llama meets all latency targets and reduces overall cost for less stringent
targets.

Pipeline | # configs. used | % invoc. that met slack
---|---|---
AMBER Alert |  27 $\pm$ 8 |  92% $\pm$ 6%
Face Blurring |  29 $\pm$ 3 |  93% $\pm$ 1%
Denoising |  40 $\pm$ 4 |  99% $\pm$ 0%
Toonify |  30 $\pm$ 5 |  97% $\pm$ 3%
Synthetic |  50 $\pm$ 16 |  88% $\pm$ 3%

Table 3. Mean and standard deviation of number of configurations used and
percent of invocations that met their allotted slack. Llama accurately allots
and meets almost all slack by selecting a variety of different configurations
per pipeline.

###  6.2. Can Llama trade off latency for cost?

We now show Llama can also meet latency targets that lie between llama-fast
and llama-cheap.

Experimental setup.  For each pipeline, we provide three latency targets to
Llama that lie between the times required to execute the pipeline using llama-
fast and llama-cheap. The 50% latency target is the mean latency between the
latencies achieved by llama-fast and llama-cheap. The 25% latency target (the
most stringent of the three) is the mean latency between llama-fast and the
50% latency target. Finally, the 75% latency target (the least stringent of
the three) is the mean latency between llama-cheap and the 50% latency target.
For example, llama-fast executed Face Blurring in 155 seconds, and llama-cheap
executed it in 423 seconds; the 25%, 50%, and 75% latency targets are 225,
290, and 380 seconds respectively.

Results and discussion.  Figure 8 shows the observed execution latency,
normalized to each of the aforementioned pipeline latency targets ($\leq$1
means that the latency target was met), as well as the raw cost values for
each pipeline execution. Llama not only meets all latency targets, but also
dynamically adjusts its configuration decisions to choose cost-efficient
configurations as the latency target became less stringent. For the Denoising
and Synthetic pipelines, the cost stays the same for the 50% and 75% targets.
This is due to Llama selecting similar invocation configurations during both
runs, since it determined them to be the most cost-efficient configurations
for both latency targets.

Table 3 shows a breakdown of how many configurations were used to meet the 50%
pipeline latency target, and what percent of invocations met the slack. We
note that (a) Llama meets the slack for 94% of invocations on average across
all pipelines, with the lowest being the Synthetic pipeline since it is the
longest, and (b) the number of configurations used varies per pipeline. Thus,
Llama’s slack allottment and configuration selection algorithms (Section 4)
are effective in meeting pipeline latency targets while minimizing cost.

Figure 9. Impact of turning Llama’s techniques off on the AMBER Alert and
Toonify pipelines. Red borders and circled slashes indicate the pipeline
latency target was violated. FB is feedback, DFP is depth-first priority, SDB
is safe-delayed batching, ESLC is early speculation and late commit, and PBC
is priority-based commit.

###  6.3. Ablation study of Llama’s techniques

We now show how each technique of Llama contributes to its ability to
efficiently meet pipeline latency targets.

Experimental setup.  We performed an ablation study with two distinct
pipelines: Amber Alert and Toonify. Following is the list of techniques
employed by Llama: feedback loop (FB, Section 3.3), depth-first priority (DFP,
Section 4.4), safe delayed batching (SDB, Section 4.4), early speculation and
late commit (ESLC, Section 4.3), and priority-based commit (PBC, Section 4.4).
Note that priority-based commit includes both depth-first priority and
hardware affinity. For each run, we turn off a single technique and record the
pipeline execution latency and cost. For each pipeline, we use its 50%
pipeline latency target specified in Section 6.2.

Results and discussion.  Figure 9 shows the results of our ablation study (red
borders and circled slashes indicate the latency target was violated). For the
AMBER Alert pipeline, disabling feedback, depth-first priority, or early
speculation and late commit results in latency target violations. All three
techniques allow Llama to accurately measure and adapt to performance
volatility caused by input-dependent execution flow (branching operations) and
resource contention. For example, disabling feedback causes Llama to miss the
latency target because resource contention resulted in invocations taking
longer than their profiled values. With feedback enabled, Llama is able to
detect this and choose configurations with higher throughput at a small
expense of cost-efficiency. On the other hand, disabling safe delayed batching
or priority-based commit causes Llama to not use large batches for deep
learning inference invocations on GPUs, resulting in reduced cost-efficiency.

For the Toonify pipeline, disabling feedback also causes a latency target
violation similar to the AMBER Alert pipeline. Disabling either safe delayed
batching or early speculation and late commit results in Llama choosing less
cost-efficient configurations. On the other hand, disabling depth-first
priority and priority-based commit results in more cost-efficient
configurations without violating the latency target. This is because these
techniques led to Llama choosing configurations that are more throughput-
intensive than necessary for merge edge/filter operation invocations in an
effort to meet the pipeline latency target. However, as noted for the AMBER
Alert pipeline and evaluated in Section 6.4, both depth-first priority and
priority-based commit are important for Llama’s robustness in right-sizing
resources and meeting latency targets despite profiling errors.

Pipeline (target) | Llama | Llama w/o FB & DFP
---|---|---
Denoising (350s) | (348s, $1.20) | (369s, $1.64)
Synthetic (520s) | (520s, $2.31) | (487s, $3.14)

Table 4. Impact of profiling errors. Latency and cost for the Denoising and
Synthetic pipelines when profiled values are inaccurate (set to 50% of their
measured latencies). FB is feedback and DFP is depth-first priority. Without
these techniques, Llama cannot meet the latency target, or uses configurations
that are not cost-effective.

###  6.4. Meeting targets despite profiling errors & failures

We now show that Llama can meet targets despite profiling errors and
invocation failures.

Experimental setup.  To evaluate “mis-profiling”, all operation profiled
latencies are set to 50% of their values. Separately, to evaluate Llama’s
resiliency to failures, we forced $3\%$ of invocations to fail ($2,114$ and
$3,617$ failures for the Denoising and Synthetic pipeline, respectively). For
both experiments, we used the Denoising and Synthetic pipelines because they
represent worst-case scenarios: an expensive operation at the end of the
pipeline with an under-estimated latency. In addition, the Synthetic pipeline
is the longest pipeline, which further exacerbates profiling errors: Llama
will under-allot slack to the last operation unless techniques are used to
mitigate mis-profiling. We use the respective 50% pipeline latency target from
Section 6.2 for each pipeline.

Results and discussion.  Table 4 shows the impact of profiling error on
latency and cost with (a) all of Llama’s techniques, and (b) both feedback and
depth-first priority turned off (the two techniques Llama relies on to adjust
for inaccurate profiling). For the Denoising pipeline, disabling feedback and
depth-first priority causes Llama to under-allot slack to the last meanshift
operation. This results in a missed pipeline latency target because Llama
could not adjust to the profiling errors until late in the pipeline execution.
For the Synthetic pipeline, when both techniques were off, Llama meets the
latency target but at a 35% higher cost. This is because the 50% lower-than-
profiled latencies cause Llama’s objective function (Equation 1) to
incorrectly calculate that the CPU, not the GPU, is most cost-efficient for
the meanshift operation. Since the CPU configuration was actually 50% slower
and less cost-effective than a GPU, the cost ends up being higher than if a
GPU would have been used.

When evaluating invocation failures, both pipelines were able to meet the
specified latency target despite the high failure rate using the techniques
described in Section 4.5.

These results demonstrate depth-first priority and feedback are necessary to
resolve profiling discrepancies early on during execution, and that Llama is
robust to failures.

Phase | Action | Latency (% of exec.)
---|---|---
Specification | Profiling |  257 $\pm$ 155 s
| Path decomposition | 1.74 s
Online | Speculate |  0.005 $\pm$ 0.005 ms (0.08%)
| Commit |  0.186 $\pm$ 0.813 ms (3.1%)
| Invoke |  0.151 $\pm$ 0.078 ms (2.5%)
| Finalize |  0.141 $\pm$ 1.209 ms (2.4%)
Table 5. Llama’s decision overheads. Mean and standard deviation latencies of
invocations for the AMBER Alert pipeline. Latencies are per-invocation for
online actions, per-operation for profiling, and per-pipeline for path
decomposition. For each online action, we show the percent of the execution
time spent on the action across all operation invocations (73K).

###  6.5. Overheads of decisions Llama makes

Finally, we evaluate Llama’s overheads and its ability to scale across
backends.

Table 5 shows the overhead for these decisions when specifying and running the
AMBER Alert pipeline with the 50% intermediate latency target from Section
6.2; all other pipelines have similar overheads. For the specification phase,
profiling each operation takes an average of 257 seconds, and only needs to be
performed the first time an operation is added to the Metadata Store. The
decomposition step, which is performed once per pipeline, takes only 1.7
seconds.

During the online phase, Llama only spends 483 micro-seconds, on average, to
process (i.e., speculate, commit, invoke, and finalize) an invocation,
allowing Llama to process over 2000 invocations per second. Calculating a
slack and determining a configuration is efficient, as speculate only requires
5 micro-seconds. Most time is spent evaluating priority between operations
during commit, connecting and sending invocations to backends during invoke,
and updating global state once invocations completed during finalize.

Low overheads also allows Llama to improve execution latency as the number of
resources or maximum concurrency increases. Compared to llama-fast for the
AMBER Alert pipeline run on 10 CPU and 2 GPU instances (Section 6.1), having 6
CPU and 1 GPU instances is 46% slower, while having 15 CPU and 3 GPU instances
is 25% faster.

##  7\. Related Work

Video and general-purpose analytics frameworks.  In Section 2, we describe the
limitations of several existing video analytics and processing frameworks
(sosp19-nexus, ; osdi18-focus, ; siggraph18-scanner, ; nsdi17-videostorm, ;
socc20-inferline, ; atc19-gg, ; socc18-sprocket, ). Other cluster-based and
serverless systems for both domain-specific and general-purpose applications
(hotcloud10-spark, ; eurosys12-jockey, ; atc18-videochef, ; eurosys07-dryad, ;
nsdi11-ciel, ; sigmod10-pregel, ; socc17-pywren, ) either do not support
independent-dependent execution flow, require extensive per-pipeline
profiling, or require users to configure and right-size resources. Llama meets
diverse pipeline latency targets across complex (and possibly dynamic) video
pipelines using heterogeneous serverless backends.

Dataflow optimizations and scheduling techniques.  GrandSLAm
(eurosys19-grandslam, ) and Fifer (middleware20-fifer, ) use slack to
statically determine the batch size for sequential microservice graphs.
Delayed batching is used by Clipper (nsdi17-clipper, ) to increase efficiency
of inference queries, but must be statically set by users. Late binding is
used by schedulers (nsdi20-sol, ; sosp13-sparrow, ; eurosys18-bindschaedler, ;
osdi18-qoop, ; osdi14-venkataraman, ) to maximize the flexibility of the
scheduling decision and knowledge of system state. However, these systems do
not consider the need to configure operations for meeting pipeline latency
targets. TetriSched (eurosys16-tetrisched, ) uses a scheduler that prevents
tasks from being sent to a sub-optimal set of resources due to resources being
held by earlier jobs, but only supports per-operation targets, not an end-to-
end pipeline latency target. Early speculation and late commit, and priority-
based commit allow Llama to compute slack and make configuration decisions for
arbitrarily complex pipelines to meet overall pipeline latency targets.
Musketeer (eurosys15-musketeer, ) and Dandelion (sosp13-dandelion, ) optimize
dataflow DAGs for execution on a broad range of execution engines or hardware
platforms. These optimizations are compatible with Llama, and can be used to
expand the backends and hardware platforms Llama supports.

Cost-based query optimization.  Several works have explored cost-based query
optimization for relational databases (sigmod02-rbqo, ; vldb19-lbce, ;
vldb12-dbtoaster, ; vldb18-listopt, ; vldb19-ibtune, ; vldb11-mrp, ),
including for queries whose optimal plan is input-dependent (vldb20-tempura,
). Llama is compatible with these frameworks, and can leverage their
optimizations as an extension to how configurations are selected.

Auto-tuning configurations.  CherryPick (nsdi17-cherrypick, ) and Ernest
(nsdi16-ernest, ) present a performance prediction framework for recurring
data analytics jobs; however, these systems require tens of executions of a
job to set the configuration parameters. PARIS (paris, ) focuses on VM-size
selection; OptimusCloud (atc20-optimuscloud, ) and Selecta (atc18-selecta, )
are domain-specific VM configuration systems for databases and storage
technologies, respectively. Llama dynamically configures general video
operations to meet diverse latency targets, and only requires one-time per-
operation profiling.

##  8\. Conclusion

We presented Llama, a heterogeneous and serverless video analytics and
processing framework that executes general video pipelines, meeting user-
specified performance targets at minimal cost. By dynamically configuring
individual operation invocations, Llama efficiently traverses large
configuration spaces, adapts to input-dependent execution flow, and
dynamically allocates resources across heterogeneous serverless backends.
Llama makes per-operation invocation decisions by first calculating invocation
slack, then leveraging techniques such as safe delayed batching, priority-
based commit, and early speculation and late commit to efficiently and
accurately select configurations that meet the slack. Llama achieves an
average improvement of 7.8$\times$ for latency and 16$\times$ for cost
compared to state-of-the-art systems.

## References

  * [1] Ambarella cvflow architecture, 2021.  https://www.ambarella.com/technology/#cvflow.
  * [2] Aws lambda, 2021.  https://aws.amazon.com/lambda/.
  * [3] Aws step functions, 2021.  https://docs.aws.amazon.com/step-functions/latest/dg/welcome.html.
  * [4] Azure functions, 2021.  https://azure.microsoft.com/en-us/services/functions/.
  * [5] Cisco annual internet report (2018-2023), 2021.  https://www.cisco.com/c/en/us/solutions/collateral/executive-perspectives/annual-internet-report/white-paper-c11-741490.html.
  * [6] Cnn - futuristic cop cars may identify suspects, 2021.  https://money.cnn.com/2017/10/19/technology/future/police-ai-dashcam/index.html.
  * [7] Google cloud, 2021.  https://cloud.google.com/.
  * [8] Google cloud functions, 2021.  https://cloud.google.com/functions.
  * [9] Multi-process service, 2021.  https://docs.nvidia.com/deploy/pdf/CUDA_Multi_Process_Service_Overview.pdf.
  * [10] Nvidia a100 gpu, 2021.  https://www.nvidia.com/en-us/data-center/a100/.
  * [11] Political rally video, 2021.  https://www.youtube.com/watch?v=FGDFAD3Jkuc.
  * [12] Scanner, 2021.  http://scanner.run/.
  * [13] Tears of steel, 2021.  https://www.youtube.com/watch?v=tjgM6ckoz88.
  * [14] Traffic footage, 2021.  https://www.youtube.com/watch?v=MNn9qKG2UFI.
  * [15] M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard, and et al.  Tensorflow: A system for large-scale machine learning.  In Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation, OSDI’16, page 265–283, USA, 2016. USENIX Association.
  * [16] Y. Ahmad, O. Kennedy, C. Koch, and M. Nikolic.  Dbtoaster: Higher-order delta processing for dynamic, frequently fresh views.  Proc. VLDB Endow., 5(10):968–979, June 2012.
  * [17] O. Alipourfard, H. H. Liu, J. Chen, S. Venkataraman, M. Yu, and M. Zhang.  Cherrypick: Adaptively unearthing the best cloud configurations for big data analytics.  In 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17), pages 469–482, Boston, MA, Mar. 2017. USENIX Association.
  * [18] Amazon Go.  https://www.amazon.com/b?ie=UTF8&node=16008589011, 2021.
  * [19] G. Ananthanarayanan, P. Bahl, P. Bodík, K. Chintalapudi, M. Philipose, L. Ravindranath, and S. Sinha.  Real-time video analytics: The killer app for edge computing.  Computer, 50(10):58–67, 2017.
  * [20] G. Ananthanarayanan, A. Ghodsi, S. Shenker, and I. Stoica.  Effective straggler mitigation: Attack of the clones.  In 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13), pages 185–198, Lombard, IL, Apr. 2013. USENIX Association.
  * [21] L. Ao, L. Izhikevich, G. M. Voelker, and G. Porter.  Sprocket: A serverless video processing framework.  In Proceedings of the ACM Symposium on Cloud Computing, SoCC ’18, page 263–274, New York, NY, USA, 2018. Association for Computing Machinery.
  * [22] Artificial Intelligence Security Surveillance Cameras.  https://www.theverge.com/2018/1/23/16907238/artificial-intelligence-surveillance-cameras-security, 2018\.
  * [23] L. Bindschaedler, J. Malicevic, N. Schiper, A. Goel, and W. Zwaenepoel.  Rock you like a hurricane: Taming skew in large scale analytics.  In Proceedings of the Thirteenth EuroSys Conference, EuroSys ’18, New York, NY, USA, 2018. Association for Computing Machinery.
  * [24] G. Bradski.  The OpenCV Library.  Dr. Dobb’s Journal of Software Tools, 2000.
  * [25] J. Choquette and W. Gandhi.  Nvidia’s a100 gpu: Performance and innovation for gpu computing.  In 2020 IEEE Hot Chips 32 Symposium (HCS), Virtual, August 16-18, 2020. IEEE, 2020.
  * [26] D. Crankshaw, G.-E. Sela, X. Mo, C. Zumar, I. Stoica, J. Gonzalez, and A. Tumanov.  Inferline: Latency-aware provisioning and scaling for prediction serving pipelines.  In Proceedings of the 11th ACM Symposium on Cloud Computing, SoCC ’20, page 477–491, New York, NY, USA, 2020. Association for Computing Machinery.
  * [27] D. Crankshaw, X. Wang, G. Zhou, M. J. Franklin, J. E. Gonzalez, and I. Stoica.  Clipper: A low-latency online prediction serving system.  In 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17), pages 613–627, Boston, MA, Mar. 2017. USENIX Association.
  * [28] J. Dean and S. Ghemawat.  Mapreduce: Simplified data processing on large clusters.  In Proceedings of the 6th Conference on Symposium on Operating Systems Design & Implementation - Volume 6, OSDI’04, page 10, USA, 2004. USENIX Association.
  * [29] T. Elgamal.  Costless: Optimizing cost of serverless computing through function fusion and placement.  In 2018 IEEE/ACM Symposium on Edge Computing (SEC), pages 300–312, Oct 2018.
  * [30] A. D. Ferguson, P. Bodik, S. Kandula, E. Boutin, and R. Fonseca.  Jockey: Guaranteed job latency in data parallel clusters.  In Proceedings of the 7th ACM European Conference on Computer Systems, EuroSys ’12, page 99–112, New York, NY, USA, 2012. Association for Computing Machinery.
  * [31] FFmpeg.  https://ffmpeg.org/, 2021.
  * [32] S. Fouladi, F. Romero, D. Iter, Q. Li, S. Chatterjee, C. Kozyrakis, M. Zaharia, and K. Winstein.  From laptop to lambda: Outsourcing everyday jobs to thousands of transient functional containers.  In Proceedings of the 2019 USENIX Conference on Usenix Annual Technical Conference, USENIX ATC ’19, page 475–488, USA, 2019. USENIX Association.
  * [33] S. Fouladi, R. S. Wahby, B. Shacklett, K. V. Balasubramaniam, W. Zeng, R. Bhalerao, A. Sivaraman, G. Porter, and K. Winstein.  Encoding, fast and slow: Low-latency video processing using thousands of tiny threads.  In Proceedings of the 14th USENIX Conference on Networked Systems Design and Implementation, NSDI’17, page 363–376, USA, 2017. USENIX Association.
  * [34] I. Ganusov and M. Iyer.  Agilex generation of intel fpgas.  In 2020 IEEE Hot Chips 32 Symposium (HCS), Virtual, August 16-18, 2020. IEEE, 2020.
  * [35] J. Gibson, D. Atkins, T. Creed, Z. Imel, P. Georgiou, and S. Narayanan.  Multi-label multi-task deep learning for behavioral coding.  IEEE Transactions on Affective Computing, pages 1–1, 2019.
  * [36] I. Gog, M. Schwarzkopf, N. Crooks, M. P. Grosvenor, A. Clement, and S. Hand.  Musketeer: All for one, one for all in data processing systems.  In Proceedings of the Tenth European Conference on Computer Systems, EuroSys ’15, New York, NY, USA, 2015. Association for Computing Machinery.
  * [37] J. R. Gunasekaran, P. Thinakaran, N. C. Nachiappan, M. T. Kandemir, and C. R. Das.  Fifer: Tackling resource underutilization in the serverless era.  In Proceedings of the 21st International Middleware Conference, Middleware ’20, page 280–295, New York, NY, USA, 2020. Association for Computing Machinery.
  * [38] H. Herodotou and S. Babu.  Profiling, what-if analysis, and cost-based optimization of mapreduce programs.  Proc. VLDB Endow., 4(11):1111–1122, Aug. 2011.
  * [39] K. Hsieh, G. Ananthanarayanan, P. Bodik, S. Venkataraman, P. Bahl, M. Philipose, P. B. Gibbons, and O. Mutlu.  Focus: Querying large video datasets with low latency and low cost.  In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18), pages 269–286, Carlsbad, CA, Oct. 2018. USENIX Association.
  * [40] M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly.  Dryad: Distributed data-parallel programs from sequential building blocks.  In Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, EuroSys ’07, page 59–72, New York, NY, USA, 2007\. Association for Computing Machinery.
  * [41] F. Jiang, Y. Jiang, H. Zhi, Y. Dong, H. Li, S. Ma, Y. Wang, Q. Dong, H. Shen, and Y. Wang.  Artificial intelligence in healthcare: past, present and future.  Stroke and Vascular Neurology, 2(4):230–243, 2017.
  * [42] J. Jiang, G. Ananthanarayanan, P. Bodik, S. Sen, and I. Stoica.  Chameleon: Scalable adaptation of video analytics.  In Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication, SIGCOMM ’18, page 253–266, New York, NY, USA, 2018. Association for Computing Machinery.
  * [43] E. Jonas, Q. Pu, S. Venkataraman, I. Stoica, and B. Recht.  Occupy the cloud: Distributed computing for the 99%.  In Proceedings of the 2017 Symposium on Cloud Computing, SoCC ’17, page 445–451, New York, NY, USA, 2017. Association for Computing Machinery.
  * [44] N. P. Jouppi, C. Young, N. Patil, D. Patterson, G. Agrawal, R. Bajwa, S. Bates, S. Bhatia, N. Boden, A. Borchers, R. Boyle, P. Cantin, C. Chao, C. Clark, J. Coriell, M. Daley, M. Dau, J. Dean, B. Gelb, T. V. Ghaemmaghami, R. Gottipati, W. Gulland, R. Hagmann, C. R. Ho, D. Hogberg, J. Hu, R. Hundt, D. Hurt, J. Ibarz, A. Jaffey, A. Jaworski, A. Kaplan, H. Khaitan, D. Killebrew, A. Koch, N. Kumar, S. Lacy, J. Laudon, J. Law, D. Le, C. Leary, Z. Liu, K. Lucke, A. Lundin, G. MacKean, A. Maggiore, M. Mahony, K. Miller, R. Nagarajan, R. Narayanaswami, R. Ni, K. Nix, T. Norrie, M. Omernick, N. Penukonda, A. Phelps, J. Ross, M. Ross, A. Salek, E. Samadiani, C. Severn, G. Sizikov, M. Snelham, J. Souter, D. Steinberg, A. Swing, M. Tan, G. Thorson, B. Tian, H. Toma, E. Tuttle, V. Vasudevan, R. Walter, W. Wang, E. Wilcox, and D. H. Yoon.  In-datacenter performance analysis of a tensor processing unit.  In 2017 ACM/IEEE 44th Annual International Symposium on Computer Architecture (ISCA), pages 1–12, June 2017.
  * [45] R. S. Kannan, L. Subramanian, A. Raju, J. Ahn, J. Mars, and L. Tang.  Grandslam: Guaranteeing slas for jobs in microservices execution frameworks.  In Proceedings of the Fourteenth EuroSys Conference 2019, EuroSys ’19, New York, NY, USA, 2019. Association for Computing Machinery.
  * [46] S. Kim, T. Lee, S.-w. Hwang, and S. Elnikety.  List intersection for web search: Algorithms, cost models, and optimizations.  Proc. VLDB Endow., 12(1):1–13, Sept. 2018.
  * [47] D. E. King.  Dlib-ml: A machine learning toolkit.  Journal of Machine Learning Research, 10:1755–1758, 2009.
  * [48] A. Klimovic, H. Litz, and C. Kozyrakis.  Selecta: Heterogeneous cloud storage configuration for data analytics.  In 2018 USENIX Annual Technical Conference (USENIX ATC 18), pages 759–773, Boston, MA, July 2018. USENIX Association.
  * [49] F. Lai, J. You, X. Zhu, H. V. Madhyastha, and M. Chowdhury.  Sol: Fast distributed computation over slow networks.  In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20), pages 273–288, Santa Clara, CA, Feb. 2020. USENIX Association.
  * [50] K. Mahajan, M. Chowdhury, A. Akella, and S. Chawla.  Dynamic query re-planning using qoop.  In Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation, OSDI’18, page 253–267, USA, 2018. USENIX Association.
  * [51] A. Mahgoub, A. M. Medoff, R. Kumar, S. Mitra, A. Klimovic, S. Chaterji, and S. Bagchi.  OPTIMUSCLOUD: Heterogeneous configuration optimization for distributed databases in the cloud.  In 2020 USENIX Annual Technical Conference (USENIX ATC 20), pages 189–203. USENIX Association, July 2020.
  * [52] G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski.  Pregel: A system for large-scale graph processing.  In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, SIGMOD ’10, page 135–146, New York, NY, USA, 2010. Association for Computing Machinery.
  * [53] D. G. Murray, M. Schwarzkopf, C. Smowton, S. Smith, A. Madhavapeddy, and S. Hand.  Ciel: A universal execution engine for distributed data-flow computing.  In Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation, NSDI’11, page 113–126, USA, 2011. USENIX Association.
  * [54] K. Ousterhout, P. Wendell, M. Zaharia, and I. Stoica.  Sparrow: Distributed, low latency scheduling.  In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP ’13, page 69–84, New York, NY, USA, 2013. Association for Computing Machinery.
  * [55] A. Poms, W. Crichton, P. Hanrahan, and K. Fatahalian.  Scanner: Efficient video analysis at scale.  ACM Trans. Graph., 37(4), July 2018.
  * [56] C. J. Rossbach, Y. Yu, J. Currey, J.-P. Martin, and D. Fetterly.  Dandelion: A compiler and runtime for heterogeneous systems.  In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP ’13, page 49–68, New York, NY, USA, 2013. Association for Computing Machinery.
  * [57] H. Shen, L. Chen, Y. Jin, L. Zhao, B. Kong, M. Philipose, A. Krishnamurthy, and R. Sundaram.  Nexus: A gpu cluster engine for accelerating dnn-based video analysis.  In Proceedings of the 27th ACM Symposium on Operating Systems Principles, SOSP ’19, page 322–337, New York, NY, USA, 2019. Association for Computing Machinery.
  * [58] J. Sun and G. Li.  An end-to-end learning-based cost estimator.  Proc. VLDB Endow., 13(3):307–319, Nov. 2019.
  * [59] J. Tan, T. Zhang, F. Li, J. Chen, Q. Zheng, P. Zhang, H. Qiao, Y. Shi, W. Cao, and R. Zhang.  Ibtune: Individualized buffer tuning for large-scale cloud databases.  Proc. VLDB Endow., 12(10):1221–1234, June 2019.
  * [60] A. Tumanov, T. Zhu, J. Park, M. Kozuch, M. Harchol-Balter, and G. Ganger.  Tetrisched: Global rescheduling with adaptive plan-ahead in dynamic heterogeneous clusters.  In Proceedings of the 11th European Conference on Computer Systems, EuroSys 2016, Proceedings of the 11th European Conference on Computer Systems, EuroSys 2016. Association for Computing Machinery, Inc, Apr. 2016.  11th European Conference on Computer Systems, EuroSys 2016 ; Conference date: 18-04-2016 Through 21-04-2016.
  * [61] S. Venkataraman, A. Panda, G. Ananthanarayanan, M. J. Franklin, and I. Stoica.  The power of choice in data-aware cluster scheduling.  In Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation, OSDI’14, page 301–316, USA, 2014. USENIX Association.
  * [62] S. Venkataraman, Z. Yang, M. Franklin, B. Recht, and I. 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, Santa Clara, CA, Mar. 2016. USENIX Association.
  * [63] S. D. Viglas and J. F. Naughton.  Rate-based query optimization for streaming information sources.  In Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, SIGMOD ’02, page 37–48, New York, NY, USA, 2002. Association for Computing Machinery.
  * [64] M. Voogel, Y. Frans, and M. Ouellette.  Xilinx versal premium series.  In 2020 IEEE Hot Chips 32 Symposium (HCS), Virtual, August 16-18, 2020. IEEE, 2020.
  * [65] L. Wang, M. Li, Y. Zhang, T. Ristenpart, and M. Swift.  Peeking behind the curtains of serverless platforms.  In 2018 USENIX Annual Technical Conference (USENIX ATC 18), pages 133–146, Boston, MA, July 2018. USENIX Association.
  * [66] Z. Wang, K. Zeng, B. Huang, W. Chen, X. Cui, B. Wang, J. Liu, L. Fan, D. Qu, Z. Hou, T. Guan, C. Li, and J. Zhou.  Tempura: A general cost-based optimizer framework for incremental data processing.  Proc. VLDB Endow., 14(1):14–27, Sept. 2020.
  * [67] R. Xu, J. Koo, R. Kumar, P. Bai, S. Mitra, S. Misailovic, and S. Bagchi.  Videochef: Efficient approximation for streaming video processing pipelines.  In 2018 USENIX Annual Technical Conference (USENIX ATC 18), pages 43–56, Boston, MA, July 2018. USENIX Association.
  * [68] N. J. Yadwadkar, G. Ananthanarayanan, and R. Katz.  Wrangler: Predictable and faster jobs using fewer resources.  In Proceedings of the ACM Symposium on Cloud Computing, SOCC ’14, page 1–14, New York, NY, USA, 2014. Association for Computing Machinery.
  * [69] N. J. Yadwadkar, B. Hariharan, J. E. Gonzalez, B. Smith, and R. H. Katz.  Selecting the best vm across multiple public clouds: A data-driven performance modeling approach.  In Proceedings of the 2017 Symposium on Cloud Computing, SoCC ’17, pages 452–465. ACM, 2017.
  * [70] M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker, and I. Stoica.  Spark: Cluster computing with working sets.  In Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing, HotCloud’10, page 10, USA, 2010. USENIX Association.
  * [71] H. Zhang, G. Ananthanarayanan, P. Bodik, M. Philipose, P. Bahl, and M. J. Freedman.  Live video analytics at scale with approximation and delay-tolerance.  In 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17), pages 377–392, Boston, MA, Mar. 2017. USENIX Association.