# Assessing the impact of Higher Order Network Structure on Tightness of OPF
Relaxation

Nafis Sadik,∗ and Mohammad Rasoul Narimani,† This work was supported by NSF
under Award Number 2308498.${\ast}$: College of Engineering and Computer
Science, Arkansas State University<EMAIL_ADDRESS>Department
of Electrical and Computer Engineering, California State University Northridge
(CSUN<EMAIL_ADDRESS>
###### Abstract

AC optimal power flow (AC OPF) is a fundamental problem in power system
operation and control. Accurately modeling the network physics via the AC
power flow equations makes AC OPF a challenging nonconvex problem that results
in significant computational challenges. To search for global optima, recent
research has developed a variety of convex relaxations to bound the optimal
objective values of AC OPF problems. However, the quality of these bounds
varies for different test cases, suggesting that OPF problems exhibit a range
of difficulties. Understanding this range of difficulty is helpful for
improving relaxation algorithms. Power grids are naturally represented as
graphs, with buses as nodes and power lines as edges. Graph theory offers
various methods to measure power grid graphs, enabling researchers to
characterize system structure and optimize algorithms. Leveraging graph
theory-based algorithms, this paper presents an empirical study aiming to find
correlations between optimality gaps and local structures in the underlying
test case’s graph. Network graphlets, which are induced subgraphs of a
network, are used to investigate the correlation between power system topology
and OPF relaxation tightness. Specifically, this paper examines how the
existence of particular graphlets that are either too frequent or infrequent
in the power system graph affects the tightness of the OPF convex relaxation.
Numerous test cases are analyzed from a local structural perspective to
establish a correlation between their topology and their OPF convex relaxation
tightness.

###### Index Terms:

Optimal power flow, Convex relaxation, Network graphlets

##  I Introduction

The optimal power flow (OPF) problem seeks an operating point that optimizes a
specified objective function (often generation cost minimization) subject to
constraints from the network physics and engineering limits. Using the
nonlinear AC power flow model to accurately represent the power flow physics
results in the AC OPF problem, which is non-convex, generally NP-Hard problems
[1] and may have local optima [2]. The inclusion of AC power flow in the OPF
problem presents non-convex feasible spaces, leading to considerable
computational complexity [3, 4]. Many convex relaxation techniques have been
used to solve OPF problems [5]. These relaxation techniques converge to a
lower bound for the OPF problem. In some cases if the relaxation solution
satisfies specific condition, the calculated lower bound by relaxation method
can be inferred as the global solution of the problem. An optimality gap can
be referred as the percent difference between the objective values for a local
solution and the lower bound obtained by relaxation techniques. A relatively
smaller optimality gap certifies global optimal solution of corresponding
local solution [6].

Many research efforts have been done in the past decades to develop convex
relaxation algorithms for NP-hard, non-convex problems [7]. Numerous
relaxation techniques including Semi-definite programming (SDP) [8], second
order cone programming (SOCP) [9], quadratic convex relaxation (QC) [10]. QC
relaxation encloses the trigonometric, squared, and product terms in a polar
representation of power flow equations within convex envelopes [10]. We
utilized the QC relaxation in this paper for investigating correlation between
relaxation optimality gap and topology of the test cases.

The correlation between power systems and graph theory is strong, as graph
theory provides a powerful tool for analyzing and optimizing complex power
systems. This correlation was first explored in [11]. Graph theoretical
analysis approach have been used in many power system applications such as
system vulnerability [12, 13], detecting structural anomalies [14],
identifying critical components in power systems [15, 16, 17], and generating
authentic synthetic grids [18]. In the mean time, some research has been done
on optimal power flow problem with the perspective from network science.
According to [19], power flow in power networks can be traced by using graph
theoretical algorithms such as breadth first search and depth first search.
Connection between cliques and semi-definite solver performance is discussed
in [20] and it is suggested that semi-definite constraints can be decomposed
into smaller constraints according to maximal cliques of the power network. In
addition, to make the SDP relaxation problem easier to solve, identifying the
problematic lines that contribute to its computational complexity is crucial.
This can be accomplished by using graph theory techniques, such as tree
decomposition, to analyze the structure of the graph and identify those lines,
as described in [21]. Though not focused in optimal power flow, the
relationship between the network topology, as characterized by the maximal
cliques, and the number of power flow solution has been explored in [22]. More
recently, graph neural networks are gaining attention to solve OPF problems.
Particularly, graph neural networks can be used to approximate optimal
interior point optimizer solution in OPF [23]. However, to the best of our
knowledge, no studies have investigated the correlation between the optimality
gap of OPF relaxations and the local structures of the underlying power grid’s
graph in power system test cases.

Graphlets and motifs are essential tools in complex network analysis. They are
subgraphs that occur frequently in a given network and can provide insights
into the network’s structure and function. Graphlets are small, connected
subgraphs that can be used to characterize the local structure of a network.
Motifs are larger subgraphs that occur more frequently than expected by chance
and can represent functional units in the network. By identifying and
analyzing graphlets and motifs, researchers can gain a deeper understanding of
the network’s organization and dynamics, and identify key nodes or pathways
that are critical to the network’s function. Graphlet and motif analysis can
be used to identify similarities and differences, and classify networks based
on their structure and function. Use of network motifs statistically to
extract information about the local structure of the data was first proposed
in [24]. At first, analysis of motif detection in a network was exclusively
restricted in the field of bio-informatics [25] [26]. Using network motifs,
comparative grid vulnerability analysis in case of contingency has been
discussed in [27] and it was found that vulnerable and robust grid have
different motif patterns and decay of motifs also reveals a different pattern
when comparing robust and fragile grids. What these local structure of a grid
network means to a power grid in case of a contingency has already been
discussed [28] and it has been found that certain motifs did play determining
the robustness of a network.

This paper first explores network graphlet patterns across various test cases
and next determines the optimality gaps for QC relaxation in those OPF test
cases. In particular, we attempt to ascertain if there is any connection
between the local structure of the network and the subsequent OPF optimality
gap for that specific network. To be more specific, this paper delves deeper
to discover if any graphlets contribute to a larger optimality gap in OPF test
cases. By identifying graphlets that contribute to a larger optimality gap in
test cases, we can identify important nodes in test systems, wherein enforcing
redundant constraints on them reduces the optimality gap for those test cases.
Moreover, such analysis can lead to the development of more effective
optimization algorithms tailored to specific network topologies and
requirements. Thus, identifying significant graphlets that contribute to
larger optimality gaps can ultimately lead to the development of more
efficient and reliable network infrastructures.

This paper is organized as follows. Sections II and III review the OPF
formulation and the QC relaxation, respectively. Section IV describes the
network graphlet theory. Section V then presents an algorithm by which
graphlets will be detected. Section VI discusses the numerical result and
Section VII concludes the paper.

##  II Overview of the Optimal Power Flow Problem

This section formulates the OPF problem using a polar voltage phasor
representation. Let’s assume voltage at bus $i$ and $j$ are $V_{i}$ and
$V_{j}$, respectively. Current flowing from bus $i$ to bus $j$ is $I_{ij}$, AC
power generation of bus $i$ is $S_{i}^{g}$, complex power demand of bus $i$ is
$S_{i}^{d}$ and complex power flowing from bus $i$ to bus $j$ is $S_{ij}$. $E$
and $F$ are the set of sending and receiving ends of lines, i.e. edges,
respectively. $Y_{ij}$ is the admittance of line $i$ to $j$. Power flow
equation for all buses can be written as follows.

$\displaystyle S_{i}^{g}-S_{i}^{d}=\sum_{\begin{subarray}{c}(i,j)\in\ {E\cup
F}\end{subarray}}\\!S_{ij}\quad\forall i\in\mathcal{\text{N}}$ (1a)
$\displaystyle
S_{ij}=Y_{ij}^{*}V_{i}V_{i}^{*}-Y_{ij}^{*}V_{i}V_{j}^{*}\quad(i,j)\in E\cup F$
(1b)

The OPF problem consists of different engineering constraints that should be
enforced along with the power flow equations. Generators in the system should
produce active and reactive power within their limits which can be addressed
by following constraints.

$\displaystyle S_{i}^{gl}\leq S_{i}^{g}\leq S_{i}^{gu}\quad\forall
i\in\mathcal{\text{N}}$ (2)

Line thermal limit is another constraint that enforces an upper bound on
apparent power flow in lines.

$\displaystyle|S_{ij}|\leq s_{ij}^{u}\quad\forall i\in\mathcal{\text{N}}$ (3)

Bus voltage limits of any grid are defined by national grid code of any
country and it is typically $\pm 10\%$ of nominal grid voltage [29].

$\displaystyle v_{i}^{l}\leq|V_{i}|\leq v_{i}^{u}\quad\forall
i\in\mathcal{\text{N}}$ (4)

For ease of power flow formulation squaring this equation gives us,

$\displaystyle{v_{i}^{l}}^{2}\leq{|V_{i}|}^{2}\leq{v_{i}^{u}}^{2}\quad\forall
i\in\mathcal{\text{N}}$ (5)

For power flow between buses, voltage angle difference between buses must be
confined. Accordingly, voltage angle difference upper and lower limits can be
shown as,

$\displaystyle-\theta_{ij}^{\Delta}\leq\angle(V_{i}V_{j}^{*})\leq\theta_{ij}^{\Delta}\quad\forall{(i,j)}\in\mathcal{\text{E}}$
(6)

To convexify the OPF problem, phase angle difference should be limited within
$[0,\pi/2]$ [30].

$\displaystyle
0\leq\theta_{ij}^{\Delta}\leq{\pi}/2\quad\forall{(i,j)}\in\mathcal{\text{N}}$
(7)

If we observe equation (6) as linear relation of real and imaginary parts of
$\angle(V_{i}V_{j}^{*})$ then it can be shown that,

$\displaystyle\tan\left(-\theta_{ij}^{\Delta}\right)\operatorname{Re}\left(V_{i}V_{j}^{*}\right)\leqslant\operatorname{Im}\left(V_{i}V_{j}^{*}\right)\leqslant\tan\left(\theta_{ij}^{\Delta}\right)\operatorname{Re}\left(V_{i}V_{j}^{*}\right)$
(8)

Objective of the OPF problem is to minimize generator fuel costs and that can
be defined as,

$\displaystyle\min\sum_{i\in\mathcal{N}}c_{2,i}\left(P_{i}^{g}\right)^{2}+c_{1,i}P_{i}^{g}+c_{0,i}$
(9)

In overall, the OPF problem can be written as,

$\displaystyle\text{variables}:S_{i}^{g}(\forall i\in N),V_{i}\quad(\forall
i\in N)$ (10a)
$\displaystyle\min\sum_{i\in\mathcal{N}}c_{2,i}\left(P_{i}^{g}\right)^{2}+c_{1,i}P_{i}^{g}+c_{0,i}$
(10b) $\displaystyle\text{subject
to}:v_{i}^{l}\leqslant\left|V_{i}\right|\leqslant v_{i}^{u}\quad\forall i\in
N$ (10c) $\displaystyle S_{i}^{gl}\leqslant S_{i}^{g}\leqslant
S_{i}^{gu}\quad\forall i\in N$ (10d)
$\displaystyle\left|S_{ij}\right|\leqslant s_{ij}^{u}\quad\forall(i,j)\in
E\cup F$ (10e) $\displaystyle S_{i}^{g}-S_{i}^{d}=\sum_{(i,j)\in E\cup
F}S_{ij}\quad\forall i\in N$ (10f) $\displaystyle
S_{ij}=Y_{ij}^{*}V_{i}V_{i}^{*}-Y_{ij}^{*}V_{i}V_{j}^{*}\quad(i,j)\in E\cup F$
(10g)
$\displaystyle-\theta_{ij}^{\Delta}\leqslant\angle\left(V_{i}V_{j}^{*}\right)\leqslant\theta_{ij}^{\Delta}\quad\forall(i,j)\in
E$ (10h)
$\displaystyle\tan\left(-\theta_{ij}^{\Delta}\right)\operatorname{Re}\left(V_{i}V_{j}^{*}\right)\leqslant\operatorname{Im}\left(V_{i}V_{j}^{*}\right)\leqslant\tan\left(\theta_{ij}^{\Delta}\right)\operatorname{Re}\left(V_{i}V_{j}^{*}\right)$
(10i)

From above equations, it can be realized that the non-convex nature of the OPF
problem arises from product of the voltage variables $V_{i}V_{j}^{*}$. Assume,
a new lifted variable $W_{ij}$ in place of $V_{i}V_{j}^{*}$ for applying
convex relaxation methods.

$\displaystyle W_{ij}=V_{i}V_{j}^{*}$ (11)

Equations (10g), (10h), and (10i) can be written as,

$\displaystyle S_{ij}=Y_{ij}^{*}W_{ij}-Y_{ij}^{*}W_{ij}\quad(i,j)\in E\cup F$
(12a)
$\displaystyle-\theta_{ij}^{\Delta}\leqslant\angle\left(W_{ij}\right)\leqslant\theta_{ij}^{\Delta}\quad\forall(i,j)\in
E$ (12b)
$\displaystyle\tan\left(-\theta_{ij}^{\Delta}\right)\operatorname{Re}\left(W_{ij}\right)\leqslant\operatorname{Im}\left(W_{ij}\right)\leqslant\tan\left(\theta_{ij}^{\Delta}\right)\operatorname{Re}\left(W_{ij}\right)$
(12c)

Next we explain how defining lifted variables can be leveraged to convexify
the OPF problem.

##  III Convex Relaxations in Optimal Power flow

Traditional OPF solving methods may find global optima of the solution but
they might stuck in local optima [31]. Conversely, convex relaxation
techniques can obtain bounds on the optimal objective values, certify
infeasibility, and in some cases, achieve globally optimal solutions. There
has been many relaxation techniques applied to the OPF problems i.e Second
order cone relaxations, Quadratic Convex relaxations and Semi-definite
relaxations [2], [32]. Each relaxation method follows separate methodology to
solve the non-convex OPF problem. To be specific, they approach differently to
convexify the source of non-convexification $V_{i}V_{j}^{*}$. In this study we
will focus only on quadratic convex (QC) relaxation.

Quadratic Convex Relaxations: The quadratic convex (QC) relaxation is a
approach that encloses the trigonometric and product terms in the polar
representation of power flow equations within convex envelopes [33, 34, 35].
It represents the voltage variables in polar coordinates and expands equation
(11) in following way,

$\displaystyle W_{ii}=v_{i}^{2}\quad\forall i\in N$ (13a)
$\displaystyle\operatorname{Re}{(W_{ij})}={v_{i}}{v_{j}}\cos({\theta{i}-\theta{j})}\quad\forall(i,j)\in
E$ (13b)
$\displaystyle\operatorname{Im}{(W_{ij})}={v_{i}}{v_{j}}\sin({\theta{i}-\theta{j})}\quad\forall(i,j)\in
E$ (13c)

QC relaxation relaxes these constraints by drawing tight envelopes around
nonconvex terms. Such as, convex envelopes for square terms can be defined as
[36],

$\displaystyle\langle
x^{2}\rangle^{T}\equiv\begin{cases}\widecheck{x}\geqslant x^{2}\\\
\widecheck{x}\leqslant\left(x^{u}+x^{l}\right)x-x^{u}x^{l}.\\\ \end{cases}$
(14)

Here, ${\widecheck{x}}$, $x^{u}$ and $x^{l}$ corresponds to convex envelopes
of $x$, upper and lower bound of $x$, respectively. Additionally, convex
envelopes for bilinear terms can be defined as,

$\displaystyle\langle
xy\rangle^{M}\equiv\left\\{\begin{array}[]{l}\widecheck{xy}\geqslant
x^{l}y+y^{l}x-x^{l}y^{l}\\\ \widecheck{xy}\geqslant
x^{u}y+y^{u}x-x^{u}y^{u}\\\ \widecheck{xy}\leqslant
x^{l}y+y^{u}x-x^{l}y^{u}\\\ \widecheck{xy}\leqslant
x^{u}y+y^{l}x-x^{u}y^{l}\end{array}\right.$ (19)

Convex envelopes for sine and cosine function for $x\in[0,\pi/2]$ can be given
as [37],

$\displaystyle\begin{array}[]{c}\langle\sin(x)\rangle^{S}\equiv\left\\{\begin{array}[]{l}\widecheck{S}\leqslant\cos\left(\frac{x^{u}}{2}\right)\left(x-\frac{x^{u}}{2}\right)+\sin\left(\frac{x^{u}}{2}\right)\\\
\widecheck{S}\geqslant\cos\left(\frac{x^{u}}{2}\right)\left(x+\frac{x^{u}}{2}\right)-\sin\left(\frac{x^{u}}{2}\right)\end{array}\right.\\\
\langle\cos(x)\rangle^{C}\equiv\left\\{\begin{array}[]{l}\widecheck{C}\leqslant
1-\frac{1-\cos\left(x^{u}\right)}{\left(x^{u}\right)^{2}}x^{2}\\\
\widecheck{C}\geqslant\cos\left(x^{u}\right)\end{array}\right.\end{array}$
(26)

Now using equations (13)–(26) convex relaxations of product terms in power
flow equation can be obtained as follows.

$\displaystyle W_{ii}=\left\langle v_{i}^{2}\right\rangle^{T}\quad i\in N$
(27a)
$\displaystyle\operatorname{Re}\left(W_{ij}\right)=\left\langle\left\langle
v_{i}v_{j}\right\rangle^{M}\left\langle\cos\left(\theta_{i}-\theta_{j}\right)\right\rangle^{C}\right\rangle^{M}\quad\forall(i,j)\in
E$ (27b)
$\displaystyle\operatorname{Im}\left(W_{ij}\right)=\left\langle\left\langle
v_{i}v_{j}\right\rangle^{M}\left\langle\sin\left(\theta_{i}-\theta_{j}\right)\right\rangle^{S}\right\rangle^{M}\quad\forall(i,j)\in
E$ (27c)

Incorporating equations (12)–(27) into equation (10) would convexify the
nonconvex terms and result in the QC relaxation of the OPF problem. The
solution of the QC relaxation is a lower bound for the original nonconvex OPF
problem. The tighter the relaxation, the better a lower bound can be computed
for the OPF problem. Next, we leverage the graphlets analysis to understand
the correlation between power system topology and the optimality of the QC
relaxation for different test cases.

##  IV Network Graphlet

To observe the local structure of any power grid we consider the grid as a
undirected graph $G(V,E)$ where $V$ as nodes is the buses in the grid and $E$
as edges stands for Lines in the grid. The order and the size of graph $G$ can
be defined as total number of nodes and total number of edges of the graph. A
graph $G^{\prime}(V^{\prime},E^{\prime})$ is a subgraph of graph ${G}$ if
${G^{\prime}}\subseteq{G}\;\text{such
that}\;{V^{\prime}}\subseteq{V}\;{and}\;{E^{\prime}}\subseteq{E}$. That
subgraph $G^{\prime}$ can be called as induced subgraph of $G$ if $E^{\prime}$
contains all edges $e_{uv}\in E$ such that $u,v\in V^{\prime}$. Graphs
$G^{\prime}$ and $G^{\prime\prime}$ can be called isomorphic if there exists a
bijection $h:V^{\prime}\rightarrow V^{\prime\prime}$ such that any two
adjacent nodes $u,v\in V^{\prime}$ of $G^{\prime}$ are also adjacent in
$G^{\prime\prime}$ after the mapping occurs. If $G_{k}=(V_{k},E_{k})$ is a $k$
node subgraph of G and there exists an isomorphism between $G_{k}$ and
$G^{\prime}$ where $G^{\prime}\in G$, then there is an occurrence of $G_{k}$
in $G$. A motif can be defined as a multi node subgraph pattern that occurs
too frequently in a graph comparing to some random graphs. These recurrent
patterns are considered as building blocks of networks, and different
combinations of a small number of motifs can generate enormously diverse
forms. Albeit the notion of motif originated in biological networks, different
motifs could be found in a variety of different types of complex networks.
Traditional network attributes, which characterize nodes, connections, or the
entire network, do not really afford for the profiling of local structural
characteristics. As it is well known, motif patterns differ substantially
among networks [38]. In this paper, we use 4 node connected undirected
subgraphs which are called graphlets. Therefore, 6 types of graphlets that can
be found in the power network are used to asses the local structure. These
graphlets are shown in figure 1. In this paper, we first explore the existence
of different graphlet types among different buses of the network and then
classify those subgraph patterns.

(a) Graphlet type 1  (b) Graphlet type 2 (c) Graphlet type 3 (d) Graphlet type
4

(e) Graphlet type 5 (f) Graphlet type 6

Figure 1: Different graphlet types

##  V Detection of Graphlets

In this section, how graphlet can be identified in different networks is
discussed.

Figure 2: A network having 5 nodes and 6 edges. Total of 5 graphlets can be
found in this network

This paper uses an algorithm that follows the footprints in [39][40]. Given a
graph G = (V, E), the following algorithm enumerates all of its 4-nodes
subgraphs. There is two sets, one is subgraph set, and another is extension
set. Extension set consists of neighboring nodes that are not in subgraph set.
When summation of subgraph set and extension set element equals to our desired
subgraph level which is four, this algorithm returns a subgraph.

  * •

In the first stage, the subgraph level is one which is basically a node. In
figure 2, for this stage, we consider node 1 as a subgraph set. Therefore,
extension set consists of {2, 4, 5}. For node 2 as a subgraph set, extension
set consists of node 3. However, Node 1 is a neighboring node of node 2 but is
not considered in extension set as it has already been considered as a
subgraph set. Following this formula, other combinations of subgraph and
extension set are [{2},{3}], [{3},{4}], [{4},{5}]. This stage returns only one
4 node subgraph, {1,2,4,5}.

  * •

In the second stage, the subgraph level is two which is an edge. In this
stage, for node {1, 2} as a subgraph set, extension set consists of
neighboring nodes of edge 1-2 which is {3, 4, and 5}. For edge {1,4} as a
subgraph set, extension set consists of {3,5}. Here node 2 is not in extension
set as edge 1,2 already have been considered as a subgraph set. Only other
possible combination are [{2,3},{4,5}]. This stage returns two 4 node
subgraph. Those are, {1,4,3,5} and {2,3,4,5}.

  * •

Following this formula for third and fourth stage, this algorithm gives two
more subgraph combination. Those are {1,2,3,4} and {1,2,3,5}.

  * •

After that, this algorithm classifies those subgraphs or graphlets. For
example, {2, 3, 4, 5} is a type 2 graphlet as previously mentioned. Following
the classification, occurrence of each graphlet is counted. Such as, type 2
graphlet has occurred 4 times out of total 5 graphlets in this graph.
Furthermore, for all other graphlets its graphlet occurrence time divided by
total graphlet count gives us a percentage. For different test cases in
Matpower [41] and PGLib-OPF v18.08 benchmark library [42], this percentages
for all graphlet types are given in Table I.

Table I: Different Networks with different graphlet percentages and their corresponding QC relaxation optimality gap Networks |  QC Gap |  Type 1 |  Type 2 |  Type 3 |  Type 4 |  Type 5 |  Type 6
---|---|---|---|---|---|---|---
case18 | 1.17E-05 | 15.38461538 | 84.61538462 | 0 | 0 | 0 | 0
case9 | 0.000379748 | 20 | 80 | 0 | 0 | 0 | 0
pglib_opf_case_ACTIVSg200 | 0.003350142 | 39.50471698 | 54.54009434 | 5.247641509 | 0.471698113 | 0.235849057 | 0
pglib_opf_case24_ieee_rts | 0.01203402 | 21.51162791 | 72.6744186 | 2.325581395 | 3.488372093 | 0 | 0
pglib_opf_case39_epri | 0.02275154 | 21.29032258 | 75.48387097 | 1.935483871 | 1.290322581 | 0 | 0
pglib_opf_case73_ieee_rts | 0.030513151 | 21.25603865 | 73.2689211 | 2.576489533 | 2.898550725 | 0 | 0
pglib_opf_case30_as | 0.055670456 | 22.07207207 | 60.36036036 | 16.66666667 | 0.900900901 | 0 | 0
pglib_opf_case60_c | 0.058817246 | 24.46555819 | 68.64608076 | 6.413301663 | 0.237529691 | 0.237529691 | 0
pglib_opf_case2868_rte | 0.094801158 | 37.85541316 | 58.46053383 | 3.202459663 | 0.440780344 | 0.040812995 | 0
pglib_opf_case14_ieee | 0.10907652 | 10.14492754 | 62.31884058 | 24.63768116 | 0 | 2.898550725 | 0
pglib_opf_case2848_rte | 0.118583008 | 36.59196075 | 59.56681719 | 3.275352623 | 0.521268886 | 0.044600546 | 0
pglib_opf_case1951_rte | 0.126574378 | 38.41369779 | 57.3786855 | 3.62791769 | 0.525952088 | 0.053746929 | 0
pglib_opf_case179_goc | 0.151274263 | 29.96515679 | 59.93031359 | 8.797909408 | 0.609756098 | 0.609756098 | 0.087108014
pglib_opf_case57_ieee | 0.158611501 | 15.15151515 | 69.6969697 | 14.04958678 | 0.550964187 | 0.550964187 | 0
pglib_opf_case89pegase | 0.165595479 | 14.37705201 | 43.13115604 | 30.43027475 | 0.380162433 | 7.033005011 | 4.648349749
pglib_opf_case500_goc | 0.240470483 | 32.58928571 | 59.56909938 | 7.104037267 | 0.36878882 | 0.349378882 | 0.019409938
pglib_opf_case2737sop_k | 0.256111524 | 27.69497108 | 69.78001098 | 2.068994638 | 0.434911118 | 0.02111219 | 0
pglib_opf_case2000_goc | 0.304646737 | 23.75966093 | 68.35203191 | 6.881077038 | 0.513587634 | 0.463724757 | 0.029917726
pglib_opf_case2746wp_k | 0.313345858 | 27.58125185 | 69.87870335 | 2.096276573 | 0.422636406 | 0.02113182 | 0
pglib_opf_case3970_goc | 0.337410369 | 20.84741502 | 76.12211267 | 2.834957964 | 0.19272128 | 0.002793062 | 0
pglib_opf_case3375wp_k | 0.530375619 | 27.47302905 | 68.91286307 | 2.933609959 | 0.257261411 | 0.315352697 | 0.107883817
pglib_opf_case9591_goc | 0.607902624 | 21.44041766 | 74.65971875 | 3.599572134 | 0.280664567 | 0.017664203 | 0.001962689
pglib_opf_case118_ieee | 0.785063339 | 26.102169 | 62.841148 | 9.237229 | 1.39958 | 0.349895 | 0.069979
pglib_opf_case2853_sdet | 0.863872504 | 40.43575845 | 44.6747692 | 11.9717117 | 0.256203947 | 0.741085797 | 1.920470907
pglib_opf_case793_goc | 1.316740725 |  28.81693649 | 69.4718876 | 1.320049813 | 0.149439601 | 0.231416564 | 0.027687821
pglib_opf_case6468_rte | 1.744539041 | 37.27092714 | 58.57706812 | 3.613454917 | 0.469181581 | 0.06306204 | 0.006306204
pglib_opf_case4917_goc | 2.491041794 | 38.3252531 | 57.84614288 | 3.156637673 | 0.50798517 | 0.144374733 | 0.019606445
pglib_opf_case240_pserc | 2.727162682 | 23.77777778 | 63.14814815 | 11.11111111 | 0.925925926 | 1 | 0.037037037
pglib_opf_case3022_goc | 2.752412865 | 41.4685445 | 53.63541972 | 4.068049306 | 0.48454514 | 0.279545273 | 0.063896062
pglib_opf_case162_ieee_dtc | 5.838058785 | 17.08751297 | 65.0639917 | 14.07817364 | 0.864752681 | 2.525077828 | 0.38049118
pglib_opf_case6515_rte | 6.389830911 | 37.67528825 | 58.22000623 | 3.573698972 | 0.462449361 | 0.062324712 | 0.006232471
pglib_opf_case6495_rte | 15.08381955 | 37.42583467 | 58.43473451 | 3.603932019 | 0.466361625 | 0.062851971 | 0.006285197

##  VI Results

We implement the QC relaxation and local structure of power systems’ graph on
various test cases from PGLib-OPF v18.08 benchmark library [42] and Matpower
to find the correlation between local structure of power systems’ graph and
OPF optimality gap. Table I tabulates optimality gap from QC relaxation and
their corresponding different graphlet type percentages for different test
cases. This table is sorted with ascending "QC gap" values. Clearly, some
patterns are visible in this Table. The most noticeable trend is that, of the
33 cases investigated, 12 cases with the low optimality gap have one
characteristic in common. That is they share the common trait of having no
type 6 graphlets. From figure 1, it is apparent that type 6 graphlet is
equivalent to 4-nodes complete subgraph. However, existence of complete 4-node
subgraph is not very frequent in any kind of networks. That is why in other
cases such low percentage of type 6 graphlets are observed. For instance,
"pglib_opf_case162_ieee_dtc" has total 2891 graphlets. Yet, it has only 11
type 6 graphlets. Particularly, this trend shows us that existence of type 6
graphlets even in such low percentage can affect the QC relaxation optimality
gap. Additionally, there is another pattern that highlights less percentage of
type 1 graphlets in low optimality gap networks in comparison with networks
with high optimality gaps. Particularly, networks with low optimality gap have
15-25% type 1 graphlets whereas most networks having high optimality gap have
25-40% type 1 graphlets. Furthermore, not as significant pattern as type 6,
type 5 graphlets are also absent in some of the lowest optimality gap
networks. In conclusion, from Table I, it can be observed that existence of
type 6, type 1 and type 5 graphlets can significantly impact OPF optimality
gap in different test cases.

The graphlet structure can be leveraged to introduce constraints or
relationships between variables in the convex relaxation problems. For
instance, in a graph with specific graphlets, the variables within the
graphlets may have strong dependencies or correlations. By incorporating these
graph constraints into the relaxation formulation, the relaxation can better
capture the underlying structure and improve its tightness. Moreover, the
graph structure can provide insights into the connectivity of variables. If
certain subsets of variables are strongly connected in the graph, it suggests
that they should have similar values or follow certain patterns. By enforcing
such connectivity constraints in the relaxation, the relaxation can better
capture the relationships between variables and improve its accuracy. Overall,
by incorporating and leveraging the graph structure in the formulation of the
relaxation, it is possible to exploit the inherent properties of the problem
and improve the tightness of the relaxation. The proposed approach results in
more accurate solutions and better bounds for convex relaxation.

##  VII Conclusion

This paper investigates the correlation between the optimality gap of the OPF
convex relaxation and the local structure of power system graphs addressed by
the distribution of graphlet types. In this context, the paper calculates the
percentage of different 4-node graphlets in various networks and examines the
relationship between graphlet counts and optimality gaps for the QC relaxation
of the OPF problem. Consequently, the results clearly indicate that networks
with high QC optimality gaps share a common characteristic of having type 6
graphlets or complete 4-node graphlets. Additionally, it is noticeable that
networks with high QC optimality gaps tend to have a high percentage of type 1
or 4-node star-shaped graphlets. Conversely, most networks with very low
optimality gaps do not have type 5 graphlets. In conclusion, this study
suggests that the existence of certain graphlets can cause a high optimality
gap in the QC relaxation. In the future, this research can be expanded to
associate electrical parameters, such as branch admittance, with graphlet-
level analysis. This research is currently studying the identification of
nodes in the power system where enforcing redundant constraints can tighten
the QC relaxation of the OPF problem for those test cases.

Regenerate response

## References

  * [1] D. Bienstock and A. Verma, “Strong NP-hardness of AC Power Flows Feasibility,” _Oper. Res. Lett._ , vol. 47, no. 6, pp. 494–501, 2019.
  * [2] S. H. Low, “Convex relaxation of optimal power flow—part i: Formulations and equivalence,” _IEEE Transactions on Control of Network Systems_ , vol. 1, no. 1, pp. 15–27, 2014.
  * [3] M. R. Narimani, D. K. Molzahn, D. Wu, and M. L. Crow, “Empirical investigation of non-convexities in optimal power flow problems,” in _2018 Annual American Control Conference (ACC)_. IEEE, 2018, pp. 3847–3854.
  * [4] M. R. Narimani, _Strengthening QC relaxations of optimal power flow problems by exploiting various coordinate changes_. Missouri University of Science and Technology, 2020.
  * [5] C. Coffrin and L. Roald, “Convex relaxations in power system optimization: A brief introduction,” 07 2018.
  * [6] A. Barzegar, D. K. Molzahn, and R. Su, “A method for quickly bounding the optimal objective value of an opf problem using a semidefinite relaxation and a local solution,” _Electric Power Systems Research_ , vol. 177, p. 105954, 2019.
  * [7] S. Gopinath, H. L. Hijazi, T. Weisser, H. Nagarajan, M. Yetkin, K. Sundar, and R. W. Bent, “Proving global optimality of acopf solutions,” _Electric Power Systems Research_ , vol. 189, p. 106688, 2020.
  * [8] J. Lavaei and S. H. Low, “Zero duality gap in optimal power flow problem,” _IEEE Transactions on Power Systems_ , vol. 27, no. 1, pp. 92–107, 2012.
  * [9] S. Bose, S. H. Low, T. Teeraratkul, and B. Hassibi, “Equivalent relaxations of optimal power flow,” _IEEE Transactions on Automatic Control_ , vol. 60, no. 3, pp. 729–742, 2015.
  * [10] C. Coffrin, H. L. Hijazi, and P. Van Hentenryck, “The qc relaxation: A theoretical and computational study on optimal power flow,” _IEEE Transactions on Power Systems_ , vol. 31, no. 4, pp. 3008–3018, 2015.
  * [11] S. Seshu and M. B. Reed, _Linear graphs and electrical networks_. Addison-Wesley Publishing Company, 1961.
  * [12] Z. Wang, A. Scaglione, and R. J. Thomas, “The node degree distribution in power grid and its topology robustness under random and selective node removals,” in _2010 IEEE International Conference on Communications Workshops_. IEEE, 2010, pp. 1–5.
  * [13] L. Cuadra, S. Salcedo-Sanz, J. Del Ser, S. Jiménez-Fernández, and Z. W. Geem, “A critical review of robustness in power grids using complex networks concepts,” _Energies_ , vol. 8, no. 9, pp. 9211–9265, 2015.
  * [14] P. Cuffe, “Assortativity anomalies in a large test system,” _IEEE Transactions on Power Systems_ , vol. 31, no. 5, pp. 4169–4170, 2015.
  * [15] M. R. Narimani, H. Huang, A. Umunnakwe, Z. Mao, A. Sahu, S. Zonouz, and K. Davis, “Generalized contingency analysis based on graph theory and line outage distribution factor,” _IEEE Systems Journal_ , vol. 16, no. 1, pp. 626–636, 2022.
  * [16] H. Huang, Z. Mao, M. R. Narimani, and K. R. Davis, “Toward efficient wide-area identification of multiple element contingencies in power systems,” in _2021 IEEE Power & Energy Society Innovative Smart Grid Technologies Conference (ISGT)_, 2021, pp. 01–05.
  * [17] O. Boyaci, M. R. Narimani, K. Davis, and E. Serpedin, “Spatio-temporal failure propagation in cyber-physical power systems,” in _2022 3rd International Conference on Smart Grid and Renewable Energy (SGRE)_ , 2022, pp. 1–6.
  * [18] A. B. Birchfield, T. Xu, K. M. Gegner, K. S. Shetye, and T. J. Overbye, “Grid structural characteristics as validation criteria for synthetic networks,” _IEEE Transactions on power systems_ , vol. 32, no. 4, pp. 3258–3265, 2016\.
  * [19] S. Chitra and N. Devarajan, “Optimal power flow control of power transmission networks using graph algorithms,” _Journal of Vibration and Control_ , vol. 21, no. 16, pp. 3320–3327, 2015.
  * [20] J. A. Kersulis, I. A. Hiskens, C. Coffrin, and D. K. Molzahn, “Topological graph metrics for detecting grid anomalies and improving algorithms,” in _2018 Power Systems Computation Conference (PSCC)_. IEEE, 2018, pp. 1–7.
  * [21] R. Madani, M. Ashraphijuo, and J. Lavaei, “Promises of conic relaxation for contingency-constrained optimal power flow problem,” _IEEE Transactions on Power Systems_ , vol. 31, no. 2, pp. 1297–1307, 2015.
  * [22] D. K. Molzahn, D. Mehta, and M. Niemerg, “Toward topologically based upper bounds on the number of power flow solutions,” in _2016 American Control Conference (ACC)_. IEEE, 2016, pp. 5927–5932.
  * [23] D. Owerko, F. Gama, and A. Ribeiro, “Optimal power flow using graph neural networks,” in _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2020, pp. 5930–5934.
  * [24] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, “Network motifs: simple building blocks of complex networks,” _Science_ , vol. 298, no. 5594, pp. 824–827, 2002.
  * [25] V. Lacroix, C. G. Fernandes, and M.-F. Sagot, “Reaction motifs in metabolic networks,” in _International Workshop on Algorithms in Bioinformatics_. Springer, 2005, pp. 178–191.
  * [26] R. J. Prill, P. A. Iglesias, and A. Levchenko, “Dynamic properties of network motifs contribute to biological network organization,” _PLoS biology_ , vol. 3, no. 11, p. e343, 2005.
  * [27] A. K. Dey, Y. R. Gel, and H. V. Poor, “Motif-based analysis of power grid robustness under attacks,” in _2017 IEEE Global Conference on Signal and Information Processing (GlobalSIP)_. IEEE, 2017, pp. 1015–1019.
  * [28] A. Abedijaberi and J. Leopold, “Motif-level robustness analysis of power grids,” in _2018 IEEE International Conference on Data Mining Workshops (ICDMW)_. IEEE, 2018, pp. 276–283.
  * [29] P. Kundur, J. Paserba, V. Ajjarapu, G. Andersson, A. Bose, C. Canizares, N. Hatziargyriou, D. Hill, A. Stankovic, C. Taylor _et al._ , “Definition and classification of power system stability ieee/cigre joint task force on stability terms and definitions,” _IEEE transactions on Power Systems_ , vol. 19, no. 3, pp. 1387–1401, 2004.
  * [30] C. Coffrin and P. Van Hentenryck, “A linear-programming approximation of ac power flows,” _INFORMS Journal on Computing_ , vol. 26, no. 4, pp. 718–734, 2014.
  * [31] D. K. Molzahn, B. C. Lesieutre, and C. L. DeMarco, “A sufficient condition for global optimality of solutions to the optimal power flow problem,” _IEEE Transactions on Power Systems_ , vol. 29, no. 2, pp. 978–979, 2013\.
  * [32] D. K. Molzahn, J. T. Holzer, B. C. Lesieutre, and C. L. DeMarco, “Implementation of a large-scale optimal power flow solver based on semidefinite programming,” _IEEE Transactions on Power Systems_ , vol. 28, no. 4, pp. 3987–3998, 2013.
  * [33] M. Rasoul Narimani, D. K. Molzahn, and M. L. Crow, “Improving qc relaxations of opf problems via voltage magnitude difference constraints and envelopes for trilinear monomials,” in _2018 Power Systems Computation Conference (PSCC)_ , 2018, pp. 1–7.
  * [34] M. R. Narimani, D. K. Molzahn, H. Nagarajan, and M. L. Crow, “Comparison of various trilinear monomial envelopes for convex relaxations of optimal power flow problems,” in _2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP)_ , 2018, pp. 865–869.
  * [35] M. R. Narimani, D. K. Molzahn, and M. L. Crow, “Tightening qc relaxations of ac optimal power flow problems via complex per unit normalization,” _IEEE Transactions on Power Systems_ , vol. 36, no. 1, pp. 281–291, 2020\.
  * [36] G. P. McCormick, “Computability of global solutions to factorable nonconvex programs: Part i—convex underestimating problems,” _Mathematical programming_ , vol. 10, no. 1, pp. 147–175, 1976.
  * [37] H. Hijazi, C. Coffrin, and P. V. Hentenryck, “Convex quadratic relaxations for mixed-integer nonlinear programs in power systems,” _Mathematical Programming Computation_ , vol. 9, no. 3, pp. 321–367, 2017.
  * [38] F. Xia, H. Wei, S. Yu, D. Zhang, and B. Xu, “A survey of measures for network motifs,” _IEEE Access_ , vol. 7, pp. 106 576–106 587, 2019.
  * [39] S. Wernicke and F. Rasche, “Fanmod: a tool for fast network motif detection,” _Bioinformatics_ , vol. 22, no. 9, pp. 1152–1153, 2006.
  * [40] P. Ribeiro, F. Silva, and M. Kaiser, “Strategies for network motifs discovery,” in _2009 Fifth IEEE International Conference on e-Science_. IEEE, 2009, pp. 80–87.
  * [41] R. D. Zimmerman, C. E. Murillo-Sanchez, and D. Gan, “Matpower,” _PSERC.[Online]. Software Available at: http://www. pserc. cornell. edu/matpower_ , 1997.
  * [42] S. Babaeinejadsarookolaee, A. Birchfield, R. D. Christie, C. Coffrin, C. DeMarco, R. Diao, M. Ferris, S. Fliscounakis, S. Greene, R. Huang _et al._ , “The power grid library for benchmarking ac optimal power flow algorithms,” _arXiv preprint arXiv:1908.02788_ , 2019.


#  X-Former: In-Memory Acceleration of Transformers

Shrihari Sridharan, Jacob R. Stevens*, Kaushik Roy and Anand Raghunathan
School of Electrical and Computer Engineering, Purdue University, West
Lafayette, IN, USA

###### Abstract

Transformers have achieved great success in a wide variety of natural language
processing (NLP) tasks due to the attention mechanism, which assigns an
importance score for every word relative to other words in a sequence.
However, these models are very large, often reaching hundreds of billions of
parameters, and therefore require a large number of DRAM accesses. Hence,
traditional deep neural network (DNN) accelerators such as GPUs and TPUs face
limitations in processing Transformers efficiently. In-memory accelerators
based on non-volatile memory promise to be an effective solution to this
challenge, since they provide high storage density while performing massively
parallel matrix vector multiplications within memory arrays. However,
attention score computations, which are frequently used in Transformers
(unlike CNNs and RNNs), require matrix vector multiplications (MVM) where both
operands change dynamically for each input. As a result, conventional NVM-
based accelerators incur high write latency and write energy when used for
Transformers, and further suffer from the low endurance of most NVM
technologies.

To address these challenges, we present X-Former, a hybrid in-memory hardware
accelerator that consists of both NVM and CMOS processing elements to execute
transformer workloads efficiently. To improve the hardware utilization of
X-Former, we also propose a sequence blocking dataflow, which overlaps the
computations of the two processing elements and reduces execution time. Across
several benchmarks, we show that X-Former achieves upto 85x and 7.5x
improvements in latency and energy over a NVIDIA GeForce GTX 1060 GPU and upto
10.7x and 4.6x improvements in latency and energy over a state-of-the-art in-
memory NVM accelerator.

###### Index Terms:

Machine Learning, Neural Networks, In-memory computing

§§footnotetext: * Jacob R. Stevens is currently a Research Scientist at Meta
Platforms, Inc., Cambridge, MA

##  I Introduction

Deep learning models that process language such as Transformers (BERT, GPT-3)
have attained state of the art accuracies in a wide variety of natural
language processing (NLP) tasks [1, 2]. These models are able to achieve
superior performance due to the attention mechanism [3], which provides an
estimate of the significance of each word with respect to every other word in
a particular sequence. However, as language tasks become more and more
complex, the model sizes continue to increase rapidly. For example, GPT-3
contains 175 billion parameters and acquires state of the art results for text
generation with input sequence length of 2048 [2]. Further, the attention
mechanism also comprises of unique operations such as matrix vector
multiplications between dynamically changing operands for every new batch of
input sequences, absent in Convolutional neural networks (CNNs) and Recurrent
neural networks (RNNs). Typically, on-chip scratchpads in commodity hardware
are very small to store the model weights and other intermediate activations
[4]. This leads to significant overheads due to data movement costs from off-
chip accesses. For example, the energy per access of a 64-byte word from DRAM
is approximately three orders of magnitude higher than on-chip access [5]. As
a result, there are several challenges associated with implementing
Transformers on existing deep learning CMOS accelerators such as GPUs and TPUs
[4]. Consequently, in-memory computing has emerged as a viable candidate to
reduce this performance bottleneck. In this paradigm, the computations are
performed within the memory array itself which minimizes the number of off-
chip accesses considerably. Non-volatile memory (NVM)-based in-memory compute
primitives (resistive crossbars) [6, 7] are well suited for this application
because they provide high storage density and facilitate massively parallel
matrix vector multiplication (MVM) operations. However, the issues with NVM-
based in-memory computing are twofold; First, Transformers require significant
number of writes into the NVM device. This is a challenge due to NVMs
requiring atleast one to two orders of magnitude higher latency and energy/bit
depending on the NVM device compared to SRAM for the same technology node [8,
9, 10]. NVM devices also have very limited endurance, only about
$10^{6}-10^{9}$ conservative writes [8, 9, 10] which degrades the lifetime of
these devices swiftly and limits their applicability to Transformers. To
alleviate the aforementioned challenges, we propose a hybrid in-memory
computing architecture that combines NVM and CMOS-based processing elements to
cater to the different computational and memory demands of Transformers. Our
overall architecture consists of a Projection engine with NVM tiles and an
Attention engine comprising of CMOS tiles, capable of executing all the
operations in a transformer network efficiently. The advantage of this
approach is that we can store these large models and perform the matrix
multiplication operations that require no reprogramming of the NVM device in
the Projection Engine. We make use of the Attention Engine to execute all the
other operations since they provide high endurance, low write latency and low
write energy. We also evaluate a traditional weight stationary dataflow for
our architecture. However, we observe that the hardware utilization is low
because the operations between different layers of a transformer encoder are
dependent on one another and the size of intermediate activations scale
quadratically with sequence length. Therefore, we introduce a sequence
blocking dataflow which divides the input sequence into smaller blocks and
processes them in a pipelined fashion. As shown in [11], this technique causes
no loss in application-level accuracy. Moreover, the proposed dataflow also
prevents the intermediate activation sizes to scale with sequence length while
keeping both the engines fully utilized. We finally compare the performance of
our hardware design with a NVIDIA GeForce GTX 1060 GPU and a previously
proposed crossbar-based machine learning accelerator on several benchmarks and
report the improvements in energy and latency. In summary, our key
contributions are:

  * •

We design X-Former, an in-memory hardware architecture for Transformers
comprising of Projection engine and Attention engine, to efficiently
accelerate attention layers in Transformers.

  * •

We propose an intra-layer sequence blocking dataflow for the proposed
architecture, which increases the hardware utilization and reduces
intermediate on-chip memory requirements.

  * •

We also develop a simulation framework to evaluate the performance of
X-Former, and observe 85x and 7.5x improvements in latency and energy on
average compared to a NVIDIA GeForce GTX 1060 GPU and upto 10.7x and 4.6x
improvements in latency and energy over a state-of-the-art NVM accelerator.

The paper is organized as follows. Section II provides an overview of
transformer models, its associated computational challenges and a brief
background on resistive crossbars. Section III discusses the existing efforts
related to this work. Section IV describes our proposed hardware architecture
in detail. Section V highlights different dataflows for X-Former and lists
their advantages. Section VI explains the experimental methodology used for
the work. We present the performance results of X-Former in Section VII and
conclude the paper in Section VIII.

##  II Preliminaries

In this section, we describe the operations in a transformer network and
analyze the various computational challenges. We also present a background on
resistive crossbars.

###  II-A Transformers

Figure 1: (a) A transformer network with multiple encoder layers and a
classification layer for a specific downstream task, (b) Distribution of
Floating Point Operations (FLOPs) for image classification models and
Transformers with varying sequence lengths (The distribution for image
classification models is shown from 90%-100%)

Background. Figure 1(a) represents an example Transformer network
architecture. It consists of an embedding layer followed by multiple
Transformer encoders and a final classification layer fine-tuned for a
specific downstream task. Every Transformer encoder is further divided into an
attention layer that contains multiple self-attention heads followed by feed
forward layers. Multi-headed attention layers help capture fine-grained
relationships in a specific context for every word in a sequence [3]. A batch
of input sequences are first processed by an embedding layer to obtain a
learned vector representation of each word in the sequence. Within each self-
attention head, these inputs are multiplied by distinct weight matrices to
obtain the Query, Key and Value matrices. The outputs, Query and Key matrices
are now multiplied and normalized by a softmax layer to generate the
intermediate attention probabilities. The intermediate attention probabilities
are then multiplied with the Value matrix to obtain the final attention
output. Multiple attention heads are processed in parallel and the resultant
matrices are concatenated before advancing the output to the feed forward
layers. This procedure is repeated for all the encoder layers.

Computational challenges. Compute kernels in a Transformer network differ from
traditional image classification and previously proposed language models.
Matrix vector multiplication operations are typically performed between
inputs/activations and weights in traditional deep learning networks. Since
the weights do not require reprogramming, these operations are matrix vector
multiplications with static matrices or $MVMStatic$. Transformers, in addition
to $MVMStatic$ operations, also encompass matrix vector multiplications
between Query, Key and Value. These data structures change for every input,
hence they are dynamic and we refer to them as $MVMDynamic$ operations. We
categorize other compute kernels such as softmax, layerNorm, vector
operations, etc. as $NonMVM$ operations. Figure 1(b) shows the floating point
operations (FLOPs) distribution of various traditional deep learning networks
compared to a Transformer self-attention block of varying sequence lengths.
For traditional deep learning models, we can observe that $MVMStatic$
operations contributes to 95% of the total FLOPs. However, in the case of
Transformers, $MVMStatic$ operations contributes 65% while $MVMDynamic$
operations contributes 35% for a sequence length of 512, accounting for a
substantial proportion of the overall distribution. Figure 1(b) illustrates
that the FLOPs count for $MVMDynamic$ operations becomes increasingly dominant
as sequence length increases. Besides, modern Transformer networks demonstrate
state of the art accuracy on a variety of NLP tasks for extremely long
sequences [2]. In traditional crossbar based architectures, this is a
bottleneck because, for every self-attention layer within a transformer
encoder, all the crossbars need to be reprogrammed before the matrix vector
multiplication operation is performed since the inputs change dynamically.
This not only causes a huge degradation in overall latency and energy but also
affects the lifetime of the NVM devices, since they have very limited
endurance [8, 9, 10]. It is also expensive to implement these operations using
the temporal 1-D single-instruction, multiple data (SIMD) lanes available in
traditional in-memory accelerators. As shown in Figure 2, for a sequence
length of 256, 80% of the total runtime is spent in processing $MVMDynamic$
operations. Therefore, it is very important to design a hardware architecture
that can store the model parameters effectively while also improve the runtime
and efficiency of $MVMDynamic$ operations for better overall performance.

Figure 2: Runtime split of transformer operations on a traditional crossbar
architecture ($MVMDynamic$ implemented in 1-D SIMD lanes)

###  II-B Resistive Crossbars

Figure 3: Structure of a resistive crossbar array with Digital to Analog
converters (DACs) and Analog to Digital converters (ADCs)

Figure 3 illustrates the fundamental organization of a resistive crossbar with
N rows and M columns where the NVM devices are arranged like a two dimensional
array and programmed to discrete conductance states. The two terminals of the
NVM device are connected via an access device to a word-line and a bit-line at
each crosspoint. The digital inputs are converted to voltages using digital to
analog converters (DACs). The voltages simultaneously activate all the
wordlines and a multiplication operation is performed between the conductance
(G) and voltage (V) at each NVM device by applying Ohm’s law. The currents (I)
from multiple NVM devices connected to a bit-line are accumulated as a
consequence of Kirchhoff’s current law (KCL) and converted to digital outputs
using analog to digital converters (ADCs). A matrix vector multiplication
operation can be realized efficiently because the currents in multiple columns
can be obtained simultaneously.

##  III Related Work

In this section, we describe the related research efforts and contrast our
work with them.
Deep learning accelerators. Recently, various hardware accelerators have been
proposed to improve the efficiency and performance of traditional deep
learning networks [4, 12, 13, 14, 15, 16]. However, they are not optimized to
process the unique computational kernels of Transformers described in section
II.

Software techniques. To improve the efficiency of Transformers, software
methods such as quantization and pruning have helped reduce the bit-width of
different data structures and compress the overall network [17, 18, 19, 20].
These efforts are complimentary to our work since they enable further
improvements to our proposed hardware architecture.

Specialized hardware accelerators. Another promising direction to improve the
performance and energy efficiency of Transformers is to build specialized
hardware for Transformers. To this end, research works such as [18, 21, 22,
19, 23] accelerate key computations in the network. These hardware
architectures have separate memory and computation units which result in
significant communication overheads. An approach to reduce the number of off-
chip accesses was proposed by EdgeBert [24], which stores a small part of the
model (embedding table) in NVM devices. Our work differs from the above
architectures by performing all the computations of the transformer network
within the memory itself.

In-memory architectures for Transformers. The existing processing in-memory
architectures on accelerating Transformers are [25] and [26]. Both the works
use NVM crossbars to accelerate both $MVMStatic$ and $MVMDynamic$ operations.
While they propose techniques to reduce latency of reprogramming the NVM
crossbars, these devices offer very low endurance which can degrade their
lifetime quickly. Our design avoids this issue by mapping $MVMStatic$
operations to NVM crossbars while processing the $MVMDynamic$ operations using
in-memory CMOS processing elements. Nevertheless, we also compare our results
against a traditional in-memory accelerator that maps $MVMDynamic$ operations
to NVM crossbars and highlight the improvements.

##  IV Overall Architecture

X-Former is a hybrid spatial architecture that consists of two different types
of processing elements to accommodate the unique needs of Transformers. We
classify key workload characteristics of the transformer network into
$MVMStatic$, where atleast one operand remains constant in the MVM operation
for all inputs and $MVMDynamic$, where both the operands change for every
batch of input sequences. X-Former is composed primarily of a Projection
Engine with NVM processing tiles for executing $MVMStatic$ operations and an
Attention Engine with CMOS processing tiles for executing $MVMDynamic$
operations, as shown in Figure 4. The weights of all the layers are stored in
the Projection Engine to prevent reprogramming the NVM tiles, while we
optimize the Attention Engine to only process the largest self-attention layer
due to area constraints. We also have a dedicated bus-based interconnect
network for data transfers between the Projection engine and the Attention
engine and model its energy and latency. In the following subsections, each of
these components will be described in more detail.

Figure 4: The X-Former hardware accelerator consisting of two different
compute Engines, Projection Engine and Attention Engine and design of
Attention Head Compute Tile (Bottom)

###  IV-A Projection Engine Overview

The Projection Engine is designed similarly to a traditional in-memory
accelerator, capable of efficiently executing $MVMStatic$ operations. It
consists of a hierarchical structure of tiles and cores connected via a shared
memory. Each tile consists of multiple cores, and each core contains multiple
resistive crossbars that can perform matrix vector multiplication operations
in parallel in the analog domain. We also provision enough memory for local
scratchpads to store the input and output activations within a core. The data
from the scratchpads is written to the shared memory only when it is
completely filled to avoid higher memory access costs. It is also important to
size both the shared memory and the scratchpads appropriately to avoid
diminishing the storage density advantage of resistive crossbars. The memory
controller helps orchestrate and schedule the movement of data between
different levels of the hierarchy. The weights are fetched from off-chip
memory and programmed into the crossbars only once during compile time. Every
resistive crossbar within a core is interfaced with DACs and ADCs (peripheral
circuit) to convert inputs to analog values and convert the analog outputs
back in the digital domain. Since the peripheral circuitry typically
introduces a large overhead in area and energy, we make use of couple of
techniques to reduce the cost: (i) Utilize low resolution DACs and ADCs (ii)
Make multiple columns within a crossbar and multiple crossbars share both DACs
and ADCs. The state of the art accuracy for Transformers inference on a
variety of downstream tasks has been shown with 8-bit fixed point weights and
8-bit fixed point activations [27]. Due to limited conductance levels in the
NVM device, we use bit-slicing and bit-streaming techniques to represent the
higher precision weights and activations respectively. Finally, the Query, Key
and Value matrices are communicated to the Attention Engine to compute the
attention scores. The Projection Engine also executes other fully connected
layers present in the transformer network. Note that the projection engine
stores the weights across all the layers of the network spatially, thereby
avoiding writing into the resistive crossbars. This is possible due to the
high storage density of the NVM devices.

As indicated in Section II, in addition to static weights in the encoder
layers, the transformer network also contains an embedding layer (lookup
table) that converts each word in a sequence to a continuous vector
representation. Therefore, we equip the Projection Engine with additional
read-only tiles to store the embedding lookup table. The read-only tiles are
organized like a standard memory array and consists of NVM devices for
efficient storage of the embedding weights, especially useful for longer
sequence lengths. They are used only once before the first encoder layer.

###  IV-B Attention Engine Overview

The Attention Engine receives the Query, Key, Value matrices from the
Projection Engine and executes the $MVMDynamic$ operations in the CMOS
processing tiles. To implement these multiheaded attention layers, the
attention engine is composed of multiple attention head compute tiles (AHCT)
that are connected via a shared bus, an on-chip transposable input buffer and
a global attention scheduler to distribute the Query, Key and Value inputs to
the tiles. Each AHCT is further divided into multiple banks composed of
multiple 8T-SRAM cells, shift and add blocks (SnA), additional scratchpads to
store partial sums and intermediate outputs and a special functional unit
(SFU) to implement softmax and other vector operations. We chose 8T-SRAM cells
to perform the matrix vector multiplication operations due to their decoupled
read and write paths, thereby ensuring that the values are stored more
robustly. The global attention scheduler assigns the Query and Value matrices
to their respective banks in the AHCT. The Query and Value matrices are then
written by enabling the write wordlines of the 8T-SRAM cells and driving the
write bitlines to high or low depending on the value to be stored. Next, the
key matrix is streamed as transposed individual vectors sequentially into the
Query banks, and the matrix vector multiplication operation between the Key
vector and Query matrix is computed in the analog domain to obtain the
intermediate attention output. We note that similar to the Projection Engine,
bit-slicing and bit-streaming are used when executing multi-bit MVM
operations. The partial intermediate attention outputs are shifted and added
using the shift and add (SnA) block and then stored in the accumulator. The
accumulated outputs across Query banks are now processed by SFU to perform the
softmax operation. The SFU consists of multiple vector units (VUs) that
provides logic units such as adders, multipliers, etc. to implement simple
operations such as addition, division, multiplication and exponentiation.
Finally, this procedure is repeated for the MVM operation between the
intermediate attention output matrix and the previously written Value matrix
to get the final attention output. The output matrix is communicated back to
the Projection Engine to process the feed forward layers. The Block Sequence
Accumulator provides hardware support for sequence blocking dataflow,
explained in more detail in Section V. All the AHCTs work in parallel to
produce the final attention output, and we repeat this approach for all the
layers.

##  V Dataflow

In this section, we describe the overall dataflow of our architecture. We
first model and implement Transformers using traditional weight, Query/Value
stationary dataflow. Later, we also propose a new sequence blocking dataflow
to overcome some of the limitations of the earlier dataflow such as low
hardware utilization and high intermediate output storage requirements. We
outline both the approaches in detail considering a batch size of 1. We refer
to the sequence length as SL, hidden size as HS and the hidden size within a
AHCT as HSS. Both HS and HSS are properties of the language model being
simulated.

Figure 5: (a) Active cycles of Projection Engine and Attention Engine during
traditional dataflow where SL input vectors are processed and sequence
blocking dataflow when SB input vectors are processed (The cycle times are not
drawn to scale), (b) Weight stationary dataflow in Projection Engine (Left)
and Query/Value stationary dataflow in a AHCT of the Attention Engine (Right)
when SL input vectors are processed

###  V-A Traditional Dataflow

Projection Engine - Weight Stationary. In this approach, the Projection Engine
first processes an entire batch of input sequences before the Attention Engine
starts computing the attention output. We adopt a weight stationary dataflow
where the model weights are distributed spatially and reused across all the
input sequences. Figure 5(b) illustrates the process of generating the Query,
Key and Value matrices for an input batch size of 1. An input sequence of size
SL x HS resides in the shared memory of the Projection Engine. Once the
controller delegates the cores that need to process a subset of the input, the
input data is sent to the local scratchpads within a tile and in a fixed
number of cycles, a vector Vk of size SL x 1 is processed by the NVM crossbars
(MVM operation) to output a vector Ok of size HS x 1. This is repeated
multiple times until the entire length of the sequence is processed to obtain
Query, Key and Value matrices of size SL x HS. Owing to the storage density of
NVM crossbars, the weights are distributed spatially across different tiles
for these input matrices. Therefore, the matrix vector multiplication
operation is parallelized for the generation of all the three matrices.

Attention engine – Query/Value stationary. The attention engine dataflow is
described in Figure 5(b). Once the Query, Key and Value matrices of size SL x
HS are generated, they are split into smaller matrices of size HSS x SL and
processed by each AHCT (Attention head). All the AHCTs operate in parallel and
the outputs are concatenated together to obtain the final attention output. To
process a HSS x SL matrix within an AHCT, we first load and write the entire
Query and Value matrices into the 8T-SRAM cells of their respective banks. The
write operation is performed only once for a sequence since we reuse the Query
matrix for the entire sequence length. Next, we step through the set of Key
vectors of size HSS x 1 SL times and aggregate the partial sums in the
accumulator to obtain the intermediate attention output. Similarly, we step
through the intermediate attention output vectors SL times and perform a
matrix vector multiplication operation with the Value matrix to acquire the
final attention output. We also observed that since the Query, Key and Value
matrices are never reused outside their respective transformer encoder, the
8T-SRAM cells are overwritten for each layer. Consequently, we only provision
enough SRAM tiles to process the largest layer in the network due to limited
area budget. Therefore, the next encoder layer can start processing only after
the current layer is completed.

###  V-B Sequence blocking Dataflow

In the projection engine, we observe that every word in a sequence is handled
independently to generate the Query, Key and Value matrices. We apply this
fact to propose a sequence blocking dataflow, shown in Figure 5(a) where a
block of words in a sequence is processed together at once before the next
block of words. This is not synonymous to changing the sequence length for the
input because the attention score is computed for every word with respect to
every other word in the overall sequence. We introduce a new parameter called
sequence block (SB), which is a subset of the total sequence length. We note
that multiple sequence blocks make up a sequence.

We identified two major inefficiencies with the traditional dataflow. First,
the utilization of the proposed hardware architecture is low because the
Attention Engine is fully idle when the Projection Engine is computing the
Query, Key, Value vectors and vice-versa. This mainly arises due to the inter-
dependencies between different layers within a transformer block. With
sequence blocking dataflow, once an SB length of Query, Key and Value is
processed, the attention engine can start computing the attention scores.
Similarly, when the attention engine is working on the previous SB, the
projection engine can process the next set of inputs, keeping both the engines
utilized. In addition, there is an overhead associated with storing the
partial sums until the product of the length of each sequence block and the
number of sequence blocks equals the length of the overall sequence. As shown
in section VII, this cost is negligible in comparison to the benefits of
sequence blocking.

Figure 6: Intermediate activation storage requirements for increasing sequence
lengths with traditional dataflow and sequence blocking dataflow

Next, since the entire sequence is processed by the Attention Engine at once,
the intermediate attention output size becomes SL x SL. As the sequence length
increases, this size scales quadratically, which leads to high on-chip memory
requirements. In contrast, sequence blocking dataflow ensures that the
intermediate attention output size (SB x SB) doesn’t change, since it only
depends on the sequence block length and not the total sequence length.

##  VI Experimental Methodology

This section explains the experimental setup and methodology used to evaluate
X-Former.
System-level modeling. We developed an architecture simulator for X-Former to
model and evaluate the different operations in the transformer network. We
obtained separate timing and power models for the resistive crossbar, DAC and
ADC for the Projection Engine from [14]. For the AHCT modules, we performed
SPICE simulations for the MVM operations (8T-SRAM macro) to obtain power and
write energy measurements. We obtained the Successive Approximation Register
(SAR) ADC power measurements from [28]. Other digital units were modeled as
Register Transfer Level (RTL) units and synthesized using 32nm CMOS
technology. We measured their power consumption using the Synopsys Design
Compiler. The execution timing and power for all the on-chip memories were
modeled using the CACTI simulator [29]. Finally, we integrated both the
Projection Engine and Attention Engine into PUMAsim [14] to obtain the
execution traces and estimate the overall latency and energy. Table I
describes the micro-architectural configuration for X-Former that achieves the
most optimal performance. We report the raw performance metrics of X-Former
compared to a NVIDIA GPU in Table IV.

TABLE I: X-Former Micro-architectural Configuration Parameter |  Value
---|---
Operating Frequency |  1 GHz
NVM device |  ReRAM - 2bit
NVM Resistance |  100k$\Omega$ \- 1M$\Omega$
Crossbar Dimension |  128x128
DAC |  1-bit
ADC |  2/crossbar, 8-bit @ 1.28GS/s
Projection Engine Config |  36 tiles; 8 cores/tile, 6 crossbars/core
Shared Memory |  384KB
Input/Output scratchpad |  4KB
Attention Engine Config |  2; 16 AHCT/PE, 8 banks/AHCT, 6 8T-SRAM cells/bank
SFU |  16 VU with 4 lanes each
Block Sequence Accumulator |  6KB
TABLE II: Summary of Network Topology Variable |  BERT-base |  BERT-large
---|---|---
# heads |  12 |  16
# layers |  12 |  24
Hidden size (HS) |  768 |  1024
Hidden size/head (HSS) |  64 |  64
Bit-width (W, Q, K, V) |  (8, 8, 8, 8) |  (8, 8, 8, 8)
TABLE III: Summary of Benchmarks Dataset |  Description |  max_sequence_length (SL)
---|---|---
GLUE [30] |  Collection of nine different language understanding tasks |  512
SQuAD [31] |  Question-Answering Tasks; max_query_length = 64, doc_stride = 128 |  384
TABLE IV: Performance metrics  Performance Metric |  NVIDIA GeForce GTX 1060 GPU |  X-Former |  X-Former with Sequence blocking Dataflow
---|---|---|---
Latency/inference |  51.46 ms |  7.94 ms |  0.98 ms
TOPS/W |  0.0158 |  0.837 |  6.72

Network architectures and Benchmarks. We evaluated X-Former on the benchmarks
specified in Table III using network configurations described in Table II. We
note that for GLUE benchmark, the final results are an average over all the
downstream tasks. In SQuAD benchmark, the doc_stride parameter denotes the
stride length when a long document is split and max_query_length indicates the
maximum number of tokens in a question [32].

##  VII Results

In this section, we evaluate X-Former using different metrics and illustrate
the benefits.

###  VII-A Accuracy Evaluation

Figure 7: Application level accuracy degradation of Bert-Base and Bert-Large
due to analog computations for a sequence length of 512

Due to the analog nature of computations in X-Former, functional errors are
introduced in the inference pass that impacts the overall application level
accuracy [33, 34]. The major sources of errors are device and circuit non-
idealities which occur during both read and write operations. These circuit
non-idealities arise from source and sink resistances in the peripheral
circuitry, wire parasitic resistances in the metal lines of the crossbar and
sneak paths. Similarly, device non-idealities include process variations and
write non-linearity. The cumulative effect of these non-idealities manifest as
errors in both $MVMStatic$ and $MVMDynamic$ operation outputs. We investigated
the impact of these inaccuracies for Bert-Base and Bert-Large for a sequence
classification (WNLI) task under different process variations using the
NeuroSim simulator [34] and summarize the results in Figure 7. The accuracy of
the ideal software implementation (var=0) is 56.34 %. At the lower device
variation regime (0-0.2), we observe less than 1% loss in accuracy. However,
for larger variations, we observe approximately 4.2 % error for Bert-Base and
9.87 % error for Bert-Large network. The accuracy degradation of Bert-Large is
higher due to errors accumulating over larger number of layers. We note that
there has been active research in the devices and materials community to
engineer devices with lower process variations. Moreover, this is a energy-
accuracy tradeoff that has been widely studied and several mitigation
strategies proposed [35] to recover the accuracy comparable to the ideal
software implementation.

###  VII-B Performance Results

Figure 8: Normalized speedup results for varying sequence lengths for GLUE and
SQUAD benchmarks.BB refers to Bert-base, BL refers to Bert-Large, GL refers to
GLUE dataset and SQ refers to SQuAD dataset (Large values clipped)

Figure 8 shows the normalized speedup results with reference to the execution
time of a NVIDIA GeForce GTX 1060 GPU. We consider two variations of X-Former:
(i) Without Sequence Blocking dataflow where the execution of the Projection
Engine and Attention Engine do not overlap (ii) With the proposed sequence
blocking (SB=64) dataflow. We also compare our results with an in-memory NVM
accelerator [14] where the $MVMDynamic$ operations are executed in the
temporal 1-D SIMD lanes instead of the NVM tiles due to limited endurance.
First, without sequence blocking, we observe upto 10x benefits on average for
both GLUE and SQuAD benchmarks over GPU. This is because X-Former is a highly
parallel spatial in-memory architecture. Moreover, we also observe
improvements compared to a traditional NVM in-memory accelerator since the
Attention Engine is more efficient in processing the MVM operation compared to
the 1-D SIMD module (vector-vector operations). Next, we notice additional
improvements with sequence blocking, upto 85x and 81x for GLUE and SQuAD
benchmarks respectively because the Attention Engine is inactive only until
the Projection Engine processes a subset of the input instead of the entire
sequence length. Therefore, both the engines work efficiently with higher
utilization, resulting in better throughput. In addition, the size of the
intermediate activations are a function of the sequence block (SB) rather than
the total length of the sequence. Consequently, the size of the intermediate
activations reduces significantly, eliminating the need for off-chip accesses.
We note that, as shown in Figure 8, for larger sequence lengths, the speedup
deteriorates because the matrix vector multiplication operation starts
consuming a larger fraction of the execution time.

Figure 9: Performance benefits of X-Former compared to a crossbar architecture
with NVMIdeal device

We also compare X-Former with two in-memory architectures with homogeneous
memory technologies and explain the advantages of our hybrid solution. First,
we consider an ideal scenario where there exists an NVM device (NVMIdeal) that
offers very high endurance and negligible write errors. For our evaluations,
we assume an existing crossbar architecture that has the same technology node
and area as X-Former and all the MVM operations mapped to the NVM tiles. As
shown in Figure 9, our architecture achieves 8.1x speedup over the NVM
architecture. This is due to NVMs requiring high latency for performing the
$MVMDynamic$ operations (both write and compute included). We also note that
sequence blocking dataflow cannot be implemented in the crossbar architecture
with NVMIdeal device since the Attention Engine requires additional execution
time due to the write latency, which increases the inactivity of the
Projection Engine and results in under-utilization of the hardware.

Figure 10: Normalized speedup and energy efficiency of X-Former compared to
baseline in-memory SRAM architecture

Next, we consider an in-memory SRAM setup under iso-area, where both the
$MVMStatic$ and the $MVMDynamic$ operations are computed in the SRAM arrays.
We note that the bit cell area of 1T-1R ReRAM is approximately 8F2 while the
area of an SRAM cell is 150F2. Even though some of this density advantage is
lost due to peripherals, the effective area of ReRAM arrays is much lower than
SRAM arrays. Therefore, under the iso-area baseline, an off-chip DRAM is
modeled from which the weights are fetched as required. We adopt a temporal
architecture design for the in-memory SRAM setup (X-Former is spatial), where
weights are written into the Projection Engine and Attention Engine. Other
effects such as writing to the SRAM cells are also considered. Although
$MVMStatic$ and $MVMDynamic$ operations can be scheduled in both the engines
due to homogeneity, most of the tiles are required to process only one type of
compute. This is because the majority of the chip is required to process
$MVMDynamic$ and performing the attention computation for that layer can cause
overwriting of some layer weights. We also observe that only a tiny fraction
of the off-chip access latency can be hidden when $MVMDynamic$ is executed
since it is 4.55x slower.

In Figure 10, we compare the speedup and energy efficiency of X-former with
the in-SRAM accelerator for GLUE tasks and a sequence length of 512. We
observe that X-former with the traditional dataflow is 1.82x and 2.03x for
Bert-Base and Bert-Large networks respectively. This speedup is due to
X-former not requiring any off-chip accesses since ReRAMs are dense and can
store the weights of all the layers on chip. Similarly, the energy efficiency
is 52.1x and 36.8x due to the off-chip accesses and SRAM write energy. The
latency can be further optimized by adopting a sequence blocking dataflow for
X-Former.

###  VII-C Energy Results

Figure 11: Normalized energy efficiency of X-Former compared to NVIDIA GPU and
a state-of-the-art in-memory accelerator

Figure 11 shows the normalized energy efficiency of X-Former compared to a GPU
and an in-memory NVM accelerator for two different benchmarks. In order to
calculate the GPU energy, we measured the average power and execution time
using utility tools such as nvidia-smi. We achieve 4.85x-7.5x and 3.52x-5.31x
energy benefits for GLUE and SQuAD benchmarks respectively with different
configurations of the transformer network. Since NVMs provide very high
storage density, the weights are already programmed in-memory leading to low
data movement costs. However, GPUs require a large number of off-chip
accesses, which increases its overall energy.

Figure 12: Energy breakdown of running a single Transformer encoder in
X-Former for a sequence length of 512

As shown in Figure 12, we report the overall energy breakdown of different
components of the X-Former architecture for GLUE benchmark. We observe that,
out of 15.2 $\mu$J, the majority of energy (58%) is consumed in computing the
relevance scores in the Attention Engine while 28% is spent on generating the
query, key and value outputs in the Projection Engine. Although the number of
FLOPs for $MVMDynamic$ operations is lower (35%) than $MVMStatic$ operations
(65%) for a sequence length of 512, a larger fraction of the energy is spent
on computing attention scores because the dynamic power required to perform an
MVM operation using a CMOS memory array is 4x more than the NVM memory array
[36]. We also observe that the attention engine write energy is only 2% (0.27
$\mu$J) of the overall write energy since CMOS processing elements are used to
process attention even though the FLOPs distribution is high. We note that the
block sequence accumulator and SFU in the attention engine only contribute a
very tiny fraction (0.02 %) of the total attention engine energy.

We also present the energy breakdown in terms of different operations within a
transformer encoder as shown in Figure 13. Note that Q gen, K gen and V gen
are processed by Projection Engine while Q x KT and Att x V layers are
realized using the Attention Engine. The ADC energy is more dominant (36.8%)
in NVM processing elements while it contributes lesser to the overall MVM
energy in Attention Engine (12.1%) since the ratio of MVM compute energy to
ADC energy in a CMOS memory array is higher than the NVM memory array.

Figure 13: Energy breakdown of all MVM operations in a attention layer for a
sequence length of 512

###  VII-D Scaling X-Former

X-Former consists of a combination of ReRAM cells as in-memory compute (IMC)
units to store model weights, ReRAM as standard memory to store embedding
weights, SRAM cells as IMC units and buffers for inputs and outputs,
intermediate activations and partial sums. Since we need the SRAM arrays to
only store a single layer of the network, the attention engine in X-Formercan
scale to arbitrary number of layers. We would only need more ReRAM cores in
the Projection Engine to store the model weights. Like most previous NVM
architectures, we assume a spatial architecture, where the amount of ReRAM
tiles needs to be increased to support the larger networks. The reason for
this design choices the limited endurance problem of ReRAM and very high write
energy costs. An alternate approach would be to scale X-Former to multiple
nodes with chip-to-chip interconnects.

##  VIII Conclusion

Transformer networks are a promising class of machine learning workloads that
have greatly improved the state of the art accuracy in a wide variety of
natural language processing tasks. However, these networks possess several
memory and computational challenges that prohibit traditional deep learning
accelerators to realize them efficiently. To this end, we propose X-Former, a
hybrid in-memory accelerator consisting of both NVM and CMOS processing tiles
that can store the model weights and perform $MVMDynamic$ operations
efficiently. We also propose a intra-layer sequence blocking dataflow to
improve the hardware utilization and reduce the size of the intermediate
activations. Our evaluations, considering different network configurations and
benchmarks, reveal that X-Former can lead to significant improvements in
latency and energy over a NVIDIA GeForce GTX 1060 GPU and a previously
proposed state-of-the-art in-memory NVM accelerator.

##  IX Acknowledgment

This work was supported by C-BRIC, one of six centers in JUMP, a Semiconductor
Research Corporation (SRC) program, sponsored by DARPA.

## References

  * [1] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: pre-training of deep bidirectional transformers for language understanding.  In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers), pages 4171–4186. Association for Computational Linguistics, 2019.
  * [2] T.B. Brown et al.  Language models are few-shot learners.  In Advances in Neural Information Processing Systems, volume 33, pages 1877–1901. Curran Associates, Inc., 2020.
  * [3] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A.N. Gomez, L. Kaiser, and I. Polosukhin.  Attention is all you need.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
  * [4] N.P. Jouppi et al.  In-datacenter performance analysis of a tensor processing unit.  In Proceedings of the 44th Annual International Symposium on Computer Architecture (ISCA), page 1–12, New York, NY, USA, 2017. Association for Computing Machinery.
  * [5] N. Verma, H. Jia, H. Valavi, Y. Tang, M. Ozatay, L.Y. Chen, B. Zhang, and P. Deaville.  In-memory computing: Advances and prospects.  IEEE Solid-State Circuits Magazine, 11(3):43–55, 2019.
  * [6] B. Rajendran, H. Lung, and C. Lam.  Phase change memory — opportunities and challenges.  In 2007 International Workshop on Physics of Semiconductor Devices, pages 92–95, 2007.
  * [7] H. Akinaga and H. Shima.  Resistive random access memory (reram) based on metal oxides.  Proceedings of the IEEE, 98(12):2237–2251, 2010.
  * [8] A. Ankit, I. Hajj, S. Chalamalasetti, S. Agarwal, M. Marinella, M. Foltin, J.P. Strachan, D. Milojicic, W.M. Hwu, and K. Roy.  Panther: A programmable architecture for neural network training harnessing energy-efficient reram.  IEEE Transactions on Computers, PP:1–1, 05 2020.
  * [9] F. Zahoor, T. Zulkifli, and F. Khanday.  Resistive random access memory (RRAM): An overview of materials, switching mechanism, performance, multilevel cell (MLC) storage, modeling, and applications.  Nanoscale Research Letters, Apr 2020.
  * [10] I. Chakraborty, M. Ali, A. Ankit, S. Jain, S. Roy, S. Sridharan, A. Agrawal, A. Raghunathan, and K. Roy.  Resistive crossbars as approximate hardware building blocks for machine learning: Opportunities and challenges.  Proceedings of the IEEE, 108(12):2276–2310, 2020.
  * [11] Y. Tay, M. Dehghani, D. Bahri, and D. Metzler.  Efficient transformers: A survey.  CoRR, abs/2009.06732, 2020.
  * [12] S. Venkataramani, A. Ranjan, S. Banerjee, D. Das, S. Avancha, A. Jagannathan, A. Durg, D. Nagaraj, B. Kaul, P. Dubey, and A. Raghunathan.  Scaledeep: A scalable compute architecture for learning and evaluating deep networks.  In Proceedings of the 44th Annual International Symposium on Computer Architecture (ISCA), page 13–26, New York, NY, USA, 2017. Association for Computing Machinery.
  * [13] Y.H. Chen, J. Emer, and V. Sze.  Eyeriss: A spatial architecture for energy-efficient dataflow for convolutional neural networks.  In 2016 ACM/IEEE 43rd Annual International Symposium on Computer Architecture (ISCA), pages 367–379, 2016.
  * [14] A. Ankit et al.  Puma: A programmable ultra-efficient memristor-based accelerator for machine learning inference.  In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), New York, NY, USA, 2019. Association for Computing Machinery.
  * [15] A. Shafiee, A. Nag, N. Muralimanohar, R. Balasubramonian, J.P. Strachan, M. Hu, R.S. Williams, and V. Srikumar.  Isaac: A convolutional neural network accelerator with in-situ analog arithmetic in crossbars.  In Proceedings of the 43rd International Symposium on Computer Architecture (ISAAC), page 14–26. IEEE Press, 2016.
  * [16] L. Song, X. Qian, H. Li, and Y. Chen.  Pipelayer: A pipelined reram-based accelerator for deep learning.  2017 IEEE International Symposium on High Performance Computer Architecture (HPCA), pages 541–552, 2017.
  * [17] A. Nagarajan, S. Sen, J.R. Stevens, and A. Raghunathan.  Optimizing transformers with approximate computing for faster, smaller and more accurate NLP models.  CoRR, abs/2010.03688, 2020.
  * [18] A. Hadizadeh, I. Edo, O.M. Awadand, and A. Moshovos.  GOBO: Quantizing attention-based NLP models for low latency and energy efficient inference.  In Proceedings of 53rd IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 811–824, 10 2020.
  * [19] H. Wang, Z. Zhang, and S. Han.  Spatten: Efficient sparse attention architecture with cascade token and head pruning.  In 2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA), pages 97–110, 2021.
  * [20] S. Goyal, A.R. Choudhury, V. Chakaravarthy, S. ManishRaje, Y. Sabharwal, and A. Verma.  Power-bert: Accelerating BERT inference for classification tasks.  CoRR, abs/2001.08950, 2020.
  * [21] T.J. Ham, S.J. Jung, S. Kim, Y.H. Oh, Y. Park, Y. Song, J.H. Park, S. Lee, K. Park, J. Lee, and D.K. Jeong.  A3: Accelerating attention mechanisms in neural networks with approximation.  In 2017 IEEE International Symposium on High Performance Computer Architecture (HPCA), 02 2020.
  * [22] J. Park, H. Yoon, D. Ahn, J. Choi, and J. Kim.  Optimus: Optimized matrix multiplication structure for transformer neural network accelerator.  In Proceedings of Machine Learning and Systems (MLSys), 2020.
  * [23] J.R. Stevens, R. Venkatesan, S. Dai, B. Khailany, and A. Raghunathan.  Softermax: Hardware/software co-design of an efficient softmax for transformers.  2021 58th ACM/IEEE Design Automation Conference (DAC), pages 469–474, 2021.
  * [24] T. Tambe et al.  Edgebert: Sentence-level energy optimizations for latency-aware multi-task nlp inference.  In MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture, page 830–844, New York, NY, USA, 2021. Association for Computing Machinery.
  * [25] X. Yang, B. Yan, H. Li, and Y. Chen.  Retransformer: Reram-based processing-in-memory architecture for transformer acceleration.  In 2020 IEEE/ACM International Conference On Computer Aided Design (ICCAD), pages 1–9, 2020.
  * [26] A.F. Laguna, A. Kazemi, M. Niemier, and X. Hu.  In-memory computing based accelerator for transformer networks for long sequences.  In 2021 Design, Automation Test in Europe Conference Exhibition (DATE), pages 1839–1844, 2021.
  * [27] Ye Lin, Yanyang Li, Tengbo Liu, Tong Xiao, Tongran Liu, and Jingbo Zhu.  Towards fully 8-bit integer inference for the transformer model.  In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI’20, 2021.
  * [28] Boris Murmann.  Adc performance survey 1997-2022.  [Online]. Available: https://github.com/bmurmann/ADC-survey.
  * [29] N. Muralimanohar, R. Balasubramonian, and N. Jouppi.  Optimizing nuca organizations and wiring alternatives for large caches with cacti 6.0.  In 40th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO 2007), pages 3–14, 2007.
  * [30] A. Wang, A. Singh, J. Michael, F. Hill, O. Levy, and S. Bowman.  GLUE: A multi-task benchmark and analysis platform for natural language understanding.  In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 353–355, Brussels, Belgium, November 2018. Association for Computational Linguistics.
  * [31] P. Rajpurkar, J. Zhang, K. Lopyrev, and P. Liang.  SQuAD: 100,000+ questions for machine comprehension of text.  In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2383–2392, Austin, Texas, November 2016. Association for Computational Linguistics.
  * [32] T. Wolf et al.  Transformers: State-of-the-art natural language processing.  In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pages 38–45, Online, October 2020. Association for Computational Linguistics.
  * [33] Sourjya Roy, Shrihari Sridharan, Shubham Jain, and Anand Raghunathan.  Txsim: Modeling training of deep neural networks on resistive crossbar systems.  IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 29(4):730–738, 2021.
  * [34] Anni Lu, Xiaochen Peng, Wantong Li, Hongwu Jiang, and Shimeng Yu.  Neurosim simulator for compute-in-memory hardware accelerator: Validation and benchmark.  Frontiers in Artificial Intelligence, 4, 2021.
  * [35] Shubham Jain and Anand Raghunathan.  Cxdnn: Hardware-software compensation methods for deep neural networks on resistive crossbar systems.  ACM Trans. Embed. Comput. Syst., 18(6), nov 2019.
  * [36] Mustafa Ali, Indranil Chakraborty, Utkarsh Saxena, Amogh Agrawal, Aayush Ankit, and Kaushik Roy.  A 35.5-127.2 tops/w dynamic sparsity-aware reconfigurable-precision compute-in-memory sram macro for machine learning.  IEEE Solid-State Circuits Letters, 4:129–132, 2021.