# CarbonScaler: Leveraging Cloud Workload Elasticity for Optimizing Carbon-
Efficiency

Walid A. Hanafy Qianlin Liang Noman Bashir David Irwin Prashant Shenoy
University of Massachusetts Amherst

###### Abstract.

Cloud platforms are increasingly emphasizing sustainable operations in order
to reduce their operational carbon footprint. One approach for reducing
emissions is to exploit the temporal flexibility inherent in many cloud
workloads by executing them in time periods with the greenest electricity
supply and suspending them at other times. Since such suspend-resume
approaches can incur long delays in job completion times, we present a new
approach that exploits the workload elasticity of batch workloads in the cloud
to optimize their carbon emissions. Our approach is based on the notion of
carbon scaling, similar to cloud autoscaling, where a job’s server allocations
are varied dynamically based on fluctuations in the carbon cost of the grid’s
electricity supply. We present an optimal greedy algorithm for minimizing a
job’s emissions through carbon scaling and implement a prototype of our
CarbonScaler system in Kubernetes using its autoscaling capabilities, along
with an analytic tool to guide the carbon-efficient deployment of batch
applications in the cloud. We evaluate CarbonScaler using real-world machine
learning training and MPI jobs on a commercial cloud platform and show that
CarbonScaler can yield up to 50% carbon savings over a carbon agnostic
execution and up to 35% over the state-of-the-art suspend resume policies.

##  1\. Introduction

Data centers worldwide consume over 200 TWh of electricity each
year—comprising around 1% of the total electricity usage (Masanet et al.,
2020)—and are poised to grow to 3-13% of the global electricity demand by 2030
(Andrae and Edler, 2015; Jones, 2018). The growth of hyper-scalar cloud
providers is fueling this rapid increase in energy use, resulting in a
significant environmental impact by increasing carbon and greenhouse gas (GHG)
emissions (Harvey, 2021; Masson-Delmotte et al., 2021). For the past two
decades, cloud providers have relentlessly focused on improving the energy
efficiency of their data centers in order to reduce operational costs—by
driving down data center power usage effectiveness (PUE) close to the optimal
value of 1. As a result, optimizations such as server consolidation, open air
cooling, and power infrastructure improvements have yielded significant energy
efficiency gains. However, energy efficiency improvements alone are not enough
to satisfy cloud data centers’ aggressive sustainability goals, since even
energy-efficient data centers generate significant carbon emissions from their
energy use. This has led to a new emphasis on carbon-efficient operations to
reduce a data centers’ overall carbon emissions (Chien, 2021).

Carbon efficiency can be achieved through supply-side or demand-side methods.
Supply-side methods include power purchase agreements from renewable
generation sources, such as solar, wind, and hydro, to _indirectly_ offset a
cloud data center’s carbon emissions. Such optimizations yield net-zero
operation (Google, 2022; META, 2022; Microsoft, 2022c) over a period, such as
a year, but offsets by themselves do not eliminate the instantaneous direct
emissions at all times (Bashir et al., 2022). Consequently, supply-side
optimizations need to be combined with demand-side methods to further reduce a
cloud data center’s carbon emissions. Demand-side optimizations exploit the
fact that carbon intensity of grid-supplied electricity varies both temporally
and geographically. A common demand-side optimization is _time shifting_
delay-tolerant workloads to time periods with the “greenest” electricity
supply. Although not all cloud workloads are delay tolerant, many types of
batch workloads exhibit significant temporal, performance, and even geographic
flexibility.

One approach for leveraging the temporal flexibility above is to use _suspend-
resume_ mechanisms (Wiesner et al., 2021; Acun et al., 2023; Dodge et al.,
2022; Radovanovic et al., 2022), where jobs are suspended when the carbon
intensity of the electricity is high and execution is resumed when it is low.
For example, Google recently adopted time-shifting in its Carbon-Intelligent
Computing System (Radovanovic et al., 2022). While suspend-resume-driven
temporal shifting policies can reduce the carbon emissions of delay-tolerant
workloads (Wiesner et al., 2021), they suffer from two drawbacks. First, the
carbon intensity of grid-supplied electricity changes slowly and there may be
long intervals (e.g., many hours) of high carbon periods where jobs remain
suspended and make no progress. Such suspensions delay completion times, with
7-10$\times$ increase in completion times in some cases (Souza et al., 2023).
Second, when batch jobs have limited temporal flexibility and cannot be
significantly shifted, the effectiveness of these methods is significantly
reduced.

To overcome these drawbacks, our paper presents _CarbonScaler_ , a new
approach that exploits the _resource elasticity_ of cloud workloads to
dynamically vary the amount of resources allocated to applications in response
to fluctuations in the carbon cost111The terms carbon intensity and carbon
cost of electricity are used interchangeably. of their energy supply. Our
“carbon scaling” approach is analogous to cloud autoscaling, where the number
of servers allocated to a cloud application is varied dynamically over time
(AWS, 2022). However, while cloud autoscalers generally respond to variations
in applications’ workload demand, often for request-based services, our carbon
scaler responds to the carbon dynamics of electricity. In essence, our “carbon
scaler” scales up the servers allocated to an application when the carbon cost
is low and gracefully scales them down when the cost increases. In contrast to
the static allocation of suspend-resume approaches, carbon scaling enables
faster progress during low carbon periods, which can potentially eliminate
delays in job completion times while also reducing carbon emissions.

Designing a cloud carbon scaler requires addressing two key design challenges:
_how much_ to scale each application up or down and _when_. Since different
applications exhibit different scaling characteristics with respect to the
number of allocated servers, a carbon scaler must take this scaling behavior
into account when determining how much to scale up each application during low
carbon periods. For example, an embarrassingly parallel job can be
opportunistically scaled up significantly without increasing its overhead (and
thus decreasing its energy-efficiency), while applications that experience
scaling bottlenecks should be scaled up more judiciously. A carbon scaler also
requires knowledge of the future carbon intensity of the energy supply to
determine when to perform such scaling operations. However, carbon forecasts
are fraught with forecasting errors, similar to weather forecasts, requiring
carbon scaling decisions to be robust to such errors.

In designing, implementing, and evaluating CarbonScaler, we make the following
contributions.

  * •

We introduce the notion of carbon scaling of cloud applications and present an
optimal greedy auto-scaling algorithm that minimizes an application’s
emissions by scaling it up and down in response to carbon cost variations.
Further, CarbonScaler can also substantially reduce or even eliminate the
completion time delays seen in suspend-resume approaches.

  * •

We implement a full prototype of CarbonScaler in Kubernetes and use it to
leverage a cloud application’s elasticity and temporal flexibility to reduce
its carbon footprint. We also implement our algorithm into CarbonScaler’s
CarbonAdvisor tool, which enables analysis and simulated execution of cloud
applications to evaluate their carbon savings before being deployed in the
cloud. CarbonAdvisor enables system designers to better understand how to
minimize their carbon cost based on their job characteristics, geographic
region, and different run-time parameters.

  * •

We evaluate CarbonScaler against several baselines using a wide range of real-
world clustered batch applications, including machine learning training and
MPI-based scientific jobs. Our results show that CarbonScaler can yield up to
50% carbon savings over a carbon agnostic execution and up to 35% over the
state-of-the-art suspend resume policy.

##  2\. Background

This section provides background on sustainable data centers and carbon-aware
scheduling.

###  2.1. Sustainable Data Centers

In addition to their long-standing emphasis on improving energy efficiency
through PUE222Power Usage Effectiveness (PUE) is the ratio of the total amount
of energy used by a data center to the energy delivered to computing.
reductions, cloud data centers have recently begun to focus on reducing their
carbon footprint (Acun et al., 2023; Radovanovic et al., 2022). This can be
achieved by reducing operational greenhouse gas (GHG) emissions measured in
gCO2eq/kWh, also known as Scope 2 emissions (Institute, 2022), resulting from
electricity use, as well as by reducing embodied carbon—Scope 3 emissions—that
arise during the manufacturing of data center hardware (e.g., servers). Our
work focuses on reducing Scope 2 emissions. Cloud platforms have little direct
(Scope 1) emissions, and optimizing embodied carbon of computing workloads is
beyond the scope of this paper.

###  2.2. Carbon Intensity of Electricity

Figure 1. _Grid’s carbon intensity shown over a 10 days period varies
spatially and temporally._

To reduce their Scope 2 emissions, cloud data centers need to track the carbon
cost of the electricity supply and modulate their electricity consumption over
time to reduce emissions. The carbon cost of electricity depends directly on
the source of generation. For example, a unit of energy generated by a coal
plant will have a high carbon cost (i.e., emissions in terms of gCO2eq/kWh),
while that generated from a hydroelectric plant will have no emissions. The
electricity supplied by the grid is produced by a mix of generation sources
and the resulting carbon cost is a weighted average of the corresponding
sources. Importantly, the mix varies from one region to another—based on the
local power plants in each region—and also varies over time since the
generation mix changes based on demand, relative cost of generation, and
intermittent generation from renewable sources.

Figure 1 depicts how the carbon cost differs by country/region and also how it
exhibits diurnal variations over the course of each day. In this case, Ontario
tends to have a low but variable carbon cost because its energy mix consists
of a large fraction of carbon-free nuclear and hydroelectric energy combined
with some coal plants, which results in non-zero carbon intensity, and solar,
which causes the diurnal fluctuations. California is similar, but has a higher
fraction of solar, which results in larger fluctuations, but also a higher
fraction of coal plants, which elevates the average carbon intensity. By
contrast, the carbon intensity of electricity in Iceland is nearly zero and
flat due to its unique abundance of carbon-free geothermal energy.

###  2.3. Carbon-aware Cloud Scheduling

Many cloud workloads, due to their temporal flexibility and resource
elasticity, are capable of exploiting the temporal and spatial variations in
energy’s carbon intensity. To facilitate such efforts, commercial services,
such as electricityMap (Maps, 2022) and WattTime (WattTime, 2022), have
emerged that aggregate data from grids in different parts of the world and
expose carbon intensity data and forecasts to cloud providers and users.
Researchers, in turn, are exploiting this data to design carbon-aware
schedulers that dynamically shift workloads across time and space to reduce
emissions.

As noted earlier, temporal shifting involves moving delay-tolerant batch
workloads to periods of low carbon intensity. In Figure 1, for instance,
rather than running a batch job continuously in a _carbon-agnostic_ manner,
_suspend-resume_ approaches can execute the job in the “valleys”, where the
carbon cost is low, and suspend the job during peak periods. This technique
has been explored in recent efforts (Radovanovic et al., 2022; Wiesner et al.,
2021; Dodge et al., 2022). Threshold-based suspend-resume approaches suspend
jobs whenever the carbon cost rises above a certain threshold, while deadline-
based methods choose the $n$ lowest carbon cost periods between the arrival
time and the deadline to execute the job. A drawback of _suspend-resume_
methods, whether threshold-based or deadline-based, is that the savings depend
on the amount of time the user is willing to wait for their job to
complete—higher delay tolerance yields higher savings but also longer
completion times.

Geographic or spatial shifting, in contrast, migrates jobs or workloads to
regions with the greenest electricity grid (Moghaddam et al., 2014; Zheng et
al., 2020; Zhou et al., 2013; Dodge et al., 2022). However, batch computation
may be unable to exploit geographic shifting due to data privacy (e.g., GDPR)
regulations that impose region restrictions. Even when possible, spatial
shifting methods can incur high migration costs if substantial state or data
needs to be moved with the job.

Figure 2. _Scaling characteristics of common MPI jobs and machine learning
training frameworks._

###  2.4. Cloud Autoscaling

Cloud workloads fall into two broad classes: interactive and batch. Due to
their latency-sensitive nature, interactive workloads are not amenable to
temporal shifting optimizations. Hence, our work primarily focuses on batch
workloads, specifically clustered batch workloads that run on a cluster of
cloud services. Many popular cloud workloads, such as MPI-style parallel batch
jobs and machine learning training frameworks (e.g., PyTorch) fall into this
category.

Our work is applicable to any batch job that is amenable to cloud autoscaling,
where the job is able to handle dynamic changes to the number of servers
allocated to it. Typically, cloud autoscalers provide horizontal scaling to
meet a job’s service level objectives (SLOs) (AWS, 2022), while our carbon
scaler exploits this resource flexibility to optimize the job’s carbon
emissions. Cloud autoscalers are used for interactive web services to handle
sudden workload spikes, rather than for batch jobs. However, clustered batch
computations such as scientific MPI applications and the Horovod elastic
framework for PyTorch (Sergeev and Balso, 2018) have recently gained
horizontal scaling capabilities, making them amenable to carbon scaling.

###  2.5. Batch Workload Resource Elasticity

Many modern clustered batch applications have elastic scaling capabilities,
but their scaling behavior can significantly vary. Figure 2 depicts the
scaling behavior of four deep learning training jobs, all of which use Horovod
and PyTorch for elastic scaling, and two MPI tasks that perform scientific
computations. As can be seen, ResNet18 training and the larger $N$-body MPI
computation show a linear increase in throughput as the number of servers
increase, indicating a linear scaling behavior. In contrast, VGG18 training
task exhibit a sub-linear increase in throughput due to scaling bottlenecks.
Finally, ResNet50 training and the smaller $N$-body MPI computation exhibit a
diminishing growth in throughput with increased server allocation. These
differences in scaling behavior should be considered by a carbon scaling
approach when optimizing for carbon savings.

##  3\. CarbonScaler Design

This section formulates the carbon scaling problem and then presents our
system design.

###  3.1. Problem Formulation

Similar to cloud autoscalers that scale each application independently, a
carbon scaler operates independently on each cloud application that wishes to
optimize its carbon emissions. When a new batch application arrives at time
$t$, it specifies (i) the minimum number of servers, $m$, that it needs to
run, where $m\geq 1$, and (ii) the maximum number of servers $M$ that can be
allocated to it, $M\geq m$. The carbon scaler can vary the servers allocated
to the application between $m$ and $M$. Suppose that $l$ is the estimated job
length when executing on the baseline allocation of $m$ servers.333The job
length $l$ can be estimated using profiling and modeling (Peng et al., 2018;
Shi et al., 2018) or using prior execution history. For example (Weng et al.,
2022) reports that 65% of batch jobs see repeated execution of at least 5
times within a two month period. By default, we assume that the desired job
completion time $T=t+l$, which means that job should complete ”on-time” with
no delays. Although $T$ must be at least $t+l$ for all jobs, some delay
tolerant jobs have significant temporal flexibility and can optionally specify
a longer completion time $T$ such that $T>t+l$. The value $T-(t+l)$ represents
the slack available when executing the job. This slack represents the
willingness of users to wait in order to maximize carbon savings. The default
case of $T=t+l$ assumes on-time completion and zero slack.

The completion time $T$ specifies the _temporal flexibility_ (delay tolerance)
available to the job, while the maximum server allocation $M$ specifies the
_resource elasticity_ of the job. The parameters $T$ and $M$ can be specified
in different ways to obtain a range of carbon scaling behaviors. For example,
when $T=t+l$, the application has no temporal flexibility and cannot be
subjected to suspend-resume mechanisms. In this case, the job can only exploit
resource elasticity by scaling up to $M$ workers during low carbon periods and
must be completed on time with no delays. In contrast, when $M=m$, the job has
no resource flexibility and a carbon scaler is limited to performing only
suspend-resume optimizations with a static number of servers, $m$, while also
ensuring it completes the job by the specified completion time $T$. Of course,
when $T>t+l$ and $M>m$, a carbon scaler has the most flexibility and can
exploit both resource elasticity and temporal shifting via suspend-resume. Our
goal is to design a carbon scaler that minimizes a job’s carbon emissions
subject to the available resource elasticity and temporal flexibility.

|
---|---
(a) Linear scaling | (b) Diminishing scaling
Figure 3. _Example marginal capacity curves._

###  3.2. Basic Design

When a new batch job arrives, our system, which we refer to as CarbonScaler,
computes an _initial_ schedule for executing the job through completion. The
execution schedule specifies how many servers to allocate to the batch job
over time and when to dynamically change the allocation in response to
variations in carbon cost. This initial schedule is based on a forecast of
future carbon cost as well as expected progress of the job over time based on
its resource allocation. As the job executes, CarbonScaler adjusts its
schedule periodically if it encounters forecast errors or deviations in
expected job progress — to ensure completion by the specified completion time
$T$. Observed deviations can occur due to profiling errors, from network and
locality interference (Jalaparti et al., 2015), or resource procurement
denials and are discussed further in §5.7.

CarbonScaler assumes that forecasts of future carbon cost of electricity are
available — this is reasonable since commercial services (Maps, 2022;
WattTime, 2022) already provide such forecasts. Since the application
specifies its temporal flexibility (in terms of completion time $T$) and its
resource elasticity (in terms of the varying server allocation from $m$ to
$M$), CarbonScaler’s schedule responds to fluctuations in forecasted carbon
cost by scaling down or completely suspending the job when the cost is high
and opportunistically scaling up when the cost is low.

Different clustered batch applications will have different scaling behaviors,
as shown in Figure 2, which should be considered when scaling an application’s
server capacity between the specified range of $m$ to $M$. As noted in Figure
2, applications throughput either increases sub-linearly or increases somewhat
linearly initially and then shows diminishing returns with additional increase
in server capacity. This behavior is a direct consequence of Amdahl’s law
(Amdahl, 1967), which states that the speedup of a parallel application is
limited by the amount of sequential code within it — adding server capacity
only speeds up the parallel component of the application. Software bottlenecks
such as synchronization overheads also limit the ability to scale up.

CarbonScaler considers this scaling behavior in terms of a _marginal capacity
curve_ , shown in Figure 3, which captures the incremental increase in
application capacity (i.e., throughput) for each unit increase in server
capacity. The ideal case of linear scaling translates to a _flat_ marginal
capacity curve where each additional server results in a unit increase in
(normalized) application capacity (see Figure 3(a)). Most applications will
have a diminishing marginal capacity curve, where marginal capacity decreases
monotonically with increase in the server capacity (see Figure 3(b)).

Input: Marginal capacity ($MC$), time slots $[t,T]$, carbon cost forecast
($c$), total work ($W$)

Output: Execution Schedule $S$

1 $S\leftarrow[0..0]$;

2 $L\leftarrow[]$ ;

3 for  _$i\in[t,T]$_ do

4 for  _$j\in[m,M]$_ do

5 $L$.append($i,j,MC_{j}/c_{i}$);

6

$L\leftarrow$ Sort($L$) ; // w.r.t. Norm. Marginal Cap.

7 $w\leftarrow 0$ ;

8 while  _$w <W$ _ do

$i,j,*\leftarrow L.pop()$; // next highest $MC_{j}/c_{i}$

$S[i]=j$; // increase allocation in slot $i$

9 $w.update(S)$ ;

10

return $S$

Algorithm 1 Carbon Scaling Algorithm()

The marginal capacity curve and the carbon intensity curve can then be used to
scale the application up or down in a carbon-efficient manner. To do so, the
marginal capacity curve is normalized by the forecasted carbon cost in each
time step to compute the marginal capacity per unit carbon — the marginal work
done per unit of carbon. CarbonScaler then adds server capacity to the time
slots that maximize the work done per unit of carbon. By doing so,
CarbonScaler allocates more server resources when the carbon cost is low,
since more marginal work can be done at a lower carbon cost. CarbonScaler will
incrementally add servers to various time slots until sufficient server
capacity has been added to complete the job within the desired completion time
$T$, thereby yielding a carbon-efficient execution schedule that optimizes the
carbon emissions.

In practice, each application can have multiple marginal capacity curves, each
representing a different phase of of its execution. For example, a MapReduce
job can have different scaling behaviors, and a different marginal capacity
curve, for its map and reduce phases. For ease of exposition, our discussion
below assumes a single marginal capacity curve per application. However, our
approach generalizes to multiple marginal capacity curves by considering the
appropriate scaling curve in each time slot that corresponds to current phase
of the application’s execution.

###  3.3. Carbon Scaling Algorithm

Our greedy carbon scaling algorithm to compute a batch job’s execution
schedule by horizontally scaling it up or down or suspending it entirely is
shown as Algorithm 1. As noted in Section 3.1, when a new job arrives at time
$t$, it specifies a _desired_ completion time (“deadline”) of time $T$. We
assume that the interval $[t,T]$ is discretized into smaller fixed-length
intervals (e.g., 15 minutes or an hour), and the number of servers allocated
to the job can be changed at the start of each interval. Suppose that there
are $n$ time intervals between $[t,T]$, $n\geq 1$. Let $c_{1},c_{2},...,c_{n}$
denote the forecasted carbon cost in each such interval $i,i\in[t,T]$.

We also assume that the marginal capacity curve of the application is obtained
by profiling the application offline (see Section 4.1) and is known at arrival
time. Suppose that the marginal capacity curve is denoted by
$MC_{m},MC_{m+1},...,MC_{M}$, where $MC_{j}$ is the marginal capacity increase
after allocating the $j$-th servers, $j\in[m,M]$. Since the estimated job
length is $l$ when executing with minimum server capacity $m$, the total
amount of work the job needs to perform is $W=l\cdot MC_{m}$. Our algorithm
needs to compute a schedule where the aggregate server capacity allocated to
the job over $[t,T]$ can perform this amount of work before the completion
time $T$, while also minimizing carbon emissions.

To do so, our algorithm first computes the marginal capacity per unit carbon
in each time interval $i$ by normalizing the $MC$ curve with carbon cost
$c_{i}$ in that interval (line 1).444If the application has multiple marginal
capacity curves, the one corresponding to the execution phase in time slot $i$
is chosen. That is, the marginal capacity per unit carbon in time interval $i$
is simply ${MC_{m}}/c_{i},MC_{m+1}/c_{i},...,MC_{M}/c_{i}$. The greedy
algorithm then iteratively and incrementally allocates server capacity to
various time slots in order of decreasing marginal capacity per unit carbon
(lines 1-1). In each iteration, it chooses the interval $i$ from [1, n] such
that allocating incremental server capacity to that time slot maximizes the
work done per unit carbon (i.e., chooses the interval with the greatest
$MC_{j}/c_{i}$ across all intervals). After allocating server capacity to that
interval, it iteratively determines the next interval where allocating
additional server capacity yields the next highest work done per unit carbon,
and so on.

Note that the greedy algorithm may allocate additional capacity to the same
interval as the previous iteration if its marginal work done per unit carbon
continues to be the highest across all intervals. Otherwise, a new time
interval with the next highest marginal work done per unit is chosen for
allocating server capacity. Also, when a time interval is initially chosen by
the greedy algorithm for capacity allocation, it must be allocated the minimum
requirement of $m$ servers, after which the allocation can be increased
incrementally by one in subsequent steps. Similarly, if a time slot reaches
the maximum allocation of $M$ servers, it is not considered further by the
greedy algorithm. The process continues until sufficient capacity has been
allocated across the $n$ time intervals to complete $W$ units of work. This
yields an initial schedule where each time interval has either a zero
allocation (causing the job to be suspended in that period) or has a non-zero
allocation between $m$ and $M$, with the server allocation potentially
changing at interval boundaries.

|  |  |
---|---|---|---
(a) Carbon-agnostic | (b) Linear scaling | (c) Diminishing scaling | (d) MC per unit carbon
Figure 4. _An illustrative example of our carbon scaling algorithm at work._

Example. To illustrate our carbon scaling algorithm, consider a job of length
2 that arrives at $t=0$ and needs to finish by $T=3$. Suppose that the job
needs to execute on at least one server ($m=1$) and at most two servers
($M=2$). Carbon-agnostic execution will run the job as soon as it arrives and
it will complete at time 2, as shown in Figure 4(a). Suppose that the
forecasted carbon cost in time slots 1, 2 and 3 is $c_{1}=10$ (”low”),
$c_{2}=100$ (”high”) and $c_{3}=20$ (”medium”), respectively. First, assume
that job has ideal scaling behavior and a flat marginal capacity curve of
$MC_{1}=1$ and $MC_{2}=1$. The algorithm simply allocates two servers to the
job in slot 1, since it has the lowest carbon cost and the highest marginal
capacity per unit carbon. As shown in Figure 4(b), such a job runs with two
servers and terminates at the end of slot 1.

Next assume a job with a diminishing marginal capacity curve, given by
$MC_{1}=1$ and $MC_{2}=0.7$. Figure 4(d) show the marginal capacity per unit
cost table ($MC_{j}/c_{i}$) for all three slots. The greedy algorithm
allocates the first server to slot 1, since it has the highest marginal
capacity per unit cost of 0.1. In the next iteration, the greedy algorithm
allocates a second server to slot 1 as it still has the highest marginal
capacity per unit cost ($MC_{2}/c_{1}=0.07$). Although two servers have been
allocated, the total work done by these two servers is only 1.7
($MC_{1}+MC_{2}$), which cannot complete the job of length 2 ($W=2$). The
algorithm then allocates another server to slot 3, which has the next highest
marginal capacity per unit cost ($MC_{1}/c_{3}=0.05$). This yields a schedule
where the job is given 2 servers in slot 1, zero in slot 2 and one server in
slot 3. The job only runs for one-third of slot 3 before it completes. The
example also illustrates a tradeoff where CarbonScaler reduces the emissions
compared to carbon-agnostic execution (from 110 to 40 carbon units), but
increases cloud costs by 15% due to the need for a third server.

Periodic Schedule Recomputation. Once the algorithm computes an initial
schedule, CarbonScaler can begin execution of the job by auto-scaling it up or
down, or suspending it, in each time slot as per the schedule. CarbonScaler
continuously monitors the work done (“job progress”) and the emissions of the
job over the course of its execution. Recall that the initial schedule is
computed based on a _forecasted_ carbon cost and an _estimated_ marginal
capacity curve derived from profiling, both of which can have errors in their
estimates. Similar to weather forecasts, carbon forecasts can have errors,
especially over a period multiple days (Maji et al., 2022). Similarly, the
marginal capacity curves may not be exact since the production environments
may somewhat differ from the profiling environment (Jalaparti et al., 2015;
Peng et al., 2018; Shi et al., 2018). These errors can cause deviations in the
expected work done or the expected carbon emissions as estimated by the
initial schedule.

To be robust to carbon prediction or profile estimation errors, CarbonScaler
compares the expected work and carbon emissions to the estimates in the
schedule at the end of each time interval. If the deviations exceed a
threshold, it recomputes the schedule for the remainder of the job’s execution
from the current time $t^{\prime}$ to the completion time $T$. When doing so,
it can use an updated carbon forecast if available, since such forecasts are
often updated every few hours, similar to weather forecasts. Thus, if the
progress deviates from the plan (e.g., due to profiling errors), CarbonScaler
will recompute the schedule to ensure highest carbon savings. Since some batch
jobs can execute for days (Tirmazi et al., 2020), such schedule adjustments
provide robustness to prediction errors and ensure timely job completion while
minimizing carbon emissions.

Carbon Scaler Optimality. The greedy algorithm in Algorithm 1 yields optimal
carbon savings.

###### Theorem 1.

Consider a batch job with a monotonically decreasing marginal capacity curve,
s.t. $MC_{m}>MC_{m+1}>..>MC_{M}$. The job needs to finish work $W$, within $n$
time slots with carbon costs $c_{1},c_{2},...,c_{n}$, respectively. Greedily
selecting the slot $i$ and scaling the job to $j$ servers with highest
marginal capacity per unit carbon $MC_{j}/c_{i}$, in each step, results in the
lowest (optimal) amount of carbon consumption.

The carbon scaling problem can be represented as a fractional knapsack problem
that can be solved optimally using greedy algorithms (Cormen et al., 2009). We
list our detailed proof in appendix A.

Run Time Complexity. In Algorithm 1, the time complexity of computing the
marginal capacity per unit carbon (steps: 3-5) is $\mathcal{O}(n.M)$, list
sorting is $\mathcal{O}(nM\log nM)$, and computing the schedule is $O(nM)$
(steps: 8-11). The total complexity is $\mathcal{O}(nM+nM\log
nM)\approx\mathcal{O}(nM\log nM)$ .

##  4\. CarbonScaler Implementation

This section describes the implementation of CarbonScaler system to optimize
the carbon emissions of batch cloud workloads. Our system comprises of three
components: (1) Carbon Profiler, which uses offline profiling to estimate
marginal capacity ($MC$) curves and energy usage of jobs, (2) Carbon
AutoScaler is our cloud-based carbon scaling system implemented in Kubernetes
(Kubernetes, 2022), and (3) Carbon Advisor, which simulates the execution of
the jobs to estimate carbon reduction under different deployment
configurations. CarbonScaler is implemented in Go using 2,437 lines of codes,
and will be open-sourced.

###  4.1. Carbon Profiler

CarbonScaler requires the marginal capacity curve of a job for carbon-aware
scaling. Carbon Profiler performs a one time offline profiling of a new job to
derive its marginal capacity curve. To do so, it runs the job with server
allocations ranging from the job-specified minimum number of servers, $m$, to
the maximum number of servers, $M$, and records the work done at each
allocation. To minimize the overhead of profiling, Carbon Profiler runs the
job for a small, configurable amount of time $\alpha$ (typically few minutes)
and varies the resource allocation with a granularity $\beta$, which depends
on $M$. If $\beta>1$, Carbon Profiler interpolates the recorded measurements
to obtain a complete marginal capacity curve. Finally, the marginal capacity
curves are valid for a computing environment similar, or identical, to the
profiling environment. The scaling behaviour and the expected savings may
change if the environment is significantly different necessitating an
environment-specific profiling or an online update of the capacity curves.
CarbonScaler also allows substituting Carbon Profiler with alternative
workload profiling approaches from prior work (Qi et al., 2017; Oyama et al.,
2016; Pei et al., 2019; Justus et al., 2018; Cai et al., 2017; Peng et al.,
2018; Shi et al., 2018).

Figure 5. _An overview of Carbon AutoScaler._

###  4.2. Carbon AutoScaler

Figure 5 shows an overview of Carbon AutoScaler that uses Kubeflow (Kubeflow,
2022) to implement our Carbon Scaling Algorithm from §3.3. The incoming
elastic batch applications use Kubernetes’ Custom Resource Definition (CRD),
written in .yaml format, to provide their general job specifications alongside
scaling and scheduling information including minimum $m$ and maximum $M$
number of servers, completion time $T$, estimated job length $l$, and marginal
capacity curve. Carbon AutoScaler deploys CRDs using Kubernetes APIs such as
kubectl.

We implement Carbon AutoScaler as a controller that sits on top of the
Kubeflow training operator and leverages its core resource management
functionalities for clustered batch jobs such as ML training and MPI. It first
runs the Carbon Scaling Algorithm to compute the initial schedule for each
job. It executes the schedule by scaling the resources allocated to the job by
modifying the Kubeflow job specification, such as the number of replicas. It
delegates the task of maintaining job status to the Kubeflow operator. Carbon
AutoScaler also registers a reconcile callback function, which is called when
the carbon intensity changes. The function updates the job’s specifications
based on the initial schedule and applies the changes to the Kubeflow
operator.

Carbon AutoScaler implements resource-level and application-level monitoring.
Carbon AutoScaler implements additional kubernetes services to monitor
resource usage, its energy usage, and carbon usage over time. We track CPU
usage using Kubernetes Metrics Server (SIGs, 2022), CPU energy usage using
Running Average Power Limiting (RAPL) (David et al., 2010) interfaces and
powerAPI (Bourdon et al., 2013), and GPU energy usage using NVIDIA Data Center
GPU Manager (DCGM) (NVIDIA, 2022). Carbon AutoScaler monitors application-
level metrics such as progress and throughput via application-level
interfaces. To do so, Carbon AutoScaler tracks carbon intensity using a
dedicated service that provides the instantaneous as well as forecasted carbon
cost. Finally, Carbon AutoScaler reacts to divergence in progress, throughput,
or carbon intensity by recomputing the schedule as explained in §3.3

Figure 6. _Carbon Advisor user interface._

###  4.3. Carbon Advisor

Carbon Advisor enables pre-deployment analysis of the carbon scaling algorithm
in an environment that simulates the operation of Carbon AutoScaler. It takes,
as an input, carbon trace, job start time, deadline, job length, and
CarbonScaler-specific parameters such as range of server allocations $[m,M]$
and marginal capacity curve. It simulates the running of the job and reports
savings for various policies outlined in the paper. This simple plug-n-play
nature of the tool allows application developers to perform what-if scenarios
and explore a wide range of parameters before actual deployment. For example,
the user can explore the benefits of extending her waiting time and its impact
on carbon savings. We also enable key high-level analysis by default such as
computing the distribution of carbon savings across different start times of
the year. Finally, to facilitate initial exploration, we will provide carbon
traces and marginal capacity curves used in the paper alongside the tool.
Figure 6 shows the web interface of Carbon Advisor.

##  5\. Experimental Evaluation

This section evaluates the performance of CarbonScaler using our prototype
implementation, described in Section 4. We augment the prototype evaluation
results with additional large-scale analysis that leverages Carbon Advisor.

###  5.1. Experimental Setup

Workload. Table 1 describes the elastic workloads used for evaluating
CarbonScaler and their specifications. The workloads spans both CPU- and GPU-
intensive applications such as $N$-body problem (Aarseth, 1985) implemented
using MPI (Forum, 1994) and machine learning models including ResNet (He et
al., 2016), EfficientNet (Tan and Le, 2019), and VGG (Tan and Le, 2019)
implemented using Pytorch (Paszke et al., 2019). The table shows the base
configurations and power measurements for jobs that need 24hrs to finish. The
chosen workloads have a wide-range of scaling characteristics (shown in Figure
2), configurations, and energy requirements.

Infrastructure. We deployed CarbonScaler in two different settings to
demonstrate its adaptability to the underlying infrastructure. For CPU-
intensive workloads, we used a local computing cluster consisting of 7
servers, each equipped with a 16-core Xeon CPU E5-2620, connected through a
10G network. For GPU-intensive workloads, we deployed CarbonScaler on Amazon
Web Services (AWS) using 8 p2.xlarge instances each equipped with NVIDIA K80
GPU.

Name | Implementation | Epochs | BatchSize | Power (W)
---|---|---|---|---
$N$-Body Simulation (10,000) | MPI | 138000 | NA | CPU (60)
$N$-Body Simulation (100,000) | MPI | 1500 | NA | CPU (60)
Resnet18 (Tiny ImageNet) | Pytorch | 173 | 256 | CPU+GPU (210)
EfficientNetB1 (ImageNet) | Pytorch | 45 | 96 | CPU+GPU (210)
VGG16 (ImageNet) | Pytorch | 31 | 96 | CPU+GPU (210)

Table 1. _Key details of elastic workloads in evaluation. Epochs is the number
of epochs needed for a 24hr job._ Figure 7. _Most cloud regions globally have
high carbon cost but also show significant daily variations, providing an
opportunity for CarbonScaler to optimize carbon emissions._

Carbon Traces. We collected carbon traces for different geographical locations
using electricityMap (Maps, 2022), an online service that provides real-time
and archival carbon intensity information. We use average carbon intensity
values, measured in grams of carbon dioxide equivalent per kilowatt-hour
(gCO2eq/kWh), provided at hourly granularity. The collected carbon traces span
from January 2020 to September 2022, we specify the duration for each trace
where it is used.

To choose representative regions for our evaluation, we analyzed the average
carbon intensity and the coefficient of variation (computed as standard
deviation over mean) for different Amazon AWS cloud availability regions.
Figure 7 shows the results for 37 different regions. As shown, most regions
have high carbon intensity but also show high daily variations, while some
have low carbon intensity with similarly high daily variations. Since suspend-
resume and CarbonScaler rely on these high variations to reduce emissions, the
figure indicates that both techniques will be effective in the majority of
low-carbon as well as high-carbon cloud regions. A few cloud regions have
stable carbon costs (i.e., low variations), including low carbon regions such
as Iceland and Sweden, and high carbon regions such as India and Singapore.
The effectiveness of suspend-resume and CarbonScaler is diminished in such
cloud regions. Still, such regions are a small minority of the total cloud
regions in a global cloud platform such as AWS. Based on this analysis, we
choose Netherlands (  ) as a representative high carbon region and Ontario,
Canada (  ) as an example of a low carbon region for our subsequent
experiments.

Baselines Policies. We evaluate the performance of CarbonScaler against three
baseline policies: carbon-agnostic, suspend-resume, and static-scale. The
carbon-agnostic is a simple policy that runs a job without considering carbon
emissions and represents the status-quo. The suspend-resume policy is inspired
by prior work (Wiesner et al., 2021; Dodge et al., 2022). As mentioned in
§2.3, suspend-resume can be implemented in two ways: threshold-based, which
uses a carbon threshold to suspend-resume a job in a deadline-unaware manner,
and deadline-based, which chooses the $k$ lowest carbon periods before the
specified deadline for execution. In this case, suspend-resume defaults to
carbon-agnostic policy when completion time equals job length ($T=l$), i.e. no
slack, since execution cannot be deferred. This policy acts as a baseline for
temporal shifting scenarios where we assume a job has a completion time higher
than job length ($T>l$). Finally, static-scale is another policy inspired by
prior work (Souza et al., 2023), where an application picks the lowest carbon
intensity points and runs with a certain _static_ scale factor to better
utilize the carbon intensity variations. This is our default baseline for
scenarios where we evaluate CarbonScaler for its ability to leverage workload
elasticity and scaling. Unless stated otherwise, we report the mean across 7
runs for our cloud experiments and across 100 runs for Carbon Advisor’s
simulated executions.

Figure 8. _CarbonScaler in action for a 48hrs long $N$-body MPI job
($N$=100k), where $T=2\times l$._

###  5.2. CarbonScaler in Action

To show CarbonScaler in action, we ran a 48hr $N$-body MPI job on our CPU
cluster and compared its execution to the threshold-based suspend-resume
(deadline-unaware) and carbon-agnostic policies. As shown in Figure 8, the
carbon-agnostic policy starts the job as soon as it arrives and finishes in
48hrs at the cost of 184g of $CO_{2}$ emissions. The suspend-resume policy
_suspends_ the job during high carbon intensity periods and waits for the
carbon emissions to fall below a threshold (25th percentile in this case) to
_resume_ the job. By leveraging temporal flexibility, suspend-resume saved 45%
carbon compared to the carbon-agnostic policy, but increases the job
completion time by 4$\times$. Finally, we set the desired completion time $T$
to be 96hrs, i.e. $T=2\times l$, and execute our proposed CarbonScaler policy.
CarbonScaler scales the number of servers depending on the application’s
scaling properties and the carbon cost at a given time. As a result,
CarbonScaler achieves 42% carbon saving over carbon-agnostic policy.
CarbonScaler achieves comparable savings with suspend-resume while also
reducing the job completion time to 2$\times$ of carbon-agnostic policy.

Figure 9. _Carbon footprint (saving % on-top) of different workloads scheduled
under carbon-agnostic, static-scale (2 $\times$), and CarbonScaler, in
Ontario, Canada, where $T=l$ (i.e., no slack and on-time completion)._

###  5.3. Impact of Workload Elasticity

The two key aspects that impact carbon savings from CarbonScaler are the
temporal flexibility and workload elasticity. While prior work necessitates
temporal flexibility for carbon savings, CarbonScaler can achieve significant
savings by leveraging workload elasticity even when no temporal flexibility is
available. The extent of savings depend on the scalability properties of the
workload: a highly scalable job (with flat or close to flat marginal capacity)
can achieve higher savings, as illustrated for the simple workload in Figure
4. To demonstrate the effect of elasticity, we limit the job completion time
to the job length, i.e., $T=l$, which means no temporal flexibility is
available. We run 24hrs long jobs for various applications in Table 1 using
carbon-agnostic policy, static-scale (2$\times$), and CarbonScaler.

Figure 9 shows the performance of the three policies for different workloads.
The static-scale (2$\times$) achieves up to 28% savings over carbon-agnostic
for highly scalable workloads ($N$-body ($N$=100k) and ML (ResNet18)).
However, since it does not consider the scalability properties of the job, it
can instead _increase_ the carbon consumption for some workloads by as much as
26% by scaling the job beyond a single _optimal_ scale factor. On the other
hand, CarbonScaler is cognizant of scaling behavior and scales the job only in
slots that have the highest work done per unit carbon cost. CarbonScaler
yields up to 47% savings in the best case (for the N-body task with good
scaling behavior) and 2% savings in the worst case (for VGG training which has
poor scaling behavior).

|  |
---|---|---
(a) $N$-body ($N$=100k) | (b) ML (ResNet18) | (c) $N$-body ($N$=10k)
Figure 10. _Normalized carbon w.r.t. CarbonScaler (CS) for static-scale (SS)
policy with different scale factors. The carbon-agnostic policy (CA) is shown
as reference._

In Figure 9, we set the scale factor for the static-scale as 2$\times$ for
initial analysis. To further explore the effect of scale factor, we use our
Carbon Advisor to compare CarbonScaler to policies with static scale factors
of 2$\times$, 4$\times$, and 6$\times$ for three of our workloads that show
almost linear and non-linear scalability, as shown in Figure 10. No single
scale factor works well for all workloads and the extent of savings depends on
the scalability properties of the workload. For jobs with almost linear
scalability, $N$-body ($N$=100k) and ML (ResNet 18), a high static scale
factor can be chosen to obtain savings similar to CarbonScaler. For a job with
non-linear scalability, $N$-body ($N$=10k), it is important to pick different
scale factors for different slots depending on the carbon cost in that slot.
The scalability-aware nature of CarbonScaler means that it always picks an
appropriate scale factor for the job.

_Key Takeaway. CarbonScaler better leverages the workload elasticity by
choosing a dynamic scale factor depending on the marginal capacity curve of
the job normalized to carbon cost._

###  5.4. Impact of Temporal Flexibility

In last section, we focused on the savings achieved by only utilizing workload
elasticity. However, temporal flexibility is also an important source of
carbon savings for delay-tolerant jobs. Therefore, we evaluate the impact of
using temporal flexibility by running workloads from Table 1 using carbon-
agnostic policy, suspend-resume policy, and CarbonScaler with extended
completion times where $T>l$. To ensure that the suspend-resume respects the
job-specified completion time, we use the deadline-aware version of the
suspend-resume policy (Wiesner et al., 2021). Figure 11 shows the carbon
consumption when _running_ the workloads with 24 hrs length $l$, and 36 hrs as
completion time $T$, $T=1.5\times l$, across two locations. CarbonScaler is
better at exploiting the temporal flexibility and outperforms the suspend-
resume policy for most workloads. The extent of savings depend on the
scalability characteristics of the workload: highly scalable workloads yield
up to 29-46% savings. On the other hand, for less scalable workloads such as
ML(VGG16), CarbonScaler most savings are from time-shifting, hence comparable
saving to suspend-resume. It is also worth noting that CarbonScaler
consistently achieves higher savings in both regions despite a significant
difference in their average carbon cost. The extent of savings depends on the
variability in the carbon trace for a given region and we evaluate its effect
on carbon savings in Section 5.6.

---
(a) Ontario, Canada
(b) Netherlands
Figure 11. _Carbon footprint (saving % on-top) of different workloads
scheduled under carbon-agnostic, suspend-resume, and CarbonScaler policies,
where $T=1.5\times l$._ Figure 12. _Effect of completion time on the carbon
footprint of a 12hrs long ResNet18 job in Ontario, Canada._

Effect of Completion Time. Prior work have demonstrated that the temporal
flexibility can yield significant savings. Figure 12 evaluates the gain in
carbon savings with increasing temporal flexibility (higher desired completion
time $T$). We run a 12hrs ML training job (ResNet18) and configure it to
complete in 12hrs ($T=l$) up to 36hrs ($T=3\times l$). For higher completion
times, more low carbon slots become available, which allows CarbonScaler and
suspend-resume to reduce the carbon consumption by 30-45% and 0-32%,
respectively. Note that since suspend-resume cannot suspend at 1$\times$ scale
factor, it is equivalent to carbon-agnostic. CarbonScaler achieves higher
savings by using a higher scale factor during the lowest carbon slots and only
picks a higher carbon slot if it gives a better marginal work done per unit
carbon. For very high completion times, the savings of CarbonScaler over
suspend-resume diminish, since it begins to prefer job suspensions over high
scale factors to avoid the impact of non-linear scaling behaviour.

Effect of Job Length. The length of a job is another key factor in determining
the carbon savings. As the job length increases, more low carbon slots become
available as grid’s carbon intensity generally has a diurnal pattern. To
evaluate the impact of job length, we varied the job length from 6 hours to 96
hours and used our Carbon Advisor to analyze the estimated carbon savings.
Figure 13 shows the carbon savings of different policies, against a carbon-
agnostic baseline, for the $N$-body($N$=100k) MPI task when $T=1.5\times l$.
The figure shows that CarbonScaler outperforms suspend-resume and carbon-
agnostic over a range of job lengths. The carbon savings increase with job
length since there are more low-carbon time slots to choose from, providing
opportunities for greater savings. Overall, CarbonScaler achieves 30% more
savings than suspend-resume for long running batch jobs.

Figure 13. _Effect of job length on CO 2 savings for an $N$-Body ($N$=100k)
job in Ontario, Canada, where $T=1.5\times l$._ Figure 14. _Carbon consumption
(% saving on-top) of 24-hour $N$-body ($N$=100k) MPI job with different
cluster sizes in Ontario, Canada, where $T=1.5\times l$._

Effect of Cluster Size. Our experiments this far have used a lower bound of 1
server ($m=1$) and an upper bound of 8 servers ($M=8$) for workloads due to
cluster size and cloud cost constraints. However, larger batch jobs execute on
larger clusters, with larger $m$ and $M$. For example, certain HPC and ML
training applications run on tens or even hundreds of servers in the cloud
(Jacobs et al., 2017; Devlin et al., 2019).

To evaluate the efficacy of CarbonScaler for large-scale clusters, we
extrapolated the marginal capacity curve for the current $N$-body($N=100k)$
job. Then, we use Carbon Advisor to estimate how carbon savings change when
running progressively bigger jobs on increasing cluster sizes while keeping
the job length unchanged at 24hrs.

Figure 14 shows that CarbonScaler can outperform both baseline policies over a
range of cluster sizes and obtain 20 to 42% additional savings. However, the
savings over suspend-resume reduce as the cluster size increases, since the
marginal capacity curve shows diminishing gains for larger cluster sizes,
which in turn reduces the savings by CarbonScaler. Interestingly, suspend-
resume achieves the same savings of 17% over carbon-agnostic policy across all
cluster sizes. Since the job length of 24hrs stays the same while running on
bigger cluster sizes, suspend-resume suspends all jobs in the same high carbon
periods regardless of the cluster size and obtains the same savings in all
cases.

_Key Takeaway. CarbonScaler can exploit temporal flexibility to outperform
suspend-resume policy across regions with widely different average carbon
costs and over different job lengths, completion times, and cluster sizes._

###  5.5. Monetary Cost Overhead

As discussed in Section 3.3, CarbonScaler can potentially incur extra cloud
costs for the workloads with diminishing marginal capacity curves. Figure 15
shows the monetary cost overhead in two of the aforementioned scenarios,
namely the added cost when evaluating CarbonScaler across workloads (figure
9), and evaluating the effect of extended completion time (figure 12). We
quantify the cost overhead as the additional compute-hours needed when
compared to carbon-agnostic policy. As shown in figure 15(a), highly scalable
workloads, such as $N$-body($N=100$) and ML (ResNet18), cost only 5-10% higher
than a carbon-agnostic policy. However, while focusing only on carbon saving,
the less scalable workloads incur higher cost. Figure 15(b) also highlight an
important aspect in extending the completion time, since better slots are
mostly available, tasks are mostly scaled to a larger number of servers,
yielding higher cost. Nonetheless, in all cases, the cost did not surpass 18%.

_Key Takeaway. The monetary cost overhead of CarbonScaler is small, and both
carbon and monetary costs should restrain less scalable tasks. _

---
(a) Workloads overhead, $T=l$ (Fig. 9)
(b) ResNet18 overhead, $\mathord{T=[1-3]\times}l$ (Fig. 12)
Figure 15. _Monetary cost overhead of CarbonScaler over carbon-agnostic
execution for different scenarios._

###  5.6. Impact of Carbon Cost Dynamics

Since achievable carbon savings depend on the temporal characteristics of the
carbon costs within a cloud region, which significantly vary across regions,
we next evaluate the impact of regions and carbon intensity variability on
carbon savings.

Figure 16. _Carbon consumption and carbon savings (%), for an ML (ResNet18)
job, where $T=l$, across multiple geographical regions. The average carbon
cost increases from left to right._

Carbon Savings Across Cloud Regions. To assess the effect of regions on carbon
savings, we use Carbon Advisor to compute carbon savings achieved by a 24hrs
long ML (ResNet18) job, with $T=l$, across 16 different AWS cloud regions.
Figure 16 provides several insights about the average relative and absolute
carbon savings compared to the carbon-agnostic policy. First, the figure shows
that the carbon emissions of the same job can vary by an order of magnitude
depending on which cloud region is used to execute it. Second, CarbonScaler is
able to achieve significant carbon savings (in %) for most regions, with a
median and average savings of 16% and 19%, respectively. So long as the carbon
costs exhibit diurnal variations, CarbonScaler can reduce the job’s emissions
over the carbon-agnostic policy regardless of whether it runs in a low or high
carbon region. Finally, Figure 16 shows that India’s (  ) region is an
exception: while it has high absolute carbon costs, its low hourly variations
prevent CarbonScaler from generating much savings.

|
---|---
(a) Savings vs. Variation | (b) Savings Distribution
Figure 17. _Effect of Variation (a) and location (b) on _realized_ savings for
an ML (ResNet18) job with $T=l=24$hrs._

Effect of Variability. As noted earlier, regions with variable carbon cost
tend to generate higher carbon savings. This is because the high variations in
such regions provide more low carbon periods to exploit for carbon reductions.
We use coefficient of variation, standard deviation divided by mean, as a
metric to quantify the variability of region. Figure 17(a) shows the carbon
savings, for each starting point of the year, for a 24hrs ML (ResNet18) job
with no excess time for Ontario, Canada using Carbon Advisor. The carbon
savings are highly correlated with the coefficient of variation, with a
Pearson coefficient of 0.82. However, even a highly variable location like
Ontario has a small fraction of hours when savings are less than 20%, a
fraction that will vary depending on the region. Figure 17(b) presents the
distribution of carbon savings and compare regions with different average
coefficient of variation. Note that the curves on the right are better as they
lead to high carbon savings most of the time. The regions represented by the
curves are also strictly ordered by their coefficient of variation, which
means that a coefficient of variation can be used to rank regions, when mean
carbon cost is comparable, for their carbon saving potential.

_Key Takeaway. CarbonScaler achieves carbon savings for most cloud regions
regardless of their absolute carbon cost. In addition, higher diurnal
variations in carbon cost translate to greater savings._

###  5.7. Robustness to Errors

In prior experiments, we assumed that the carbon forecasts are perfect and
applications are profiled on an environment similar to what they eventually
run on, yielding highly accurate marginal capacity curves. However, in
practice, these assumptions may not always be true and we evaluate the impact
of deviation from the ground-truth for these two factors.

Figure 18. _Illustrative example of error in carbon forecasts for an $N$-Body
($N=100k$) workload._

Figure 19. _Effect of carbon forecast errors for an $N$-body ($N$=100k) job._

Figure 20. _Effect of errors in observed and profiled marginal capacity
curves._

Figure 21. _Carbon overhead of the server procurement denial._

Effect of Carbon Forecast Error. Carbon forecasts are easily available through
online tools and services such as (Maps, 2022; WattTime, 2022; Maji et al.,
2022), with a reported mean accuracy of 6.4%. More importantly, the fidelity
of CarbonScaler does not depend on the actual magnitude of the carbon forecast
and instead relies on correctly identifying the hills (high carbon slots) and
valleys (low carbon slots) in the carbon trace, which can be predicted with
high accuracy. To illustrate this effect, we generate carbon traces with
forecast errors of up to 30% by adding a uniformly random error in the range
of -X% to X% for an error of X%. Figure 18(top) shows an example ground-truth
and forecasted (X = 30% error) carbon cost time-series. While an erroneous
forecast deviates from ground-truth at certain points, it still retains the
hills and valleys, leading to harmonious schedules in both cases.

To further quantify the effect of forecast errors, we compare the performance
of CarbonScaler with perfect carbon forecast to an error-agnostic variant of
CarbonScaler that is oblivious to forecast errors, and CarbonScaler that
recompute the schedule when the realized forecast error exceeds 5%. Figure 21
shows the carbon overhead over the perfect forecast scenario. The results
highlight the resiliency of CarbonScaler to forecast errors, as a 30% forecast
error resulted in merely 4% added carbon at 95th percentile.

Effect of Profiling Errors. The marginal capacity curves generated by the
Carbon Profiler can become erroneous if the environment characteristics, such
as network bottlenecks (Jalaparti et al., 2015), change during the execution.
This can impact the carbon savings of a given job if scaling behaviour changes
as a result of deviation from actual marginal capacity curves. To evaluate the
effect of erroneous profiles, we added uniformly random errors to the marginal
capacity curves and measured the carbon consumption using Carbon Advisor.
Figure 21 shows the carbon overhead over CarbonScaler with accurate marginal
capacity profiles. The results shows that the magnitude of error depends on
the application power consumption and scalability behaviour, e.g., the
$N$-body job is less affected by errors as it has low power consumption and
scales somewhat linearly. Additionally, we only show the results for the
initial phase of execution where errors persist. CarbonScaler’s error-handling
mechanism of updating marginal capacity curves, when they deviate, corrects
the errors and net overhead over the entire execution of the workload would be
considerably small.

Impact of Server Procurement Denial. Since CarbonScaler dynamically scales
each job independently, similar to cloud autoscalers, many jobs may request
cloud servers during low carbon periods, creating a high demand for servers
during such periods. Thus, jobs may end up competing with one another for
additional servers, which can cause the cloud platform to deny some requests
for new instances. For example, it is not uncommon to see denials for popular
GPU instances even in the absence of carbon scaling. To evaluate the effect of
such denials, we run a 24hr job with 48hr completion time, $(T=2\times l)$,
with different probability of random procurement denials. In such cases
CarbonScaler keeps retrying its request and then recomputes the schedule to
mitigate the impact of denials on job completion. Figure 21 illustrates that
the carbon overhead, compared to a no denial scenario, increases as the denial
percentage increases. The overhead’s magnitude depends on a job’s scalability
behaviour. For example, a highly scalable $N$-body job incurs 5% overhead
while a non-scalable ML job (VGG16) incurs up to 15% overhead.

_Key Takeaway. CarbonScaler only depends carbon cost trends and simple
recomputations achieve saving comparable to the perfect estimation. The
potential overheads of profiling error can be overcome by updating marginal
capacity curves as they start to deviate. Finally, resource availability can
impact the achievable savings, but the magnitude depends on the scalability
properties of the workloads._

###  5.8. System Overheads

CarbonScaler incurs two types of systemic overheads in its execution. First is
the overhead of scaling as the number of resources change over time. The
scaling overhead is a function of the application state size (e.g., the number
of parameters in ML models). In our experiments, the scaling overhead was
between 20-40 seconds. We note that suspend-resume incurs similar overheads as
the state is scale-independent. The second source of overhead is the time
needed by Carbon Profiler to obtain marginal capacity curves. As mentioned in
§4.1, profiling time can be configured using profile duration $\alpha$ at each
allocation level, and granularity $\beta$ of allocations profiled. We use
$\alpha=1$ minute, and $\beta=1$, i.e., we profile across all possible
allocation levels. Thus, for our evaluation, the once-needed total profile
time was 40 minutes, 8-minutes per workload in Figure 9.

_Key Takeaway. CarbonScaler’s systemic overheads are small, configurable, and
generally occur once._

##  6\. Related Work

Energy Accounting. CarbonScaler depends on a cluster’s ability to account for
an individual tenant’s energy consumption. CarbonScaler currently focuses on
CPU and GPU resources as they are 1) highly correlated with total energy
consumption (Kansal et al., 2010), 2) software tools such as (RAPL) (David et
al., 2010) and nvidia-smi (NVIDIA, 2022), are available on modern processors
and GPUs. However, our accounting methods can be generalized to other server
resources as shown in (Bourdon et al., 2013; Kansal et al., 2010; Colmant et
al., 2015; Fieni et al., 2020). Such accounting techniques are vital for
holistic carbon optimization since cloud service providers such as Microsoft
(Microsoft, 2022b) and AWS (Microsoft, 2022a) are starting to offer basic
carbon management capabilities.

Temporal Shifting. Temporal shifting by delaying execution of batch jobs from
high carbon slots to lower carbon slots has been explored in (Wiesner et al.,
2021; Dodge et al., 2022; Radovanovic et al., 2022). The Let’s wait-a-while
(Wiesner et al., 2021) approach uses temporal shifting to reduce the carbon
footprint of batch workloads using threshold and deadline-based methods and by
exploiting overnight or weekends hours to extract savings. In (Dodge et al.,
2022), the authors highlight the implications of scheduling AI workloads in
different settings and suggest temporal shifting to minimize the carbon
footprint. Finally, in (Radovanovic et al., 2022), the authors employ a
virtual limit on resources when carbon cost is high to force the scheduler to
shift workloads to lower carbon periods. As noted in §1, a limitation of
temporal shifting approaches is that they delay job completion times and may
also require user’s to specify deadlines for job. In contrast, CarbonScaler
employs resource elasticity to scale and complete jobs in a timely manner and
can additionally exploit temporal flexibility whenever available.

Spatial Shifting. Spatial shifting approaches that to select the region with
lowest carbon footprint to execute newly arriving jobs has also been studied.
The authors of (Acun et al., 2023; Dodge et al., 2022; Zheng et al., 2020)
explore the spatial selection to achieve lower carbon cost. The authors of
(Acun et al., 2023) explore data center and power upgrade plans to allow more
carbon-efficient execution, while (Dodge et al., 2022) explore cloud data
center regions and potential carbon savings. Lastly, (Zheng et al., 2020)
exploits migration to avoid energy curtailment. While we study the benefits on
using different geographic regions to run carbon scaling jobs in §5.6, a full
analysis of combining spatial shifting with carbon scaling is part of future
work and beyond the scope of the current paper.

##  7\. Conclusion

Many compute-intensive cloud workloads, such as ML training and scientific
computations, have inherent resource elasticity and temporal flexibility that
can be leveraged to optimize for carbon emission reductions. To exploit this
opportunity, we propose CarbonScaler that judiciously scales up or down an
application, based on the application’s scalability behaviour and carbon cost,
to minimize its carbon emissions. We implement CarbonScaler as a cloud-based
autoscaler implemented using Kubernetes as well as a simulation-based advisory
tool to facilitate pre-deployment analysis. We demonstrate the efficacy of
CarbonScaler in reducing carbon emissions for a variety of workloads, job
configurations, and cloud regions. In the future, we plan to extend
CarbonScaler into cluster-wide scheduling. Cluster-wide scheduling is
accompanied with challenges such as heterogeneity, resource pressure,
priorities, and power management.

## References

  * (1)
  * Aarseth (1985) J. Sverre Aarseth. 1985\.  12 - Direct Methods for N-Body Simulations.  In _Multiple Time Scales_. Academic Press, 377–418.  https://doi.org/10.1016/B978-0-12-123420-1.50017-3
  * Acun et al. (2023) Bilge Acun, Benjamin Lee, Fiodar Kazhamiaka, Kiwan Maeng, Manoj Chakkaravarthy, Udit Gupta, David Brooks, and Carole-Jean Wu. 2023\.  Carbon Explorer: A Holistic Approach for Designing Carbon Aware Datacenters.  _Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems_ (2023).
  * Amdahl (1967) Gene M Amdahl. 1967\.  Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities. In _Proceedings of the Spring Joint Computer Conference_.
  * Andrae and Edler (2015) Anders S. G. Andrae and Tomas Edler. 2015.  On Global Electricity Usage of Communication Technology: Trends to 2030.  _Challenges_ 6 (2015).
  * AWS (2022) AWS. 2022.  AWS Auto Scaling.  https://aws.amazon.com/autoscaling/.
  * Bashir et al. (2022) Noman Bashir, David Irwin, Prashant Shenoy, and Abel Souza. 2022.  Sustainable Computing – Without the Hot Air. In _HotCarbon: Workshop on Sustainable Computer Systems Design and Implementation_.
  * Bourdon et al. (2013) Aurélien Bourdon, Adel Noureddine, Romain Rouvoy, and Lionel Seinturier. 2013.  Powerapi: A Software Library to Monitor the Energy Consumed at the Process-level.  _ERCIM News_ (2013).
  * Cai et al. (2017) Ermao Cai, Da-Cheng Juan, Dimitrios Stamoulis, and Diana Marculescu. 2017.  Neuralpower: Predict and Deploy Energy-efficient Convolutional Neural Networks. In _Asian Conference on Machine Learning_.
  * Chien (2021) A. Chien. 2021.  Driving the Cloud to True Zero Carbon.  _Communication of the ACM_ 64, 2 (February 2021).
  * Colmant et al. (2015) Maxime Colmant, Mascha Kurpicz, Pascal Felber, Loïc Huertas, Romain Rouvoy, and Anita Sobe. 2015.  Process-Level Power Estimation in VM-Based Systems. In _Proceedings of the Tenth European Conference on Computer Systems_ (Bordeaux, France) _(EuroSys ’15)_. Association for Computing Machinery, New York, NY, USA, Article 14, 14 pages.  https://doi.org/10.1145/2741948.2741971
  * Cormen et al. (2009) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009.  _Introduction to Algorithms, 3rd Edition_.  MIT Press.  http://mitpress.mit.edu/books/introduction-algorithms
  * David et al. (2010) Howard David, Eugene Gorbatov, Ulf R Hanebutte, Rahul Khanna, and Christian Le. 2010.  RAPL: Memory Power Estimation and Capping. In _ACM/IEEE International Symposium on Low-Power Electronics and Design (ISLPED)_.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_. Association for Computational Linguistics, Minneapolis, Minnesota, 4171–4186.  https://doi.org/10.18653/v1/N19-1423
  * Dodge et al. (2022) Jesse Dodge, Taylor Prewitt, Remi Tachet des Combes, Erika Odmark, Roy Schwartz, Emma Strubell, Alexandra Sasha Luccioni, Noah A. Smith, Nicole DeCario, and Will Buchanan. 2022\.  Measuring the Carbon Intensity of AI in Cloud Instances. In _2022 ACM Conference on Fairness, Accountability, and Transparency_ _(FAccT ’22)_.
  * Fieni et al. (2020) Guillaume Fieni, Romain Rouvoy, and Lionel Seinturier. 2020\.  SmartWatts: Self-Calibrating Software-Defined Power Meter for Containers. In _2020 20th IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing (CCGRID)_. 479–488.  https://doi.org/10.1109/CCGrid49817.2020.00-45
  * Forum (1994) Message P Forum. 1994\.  _MPI: A Message-Passing Interface Standard_.  Technical Report. USA.
  * Google (2022) Google. 2022.  Google’s Green PPAs: What, How, and Why.  https://static.googleusercontent.com/media/www.google.com/en//green/pdfs/renewable-energy.pdf.
  * Harvey (2021) Fiona Harvey. 2021\.  The Guardian, Major Climate Changes Inevitable and Irreversible – IPCC’s Starkest Warning Yet.  https://www.theguardian.com/science/2021/aug/09/humans-have-caused-unprecedented-and-/irreversible-change-to-climate-scientists-warn.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016\.  Deep Residual Learning for Image Recognition. In _Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR)_.
  * Institute (2022) World Resource Institute. 2022\.  _GreenHouseGas Protocol_.  https://ghgprotocol.org/
  * Jacobs et al. (2017) Sam Adé Jacobs, Nikoli Dryden, Roger Pearce, and Brian Van Essen. 2017.  Towards Scalable Parallel Training of Deep Neural Networks. In _Proceedings of the Machine Learning on HPC Environments_ _(MLHPC’17)_.
  * Jalaparti et al. (2015) Virajith Jalaparti, Peter Bodik, Ishai Menache, Sriram Rao, Konstantin Makarychev, and Matthew Caesar. 2015.  Network-Aware Scheduling for Data-Parallel Jobs: Plan When You Can. In _Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication_ (London, United Kingdom) _(SIGCOMM ’15)_. Association for Computing Machinery, New York, NY, USA, 407–420.  https://doi.org/10.1145/2785956.2787488
  * Jones (2018) Nicola Jones. 2018\.  How to Stop Data Centres from Gobbling Up the World’s Electricity.  _Nature_ (2018).
  * Justus et al. (2018) Daniel Justus, John Brennan, Stephen Bonner, and Andrew Stephen McGough. 2018.  Predicting the Computational Cost of Deep Learning Models. In _2018 IEEE International Conference on Big Data (Big Data)_.
  * Kansal et al. (2010) Aman Kansal, Feng Zhao, Jie Liu, Nupur Kothari, and Arka A. Bhattacharya. 2010.  Virtual Machine Power Metering and Provisioning. In _Proceedings of the 1st ACM Symposium on Cloud Computing_ (Indianapolis, Indiana, USA) _(SoCC ’10)_. Association for Computing Machinery, New York, NY, USA, 39–50.  https://doi.org/10.1145/1807128.1807136
  * Kubeflow (2022) Kubeflow. 2022.  Kubeflow: The Machine Learning Toolkit for Kubernetes.  https://www.kubeflow.org/.  Accessed: 2022-10-03.
  * Kubernetes (2022) Kubernetes. 2022\.  Kubernetes: Production-grade Container Orchestration.  https://kubernetes.io/.  Accessed: 2022-10-03.
  * Maji et al. (2022) Diptyaroop Maji, Ramesh K. Sitaraman, and Prashant Shenoy. 2022\.  DACF: Day-Ahead Carbon Intensity Forecasting of Power Grids Using Machine Learning. In _Proceedings of the Thirteenth ACM International Conference on Future Energy Systems_ _(e-Energy’22)_.
  * Maps (2022) Electricity Maps. 2022\.  Electricity Map.  https://www.electricitymap.org/map.
  * Masanet et al. (2020) Eric R. Masanet, Arman Shehabi, Nuoa Lei, Sarah J. Smith, and Jonathan G. Koomey. 2020.  Recalibrating Global Data Center Energy-use Estimates.  _Science_ (2020).
  * Masson-Delmotte et al. (2021) Valérie Masson-Delmotte, Panmao Zhai, Anna Pirani, Sarah L Connors, Clotilde Péan, Sophie Berger, Nada Caud, Yang Chen, Leah Goldfarb, Melissa I Gomis, et al. 2021\.  _Summary for Policymakers. In: Climate Change 2021: The Physical Science Basis. Contribution of Working Group I to the Sixth Assessment Report of the Intergovernmental Panel on Climate Change_.  Technical Report. United Nation Intergovernmental Panel on Climate Change (IPCC).
  * META (2022) META. 2022.  How We’re Helping Fight Climate Change.  https://about.fb.com/news/2021/06/2020-sustainability-report-how-were-helping-fight-climate-change/.
  * Microsoft (2022a) Microsoft. 2022a.  AWS Customer Carbon Footprint Tool.  https://aws.amazon.com/blogs/aws/new-customer-carbon-footprint-tool/.
  * Microsoft (2022b) Microsoft. 2022b.  Microsoft Carbon accouting tool.  https://www.microsoft.com/en-us/sustainability/emissions-impact-dashboard.
  * Microsoft (2022c) Microsoft. 2022c.  Microsoft is Changing the Way It Buys Renewable Energy.  https://www.theverge.com/2021/7/14/22574431/microsoft-renewable-energy-purchases.
  * Moghaddam et al. (2014) Fereydoun Farrahi Moghaddam, Reza Farrahi Moghaddam, and Mohamed Cheriet. 2014.  Carbon-aware Distributed Cloud: Multi-level Grouping Genetic Algorithm.  _Cluster Computing_ (2014).
  * NVIDIA (2022) NVIDIA. 2022.  Manage and Monitor GPUs in Cluster Environments.  https://developer.nvidia.com/dcgm.  Accessed: 2022-10-08.
  * Oyama et al. (2016) Yosuke Oyama, Akihiro Nomura, Ikuro Sato, Hiroki Nishimura, Yukimasa Tamatsu, and Satoshi Matsuoka. 2016.  Predicting Statistics of Asynchronous SGD Parameters for a Large-scale Distributed Deep Learning System on GPU Supercomputers. In _2016 IEEE International Conference on Big Data (Big Data)_.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019.  PyTorch: An Imperative Style, High-Performance Deep Learning Library. In _Advances in Neural Information Processing Systems_ _(NIPS’19)_.
  * Pei et al. (2019) Ziqian Pei, Chensheng Li, Xiaowei Qin, Xiaohui Chen, and Guo Wei. 2019.  Iteration Time Prediction for CNN in Multi-GPU Platform: Modeling and Analysis.  _IEEE Access_ (2019).
  * Peng et al. (2018) Yanghua Peng, Yixin Bao, Yangrui Chen, Chuan Wu, and Chuanxiong Guo. 2018.  Optimus: An Efficient Dynamic Resource Scheduler for Deep Learning Clusters. In _Proceedings of the Thirteenth EuroSys Conference_ (Porto, Portugal) _(EuroSys ’18)_. Association for Computing Machinery, New York, NY, USA, Article 3, 14 pages.  https://doi.org/10.1145/3190508.3190517
  * Qi et al. (2017) Qi, Evan R. Sparks, and Ameet S. Talwalkar. 2017.  Paleo: A Performance Model for Deep Neural Networks. In _The International Conference on Learning Representations_ _(ICLR’17)_.
  * Radovanovic et al. (2022) Ana Radovanovic, Ross Koningstein, Ian Schneider, Bokan Chen, Alexandre Duarte, Binz Roy, Diyue Xiao, Maya Haridasan, Patrick Hung, Nick Care, Saurav Talukdar, Eric Mullen, Kendal Smith, Mariellen Cottman, and Walfredo Cirne. 2022.  Carbon-Aware Computing for Datacenters.  _IEEE Transactions on Power Systems_ (2022), 1–1.  https://doi.org/10.1109/TPWRS.2022.3173250
  * Sergeev and Balso (2018) Alexander Sergeev and Mike Del Balso. 2018.  Horovod: Fast and Easy Distributed Deep Learning in TensorFlow.  _arXiv preprint arXiv:1802.05799_ (2018).
  * Shi et al. (2018) Shaohuai Shi, Qiang Wang, and Xiaowen Chu. 2018.  Performance Modeling and Evaluation of Distributed Deep Learning Frameworks on GPUs. In _2018 IEEE 16th Intl Conf on Dependable, Autonomic and Secure Computing, 16th Intl Conf on Pervasive Intelligence and Computing, 4th Intl Conf on Big Data Intelligence and Computing and Cyber Science and Technology Congress(DASC/PiCom/DataCom/CyberSciTech)_. 949–957.  https://doi.org/10.1109/DASC/PiCom/DataCom/CyberSciTec.2018.000-4
  * SIGs (2022) Kubernetes SIGs. 2022\.  _Kubernetes Metrics Server_.  Kubernetes SIGs.  https://github.com/kubernetes-sigs/metrics-server
  * Souza et al. (2023) Abel Souza, Noman Bashir, Jorge Murillo, Walid Hanafy, Qianlin Liang, David Irwin, and Prashant Shenoy. 2023.  Ecovisor: A Virtual Energy System for Carbon-Efficient Applications. In _27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS ’23)_.
  * Tan and Le (2019) Mingxing Tan and Quoc Le. 2019.  EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks. In _Proceedings of the 36th International Conference on Machine Learning_ _(Proceedings of Machine Learning Research, Vol. 97)_. PMLR, 6105–6114.  https://proceedings.mlr.press/v97/tan19a.html
  * Tirmazi et al. (2020) Muhammad Tirmazi, Adam Barker, Nan Deng, Md E. Haque, Zhijing Gene Qin, Steven Hand, Mor Harchol-Balter, and John Wilkes. 2020\.  Borg: The next Generation. In _Proceedings of the Fifteenth European Conference on Computer Systems_ (Heraklion, Greece) _(EuroSys ’20)_. Association for Computing Machinery, New York, NY, USA, Article 30, 14 pages.  https://doi.org/10.1145/3342195.3387517
  * WattTime (2022) WattTime. 2022.  WattTime.  https://www.watttime.org/.
  * Weng et al. (2022) Qizhen Weng, Wencong Xiao, Yinghao Yu, Wei Wang, Cheng Wang, Jian He, Yong Li, Liping Zhang, Wei Lin, and Yu Ding. 2022\.  MLaaS in the wild: Workload analysis and scheduling in Large-Scale heterogeneous GPU clusters. In _19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22)_. USENIX Association, 945–960.
  * Wiesner et al. (2021) Philipp Wiesner, Ilja Behnke, Dominik Scheinert, Kordian Gontarska, and Lauritz Thamsen. 2021\.  Let’s Wait Awhile: How Temporal Workload Shifting Can Reduce Carbon Emissions in the Cloud. In _Proceedings of the 22nd International Middleware Conference_ (Québec city, Canada) _(Middleware ’21)_. Association for Computing Machinery, New York, NY, USA, 260–272.  https://doi.org/10.1145/3464298.3493399
  * Zheng et al. (2020) Jiajia Zheng, Andrew A. Chien, and Sangwon Suh. 2020\.  Mitigating Curtailment and Carbon Emissions through Load Migration between Data Centers.  _Joule_ 4, 10 (2020), 2208–2222.  https://doi.org/10.1016/j.joule.2020.08.001
  * Zhou et al. (2013) Zhi Zhou, Fangming Liu, Yong Xu, Ruolan Zou, Hong Xu, John C.S. Lui, and Hai Jin. 2013.  Carbon-Aware Load Balancing for Geo-distributed Cloud Services. In _International Symposium on Modelling, Analysis and Simulation of Computer and Telecommunication Systems_ _(MASCOTS’13)_.

##  Appendix A CarbonScaler Optimality

The carbon scaling problem resembles a fractional knapsack problem that can be
solved optimally using greedy algorithms (Cormen et al., 2009).

###### Proof.

We prove Theorem 1 by contradiction. Let $S$ be an optimal solution schedule
that finishes work $W$ and has a carbon cost $C_{S}$. The schedule $S$ is
constructed by allocating time slots and number of server, until $W$ is
completed. The tuple $(i,j)$ denotes the $i$-th time slot and the $j$-th
server allocated to the job. $MC_{j}$ is the marginal work done when
allocating the $j$-th server, and $c_{i}$ is the carbon cost used per server
at time slot $i$. The total carbon cost is $C_{S}=\sum_{i\in n}{c_{i}\times
S[i]}$, where $S[i]$ is the used number of servers at time slot $i$.

The tuple $(k,l)$ denotes the $k$-th time slot and the $l$-th server, with
marginal capacity per unit carbon of $MC_{l}/c_{k}$. Assume that there exists
a time slot $i$ and a number of servers $j$, where
$MC_{l}/c_{k}>MC_{j}/c_{i}$, s.t., $(i,j)\in S$ and $(k,l)\notin S$. We denote
$S^{{}^{\prime}}$ as a new schedule, where we only switch the $i$-th time slot
and $j$-th server with $k$-th time slot and the $l$-th server, which has the
higher marginal capacity per unit carbon. To ensure that the schedule
$S^{{}^{\prime}}$ finishes work $W$, the amount of work $MC_{j}$ must be
incorporated in the new schedule. We denote $c_{i}$ and $\gamma$, as the old
carbon and new carbon cost to perform work $MC_{j}$, respectively. $\gamma$ is
computed based on the relationship between $l$ and $j$, where:

(1) $\gamma=\begin{cases}c_{k}\cdot\frac{MC_{j}}{MC_{l}},&\text{if $l\leq
j$}.\\\ c_{k}+(\frac{MC_{j}-MC_{l}}{MC_{j}})\cdot c_{i},&\text{otherwise
$(l>j)$}.\\\ \end{cases}$

In the first case $(l\leq j)$, $MC_{l}\geq MC_{j}$ and job will use part or
all of the time slot $k$. In the second case $(l>j)$, $MC_{l}<MC_{j}$. We
perform $MC_{l}$ work in time slot $k$, and run the overflow work,
$MC_{j}-MC_{l}$, in time slot $i$, utilizing $\frac{MC_{j}-MC_{l}}{MC_{j}}$ of
time slot $i$ and all of time slot $k$.

Next, to show that $c_{i}>\gamma$ and $(C_{S}>C_{S^{{}^{\prime}}})$, we
consider both cases. In the first case, since $MC_{l}/c_{k}>MC_{j}/c_{i}$,
then:

(2) $\displaystyle c_{i}>c_{k}\cdot\frac{MC_{j}}{MC_{l}}$ (3) $\displaystyle
c_{i}>\gamma$

In the second case, since $\frac{MC_{l}}{c_{k}}>\frac{MC_{j}}{c_{i}}$, then:

(4) $\displaystyle c_{k}<\frac{MC_{l}}{MC_{j}}\cdot c_{i}$

By substituting $c_{k}$ in case 2:

(5) $\displaystyle\frac{MC_{l}}{MC_{j}}\cdot
c_{i}+(\frac{MC_{j}-MC_{l}}{MC_{j}})\cdot c_{i}>\gamma$ (6)
$\displaystyle\frac{MC_{l}\cdot c_{i}+MC_{j}\cdot c_{i}-MC_{l}\cdot
c_{i}}{MC_{j}}>\gamma$ (7) $\displaystyle c_{i}>\gamma$

Therefore, carbon consumption of $S^{{}^{\prime}}$, denoted as
$C_{S^{{}^{\prime}}}=C_{S}-c_{i}+\gamma$ is less than carbon cost of $S$
$(C_{S})$, since $c_{i}>\gamma$. Hence, $S$ is not optimal, a contradiction. ∎