[1]Emanuele Sangiorgio

[1]Department of Social Sciences and Economics, Sapienza University of Rome,
P.le Aldo Moro, 5, 00185, Rome, Italy

2]Department of Computer Science, Sapienza University of Rome, Viale Regina
Elena, 295, 00161, Rome, Italy

3]GRANEM, Université d’Angers, SFR Confluences, F-49000, Angers, France

# The inherent randomness of news virality on social media

<EMAIL_ADDRESS>Matteo Cinelli<EMAIL_ADDRESS>Roy
Cerqueti<EMAIL_ADDRESS>Walter Quattrociocchi
<EMAIL_ADDRESS>*  [  [

###### Abstract

Initially conceived for entertainment, social media platforms have profoundly
transformed the dissemination of information and consequently reshaped the
dynamics of agenda-setting. In this scenario, understanding the factors that
capture audience attention and drive viral content is crucial. Employing
Gibrat’s Law, which posits that an entity’s growth rate is unrelated to its
size, we examine the engagement growth dynamics of news outlets on social
media. Our analysis encloses the Facebook historical data of over a thousand
news outlets, encompassing approximately 57 million posts in four European
languages from 2008 to the end of 2022. We discover universal growth dynamics
according to which news virality is independent of the traditional size or
engagement with the outlet. Moreover, our analysis reveals a significant long-
term impact of news source reliability on engagement growth, with engagement
induced by unreliable sources decreasing over time. We conclude the paper by
presenting a statistical model replicating the observed growth dynamics.

###### keywords:

Social media $|$ Growth dynamics $|$ Attention economy

##  1 Introduction

Originally designed for entertainment, social media platforms have evolved
into significant channels for information dissemination [1, 2, 3, 4, 5],
altering traditional agenda-setting dynamics [6, 7, 8, 9]. In this competitive
landscape marked by many information sources, we aim to uncover the
determinants of audience attention and the factors contributing to content
virality [10], that is the propensity of content to achieve rapid diffusion
and high engagement levels on social media platforms [11, 12, 13]. Indeed,
social media often dictate which topics become prominent while others are
overlooked [8, 14]. As online users tend to favor information aligning with
their existing beliefs, commonly ignoring opposing viewpoints [15, 16, 17],
this behavior can create and reinforce online ’echo chambers’ [18]— digital
clusters of homogeneous thought where narratives are collectively shaped and
solidified [19, 20, 21]. The magnitude of the echo chamber phenomenon and its
consequent effects on polarization may vary among social media platforms [22].
Furthermore, many platforms implement algorithms designed to prioritize user
engagement that might alter information spreading [23, 24, 25], thereby
exacerbating ideological divisions [26, 27, 28]. The rise of the attention
economy is at the heart of digital discourse transformation [29, 30, 31, 32].
In this economy, a broad spectrum of content creators, ranging from news
outlets to individual influencers, vie for limited users’ attention [33, 34,
35, 36]. Like traditional market evolution, digital stakeholders chase user
engagement, converting this captured attention into tangible revenues through
advertising, service offerings, and subscription models [37, 38]. With
revenues closely linked to audience reach and engagement, understanding the
growth mechanisms of digital content creators is crucial. Our research aims to
unravel the dynamics of the digital ecosystem, focusing on the evolution of
content consumption and audience reach. We anchor our analysis in Gibrat’s Law
[39], originally formulated to explain traditional business growth, extending
its application to the digital domain. The foundational premise of this law,
positing that a firm’s growth rate is independent of its initial size, has
found relevance in various realms beyond business, like the growth patterns of
city sizes [40, 41, 42]. While various studies have explored Gibrat’s Law
across different contexts, yielding mixed methodologies and results [43, 44,
45, 46], its implications for digital domains remain unexamined. Focusing on
the supply and demand of news in the attention economy of social media
platforms, we aim to determine whether the principles of proportionate growth
hold in social media news dissemination. We systematically study the growth
patterns of news outlets on Facebook, comparing their growth to audience sizes
over different periods. For a deeper understanding of news engagement on
social media, we obtain a list of news outlets from NewsGuard [47], an entity
recognized for tackling misinformation by assessing the credibility and
reliability of news sources. After selecting all the news outlets with a
Facebook account listed on NewsGuard, we use their Facebook URLs to gather
their data from CrowdTangle [48], a Facebook-owned tool that monitors
interactions on public content from Facebook pages, groups, and verified
profiles. This effort provides a comprehensive dataset: the Facebook
historical data, from 2008 to the end of 2022, of over 1000 news outlets
across four languages - English, French, German, and Italian. Thanks to the
post-level granularity of our dataset, we can measure the growth of pages’
metrics on various timescales by aggregating data according to a broader or
narrower time window (daily, weekly, monthly, and quarterly), providing robust
insights into online news outlets’ growth dynamics. The paper is structured as
follows: Initially, we define our analysis framework, investigate the growth
regime, and assess its dynamics. Next, we introduce a stochastic model to
replicate the observed growth patterns, illustrating the consistency between
results and empirical evidence. Finally, we compare the growth of news outlets
based on their information quality. We find that the ability to create viral
content and capture widespread attention is untied to the size of the
information provider. Engagement follows a universal growth pattern in short-
term intervals. Contrary to common belief, we observe that Followers count is
not a reliable measure of a page’s peaks of influence; the impact on
engagement becomes apparent only over extended periods. Additionally, we
discover that the unreliability of a news source negatively affects engagement
growth in the long term.

## Results

We start by defining our framework of analysis. The simplest growth model,
proposed by Gibrat [39], states that a given company’s proportional growth
rate is independent of its absolute initial size. His assumptions can be
formalized by the following random multiplicative process for the size $S$:

$S_{t+\Delta t}=S_{t}(1+\epsilon_{t}),$ (1)

where $t\geq 0$ is time, $\Delta t>0$, $S_{t+\Delta t}$ and $S_{t}$ are the
sizes at time ${t+\Delta t}$ and $t$, respectively, and $\epsilon_{t}$ is a
random variable coming from an i.i.d. stochastic process uncorrelated to
$S_{s}$ ($0\leq s\leq t$) having mean $\mu$ and standard deviation $\sigma$.
Due to the generic formulation of the original model, we adapt its
interpretation to achieve a meaningful application in the context of social
media. In terms of information spreading, virality refers to the rapid and
widespread dissemination of information or content. By focusing on the extent
and impact of the diffusion, virality refers to content engagement exceeding
typical expectations, reaching a high level of users and interactions. In our
analysis we focus on the latter facet, characterizing the growth of content
performance with respect to the size of its source. The analysis is performed
on two key metrics: Followers and Engagement. We first define how to assess
page size and performance on social media, and our timescales of analysis.
Then we evaluate the growth regime of both metrics concerning size for each
timescale.

### Metrics and Methodology for Social Media Page Analysis

In evaluating whether the size of a page affects its growth, we first need to
establish how to measure the size and its performance. In the study of social
media platforms, notably Facebook, we primarily rely on two metrics: 1) Page
Followers, the number of users subscribed to a given page at the time of
posting, representing a metric of reach, and 2) Engagement, encompassing the
total number of users’ interactions with the page’s posts (that is, the sum of
Likes, Comments, and Shares). The size of a page is typically inferred from
its Followers count, a standard measure on such platforms. The alternative
would be using Engagement, but such a choice would introduce undesired issues.
Indeed, the engagement definition is inherently ambiguous: it can be a
cumulative sum of interactions over the entire lifespan or a count over a
specific duration, such as a week. With period-specific measures, pages’ size
could fluctuate too widely (spanning even across orders of magnitude), thus
leading to interpretational challenges. Conversely, using a cumulative
engagement count to quantify size may over-represent past performances.
Consequently, we opt to use Followers as a more stable representation of page
size. On the other hand, Engagement represents the page performance in terms
of users’ attention. Our analysis leverages varied timescales to observe
growth patterns. Specifically, we consider four time-granularity: daily (D),
weekly (W), monthly (M), and quarterly (Q). Therefore, for each page, we
consider both metrics, Followers, and Engagement, according to different time
windows. To measure engagement, we consider aggregated data depending on the
timescale of the analysis. Focusing on the total attention received by the
news outlets, we consider higher total engagement as a higher users’
attention, regardless of the number of posts. Such interpretation relies on
the fact that publishing more posts does not lead to more engagement if users
are not interested in a topic. Likewise, getting engagement with several posts
implies high attention, and using the mean value would underestimate the
latter. We further validate it by showing that both measures bring equivalent
results. For Followers, since they already are a cumulative value, we take
only a representative data point in the time window, depending on the chosen
timescale (see Materials and Methods for further details). Transitioning
between these scales offers diverse and new perspectives on growth dynamics.
In the case of Followers’ growth, daily measurements are deemed unsuitable due
to limited variability, whereas all four scales are relevant for Engagement
analysis, since news outlets are very active accounts and usually have
multiple posts per day.

### Assessing the growth regime

Figure 1: (A-C) p-values of Mann-Whitney U tests between classes of size for
Followers and Engagement growth rate distributions. Panel titles indicate the
metric being tested and the metric according to which we determine the size.
Row and column headers represent the class size. Bold numbers represent
p-values for which we reject the hypothesis that the growth distributions do
not differ, with the alternative hypothesis that the smaller class grows at a
higher rate. For readability, 0 represents p-values smaller than 0.0001.

Based on the definition of Followers and Engagement, and according to (1), we
refer to Followers and Engagement growth, respectively, as

$F_{t+\Delta t}=F_{t}(1+\epsilon^{(F)}_{t})$ (2) $E_{t+\Delta
t}=E_{t}(1+\epsilon^{(E)}_{t}),$ (3)

where the superscripts $(F)$ and $(E)$ point to an intuitive notation for the
process $\epsilon$ with mean $\mu_{F}$ and $\mu_{E}$ and standard deviation
$\sigma_{F}$ and $\sigma_{E}$ for Followers and Engagement, respectively. Time
measures the different timescales: D, W, M and Q. In (2), $F_{t}$ is the
number of Followers at time $t$ while $E_{t}$ represents the number of
interactions generated at time $t$. In the same way, $(1+\epsilon^{(F)}_{t})$
and $(1+\epsilon^{(E)}_{t})$ are the growth rates of $F_{t}$ and $E_{t}$,
respectively. As Gibrat’s Law was originally intended to explain the emergence
of a log-normal distribution of sizes, we first assess that Followers and
Engagement distributions comply with this assumption. Since Followers’ records
on CrowdTangle start from 1/1/2018 and stop on 31/12/2022, hence relying on a
five-year timespan of analysis, we take into consideration such a period for
the relationship between Followers and Engagement growth. For this reason,
when we consider the metrics of Followers and Engagement jointly, we restrict
our analysis period to 01/01/2018 - 31/12/2022. In the analysis in which we do
not account for Followers’ value, we consider the entire 15-year timespan,
ranging from 01/01/2008 to 31/12/2022. See Processing Methods Section and
Fig.S1 in SI Appendix for further details. Fig.S2 in SI Appendix shows
distributions of both metrics at the start and end of the considered period.
To assess whether growth rate distributions vary based on page size, we define
four classes of pages based on their Followers, so as to have comparable
populations between them over the entire period. The considered four classes
of Followers are: 10K–50K, 50K–150K, 150K–500K, and 500K–5M. The bin
boundaries were defined by jointly considering two aspects: a comparable
number of pages between classes and actual values of Followers for which it
was reasonable to account for a page as small, medium, large, or very large.
As a robustness check, we reported the clustering in Fig. S3 in the SI
Appendix from which our classes and the clustering ones are predominantly
overlapping. In evaluating growth regimes, we posit that the absence of size
effects should, as an initial assumption, result in comparable growth rate
distributions across different classes. To compare growth rate distributions
among different classes of size, we apply, to each pair of bins, a Mann-
Whitney U test on both metrics and for different timescales. Results are
reported in Fig.1, while Fig.S4 in SI Appendix reports p-values of the two-
tailed tests. We first inspect the case of Followers, reported in Fig.1A.
Statistical tests across observed timescales consistently demonstrate that
smaller pages experience greater Followers’ growth than their larger
counterparts. This evidence counters the notion of proportionate effect growth
as described by Gibrat. In contrast, the growth dynamics of Engagement provide
intriguing insights. Specifically, in Fig.1B, the growth regime is influenced
by the duration of the observed timescale. In short-term observations (daily
and weekly scales), engagement variation is consistent irrespective of page
size. Thus, from a micro-level perspective, engagement adheres to a universal
growth regime, independently of page size. However, as we transition to a
monthly scale, a deviation in the regime emerges, with smaller-sized classes
outperforming their larger counterparts. This deviation becomes definite on a
quarterly timescale, underscoring the influence of size on long-term
engagement growth.

For a comprehensive perspective, we recalibrated our Engagement analysis,
reported in Fig. 1C, categorizing size based on Engagement metric. Bins are
delineated by the quartiles of Engagement distribution across all pages within
a specific timescale, after trimming between the 5th and the 95th percentiles.
Our analysis indicates that, in this case, the system predominantly diverges
from Gibrat’s law of proportionate effect. Exceptions are noted for middle-
sized pages (those within the 2nd and 3rd quartiles) on a quarterly timescale.
Thus, in short-term observations, Engagement consistently depends on its
recent performance, irrespective of page size, while the influence of
Followers becomes evident with the increase of the observed timescale. We note
that our results show correspondences with evidence from prior studies in
different domains, such as the distribution of growth rates displaying a
’universal’ form that does not depend on the size [49], and the system
experiencing a growth regime transition as the timescale widens [50]. These
findings bear significant implications. Notably, in the short term, size does
not dictate the probability of engagement growth. Extrapolating this to
individual posts suggests an egalitarian landscape where every news item,
irrespective of its source or the number of its Followers, has an equal
propensity to go viral, that is to suddenly gain disproportionate engagement.
Consequently, the mere count of Followers proves inadequate in gauging the
page’s potential influence. As a robustness check, in Fig S5 and S6 of SI
Appendix, we reported two variants of the tests performed in Fig 1B, showing
how the results still hold by using the mean engagement value or by changing
the bin boundaries.

### Analyzing Engagement and Followers Dynamics

Figure 2: Comparison of observed and theoretical growth rate distributions for
Engagement and Followers. Red lines denote theoretical densities obtained by
fitting empirical ones, with labels D, W, M, and Q indicating Daily, Weekly,
Monthly, and Quarterly timescales.

Empirical evidence suggests that the logarithm of many growth rate
distributions often takes an exponential form. Consistently with prior studies
[51, 52], our analysis reveals that the logarithm of Engagement growth rates
adheres to a particular exponential distribution known as the Laplace
distribution. In contrast, the growth rates for Followers display an
asymmetry, exhibiting a right-skewed distribution. Our analysis suggests a fit
with a heavy-tailed distribution, specifically the Burr distribution [53].
Since the Burr is exclusively defined for positive values, we here employ the
absolute growth rates, rather than their logarithms. A visual comparison
between the observed and fitted distributions is reported in Fig.2 (see
Materials and Methods section for details of the fitting procedure). The
matching of the empirical distributions of Engagement growth with the Laplace
brings significant upshots. As pointed out by previous works [54, 55], growth
phenomena could display a non-trivial relation between the positive and
negative side of its rate distribution. The detailed balance property, or
time-reversal symmetry, states that the empirical probability of changing size
from one value to another is statistically the same as that for its reverse
process. Statistical tests provided evidence of how the Engagement’s short-
term fluctuations adhere to a universal distribution, independently of the
page size, with $\mu_{E}\to 0$ when passing from timescale Q to timescale D.
Fig.S7 in SI Appendix shows parameters variation according to timescales for
the considered size classes. Furthermore, the symmetry property of the Laplace
distribution, with $\mu\approx 0$, directly implies the validity of detailed
balance. We can draw two significant implications from this outcome. From a
viewpoint of interpretation, assessing these statistical properties of short-
term engagement provides a deeper understanding of news consumption dynamics,
which can influence how news providers act to handle users’ fluctuating
attention. From a technical standpoint, ascertaining the universality of this
dynamic and the probability distribution that describes it enables us to
exploit it as a proxy for defining and detecting virality, namely gaining
disproportionate engagement.

### Modelling growth

Our empirical findings show that the impact of size on growth becomes evident
only if observed through larger timescales and that the growth pattern is
universal at the micro-level. Knowing the distributions that define the
evolution of our metrics allows us to evaluate the variation of their
parameters according to size and timescale. For each time scale, we can model
parameters of both growth rate distributions based on Followers and Engagement
values. The regression coefficients are reported in Tab 1.

Table 1: Regression coefficients and p-values of Laplace and Burr distribution parameters estimation for different timescales. $\beta 0$ |  | $\beta 1$ |  | $\beta 2$ |  | Par | Time
---|---|---|---|---|---|---|---
-0.109 | (0.063) | 0.054 | (<0.001) | -0.062 | (<0.001) | $\mu$ | W
0.073 | (0.248) | 0.037 | (<0.001) | -0.051 | (<0.001) | $\mu$ | M
0.384 | (<0.001) | 0.031 | (<0.001) | -0.065 | (<0.001) | $\mu$ | Q
0.613 | (<0.001) | 0.027 | (0.001) | -0.054 | (<0.001) | $b$ | W
0.593 | (<0.001) | 0.041 | (<0.001) | -0.066 | (<0.001) | $b$ | M
0.844 | (<0.001) | 0.056 | (<0.001) | -0.094 | (<0.001) | $b$ | Q
8420.469 | (<0.001) | -372.77 | (0.025) | - |  | $c$ | W
2550.01 | (<0.001) | -127.559 | (0.014) | - |  | $c$ | M
1053.905 | (0.002) | -56.113 | (0.017) | - |  | $c$ | Q
-0.778 | (<0.001) | 0.083 | (<0.001) | - |  | $k$ | W
-0.751 | (<0.001) | 0.078 | (<0.001) | - |  | $k$ | M
-0.714 | (0.001) | 0.073 | (<0.001) | - |  | $k$ | Q

We can thereby simulate growth on the chosen timescale, given two starting
values of Followers and Engagement, $F_{0}$ and $E_{0}$, by iteratively
sampling growth rates value from the distributions modeled using the
parameters specified in Case 1 and Case 2.

#### Case 1: Engagement growth

We consider the dynamics described in (3) with $\epsilon^{(E)}$ following the
Laplace distribution in (8) (see Materials and Methods), with:

$\mu=\beta 0_{\mu}+\beta 1_{\mu}ln(F_{t})+\beta 2_{\mu}ln(E_{t})$ (4) $b=\beta
0_{b}+\beta 1_{b}ln(F_{t})+\beta 2_{b}ln(E_{t})$ (5)

#### Case 2: Followers growth

We consider (2), being $\epsilon^{(F)}$ the logarithm of the growth rate
behaving according to the Burr distribution in (10) (see Materials and
Methods), with:

$c=\beta 0_{c}+\beta 1_{c}ln(F_{t})$ (6) $k=\beta 0_{k}+\beta 1_{k}ln(F_{t})$
(7)

Figure 3: Results of growth simulation with different starting sizes. Sub-plot
headers indicate the Followers starting value and the related timescale. Solid
lines represent the mean cumulative distribution function value of the
iteration time, shades represent the corresponding standard error.

Results of simulations are shown in Fig. 3, representing the evolution of both
metrics for different starting sizes (Followers) on three timescales used for
the analysis (W, M, and Q). We selected three starting sizes representing
pages with low, medium, and high number of Followers, i.e., 25K, 250K, and 1M,
respectively. As results show, by observing the system on a weekly timescale,
the engagement shows a basically steady evolution for all three sizes. As we
extend the observed timescale, by passing from weekly to quarterly, the
engagement growth of small pages begins to exhibit convex behavior, while the
growth curve of big pages shifts toward concavity, providing evidence of how
Followers impact the engagement evolution only over long-term intervals. On
the other hand, Followers of smaller pages always grow faster than bigger ones
in each timescale. Our simulations consistently match empirical evidences.
Despite the model’s engagement growth probability being based on Followers,
the universal characteristic of the process at the temporal micro-scale level
is evident. These results highlight the limitation of using Followers as the
sole metric to gauge overall page influence. Short-term outcomes seem to
derive from a uniform stochastic process, possibly elucidating the influence
of algorithms on user news consumption behaviors. While this suggests an
environment where all content providers might be on an equal stand regarding
visibility, it also necessitates continuous monitoring to mitigate the spread
of harmful content, such as misinformation. Basing influence assessments
solely on the number of Followers can lead to oversight. The potential
presence of ’one-time’ or ’hidden influencers’ — entities with a
disproportionate influence relative to their Follower count — needs attention.
The missing of a clear engagement effect on Follower growth, the lack of
significance of ${\beta 2}$ on Burr’s parameters variation, further emphasizes
this, indicating that heightened interactions do not necessarily translate to
a corresponding increase in Followers or sustained reach.

### Growth and Information Quality

Figure 4: A) Comparison of Engagement growth rate distributions of
Questionable and Reliable pages for different timescales. B) Mean growths of
Questionable and Reliable pages across increasing timescales.

The effects of external factors on engagement growth manifest in the long
term. Potential explanations for differences in page growth could be plenty,
though one of the most relevant for society is the propensity of news outlets
to produce unverified news and misinformation. For this reason, we conclude
our analysis by comparing two sub-samples of pages representing reliable and
questionable ones. Since we do not account for Followers value, this analysis
encompasses the entire pages’ lifespan. The classification is performed based
on reliability scores provided by Newsguard. Since our dataset comprises 898
reliable sources and 131 non-reliable ones, we performed a sampling of 131
reliable sources to obtain two comparable samples. See Materials and Methods
and Fig.S8 in SI Appendix for further details about the reliability ratings
and the sampling procedure. Fig.4 shows growth rate distributions of
engagement and their evolution across the various timescales. Tab.S1 in SI
Appendix shows the p-values of Mann-Whitney U tests between the two sub-
samples, as in our previous analyses. Both graphic representations and tests
display how the trustworthiness of the news source plays a crucial role, as
the engagement of unreliable pages progressively decreases as the time scale
widens. Anew, the short-term fluctuations follow a universal dynamic, and
neither the reliability turns out to determine growth differences. The long-
term divergence, which may result from both users’ behavior and platform
moderation policies, along with the inherent randomness of short-term
fluctuations, highlight the importance of continuous efforts to monitor the
consumption of sensitive content, such as misinformation.

### Conclusions

In historical media landscapes, prominent news outlets predominantly
influenced agenda-setting, their reach determining the flow and focus of
public discourse. However, the emergence of social media platforms—designed
more for entertainment than information spreading—has reshaped this dynamic.
While many assume larger outlets and their inherent reach would dominate
social media discourse, our research challenges this perspective. Analyzing
engagement metrics across diverse news outlets on Facebook, we find that news
virality, namely a disproportionate growth of engagement, is not strictly tied
to the traditional size of the outlet. Instead, a myriad of factors may drive
online discourse: rapid user engagement [56], the reinforcing nature of echo
chambers [22], the amplifying power of influencers [57, 12], the emotional
resonance of content [18], and even artificial amplification via bots [58].
This complex web of drivers, some of which exhibit random behaviors, defies
conventional models of media influence. Indeed, understanding the dynamics of
the attention economy is pivotal for charting the trajectory of content
creators on platforms like Facebook. In this work, we analyze a massive
dataset composed of 57 million posts comprising the entire Facebook history,
spanning 15 years, of over 1000 news outlets. In particular, this study took a
deep dive into these dynamics, evaluating the applicability of Gibrat’s Law —
a principle traditionally applied to business growth — in social media content
creation. Empirical results provided a nuanced understanding of growth
patterns. We observe that the likelihood of generating viral content and
capturing widespread attention is independent of the information provider’s
size. Indeed, engagement adheres to a universal growth pattern in short-term
intervals. This pattern shifts as the analysis extends to longer timescales
like monthly and quarterly intervals, where size effects begin to manifest. We
validated this dynamic by comparing news outlets’ growth based on their
information quality, providing evidence on how, though the unreliability of
the news source negatively impacts engagement growth, its effect only
manifests in the long term. Another significant observation challenges
conventional wisdom: Followers count is not a sufficient indicator of a page’s
potential influence, and its actual impact only emerges over extended periods.
Our examination of growth dynamics further elucidated these insights. After
detecting their probability distributions, we evaluated their behavior
according to size and timescale. We developed a stochastic model validating
our empirical findings, emphasizing that Followers do not always depict actual
influence or engagement potential in the short term. This brings broader
implications in the context of agenda-setting dynamics in the social media
era. Our study shows that contrary to traditional media, influence is not
strictly tied to size or following in the digital realm. This stochastic
nature of short-term engagement suggests an environment where all content,
irrespective of its source, stands a roughly equal chance of capturing
attention, possibly elucidating the influence of algorithms on users’ news
consumption. This democratization of potential attention influences how
narratives and agendas are set, with even smaller entities having the power to
shape discourse. However, it also emphasizes the importance of vigilant
monitoring mechanisms, given the risk of rapid misinformation or harmful
content spread. Our research highlights the intricate dynamics of growth in
the digital attention economy, revealing how traditional metrics may not align
with real-world influence. It also offers key insights into how the modern
agenda-setting dynamics are being reshaped in the era of social media. These
findings are precious for content creators, platform designers, and
policymakers as they navigate the complexities of the digital age.

##  2 Materials and Methods

###  2.1 Selecting Followers’ value

In determining the Followers’ value for each time window, we selected the
closest observation to a given time point of the window, which we referred to
as a ’representative point in time’ since it varies depending on the
timescale. For the weekly scale, we selected the value on the minimum observed
date of the week. For the monthly scale, we selected the value of the closest
observed date to the central point of the month (the 15th day). For the
quarterly scale, we selected the value of the farther observed date.

### Labeling of Media Sources

The reliability labeling of news outlets is based on the trust ratings
provided by Newsguard [47]. Each site is rated using nine basic, apolitical
criteria of journalistic practice, related to credibility and transparency.
Based on the nine criteria, each site gets a trust score of 0-100 points.
NewsGuard labels the source as Trustable if the resulting score equals or
exceeds 60. The total number of news outlets for which we have a trust rating
is 1029.

### Parameters Estimation

Here we provide details about the fitting procedure of distributions reported
in Fig 2 of sections Analyzing Engagement and Followers Dynamics, and
Modelling Growth.

#### Laplace Distribution

The probability density function of the Engagement growth rate is the Laplace
distribution, expressed as:

$f_{L}(x|\mu,b)=\frac{1}{2b}\exp\left(-\frac{|x-\mu|}{b}\right),$ (8)

where $x\in\mathbb{R}$ and $\mu$ and $b$ are parameters to be calibrated. In
this respect, the parameters of the Laplace distribution can be derived
analytically from the mean $\mu_{X}$ and standard deviation $\sigma_{X}$ of
the empirical distribution $X$, since

$\displaystyle\mu=\mu_{X};\,b=\frac{\sigma_{X}}{\sqrt{2}}$ (9)

#### Burr Distribution

The probability density function for Followers’ growth is described by the
Burr distribution, whose density is:

$f_{B}(x|c,k)=ck\frac{x^{c-1}}{(1+x^{c})^{k+1}},$ (10)

where $x\in\mathbb{R}$ and $c$ and $k$ are scalars to be calibrated. In
particular, such parameters are evaluated by fitting the empirical cumulative
distribution function of the observed growth rates with the Burr’s one.

#### Regression of distribution parameters

To model parameters variation according to Followers and Engagement values, we
first applied the fitting procedure described above to the growth
distributions of the sub-samples obtained by binning based on Followers and
Engagement, after trimming within the 5th and 95th percentiles of our observed
distributions, in each timescale. After obtaining the parameters of the
Laplace and Burr distribution of each sub-sample, we performed the parameter
regression as described by equations [4], [5], [6], and [7], of section
Modelling growth.

### Sampling of reliable news outlets

According to NewsGuard ratings, our dataset comprises 898 reliable sources and
131 non-reliable ones. We performed a sampling of 131 reliable sources to have
two comparable samples. To obtain similar structural characteristics that are
not being tested, namely Followers and Page’s lifespan, the distance is
computed using the maximum number of Followers and the page’s creation date as
distance variables, since most pages’ last observations coincide with the end
of the analyzed period. The resulting sample is obtained by computing the
Euclidean distances of all the possible couples of Questionable and Reliable
pages in a two-dimensional space, using Followers and Lifespan as space
variables. Then we selected the partition of 131 Reliable pages for which the
sum of their Euclidean distances from the 131 Questionable pages was
minimized.

##  3 Funding

The work is supported by IRIS Infodemic Coalition (UK government, grant no.
SCH-00001-3391), SERICS (PE00000014) under the NRRP MUR program funded by the
European Union - NextGenerationEU, project CRESP from the Italian Ministry of
Health under the program CCM 2022, and PON project “Ricerca e Innovazione”
2014-2020.

##  4 Author contributions statement

E.S. and M.C. designed the paper; E.S. performed data collection and analysis;
M.C., R.C. and W.Q. supervised the project; All authors wrote the paper.

##  5 Data availability

The data collection and analysis process are compliant with the terms and
conditions imposed by Crowdtangle [48]. Therefore, the results described in
this paper cannot be exploited to infer the identity of the accounts involved.
CrowdTangle does not include paid ads unless those ads began as organic, non-
paid posts that were subsequently “boosted” using Facebook’s advertising
tools. It also does not include activity on private accounts, or posts made
visible only to specific groups of followers.

## References

  *   * Kümpel et al. [2015] Kümpel, A.S., Karnowski, V., Keyling, T.: News sharing in social media: A review of current research on news sharing users, content, and networks. Social media+ society 1(2), 2056305115610141 (2015)
  * Walker and Matsa [2021] Walker, M., Matsa, K.E.: News consumption across social media in 2021. Technical report, Pew Research Center (2021)
  * Flintham et al. [2018] Flintham, M., Karner, C., Bachour, K., Creswick, H., Gupta, N., Moran, S.: Falling for fake news: investigating the consumption of news via social media. In: Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems, pp. 1–10 (2018)
  * Bergström and Jervelycke Belfrage [2018] Bergström, A., Jervelycke Belfrage, M.: News in social media: Incidental consumption and the role of opinion leaders. Digital journalism 6(5), 583–598 (2018)
  * Schmidt et al. [2017] Schmidt, A.L., Zollo, F., Del Vicario, M., Bessi, A., Scala, A., Caldarelli, G., Stanley, H.E., Quattrociocchi, W.: Anatomy of news consumption on facebook. Proceedings of the National Academy of Sciences 114(12), 3035–3039 (2017)
  * Coleman et al. [2009] Coleman, R., McCombs, M., Shaw, D., Weaver, D.: Agenda setting. In: The Handbook of Journalism Studies, pp. 167–180. Routledge, ??? (2009)
  * Harder et al. [2017] Harder, R.A., Sevenans, J., Van Aelst, P.: Intermedia agenda setting in the social media age: How traditional players dominate the news agenda in election times. The international journal of press/politics 22(3), 275–293 (2017)
  * Feezell [2018] Feezell, J.T.: Agenda setting through social media: The importance of incidental news exposure and social filtering in the digital era. Political Research Quarterly 71(2), 482–494 (2018)
  * Russell Neuman et al. [2014] Russell Neuman, W., Guggenheim, L., Mo Jang, S.a., Bae, S.Y.: The dynamics of public attention: Agenda-setting theory meets big data. Journal of communication 64(2), 193–214 (2014)
  * Al-Rawi [2019] Al-Rawi, A.: Viral news on social media. Digital journalism 7(1), 63–79 (2019)
  * Cha et al. [2010] Cha, M., Haddadi, H., Benevenuto, F., Gummadi, K.: Measuring user influence in twitter: The million follower fallacy. In: Proceedings of the International AAAI Conference on Web and Social Media, vol. 4, pp. 10–17 (2010)
  * Bakshy et al. [2012] Bakshy, E., Rosenn, I., Marlow, C., Adamic, L.: The role of social networks in information diffusion. In: Proceedings of the 21st International Conference on World Wide Web, pp. 519–528 (2012)
  * Berger and Milkman [2012] Berger, J., Milkman, K.L.: What makes online content viral? Journal of marketing research 49(2), 192–205 (2012)
  * Barberá et al. [2019] Barberá, P., Casas, A., Nagler, J., Egan, P.J., Bonneau, R., Jost, J.T., Tucker, J.A.: Who leads? who follows? measuring issue attention and agenda setting by legislators and the mass public using social media data. American Political Science Review 113(4), 883–901 (2019)
  * Bessi et al. [2015] Bessi, A., Coletto, M., Davidescu, G.A., Scala, A., Caldarelli, G., Quattrociocchi, W.: Science vs conspiracy: Collective narratives in the age of misinformation. PloS one 10(2), 0118093 (2015)
  * Zollo et al. [2017] Zollo, F., Bessi, A., Del Vicario, M., Scala, A., Caldarelli, G., Shekhtman, L., Havlin, S., Quattrociocchi, W.: Debunking in a world of tribes. PloS one 12(7), 0181821 (2017)
  * Bakshy et al. [2015] Bakshy, E., Messing, S., Adamic, L.A.: Exposure to ideologically diverse news and opinion on facebook. Science 348(6239), 1130–1132 (2015)
  * Del Vicario et al. [2016a] Del Vicario, M., Vivaldo, G., Bessi, A., Zollo, F., Scala, A., Caldarelli, G., Quattrociocchi, W.: Echo chambers: Emotional contagion and group polarization on facebook. Scientific reports 6(1), 37825 (2016)
  * Del Vicario et al. [2016b] Del Vicario, M., Bessi, A., Zollo, F., Petroni, F., Scala, A., Caldarelli, G., Stanley, H.E., Quattrociocchi, W.: The spreading of misinformation online. Proceedings of the national academy of Sciences 113(3), 554–559 (2016)
  * Choi et al. [2020] Choi, D., Chun, S., Oh, H., Han, J., Kwon, T.T.: Rumor propagation is amplified by echo chambers in social media. Scientific reports 10(1), 310 (2020)
  * Nyhan et al. [2023] Nyhan, B., Settle, J., Thorson, E., Wojcieszak, M., Barberá, P., Chen, A.Y., Allcott, H., Brown, T., Crespo-Tenorio, A., Dimmery, D., et al.: Like-minded sources on facebook are prevalent but not polarizing. Nature 620(7972), 137–144 (2023)
  * Cinelli et al. [2021] Cinelli, M., De Francisci Morales, G., Galeazzi, A., Quattrociocchi, W., Starnini, M.: The echo chamber effect on social media. Proceedings of the National Academy of Sciences 118(9), 2023301118 (2021)
  * Briand et al. [2021] Briand, S.C., Cinelli, M., Nguyen, T., Lewis, R., Prybylski, D., Valensise, C.M., Colizza, V., Tozzi, A.E., Perra, N., Baronchelli, A., et al.: Infodemics: A new challenge for public health. Cell 184(25), 6010–6014 (2021)
  * Perra and Rocha [2019] Perra, N., Rocha, L.E.: Modelling opinion dynamics in the age of algorithmic personalisation. Scientific reports 9(1), 7261 (2019)
  * Guess et al. [2023] Guess, A.M., Malhotra, N., Pan, J., Barberá, P., Allcott, H., Brown, T., Crespo-Tenorio, A., Dimmery, D., Freelon, D., Gentzkow, M., et al.: How do social media feed algorithms affect attitudes and behavior in an election campaign? Science 381(6656), 398–404 (2023)
  * Valensise et al. [2023] Valensise, C.M., Cinelli, M., Quattrociocchi, W.: The drivers of online polarization: Fitting models to data. Information Sciences 642, 119152 (2023)
  * González-Bailón and Lelkes [2023] González-Bailón, S., Lelkes, Y.: Do social media undermine social cohesion? a critical review. Social Issues and Policy Review 17(1), 155–180 (2023)
  * González-Bailón et al. [2023] González-Bailón, S., Lazer, D., Barberá, P., Zhang, M., Allcott, H., Brown, T., Crespo-Tenorio, A., Freelon, D., Gentzkow, M., Guess, A.M., et al.: Asymmetric ideological segregation in exposure to political news on facebook. Science 381(6656), 392–398 (2023)
  * Simon and Greenberger [1971] Simon, H., Greenberger, M.: Computers, communications and the public interest. Computers, communications, and the public interest. Johns Hopkins Press, Baltimore, 40–41 (1971)
  * Davenport and Beck [2001] Davenport, T.H., Beck, J.C.: The attention economy. Ubiquity 2001(May), 1 (2001)
  * Falkinger [2007] Falkinger, J.: Attention economies. Journal of Economic Theory 133(1), 266–294 (2007)
  * Falkinger [2008] Falkinger, J.: Limited attention as a scarce resource in information-rich economies. The Economic Journal 118(532), 1596–1620 (2008)
  * Anderson and De Palma [2012] Anderson, S.P., De Palma, A.: Competition for attention in the information (overload) age. The RAND Journal of Economics 43(1), 1–25 (2012)
  * Weng et al. [2012] Weng, L., Flammini, A., Vespignani, A., Menczer, F.: Competition among memes in a world with limited attention. Scientific reports 2(1), 335 (2012)
  * Tufekci [2013] Tufekci, Z.: “not this one” social movements, the attention economy, and microcelebrity networked activism. American behavioral scientist 57(7), 848–870 (2013)
  * Lorenz-Spreen et al. [2019] Lorenz-Spreen, P., Mønsted, B.M., Hövel, P., Lehmann, S.: Accelerating dynamics of collective attention. Nature communications 10(1), 1759 (2019)
  * Bhargava and Velasquez [2021] Bhargava, V.R., Velasquez, M.: Ethics of the attention economy: The problem of social media addiction. Business Ethics Quarterly 31(3), 321–359 (2021)
  * Ciampaglia et al. [2015] Ciampaglia, G.L., Flammini, A., Menczer, F.: The production of information in the attention economy. Scientific reports 5(1), 9452 (2015)
  * Gibrat [1931] Gibrat, R.: Les inégalits économiques. Sirey (1931)
  * Rozenfeld et al. [2008] Rozenfeld, H.D., Rybski, D., Andrade Jr, J.S., Batty, M., Stanley, H.E., Makse, H.A.: Laws of population growth. Proceedings of the National Academy of Sciences 105(48), 18702–18707 (2008)
  * Eeckhout [2004] Eeckhout, J.: Gibrat’s law for (all) cities. American Economic Review 94(5), 1429–1451 (2004)
  * Rose [2005] Rose, A.K.: Cities and countries. National Bureau of Economic Research Cambridge, Mass., USA (2005)
  * Mansfield [1962] Mansfield, E.: Entry, gibrat’s law, innovation, and the growth of firms. The American economic review 52(5), 1023–1051 (1962)
  * Chesher [1979] Chesher, A.: Testing the law of proportionate effect. The Journal of industrial economics 27(4), 403–411 (1979)
  * Sutton [1997] Sutton, J.: Gibrat’s legacy. Journal of economic literature 35(1), 40–59 (1997)
  * Santarelli et al. [2006] Santarelli, E., Klomp, L., Thurik, A.R.: Gibrat’s law: An overview of the empirical literature. Entrepreneurship, growth, and innovation: The dynamics of firms and industries, 41–73 (2006)
  * [47] NewsGuard. https://www.newsguardtech.com (2023)
  * [48] CrowdTangle. CrowdTangle Team. Facebook, Menlo Park, California, United States (2023)
  * Plerou et al. [1999] Plerou, V., Amaral, L.A.N., Gopikrishnan, P., Meyer, M., Stanley, H.E.: Similarities between the growth dynamics of university research and of competitive economic activities. Nature 400(6743), 433–437 (1999)
  * Qian et al. [2014] Qian, J.-H., Chen, Q., Han, D.-D., Ma, Y.-G., Shen, W.-Q.: Origin of gibrat law in internet: Asymmetric distribution of the correlation. Physical Review E 89(6), 062808 (2014)
  * Stanley et al. [1996] Stanley, M.H., Amaral, L.A., Buldyrev, S.V., Havlin, S., Leschhorn, H., Maass, P., Salinger, M.A., Stanley, H.E.: Scaling behaviour in the growth of companies. Nature 379(6568), 804–806 (1996)
  * Amaral et al. [1997] Amaral, L.A.N., Buldyrev, S.V., Havlin, S., Leschhorn, H., Maass, P., Salinger, M.A., Stanley, H.E., Stanley, M.H.: Scaling behavior in economics: I. empirical results for company growth. Journal de Physique I 7(4), 621–633 (1997)
  * Burr [1942] Burr, I.W.: Cumulative frequency functions. The Annals of mathematical statistics 13(2), 215–232 (1942)
  * Fujiwara et al. [2003] Fujiwara, Y., Souma, W., Aoyama, H., Kaizoji, T., Aoki, M.: Growth and fluctuations of personal income. Physica A: Statistical Mechanics and its Applications 321(3-4), 598–604 (2003)
  * Fujiwara et al. [2004] Fujiwara, Y., Di Guilmi, C., Aoyama, H., Gallegati, M., Souma, W.: Do pareto–zipf and gibrat laws hold true? an analysis with european firms. Physica A: Statistical Mechanics and its Applications 335(1-2), 197–216 (2004)
  * Etta et al. [2023] Etta, G., Sangiorgio, E., Di Marco, N., Avalle, M., Scala, A., Cinelli, M., Quattrociocchi, W.: Characterizing engagement dynamics across topics on facebook. Plos one 18(6), 0286150 (2023)
  * Bakshy et al. [2011] Bakshy, E., Hofman, J.M., Mason, W.A., Watts, D.J.: Everyone’s an influencer: quantifying influence on twitter. In: Proceedings of the Fourth ACM International Conference on Web Search and Data Mining, pp. 65–74 (2011)
  * Cresci [2020] Cresci, S.: A decade of social bot detection. Communications of the ACM 63(10), 72–83 (2020)

##  6 Supporting Information

###  6.1 Data Collection

We download our data from CrowdTangle, a Facebook-owned tool that monitors
interactions on public content from Facebook pages, groups, and verified
profiles. CrowdTangle is accessible to researchers upon request at this link
https://www.crowdtangle.com/request. We obtain the list of news outlets
employed in the analysis via NewsGuard, which provides, for each outlet, more
than 30 distinct categories of descriptive metadata, including a breakdown of
their assessment, an indication of its political slant, descriptions of the
topics—or types of misinformation—it covers, and more. After selecting all the
news outlets with a Facebook account listed on NewsGuard, we use their
Facebook URLs to gather their data on CrowdTangle. Using the tool ’Historical
Data’ provided by CrowdTangle, we download the entire history of each page
from its creation date as a table containing information regarding each posted
item in chronological order.

###  6.2 Processing Methods

With a post-level granularity, the table’s columns include several relevant
fields, including the post type (link, image, video), its text, the number of
reactions to the post, and more. Among these columns, we select two relevant
ones: Total Interactions and Followers at Posting. The Total Interactions
column contains the total number of reactions per post (that is, the sum of
Likes, Comments, and Shares) that we aggregate (sum) depending on the time
scale of the analysis. The Total Interactions are thus our metric accounting
for the Engagement. These data are available for the whole page history, that
is, for the longest-running pages, from the beginning of 2008 to the end of
2022, when we downloaded data. Since pages’ creation dates span through time,
our analysis of growth rates is independent of the creation date once
accounted for a sufficient life span and activity of the page. The cumulative
time series regarding existing pages starting to be active on Facebook is
reported in panel A of Fig. 5. The number of pages included in the dataset is
1082, and 94 % of them were created before 01/01/2018. The second variable we
use for our analysis is Followers at Posting, which represents the number of
users subscribed to a given page at the time of posting. This information,
however, is only available for posts made since 01/01/2018. Before that day,
CrowdTangle was not collecting such information, or it is not sharing it with
end users as of now. For this reason, when we consider the metrics of
Followers and Engagement jointly, we restrict our analysis period to
01/01/2018 - 31/12/2022. In the analysis in which we do not account for
Followers’ value, we consider the entire 15-year timespan. Quantitatively
speaking, in panel B of Fig. 5, we report the evolution of the number of posts
we consider in the analysis, which is around 57 million, and the Total
Interactions, which is around 21 billion, over time. We note from 1/1/2018
onward, 63 % of posts and 56 % of Total Interactions were produced.

###  6.3 Test Results

Table S1 shows p-values of Mann-Whitney U tests between Questionable and
Reliable pages. The alternative hypothesis is that the distribution of
Reliable sources is right-shifted (higher mean) with respect to the
Questionable one. Engagement indicate the absolute value distributions,
Engagement growth indicate the growth rate ones. This comparison based on
information quality is consistent with overall evidence. The engagement growth
of unreliable pages progressively became negative as the time scale widens, in
Monthly and Quarterly scales, despite having constantly lower absolute
Engagement. Anew, the short-term fluctuations follow a universal dynamic, and
neither the reliability turns out to determine growth differences.

Timescale | p-value | Metric
---|---|---
Day | 0.00 | Engagement
Week | 0.00 | Engagement
Month | 0.00 | Engagement
Quarter | 0.00 | Engagement
Day | 0.32 | Engagement growth
Week | 0.10 | Engagement growth
Month | 0.00 | Engagement growth
Quarter | 0.00 | Engagement growth
Table 2: p-values of Mann-Whitney U tests between Questionable and Reliable
pages. H1: The distribution of Reliable sources is right-shifted (higher mean)
with respect to the Questionable one. Figure 5: (A) Pages’ creation across
time. (B) Evolution of the number of posts and Total Interactions over time.

Figure 6: Distributions of both possible size indicators, Followers and
Cumulative Engagement, of the entire sample at the start and end of our
analysis period. Both distributions manifest as heavy-tailed, here displayed
on a logarithmic scale. Figure 7: (A-B) Partitions of PAM clustering of news
outlets, based on Followers and Cumulative Engagement values at the start
(1/1/2018) and the end (31/12/2022) of our analysis period, respectively.
Solid vertical lines represent the range limits of our selected classes of
Followers. (C) Frequencies of the size classes across the analysis period.

Figure 8: (A-C) p-values of two-sided Mann-Whitney U tests between classes of
size for Followers and Engagement growth rate distributions. Panel titles
indicate the metric being tested and the metric according to which we
determine the size. Row and column headers represent the class size. Bold
numbers represent p-values for which we reject the hypothesis that the growth
distributions do not differ, with the alternative hypothesis that the true
location shift is not equal to 0. For readability, 0 represents p-values
smaller than 0.0001.

Figure 9: We recalculated the Engagement using its mean value and repeated the
tests reported in Fig. 1B and 1C. (A-C) p-values of two-sided Mann-Whitney U
tests between classes of size for Followers and Engagement growth rate
distributions. Panel titles indicate the metric being tested and the metric
according to which we determine the size. Row and column headers represent the
class size. Bold numbers represent p-values for which we reject the hypothesis
that the growth distributions do not differ, with the alternative hypothesis
that the smaller class grows at a higher rate. For readability, 0 represents
p-values smaller than 0.0001.

Figure 10: As the growth dynamic emerges clearly across the different
timescales, changing the bin boundaries should not lead to changes in the
results. We repeated the tests reported in Fig. 1B and 1C, dividing each
original bin into two sub-classes of an equal number of observations by
cutting the bin through its Median Followers Value. The independence of growth
from size in the short term still holds, with none of the 28 tests showing
differences in growth in both Daily and Weekly measurements. On the monthly
scale, the three smaller classes grow faster than the three bigger ones, while
on the quarterly scale, most tests show statistically significant p-values,
except for the pairs of adjacent classes. (A-C) p-values of two-sided Mann-
Whitney U tests between classes of size for Followers and Engagement growth
rate distributions. Panel titles indicate the metric being tested and the
metric according to which we determine the size. Row and column headers
represent the class size. Bold numbers represent p-values for which we reject
the hypothesis that the growth distributions do not differ, with the
alternative hypothesis that the smaller class grows at a higher rate. For
readability, 0 represents p-values smaller than 0.0001.

Figure 11: Laplace parameter variation with the increase of the observed
timescale for the four size classes. Upper panel represent $\mu$ parameter
variation, lower panel represent $b$ parameter variation. As upper panel
shows, $\mu\to 0$ with the narrowing of the observed timescale.

Figure 12: Scatterplot of Questionable and Reliable pages sub-sample.
According to NewsGuard ratings, our dataset comprises 898 reliable sources and
131 non-reliable ones. We performed a sampling of 131 reliable sources to have
two comparable samples. The resulting sample is obtained by selecting the
reliable pages for which the overall Euclidean distance from the non-reliable
sample is minimized. We aim to achieve similar structural characteristics that
are not being tested, namely Followers and Lifespan (here shown in days).
Therefore, we compute distance using the number of Followers and the page’s
creation date as distance variables since most pages’ last observations
coincide with the end of the analyzed period.


# Combining Power and Arithmetic Optimization via Datapath Rewriting

Samuel Coward1,2, Theo Drane1, Emiliano Morini1 and George A. Constantinides2
1 Intel Corporation, 2 Imperial College London,
Email: {samuel.coward, theo.drane<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Industrial datapath designers consider dynamic power consumption to be a key
metric. Arithmetic circuits contribute a major component of total chip power
consumption and are therefore a common target for power optimization. While
arithmetic circuit area and dynamic power consumption are often correlated,
there is also a tradeoff to consider, as additional gates can be added to
explicitly reduce arithmetic circuit activity and hence reduce power
consumption. In this work, we consider two forms of power optimization and
their interaction: circuit area reduction via arithmetic optimization, and the
elimination of redundant computations using both data and clock gating. By
encoding both these classes of optimization as local rewrites of expressions,
our tool flow can simultaneously explore them, uncovering new opportunities
for power saving through arithmetic rewrites using the e-graph data structure.
Since power consumption is highly dependent upon the workload performed by the
circuit, our tool flow facilitates a data dependent design paradigm, where an
implementation is automatically tailored to particular contexts of data
activity. We develop an automated RTL to RTL optimization framework, ROVER,
that takes circuit input stimuli and generates power-efficient architectures.
We evaluate the effectiveness on both open-source arithmetic benchmarks and
benchmarks derived from Intel production examples. The tool is able to reduce
the total power consumption by up to 33.9%.

##  1 Introduction

The three mostly common circuit quality metrics used in digital hardware
design are power, performance and area, abbreviated to PPA. The performance of
a circuit refers to how fast the circuit can execute the specified
computation, the area is a measurement of how much silicon the circuit
occupies on a die, which is highly correlated with manufacturing cost. Lastly,
power is a measurement of the energy per unit time used to perform a given
computation. The rise of custom accelerators presents the opportunity to
optimize arithmetic hardware designs for particular computations, allowing us
to perform those computations using less energy.

$A$$B$$C$$S$10out$*$ Figure 1: An operand isolation opportunity. In the
original circuit (black), the input to the multiplier can be data gated when
the select signal is one, as shown by the red gate. The negated select signal,
$\overline{S}$ is a common input to an array of AND gates equal to the
bitwidth of $C$.

Whilst performance and area are relatively simple to estimate, power can only
be estimated accurately knowing the data values being operated upon, e.g. via
representative workloads. The majority of power estimation tools in the
electronic design automation (EDA) industry are based on randomly generated or
real-world simulation stimuli [1, 2]. In this work, we focus on dynamic power
consumption that is influenced heavily by register transfer level (RTL)
design. From a simulation of a circuit design it is possible to infer bit-
level switching activity, that is the frequency of transitions of a bit from
zero to one or one to zero. These switching activities can be translated into
power consumption estimates via a power model.

Recently, Coward et al. developed an RTL rewriting framework to address both
area [3] and performance [4]. The core of their approach is an
e(quivalence)-graph representation of RTL that facilitates exploration of
these two metrics. In this work, we leverage this RTL rewriting framework and
complete the PPA axes. We encode power optimizations such as clock gating and
operand isolation via a set of local rewrites that, when combined with
arithmetic rewrites, facilitate the exploration of new design spaces and the
discovery of novel power efficient designs. We also exploit the compact
e-graph representation to develop a computationally efficient power model that
enables data-dependent circuit design. We develop a tool, ROVER, which can
customize an implementation based on representative workloads.

In Section 2 we provide background on RTL power analysis and optimization
along with an introduction to e-graphs. In Section 3 we describe how ROVER
encodes power optimizations in terms of RTL rewrites. We also describe ROVER’s
power model and how the compact representation provided by the e-graph yields
efficiency gains for RTL simulation. Lastly, in Section 4 we demonstrate
ROVER’s impact on power consumption on a set of benchmarks.

The paper contains the following novel contributions:

  * •

a set of local equivalence preserving RTL rewrites that capture power-specific
optimizations,

  * •

an encoding of clock gating and operand isolation that goes beyond current mux
tree analysis,

  * •

a computationally-efficient methodology to simulate a large set of design
choices, leveraging the compact e-graph representation,

  * •

an automated method for data-driven design.

##  2 Background

###  2.1 RTL Power Optimization and Analysis

Power optimizations can be broadly separated into two groups. First, a set of
optimizations that primarily target circuit area reduction, since there is a
correlation between circuit area and dynamic power consumption. This is
intuitive because a smaller circuit area corresponds to fewer gates and thus
fewer gates to toggle. Several previous works from both academia [5, 6, 7] and
industry [8] have explored datapath RTL area reduction, including one work
that used e-graph rewriting [3].

$D$$en$01Q

(a) A transparent register.

$A$$en\&B$01out

(b) An enabled register.

Figure 2: Circuit diagrams of the TREG and REG operators.

The second set of optimizations, which are the primary focus of this work,
detects opportunities to switch off, or gate, sub-circuits in the design.
Clock gating and operand isolation are two such optimizations. For a clock
gating example, consider a pipelined floating-point adder in which exception
cases, e.g. NaNs, are handled on a separate exception path. If we detect an
exceptional input in the first stage, we can gate all registers on the
standard input path for subsequent stages, since the result is redundant.
Gating the registers stops the register outputs changing and hence prevents
any toggling of the downstream combinational logic. The additional gating
logic adds an area (and possible delay) overhead which must be evaluated
alongside the data-dependent power saving. For an operand isolation example,
consider Figure 1. In this circuit we can identify a redundant operation and
construct an activation signal that we use to zero one of the multiplier
inputs, limiting operator power consumption. We refer to this technique as
data gating. Alternatively, both multiplier inputs could be “frozen” using
transparent registers to eliminate redundant toggling [9, 10]. The transparent
register shown in Figure 2a has an enable signal, which, when high, allows the
input to transparently flow through to the output and, when low, freezes the
output. Prior work has called this circuit a transparent latch, but since we
operate in a synchronous domain we shall instead call it a transparent
register.

In academia, clock gating has been explored at a gate-level [11] and from a
clock tree synthesis perspective [12]. A subset of industrial tools, such as
Synopsys Power Compiler [1] and Cadence Joules [2], are incorporated into the
logic synthesis engines and automatically perform clock-gating optimizations.
Siemens PowerPro [13] is a standalone RTL to RTL tool that targets sequential
clock gating. A limitation of these approaches is that they rely on analyzing
the mux tree structure of the RTL design, but this may miss opportunities as
we shall see in Section 3.2. The automation of operand isolation has been
explored at both the word-level [9] and at gate-level [10, 14]. An e-graph
based rewriting approach allows us to compare and combine these different
power optimization techniques.

RTL power analysis tools typically rely on simulation to estimate power
consumption of a given design. Tool users can either provide simulation
stimuli or set input switching activities and static probabilities [1, 2]. For
a given simulation period, the switching activity describes how frequently
each bit of the given signal transitions from zero to one or vice versa, and
the static probability specifies what proportion of the time that bit is
expected to be in the one state. Commercial logic synthesis tools [15], take
user provided simulation configurations and perform power optimizations guided
by the simulation.

This paper describes how to encode the power optimizations discussed above as
local RTL rewrites and a framework to explore the combination of power,
arithmetic and area optimizations. Our tool encodes arithmetic optimizations
performed by downstream synthesis tools in the optimization flow, a key factor
not considered by prior work. For analysis the underlying data structure of
our tool also enables efficient evaluation of the power consumption of
equivalent design candidates.

###  2.2 E-Graphs

(a) Initial e-graph contains $A\,\&\,\\{8\\{M\\}\\}$

(b) Apply rewrite
$A\&\\{8\\{M\\}\\}\rightarrow\texttt{TREG}(A,M)\&\\{8\\{M\\}\\}$

Figure 3: E-graph rewriting of a masking operation. Dashed boxes represent
e-classes of equivalent expressions. A new equivalent expression is added to
the e-graph represented by the second $\&$ operator in the root e-class. Input
Verilog ROVER Front-End VeriLang eggE-GraphSimulation Switching Activity Input
Stimuli RewriteExtraction VeriLang ROVER Back-End Optimized Verilog Figure 4:
ROVER’s power optimization tool flow. Users provide an input Verilog design
and input stimuli via simulation data or switching activity statistics.

An e-graph is typically initialized with a single expression, such that every
e-class contains a single node. The e-graph is grown via constructive rewrite
application, where a pattern, $l$, is matched in the e-graph and gets
rewritten to a different expression, $r$. The e-graph retains the original
expression $l$ in the data structure, $r$ is simply added to the matched
e-class. Figure 3 shows an example e-graph before and after applying a
rewrite. Given a set of rewrites, all rewrites are applied to the e-graph at
each rewriting iteration. Determining an optimal sequence of rewrite
applications is deferred to the extraction phase. We grow an e-graph until we
reach a computational limit or we reach a state called saturation, where
further rewriting adds no new nodes to the data structure. The final e-graph
represents a set of equivalent implementations. The process to select the
‘best’ implementation is known as extraction and is typically based on a
custom cost model for each application.

Coward, et al. introduced an intermediate language, VeriLang, that can
represent combinational RTL in an e-graph [3, 4]. We adopt the same
representation here, but extend it to incorporate registers, allowing us to
represent pipelined designs in the e-graph. Earlier work by the same authors
developed an RTL optimization tool using mixed precision RTL rewriting to
reduce circuit area and delay. We build on their framework as a foundation,
extending it to target power optimization. Our key insight is that their delay
optimization work [4], introduced ASSUME nodes to exploit the mux tree
structure of a design in an e-graph rewriting framework. The ASSUME node
associates code branches with observability don’t care conditions and allow
the e-graph to capture equivalence under some constraint, which they show to
be useful in identifying logic to accelerate special cases, e.g. near/far path
floating point addition. As noted above, observability don’t cares are also –
for other reasons – of central relevance to power-saving optimizations in RTL
datapath design, and we describe in this paper how to exploit that
commonality.

Recently, a general purpose and extensible e-graph library, egg, was released
[16]. egg provides a number of innovations in performance and e-graph features
that has led to applications in numerical stability improvement [17] and FPGA
multiplier design [7].

##  3 Methodology

In Figure 4 we provide an overview of how ROVER optimizes a design to reduce
power consumption. Using the ROVER front-end, an input Verilog design is
converted to VeriLang, which egg uses to initialize an e-graph [3]. ROVER then
applies a set of power optimization rewrites, described in Sections 3.1 and
3.2, to the e-graph, constructing a set of implementation candidates. To
accurately model per implementation power consumption, ROVER simulates the
entire e-graph based on user configured input stimuli as described in Section
3.3. The user configured input stimuli provide, for every module input, a
sequence of bitvectors that are fed one per clock cycle. Throughout this work,
we assume a single clock domain, for simplicity. E-graph simulation provides
switching activities for all the internal signals of all the candidates, which
are fed into the power model, described in Section 3.4. The power model is
used by ROVER to determine the optimal implementation, producing a VeriLang
expression. The ROVER back-end converts the extracted VeriLang expression into
Verilog.

In the original paper where VeriLang was introduced [3], the authors envisaged
its semantics as operating over Boolean values. In this work, we modify the
semantics of VeriLang to consider input variables as streams of Boolean data,
such that a new data point enters the module every clock cycle. Since we
consider streams of data, every intermediate signal created in the e-graph has
an associated stream. The semantics of combinational operators are such that
each clock cycle the new data points are used to generate a new output within
the same cycle.

We incorporate a new VeriLang operator, REG, which describes a register with
an enable signal. The corresponding circuit is shown in Figure 2b. Given input
$a$ and enable signal $en$ with associated data streams $a_{i}$ and $en_{i}$,
$\texttt{REG}(a,en)$ has the following semantics:

$\texttt{REG}(a_{i},en_{i})=\begin{cases}0&\text{, if }i==0\\\ a_{i-1}&\text{,
if }en_{i-1}\\\ \texttt{REG}(a_{i-1},en_{i-1})&\text{, else.}\\\ \end{cases}$
(1)

These semantics assume that a register is initialized to zero.

###  3.1 Data Gating

TABLE I:  A set of RTL rewrites encoding operand isolation and clock gating optimizations. We define four sets of operators such that op is any arithmetic or logical VeriLang operator, $\texttt{op1}\in\\{*,\ll,\gg,+,-\\}$, $\texttt{op2}\in\texttt{op1}\setminus\\{+,-\\}$ and op3 is any Boolean operator. We use $w_{a}$ to denote the bitwidth of a bitvector $a$, $w_{o}$ to denote the output bitwidth of an operation.  Group | Name | Left-Hand Side | Right-Hand Side
---|---|---|---
Data Gate | Gate Left | $s\,?\,b\,:\,c$ | $s\,?\,\left(b\,\&\,\\{w_{b}\\{s\\}\\}\right)\,:\,c$
Gate Right | $s\,?\,b\,:\,c$ | $s\,?\,b\,:\,\left(c\,\&\,\\{w_{c}\\{\overline{s}\\}\\}\right)$
Propagate Mask | $(a\;\texttt{op1}\;b)\,\&\,\\{w_{o}\\{s\\}\\}$ | $(a\,\&\,\\{w_{a}\\{s\\}\\})\;\texttt{op1}\;(b\,\&\,\\{w_{b}\\{s\\}\\})$
Propagate Mask Left | $(a\;\texttt{op2}\;b)\,\&\,\\{w_{o}\\{s\\}\\}$ | $(a\,\&\,\\{w_{a}\\{s\\}\\})\;\texttt{op2}\;b$
Propagate Mux Mask | $(s_{1}\,?\,a\,:\,b)\,\&\,\\{w_{o}\\{s_{2}\\}\\}$ | $s_{1}\,?\,(a\,\&\,\\{w_{a}\\{s_{2}\\}\\})\,:\,(b\,\&\,\\{w_{b}\\{s_{2}\\}\\})$
Propagate Mux Mask Right | $(s_{1}\,?\,a\,:\,b)\,\&\,\\{w_{o}\\{s_{2}\\}\\}$ | $s_{1}\&s_{2}\,?\,a\,:\,(b\,\&\,\\{w_{b}\\{s_{2}\\}\\})$
Propagate Mux Mask Left | $(s_{1}\,?\,a\,:\,b)\,\&\,\\{w_{o}\\{s_{2}\\}\\}$ | $s_{1}\,\|\,\overline{s_{2}}\,?\,(a\,\&\,\\{w_{a}\\{s_{2}\\}\\})\,:\,b$
Combine Masks | $(a\,\&\,\\{w_{a}\\{s_{1}\\}\\})\,\&\,\\{w_{a}\\{s_{2}\\}\\}$ | $a\,\&\,\\{w_{a}\\{s_{1}\&s_{2}\\}\\}$
Transparent Registers | Transp Reg Left | $s\,?\,b\,:\,c$ | $s\,?\,\texttt{TREG}{(b,s)}\,:\,c$
Transp Reg Right | $s\,?\,b\,:\,c$ | $s\,?\,b\,:\,\texttt{TREG}(c,\overline{s})$
Transp Reg Mask | $a\,\&\,\\{w_{a}\\{s\\}\\}$ | $\texttt{TREG}(a,s)\,\&\,\\{w_{a}\\{s\\}\\}$
Transp Reg Saturate | $a\,\|\,\\{w_{a}\\{s\\}\\}$ | $\texttt{TREG}(a,\overline{s})\,\|\,\\{w_{a}\\{s\\}\\}$
Transp Reg Reg | $\texttt{REG}(a,en)$ | $\texttt{REG}\left(\texttt{TREG}(a,en),en\right)$
Propagate | $\texttt{TREG}(a\;\texttt{op}\;b,s)$ | $\texttt{TREG}(a,s)\;\texttt{op}\;\texttt{TREG}(b,s)$
Propagate Mux | $\texttt{TREG}(s_{1}\,?\,a\,:\,b,s_{2})$ | $\texttt{TREG}(s_{1},s_{2})\,?\,\texttt{TREG}(a,s_{2})\,:\,\texttt{TREG}(b,s_{2})$
Combine Transp Reg | $\texttt{TREG}(\texttt{TREG}(a,s_{1}),s_{2})$ | $\texttt{TREG}(a,s_{1}\,\&\,s_{2})$
Clock Gate & Retime | Retime Boolean | $\texttt{REG}(a,en)\texttt{ op3 }\texttt{REG}(b,en)$ | $\texttt{REG}(a\texttt{ op3 }b,en)$
Clock Gate Reg | $\texttt{TREG}(\texttt{REG}(a,en),\texttt{REG}(b,en))$ | $\texttt{REG}(a,en\,\&\,b)$

In this section we describe a set of rewrites that encodes the operand
isolation optimizations described in Section 2.1. A key challenge in
expressing operand isolation via local rewrites, is that having identified a
redundant computation from a functional perspective we do not care what value
is produced under certain conditions. Therefore, from a functional
perspective, when we do not care, we can generate any value we choose.
However, the values that we select have a significant impact upon power
consumption.

Before progressing, we define notation used throughout. We let $w_{x}$ denote
the bitwidth of a bitvector variable $x$ and let $w_{o}$ denote the output
bitwidth of an operation. We use $\\{w\\{S\\}\\}$ to denote $w$-fold
replication of a bitvector $S$, which will usually be a single bit. Lastly, we
use $\overline{S}$ to denote the bitwise logical complement of a bitvector
$S$.

In one approach to perform operand isolation we can apply data gating to each
branch of a mux operator. Data gating creates a mask by duplicating a select
signal and applies a bitwise AND operation. This rewrite explicitly zeroes
redundant outputs. The first group in Table I contains rewrites to create
initial data gating operations. We include two “Gate” rewrites as we may wish
to data gate only the true branch, only the false branch or both, by applying
“Gate Left” and “Gate Right” in sequence. The rewrite from (2) to (3)
illustrates the creation of a mask and data gating of a mux branch, in order
to avoid dynamic power in the multiplier. Table I next describes how the data
gating operations are propagated over arithmetic operations, since these
operators typically account for the largest power consumption in datapath
circuits. The “Propagate” rewrites incrementally gate larger sub-circuits. For
a subset of operators, e.g. multiplication, it is equivalent to data gate a
single operand, as illustrated in (3) and (4). The rewrites in Table I encode
the optimization shown in Figure 1.

$\displaystyle S\;?\;A\,:\,(C*B)\hskip 49.79231pt\rightarrow\textit{ (Gate
Right)}$ (2) $\displaystyle
S\;?\;A\,:\,(C*B)\,\&\,\\{w_{o}\\{\overline{S}\\}\\}\rightarrow\textit{(Propagate
Left)}$ (3) $\displaystyle
S\;?\;A\,:\,(C\,\&\,\\{w_{c}\\{\overline{S}\\}\\})*B$ (4)

The impact of data gating redundant operations depends on the wider module
context. Exploring data gating via e-graph rewriting allows ROVER to retain a
set of gated and ungated designs, deferring architecture selection and
evaluation to the extraction phase. For example, in

$(s\,?\,f(a)\,:\,b)+g(f(a)),$ (5)

the computation of $f(a)$ appears redundant when $s$ is zero, however we
always use $f(a)$ in the computation of $g(f(a))$, thus there is no value in a
gated version.

Applying these rewrites to a nested mux structure, ROVER naturally generates
nested gating operations which are combined via classical Boolean rewriting.
Such an approach constructs observability don’t care conditions that are not
present in the original design. These newly created conditions can be
simplified using Boolean rewriting.

In addition to the rewrites described in Table I, ROVER deploys the arithmetic
and area optimization rewrites described in [3], that crucially encode
downstream logic synthesis optimizations. ROVER also includes standard Boolean
rewrites for optimizing logical expressions. Exploring these transformations
in parallel, ROVER discovers architectures providing an efficient area power
tradeoff.

###  3.2 Clock Gating

In the previous section, we described how data gating rewrites can encode
operand isolation. In this section, we shall describe a set of local
equivalence preserving rewrites that create transparent registers providing an
alternative way to achieve operand isolation. In (1) we defined the semantics
of REG. We define an additional VeriLang operator, TREG, representing a
transparent register, shown in Figure 2a, with semantics that are similar to
those of REG.

$\texttt{TREG}(a_{i},b_{i})=\begin{cases}a_{i}&\text{, if }b_{i}\\\
\texttt{TREG}(a_{i-1},b_{i-1})&\text{, elif }i>0\\\ 0&\text{,
else}\end{cases}$

The second group in Table I contains a set of rewrites, similar to the first
group, that encode the creation and propagation of TREG operators. We improve
upon approaches based on mux tree analysis by including the “Transp Reg
Mask/Saturate” rewrites that detect redundant computation, as used in Figure
3. We also create transparent registers from register enable signals, since
disabled registers correspond to redundant computation. The “Combine Transp
Reg” rewrite allows ROVER to construct complex observability don’t care
signals that may not be present in the initial design. These signals may be
simplified via Boolean rewriting.

In the final group in Table I, we describe how ROVER encodes clock gating via
local rewrites. When the TREG operator meets the output of a register, it
represents an opportunity to refine the enable condition of the register,
eliminating the overhead of the transparent register. We can prove the
equivalence of

$\displaystyle L_{i}$
$\displaystyle=\texttt{TREG}(\texttt{REG}(a_{i},en_{i}),\texttt{REG}(b_{i},en_{i}))\text{
and }$ $\displaystyle R_{i}$ $\displaystyle=\texttt{REG}(a_{i},en_{i}\&b_{i})$

for all clock cycles $i$ via induction. First, let

$p_{i}=\texttt{REG}(a_{i},en_{i})\text{ and
}q_{i}=\texttt{REG}(b_{i},en_{i}).$

Suppose $\forall i\leq k\;L_{i}=R_{i}$, then if $en_{k}=1$:

$\displaystyle q_{k+1}$ $\displaystyle=b_{k}\hskip 20.00003ptp_{k+1}=a_{k}$
$\displaystyle L_{k+1}$ $\displaystyle=q_{k+1}\,?\,p_{k+1}\,:\,L_{k}$
$\displaystyle=b_{k}\,\hskip 11.00008pt?\,a_{k}\,\hskip 10.00002pt:\,L_{k}$

Then, since $en_{k}=1$ and $R_{k}=L_{k}$,

$\displaystyle R_{k+1}$ $\displaystyle=en_{k}\&b_{k}\,?\,a_{k}\,:\,R_{k}$
$\displaystyle=\hskip 25.00003ptb_{k}\,?\,a_{k}\,:\,R_{k}=L_{k+1}$

Now if $en_{k}=0$, then $R_{k+1}=R_{k}=L_{k}$ and

$\displaystyle q_{k+1}$ $\displaystyle=q_{k}\hskip 20.00003ptp_{k+1}=p_{k}$
$\displaystyle L_{k+1}$ $\displaystyle=q_{k}\,?\,p_{k}\,:\,L_{k}$
$\displaystyle q_{k}=1\Rightarrow L_{k}$
$\displaystyle=q_{k}\,?\,p_{k}\,:\,L_{k-1}=p_{k}$

Therefore $L_{k+1}=L_{k}=R_{k+1}$ and hence $R_{k+1}=L_{k+1}$ for all values
of $en_{k}$. Under the zero register initialization assumption it is trivial
to prove $L_{0}=R_{0}$.

A key requirement of the “Clock Gate Reg” rewrite, is that the observability
don’t care condition be available in the previous clock cycle. This constraint
ensures that the register is disabled for the clock cycle corresponding to the
redundant computation. In certain cases, it may be necessary to move
operations into earlier clock cycles to ensure the gating signal is available
in the correct cycle. To transfer operations between clock cycles we implement
limited retiming of Boolean operators.

As described in Figure 4, ROVER applies all rewrites described to grow an
e-graph of equivalent implementations until a user defined limit or saturation
is reached. The final e-graph contains designs with different combinations of
gating and arithmetic optimizations. Determining which combination of
optimizations produce the most power efficient design is left to extraction,
which we describe next.

###  3.3 Simulation

In order to analyze power consumption, ROVER must first simulate all designs
within the e-graph based on a set of stimuli. ROVER takes an additional input
configuration file that provides simulation stimuli or sets the switching
activity for each module input. If the user only defines a switching activity
and simulation length, ROVER automatically generates simulation stimuli for
all module inputs using an algorithm that randomly toggles each bit in a
bitvector according to the configured toggle rate.

Since all nodes in a given e-class are functionally equivalent, ROVER
simulates one node per e-class to obtain simulation data for the entire class.
This observation provides a significant computational efficiency gain, as the
complexity of simulating all designs in the e-graph scales with the number of
e-classes. Meanwhile, the number of distinct designs contained in the e-graph
can grow exponentially with the number of classes [7], as shown for the
example of Figure 1 in Figure 5. In this example, the number of e-classes
grows by a factor of four whilst the number of designs grows by a factor of
1000. The number of e-classes in Figure 5 does not grow monotonically, since
in later rewriting iterations e-classes get merged due to proof of equivalence
generated by ROVER reducing the number of classes. Note that, whilst a single
node evaluation can be shared across the e-class, each node in the e-class may
require more or less power to produce that same value. For example, $x+x$ and
$x\ll 1$ are functionally equivalent but may consume significantly different
power. It is this difference our extraction is designed to estimate and
exploit.

From the e-class simulation data, ROVER calculates an average switching
activity across the entire output word of that e-class. For example, for a
3-bit word with switching activities of 0.25 for bit 0, 0.5 for bit 1 and 0.75
for bit 2 would average to 0.5 across the entire word.

$8$$10$$12$$14$$16$$18$$20$$22$$24$$26$$28$$30$$32$$34$$36$$38$$40$$42$$44$$-100$$0$$100$$200$$300$$400$$500$$600$$700$$800$$900$$1{,}000$$1{,}100$Number
of E-ClassesNumber of Designs

Figure 5: The number of designs vs. the number of e-classes after each
iteration of rewriting the design in Figure 1. Simulation complexity scales
with the number of e-classes but evaluates all designs in the e-graph.

###  3.4 Operator Power Model

The purpose of the power model is to order the candidate implementations so
that ROVER can select the most power efficient design. The e-graph simulation
provides us with an average word-level switching activity for each e-class.

It is a known challenge to accurately estimate operator power consumption
based on a word-level RTL implementation as it is highly dependent on
downstream transformations and library selection [18]. ROVER mitigates this by
encoding certain high-level datapath optimizations, such as arithmetic
clustering [8], in the e-graph [3]. In this work, we combine the existing
theoretical circuit area model from [3] with the simulated switching activity
statistics to estimate the number of two-input gates toggling per clock cycle.
For each node $n$ in a given e-class $c$ with child e-classes
$c_{0},\cdots,c_{k-1}$, we compute a power estimate, $P(n)$.

$P(n)=A(n)\times\frac{1}{k+1}\left(T_{c}+\sum_{i=0}^{k-1}T_{c_{i}}\right)$ (6)

where, $A(n)$ is an estimate of the number of two-input gates required to
synthesize that operator, and $T_{c}$ and $T_{c_{i}}$ are the operator’s
output and input toggle frequencies, respectively. For arithmetic operators
the area model fixes an architecture, based on known logic synthesis
implementations, following the methodology described in [3]. The area model
accounts for operand bitwidths and constant operands. The power model assigns
an equal weight to input and output switching activities to approximate the
proportion of the gates which transition each cycle. We do not model wire
power consumption. In Section 4 we evaluate how accurately ROVER’s model is
able to estimate power consumption.

As in previous works on RTL optimization using e-graphs, to correctly account
for common sub-expressions, we formulate extraction as an integer linear
programming (ILP) problem [3]. Leting $N$ denote the set of e-graph nodes, we
use Boolean variables $x_{n}$ to encode whether we select a particular node
$n$ and minimize,

$\sum_{n\in N}x_{n}\times P(n).$ (7)

Additional constraints ensure that we extract a valid implementation computing
all the module outputs [3].

##  4 Results

TABLE II: Logic synthesis results comparing the average total power consumption and average area across several delay targets. We compare the baseline, against two implementations generated by ROVER, one targeting area optimization and one targeting power optimization. We bold the best result for each metric. We report the relative change vs the baseline and highlight our new contribution in blue. We include the number of nodes in the initial e-graph for each benchmark. Benchmark | Nodes | Baseline | Area Optimized | Power Optimized
---|---|---|---|---
Area ($\mu m^{2}$) | Power ($\mu W$) | Area ($\mu m^{2}$) | Power ($\mu W$) | Area ($\mu m^{2}$) | Power ($\mu W$)
Comb. Mux Add Tree | 20 | 32.9 | 98.2 | 32.8 (\- 0.4%) | 98.8 (\+ 0.5%) |  31.0 (\- 7.4%) |  83.2 (-15.5%)
Address Generation | 22 | 58.5 | 421.9 |  57.1 (\- 0.2%) | 419.2 (-0.6%) | 57.2 (\+ 2.2%) |  301.2 (-28.7%)
Weight Calculation | 81 | 51.6 | 1141.4 |  46.4 (-10.2%) | 1072.3 (-6.1%) | 53.3 (\+ 3.2%) |  871.5 (-23.7%)
Pipe. Mux Add Tree [9] | 23 | 38.6 | 852.3 |  38.6 ( 0.0%) | 852.3 ( 0.0%) | 44.1 (+14.9%) |  615.3 (-27.2%)
Dual Op ALU [10] | 17 | 6.5 | 186.9 |  6.5 ( 0.0%) | 186.9 ( 0.0%) | 7.5 (+15.1%) |  146.8 (-21.3%)
Sequential Reg [13] | 13 | 12.4 | 579.6 |  12.4 ( 0.0%) | 579.6 ( 0.0%) | 12.8 (\+ 2.9%) |  383.0 (-33.9%)
Dual Path FP Sub [4] | 62 | 27.8 | 1097.1 |  27.8 ( 0.0%) | 1097.1 ( 0.0%) | 29.0 (\+ 3.5%) |  929.4 (-14.9%)

To evaluate ROVER’s impact on dynamic power consumption, we gathered two sets
of benchmarks as shown in Table II. The first set of three benchmarks are
provided by Intel. The “Combinational Mux Add Tree”, is taken from Intel low
power training materials and comprises of three adders and three muxes. The
example demonstrates how the dataflow graph can be rearranged to move
particularly high toggling signals towards the outputs, reducing toggling in
the rearranged circuit. The second benchmark, “Address Generation”, is a
snippet from production code, which is used as an example of how to perform
power optimization in the training materials. It is comprised of two adders, a
multiplier and a pair of muxes. The third benchmark, “Weight Calculation”, is
a production two-stage pipelined design computing pixel offsets in the
graphics pipeline.

The second set of benchmarks are taken from prior publications [10, 9, 4, 13].
The “Pipelined Mux Add Tree” [9] is similar to the “Combinational Mux Add
Tree” but introduces a distinct pipelined structure. It is comprised of two
adders, three muxes and a pair of registers. The “Dual Path ALU” design [10]
can optionally perform either a shift or addition. Next, the “Sequential Reg”
benchmark is used in the PowerPro white paper to demonstrate the tool’s
sequential clock gating capabilities. It is a combination of registers and a
mux. The “Dual Path FP Sub” is a pipelined floating point subtractor with a
near/far path split [4].

For each design, we pass ROVER the original System Verilog design, which does
not contain any existing power optimizations, along with a json file that
specifies the input switching activities. We run ROVER twice generating an
area optimized and a power optimized design in System Verilog and an estimate
of the power reduction according to ROVER’s power model. Using a commercial
logic synthesis tool targeting a TSMC 5nm cell library, we synthesize the
original and ROVER generated designs at a range of delay targets to mitigate
the impact of logic synthesis noise [3]. We provide the commercial tool with
the same switching activity configuration as given to ROVER. In Table II, we
show the average circuit area and average total power consumption (including
leakage power) reported by the synthesis tool across the range of delay
targets. The commercial synthesis tool incorporates a power analysis and
optimization tool, which provides relevant power estimates based on the
switching activities configured. To ensure the correctness, we verify the
cycle-accurate equivalence of the original and ROVER generated designs using a
commercial formal equivalence checking tool.

###  4.1 Dynamic Power Reduction

Table II compares total power and area results for each of the benchmarks
before and after ROVER optimization. ROVER reduces total power consumption by
up to 33.9% and 23.6% on average at the expense of an average 5.0% increase in
circuit area. The reported power reduction is for a representative set of
switching activity configurations. The area optimized designs do not
demonstrate the same power reduction but show some limited area improvements.
For several designs the area optimization could not find any improvement,
returning the baseline implementation. Whilst ROVER only models dynamic power,
we evaluate based on total power, including leakage power.

To best understand the benefit of exploring arithmetic, area and power in
tandem, we study an open-source benchmark. Figure 6 shows the circuits
corresponding to the baseline “Pipelined Mux Add Tree”, the design proposed in
[9] and the ROVER generated version. The optimizations proposed in [9] add
transparent registers to both adder inputs, as this work only added operators.
Meanwhile, ROVER performs an entirely different optimization, re-ordering the
dataflow graph to push the adders towards the output of the circuit. Note that
the ROVER generated design contains a three input adder, which, thanks to
ROVER’s comprehension of logic synthesis optimizations, is recognised as only
a single carry-save adder, rather than two full carry-propagate adders. ROVER
then inserts area efficient data gating on the adder inputs to save power.
Synthesizing the design proposed in [9], the ROVER generated architecture is
strictly better, consuming 11% less power within 17% less area.

For the “Combinational Mux Add Tree” ROVER once again re-orders the mux tree
converting three separate adders to one single adder taking four inputs. This
differs from the solution proposed in the Intel training materials. ROVER’s
design reduces both power and area by 10% when compared to the design proposed
in the training materials. In the “Address Generation” benchmark, ROVER
deploys data gating as recommended by the training material, but also an
optimization to combine two adders into one three input adder. This area
optimization offsets the overhead of the gating operators, leading to only a
2.2% increase in area. For the “Dual Op ALU” and “Sequential Reg” benchmarks,
ROVER is able to rediscover the optimizations proposed in [10] and [13],
demonstrating ROVER’s ability to generalize prior work. Lastly, ROVER
recognises the distinct computational paths in the “Dual Path FP Sub” and
inserts the appropriate clock gating for each path.

$A$$B$$x$$y$$C$$D$$E$$F$$S_{0}$$S_{1}$$S_{2}$$G_{0}$$G_{1}$$+$$+$ (a) Baseline
design (black). In [9] the authors add the transparent registers (red), where
$x=(\overline{S_{2}}\&G_{0})\|(S_{0}\&\overline{S_{1}}\&G_{1})$ and $y=G_{1}$.

$A$$B$$C$$D$$E$$z$$w$$F$$S_{0}$$S_{1}$$S_{2}$$G_{0}$$G_{1}$$+$$+$ (b) ROVER
generated design. ROVER rearranged the mux tree and added data gating (red),
where $w=\overline{S_{2}}\&G_{0}$ and $z=G_{1}\&\overline{S_{1}}\&S_{0}$.

Figure 6: Circuit diagrams of the “Pipelined Mux Add Tree” benchmark with
power optimizations from prior work and from ROVER.

For all but two benchmarks ROVER ran in less than 10 seconds, taking only a
few seconds for the majority. For the “Address Generation” and “Weight
Calculation” benchmarks ROVER ran for 130 seconds and 160 seconds,
respectively. These long running cases were dominated by the ILP solver.
Comparing the reduction in power consumption predicted by ROVER’s model
against the actual impact reported by logic synthesis, we see that for a group
of five benchmarks the model provides a relevant estimate of the power
reduction, within 14 percentage points of the actual. However, for the
“Combinational Mux Add Tree” and “Address Generation” the model overestimates
the improvement in power consumption by around 45 percentage points. We
attribute this to two causes. First, for both benchmarks, the area model
predicted an area reduction that was not realized. Second, the power model
uses only a simple linear relationship between operator power and toggle
frequencies.

###  4.2 Data Dependent Design

To demonstrate how ROVER is capable of tailoring the implementation to the
computation, we study how ROVER’s output changes as we modify the switching
activities of mux select and register enable signals. We focus on the
“Pipelined Mux Add Tree” as shown in Figure 6. In Table III we pass ROVER four
different switching activity configurations and report the optimizations
selected by ROVER for each. Given Cfg. 1, ROVER elects to insert data gating
using the $S_{0},S_{1},S_{2}$ and $G_{1}$ signals. Given Cfg. 3, where we
increase the switching activity for all signals, ROVER instead elects to
insert a single transparent register. In Cfg. 4, we see ROVER use the $G_{0}$
signal to data gate, which we do not see in other configurations. The final
columns show how the power benefit of ROVER’s optimizations varies with
switching activities.

TABLE III: Each row represents a different switching activity configuration (Cfg.) for the mux select and register enable signals in the “Pipelined Mux Add Tree” (Figure 6a). For each Cfg., if ROVER inserted a data gate (transparent register) using one of these signals, we color the corresponding cell green (purple). | Muxes | Registers | Total Power (mW)
---|---|---|---
Cfg. | $S_{0}$ | $S_{1}$ | $S_{2}$ | $G_{0}$ | $G_{1}$ | Baseline | ROVER
1 | 0.1 | 0.1 | 0.1 | 0.1 | 0.1 | 1.09 | 0.76 (-30%)
2 | 0.1 | 0.1 | 0.1 | 0.8 | 0.8 | 1.09 | 0.95 (-14%)
3 | 0.8 | 0.8 | 0.8 | 0.8 | 0.8 | 1.30 | 1.15 (-11%)
4 | 0.8 | 0.8 | 0.8 | 0.1 | 0.1 | 1.29 | 1.03 (-20%)

##  5 Conclusions and Future Work

This paper describes how to encode power optimizations, such as operand
isolation and clock gating, as local equivalence preserving rewrites. By
phrasing power reduction as a rewrite problem we can combine it with existing
arithmetic rewrites to explore both power and area in tandem. We developed an
e-graph based rewriting framework, ROVER, that can simultaneously explore and
balance the area-power tradeoff. The e-graph enables efficient simulation of
many functionally equivalent implementations as we only need to simulate one
node from each class. Optimizing a set of benchmarks using ROVER we see a
23.6% reduction in total power consumption on average for just an average
circuit area increase of 5.0%. We show the importance of ROVER’s understanding
of downstream logic synthesis optimizations, leading to designs not seen in
prior work.

Whilst ROVER is able to generalize the majority of optimizations discussed in
prior work, the optimization presented in Figure 6a, is not expressible via
the current set of rewrites. We can describe this as a resource sharing
problem, a general optimization that future work on e-graph rewriting will
address. We will also automatically derive useful case-splits from simulation
stimuli to insert into the RTL.

## References

  * [1] Synopsys, “Power Compiler,” 2023. [Online]. Available: https://www.synopsys.com/implementation-and-signoff/rtl-synthesis-test/power-compiler.html
  * [2] Cadence, “Joules RTL Power Solution,” 2023. [Online]. Available: https://www.cadence.com/en_US/home/tools/digital-design-and-signoff/power-analysis/joules-rtl-power-solution.html
  * [3] S. Coward, G. A. Constantinides, and T. Drane, “Automatic Datapath Optimization using E-Graphs,” in _IEEE 29th Symposium on Computer Arithmetic (ARITH)_. IEEE, 9 2022, pp. 43–50.
  * [4] S. Coward, G. Constantinides, and T. Drane, “Automating Constraint-Aware Datapath Optimization using E-Graphs,” in _Design Automation Conference_ , 2023.
  * [5] A. K. Verma, P. Brisk, and P. Ienne, “Data-flow transformations to maximize the use of carry-save representation in arithmetic circuits,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , vol. 27, no. 10, pp. 1761–1774, 2008.
  * [6] F. De Dinechin, S. I. Filip, M. Kumm, and A. Volkova, “Towards Arithmetic-Centered Filter Design,” in _Proceedings - Symposium on Computer Arithmetic_ , vol. 2021-June, 2021.
  * [7] E. Ustun, I. San, J. Yin, C. Yu, and Z. Zhang, “IMpress: Large Integer Multiplication Expression Rewriting for FPGA HLS,” in _2022 IEEE 30th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)_ , 2022, pp. 1–10.
  * [8] R. Zimmermann, “Datapath synthesis for standard-cell design,” in _Proceedings - Symposium on Computer Arithmetic_ , 2009.
  * [9] M. Münch, B. Wurth, R. Mehra, J. Sproch, and N. Wehn, “Automating RT-level operand isolation to minimize power consumption in datapaths,” in _Proceedings Design, Automation and Test in Europe Conference and Exhibition 2000_ , 2000.
  * [10] V. Tiwari, S. Malik, and P. Ashar, “Guarded evaluation: pushing power management to logic synthesis/design,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , vol. 17, no. 10, 1998.
  * [11] A. P. Hurst, “Automatic synthesis of clock gating logic with controlled netlist perturbation,” in _Proceedings - Design Automation Conference_ , 2008.
  * [12] M. Donno, A. Ivaldi, L. Benini, and E. Macii, “Clock-tree power optimization based on RTL clock-gating,” in _Proceedings - Design Automation Conference_ , 2003.
  * [13] Siemens Digital Industries Software, “Automatic sequential clock gating with PowerPro,” 2021.
  * [14] T. T. Hoang and P. Larsson-Edefors, “Data-width-driven power gating of integer arithmetic circuits,” in _Proceedings - 2012 IEEE Computer Society Annual Symposium on VLSI, ISVLSI 2012_ , 2012.
  * [15] Synopsys, “Design Compiler User Guide S-2021.06-SP2,” Synopsys, Mountain View, Tech. Rep., 6 2021.
  * [16] M. Willsey, C. Nandi, Y. R. Wang, O. Flatt, Z. Tatlock, and P. Panchekha, “Egg: Fast and extensible equality saturation,” in _Proceedings of the ACM on Principles of Programming Languages_ , vol. 5, no. POPL, 2021.
  * [17] P. Panchekha, A. Sanchez-Stern, J. R. Wilcox, and Z. Tatlock, “Automatically improving accuracy for floating point expressions,” _ACM SIGPLAN Notices_ , vol. 50, no. 6, pp. 1–11, 2015.
  * [18] S. Reda and A. N. Nowroz, “Power modeling and characterization of computing devices: A survey,” _Foundations and Trends in Electronic Design Automation_ , vol. 6, no. 2, 2012.