# A Learning-based Optimal Market Bidding Strategy
for Price-Maker Energy Storage

Mathilde D. Badoual1 and Scott J. Moura1 1M. Badoual and S. Moura are with the
Energy, Controls and Applications Lab (eCAL) at University of California,
Berkeley, USA. {mathilde.badoual<EMAIL_ADDRESS>
###### Abstract

Load serving entities with storage units reach sizes and performances that can
significantly impact clearing prices in electricity markets. Nevertheless,
price endogeneity is rarely considered in storage bidding strategies and
modeling the electricity market is a challenging task. Meanwhile, model-free
reinforcement learning such as the Actor-Critic are becoming increasingly
popular for designing energy system controllers. Yet implementation frequently
requires lengthy, data-intense, and unsafe trial-and-error training. To fill
these gaps, we implement an online Supervised Actor-Critic (SAC) algorithm,
supervised with a model-based controller – Model Predictive Control (MPC). The
energy storage agent is trained with this algorithm to optimally bid while
learning and adjusting to its impact on the market clearing prices. We compare
the supervised Actor-Critic algorithm with the MPC algorithm as a supervisor,
finding that the former reaps higher profits via learning. Our contribution,
thus, is an online and safe SAC algorithm that outperforms the current model-
based state-of-the-art.

##  I INTRODUCTION

###  I-A Background & Motivation

Large-scale energy storage systems can solve a number of issues that can arise
on electric power systems with high penetration of intermittent renewable
energy generation. Energy storage and more specifically, lithium-ion batteries
which are particularly fast to charge and discharge, can help to keep the
voltage within bounds, stabilize grid frequency, and provide reserves that can
be called on should a contingency occur. Storage can also address issues
related to surplus that can occur when renewable sources produce more
electricity than consumers demand, and can mitigate congestion when the
transmission capacity of the system is exceeded. Because legacy grid
technologies are unable to store electricity once produced, electricity prices
vary significantly between times of surplus and shortage. This allows
batteries to conduct arbitrage, and gives them a competitive edge on the
energy market. [1] [2] [3].

In 2018, the U.S. Energy Information Administration [4] reported that
operational large-scale battery storage represented 869 megawatts (MW) of
power capacity and 1,236-megawatt hours (MWh) of energy capacity. Moreover,
markets across the globe are implementing new regulations that will create new
value streams for large-scale batteries [5]. In the US, the Federal Energy
Regulatory Commission issued an order in 2011 requiring transmission grid
operators – including Independent System Operators and Regional Transmission
Operations (ISO/RTO) – to compensate fast-ramping resources on the frequency
regulation market [6]. In Europe, the Frequency Control Regulation (FCR)
market is updated to respond to the increased need for battery storage [7].
These new market rules favor grid-scale storage resources, which have response
capabilities that conventional generation resources do not. These market
incentives have led to increased investment in energy storage capacity.

The increase in storage capacity coupled with a unique position in the market
has caused grid-scale energy storage to become a driver of the market price.
In economic terms, energy storage is said to be a price-maker, or a
monopolistic seller capable of influencing the market because no substitutes
exist for their product. Conventional power plants, on the other hand, are
said to be a price-taker with trivial influence on the market due to market
size, suitability, or other anti-competitive factors. In a perfectly
competitive market, all the sellers are price-takers and bid their marginal
cost. More details on the price-maker/price-taker concepts can be found in [8]
and [9].

One real-world example is the Australian Hornsdale power reserve. Upon
entering the Australian market [10] [11] in December 2017, the battery
achieved over 55% of the Frequency Control Ancilliary Services (FCAS) revenues
in South Australia and prices went down by 90%. This occurred both due to the
size of the battery and due to its fast-ramping capabilities that could not be
matched by other market participants with pre-existing technologies.

Strategic bidding in markets with price-makers is a very challenging problem,
due to the complexity of the market model as well as the lack of information
about other players. Each agent must try to anticipate not only the demand but
also the actions of other market participants. However, agents generally do
not have models that describe the bidding strategies of other market
participants. The current work explores the use of adaptive control for
optimizing the bidding strategy of a price-maker agent participating in a
regular wholesale market.

###  I-B Literature Review

Several papers explore optimal bidding algorithms on the electricity market
when bids influence the clearing price, i.e. the market player is a price-
maker. Some relevant examples include the following: Oren et al. [12] computed
the optimal bidding strategy with dynamic programming by estimating other
market players. Kwon et al. [13] review the optimization problem for bidding
in the day ahead market. Velazquez et al. [14] base their bidding strategy on
the study of the residual demand curve.

The bidding of energy storage capacity on the electricity market adds a layer
of complexity. The battery has a limited capacity and accumulates revenue by
scheduling efficiently generation and load modes. J. Arteaga et al. [15]
develop a robust and stochastic optimization for the bidding on the Real-Time
and Day-Ahead market in which the battery is a price-taker. They also study
participation in the ancillary services market where the storage system is
price-maker due to the battery efficiency in ramping up and down under
emergency.

Throughout this literature, a common method to solve the optimal bidding
strategy for a price-maker is used. A bi-level optimization program where the
first layer maximizes the player’s revenue and the second layer solves a
dispatch problem to maximize the social welfare. This method is developed,
among others, by Tómasson et al. [16] and Y. Ye et al. [17]. The resulting bi-
level optimization problem is complex to solve and is commonly simplified
using the Karush-Kuhn-Tucker (KKT) conditions relying on the convexity of the
problem which is not guaranteed. Indeed, modeling the energy market dynamics
as an optimization problem yields non-linearities. For instance, the dispatch
can involve binary unit commitments. Perhaps more importantly, modeling the
entire market requires knowledge of other players’ strategies and predictions
of their future behaviors. This can be difficult or even impossible due to
lack of data and highly non-predictable behavior. Moreover, market prices can
be volatile and depend on physical constraints, e.g. congestion, frequency
instabilities.

A possible solution for this problem is to use learning-based and adaptive
controllers, such as reinforcement Learning (RL) which learns a controller (or
policy) via structured trial-and-error. Such techniques enable design of
controllers for partially known systems. Moreover, the learned controller
becomes a function mapping the state to an action (state-feedback control),
which makes the controller computationally efficient. Glavic et al. [18]
review the literature of Reinforcement Learning in electric power system
decision making, presenting recent breakthroughs in Reinforcement Learning
such as “safe RL” and “path integral control for RL”. More recently Z. Zhang
et al. [19] review the application of Deep Reinforcement Learning (DRL) –
Reinforcement Learning with the use of Deep Neural Networks – in Power
Systems. They point out the benefits of DRL as an adaptive and model-free
controller applied on electricity market trading in the case of incomplete
information.

Among others, Gajjar et al. [20] use an Actor-Critic Algorithm to solve the
bidding problem. The authors construct an Actor-Critic algorithm to model the
behavior of generating companies, formalizing a mathematical model for
competitor’s behavior. However the battery is considered as a price-taker on
the market. As a result, the paper does not investigate the use of DRL in an
environment reacting to its action. Y. Ye et al. [17] use a form of Policy
Gradient method in the case of a price-maker battery. The algorithm is a Deep
Deterministic Policy Gradient with a Prioritized experience replay. In other
words, Ye et al. use a policy gradient trained using a prioritized sample
batch. The paper reports interesting results but does not tackle the safety
issue of trial and error training on a real market, neither the complexity of
building a realistic market environment for an off-line training. Indeed, the
main justification for the use of RL and DRL lies in the complexity of the
market model which makes the optimization of the bidding strategy a complex
task. However, if this model can be built to train an adaptive algorithm, then
optimization techniques will be more safe and reliable than a trial and error
training.

Safety in DRL can take multiple definitions. In our context, safety is
achieved when actions taken by the DRL algorithm, also called agent or policy,
are not putting the system in states that are physically impossible to reach
and that can lead to dangerous situations, such as discharging an empty
battery.

###  I-C Contributions

The main contribution of this paper is to ensure safety and improve
performance via an online learning-based algorithm for optimal energy storage
bidding, under price-maker conditions. Specifically, we develop a Supervised
Actor-Critic algorithm. The supervisor technique reduces the action space
dimension and thus accelerates the learning process while ensuring that the
algorithm tries less dangerous actions. The supervisor is a naive and model-
based algorithm, MPC, with the assumption that the battery is a price-taker.
This algorithm is deterministic and does not take dangerous actions. In
addition, we develop a shield, to protect the battery from charging or
discharging above limits. Finally, we add a penalty term to the reward
function to inform the algorithm of dangerous actions. We achieve a more
efficient bidding strategy than the baseline model-based technique, while also
ensuring safety during training.

###  I-D Paper Organization

Section II, details the market model and simulation. Section III introduces
the Supervised Actor-Critic and Section IV describes the results.

##  II Market and Storage System Model

In this section we describe the market setup and energy storage system
operation used in our simulation.

Figure 1: The Market Clearing Process as a Uniform-Price Auction

The electricity market is managed by the Independent System Operator (ISO) and
maximizes the social welfare across generators and consumers so that enough
generation is dispatched to serve a predicted demand. One step of the bidding
process is represented in Fig. 1, where the demand is the vertical black line.
At the point where the cumulative bid capacity reaches the demand, the market
clears at this bid price, represented by the green line on the figure. This
price is the so-called clearing price. The market used in this paper follows a
uniform-price auction [21], i.e. the actors are paid the clearing price
instead of being paid at their bidding price. The clearing process can be
written as the following optimization problem (1)-(3):

$\displaystyle\min_{{\color[rgb]{0,0,1}P^{t}}}\quad$
$\displaystyle\sum_{i=0}^{n}c^{t}_{i}{\color[rgb]{0,0,1}P^{t}_{i}}$ (1)
$\displaystyle\textrm{s.t}\quad\forall i,\quad$ $\displaystyle
0\leq{\color[rgb]{0,0,1}P^{t}_{i}}\leq p^{t}_{i}$ (2)
$\displaystyle\sum_{i=0}^{n}{\color[rgb]{0,0,1}P^{t}_{i}}=\hat{d}_{t}$ (3)

Each agent is represented by the index $i$ and sends a bid at each time step
$t$. A bid is of the form $\\{c^{t}_{i},p^{t}_{i}\\}$ where $c^{t}_{i}$ is the
cost per unit energy and $p^{t}_{i}$ is the capacity that the agent $i$ can
provide during time $t$. The variable $\hat{d}_{t}$ is the total predicted
energy demand from retailers, industrial sites or storage systems. The market
solves the social welfare maximization problem (1) by dispatching a capacity
$P^{t}_{i}$ for each agent while matching supply and demand (3). This capacity
is either 0 when the bid is not cleared, or a number between 0 and $p^{t}$,
the capacity bid by the agent (2). The optimization variable is
$P^{t}=[P^{t}_{0}\ \cdots\ P^{t}_{n}]^{T}$ with $n$ the number of agents.

The complete bidding process of the battery owner or agent can be described as
follows, and represented in Fig. 2. The agent sends a bid to the market. The
market clears the bids depending on the demand and according to the process
described in Fig. 1. Then, if the battery bid is cleared amongst all bids to
the left of the black line in Fig. 1, a command is passed to the battery to
provide the capacity dispatched by the market at the cleared price. The
combination of the market state and the battery state is sent back to the
battery’s bidding agent to compute a new bid at the next step.

Batteries generally have a larger impact on ancillary service markets and
especially on frequency control markets. The reason is that, in small markets,
the battery’s fast response give them a competitive advantage over other
players [22]. Here, we focus on the use and limitations of reinforcement
learning as a bidding algorithm. We use a stylized representation of market
dynamics in order to focus more specifically on the algorithm itself.

##  III Bidding Strategy Algorithm

In this section we introduce two algorithms: the first is a common Model
Predictive Control (MPC) algorithm that computes the optimal bidding strategy
over a one day horizon. It will serve as our benchmark algorithm, and
importantly it does not take into account that the battery is a price-maker on
the market. The second and novel approach is an adaptive controller which
learns and adapts to the price-maker situation. Specifically, the proposed
controller is trained using a new SAC algorithm where the supervisor is the
aforementioned MPC controller.

The online training of the SAC during the simulation is detailed in Fig. 2,
and explained in the next sections.

Figure 2: Learning and Bidding procedure for the proposed SAC. Bids are
produced by combining actions from the MPC supervisor and the DRL agent. A
shield adjusts bids to ensure physical and market constraints are satisfied by
allowing only feasible bids. After the market clears and the battery state
evolves, the reward (i.e. profit) is used to update the DRL agent.

###  III-A Model Predictive Control as a RL Supervisor

Under the price-taker assumption, the energy prices are considered exogenous
to the bidding strategy, and the optimal bidding strategy is computed
regardless of its impact on the market price. In this case, the strategy
relies on predictions of the clearing price: $\hat{\lambda}_{energy}^{t}$ and
is formulated as a common deterministic Model Predictive Control algorithm:

$\displaystyle\max_{{\color[rgb]{0,0,1}p_{l}},{\color[rgb]{0,0,1}p_{g}},{\color[rgb]{0,0,1}soe},{\color[rgb]{0,0,1}m}\in\mathbb{R}^{H}}\quad$
$\displaystyle\sum_{t=T}^{T+H}\hat{\lambda}^{t}({\color[rgb]{0,0,1}p^{t}_{g}}-{\color[rgb]{0,0,1}p^{t}_{l}})$
(4) $\displaystyle\textrm{s. to:}\quad\forall t,\quad$
$\displaystyle{\color[rgb]{0,0,1}soe^{t+1}}={\color[rgb]{0,0,1}soe^{t}}-\eta_{g}{\color[rgb]{0,0,1}p^{t}_{g}}+\eta_{l}{\color[rgb]{0,0,1}p^{t}_{l}}$
(5) $\displaystyle{\color[rgb]{0,0,1}m^{t}}\in\\{0,1\\}$ (6) $\displaystyle
0\leq{\color[rgb]{0,0,1}p^{t}_{l}}\leq{\color[rgb]{0,0,1}m^{t}}\overline{p_{l}}$
(7) $\displaystyle
0\leq{\color[rgb]{0,0,1}p^{t}_{g}}\leq(1-{\color[rgb]{0,0,1}m^{t}})\overline{p_{g}}$
(8)
$\displaystyle\underline{soe}\leq{\color[rgb]{0,0,1}soe^{t}}\leq\overline{soe}$
(9)

The cost function (4) is the cumulative revenue for the energy storage system
owner over the horizon $H$. The variables $p_{l}^{t}$ and $p_{g}^{t}$ are the
load and generation bids with price $\hat{\lambda}^{t}$. Equation (5)
describes the storage system dynamics, with coefficients $\eta_{g}$ and
$\eta_{l}$ referring to the charging and discharging efficiency coefficients.
Since the storage system agent is not allowed to participate on the energy
market as a load _and_ a generator simultaneously, constraint (6) forces the
solution to chose between one of the two products (7) and (8). The remaining
constraints (9) are physical limits on the storage system capacities. Other
physical constraints as temperature could be added in the form of linear
constraints without changing the structure of the problem solved in this
paper.

In a perfectly competitive uniform-price auction market the agents are bidding
their marginal cost. The marginal cost of the battery can be seen as the cost
of electricity at the time of generation, thus the battery bids the expected
clearing price $\hat{\lambda}^{t}$. As a price-taker the battery will not
impact the market clearing price and can be sure to clear if its bidding price
is less than or equal to the market clearing price. The complete bid can be
written as: $\\{c^{t},p^{t}\\}=\\{\hat{\lambda}^{t},p_{g}^{t}-p_{l}^{t}\\}$.

The problem is formulated for a horizon $H$, which allows the battery to plan
its charging and discharging schedule depending on the variation of
electricity prices. In MPC, only the first step of the solution bid is used
and the problem is re-computed at every new time step $t$.

###  III-B Supervised Actor-Critic Algorithm

Reinforcement Learning (RL) theory is based on the idea that we learn how to
perform an action in an environment by structured try-fail cycles. In other
words, after performing an action, we receive a reward, which measures the
value of our action. We then learn how to increase that reward with subsequent
actions. Sutton and Barto provide an excellent conceptual exposition of RL
theory and application [23].

The system at time $t$ is described by state $s^{t}$, and the agent’s action
is denoted by $a^{t}$. We define a reward function that quantifies the agent’s
performance, $r(s^{t},a^{t})$. The objective is to refine a policy
$\pi_{\theta}$ that maximizes the expected cumulative reward of the trajectory
$\tau=((s^{1},a^{1}),...,(s^{t},a^{t}))$:

$J(\tau)=\sum_{t=1}^{\infty}\gamma^{t}r(s^{t},a^{t})$ (10)

where $\gamma$ represents a “discount factor” that priorities near-term gains
over future and less certain events. We also introduce the value function:

$V(s^{t})=\mathbb{E}_{a\sim\pi_{\theta}}[\sum_{i=t}^{\infty}\gamma^{i}r(a^{i},s^{i})]$
(11)

The value function $V(s^{t})$ represents the expected cumulative reward,
starting from state $s^{t}$ until $t\rightarrow\infty$, under policy $\pi$.
The value function satisfies Bellman’s Equation, where $s^{t+1}$ is the state
at $t+1$ time step:

$V(s^{t})=\mathbb{E}_{a^{t}\sim\pi_{\theta}}[r(a^{t},s^{t})+\gamma
V(s^{t+1})]$ (12)

The Actor-Critic algorithm estimates the value function from data. To compute
these estimates, we utilize Bellman’s equation as a regression model. Namely,
we define the temporal difference $\delta$ [24] as:

$\delta^{t}=r(a^{t},s^{t})+\gamma V(s^{t+1})-V(s^{t})$ (13)

The Actor-Critic algorithm involves an “actor” that runs the policy
$\pi_{\theta}$ with parameters $\theta$, and the “Critic” which is an estimate
of the value function $V_{\omega}$ with parameters $\omega$.

The Supervised Actor-Critic algorithm is similar to AC, with the addition of a
“supervisor” policy that also proposes an action. The final action applied is
a combination of the supervisor’s and the Actor’s action. Introduced by
Rosenstein and Barto [25], the SAC is implemented as follows:

Initialization: We initialize the parameters of the Actor and the Critic,
respectively $\theta$ and $\omega$.

The Actor’s parameters are first updated with the difference between the
policy action $a_{A}^{t}$ and the supervisor action $a_{S}^{t}$ by one step of
stochastic gradient descent on the following optimization problem:

$\min_{\theta}\left\\{F_{a}(a_{A}^{t},a_{S}^{t})=\frac{1}{2}\|a_{A}^{t}-a_{S}^{t}\|^{2}\right\\}$
(14)

Then the combined action is chosen using the risk parameter $k$, where
$a_{E}^{t}\sim\mathcal{N}(0,\sigma)$ is an exploration term:

$a^{t}=(1-k)(a_{A}^{t}+a_{E}^{t})+ka_{S}^{t}$ (15)

Critic and Actor Updates: The Critic and the Actor’s parameters are then
updated using Temporal Difference and Bellman’s Principle of Optimality
equation with the updated value function. To update the critic, we again run
one step of stochastic gradient descent on the following optimization
problems:

$\min_{\omega}\left\\{F_{c}(\delta^{t})=\frac{1}{2}\|\delta^{t}\|^{2}\right\\}$
(16)

Finally, we update the parameters of the Actor in order to increase the value
function. The update is based on Bellman’s principle of optimality:

$\theta\leftarrow\arg\max_{\theta}\mathbb{E}_{a^{t}\sim\pi_{\theta}}[r(a^{t},s^{t})+\gamma
V(s^{t+1})]$ (17)

In practice (17) is computed using the Policy Gradient Theorem with
“baseline”, detailed by Sutton and Barto [23]. The “baseline” here is an
estimate of the value function given by the Critic. The update is the
following:

$\theta\leftarrow\theta+\beta_{2}\delta^{t}\nabla_{\theta}\ln{\pi_{\theta}(s^{t})}$
(18)

Algorithm 1 details the implementation of the Supervised Actor-Critic.

Algorithm 1 Supervised Actor-Critic

Inputs

$V_{\omega}(s)$, Critic value function parameterized by $\omega$

$\pi^{A}_{\theta}$, Actor policy parameterized by $\theta$

$\pi^{S}$, supervisor policy

$\sigma$, exploration factor

$\alpha$, Critic step size

$\beta_{1}$ and $\beta_{2}$, Actor step size

$\gamma\in[0,1]$, discount factor

initialize $\theta,\omega$ randomly

initialize $s\leftarrow$ starting state

repeat for each time step, $t$

$a^{A}\leftarrow$ action given by $\pi^{A}_{\theta}(s)$

$a^{S}\leftarrow$ action given by a supervisor policy $\pi^{S}(s)$

$\theta\leftarrow\theta+\beta_{1}\nabla_{\theta}F_{a}(a^{A},a^{S})$

$a^{E}\sim\mathcal{N}(0,\sigma)$

$a\leftarrow(1-k)(a^{A}+a^{E})+ka^{S}$

if $a$ is not safe then

$a\leftarrow a^{S}$

end if

take action $a$, observe reward, $r$, and next state, $s^{\prime}$

$\delta\leftarrow r+\gamma V(s^{\prime})-V(s)$

$\theta\leftarrow\theta+\beta_{2}\delta^{t}\nabla_{\theta}\ln{\pi_{\theta}(s^{t})}$

$\omega\leftarrow\omega+\alpha\nabla_{\omega}F_{c}(\delta)$

$s\leftarrow s^{\prime}$

Update $k\in[0,1]$

until terminal state reached

The SAC algorithm allows the bidding algorithm to train online while
satisfying physical and market constraints during exploration. When the RL
agent yields higher rewards than MPC, then the coefficient $k$ can be changed
from $k=0$ toward $k=0.5$ to progressively weight in favor of the RL agent’s
bid.

To implement this algorithm within our environment, we specify the state, the
action, and the reward formulation as follows.

The environment or system (i.e. the storage system and market) has the
following state: $t_{day}$ is the time step of the day, $\lambda$ is a price
either estimated, $\hat{\lambda}$, or exactly known, ${\lambda}$, and
$\hat{d}_{up}$ is the estimated demand for the market. In math,
$s^{t}=\left[\hat{\lambda^{t}},\lambda^{t-1},soe^{t},t_{day},\hat{d}^{t}\right]$.

The action is composed of the energy market bid at time $t$. A bid has the
following structure: $a^{t}=\\{\lambda^{t},p_{g}^{t}-p_{l}^{t}\\}$.

In order to propose safe actions (actions that lead to a feasible state) while
learning, we transform our reward function using a Lagrangian with predefined
Lagrange multipliers. This is equivalent to adding penalty terms to the
reward. The reward function is as follows:

$\begin{split}r(a^{t},s^{t})=&\hat{\lambda}^{t}(p^{t}_{g}-p^{t}_{l})+\mu^{T}\mathcal{Y}(a^{t},s^{t})\end{split}$
(19)

where $\mathcal{Y}(a^{t},s^{t})$ refers to constraints (5) - (9) listed in the
MPC formulation, and $\mu$ serves as weights to penalize constraints
violations.

##  IV Experiment and Results

###  IV-A Experimental Settings

We run the simulation using electricity demand data from the Australian
electricity market, also known as AEMO (Australian Energy Market Operator)
[26]. The simulation is run over 5 months: June to October 2018. The other
players are simulated as deterministic agents bidding a fixed quantity at a
fixed marginal cost.

The parameters used for the supervised Actor-Critic are:

TABLE I: SAC Parameters Parameters | Values
---|---
$\gamma$ discount factor | 0.98
optimizer | Adagrad [27]
learning rate | $10^{-4}$
hidden layers | 6
Activation function | Leaky Relu
exploration $\sigma$ | 1

We set $k=0$ for the first 400 steps in order to select the supervisor’s
action while the Actor-Critic agent is training. We then progressively
increase the value of $k$ until it reaches 0.5. The update of $k$ is shown in
Fig. 3.

Figure 3: Risk Factor Update

The battery is designed with a capacity of 1029 MWh and a maximum capacity of
300 MWh. Those number are unrealistic but in order to simulate the behavior of
a price-taker on the energy market we had to increase the battery capacity to
create market power. We remind that batteries are price-maker on smaller
markets as ancillary services markets. The charging and discharging efficiency
rate are set to 1 for simplicity. When the battery behaves as a load, its bid
is added directly to the total load of the grid. As a generator the battery
bid is submitted to the clearing process described in Section II.

###  IV-B Results

First, we evaluate that the MPC is behaving correctly, i.e. buying electricity
at low price and selling at higher price. Figure 4 plots the simulation result
over two days. The bar plot in the above figure represents the generation and
load bids capacity that were cleared by the market. The black line is the
cleared price and the green line is the battery’s bidding price. The MPC bids
as a generator when prices are high and as a load when prices are low. An
interesting observation is that the MPC algorithm bids at the clearing price
when behaving as a generator. That is, the battery plays the role of the
orange bid in Fig. 1. In this case, the market cannot clear the entire
capacity bid since this is the marginal bid. As a consequence the battery is
not discharging as much capacity as predicted by the MPC, this is the main
source of loss for the MPC algorithm. Another observation is that when the
battery behaves as a load, it increases the demand and consequently increases
the prices due to the price-maker condition occurring.

In addition to showing the expected behavior, Fig. 4 highlights the impact of
the battery’s bids on the market: Our system is a price-maker on this market.

We then apply the SAC algorithm to the same simulation. Our claim is that the
SAC algorithm would recognize the battery’s impact on the electricity market,
and adapt. As a result, it is interesting but expected to see that the
clearing price distribution varies depending on the bidding algorithm, as
shown in Fig. 5.

Figure 4: MPC strategy over two days of the simulation Figure 5: Market
Clearing Price Distribution for MPC and SAC

To compare the SAC with the MPC algorithm, we compute in Table II the total
revenue earned by the two algorithms. The SAC significantly outperforms the
MPC algorithm by earning over 3.5 times more revenue on average. In Fig. 6 we
can see the cumulative revenue increasing at a much faster rate after the
increase of $k$ over the time.

The SAC proves to be a safe algorithm: only $6\%$ of the bids are charging or
discharging the battery above limits. Fortunately our system is built with a
shield that blocs those actions.

To understand the behavioral differences between the two algorithms we plot
the distribution of the battery state of energy in Fig. 7, as well as the
distribution of capacity bids in Fig. 8. The state of energy is varying across
the entire range of possible values with SAC, taking full advantage of the
battery’s energy capacity. With MPC, the battery discharges less energy on the
grid. This observation is related to the conclusion made on Fig. 4. Namely,
the battery clears at the market clearing price and thus does not clear the
entire capacity bid. We observe that the SAC algorithm solves this problem by
recognizing the lower cleared quantity, and consequently adjusts the bid. This
results in using the entire range of the battery capacity which leads to a
significantly higher revenue.

TABLE II: Bidding Strategies | SAC | MPC
---|---|---
Average revenue per day | 599 $/day | 175 $/day
Average % of bids capacity cleared | 80% | 15%
Violations of battery capacity before shield | 6 % | 0 %
% of Generator bids | 66 % | 63 %
Figure 6: Cumulative Revenue for MPC and SAC Figure 7: Battery State of Energy
Distribution for MPC and SAC Figure 8: Generation and Load Bids for MPC and
SAC

Yielding higher revenue charging and discharging cycles of the battery
requires that the SAC generates more strategic bids. In Fig. 8 we compare the
distribution of capacity bids between the two algorithms. The MPC constantly
bids as a generator at a capacity of 300 MWh, which is the maximum. This
strategy is normal since the battery is most of the time at high state of
energy and thus can discharge at maximum rate. The SAC strategy cannot bid
more than the battery capacity allows, which yields a broad distribution in
Fig. 7. Another interesting behavior to point out is that the SAC generated
load bids that are lower than MPC. However the load bids behave like an
additional demand for the market and thus increases the clearing price a
significant amount as seen in Fig. 4. Recall that the battery pays the market
the clearing price when it operates as a load. The SAC recognizes that when
the battery operates as a load, it inflates prices. Consequently, the SAC
algorithm has lower capacity bids as to not inflate instantaneous costs.

##  V Conclusion

Learning-based methods are particularly well suited to answer the need for
optimal bidding algorithms. Indeed, markets have always been complex to model
as they are multi-player and dynamic systems, but are necessary to understand
when one player’s bid impacts the clearing process, or when an ISO experiments
with new market designs. For this reason, model-free or learning-based
algorithms such as DRL are an appealing option. Those algorithms do not
require a complete model of the system, and can adapt their actions in
response to observed impacts on the system. DRL has proven its efficiency for
controlling robots, playing video games, and targeting web content, but is
rarely applied in energy systems. The main reason is because those algorithms
learn through trial and error, and error can have dangerous consequences in
real-world energy systems. Designing simulations to train these algorithms
raises a paradox: if we can build a model of the environment, then why use a
model-free algorithm?

To use DRL in real-world energy system, we must overcome the danger of
training the algorithm. Techniques like developing shields to limit dangerous
actions, adding penalty terms to the reward function, or using supervisors to
reduce the search in the action space have the potential to solve this issue.

In this paper, we develop a Supervised Actor-Critic algorithm to optimally bid
the energy of a price-maker grid-scale battery on the electricity market. In
addition, we use a shield as well as a penalty term in the reward to avoid
dangerous actions.

The results show that those techniques improve bidding performance relative to
the baseline price-taker algorithm, while ensuring safety during algorithm
training.

This first approach is experimental, and developing those techniques at an
industrial level would require more theoretical work on the action space
reduction and the effect of a shield. Moreover, future work could study the
reaction of the SAC to a market with dynamic and multiple price-maker players.

## References

  * [1] J. P. Barton and D. G. Infield, “Energy storage and its use with intermittent renewable energy,” _IEEE Transactions on Energy Conversion_ , vol. 19, no. 2, pp. 441–448, 2004.
  * [2] J. M. Carrasco, L. G. Franquelo, J. T. Bialasiewicz, E. Galvan, R. C. PortilloGuisado, M. A. M. Prats, J. I. Leon, and N. Moreno-Alfonso, “Power-electronic systems for the grid integration of renewable energy sources: A survey,” _IEEE Transactions on Industrial Electronics_ , vol. 53, no. 4, pp. 1002–1016, 2006.
  * [3] J. A. Taylor, D. S. Callaway, and K. Poolla, “Competitive energy storage in the presence of renewables,” _IEEE Transactions on Power Systems_ , vol. 28, no. 2, pp. 985–996, 2013.
  * [4] EIA, “Battery storage in the united states: An update on market trends,” _U.S. Energy Information Administration_ , 2020. [Online]. Available: https://www.eia.gov/analysis/studies/electricity/batterystorage/
  * [5] Bolun Xu, Y. Dvorkin, D. S. Kirschen, C. A. Silva-Monroy, and J. Watson, “A comparison of policies on the participation of storage in u.s. frequency regulation markets,” in _2016 IEEE Power and Energy Society General Meeting (PESGM)_ , 2016, pp. 1–5.
  * [6] M. Kintner-Meyer, “Regulatory policy and markets for energy storage in north america,” _Proceedings of the IEEE_ , vol. 102, no. 7, pp. 1065–1072, 2014\.
  * [7] J.-P. Harreman. (2019) Europe’s changing fcr auctions and their impact on the energy storage industry. [Online]. Available: https://www.energy-storage.news/blogs/europes-changing-frequency-control-reserve-auctions-and-their-impact-on-the
  * [8] G. Steeger, L. A. Barroso, and S. Rebennack, “Optimal bidding strategies for hydro-electric producers: A literature survey,” _IEEE Transactions on Power Systems_ , vol. 29, no. 4, pp. 1758–1766, 2014.
  * [9] S. Borenstein. (2000) Understanding competitive pricing and market power in wholesale electricity markets. [Online]. Available: http://faculty.haas.berkeley.edu/borenste/mba212/ElecJo00MktPower.pdf
  * [10] S. Vorrath and G. Parkinson. (2018) The stunning numbers behind success of tesla big battery. [Online]. Available: https://reneweconomy.com.au/the-stunning-numbers-behind-success-of-tesla-big-battery-63917/
  * [11] M. Petkovic. (2019) Tesla big battery at hornsdale earns record revenue in september 2019. [Online]. Available: https://reneweconomy.com.au/tesla-big-battery-at-hornsdale-earns-record-revenue-in-september-2019/
  * [12] S. S. Oren and M. H. Rothkopfn, “Optimal bidding in sequential auctions,” _Operations Research_ , vol. 23, no. 6, pp. 1045–1191, 1975.
  * [13] R. H. Kwon and D. Frances, _Optimization-Based Bidding in Day-Ahead Electricity Auction Markets: A Review of Models for Power Producers_. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 41–59.
  * [14] S. E. Vazquez, P. Rodilla, and C. A. M. Batlle, “Residual demand models for strategic bidding in european power exchanges : revisiting the methodology in the presence of a large penetration of renewables,” _Electric Power Systems Research_ , vol. 108, pp. 178–184, 2014.
  * [15] J. Arteaga and H. Zareipour, “A price-maker/price-taker model for the operation of battery storage systems in electricity markets,” _IEEE Transactions on Smart Grid_ , vol. 10, pp. 6912–6920, 11 2019.
  * [16] E. Tomasson, M. Hesamzadeh, and F. Wolak, “Optimal offer-bid strategy of an energy storage portfolio: A linear quasi-relaxation approach,” _Applied Energy_ , vol. 260, p. 114251, 02 2020.
  * [17] Y. Ye, D. Qiu, M. Sun, D. Papadaskalopoulos, and G. Strbac, “Deep reinforcement learning for strategic bidding in electricity markets,” _IEEE Transactions on Smart Grid_ , vol. 11, pp. 1343–1355, 3 2020.
  * [18] M. Glavic, R. Fonteneau, and D. Ernst, “Reinforcement learning for electric power system decision and control: Past considerations and perspectives,” _IFAC-PapersOnLine_ , vol. 50, no. 1, pp. 6918–6927, 2017, 20th IFAC World Congress. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S2405896317317238
  * [19] Z. Zhang, D. Zhang, and R. C. Qiu, “Deep reinforcement learning for power system applications: An overview,” _CSEE Journal of Power and Energy Systems_ , vol. 6, no. 1, pp. 213–225, 2020.
  * [20] G. R. Gajjar, S. A. Khaparde, P. Nagaraju, and S. A. Soman, “Application of actor-critic learning algorithm for optimal bidding problem of a genco,” _IEEE Transactions on Power Systems_ , vol. 18, no. 1, pp. 11–18, 2003.
  * [21] A. Akbari-Dibavar, B. Mohammadi-Ivatloo, and K. Zare, “Electricity market pricing: Uniform pricing vs. pay-as-bid pricing,” _Proceedings of the IEEE_ , pp. 19–35, 2020. [Online]. Available: https://doi.org/10.1007/978-3-030-36979-8_2
  * [22] A. Berrada, K. Loudiyi, and I. Zorkani, “Valuation of energy storage in energy and regulation markets,” _Energy_ , vol. 115, pp. 1109 – 1118, 2016. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0360544216313639
  * [23] R. S. Sutton and A. G. Barto, _Introduction to Reinforcement Learning, Second Edition_. MIT Press, 2018.
  * [24] R. S. Sutton, “Learning to predict by the methods of temporal differences,” _Machine Learning_ , vol. 3, no. 1, pp. 9–44, 1988. [Online]. Available: https://doi.org/10.1007/BF00115009
  * [25] M. Rosenstein and A. Barto, “Supervised learning combined with an actor-critic architecture,” _ACM Sigevolution_ , 2002.
  * [26] Aemo market data nemweb. [Online]. Available: http://nemweb.com.au/
  * [27] J. D. JDUCHI and Y. Singer, “Adaptive subgradient methods for online learning and stochastic optimization * elad hazan,” _Journal of Machine Learning Research_ , vol. 12, pp. 2121–2159, 2011.


# CesASMe and Staticdeps: static detection of memory-carried dependencies for
code analyzers

Théophile Bastian  Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000
Grenoble, France<EMAIL_ADDRESS>,  Hugo Pompougnac  Univ. Grenoble
Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France
<EMAIL_ADDRESS>,  Alban Dutilleul  ENS RennesFrance
<EMAIL_ADDRESS>and  Fabrice Rastello  Univ. Grenoble Alpes,
Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France
<EMAIL_ADDRESS>
###### Abstract.

A variety of code analyzers, such as IACA, uiCA, llvm-mca or Ithemal, strive
to statically predict the throughput of a computation kernel. Each analyzer is
based on its own simplified CPU model reasoning at the scale of a basic block.
Facing this diversity, evaluating their strengths and weaknesses is important
to guide both their usage and their enhancement.

We present CesASMe, a fully-tooled solution to evaluate code analyzers on
C-level benchmarks composed of a benchmark derivation procedure that feeds an
evaluation harness. We conclude that memory-carried data dependencies are a
major source of imprecision for these tools. We tackle this issue with
staticdeps, a static analyzer extracting memory-carried data dependencies,
including across loop iterations, from an assembly basic block. We integrate
its output to uiCA, a state-of-the-art code analyzer, to evaluate staticdeps’
impact on a code analyzer’s precision through CesASMe.

##  1\. Introduction

At a time when software is expected to perform more computations, faster and
in more constrained environments, tools that statically predict the resources
they consume are very useful to guide optimizations. This need is reflected in
the diversity of binary or assembly code analyzers that appeared following the
deprecation of IACA (Intel Corporation, [n. d.]), which Intel has maintained
through 2019. Whether it is llvm-mca (Sony Corporation and LLVM Project, [n.
d.]), uiCA (Abel and Reineke, 2022), Ithemal (Mendis et al., 2018) or Gus
(Gruber, 2019), all these tools strive to produce various performance metrics,
including the number of CPU cycles a computation kernel will take — which
roughly translates to execution time. In addition to raw measurements relying
on hardware counters, these model-based analyses provide higher-level and
refined data, to expose the bottlenecks and guide the optimization of a given
code. This feedback is useful to experts optimizing computation kernels,
including scientific simulations and deep-learning kernels.

An exact throughput prediction would require a cycle-accurate simulator of the
processor such as gem5 (Binkert et al., 2011), but would also require
microarchitectural data that is most often not publicly available, and would
be prohibitively slow in any case. These tools thus each solve in their own
way the challenge of modeling complex CPUs while remaining simple enough to
yield a prediction in a reasonable time, ending up with different models.

In particular, previous works (eg. AnICA (Ritter and Hack, 2022)) have exposed
significant discrepancies in the reported predictions for programs with
memory-carried dependencies. This is a clue of a more general limitation of
current code analyzers, which leads to the hypothesis that the underlying
performance models have trouble with memory dependencies modelization. One way
to verify this is to provide an alternative analysis method and be able to
show that it produces more accurate predictions. Such an approach will also
need an evaluation framework sound enough to trustworthy compare one method
with another.

###  1.1. Contributions

We present a new method to construct sound baselines against which to compare
the predictions of code analyzers, in order to evaluate the performance models
underlying the latter. Indeed, existing approaches lack such a baseline and
often require ad hoc, handmade supplementary analysis. Some evaluate the
results of a code analyzer by comparing it to those of another code analyzer
(eg. AnICA), while others perform actual measurements, but on — possibly
randomly-generated — basic blocks isolated from their context, eg. using BHive
(Chen et al., 2019).

By comparison, our approach, which is materialized in a tool called CesASMe,
consists in generating various (L1-resident, code analyzers-compliant)
microbenchmarks from an existing benchmark suite, and then using them without
isolating their constituent basic blocks to evaluate code analyzers. To do so,
CesASMe applies static analyses on their constituent basic blocks. At the same
time, it executes the microbenchmarks and performs hardware counters-based
measurements. It finally aggregates measurements and analyses in such a way as
to make them commensurable.

We also provide a new heuristic called staticdeps to extract memory-carried
dependencies. We use this heuristic with CesASMe to test the hypothesis
mentioned above that current code analyzers struggle to model the latter. We
show that this approach significantly improves the accuracy of the code
analyzer uiCA(Abel and Reineke, 2022), which is tantamount to showing that
dependencies constitute a significant limitation of its underlying model. We
also show that the resulting extended analyzer fully outperforms the state of
the art.

###  1.2. Related works

The static throughput analyzers studied rely on a variety of models. IACA
(Intel Corporation, [n. d.]), developed by Intel and now deprecated, is
closed-source and relies on Intel’s expertise on their own processors. The
LLVM compiling ecosystem, to guide optimization passes, maintains models of
many architectures. These models are used in the LLVM Machine Code Analyzer,
llvm-mca (Sony Corporation and LLVM Project, [n. d.]), to statically evaluate
the performance of a segment of assembly. Independently, Abel and Reineke used
an automated microbenchmark generation approach to generate port mappings of
many architectures in uops.info (Abel and Reineke, 2019a, b) to model
processors’ backends. This work was continued with uiCA (Abel and Reineke,
2022), extending this model with an extensive frontend description. Following
a completely different approach, Ithemal (Mendis et al., 2018) uses a deep
neural network to predict basic blocks throughput. To obtain enough data to
train its model, the authors also developed BHive (Chen et al., 2019), a
profiling tool working on isolated basic blocks.

Another static tool, Osaca (Laukemann et al., 2019), provides lower- and
upper-bounds to the execution time of a basic block. As this kind of
information cannot be fairly compared with tools yielding an exact throughput
prediction, we exclude it from our scope.

All these tools statically predict the number of cycles taken by a piece of
assembly or binary that is assumed to be the body of an infinite — or
sufficiently large — loop in steady state, all its data being L1-resident. As
discussed by uiCA’s authors (Abel and Reineke, 2022), hypotheses can subtly
vary between analyzers; eg. by assuming that the loop is either unrolled or
has control instructions, with non-negligible impact. Some of the tools, eg.
Ithemal, necessarily work on a single basic block, while some others, eg.
IACA, work on a section of code delimited by markers. However, even in the
second case, the code is assumed to be _straight-line code_ : branch
instructions, if any, are assumed not taken.

Throughput prediction tools, however, are not all static. Gus (Gruber, 2019)
dynamically predicts the throughput of a whole program region, instrumenting
it to retrieve the exact events occurring through its execution. This way, Gus
can detect bottlenecks more finely through sensitivity analysis, at the cost
of a significantly longer run time.

The BHive profiler (Chen et al., 2019) takes another approach by performing
basic block throughput measurement instead of analysis: by mapping memory at
any address accessed by a basic block, it can effectively run and measure
arbitrary code without context, often — but not always, as we discuss later —
yielding good results as one would expect from an actual measurement.

The AnICA framework (Ritter and Hack, 2022) also attempts to evaluate
throughput predictors by finding examples on which they are inaccurate. AnICA
starts with randomly generated assembly snippets, and refines them through a
process derived from abstract interpretation to reach general categories of
problems.

##  2\. Benchmarking harness

The obvious solution to evaluate predictions is to compare them to an actual
measure. However, as these tools reason at the basic block level, this is not
as trivially defined as it would seem, especially when it comes to showing the
impact of dependencies. As detailed later in Section 2.6, _without proper
context, a basic block’s throughput is not well-defined_.

To recover the context of each basic block, we reason instead at the scale of
a C source code. This makes the measures unambiguous: one can use hardware
counters to measure the elapsed cycles during a loop nest. This requires a
suite of benchmarks, in C, that both is representative of the domain studied,
and wide enough to have a good coverage of the domain. However, this is not in
itself sufficient to evaluate static tools: the number of cycles reported by
the counters can be the result of an arbitrarily large number of loop turns,
with conditional branches taken or not. This number hardly compares to llvm-
mca, IACA, Ithemal, and uiCA basic block-level predictions seen above that
only predict throughput of individual basic block.

ptBenchmark suiteLoop nest optimizersMicrokernel extractionCompilationsBasic
block extraction [2.2]IthemalIACAuiCAllvm-mcaBHive (measure)perf
(measure)GusPrediction lifting[2.4]Throughput predictions & measures
[2.3]Transformations [2.1]Evaluation metrics for code analyzersGenerating
microbenchmarksBenchmarking harnessResults analysis

Figure 1. Our analysis and measurement environment.

#### Predictions lifting.

We developed a basic block occurences counter to count the number of
occurrences of a basic block during kernel execution. Then, we use this number
of occurrences to weight basic block throughput predictions. Finally, we lift
code analyzers’ results by summing the weighted basic block predictions:

(1)
$\displaystyle\text{lifted\\_pred}(\mathcal{K})=\sum_{b\in\operatorname{BBs}(\mathcal{K})}\operatorname{occurences}(b)\times\operatorname{pred}(b)$

#### Architecture of our benchmarking harness.

Our benchmarking framework works in four successive stages, whose a high-level
view is shown in Figure 1. It first generates relevant microbenchmarks (ie.
L1-resident benchmarks) by applying a series of transformations to an existing
benchmark suite which is, in our case, the HPC-native Polybench (Pouchet and
Yuki, 2016) suite. It then extracts the basic blocks constituting a
computation kernel, and instruments it to retrieve their respective
occurrences in the original context. It runs all the studied tools on each
basic block, while also running measures on the whole computation kernel.
Finally, the block-level results are lifted to kernel-level results thanks to
the occurrences previously measured.

###  2.1. Generating microbenchmarks

The first stage of our benchmarking harness consists in generating a set of
microbenchmarks. We extend AnICA’s random-based approach mentioned above in
order to produce microbenchmarks diverse enough, but related to real-life
kernels. Thus, our approach consists in applying several transformations to an
existing benchmark suite:

  1. (1)

We produce several versions of each benchmark using loop nest optimizers
(Pluto(Bondhugula et al., 2007) and PoCC (PoCC, [n. d.])). The latter gives
access to a wide variety of transformations: register tiling, tiling, skewing,
vectorization/simdization, loop unrolling, loop permutation, loop fusion and
so on.

  2. (2)

We instrument the resulting code in order to extract the loop which has the
greatest impact on performance while being L1-resident. This microkernel is
isolated from the initial benchmark, and incorporated into a parameterized
template where requested behaviors, as the number of successive measurements,
are set. We call this refined benchmark a microbenchmark.

  3. (3)

Given a microbenchmark, we produce several binaries by applying different
compilation strategies (enabling/disabling auto-vectorization, extended
instruction sets, etc.).

This pipeline allows us to produce a diversified yet domain-specific range of
microbenchmarks.

###  2.2. Basic block extraction

Given a compiled microbenchmark, we use the Capstone disassembler (Quynh and
the Capstone collaborators, [n. d.]), and split the assembly code at each
control flow instruction (jump, call, return, …) and each jump site.

To accurately obtain the occurrences of each basic block in the whole kernel’s
computation, we then instrument it with gdb by placing a break point at each
basic block’s first instruction in order to count the occurrences of each
basic block between two calls to the perf counters111We assume the program
under analysis to be deterministic..

###  2.3. Throughput predictions and measures

The harness leverages a variety of tools: actual CPU measurement; the BHive
basic block profiler (Chen et al., 2019); llvm-mca (Sony Corporation and LLVM
Project, [n. d.]), uiCA (Abel and Reineke, 2022) and IACA (Intel Corporation,
[n. d.]), which leverage microarchitectural models to predict a block’s
throughput; Ithemal (Mendis et al., 2018), a machine learning model; and Gus
(Gruber, 2019), a dynamic analyzer based on QEmu that works at the whole
binary level.

The execution time of the full kernel is measured using Linux perf (Linux
Kernel, [n. d.]) CPU counters around the full computation kernel. The measure
is repeated four times and the smallest is kept; as the caches are not
flushed, this ensures that the cache is warm and compensates for context
switching or other measurement artifacts. Gus instruments the whole function
body. The other tools work at basic block level; these are run on each basic
block of each benchmark.

We emphasize the importance, throughout the whole evaluation chain, to keep
the exact same assembled binary. Indeed, recompiling the kernel from source
_cannot_ be assumed to produce the same assembly kernel. This is even more
important in the presence of slight changes: for instance, inserting IACA
markers at the C-level — as is intended — around the kernel _might_ change the
compiled kernel, if only for alignment reasons. Furthermore, those markers
prevent a binary from being run by overwriting registers with arbitrary
values. This forces a user to run and measure a version which is different
from the analyzed one. In our harness, we circumvent this issue by adding
markers directly at the assembly (already compiled) basic block level. Our gdb
instrumentation procedure also respects this principle of single-compilation.
As QEmu breaks the perf interface, we have to run Gus with a preloaded stub
shared library to be able to instrument binaries containing calls to perf.

###  2.4. Prediction lifting and filtering

We finally lift single basic block predictions to a whole-kernel cycle
prediction by summing the block-level results, weighted by the occurrences of
the basic block in the original context (Equation 1 above). If an analyzer
fails on one of the basic blocks of a benchmark, the whole benchmark is
discarded for this analyzer.

Finally, we control the proportion of cache misses in the program’s execution
using Cachegrind (Nethercote and Seward, 2003) and Gus; programs that have
more than 15 % of cache misses on a warm cache are not considered L1-resident
and are discarded.

###  2.5. Soundness of CesASMe’s methodology

Given a time prediction $C_{\text{pred}}$ (in cycles) and a baseline
$C_{\text{baseline}}$, we define its relative error as

(2)
$\displaystyle\operatorname{err}=\frac{\left|C_{\text{pred}}-C_{\text{baseline}}\right|}{C_{\text{baseline}}}$

We assess the commensurability of the whole benchmark, measured with perf, to
lifted block-based results by measuring the statistical distribution of the
relative error of two series: the predictions made by BHive, and the series of
the best block-based prediction for each benchmark.

We single out BHive as it is the only tool able to measure — instead of
predicting — an isolated basic block’s timing. Since BHive is based on
measures — instead of predictions — through hardware counters, an excellent
accuracy is expected. This, however, is not sufficient: as discussed later in
Section 2.6, BHive is not able to yield a result for about $40\,\%$ of the
benchmarks, and is subject to large errors in some cases.

The result of this analysis is presented in Table 1 and in Figure 2. The
results are in a range compatible with common results of the field, as seen
eg. in (Abel and Reineke, 2022) reporting Mean Absolute Percentage Error
(MAPE, corresponding to the “Average” row) of about 10-15 % in many cases.
While lifted BHive’s average error is driven high by large errors on certain
benchmarks, investigated later in this article, its median error is still
comparable to the errors of state-of-the-art tools. From this, we conclude
that lifted cycle measures and predictions are consistent with whole-benchmark
measures; and consequently, lifted predictions can reasonably be compared to
one another.

Figure 2. Relative error distribution wrt. perf | Best block-based | BHive
---|---|---
Datapoints | 3500 | 2198
Errors | 0 | 1302
| (0 %) | (37.20 %)
Average (%) | 11.60 | 27.95
Median (%) | 5.81 | 7.78
Q1 (%) | 1.99 | 3.01
Q3 (%) | 15.41 | 23.01
Table 1. Relative error statistics wrt. perf

###  2.6. Understanding BHive’s results

The error distribution of BHive against perf, plotted right in Figure 2, puts
forward irregularities in BHive’s results. Its lack of support for control
flow instructions can be held accountable for a portion of this accuracy drop;
our lifting method, based on block occurrences instead of paths, can explain
another portion. We also find that BHive fails to produce a result in about 40
% of the kernels explored — which means that, for those cases, BHive failed to
produce a result on at least one of the constituent basic blocks. In fact,
this is due to the need to reconstruct the context of each basic block ex
nihilo.

The basis of BHive’s method is to run the code to be measured, unrolled a
number of times depending on the code size, with all memory pages but the code
unmapped. As the code tries to access memory, it will raise segfaults, caught
by BHive’s harness, which allocates a single shared-memory page, filled with a
repeated constant, that it will map wherever segfaults occur before restarting
the program. BHive mainly fails on bad code behaviour (eg. control flow not
reaching the exit point of the measure if a bad jump is inserted), too many
segfaults to be handled, or a segfault that occurs even after mapping a page
at the problematic address.

The registers are also initialized, at the beginning of the measurement, to
the fixed constant 0x2324000. We show through two examples that this initial
value can be of crucial importance.

The following experiments are executed on an Intel(R) Xeon(R) Gold 6230R CPU
(Cascade Lake), with hyperthreading disabled.

#### Imprecise analysis

Consider this x86-64 kernel:

⬇

vmulsd (%rax), %xmm3, %xmm0

vmovsd %xmm0, (%r10)

When executed with all the general purpose registers initialized to the
default constant, BHive reports 9 cycles per iteration, since %rax and %r10
hold the same value, inducing a read-after-write dependency between the two
instructions. If, however, BHive is tweaked to initialize %r10 to a value that
aliases (wrt. physical addresses) with the value in %rax, eg. between 0x10000
and 0x10007 (inclusive), it reports 19 cycles per iteration instead; while a
value between 0x10008 and 0x1009f (inclusive) yields the expected 1 cycle —
except for values in 0x10039-0x1003f and 0x10079-0x1007f, yielding 2 cycles as
the store crosses a cache line boundary.

In the same way, the value used to initialize the shared memory page can
influence the results whenever it gets loaded into registers.

#### Failed analysis

Some memory accesses will always result in an error; for instance, it is
impossible (by default) to mmap at an address lower than 0x10000. Thus, with
equal initial values for all registers, the following kernel would fail, since
the second operation attempts to load at address 0:

⬇

subq %r11, %r10

movq (%r10), %rax

Such errors can occur in more circumvoluted ways. The following x86-64 kernel,
for instance, is extracted from a version of the durbin kernel:

⬇

vmovsd 0x10(%r8, %rcx), %xmm6

subl %eax, %esi

movslq %esi, %rsi

vfmadd231sd -8(%r9, %rsi, 8), \

%xmm6, %xmm0

Here, BHive fails to measure the kernel when run with registers initialized to
the default constant at the 2nd occurrence of the unrolled loop body, failing
to recover from an error at the vfmadd231sd instruction with the mmap
strategy. Indeed, after the first iteration the value in %rsi becomes null,
then negative at the second iteration; thus, the second occurrence of the last
instruction fetches at address 0xfffffffff0a03ff8, which is in kernel space.
This microkernel can be benchmarked with BHive eg. by initializing %rax to 1.
Furthermore, on most 64-bits CPUs, addresses are only valid if they are
representable on 48 bits (correctly sign-extended to fill 64 bits) (Intel
Corporation, 2023; AMD, 2023), called _canonical form_ , causing further
failures in BHive. Other kernels still fail with accesses relative to the
instruction pointer, as BHive read-protects the unrolled microkernel’s
instructions page.

##  3\. Static extraction of memory-carried dependencies

As put forwards by AnICA (Ritter and Hack, 2022), memory-carried dependencies
are a difficult challenge for code analyzers. This is further confirmed by the
results of CesASMe, presented in Section 4.3.

To this end, we present staticdeps, a heuristic-based static assembly analyzer
able to extract most of the memory-carried dependencies that are relevant from
a latency analysis perspective. It operates at the basic-block level, and
tracks dependencies across arbitrarily complex pointer arithmetic, through
arbitrarily many loop iterations.

Working at the basic-block level, it is however lacking context, as we argued
earlier; as such, it cannot detect aliasing stemming from outside of the loop.

###  3.1. Relevance of memory dependencies in hardware

Modern Out-of-Order (OoO) hardware has dedicated significant architectural
resources to maximize the pipeline usage. One such key component is the
reorder buffer (ROB) — an extension of Tomasulo’s algorithm (Tomasulo, 1967)
—, a circular buffer storing incoming $\mu$OPs, decoded and renamed from
instructions, in the frontend. When a $\mu$OP is committed, as soon as it is
no longer busy, the ROB can safely move its head pointer, freeing space for
new $\mu$OPs at its tail.

In particular, if a $\mu$OP $\mu_{1}$ is not yet committed, the ROB may not
contain $\mu$OPs more than the ROB’s size ahead of $\mu_{1}$. This is also
true for instructions, as the vast majority of instructions decode to at least
one $\mu$OP222Some mov instructions from register to register may, for
instance, only have an impact on the renamer; no $\mu$OPs are dispatched to
the backend..

Nevertheless, instruction level parallelism (ILP) might still be limited,
either by dependencies or other factors. Speculative techniques such as memory
disambiguation address that point, by for instance trying to detect whether a
given load depends on an earlier not-yet-committed store, in order to allow
safe out-of-order execution of non-dependent memory accesses. If such
speculation turns out wrong, execution is typically rolled back to before the
offending load in the ROB, incurring at least the penalty of another load.

Recent microarchitectures still lack ways of dealing with true data
dependencies, especially at the memory level, even if ongoing research with
value prediction (Perais and Seznec, 2014; Sheikh et al., 2017) tackles that
issue, but to the best of our knowledge value prediction has not yet been
implemented in products of mainstream CPU vendors.

###  3.2. Detecting different types of dependencies

Depending on their type, some dependencies are significantly harder to
statically detect than others.

Register-carried dependencies in straight-line code are easiest to detect, by
keeping track of which instruction last wrote each register in a _shadow
register file_. This is most often supported by code analyzers — for instance,
llvm-mca and uiCA support it.

Register-carried, loop-carried dependencies can, to some extent, be detected
the same way. As the basic block is always assumed to be the body of an
infinite loop, a straight-line analysis can be performed on a duplicated
kernel. This strategy is eg. adopted by Osaca (Laukemann et al., 2019)
(§II.D). When dealing only with register accesses, this strategy is always
sufficient: as each iteration always executes the same basic block, it is not
possible for an instruction to depend on another instruction two iterations
earlier or more.

Memory-carried dependencies, however, are significantly harder to tackle.
While basic heuristics can handle some simple cases, in the general case two
main difficulties arise:

  1. (i)

pointers may _alias_ , ie. point to the same address or array; for instance,
if %rax points to an array, it may be that %rbx points to $\texttt{\%rax}+8$,
making the detection of such a dependency difficult;

  2. (ii)

arbitrary arithmetic operations may be performed on pointers, possibly through
diverting paths: eg. it might be necessary to detect that
$\texttt{\%rax}+16<<2$ is identical to $\texttt{\%rax}+128/2$; this requires
semantics for assembly instructions and tracking formal expressions across
register values — and possibly even memory.

Tracking memory-carried dependencies is, to the best of our knowledge, not
done in code analyzers, or only with simple heuristics, as our results with
CesASMe suggests.

For loop-carried, memory-carried dependencies, the strategy previously used
for register-carried dependencies is not sufficient at all times when the
dependencies tracked are memory-carried, as dependencies may reach further
back than the previous iteration, eg. in a dynamic implementation of the
Fibonacci sequence.

###  3.3. The staticdeps heuristic

To statically detect memory dependencies, we use a randomized heuristic
approach. We consider the set $\mathcal{R}$ of values representable by a
64-bits unsigned integer; we extend this set to
$\overline{\mathcal{R}}=\mathcal{R}\cup\\{\bot\\}$, where $\bot$ denotes an
invalid value. We then proceed by keeping track of which instruction last
wrote each memory address written to, using the following principles.

  * •

Whenever an unknown value is read, either from a register or from memory,
generate a fresh value from $\mathcal{R}$, uniformly sampled at random. This
value is saved to a shadow register file or memory, and will be used again the
next time this same data is accessed. Note that a shadow is a data structure
that describes the original component with a given granularity and additional
meta-information. For instance, a shadow memory in our case is a set of memory
locations, each of which is associated with a value from
$\overline{\mathcal{R}}$ and the last instruction that wrote to it.

  * •

Whenever an integer arithmetic operation is encountered, compute the result of
the operation and save the result to the shadow register file or memory.

  * •

Whenever another kind of operation or an unsupported operation is encountered,
save the destination operand as $\bot$; this operation is assumed to not be
valid pointer arithmetic. Operations on $\bot$ always yield $\bot$ as a
result.

  * •

Whenever writing to a memory location, compute the written address using the
above principles, and keep track of the instruction that last wrote to a
memory address.

  * •

Whenever reading from a memory location, compute the read address using the
above principles, and generate a dependency from the current instruction to
the instruction that last wrote to this address (if known).

To handle loop-carried dependencies, we remark that while far-reaching
dependencies may _exist_ , they are not necessarily _relevant_ from a
performance analysis point of view. Indeed, if an instruction $i_{2}$ depends
on a result previously produced by an instruction $i_{1}$, this dependency is
only relevant if it is possible that $i_{1}$ is not yet completed when $i_{2}$
is considered for issuing — else, the result is already produced, and $i_{2}$
needs not wait to execute. Given the structure of the ROB as detailed in
Section 3.1 above, it seems that a dependency is relevant only if it does not
reach more than the size of the ROB away; we formalize and prove this
intuition in Section 3.5 below.

A possible solution to detect loop-carried dependencies in a kernel
$\mathcal{K}$ is thus to unroll it until it contains at least
$\left|\text{ROB}\right|+\left|\mathcal{K}\right|$ instructions. This ensures
that every instruction in the last kernel can find dependencies reaching up to
$\left|\text{ROB}\right|$ back.

On Intel CPUs, the reorder buffer size contained 224 $\mu$OPs on Skylake
(2015), or 512 $\mu$OPs on Golden Cove (2021) (WikiChip, 2021). These sizes
are small enough to reasonably use this solution without excessive slowdown.

###  3.4. Practical implementation

We implement staticdeps in Python, using pyelftools and the capstone
disassembler to extract and disassemble the targeted basic block. The
semantics needed to compute encountered operations are obtained by lifting the
kernel’s assembly to valgrind’s VEX intermediary representation.

The implementation of the heuristic detailed above provides us with a list of
dependencies across iterations of the considered basic block. We then “re-
roll” the unrolled kernel: each dependency is written as a triplet
$(\texttt{source},\texttt{dest},\Delta{}k)$, where the first two elements are
the source and destination instruction of the dependency _in the original,
non-unrolled kernel_ , and $\Delta{}k$ is the number of iterations of the
kernel between the source and destination of the dependency.

Finally, we filter out spurious dependencies: each dependency found should
occur for each kernel iteration $i$ at which $i+\Delta{}k$ is within bounds.
If the dependency is found for less than $80\,\%$ of those iterations, the
dependency is declared spurious and is dropped.

###  3.5. Long distance dependences can be ignored

###### Definition 0 (Distance between instructions).

Let $\left(I_{p}\right)_{0\leq p<n}$ be the trace of executed instructions.
For $p<q$, $\textrm{distance}\left(I_{p},I_{p^{\prime}}\right)$ is the overall
number of decoded $\mu$OPs for the subtrace $\left(I_{r}\right)_{p\leq r\leq
p^{\prime}}$ minus one.

###### Theorem 1 (Long distance dependencies).

A dependency between two instructions that are separated by at least $R$
others $\mu$OPs can be ignored.

To prove this assertion we need a few postulates that describe the functioning
of a CPU and in particular how $\mu$OPs transit in (decoded) and out (retired)
the reorder buffer.

###### Postulate 1 (Reorder buffer as a circular buffer).

Reorder buffer is a circular buffer of size say $R$. It contains only decoded
$\mu$OPs. Let us denote $i_{d}$ the $\mu$OP at position $d$ in the reorder
buffer. Assume $i_{d}$ just got decoded. We have that for every $q$ and
$q^{\prime}$ in $[0,R)$:

$(q-d-1)\%R<(q^{\prime}-d-1)\%R\ \Leftrightarrow\ i_{q}\textrm{ is decoded
before }i_{q^{\prime}}$

If a $\mu$OP has not been retired yet (issued and executed), it cannot be
replaced by any freshly decoded instruction. In other words every non-retired
decoded $\mu$OP are in the reorder buffer. This is possible thanks to the
notion of _full reorder buffer_ :

###### Postulate 2 (Full reorder buffer).

Let us denote by $i_{d}$ the $\mu$OP that just got decoded. The reorder buffer
is said to be full if for $q=(d+1)\%R$, $\mu$OP $i_{q}$ is not retired yet. If
the reorder buffer is full, then instruction decoding is stalled.

Let $(I_{p})_{0\leq p<n}$ be a trace of executed instructions. Each of these
instructions are iteratively decoded, issued, and retired. We will also denote
by $(i_{q})_{0\leq q<m}$ the trace of decoded $\mu$OPs. To prove Theorem 1 we
need to state that two in-flight $\mu$OPs are distant of at most $R$ $\mu$OPs.
For any instruction $I_{p}$, we denote as $Q_{p}$ the range of indices such
that $(i_{q})_{q\in Q_{p}}$ are the $\mu$OPs from the decoding of $I_{p}$. We
will call an _in-flight_ $\mu$OP, a $\mu$OP that is decoded but not yet
retired; It is necessarily in the reorder buffer.

###### Lemma 0 (Distance of in-flight $\mu$OPs).

For any pair of instructions $(I_{p},I_{p^{\prime}})$, and two corresponding
$\mu$OPs, $(i_{q},i_{q^{\prime}})$ with $(q,q^{\prime})\in Q_{p}\times
Q_{p^{\prime}}$,

$\textrm{inflight}(i_{q})\wedge\textrm{inflight}(i_{q^{\prime}})\Rightarrow\textrm{distance}\left(I_{p},I_{p^{\prime}}\right)<R$

In case of branch misprediction, some additional instructions might also be
decoded (and potentially issued). In other words, $(i_{q})_{0\leq q<m}$
potentially contains more $\mu$OPs than those matching the executed
instruction. However, if not surjective, the relation from $\\{I_{p}\\}_{0\leq
p<n}$ to $\\{i_{q}\\}_{0\leq q<m}$ is clearly injective and increasing (using
the order within which instructions and $\mu$OPs are listed). In other words,
$\textrm{distance}\left(I_{p},I_{p^{\prime}}\right)\leq|q^{\prime}-q|$.
Observe that at any time, the content of the ROB can be seen as a window of
length $R$ over $(i_{q})_{0\leq q<m}$. Consequently, if both $i_{q}$ and
$i_{q^{\prime}}$ are in-flight then $|q^{\prime}-q|<R$. ∎

###### Postulate 3 (Issue delay).

Reasons why the issue of a $\mu$OP $i$ is delayed can be:

  1. (1)

$i$ is not yet in the reorder buffer

  2. (2)

$i$ depends on $\mu$OP $i^{\prime}$ which is not retired yet

  3. (3)

ports on which $i$ can be mapped are all occupied

Theorem 1 is now a direct consequence (proof by contradiction) of the previous
observations. Let us consider a delayed issue for $\mu$OP $i$ where the unique
cause is a dependence from $\mu$OP $i^{\prime}$, that is:

  1. (1)

$i$ is already in the reorder buffer

  2. (2)

$i$ depends on $\mu$OP $i^{\prime}$ which is not retired yet

  3. (3)

at least one port on which $i$ can be mapped is available

Since $i^{\prime}$ is not retired yet and $i^{\prime}$ is “before” $i$,
$i^{\prime}$ is still in the reorder buffer, ie. both $i$ and $i^{\prime}$ are
in the reorder buffer. ∎

###  3.6. Limitations

In its current implementation, staticdeps is limited to read-after-write
dependencies, which we believe to be sufficient for latency analysis on usual
CPUs. However, our heuristic may easily support other types of dependencies
(eg. write-after-write) by tracking additional data if necessary.

We argued earlier that one of the shortcomings that most crippled state-of-
the-art tools was that analyses were conducted out-of-context, considering
only the basic block at hand. This analysis is also true for staticdeps, as it
is still focused on a single basic block in isolation; in particular, any
aliasing that stems from outside the analyzed basic block is not visible to
staticdeps.

Work towards a broader analysis range, eg. at the scale of a function, or at
least initializing values with gathered assertions — maybe based on abstract
interpretation techniques — could be beneficial to the quality of dependencies
detections.

As staticdeps’s heuristic is based on randomness, it may yield false
positives: two registers could theoretically be assigned the same value
sampled at random, making them aliasing addresses. This is, however, very
improbable, as values are sampled from a set of cardinality $2^{64}$. If
necessary, the error can be reduced by amplification: running multiple times
the algorithm on different randomness seeds reduces the error exponentially.

Conversely, staticdeps should not present false negatives due to randomness.
Dependencies may go undetected, eg. because of out-of-scope aliasing or
unsupported operations. However, no dependency that falls into the scope of
our baseline depsim — as briefly described in Section 4.4 — should be missed
because of random initialisations.

In silicon, dependencies are implemented not between instructions, but between
$\mu$OPs. Modeling the decomposition of instructions to $\mu$OPs, together
with providing semantics for each $\mu$OP, however, is not done to our
knowledge. Furthermore, it would need to be done for each microarchitecture:
while instructions’ semantics are defined by the ISA, each microarchitecture
may split instructions to $\mu$OPs in its own way.

##  4\. Experiments and evaluation

Our experiments are twofold. We first analyze the results from CesASMe, from
which we confirm AnICA’s case study: memory-carried dependencies are a crucial
shortcoming of state-of-the-art analyzers. We then evaluate staticdeps’
capacity to detect these dependencies: we first compare the dependencies
detected to those actually present, then evaluate the gain in precision when
enriching uiCA’s model with staticdeps.

###  4.1. Experimental environment

The experiments presented in this paper were all realized on a Dell PowerEdge
C6420 machine from the Grid5000 cluster (Balouek et al., 2013), equipped with
192 GB of DDR4 SDRAM — only a small fraction of which was used — and two Intel
Xeon Gold 6130 CPUs (x86-64, Skylake microarchitecture) with 16 cores each.

The experiments themselves were run inside a Docker environment very close to
our artifact, based on Debian Bullseye. Care was taken to disable
hyperthreading to improve measurements stability. For tools whose output is
based on a direct measurement (perf, BHive), the benchmarks were run
sequentially on a single core with no experiments on the other cores. No such
care was taken for Gus as, although based on a dynamic run, its prediction is
purely function of recorded program events and not of program measures. All
other tools were run in parallel.

We use llvm-mca v13.0.1, IACA v3.0-28-g1ba2cbb, Gus at commit 87463c9, BHive
at commit 5f1d500, uiCA at commit 9cbbe93, Ithemal at commit b3c39a8.

###  4.2. CesASMe: analyzers’ throughput predictions

Running CesASMe’s harness provides us with 3500 benchmarks — after filtering
out non-L1-resident benchmarks —, on which each throughput predictor is run.
We make the full output of our tool available in our artifact.

The raw complete output from CesASMe — roughly speaking, a large table with,
for each benchmark, a cycle measurement, cycle count for each throughput
analyzer, the resulting relative error, and a synthesis of the bottlenecks
reported by each tool — enables many analyses that, we believe, could be
useful both to throughput analysis tool developers and users. Tool designers
can draw insights on their tool’s best strengths and weaknesses, and work
towards improving them with a clearer vision. Users can gain a better
understanding of which tool is more suited for each situation.

Bencher | Datapoints | Failures | (%) | MAPE | Median | Q1 | Q3 | K. tau | Time (CPU$\cdot$h)
---|---|---|---|---|---|---|---|---|---
BHive | 2198 | 1302 | (37.20 %) | 27.95 % | 7.78 % | 3.01 % | 23.01 % | 0.81 | 1.37
llvm-mca | 3500 | 0 | (0.00 %) | 36.71 % | 27.80 % | 12.92 % | 59.80 % | 0.57 | 0.96
UiCA | 3500 | 0 | (0.00 %) | 29.59 % | 18.26 % | 7.11 % | 52.99 % | 0.58 | 2.12
Ithemal | 3500 | 0 | (0.00 %) | 57.04 % | 48.70 % | 22.92 % | 75.69 % | 0.39 | 0.38
Iaca | 3500 | 0 | (0.00 %) | 30.23 % | 18.51 % | 7.13 % | 57.18 % | 0.59 | 1.31
Gus | 3500 | 0 | (0.00 %) | 20.37 % | 15.01 % | 7.82 % | 30.59 % | 0.82 | 188.04
Table 2. Statistical analysis of overall results

The error distribution of the relative errors, for each tool, is presented as
a box plot in Figure 3. Statistical indicators are also given in Table 2. We
also give, for each tool, its Kendall’s tau indicator (Kendall, 1938): this
indicator, used to evaluate eg. uiCA (Abel and Reineke, 2022) and Palmed
(Derumigny et al., 2022), measures how well the pair-wise ordering of
benchmarks is preserved, $-1$ being a full anti-correlation and $1$ a full
correlation. This is especially useful when one is not interested in a
program’s absolute throughput, but rather in comparing which program has a
better throughput.

Figure 3. Statistical distribution of relative errors

These results are, overall, significantly worse than what each tool’s article
presents. We attribute this difference mostly to the specificities of
Polybench: composed of computation kernels, it intrinsically stresses the CPU
more than basic blocks extracted out of the Spec benchmark suite. This
difference is clearly reflected in the experimental section of the Palmed
article (Derumigny et al., 2022): the accuracy of most tools is worse on
Polybench than on Spec, often by more than a factor of two.

As BHive and Ithemal do not support control flow instructions (eg. jump
instructions), those had to be removed from the blocks before analysis. While
none of these tools, apart from Gus — which is dynamic —, is able to account
for branching costs, these two analyzers were also unable to account for the
front- and backend cost of the control flow instructions themselves as well —
corresponding to the $TP_{U}$ mode introduced by uiCA (Abel and Reineke,
2022), while others measure $TP_{L}$.

###  4.3. CesASMe: impact of dependency-boundness

An overview of the full results table (available in our artifact) suggests
that on a significant number of rows, the static tools — thus leaving Gus and
BHive apart —, excepted Ithemal, often yield comparatively bad throughput
predictions _together_. To confirm this observation, we look at the 30 % worst
benchmarks — in terms of MAPE relative to perf — for llvm-mca, uiCA and IACA —
yielding 1050 rows each. All of these share 869 rows (82.8 %), which we call
jointly bad rows. In the overwhelming majority (97.5 %) of those jointly bad
rows, the tools predicted fewer cycles than measured, meaning that a
bottleneck is either missed or underestimated.

Figure 4. Statistical distribution of relative errors, with and without
pruning latency bound through memory-carried dependencies rows (llvm-mca
outliers trimmed)

There is no easy way, however, to know for certain which of the 3500
benchmarks are latency bound: no hardware counter reports this. We investigate
this further using Gus’s sensitivity analysis: in complement of the “normal”
throughput estimation of Gus, we run it a second time, disabling the
accounting for latency through memory dependencies. By construction, this
second measurement should be either very close to the first one, or
significantly below. We then assume a benchmark to be latency bound due to
memory-carried dependencies when it is at least 40 % faster when this latency
is disabled; there are 1112 (31.8 %) such benchmarks.

Of the 869 jointly bad rows, 745 (85.7 %) are declared latency bound through
memory-carried dependencies by Gus. In Section 4.2, we presented in Figure 3
general statistics on the tools on the full set of benchmarks. We now remove
the 1112 benchmarks flagged as latency bound through memory-carried
dependencies by Gus from the dataset, and present in Figure 4 a comparative
box plot for the tools under scrutiny, with Kendall’s tau coefficient. While
the results for llvm-mca, uiCA and IACA globally improved significantly, the
most noticeable improvements are the reduced spread of the results and the
Kendall’s $\tau$ correlation coefficient’s increase.

From this, we argue that detecting memory-carried dependencies is a weak point
in current state-of-the-art static analyzers, and that their results could be
significantly more accurate if improvements are made in this direction. We
thus confirm AnICA’s case study on a large dataset of benchmarks, stemming
from real-world code.

###  4.4. Staticdeps: dependency coverage wrt. depsim

In order to assess staticdeps’ results, we implemented depsim, a simple
dynamic analyzer instrumenting binaries using valgrind. It analyzes and
reports memory dependencies of a given binary at runtime.

We use the binaries produced by CesASMe as a dataset, as we already assessed
its relevance and contains enough benchmarks to be statistically meaningful.
We also already have tooling and basic-block segmentation available for those
benchmarks, making the analysis more convenient.

For each binary previously generated by CesASMe, we use its cached basic block
splitting and occurrence count. Among each binary, we discard any basic block
with fewer than 10 % of the occurrence count of the most-hit basic block as
irrelevant.

For each of the considered binaries, we run our baseline dynamic analysis,
depsim, and record its results.

For each of the considered basic blocks, we run staticdeps. We translate the
detected dependencies back to original ELF addresses, and discard the
$\Delta{}k$ parameter, as our dynamic analysis does not report an equivalent
parameter, but only a pair of program counters. Each of the dependencies
reported by depsim whose source and destination addresses belong to the basic
block considered are then classified as either detected or missed by
staticdeps. Dynamically detected dependencies spanning across basic blocks are
discarded, as staticdeps cannot detect them by construction.

We consider two metrics: the unweighted dependencies coverage,
$\operatorname{cov}_{u}$, as well as the weighted dependencies coverage,
$\operatorname{cov}_{w}$:

$\operatorname{cov}_{u}=\dfrac{\left|\text{found}\right|}{\left|\text{found}\right|+\left|\text{missed}\right|}$

$\operatorname{cov}_{w}=\dfrac{\sum_{d\in\text{found}}\rho_{d}}{\sum_{d\in\text{found}\,\cup\,\text{missed}}\rho_{d}}$

where $\rho_{d}$ is the number of occurrences of the dependency $d$,
dynamically detected by depsim.

Lifetime |  $\operatorname{cov}_{u}$ (%) |  $\operatorname{cov}_{w}$ (%)
---|---|---
$\infty$ | 38.1 % | 44.0 %
1024 | 57.6 % | 58.2 %
512 | 56.4 % | 63.5 %
Table 3. Unweighted and weighted coverage of staticdeps on CesASMe’s binaries Dataset | Bencher | Datapoints | MAPE | Median | Q1 | Q3 | $K_{\tau}$
---|---|---|---|---|---|---|---
Full | uiCA | 3500 | 29.59 % | 18.26 % | 7.11 % | 52.99 % | 0.58
\+ staticdeps | 3500 | 19.15 % | 14.44 % | 5.86 % | 23.96 % | 0.81
Pruned | uiCA | 2388 | 18.42 % | 11.96 % | 5.42 % | 23.32 % | 0.80
\+ staticdeps | 2388 | 18.77 % | 12.18 % | 5.31 % | 23.55 % | 0.80
Table 4. Evaluation through CesASMe of the integration of staticdeps to uiCA

These metrics are presented for the 3 500 binaries of CesASMe in the first
data row of Table 3. The obtained coverage, of about 40 %, is lower than
expected.

However, as we already pointed, dependencies matter only if the source and
destination are not too far away. To this end, we introduce in depsim a notion
of _dependency lifetime_. As we do not have access without a heavy runtime
slowdown to elapsed cycles in valgrind, we define a _timestamp_ as the number
of instructions executed since beginning of the program’s execution; we
increment this count at each branch instruction to avoid excessive
instrumentation slowdown. We re-run the previous experiments with lifetimes of
respectively 1 024 and 512 instructions, which roughly corresponds to the
order of magnitude of the size of a reorder buffer; results can also be found
in Table 3. While the introduction of a 1 024 instructions lifetime greatly
improves the coverage rates, both unweighted and weighted, further reducing
this lifetime to 512 does not yield significant enhancements.

The final coverage results, with a rough 60 % detection rate, are reasonable
and detect a significant proportion of dependencies; however, many are still
not detected.

This may be explained by the limitations studied in subsection 3.6 above, and
especially the inability of staticdeps to detect dependencies through aliasing
pointers. This falls, more broadly, into the problem of lack of context that
we expressed before: we expect that an analysis at the scale of the whole
program, that would be able to integrate constraints stemming from outside the
loop body, would capture many more dependencies.

###  4.5. Staticdeps: enriching uiCA’s model

Figure 5. Statistical distribution of relative errors of uiCA, with and
without staticdeps hints, with and without pruning latency bound through
memory-carried dependencies rows

To estimate the real gain in performance debugging scenarios, however, we
integrate staticdeps into uiCA.

There is, however, a discrepancy between the two tools: while staticdeps works
at the assembly instruction level, uiCA works at the $\mu$OP level. In real
hardware, dependencies indeed occur between $\mu$OPs; however, we are not
aware of the existence of a $\mu$OP-level semantic description of the x86-64
ISA, which made this level of detail unsuitable for the staticdeps analysis.

We bridge this gap in a conservative way: whenever two instructions
$i_{1},i_{2}$ are found to be dependant, we add a dependency between each
couple $\mu_{1}\in i_{1},\mu_{2}\in i_{2}$. This approximation is thus
pessimistic, and should predict execution times biased towards a slower
computation kernel. A finer model, or a finer (conservative) filtering of
which $\mu$OPs must be considered dependent — eg. a memory dependency can only
come from a memory-related $\mu$OP — may enhance the accuracy of our
integration.

We then evaluate our gains by running CesASMe’s harness by running both uiCA
and uiCA \+ staticdeps, as we did in Section 4.3, on two datasets: first, the
full set of 3 500 binaries from CesASMe; then, the set of binaries pruned to
exclude benchmarks heavily relying on memory-carried dependencies introduced
in subsection 4.3. If staticdeps is beneficial to uiCA, we expect uiCA \+
staticdeps to yield significantly better results than uiCA alone on the first
dataset. On the second dataset, however, staticdeps should provide no
significant contribution, as the dataset was pruned to not exhibit significant
memory-carried latency-boundness. We present these results in Table 4, as well
as the corresponding box-plots in Figure 5.

The full dataset uiCA \+ staticdeps row is extremely close, on every metric,
to the pruned, uiCA-only row. On this basis, we argue that staticdeps’
addition to uiCA is very conclusive: the hints provided by staticdeps are
sufficient to make uiCA’s results as good on the full dataset as they were
before on a dataset pruned of precisely the kind of dependencies we aim to
detect. Furthermore, uiCA and uiCA \+ staticdeps’ results on the pruned
dataset are extremely close: this further supports the accuracy of staticdeps.

While the results obtained against depsim in subsection 4.4 above were
reasonable, they were not excellent either, and showed that many kinds of
dependencies were still missed by staticdeps. However, our evaluation on
CesASMe by enriching uiCA shows that, at least on the workload considered, the
dependencies that actually matter from a performance debugging point of view
are properly found.

This, however, might not be true for other kinds of applications that would
require a dependencies analysis.

##  5\. Conclusion

In this article, we have presented the new heuristic-based analyzer,
staticdeps, for statically identifying memory-carried dependencies of a binary
basic block. We have shown that it can be used to beneficially extend state-
of-the-art code analyzers, such as uiCA. In order to provide sound baselines
for evaluating such extensions, we also have introduced the evaluation
framework CesASMe, which is meant to compose measurement environments and code
analyzers and make their results commensurable. In order to take into account
the impact of a basic block’s context on its measured throughput, the method
we propose consists in reasoning at kernel-level by lifting the basic block-
level predictions. Finally, CesASMe has allowed us to exhibit a significant
gain in accuracy, thanks to staticdeps, on latency-bound microbenchmarks
generated from the HPC-native Polybench benchmark suite.

## References

  * (1)
  * Abel and Reineke (2019a) Andreas Abel and Jan Reineke. 2019a.  nanoBench: A Low-Overhead Tool for Running Microbenchmarks on x86 Systems.  _arXiv e-prints_ abs/1911.03282 (2019).  arXiv:1911.03282 http://arxiv.org/abs/1911.03282
  * Abel and Reineke (2019b) Andreas Abel and Jan Reineke. 2019b.  uops.info: Characterizing Latency, Throughput, and Port Usage of Instructions on Intel Microarchitectures. In _ASPLOS_ (Providence, RI, USA) _(ASPLOS ’19)_. ACM, New York, NY, USA, 673–686.  https://doi.org/10.1145/3297858.3304062
  * Abel and Reineke (2022) Andreas Abel and Jan Reineke. 2022.  UiCA: Accurate Throughput Prediction of Basic Blocks on Recent Intel Microarchitectures. In _Proceedings of the 36th ACM International Conference on Supercomputing_ (Virtual Event) _(ICS ’22)_. Association for Computing Machinery, New York, NY, USA, Article 33, 14 pages.  https://doi.org/10.1145/3524059.3532396
  * AMD (2023) AMD 2023.  _AMD64 Architecture Programmer’s Manual, volume 2_.  AMD.
  * Balouek et al. (2013) Daniel Balouek, Alexandra Carpen Amarie, Ghislain Charrier, Frédéric Desprez, Emmanuel Jeannot, Emmanuel Jeanvoine, Adrien Lèbre, David Margery, Nicolas Niclausse, Lucas Nussbaum, Olivier Richard, Christian Pérez, Flavien Quesnel, Cyril Rohr, and Luc Sarzyniec. 2013.  Adding Virtualization Capabilities to the Grid’5000 Testbed.  In _Cloud Computing and Services Science_ , Ivan I. Ivanov, Marten van Sinderen, Frank Leymann, and Tony Shan (Eds.). Communications in Computer and Information Science, Vol. 367. Springer International Publishing, 3–20.  https://doi.org/10.1007/978-3-319-04519-1_1
  * Binkert et al. (2011) Nathan Binkert, Bradford Beckmann, Gabriel Black, Steven K. Reinhardt, Ali Saidi, Arkaprava Basu, Joel Hestness, Derek R. Hower, Tushar Krishna, Somayeh Sardashti, Rathijit Sen, Korey Sewell, Muhammad Shoaib, Nilay Vaish, Mark D. Hill, and David A. Wood. 2011\.  The Gem5 Simulator.  _SIGARCH Comput. Archit. News_ 39, 2 (aug 2011), 1–7.  https://doi.org/10.1145/2024716.2024718
  * Bondhugula et al. (2007) Uday Bondhugula, J. Ramanujam, and P. Sadayappan. 2007\.  _PLuTo: A Practical and Fully Automatic Polyhedral Parallelizer and Locality Optimizer_.  Technical Report OSU-CISRC-10/07-TR70. The Ohio State University.
  * Chen et al. (2019) Yishen Chen, Ajay Brahmakshatriya, Charith Mendis, Alex Renda, Eric Atkinson, Ondřej Sýkora, Saman Amarasinghe, and Michael Carbin. 2019\.  BHive: A Benchmark Suite and Measurement Framework for Validating x86-64 Basic Block Performance Models. In _2019 IEEE International Symposium on Workload Characterization (IISWC)_. 167–177.  https://doi.org/10.1109/IISWC47752.2019.9042166
  * Derumigny et al. (2022) Nicolas Derumigny, Théophile Bastian, Fabian Gruber, Guillaume Iooss, Christophe Guillon, Louis-Noël Pouchet, and Fabrice Rastello. 2022.  PALMED: Throughput Characterization for Superscalar Architectures. In _2022 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)_. 106–117.  https://doi.org/10.1109/CGO53902.2022.9741289
  * Gruber (2019) Fabian Gruber. 2019\.  _Performance Debugging Toolbox for Binaries: Sensitivity Analysis and Dependence Profiling_.  Ph. D. Dissertation. Université Grenoble Alpes.  http://www.theses.fr/2019GREAM071 2019GREAM071.
  * Intel Corporation ([n. d.]) Intel Corporation. [n. d.].  Intel Architecture Code Analyzer (IACA).  https://software.intel.com/en-us/articles/intel-architecture-code-analyzer/.
  * Intel Corporation (2023) Intel Corporation 2023.  _Intel® 64 and IA-32 Architectures Software Developer’s Manual, volume 1_.  Intel Corporation.
  * Kendall (1938) Maurice G Kendall. 1938\.  A new measure of rank correlation.  _Biometrika_ 30, 1/2 (1938), 81–93.
  * Laukemann et al. (2019) Jan Laukemann, Julian Hammer, Georg Hager, and Gerhard Wellein. 2019.  Automatic Throughput and Critical Path Analysis of x86 and ARM Assembly Kernels. In _2019 IEEE/ACM Performance Modeling, Benchmarking and Simulation of High Performance Computer Systems (PMBS)_. 1–6.  https://doi.org/10.1109/PMBS49563.2019.00006
  * Linux Kernel ([n. d.]) Linux Kernel. [n. d.].  perf: Linux profiling with performance counters.  http://perf.wiki.kernel.org/index.php/Main_Page.
  * Mendis et al. (2018) Charith Mendis, Saman P. Amarasinghe, and Michael Carbin. 2018\.  Ithemal: Accurate, Portable and Fast Basic Block Throughput Estimation using Deep Neural Networks.  _CoRR_ abs/1808.07412 (2018).  arXiv:1808.07412 http://arxiv.org/abs/1808.07412
  * Nethercote and Seward (2003) Nicholas Nethercote and Julian Seward. 2003.  Valgrind: A Program Supervision Framework.  _Electr. Notes Theor. Comput. Sci._ 89, 2 (2003), 44–66.
  * Perais and Seznec (2014) Arthur Perais and André Seznec. 2014.  Practical data value speculation for future high-end processors. In _2014 IEEE 20th International Symposium on High Performance Computer Architecture (HPCA)_. 428–439.  https://doi.org/10.1109/HPCA.2014.6835952
  * PoCC ([n. d.]) PoCC [n. d.].  PoCC, the Polyhedral Compiler Collection.  https://www.cs.colostate.edu/~pouchet/software/pocc/.
  * Pouchet and Yuki (2016) Louis-Noël Pouchet and Tomofumi Yuki. 2016.  PolyBench/C: The polyhedral benchmark suite, version 4.2.  http://polybench.sf.net.
  * Quynh and the Capstone collaborators ([n. d.]) Nguyen Anh Quynh and the Capstone collaborators. [n. d.].  Capstone engine.  https://www.capstone-engine.org/.
  * Ritter and Hack (2022) Fabian Ritter and Sebastian Hack. 2022.  AnICA: Analyzing Inconsistencies in Microarchitectural Code Analyzers.  _Proc. ACM Program. Lang._ 6, OOPSLA2, Article 125 (oct 2022), 29 pages.  https://doi.org/10.1145/3563288
  * Sheikh et al. (2017) Rami Sheikh, Harold W. Cain, and Raguram Damodaran. 2017\.  Load Value Prediction via Path-based Address Prediction: Avoiding Mispredictions due to Conflicting Stores. In _2017 50th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_. 423–435.
  * Sony Corporation and LLVM Project ([n. d.]) Sony Corporation and LLVM Project. [n. d.].  LLVM Machine Code Analyzer.  https://llvm.org/docs/CommandGuide/llvm-mca.html.
  * Tomasulo (1967) R. M. Tomasulo. 1967\.  An Efficient Algorithm for Exploiting Multiple Arithmetic Units.  _IBM Journal of Research and Development_ 11, 1 (1967), 25–33.  https://doi.org/10.1147/rd.111.0025
  * WikiChip (2021) WikiChip. 2021\.  Intel Details Golden Cove: Next-Generation Big Core For Client and Server SoCs.  https://fuse.wikichip.org/news/6111/intel-details-golden-cove-next-generation-big-core-for-client-and-server-socs/.