# Final Sentential Forms

Tomáš Kožár Faculty of Information Technology
Brno University of Technology
Czech Republic<EMAIL_ADDRESS>Faculty of Information Technology
Brno University of Technology
Czech RepublicFaculty of Information Technology
Brno University of Technology
Czech Republic Zbyněk Křivka Faculty of Information Technology
Brno University of Technology
Czech Republic<EMAIL_ADDRESS>Faculty of Information Technology
Brno University of Technology
Czech Republic Alexander Meduna Faculty of Information Technology
Brno University of Technology
Czech Republic<EMAIL_ADDRESS>
###### Abstract

Let $G$ be a context-free grammar with a total alphabet $V$, and let $F$ be a
final language over an alphabet $W\subseteq V$. A final sentential form is any
sentential form of $G$ that, after omitting symbols from $V-W$, it belongs to
$F$. The string resulting from the elimination of all nonterminals from $W$ in
a final sentential form is in the language of $G$ finalized by $F$ if and only
if it contains only terminals.

The language of any context-free grammar finalized by a regular language is
context-free. On the other hand, it is demonstrated that $L$ is a recursively
enumerable language if and only if there exists a propagating context-free
grammar $G$ such that $L$ equals the language of $G$ finalized by
$\\{w\\#w^{R}\,|\,w\in\\{0,1\\}^{*}\\}$, where $w^{R}$ is the reversal of $w$.

##  1 Introduction

The present paper introduces and studies final sentential forms of context-
free grammars. These forms represent the sentential forms in which the
sequences of prescribed symbols, possibly including nonterminals, belong to
given final languages. If all the other symbols are terminals, these final
forms are changed to the sentences of the generated languages by simply
eliminating all nonterminals in them. Next, we sketch both a practical
inspiration and a theoretical reason for introducing this new way of context-
free language generation.

  1. I.

Indisputably, parsing represents a crucially important application area of
ordinary context-free grammars (see Chapters 3 through 5 in [5]) as well as
their modified versions, such as regulated grammars (see Section 20.3 in [7]).
During the parsing process, the correctness of the source program syntax is
often verified before all nonterminals are eliminated; nevertheless, most
classically constructed parsers go on eliminating these nonterminals by using
erasing rules until only terminals are derived. As a result, the entire
parsing process is slowed down uselessly during this closing phase (for a
simple, but straightforward illustration of this computational situation, see,
for instance, Case Study 14/35 in [5] or Example 4.35 in [2]). Clearly, as the
newly introduced way of language generation frees us from a necessity of this
closing elimination of all nonterminals, the parsers that make use of it work
faster.

  2. II.

From a theoretical viewpoint, in the present paper, we achieve a new
representation for recursively enumerable languages based upon context-free
languages. Admittedly, the theory of formal languages is overflown with many
representations for recursively enumerable languages based upon operations
over some context-free languages or their special cases (see Section 4.1.3 in
[8]). Nonetheless, we believe this new representation is of some interest when
compared with the previously demonstrated representations. Indeed, each of the
already existing representations is demonstrated, in essence, by a proof that
has the following general format. (i) First, given any recursively enumerable
language $L$, it represents $L$ by a suitable language model $G$, such as a
phrase structure grammar in a normal form. (ii) Then, from $G$, it derives
both operations and context-free languages involved in the representation in
question. (iii) Finally, it shows that the representation made in this way
from $G$ holds true. What is important from our standpoint is that in a proof
like this, the specific form of all the operations as well as the languages
involved in the representation always depend on $G$, which generates $L$. As
opposed to this, the new representation achieved in the present paper is much
less dependent on $L$ or any of its language models . More precisely, we
demonstrate the existence of a unique constant language $C$ defined as
$C=\\{w\\#w^{R}\,\,|\,w\in\\{0,1\\}^{*}\\}$ and express any recursively
enumerable language $L$ by using $C$ and a minimal linear language without any
operation. Consequently, $C$ always remains unchanged and, therefore,
independent of $L$ or its models. Considering this independency as well as the
absence of any operations in the new representation, we believe this
representation might be of some interest to formal language theory.

To give a more detailed insight into this study, we first informally recall
the notion of an ordinary context-free grammar and its language (this paper
assumes a familiarity with formal language theory). A context-free grammar $G$
is based upon a grammatical alphabet $V$ of symbols and a finite set of rules.
The alphabet $V$ is divided into two disjoint subalphabets—the alphabet of
terminals $T$ and the alphabet of nonterminals $N$. Each rule has the form
$A\to x$, where $A$ is a nonterminal and $x$ is a string over $V$. Starting
from a special start nonterminal, $G$ repeatedly rewrites strings according to
its rules, and in this way, it generates its sentential forms. Sentential
forms that consist only of terminal symbols are called sentences, and the set
of all sentences represents the language generated by $G$.

In this paper, we shortened the generating process sketched above by
introducing a final language $F$ over a subalphabet $W\subseteq V$. A final
sentential form of $G$ is any of the sentential forms in which the sequence of
symbols from $W$ belong to $F$. If in this form, all the symbols from $V-W$
are terminals, the string obtained by eliminating all nonterminals from $N\cap
W$ results into a sentence of the generated language $L(G,F)$ finalized by
$F$.

Next, we illustrate the newly introduced concept of final sentential forms by
a simple example in linguistic morphology, which studies word formation, such
as inflection and compounding, in natural languages.

######  Example 1.

Consider an alphabet $\Sigma$ of consonants and vowels. Suppose that a
morphological study deals with a language $L$ consisting of all possible words
over $\Sigma$ together with their consonant-vowel binary schemes in which
every consonant and every vowel are represented by 1 and 0, respectively.
Mathematically, $L=\\{w\\#\sigma(w)\,|\,w\in\Sigma^{+}\\}$, where $\sigma$ is
the homomorphism from $\Sigma^{*}$ to $\\{0,1\\}^{*}$ defined as $\sigma(x)=1$
and $\sigma(y)=0$ for every consonant $x$ in $\Sigma$ and every vowel $y$ in
$\Sigma$, respectively. For instance, considering $\Sigma$ as the English
alphabet, $the\\#110\in L$ while $the\\#100\not\in L$. Define the context-free
grammar $G$ with the following rules.

  * •

$S\to A\\#B$, $B\to 0YB$, $B\to 0Y$, $B\to 1XB$, $B\to 1X$,

  * •

$A\to aAY$, $A\to aY$ for all vowels $a$ in $\Sigma$,

  * •

$A\to bAX$, $A\to bX$ for all consonants $b$ in $\Sigma$,

where the uppercase symbols are nonterminals with $S$ being the start
nonterminal, and the other symbols are terminals. Set $W=\\{X,Y,\\#\\}$ and
$F=\\{w\\#w^{R}\,|\,w\in\\{X,Y\\}^{*}\\}$. For instance, take this step-by-
step derivation

$\displaystyle S$ $\displaystyle\Rightarrow A\\#B\Rightarrow
tAX\\#B\Rightarrow thAXX\\#B\Rightarrow theYXX\\#B$ $\displaystyle\Rightarrow
theYXX\\#1XB\Rightarrow theYXX\\#1X1XB\Rightarrow theYXX\\#1X1X0Y$

In $theYXX\\#1X1X0Y$, $YXX\\#XXY\in F$, and apart from $X,Y,\\#\in W$,
$theYXX\\#1X1X0Y$ contains only terminals. The removal of all $X$s and $Y$s in
$theYXX\\#1X1X0Y$ results into $the\\#110$, which thus belongs to $L(G,F)$. On
contrary,

$\displaystyle S$ $\displaystyle\Rightarrow^{*}theYXX\\#1X1XB\Rightarrow
theYXX\\#1X1X0YB=\gamma\Rightarrow theYXX\\#1X1X0Y0Y=\delta$

Let $T=\Sigma\cup\\{0,1\\}$. Consider $\gamma$. Although $YXX\\#XXY\in F$,
$the\\#110B\notin L(G,F)$ since $B\notin W\cup T$. On the other hand,
considering $\delta$, after omitting symbols from $W-T$, we have
$the\\#1100\in T^{*}$, but since $YXX\\#XXYY\notin F$, $the\\#1100\notin
L(G,F)$.

Clearly, $L(G,F)=L$.

As its main result, the present paper demonstrates that $L$ is a recursively
enumerable language if and only if
$L=L(G,\\{w\\#w^{R}\,|\,w\in\\{0,1\\}^{*}\\})$, where $G$ is a context-free
grammar; observe that in this equivalence, the final language
$\\{w\\#w^{R}\,|\,w\in\\{0,1\\}^{*}\\}$ remains constant independently of $L$.
On the other hand, the paper also proves that any $L(G,F)$ is context-free if
$G$ is a context-free grammar and $F$ is regular.

The rest of the paper is organized as follows. First, Section 2 gives all the
necessary terminology and defines the new notions, informally sketched in this
introduction. Then, Section 3 establishes the above-mentioned results and
points out an open problem related to the present study.

##  2 Preliminaries and Definitions

This paper assumes that the reader is familiar with the language theory (see
[6]).

For a set $Q$, $card(Q)$ denotes the cardinality of $Q$. For an alphabet $V$,
$V^{*}$ represents the free monoid generated by $V$ under the operation of
concatenation. The unit of $V^{*}$ is denoted by $\varepsilon$. Set $V^{+}$ =
$V^{*}$ \- $\\{\varepsilon\\}$; algebraically, $V^{+}$ is thus the free
semigroup generated by $V$ under the operation of concatenation. For $w\in
V^{*}$, $|w|$ and $w^{R}$ denotes the length of $w$ and the reversal of $w$,
respectively. Let $W$ be an alphabet and $\omega$ be a homomorphism from
$V^{*}$ to $W^{*}$ (see [6] for the definition of homomorphism); $\omega$ is a
weak identity if $\omega(a)\in\\{a,\varepsilon\\}$ for all $a\in V$.

A context-free grammar (CFG for short) is a quadruple $G=(V,T,P,S)$, where $V$
is an alphabet, $T\subseteq V$, $P\subseteq(V-T)\times V^{*}$ is finite, and
$S\in V-T$. Set $N=V-T$. The components $V,T,N,P$, and $S$ are referred to as
the total alphabet, the terminal alphabet, the nonterminal alphabet, the set
of rules, and the start symbol of $G$, respectively. Instead of $(A,x)\in P$,
we write $A\to x\in P$ throughout. For brevity, we often denote $A\to x$ by a
unique label $p$ as $p:A\to x$, and we briefly use $p$ instead of $A\to x$
under this denotation. For every $p:A\to x\in P$, the left-hand side of $p$ is
defined as $lhs(p)=A$. The grammar $G$ is propagating if $A\to x\in P$ implies
$x\in V^{+}$. The grammar $G$ is linear if no more than one nonterminal
appears on the right-hand side of any rule in $P$. Furthermore, a linear
grammar $G$ is minimal (see page 76 in [9]) if $N=\\{S\\}$ and $S\to\\#\in P$,
$\\#\in T$, is the only rule with no nonterminal on the right-hand side,
whereas it is assumed that $\\#$ does not occur in any other rule. In this
paper, a minimal linear grammar $G$ is called a palindromial grammar if
$card(P)\geq 2$, and every rule of the form $S\to xSy$, where $x,y\in T^{*}$,
satisfies $x=y$ and $x,y\in T$. For instance,
$H=(\\{S,0,1,\\#\\},\\{0,1,\\#\\},\\{S\to 0S0,S\to 1S1,S\to\\#\\},S)$ is a
palindromial grammar.

For every $u,v\in V^{*}$ and $p:A\to x\in P$, write $uAv\Rightarrow uxv\,[p]$
or, simply, $uAv\Rightarrow uxv$; $\Rightarrow$ is called the direct
derivation relation over $V^{*}$. For $n\geq 0,\Rightarrow^{n}$ denotes the
$n$-th power of $\Rightarrow$. Furthermore, $\Rightarrow^{+}$ and
$\Rightarrow^{*}$ denote the transitive closure and the transitive-reflexive
closure of $\Rightarrow$, respectively. Let $\phi(G)=\\{w\in V^{*}|$
$S\Rightarrow^{*}w\\}$ denotes the set of all sentential forms of $G$. The
language of $G$ is denoted by $L(G)$ and defined as $L(G)=T^{*}\cap\,\phi(G)$.
For example, $L(H)=\\{w\\#w^{R}\,|\,w\in\\{0,1\\}^{*}\\}$, where $H$ is
defined as above.

Let $G=(V,T,P,S)$ be a CFG and $W\subseteq V$. Define the weak identity
$\prescript{}{W}{\omega}$ from $V^{*}$ to $W^{*}$ as
$\prescript{}{W}{\omega}(X)=X$ for all $X\in W$, and
$\prescript{}{W}{\omega}(X)=\varepsilon$ for all $X\in V-W$. Let $F\subseteq
W^{*}$. Set

$\displaystyle\phi(G,F)=\\{x\,|\,x\in\phi(G),\,\prescript{}{W}{\omega}(x)\in
F\\}$ $\displaystyle
L(G,F)=\\{\,\prescript{}{T}{\omega}(y)\,|\,y\in\phi(G,F),\prescript{}{(N-W)}{\omega}(y)=\varepsilon\\}.$

$\phi(G,F)$ and $L(G,F)$ are referred to as the set of sentential forms of $G$
finalized by $F$ and the language of $G$ finalized by $F$, respectively.
Members of $\phi(G,F)$ are called final sentential forms.
$\mathbf{REG},\mathbf{PAL},\mathbf{LIN},\mathbf{CF}$, and $\mathbf{RE}$ denote
the families of regular, palindromial, linear, context-free, and recursively
enumerable languages, respectively. Observe that

$\textbf{REG}\cap\textbf{PAL}=\emptyset\text{ and
}\mathbf{REG}\cup\mathbf{PAL}\subset\mathbf{LIN}.$

Set

$\displaystyle\mathbf{CF_{PAL}}=\\{L(G,F)\,|\,G\text{ is a CFG,
}F\in\mathbf{PAL}\\}$ $\displaystyle\mathbf{CF_{REG}}=\\{L(G,F)\,|\,G\text{ is
a CFG, }F\in\mathbf{REG}\\}$

######  Example 2.

Set $I=\\{i(x)\,|\,x\in\\{0,1\\}^{+}\\}$, where $i(x)$ denotes the integer
represented by $x$ in the standard way; for instance, $i(011)=3$. Consider

$L=\\{u\\#v\,|\,u,v\in\\{0,1\\}^{+}\text{, }i(u)>i(v)\text{ and }|u|=|v|\\}.$

Next, we define a CFG $G$ and $F\in\mathbf{PAL}$ such that $L=L(G,F)$. Let
$G=(V,T,P,S)$ be a context-free grammar. Set
$V=\\{S,X,\overline{X},Y,\overline{Y},A,B,C,D,0,1,\\#\\}$, $T=\\{0,1,\\#\\}$,
and set $P$ as the set of the following rules

  * •

$S\to X\\#\overline{X}$,

  * •

$X\to 1AX$, $X\to 0BX$, $X\to 1CY$, $X\to 1C$,

  * •

$\overline{X}\to 1\overline{X}A$, $\overline{X}\to 0\overline{X}B$,
$\overline{X}\to 0\overline{Y}C$, $\overline{X}\to 0C$,

  * •

$Y\to\alpha DY$, $Y\to\alpha D$, $\overline{Y}\to\alpha\overline{Y}D$,
$\overline{Y}\to\alpha D$ for all $\alpha\in\\{0,1\\}$.

Set $W=\\{A,B,C,D,\\#\\}$ and $F=\\{w\\#w^{R}\,|\,w\in\\{A,B,C,D\\}^{+}\text{
and }n\geq 1\\}$. Observe that $F=L(H)$, where
$H=(\\{S,A,B,C,D,\\#\\},\\{A,B,C,D,\\#\\},\\{S\to ASA,S\to BSB,S\to CSC,S\to
DSD,S\to\\#\\},S)$ is a palindromial grammar. Therefore, $F\in\mathbf{PAL}$.
For instance, take this step-by-step derivation

$\displaystyle S$ $\displaystyle\Rightarrow X\\#\overline{X}\Rightarrow
1AX\\#\overline{X}\Rightarrow 1A0BX\\#\overline{X}\Rightarrow
1A0B1CY\\#\overline{X}\Rightarrow 1A0B1C0D\\#\overline{X}$
$\displaystyle\Rightarrow 1A0B1C0D\\#1\overline{X}A\Rightarrow
1A0B1C0D\\#10\overline{X}BA\Rightarrow 1A0B1C0D\\#100\overline{Y}CBA$
$\displaystyle\Rightarrow 1A0B1C0D\\#1001\overline{Y}DCBA\Rightarrow
1A0B1C0D\\#1001DCBA$

in $G$. Notice that $\prescript{}{W}{\omega}(1A0B1C0D\\#1001DCBA)\in F,$ and
$\prescript{}{T}{\omega}(1A0B1C0D\\#1001DCBA)\in L(G,F)$. The reader is
encouraged to verify that $L=L(G,F)$.

A queue grammar (see [3]) is a sextuple, $Q=(V,T,U,D,s,P)$, where $V$ and $U$
are alphabets satisfying $V\cap\,U=\emptyset$, $T\subseteq V$, $D\subseteq U$,
$s\in(V-T)(U-D)$, and $P\subseteq(V\times(U-D))\times(V^{*}\times U)$ is a
finite relation such that for for every $a\in V$, there exists an element
$(a,b,z,c)\in P$. If $u,v\in V^{*}U$ such that $u=arb;v=rzc;a\in V;r,z\in
V^{*};b,c\in U;$ and $(a,b,z,c)\in P$, then $u\Rightarrow v$ $[(a,b,z,c)]$ in
$G$ or, simply, $u\Rightarrow v$. In the standard manner, extend $\Rightarrow$
to $\Rightarrow^{n}$, where $n\geq 0;$ then, based on $\Rightarrow^{n}$,
define $\Rightarrow^{+}$ and $\Rightarrow^{*}$. The language of $Q$, $L(Q)$,
is defined as $L(Q)=\\{w\in T^{*}\,|\,s\Rightarrow^{*}wf$ where $f\in D\\}$. A
left-extended queue grammar is a sextuple, $Q=(V,T,U,D,s,P)$, where $V,T,U,D$,
and $s$ have the same meaning as in a queue grammar, and
$P\subseteq(V\times(U-D))\times(V^{*}\times U)$ is a finite relation (as
opposed to an ordinary queue grammar, this definition does not require that
for every $a\in V$, there exists an element $(a,b,z,c)\in P)$. Furthermore,
assume that $\\#\notin V\cup U$. If $u,v\in V^{*}\\{\\#\\}V^{*}U$ so that
$u=w\\#arb$; $v=wa\\#rzc$; $a\in V$; $r,z,w\in V^{*}$; $b,c\in U$; and
$(a,b,z,c)\in P$, then $u\Rightarrow v[(a,b,z,c)]$ in $G$ or, simply
$u\Rightarrow v$. In the standard manner, extend $\Rightarrow$ to
$\Rightarrow^{n}$, where $n\geq 0;$ then, based on $\Rightarrow^{n}$, define
$\Rightarrow^{+}$ and $\Rightarrow^{*}$. The language of $Q$, $L(Q)$, is
defined as $L(Q)=\\{v\in T^{*}\,|\,\\#s\Rightarrow^{*}w\\#vf$ for some $w\in
V^{*}$ and $f\in D\\}$. Less formally, during every step of a derivation, a
left-extended queue grammar shifts the rewritten symbol over $\\#;$ in this
way, it records the derivation history, which plays a crucial role in the
proof of Lemma 5 in the next section.

A deterministic finite automaton (DFA for short) is a quintuple
$M=(Q,\Sigma,R,s,F)$, where $Q$ is a finite set of states, $\Sigma$ is an
alphabet of input symbols, $Q\cap\Sigma=\emptyset$, $s\in Q$ is a special
state called the start state, $F\subseteq Q$ is a set of final states in $M$,
and $R$ is a total function from $Q\times\Sigma$ to $Q$. Instead of
$R(q,a)=p$, we write $qa\to p$, where $q,p\in Q$ and
$a\in\Sigma\cup\\{\varepsilon\\}$; $R$ is referred to as the set of rules in
$M$. For any $x\in\Sigma^{*}$ and $qa\to p\in R$, we write $qax\Rightarrow
px$. The language of $M$, $L(M)$, is defined as
$L(M)=\\{w\,|\,w\in\Sigma^{*}$, $sw\Rightarrow^{*}f$, $f\in F\\}$, where
$\Rightarrow^{*}$ denotes the reflexive-transitive closure of $\Rightarrow$.
Recall that DFAs characterize $\mathbf{REG}$ (see page 29 in [6]).

##  3 Results

In this section, we show that every language generated by a context-free
grammar finalized by a regular language is context-free (see Theorem 2). On
the other hand, we prove that every recursively enumerable language can be
generated by a propagating context-free grammar finalized by
$\\{w\\#w^{R}\,|\,w\in\\{0,1\\}^{*}\\}$ (see Theorem 9).

######  Lemma 1.

Let $G=(V,T,P,S)$ be any CFG and $F\in\mathbf{REG}$. Then,
$L(G,F)\in\mathbf{CF}$.

######  Proof.

Let $G=(V,T,P,S)$ be any CFG and $F\in\mathbf{REG}$. Let $F=L(M)$, where
$M=(Q,W,R,q_{s},Q_{F})$ is a DFA.

Construction. Introduce $U=\\{\langle paq\rangle\,|\,p,q\in Q$, $a\in
V\\}\cup\\{\langle q_{s}SQ_{F}\rangle\\}$. From $G$ and $M$, construct a new
CFG $H$ such that $L(H)=L(G,F)$ in the following way. Set

$H=(\overline{V},T,\overline{P},\langle q_{s}SQ_{F}\rangle)$

The components of $H$ are constructed as follows. Set $\overline{V}=V\cup U$
and initialize $\overline{P}$ to $\emptyset$. Construct $\overline{P}$ as
follows:

  1. (0)

Add $\langle q_{s}SQ_{F}\rangle\to\langle q_{s}Sq_{f}\rangle$ for all
$q_{f}\in Q_{F}$.

  2. (1)

Let $A\to y_{0}X_{1}y_{1}X_{2}\dots X_{n}y_{n}\in P$, where $A\in
V-T,y_{i}\in(V-W)^{*}$ and $X_{j}\in V$, $0\leq i\leq n$, $1\leq j\leq n$, for
some $n\geq 1$;
then, add $\langle q_{1}Aq_{n+1}\rangle\to y_{0}\langle q_{1}X_{1}q_{2}\rangle
y_{1}\langle q_{2}X_{2}q_{3}\rangle\dots\langle q_{n}X_{n}q_{n+1}\rangle
y_{n}$ to $\overline{P}$, for all $q_{1},q_{2},\dots,q_{n+1}\in Q$.

  3. (2)

Let $A\to\alpha\in P$, where $A\in V-(T\cup W),\alpha\in(V-W)^{*}$;
then, add $A\to\alpha$ to $\overline{P}$.

  4. (3)

Let $\langle paq\rangle\in U$, where $a\in W\cap T,pa\to q\in R$;
then, add $\langle paq\rangle\to a$ to $\overline{P}$.

  5. (4)

Let $\langle pBq\rangle\in U$, where $pB\to q\in R,B\in W\cap(V-T)$;
then, add $\langle pBq\rangle\to\varepsilon$ to $\overline{P}$.

To prove $L(G,F)=L(H)$, we first prove $L(H)\subseteq L(G,F)$; then, we
establish $L(G,F)\subseteq L(H)$. To demonstrate $L(H)\subseteq L(G,F)$, we
first make three observations—(i) through (iii)—concerning every derivation of
the form $\langle q_{s}Sq_{f}\rangle\Rightarrow^{*}y$ with $y\in T^{*}$.

(i) By using rules constructed in (1) and (2), $H$ makes a derivation of the
form

$\langle q_{s}Sq_{f}\rangle\Rightarrow^{*}x_{0}\langle q_{1}Z_{1}q_{2}\rangle
x_{1}\dots\langle q_{n}Z_{n}q_{n+1}\rangle x_{n}$

where $x_{i}\in(T-W)^{*}$, $0\leq i\leq n$, $\langle
q_{j}Z_{j}q_{j+1}\rangle\in U$, $Z_{j}\in W$, $1\leq j\leq n$, $q_{1}=q_{s}$,
$q_{n+1}=q_{f}$, $q_{1},\dots,q_{n+1}\in Q$, $q_{f}\in Q_{F}$.

(ii) If

$\langle q_{s}Sq_{f}\rangle\Rightarrow^{*}x_{0}\langle q_{1}Z_{1}q_{2}\rangle
x_{1}\dots\langle q_{n}Z_{n}q_{n+1}\rangle x_{n}$

in $H$, then

$S\Rightarrow^{*}x_{0}Z_{1}x_{1}\dots Z_{n}x_{n}$

in $G$, where all the symbols have the same meaning as in (i).

(iii) Let $H$ make

$x_{0}\langle q_{1}Z_{1}q_{2}\rangle x_{1}\dots\langle
q_{n}Z_{n}q_{n+1}\rangle x_{n}\Rightarrow^{*}y$

by using rules constructed in (3) and (4), where $y\in T^{*}$, and all the
other symbols have the same meaning as in (i). Then, for all $1\leq j\leq
n,q_{j}Z_{j}\to q_{j+1}\in R,y=x_{0}U_{1}x_{1}\dots U_{n}x_{n}$, where
$U_{j}=\prescript{}{T}{\omega}(Z_{j})$. As $q_{j}Z_{j}\to q_{j+1}\in R$,
$1\leq j\leq n$, $q_{1}=q_{s}$ and $q_{n+1}=q_{f}$, $q_{f}\in Q_{F}$, we have
$Z_{1}\dots Z_{n}\in L(M)$.

Based on (i) through (iii), we are now ready to prove $L(H)\subseteq L(G,F)$.
Let $y\in L(H)$. Thus, $\langle q_{s}SQ_{F}\rangle\Rightarrow^{*}y$, $y\in
T^{*}$ in $H$. As $H$ is an ordinary CFG, we can always rearrange the
applications of rules during $\langle q_{s}SQ_{F}\rangle\Rightarrow^{*}y$ in
such a way that

$\langle q_{s}SQ_{F}\rangle$ | $\Rightarrow$ | $\langle q_{s}Sq_{f}\rangle$ | $(\alpha)$
---|---|---|---
| $\Rightarrow^{*}$ | $x_{0}\langle q_{1}Z_{1}q_{2}\rangle x_{1}\dots\langle q_{m}Z_{m}q_{m+1}\rangle x_{m}$ | $(\beta)$
| $\Rightarrow^{*}$ | $y$ | $(\gamma)$

so that during ($\alpha$), only a rule from (0) is used, during $\beta$ only
rules from (1) and (2) are used, and during ($\gamma$) only rules from (3) and
(4) are used. Recall that $Z_{1}Z_{2}\dots Z_{n}\in F$ (see (iii)).
Consequently, $\prescript{}{W}{\omega}(x_{0}Z_{1}x_{1}\dots Z_{n}x_{n})\in F$.
From (3), (4), (ii), and (iii), it follows that

$S\Rightarrow^{*}x_{0}Z_{1}x_{1}\dots x_{n-1}Z_{n}x_{n}\text{ in }G\textrm{.}$

Thus, as $L(M)=F$, we have $y\in L(G,F)$, so $L(H)\subseteq L(G,F)$.

To prove $L(G,F)\subseteq L(H)$, take any $y\in L(G,F)$. Thus,

$\displaystyle S\Rightarrow^{*}x_{0}Z_{1}x_{1}\dots x_{n-1}Z_{n}x_{n}\text{ in
}G\textrm{, and}$ $\displaystyle
y=\,\prescript{}{T}{\omega}(x_{0}Z_{1}x_{1}\dots x_{n-1}Z_{n}x_{n})\textrm{
with }Z_{1}\dots Z_{n}\in F$

where $x_{i}\in(T-W)^{*},0\leq i\leq n,Z_{j}\in W,1\leq j\leq n$. As
$Z_{1}\dots Z_{n}\in F$, we have $q_{1}Z_{1}\to q_{2}$, $\dots$,
$q_{n}Z_{n}\to q_{n+1}\in R$, $q_{1},\dots,q_{n+1}\in Q$, $q_{1}=q_{s}$,
$q_{n+1}=q_{f}$, $q_{f}\in Q_{F}$. Consequently, from (0) through (4) of the
Construction, we see that

$\displaystyle\langle q_{s}SQ_{f}\rangle$ $\displaystyle\Rightarrow\langle
q_{s}Sq_{f}\rangle$ $\displaystyle\Rightarrow^{*}x_{0}Z_{1}x_{1}\dots
Z_{n}x_{n}$ $\displaystyle\Rightarrow^{*}x_{0}U_{1}x_{1}\dots U_{n}x_{n}$

where $U_{j}=\,\prescript{}{T}{\omega}(Z_{j})$, $1\leq j\leq n$. Hence, $y\in
L(H)$, so $L(G,F)\subseteq L(H)$.

Thus, $L(G,F)=L(H)$. ∎

######  Theorem 2.

$\mathbf{CF_{REG}}=\mathbf{CF}$.

######  Proof.

Clearly, $\mathbf{CF}\subseteq\mathbf{CF_{REG}}$. From Lemma 1,
$\mathbf{CF_{REG}}\subseteq\mathbf{CF}$. Thus, Theorem 2 holds true. ∎

Now, we prove that by using the constant palindromial language
$\\{w\\#w^{R}\,\,|\,w\in\\{0,1\\}^{*}\\}$ to finalize a propagating context-
free grammar, we can represent any recursively enumerable language.

######  Lemma 3.

Let $L\in\mathbf{RE}$. Then, there exists a left-extended queue grammar $Q$
satisfying $L(Q)=L$.

######  Proof.

See _Lemma_ 1 in [4]. ∎

######  Lemma 4.

Let $H$ be a left-extended queue grammar. Then, there exists a left-extended
queue grammar, $Q=(V,T,U,D,s,R)$, such that $L(H)=L(Q)$ and every
$(a,b,x,c)\in R$ satisfies $a\in V-T$, $b\in U-D$, $x\in(V-T)^{*}\cup T^{*}$,
and $c\in U$.

######  Proof.

See _Lemma_ 2 in [4]. ∎

######  Lemma 5.

Let $Q=(V,T,U,D,s,R)$ be a left-extended queue grammar. Then,
$L(Q)=L(G,\\{w\\#w^{R}\,|\,w\in\\{0,1\\}^{*}\\})$, where $G$ is a CFG.

######  Proof.

Without any loss of generality, assume that $Q$ satisfies the properties
described in Lemma 4 and that $\\{0,1\\}\cap(V\cup U)=\emptyset$. For some
positive integer, $n$, define an injection, $\iota$, from $\Psi^{*}$ to
$(\\{0,1\\}^{n}-1^{n})$, where $\Psi=\\{ab\,|\,(a,b,x,c)\in R$, $a\in V-T$,
$b\in U-D$, $x\in(V-T)^{*}\cup T^{*}$, $c\in U\\}$ so that $\iota$ is an
injective homomorphism when its domain is extended to $\Psi^{*}$; after this
extension, $\iota$ thus represents an injective homomorphism from $\Psi^{*}$
to $(\\{0,1\\}^{n}-1^{n})^{*}$ (a proof that such an injection necessarily
exists is simple and left to the reader). Based on $\iota$, define the
substitution, $\nu$ from $V$ to $(\\{0,1\\}^{n}-1^{n})$ as
$\nu(a)=\\{\iota(aq)\,|\,q\in U\\}$ for every $a\in V$. Extend domain of $\nu$
to $V^{*}$. Furthermore, define the substitution, $\mu$, from $U$ to
$(\\{0,1\\}^{n}-1^{n})$ as $\mu(q)=\\{\iota(aq)^{R}\,|\,a\in V\\}$ for every
$q\in U$. Extend the domain of $\mu$ to $U^{*}$. Set $J=\\{\langle
p,i\rangle\,|\,p\in U-D\textrm{ and }i\in\\{1,2\\}\\}$.

Construction. Next, we introduce a CFG $G$ so that
$L(Q)=L(G,\\{w\\#w^{R}\,|\,w\in\\{0,1\\}^{*}\\})$. Let
$G=(\overline{V},T,P,S)$, where
$\overline{V}=J\,\cup\,\\{0,1,\\#\\}\,\cup\,T$. Construct $P$ in the following
way. Initially, set $P=\emptyset$; then, perform the following steps 1 through
5.

  1. 1.

if $(a,q,y,p)\in R$, where $a\in V-T$, $p,q\in U-D$, $y\in(V-T)^{*}$ and
$aq=s$,
then add $S\to u\langle p,1\rangle v$ to $P$, for all $u\in\nu(y)$ and
$v\in\mu(p)$;

  2. 2.

if $(a,q,y,p)\in R$, where $a\in V-T$, $p,q\in U-D$ and $y\in(V-T)^{*}$,
then add $\langle q,1\rangle\to u\langle p,1\rangle v$ to $P$, for all
$u\in\nu(y)$ and $v\in\mu(p)$;

  3. 3.

for every $q\in U-D$, add $\langle q,1\rangle\to\langle q,2\rangle$ to $P$;

  4. 4.

if $(a,q,y,p)\in R$, where $a\in V-T$, $p,q\in U-D$, $y\in T^{*}$,
then add $\langle q,2\rangle\to y\langle p,2\rangle v$ to $P$, for all
$v\in\mu(p)$;

  5. 5.

if $(a,q,y,p)\in R$, where $a\in V-T$, $q\in U-D$, $y\in T^{*}$, and $p\in D$,
then add $\langle q,2\rangle\to y\\#$ to $P$.

Set $W=\\{0,1,\\#\\}$ and $\Omega=\\{xy\\#z\in\phi(G)\,|\,x\in\\{0,1\\}^{+}$,
$y\in T^{*}$, $z=x^{R}\\}$.

######  Claim 6.

Every $h\in\Omega$ is generated by $G$ in this way

| $S$
---|---
$\Rightarrow$ | $g_{1}\langle q_{1},1\rangle t_{1}\Rightarrow g_{2}\langle q_{2},1\rangle t_{2}\Rightarrow\dots\Rightarrow g_{k}\langle q_{k},1\rangle t_{k}\Rightarrow g_{k}\langle q_{k},2\rangle t_{k}$
$\Rightarrow$ | $g_{k}y_{1}\langle q_{k+1},2\rangle t_{k+1}\Rightarrow g_{k}y_{1}y_{2}\langle q_{k+2},2\rangle t_{k+2}\Rightarrow\dots\Rightarrow g_{k}y_{1}y_{2}\dots y_{m-1}\langle q_{k+m-1},2\rangle t_{k+m-1}$
$\Rightarrow$ | $g_{k}y_{1}y_{2}\dots y_{m-1}y_{m}\\#t_{k+m}$

in $G$, where $k,m\geq 1$; $q_{1},\dots,q_{k+m-1}\in U-D$;
$y_{1},\dots,y_{m}\in T^{*}$; $t_{i}\in\mu(q_{i}\dots q_{1})$ for
$i=1,\dots,k+m$; $g_{j}\in\nu(d_{1}\dots d_{j})$ with
$d_{1},\dots,d_{j}\in(V-T)^{*}$ for $j=1,\dots,k$; $d_{1}\dots
d_{k}=a_{1}\dots a_{k+m}$ with $a_{1}$, $\dots$, $a_{k+m}\in V-T$ (that is,
$g_{k}\in\nu(a_{1}\dots a_{k+m})$ with
$g_{k}={(t_{k+m})}^{R});h=y_{1}y_{2}\dots y_{m-1}y_{m}$.

######  Proof.

Examine the construction of $P$. Observe that every derivation begins with an
application of a rule having $S$ on its left-hand side. Set
$1\textrm{-}J=\\{\langle p,1\rangle\,|\,p\in U\\},2\textrm{-}J=\\{\langle
p,2\rangle\,|\,p\in U\\},1\textrm{-}P=\\{p\,|\,p\in P\textrm{ and }lhs(p)\in
1\textrm{-}J\\},2\textrm{-}P=\\{p\,|\,p\in P\textrm{ and }lhs(p)\in
2\textrm{-}J\\}$. Observe that in every successful derivation of $h$, all
applications of rules from $1\textrm{-}P$ precede the applications of rules
from $2\textrm{-}P$. Thus, the generation of $h$ can be expressed as

| $S$
---|---
$\Rightarrow$ | $g_{1}\langle q_{1},1\rangle t_{1}\Rightarrow g_{2}\langle q_{2},1\rangle t_{2}\Rightarrow\dots\Rightarrow g_{k}\langle q_{k},1\rangle t_{k}\Rightarrow g_{k}\langle q_{k},2\rangle t_{k}$
$\Rightarrow$ | $g_{k}y_{1}\langle q_{k+1},2\rangle t_{k+1}\Rightarrow g_{k}y_{1}y_{2}\langle q_{k+2},2\rangle t_{k+2}\Rightarrow\dots\Rightarrow g_{k}y_{1}y_{2}\dots y_{m-1}\langle q_{k+m-1},2\rangle t_{k+m-1}$
$\Rightarrow$ | $g_{k}y_{1}y_{2}\dots y_{m-1}y_{m}\\#t_{k+m}$

where all the involved symbols have the meaning stated in Claim 6. ∎

######  Claim 7.

Every $h\in L(Q)$ is generated by $Q$ in this way

| $\\#a_{0}q_{0}$ |
---|---|---
$\Rightarrow$ | $a_{0}\\#x_{0}q_{1}$ | $[(a_{0},q_{0},z_{0},q_{1})]$
$\Rightarrow$ | $a_{0}a_{1}\\#x_{1}q_{2}$ | $[(a_{1},q_{1},z_{1},q_{2})]$
⋮ |  |
$\Rightarrow$ | $a_{0}a_{1}\dots a_{k}\\#x_{k}q_{k+1}$ | $[(a_{k},q_{k},z_{k},q_{k+1})]$
$\Rightarrow$ | $a_{0}a_{1}\dots a_{k}a_{k+1}\\#x_{k+1}q_{k+2}$ | $[(a_{k+1},q_{k+1},y_{1},q_{k+2})]$
⋮ |  |
$\Rightarrow$ | $a_{0}a_{1}\dots a_{k}a_{k+1}\dots a_{k+m-1}\\#x_{k+m-1}y_{1}\dots y_{m-1}q_{k+m}$ | $[(a_{k+m-1},q_{k+m-1},y_{m-1},q_{k+m})]$
$\Rightarrow$ | $a_{0}a_{1}\dots a_{k}a_{k+1}\dots a_{k+m}\\#y_{1}\dots y_{m}q_{k+m+1}$ | $[(a_{k+m},q_{k+m},y_{m},q_{k+m+1})]$

where $k,m\geq 1$, $a_{i}\in V-T$ for $i=0,\dots,k+m$, $x_{j}\in(V-T)^{*}$ for
$j=1,\dots,k+m$, $s=a_{0}q_{0}$, $a_{j}x_{j}=x_{j-1}z_{j}$ for $j=1,\dots,k$,
$a_{1}\dots a_{k}x_{k+1}=z_{0}\dots z_{k}$, $a_{k+1}\dots a_{k+m}=x_{k}$,
$q_{0},q_{1},\dots,q_{k+m}\in U-D$ and $q_{k+m+1}\in D$,
$z_{1},\dots,z_{k}\in(V-T)^{*}$, $y_{1},\dots,y_{m}\in T^{*}$,
$h=y_{1}y_{2}\dots y_{m-1}y_{m}$.

######  Proof.

Recall that $Q$ satisfies the properties given in Lemma 4. These properties
imply that Claim 7 holds true. ∎

######  Claim 8.

$L(G,\\{w\\#w^{R}\,|\,w\in\\{0,1\\}^{*}\\})=L(Q)$.

######  Proof.

To prove that $L(G,\\{w\\#w^{R}\,|\,w\in\\{0,1\\}^{*}\\})\subseteq L(Q)$, take
any $h\in\Omega$ generated in the way described in Claim 6. From
$\prescript{}{W}{\omega}(h)\in\\{w\\#w^{R}\,|\,w\in\\{0,1\\}^{*}\\}$ with
$W=\\{0,1,\\#\\}$, it follows that $xy\\#z$ with $z=x^{R}$ where $x=g_{k}$,
$y=y_{1}\dots y_{m}$, $z=t_{k+m}$. At this point, $R$ contains
$(a_{0},q_{0},z_{0},q_{1})$, $\dots$, $(a_{k},q_{k},z_{k},q_{k+1})$,
$(a_{k+1},q_{k+1},y_{1},q_{k+2})$, $\dots$, $(a_{k+m-1}$, $q_{k+m-1}$,
$y_{m-1}$, $q_{k+m})$, $(a_{k+m}$, $q_{k+m}$, $y_{m}$, $q_{k+m+1})$, where
$z_{1}$, $\dots$, $z_{k}\in(V-T)^{*}$, and $y_{1}$, $\dots$, $y_{m}\in T^{*}$.
Then, $Q$ makes the generation of $\prescript{}{T}{\omega}(h)$ in the way
described in Claim 7. Thus, $\prescript{}{T}{\omega}(h)\in L(Q)$.

To prove $L(Q)\subseteq L(G,\\{w\\#w^{R}\,|\,w\in\\{0,1\\}^{*}\\})$, take any
$h\in L(Q)$. Recall that $h$ is generated in the way described in Claim 7.
Consider the rules used in this generation. Furthermore, consider the
definition of $\nu$ and $\mu$. Based on this consideration, observe that from
the construction of $P$, it follows that $S\Rightarrow^{*}oh\\#\overline{o}$
in $G$ for some $o,\overline{o}\in\\{0,1\\}^{+}$ with $\overline{o}=o^{R}$.
Thus,
$\prescript{}{W}{\omega}(oh\\#\overline{o})\in\\{w\\#w^{R}\,|\,w\in\\{0,1\\}^{*}\\}$,
so consequently, $h\in L(G,\\{w\\#w^{R}\,|\,w\in\\{0,1\\}^{*}\\})$. ∎

Claims 6 through 8 imply that Lemma 5 holds true.

######  Theorem 9.

A language $L\in\mathbf{RE}$ if and only if
$L=L(G,\\{w\\#w^{R}\,|\,w\in\\{0,1\\}^{*}\\})$, where $G$ is a propagating
CFG.

######  Proof.

This theorem follows from Lemmas 3 through 5.

######  Corollary 10.

$\mathbf{RE}=\mathbf{CF_{PAL}}$.

Consider $\\{w\\#w^{R}\,|\,w\in\\{0,1\\}^{*}\\}$ without $\\#$—that is
$\\{ww^{R}\,|\,w\in\\{0,1\\}^{*}\\}$. On the one hand, this language is out of
$\mathbf{CF_{PAL}}$ because the central symbol $\\#$ does not occur in it. On
the other hand, it is worth pointing out that Theorem 9 can be based upon this
purely binary language as well.

######  Corollary 11.

A language $L\in\mathbf{RE}$ if and only if
$L=L(G,\\{ww^{R}\,|\,w\in\\{0,1\\}^{*}\\})$, where $G$ is propagating CFG.

######  Proof.

Prove this corollary by analogy with the way Theorem 9 is demonstrated.

Before closing this paper, we point out an open problem. As its main results,
the paper has demonstrated that every recursively enumerable language can be
generated by a propagating context-free grammar $G$ finalized by
$\\{w\\#w^{R}\,|\,w\in\\{0,1\\}^{*}\\}$ (see Theorem 9). Can this results be
established with $G$ having a limited number of nonterminals and/or rules?

## Acknowledgement

This work was supported by Brno University of Technology grant FIT-S-23-8209.

## References

  * [1]
  * [2] A. V. Aho, M. S. Lam, R. Sethi & J. D. Ullman (2006): _Compilers: Principles, Techniques, and Tools (2nd Edition)_ , 2nd edition.  Addison-Wesley.
  * [3] H. C. M. Kleijn & G. Rozenberg (1983): _On the Generative Power of Regular Pattern Grammars_.  Acta Informatica 20(4), pp. 391–411, 10.1007/BF00264281.
  * [4] A. Meduna (2000): _Generative Power of Three-Nonterminal Scattered Context Grammars_.  Theoretical Computer Science 246(1–2), pp. 279–284, 10.1016/S0304-3975(00)00153-5.
  * [5] A. Meduna (2008): _Elements of Compiler Design_.  Taylor & Francis, 10.1201/9781420063257.
  * [6] A. Meduna (2014): _Formal Languages and Computation_.  Taylor & Francis, 10.1201/b16376.
  * [7] A. Meduna & P. Zemek (2014): _Regulated Grammars and Automata_.  Springer, 10.1007/978-1-4939-0369-6.
  * [8] G. Rozenberg & A. Salomaa, editors (1997): _Handbook of Formal Languages, Vol. 1: Word, Language, Grammar_.  Springer.
  * [9] A. Salomaa (1973): _Formal Languages_.  ACM monograph series, Academic Press.


#  Evaluation of STT-MRAM as a Scratchpad for Training in ML Accelerators

Sourjya Roy1, Cheng Wang2, and Anand Raghunathan1

<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>1School of
Electrical and Computer Engineering, Purdue University, West Lafayette, IN,
USA
2Department of Electrical and Computer Engineering, Iowa State University,
Ames, IA, USA

###### Abstract

Progress in artificial intelligence and machine learning over the past decade
has been driven by the ability to train larger deep neural networks (DNNs)
with increased amounts of data, leading to a compute demand that far exceeds
the growth in hardware performance afforded by Moore’s law. Training DNNs is
an extremely memory-intensive process, requiring not just the model weights
but also activations and gradients for an entire minibatch to be stored.
Inability to store these data structures on chip results in expensive off-chip
memory accesses, limiting both training speed and energy efficiency. Current
training accelerators use large SRAM-based scratchpads, but the need to
provide larger on-chip memory capacities and mitigate the leakage power of
SRAM motivates the exploration of more dense non-volatile memory technologies.
Among the emerging non-volatile memory (NVM) options, we observe that
spintronic memories like Spin-Transfer-Torque MRAM (STT-MRAM) offer several
desirable properties for training accelerators, including high endurance and
reasonable access time. Compared to SRAM, STT-MRAM provides 3-4 times higher
density and significantly reduced leakage power on the one hand, while
requiring higher write energy and write time on the other hand. The
inefficient writes are due to the need for a higher write voltage and longer
write duration to ensure reliable switching.

In this study, we perform a comprehensive device-to-system evaluation and co-
optimization of STT-MRAM for efficient ML training accelerator design. We
devised a cross-layer simulation framework to evaluate the effectiveness of
STT-MRAM as a scratchpad in a systolic-array-based DNN accelerator. We
consider two design scenarios — replacing SRAM scratchpads with iso-capacity
and iso-area equivalent versions of STT-MRAM scratchpads. We further propose
to address the inefficiency of writes in STT-MRAM by utilizing reduced write
voltage and duration, which come at the cost of introducing errors. This is
based on the observation that the intrinsically error-resilient nature of DNN
training can tolerate such errors to an extent. To evaluate the ensuing
accuracy-efficiency trade-off, we conduct a thorough analysis of the error
tolerance of input activations, weights and errors during the training
process. We propose heterogeneous memory configurations that enable training
convergence with good accuracy. Our results indicate that replacing SRAM with
STT-MRAM can provide up to 15x and 22x improvement in system level energy for
iso-capacity and iso-area scenarios respectively, across a suite of DNN
benchmarks (AlexNet, VGG16, ResNet18 and ResNet34). Further optimizing STT-
MRAM write operations can provide over 2x improvement in write energy for
minimal degradation in application level training accuracy.

##  I Introduction

Modern machine learning (ML) algorithms, particularly deep neural networks
(DNNs), have achieved remarkable performance, surpassing human capabilities
across diverse tasks in computer vision and language processing [1]. However,
this success has been accompanied by a rapid growth in the computational
requirements for DNN processing, resulting in great interest in efficient
hardware accelerators specifically designed for DNNs. A predominant factor
contributing to the computational challenge of DNN workloads is their memory-
intensive nature [2]; consequently, a substantial volume of data must be
transferred from off-chip main memory to on-chip processing elements. This
data movement gives rise to a critical bottleneck in hardware performance,
commonly referred to as the von-Neumann or memory wall bottleneck. Larger on-
chip memory can potentially mitigate this bottleneck by storing more data and
feeding more accesses without going off-chip. Indeed, this has been the
driving factor behind the use of ever-increasing scratchpads in DNN
accelerators [3, 4]. Nevertheless, on-chip memory built on standard static
random-access-memory (SRAM) occupies considerable space, requiring a minimum
of six transistors (6T) per cell. Additionally, the scaling of SRAM cells at
advanced nodes (7nm and beyond) has considerably slowed down [5] [6],
resulting in diminishing gains in effective memory density in terms of bits
per unit area. The net effect of these trends is evident in today’s DNN
accelerators where a majority of the chip area is consumed by scratchpads [7,
3].

An alternative pathway to enhancing on-chip memory capacity involves
leveraging emerging embedded non-volatile memories (NVMs), whose compact cell
sizes contribute to improved on-chip scratchpad capacity. Additionally, the
non-volatile nature of NVMs offers substantial reductions in leakage power
when compared to CMOS-based memory technologies. The combination of
compactness and reduced power consumption positions embedded NVMs as a highly
promising solution for overcoming the memory challenges associated with DNN
accelerators. We note that the use of NVMs for on-chip storage also opens up
the possibility for in-memory computing [8, 9], leading to further potential
improvements in energy efficiency. While this approach is promising and has
been an acrive area of research over the past decade, it nevertheless faces
considerable challenges related to analog noise and non-idealities, overheads
of peripheral circuits, etc. that are being actively addressed.
Notwithstanding the potential of STT-MRAM for in-memory computing [10], we
focus on the nearer-term use case for NVMs as scratchpad replacement since it
is not subject to the above challenges.

Most efforts exploring NVMs as scratchpads in DNN accelerators focus on
inference, where NVMs are used to store the pre-trained DNN model weights.
While inference is an important type of workload, it is also important to
address the significantly larger computational demands of training DNNs.
Training is a highly memory intensive process due to the need to store several
data structures like weights, minibatch activations and error and weight
gradients. It is also important to note that training performs large numbers
of writes to the memory storing these data structures, demanding high device
endurance. The adoption of embedded NVMs for training remains largely hindered
by the limited endurance as well as costly write operations of NVMs compared
to SRAMs. Specifically, the leading NVM candidates, such as resistive memory
(ReRAM) and phase change memory (PCM) require sophisticated pulsing schemes
($>$ 102 ns) to set/reset during write operations and suffer from poor write
endurance [11][12][13]. In contrast, STT-MRAM provides the highest endurance
($>$ 1015 cycles) with 1 to 10 ns access time [14] while also providing 3-4X
higher density compared to SRAM. Therefore, STT-MRAM can be considered the
most promising NVM technology for DNN training accelerators.

Notwithstanding its advantages, when compared to SRAM at the same technology
node, standard STT-MRAM still exhibits higher write energy and latency. This
is primarily attributed to the need for large write voltages and long write
pulse durations to ensure reliable switching of the magnetization. The high
writing cost of STT-MRAM presents a major barrier that needs to be addressed
to fully leverage its potential for use in DNN training accelerators.

In this work, we investigate device-to-system co-optimization of STT-MRAM for
efficient DNN training acceleration. We propose to exploit MRAM with reduced
write voltage and write duration to address the large cost of write
operations, and evaluate the impact of the low-cost write operations on both
energy-to-train and the accuracy of the resulting DNN models. We
systematically analyze the error tolerance of input activations and weights
during training, and propose a heterogeneous memory architecture wherein
different parts of a number (e.g., mantissa and exponent) are mapped onto
memory arrays with different write error rates.

In summary, this work makes the following contributions:

  1. 1.

We develop a cross-layer design space exploration framework to evaluate
STTMRAM as a scratchpad in DNN training accelerators and compare it with SRAM
under iso-capacity and iso-area scenarios to study the potential energy
benefits.

  2. 2.

We explore the use of reduced write voltage and duration to address the STT-
MRAM write bottleneck. Technology-dependent bit errors are incorporated into
the training of DNNs for standard image classification tasks to study the
impact of write errors on application-level accuracy. To mitigate this impact,
particularly in the low-energy write regime, we observe that the different
parts of a word (sign, exponent and mantissa) have distinct error tolerances.
Based on this insight, we propose a heterogeneous memory organization where
these parts are mapped to different STT-MRAM arrays that are operated with
different write voltages and durations.

  3. 3.

Replacing STT-MRAM with SRAM as an on-chip scratchpad, we achieve up to 15x
and up to 23x improvement in energy efficiency for iso capacity and iso area
scenarios, respectively. Further optimization of STTMRAM for writes can
provide more than 2x improvement in system level write energy at the cost of
minimal accuracy loss at application level.

##  II Related Work

NVM technologies have been explored to provide high-density and low-power
embedded memory for efficient ML hardware systems. In particular, MRAM has
emerged as a leading candidate thanks to its demonstrated scalability, high
energy efficiency (compared to other NVMs), and superior endurance. In
general, the explorations of exploiting MRAM for ML acceleration can be
grouped into two categories: MRAM for digital hardware accelerators and MRAM
for analog and mixed-signal in-memory computing.

Several recent works have explored using MRAM for digital accelerator
architectures in various places including caches, global buffer, and
3D-stacked high bandwidth memory. DeepNVM [15] introduced a technology-aware
simulation framework that demonstrate performance improvement when MRAM is
implemented for last-level caches in GPU architectures for executing deep
learning workloads. Authors in [16] presented a domain-specific convolutional
neural network (CNN) accelerator using co-designed STT-MRAM for on-chip neural
network weight storage, and demonstrated energy-efficient ML inference. A
hierarchical hybrid embedded memory system for systolic array was designed to
thoughtfully partition the mapping of different layers in a CNN model [17]
into 3D-stacked STT-MRAM and on-die SRAM. Such memory systems could exploit
the non-volatility and high density of MRAM for storing pre-trained models,
and at the same time leverage the low latency on-die SRAM to enable efficient
real-time on-chip learning. Another recent work looked into directly using
MRAM as the on-chip buffer in a DNN inference accelerator[18]. In order to
maximize the density of on-chip MRAM buffer and thus minimize the off-chip
DRAM access latency and energy, [18] proposed to relax the thermal stability
of MRAM cell in order to achieve efficient and fast write operations with
reduced memory cell area. While such MRAM design with reduced retention
exhibits satisfactory inference accuracy, it is unclear whether the MRAM with
elevated bit errors due to the reduced thermal stability would still function
for ML training. Moreover, the scaled thermal stability approach can only be
done at fabrication, lacking the flexibility required for processing workloads
in various application scenarios. In contrast, our presented work focuses on
accelerating ML training with customized MRAM design. The proposed MRAM-based
scratchpad design with bit-level granularity and reconfigurable heterogeneity
offers the flexibility to handle diverse ML workloads with distinct error
resilience while achieving improved hardware efficiency for DNN training.

In addition to the exploration for digital accelerators, a plethora of works
have also investigated developing in-memory computing architectures with MRAM
arrays[8, 9, 10, 19, 20, 21, 22, 23]. While in-memory computing with MRAM for
non-volatile weight storage demonstrates great potential for efficient ML
inference, the adoption of in-memory computing at large scale still faces
immense challenges such as device/circuit non-idealities, limited sensing
margin, and large overhead of peripheral circuits. Addressing these challenges
remains an active area of research.

##  III Preliminaries

###  III-A DNN Training

Figure 1: DNN Training

DNN (Deep Neural Network) training, depicted in Figure 1, is a learning
process aimed at adjusting the parameters (weights) of a DNN to maximize its
performance on samples in the training dataset. The model’s parameters are
initialized randomly and then iteratively updated during the training process,
guided by a loss function and an optimizer. The learning rate, a
hyperparameter, determines the speed of learning by modulating the magnitude
of the parameter updates. The training process involves three stages: Forward
Propagation, Back Propagation, and Weight Update, which we describe in turn
below.
Forward Propagation: During the process of forward propagation, a mini-batch
of input activations belonging to a specific layer is multiplied by the
corresponding weights or parameters associated with that layer. This
multiplication yields a mini-batch of output activations, which subsequently
serve as the input for the subsequent layer. The propagation of these
activations continues until they reach the final layer, where an output
prediction is generated. The data structures necessary for this phase are the
activations and weights.
Back Propagation: The final layer plays a pivotal role in computing the error
by comparing the predicted output with the true output using the selected loss
function. In the subsequent phase known as Back Propagation, this error is
propagated in a reverse manner, starting from the final layer and reaching all
the way back to the first layer. At each layer, the gradients of the error
with respect to the weights and input activations are computed. To facilitate
the execution of this phase, the essential data structures include the
activations, weights, and error gradients. These data structures are crucial
for accurately adjusting the network’s parameters and fine-tuning the model
based on the computed gradients.
Weight Update: During the learning process, the error gradients are crucial in
updating the weights. These gradients, which represent the changes needed in
the weights, are multiplied by the learning rate before being utilized to
update the previous weight values. This update operation ensures that the new
weights obtained will be used in the subsequent forward pass. It is important
to note that the sign of the gradients determines whether the new weight value
will be higher or lower than the previous one. To facilitate this phase, two
key data structures are necessary: the weights and the weight gradients.

###  III-B Embedded STT-MRAM

Figure 2: STTMRAM

The STT-MRAM cell is based on a magnetic tunnel junction (MTJ) in series with
its access transistor (Figure 2). An MTJ comprises of an insulating tunnel
barrier (commonly made of MgO) sandwiched between two ferromagnetic layers,
i.e., a fixed reference layer (RL) and a free layer (FL). The MTJ provides bi-
stable resistance states that follow the relative orientation of the two
layers being parallel (P) or anti-parallel (AP). The tunneling magneto-
resistance ratio (TMR = (RAP $-$ RP)/RP) reflects the device OFF/ON ratio,
which impacts the sensing margin. The magnetization of FL is switched by STT
from the spin-polarized current passing through the MTJ due to the interaction
of local magnetic moments and electron spins in the conduction current. In
order to provide thermal stability and minimize errors due to thermal
agitation and process variation, the thermal stability factor KuV/kBT needs to
be about 45-75. The design choice of thermal stability depends on the system-
level requirement for data retention. Since the uniaxial anisotropy constant
Ku is a material-dependent constant, the variation of thermal stability factor
is usually achieved by modifying the volume of the FL in an MTJ. MTJs with
perpendicular anisotropy offer the potential of achieving higher density and
more efficient switching dynamics.

Compared to SRAM which normally requires at least 6 transistors per bit-cell,
the 1T-1MTJ STT-MRAM provides 2-4x higher density with substantially reduced
leakage power. At the cell level, although STT-MRAM is already improved in
write efficency compared to field-driven switching, the write energy and
latency of STT-MRAM is about 10x higher than SRAM. Due to the large write
current density required, the MRAM cell area is determined by the access
transistor (not the MTJ pillar size). Today, novel technologies such as spin-
orbit torque (SOT) and voltage-controlled magnetic anisotropy (VCMA) are being
explored to further improve the MRAM write performance, although these
technologies are still in their nascent stage of development.

###  III-C Baseline accelerator architecture and dataflow

Figure 3: Systolic array accelerator with activation and weight buffers

Figure 3 presents the architecture of a simple systolic-array-based DNN
accelerator used in our evaluation. A systolic array comprises a 2D array of
processing elements (PEs), where each PE is interconnected with all or a
subset of its nearest neighbor PEs. When mapping DNN computations to systolic
arrays, it is important to choose a suitable dataflow [3]. In the output
stationary dataflow, each PE in the systolic array stores an output while the
computation of a DNN layer is being performed. Inputs and weights are streamed
into the systolic array from different directions at each cycle, enabling in-
place reduction at each PE. Let us consider a forward pass in a convolution
layer as an example. An input layer with dimensions of B*I*M*N undergoes
convolution with a weight layer of dimensions O*I*K*K. Here M and N refers to
the input height and width, B refers to the batch size, K refers to the kernel
width and I and O refer to the number of input and output channels,
respectively. K2I scalar values are streamed in from activation and weight
buffers and reduced at every PE to produce one output activation value. The
dimensions of the systolic array determine the level of temporal reuse within
it.

##  IV Experimental Methodology

Figure 4: Cross Layer Evaluation Framework

To enable the evaluation of STT-MRAM based scratchpads in DNN training
accelerators, we developed the cross-layer framework illustrated in Figure 4.
The framework includes energy simulation of a hardware system comprised of on-
chip memory, a compute unit based on systolic array architecture, and off-chip
DRAM. The device-to-array simulation of on-chip memory includes STT-MRAM
modeling using a MATLAB-based macro-spin simulator for capturing the magnetic
switching dynamics. The device-level behaviors obtained from MATLAB are
provided to NVSim [24], a simulation tool for evaluating the performance,
energy, and area of NVM-based on-chip memory. NVSim provides latency, area,
and energy estimates for memory arrays of different capacities based on the
specifications of memory cells. The results of both MRAM and the baseline SRAM
arrays in our experiments are obtained using NVSim. The technology-dependent
specifications of on-chip memories, namely STT-MRAM and SRAM, are based on a
28nm technology node. The energy estimation for off-chip DRAM is performed
using the CACTI tool [25]. DRAM is modeled using the DDR3 interface and a 65nm
technology node. The evaluated compute unit is based on a systolic array
architecture with output stationary data flow. The compute energy for the
systolic array is obtained using Accelergy [26]. The system-level evaluation
considers a systolic array size of 256x256 with an on-chip clock frequency of
1 GHz.

To evaluate the system-level energy efficiency, we developed a simulator based
on PyTorch. This simulator takes both algorithmic attributes (such as the DNN
architecture) and hardware attributes (such as the accelerator architecture)
as inputs. The algorithmic attributes of DNN workloads include the layer type
(convolution and fully connected), dataset, and layer dimensions, while the
hardware attributes include the data flow type, systolic array size, and on-
chip memory sizes. Based on these input parameters, the PyTorch simulator
calculates the number of on-chip memory accesses, off-chip DRAM accesses, and
leakage cycles. The estimations from NVSim, CACTI, and Accelergy, along with
the output from the PyTorch-based simulator, are sent to an energy estimator
to calculate the total output energy.

We make the following assumptions for the system-level evaluation:

  1. 1.

Three types of buffers are considered in the evaluated architecture:
activation buffer, weight buffer, and error buffer. However, there is no
separate output buffer included due to the output stationary dataflow. The
total on-chip memory capacity is divided equally among the activation buffer,
weight buffer, and error buffer.

  2. 2.

Accesses to DRAM and the on-chip memory array are executed in a sequential
manner, one after the other, rather than concurrently or in a parallel
fashion.

  3. 3.

The values of a data structure, such as activations, weights, and errors, are
stored in the on-chip memory array only if the entire data structure for a
layer can fit within the available on-chip memory capacity. If the size of a
data structure exceeds the capacity of the on-chip memory array, it would be
stored in off-chip memory instead. This is typical of software-managed
scratchpads where each data structure is treated as atomic.

  4. 4.

During the forward pass of the neural network, data structures (such as
activations, weights, and errors) are removed from the memory array in a
serial manner. This means that data structures are evicted from the memory
array one by one, typically in the order they were stored, to make space for
incoming data structures. Similarly, during the backward pass of the neural
network, data structures are also removed from the memory array in a serial
manner, but in the reverse order compared to the forward pass. This ensures
that the data structures required for the backward pass are evicted in the
correct order, allowing for proper gradient calculations and parameter
updates.

##  V Results and Discussions

In this section, we will discuss the results from the proposed cross-layer
exploration. First, we will delve into the probabilistic switching in STT-MRAM
write operations. We focus on simulating the STT-driven switching dynamics of
MTJ and evaluating the elevated write error rates due to probabilistic
switching under write voltage with reduced magnitude and/or reduced duration.
Next, at the array level, comparison between SRAM and STT-MRAM will be
performed under iso-capacity and iso-area scenarios when STT-MRAM designs with
both standard and low-overhead write operations will be evaluated.
Subsequently, we will evaluate the system-level energy consumption of running
DNN training workload in a ML accelerator with systolic array architecture.
Both SRAM and STT-MRAM will be designed as the scratchpad in systolic array
architecture with an output stationary dataflow. We will compare the energy
efficiency of the hardware using MRAM and SRAM under iso-capacity and iso-area
scenarios. Lastly, we will investigate the impact of write optimization on
application-level accuracy and the trade-off between hardware efficiency and
algorithmic accuracy. After incorporating the elevated write errors into our
PyTorch-based simulator, we propose a hybrid architecture with distinct memory
write settings for different bits of the floating point representation. The
proposed hybrid memory architecture enables energy-efficient MRAM writing,
leading to further improvement in the write energy of memory arrays while
ensuring minimal degradation of DNN accuracy.

Figure 5: Switching probability of MRAM cell under varying write voltage
durations and magnitudes.

###  V-A Modeling of the STT-MRAM write operations

####  V-A1 Simulation of MTJ switching dynamics

We investigate the write operations of STT-MRAM cell based on macro-spin
simulations of the magnetization switching. The magnetization dynamics of the
FL of MRAM cell can be modeled by solving the Landau-Liftshitz Gilbert
equation with the STT term incorporated. Based on the recently reported STT-
MRAM device fabrications, the MTJ for 28nm STT-MRAM is set to have a lateral
dimension 35-40 nm in our simulations, and the free layer CoFeB has
interfacial perpendicular magnetic anisotropy. The detailed simulation
parameters are summarized in Table I.

Parameter | Value
---|---
FL thickness tCoFeB | 1.0 nm
MTJ lateral dimension | 35nm x 35nm
Gilbert damping $\alpha$ | 0.006
Anisotropy constant K |  1.0 ergs/cm2
Saturation magnetization | 1200 emu/cc
TABLE I:  Key parameters of device-level macro-spin simulation of the STT-
driven switching.

Since the onset of STT switching is attributed to the combination of the
thermal agitation at room temperature and the directional torque exerted from
the currents, there is intrinsic stochasticity in MRAM switching. We model the
stochasticity originated from thermal perturbation as an effective
perturbation field [27]:

$H_{Thermal}=\mathcal{N}(0,1)\sqrt{\frac{2\alpha k_{B}T}{\gamma M_{S}V\delta
t}},$ (1)

where $\mathcal{N}$(0,1) is a Gaussian random variable with mean and stand
deviation being 0 and 1 respectively, and $\delta$t is the simulation time
step. As a result of the stochastic switching, varying probabilities $P_{sw}$
can be observed under applied write voltages with different magnitudes and
durations. As is illustrated in Figure 5, the switching probability $P_{sw}$
exhibit a sigmoid-like behavior as the excitation current increases. The onset
of switching occurs at smaller currents when the excitation duration is
longer. We obtain that the STT efficiency $\eta=1.15$ kBT/$\mu A$ ($\eta$
defined as the ratio of energy barrier and critical current
$\eta=E\textsubscript{B}/I\textsubscript{c0}$), which is consistent with the
reported values of 1.0$-$3.0 in recent fabrication works [28] [29] . It has
been demonstrated that reducing the energy barrier EB by reducing the MTJ
dimension will lead to a trade-off between thermal stability and lower write
current [28] [30]. However, it is important to note that lowering the energy
barrier will make the MTJ susceptible to process variations and thermal
noises, and modifying the MTJ device dimension post fabrication is not
feasible. Therefore, we chose to explore our MRAM design with a sufficient
energy barrier Eb = 55 kBT that ensures stable data retention at the room
temperature for several months.

####  V-A2 Write error rate (WER) with reduced magnitude and duration of STT
voltage

Figure 6: (a) WER of MRAM under varying write voltage durations and
magnitudes. (b) Trade-off of write energy and WER based on the macrospin
simulations.

The switching probability $P_{sw}$ is linked to the write error rate (WER) of
MRAM:

$lnWER=ln\left(1-P_{sw}\left(V_{STT},t_{STT}\right)\right),$ (2)

where $V_{STT}$, $t_{STT}$ are the magnitude and duration of the applied write
voltage, respectively.

Figure 6 (a) shows the WER as a function of write current/voltage under
varying write pulse durations. It is observed that the WER remains around 1.0
(no switching) until the write current reaches a threshold. After the onset of
switching, WER decreases exponentially with the increasing current, as
suggested by the approximately constant slope in such ln(WER) plot. Such
observation of constant slope in ln(WER) plots is consistent with the Fokker-
Planck theory based on macro-spin approximation . In our experiment, we run
magnetic switching dynamics for 20K iterations to capture the WER down to
ln(WER)$\sim$-4. We obtain the required write currents for WER valued from
1E-5 to 1E-9 based on linear extrapolation of the ln(WER) vs. VSTT curves.

The design of robust on-chip MRAM requires to reach WER $<$ 1E-9 in order to
inhibit bit errors during memory updates. Therefore, we set the WER $\sim$
1E-9 (8.62E-10) as our baseline for setting the write current’s magnitude and
duration. As shown in Figure 6 (b), lowering $V_{STT}$ will lead to reduction
of write energy per bit at the cost of deteriorating the WER. Moreover, while
reducing the $t_{STT}$ leads to latency improvement, ensuring a certain WER
requires more write energy per bit. This is due to the requirement of applying
larger STT currents when the write duration is reduced. Next, we will
incorporate the modifications of $V_{STT}$ and $t_{STT}$ in MRAM cell into
memory array and micro-architecture design, and elucidate the implications of
device cell modifications on the hardware performance at the micro-
architecture level.

###  V-B Array-level design of on-chip memory

Figure 7: Iso-capacity analysis of SRAM and STT-MRAM memory design based on
NVsim simulations for capacity 32 KB to 512 MB. For MRAM with reduced write
duration (low-dur) and reduced write voltage (low-V), the WER is elevated to
8E-4.

In this sub section, we evaluate the array-level hardware performance of STT-
MRAM in comparison with the SRAM. We employ NVsim [24] to analyze the circuit-
level energy efficiency, latency, and area based on varying cell designs
including standard SRAM, standard MRAM, and MRAM with low-cost write
operations. The simulated MRAM bit cell parameters are summarized in Table 2
together with SRAM baseline. Note that the NVsim simulator contains various
optimization targets that may lead to variance in the simulation results.
After experimenting various optimization targets, we select cache
configuration with Read Latency as the optimization target, which works well
for the whole range of memory capacity in our exploration.

We first provide the iso-capacity analysis of circuit-level simulations for
capacity ranged from 32 KB to 512 MB. In general, the the capacity increases,
both SRAM and STT-MRAM consume larger area and increased leakage power due to
increased numbers of transistors employed. As a result of larger arrays and
larger banks, the parasitic resistance and capacitors in the circuit also
increases, leading to increased latency and read/write energy.

WE further observe that compared to SRAM, STT-MRAM starts to exhibit
advantages in area efficiency as the memory capacity exceeds 128 KB. Thanks to
the compact cell size, MRAM achieves 2-3x better area efficiency for the wide
range of capacity from 1MB to 512 MB. Moreover, the leakage power of STT-MRAM
is substantially reduced compared to SRAM thanks to the non-volatility of
magnetic storage. We further observe that while the read/write latency and
energy of SRAM is significantly lower than MRAM at the cell level, the array-
level latency and energy of SRAM will increase with the capacity at a much
faster rate compared to MRAM. Such significant increased cost at the array-
level is due to the significantly larger SRAM cell area. As capacity
increases, SRAM arrays consume much larger areas and longer wires along the
bitlines and wordlines, leading to more severe parasitic resistance and
capacitance that dominate the access latency and energy at higher capacity.

We further explore the array-level MRAM performance with reduced write
overheads. Both reduced write voltage and shortened write duration are
evaluated. As is shown in Figure 7, we observe that with reduced write voltage
and write latency, the crossover between STT-MRAM and SRAM in their array-
level metrics will shift to smaller capacity, indicating more performance
advantage from MRAM. Such improvement in hardware performance is achieved with
the trade-off of elevated WER due to the induced non-deterministic switching.
For example, compared to the baseline MRAM, the memory design with reduced
write overhead can lead to 53$\%$ reduction in latency and 60$\%$ access
energy at a cost of increasing the WER to 0.8E-4. We will exploit the MRAM
design optimization with low write costs and investigate the impacts of the
inflated WER for DNN training.

Figure 8: Iso-area analysis of SRAM and STT-MRAM design for area budgets from 0.5 to 187 mm2. For MRAM with reduced write duration (low-dur) and reduced write voltage (low-V), the WER is elevated to 8E-4. Area (mm2) | 0.5 | 48.1
---|---|---
Memory type |  SRAM |  MRAM |  SRAM |  MRAM
Capacity (KB) |  183 |  512 |  40592 |  131072
Read latency (ns) |  0.2 |  3.3 |  10.3 |  14.6
Write latency (ns) |  0.1 |  10.2 |  5.3 |  15.8
Read energy (pJ) |  0.1 |  0.3 |  1.8 |  1.6
Write energy (pJ) |  0.1 |  1.5 |  1.4 |  2.6
Leakage Power (mW) |  594 |  323 |  64257 |  14573
TABLE II:  Iso-area comparison of SRAM and baseline STT-MRAM under small (0.5
mm2) and large (48.1 mm2) area budgets.

We also present an iso-area analysis so that the comparison of MRAM and SRAM
could be drawn in more practical scenarios. As summarized in Figure 8,
hardware cost of both SRAM and MRAM increase at larger area. While SRAM
overall has lower access latency and energy, the performance gap between SRAM
and MRAM under iso-area shrinks rapidly as the chip capacity grows under
larger area. Such observations reflect the increasing impact of circuit
parasitics on the array-level performance as the chip area grows, which is
consistent with the observation from the iso-capacity curves in Figure 7.
Moreover, MRAM designs with reduced write duration and reduced write voltage
exhibit further narrowing of the performance gap between MRAM and SRAM. We
summarize in Table II the array-level memory performance of SRAM and MRAM
under two representative area budgets. We observe that MRAM improves the iso-
area capacity by 2.8-3.2x while reducing the leakage power by a factor of
1.9-4.4. In the next section, we will evaluate the system-level implications
of such MRAM write optimizations on the hardware performance of DNN training
accelerators, where both area constraints and off-chip DRAM accesses are taken
into account.

###  V-C System-level analysis of energy efficiency

In this subsection, we are going to discuss the system level results of STT-
MRAM in comparison with SRAM as an on-chip scratchpad for a suite of DNN
benchmarks. The DNNs that we chose for our evaluation are from image
recognition tasks- AlexNet, VGG16, ResNet18 and ResNet34. The data sets used
are CIFAR10 and CIFAR100. A batchsize of 512 is considered for the evaluation.
There are two different scenarios used for the system level evaluation- iso-
capacity and iso-area. Iso-capacity signifies the same capacity being used for
SRAM and STT-MRAM memory arrays. Iso-area signifies same area being used for
both STT-MRAM and SRAM arrays with different memory capacities. As mentioned
in Section IV, an output stationary dataflow for a systolic array architecture
was used for the evaluation. Subsequently, we will discuss about the results
for the two different scenarios. We have used VGG16 as the benchmark to study
the two scenarios in details.

####  V-C1 Iso-capacity

Figure 9: Iso capacity energy improvements of STTMRAM over SRAM on chip array
for VGG16 evaluated on CIFAR100 and sytem energy breakdown for different
components while using SRAM and STTMRAM as an on-chip scratchpad Figure 10:
Iso capacity energy improvements of STTMRAM over SRAM on chip array for
AlexNet, ResNet18 and ResNet34 evaluated on CIFAR10 and CIFAR100

In this particular scenario, both SRAM and STTMRAM on-chip memory arrays
maintain the same capacity. Fig 9 illustrates the energy improvement of STT-
MRAM compared to SRAM for VGG16 on CIFAR100 at iso capacities with varying
memory capacities. STT-MRAM exhibits a remarkable energy improvement of up to
15x over SRAM at iso capacity for different memory capacities in the case of
VGG16 evaluated on CIFAR100. In this scenario, both DRAM accesses and on-chip
access remain unchanged. However, the energy difference arises from the on-
chip read and write energy, as well as the on-chip leakage energy. The
improvement primarily stems from the reduction in leakage energy. The
enhancements are more pronounced at higher memory capacities, mainly due to
the diminishing gap in write energy between SRAM and STTMRAM. The breakdown of
the different energy components can be observed in Fig 9. For smaller
capacities, the major contributors to the total system energy are DRAM access
energy and on-chip leakage energy. On-chip accesses account for a smaller
portion of the total energy. The compute energy percentage is negligible when
compared to other energy components. As the memory capacity increases, the
number of DRAM accesses decreases, and on-chip leakage becomes the dominant
component of the total energy. This trend holds true for both SRAM and
STTMRAM. However, due to the lower leakage power of STTMRAM arrays compared to
SRAM arrays, the percentage of leakage in the overall energy is slightly lower
for STTMRAM at iso capacity. STT-MRAM arrays have a higher contribution from
on-chip access energy to the total energy compared to SRAM arrays. This is
primarily due to the higher write energy of STTMRAM arrays in comparison to
SRAM. The graphs in Fig 10 demonstrate the energy improvement of STTMRAM over
SRAM for AlexNet, ResNet18, and ResNet34 evaluated on CIFAR10, and CIFAR100 at
iso capacities with different memory capacities. Similar trends can be
observed across all benchmarks, akin to the case of VGG16. The improvement
remains consistent across different capacities, with smaller improvements at
lower capacities and more significant improvements as capacity increases,
primarily due to the widening gap in leakage and the closing gap between write
energy of SRAM and STTMRAM.

####  V-C2 Iso-area

Figure 11: Iso area energy improvements of STTMRAM over SRAM on chip array for
VGG16 evaluated on CIFAR100 and sytem energy breakdown for different
components while using SRAM and STTMRAM as an on-chip scratchpad Figure 12:
Iso area energy ratio (STTMRAM over SRAM) of different energy components for
VGG16 evaluated on CIFAR100 Figure 13: Iso area energy improvements of STTMRAM
over SRAM on chip array for AlexNet, ResNet18 and ResNet34 evaluated on
CIFAR10 and CIFAR100

In this scenario, we maintain the same on-chip area for both SRAM and STT-MRAM
memory arrays. We adjust the SRAM memory capacities while keeping the capacity
for STT-MRAM the same, ensuring the on-chip area remains unchanged. Figure 11
illustrates the energy improvement of STT-MRAM over SRAM when used as an on-
chip scratchpad at iso area, considering different area values for VGG16
evaluated on CIFAR100. At a specific capacity, STT-MRAM requires fewer DRAM
accesses compared to SRAM memory arrays. Additionally, the on-chip accesses
differ, with variations in energy stemming from on-chip read and write
operations, on-chip leakage, and DRAM access. The ratio of these energy
components for SRAM over STT-MRAM is depicted in Figure 12. As expected, the
energy consumption of DRAM is higher for SRAM than for STT-MRAM when utilized
as a scratchpad across various area values. The improvement in the DRAM access
energy ratio fluctuates due to the varying capacity ratios between SRAM and
STT-MRAM. The increased on-chip capacity of STT-MRAM arrays compared to SRAM
arrays accounts for the enhancements in DRAM access. The number of on-chip
accesses depends on the capacity, and variations in replacement policy and
capacity lead to different numbers of on-chip accesses for different area
values. As anticipated, SRAM generally exhibits lower on-chip energy than STT-
MRAM for most areas due to significantly lower write energy. At higher area
values, it is possible for on-chip accesses to be lower for STT-MRAM than for
SRAM, resulting in a slight improvement in on-chip access energy. The memory
array results indicate that the gap between SRAM and STT-MRAM write energy
decreases at higher capacity values. Even with different on-chip capacities,
we can expect the write energy of SRAM and STT-MRAM to be closer at higher
memory capacities (larger areas). In scenarios where on-chip accesses are
smaller for STT-MRAM arrays compared to SRAM arrays, it is possible for STT-
MRAM arrays to have lower overall write energy. Notably, there is a
significant improvement in leakage energy, albeit lower than in the iso-
capacity case, due to the higher capacity of STT-MRAM compared to SRAM for a
specific area. The trend of increasing leakage energy with increasing area is
not as clear as in the iso-scenario case since the capacity ratios differ
across different area values. Overall, at iso area, STT-MRAM memory arrays
offer significant benefits over SRAM memory arrays for all area values. The
energy improvement of STT-MRAM over SRAM for AlexNet, ResNet18, and ResNet34
evaluated on CIFAR10, and CIFAR100 at iso area for various area values is
depicted in the graphs of Figure 13. Similar trends to the VGG16 case are
observed for all other benchmarks. In the case of AlexNet, there is a sudden
increase in energy improvement. At a certain area value, the capacity of STT-
MRAM becomes large enough to accommodate all the required data structures for
training, whereas the SRAM memory array cannot due to its lower capacity.
Hence, we observe a sudden spike in energy improvement, which we do not
include in the reported results since it is only observed at a narrow range of
areas. As the area value increases further, the SRAM capacity also becomes
capable of accommodating all the data structures, leading to a drop in energy
improvement, although there is still a significant improvement for STT-MRAM.
If we increase the area values in the other benchmarks, a similar trend can be
expected, although not captured in the current graphs. Therefore, the trend
heavily depends on the network type and dimensions.

###  V-D Impact on Write Optimization on Application Level Accuracy and Write
Energy Benefits

Figure 14: Application level accuracy plots for different write error rates as
a result of STT-MRAM write optimizations for LeNet, AlexNet, VGG16 and
ResNet18 evaluated on MNIST, CIFAR10 and CIFAR100 Figure 15: Normalized write
energy for VGG16 evaluated on CIFAR100 for iso-capacity scenario. The write
energy is based on using the optimized STT-MRAM for only the mantissa bits and
the base STT-MRAM for the exponent and sign bits

In previous subsections, we observed that the write energy of STT-MRAM arrays
was significantly higher than that of SRAM. However, it is possible to
optimize STT-MRAM writes by reducing the voltage and duration of the write
operation, albeit at the expense of write errors. In this subsection, we
evaluate the impact of these write optimizations on application-level accuracy
and the corresponding system-level write energy benefits. To assess the effect
of write errors on application-level accuracy, errors were introduced at the
bit level in single precision floating-point data format. We considered the
IEEE754 data format, which consists of 1 sign bit, 8 exponent bits, and 23
mantissa bits. We emulated error-based training in PyTorch for some of the
aforementioned benchmarks. Our results indicated that significant bits (1 sign
bit and 8 exponent bits) can cause significant variations in gradient values
for high write error rates, leading to error propagation and non-convergence
of the training process. On the other hand, higher significant bits can
tolerate small error rates. Therefore, we decided to apply errors to the least
significant bits of the floating-point data format (mantissa bits). The
training results for different error rates are presented in Figure 14 for
LeNet5, AlexNet, VGG16, and ResNet18 evaluated on MNIST, CIFAR10, and
CIFAR100. The legends in the graph indicate the write error rate, and the
numbers in brackets signify the number of bits from the floating-point data
format considered for introducing errors based on the error probability.
Training with errors at the bit level is time-consuming even on a GPU, so for
some benchmarks, only a few epochs are shown. It is evident from Figure 14
that partitioning words among different arrays with varying levels of
reliability can lead to minimal accuracy degradation in training, even for
higher write error rates. Lower error rates show almost no drop in
application-level accuracy. We attempted to evaluate the system-level write
energy by utilizing a heterogeneous memory array, where the least significant
bits (mantissa bits) are mapped to the optimized STT-MRAM array, while the
higher significant bits (exponent and sign) are mapped to the base STT-MRAM
array. Figure 15 illustrates the normalized system-level write energy for the
heterogeneous memory array at different error rates for different memory
capacities. The energy numbers are normalized to the STT-MRAM array with the
highest error rate (0.8e-3). We also included the normalized SRAM number for
comparison. In this optimization, the write latency of STT-MRAM is fixed at
10ns, and the write voltage is varied to generate the different error rates
shown in the graph. It is evident that higher error rates bring the system-
level write energy closer to the write energy of SRAM. Tolerating a high error
rate can result in up to a 2.03x improvement in total write energy compared to
unoptimized STT-MRAM for VGG16 evaluated on CIFAR100. Hence, selectively
choosing the bits for the optimized STT-MRAM array can provide a significant
improvement in system-level write energy with minimal application-level
accuracy degradation.

##  VI Conclusion

We demonstrate a device-to-algorithm co-exploration towards efficient
implementation of embedded STT-MRAM as the scratchpad for ML training
acceleration. We exploit the error-resiliency of DNNs and utilize low-cost
MRAM write operations with reduced voltage and pulse duration. In order to
mitigate the elevated write errors due to the probabilistic switching dynamics
of MRAM, we propose heterogeneous memory architecture where the different bit
segments (sign/exponent/mantissa) of input and weight parameters are mapped
into MRAM sub-arrays with distinct write configurations. Our device-to-system
simulation shows that by replacing the standard CMOS-based SRAM with STT-MRAM,
substantial energy improvement is achieved due to the improved density and
reduction of leakage power. Moreover, our cross-layer evaluation demonstrate
that MRAM with reduced write costs can further harness improvement in the
memory write energy while maintaining the training convergence and prediction
accuracy of DNNs. Our proposed cross-layer co-optimization essentially closes
the performance gap between MRAM and SRAM (in terms of write latency and
energy consumption) at the array-level, leading to a promising pathway of
designing high-performing ML training accelerators with high-density and
energy-efficient NVMs.

##  VII 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] M. Roser.  The brief history of artificial intelligence: The world has changed fast – what might be next?, 2022.
  * [2] B. Fleischer et al.  Unlocking the promise of approximate computing for on-chip ai acceleration, IBM Research Blog, 2020.
  * [3] Vivienne Sze, Yu-Hsin Chen, Tien-Ju Yang, and Joel S. Emer.  Efficient processing of deep neural networks: A tutorial and survey.  Proceedings of the IEEE, 105(12):2295–2329, 2017.
  * [4] Subhankar Pal, Swagath Venkataramani, Viji Srinivasan, and Kailash Gopalakrishnan.  Efficient management of scratch-pad memories in deep learning accelerators.  In 2021 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), pages 240–242, 2021.
  * [5] Chih-Hao Chang, V.S. Chang, K.H. Pan, K.T. Lai, J. H. Lu, J.A. Ng, C.Y. Chen, B.F. Wu, C.J. Lin, C.S. Liang, C.P. Tsao, Y.S. Mor, C.T. Li, T.C. Lin, C.H. Hsieh, P.N. Chen, H.H. Hsu, J.H. Chen, H.F. Chen, J.Y. Yeh, M.C. Chiang, C.Y. Lin, J.J. Liaw, C.H. Wang, S.B. Lee, C.C. Chen, H.J. Lin, R. Chen, K.W. Chen, C.O. Chui, Y.C. Yeo, K.B. Huang, T.L. Lee, M.H. Tsai, K.S. Chen, Y.C. Lu, S.M. Jang, and S.-Y. Wu.  Critical process features enabling aggressive contacted gate pitch scaling for 3nm cmos technology and beyond.  In 2022 International Electron Devices Meeting (IEDM), pages 27.1.1–27.1.4, 2022.
  * [6] David Schor.  IEDM 2022: Did we just witness the death of sram?, WikiChip, 2022\.
  * [7] Norman P. Jouppi, Doe Hyun Yoon, Matthew Ashcraft, Mark Gottscho, Thomas B. Jablin, George Kurian, James Laudon, Sheng Li, Peter Ma, Xiaoyu Ma, Thomas Norrie, Nishant Patil, Sushma Prasad, Cliff Young, Zongwei Zhou, and David Patterson.  Ten lessons from three generations shaped google’s tpuv4i : Industrial product.  In 2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA), pages 1–14, 2021.
  * [8] T. Patrick Xiao, Christopher H. Bennett, Ben Feinberg, Sapan Agarwal, and Matthew J. Marinella.  Analog architectures for neural network acceleration based on non-volatile memory.  Applied Physics Reviews, 7(3), 07 2020.  031301\.
  * [9] Indranil Chakraborty, Mustafa Ali, Aayush Ankit, Shubham Jain, Sourjya Roy, Shrihari Sridharan, Amogh Agrawal, Anand Raghunathan, and Kaushik Roy.  Resistive crossbars as approximate hardware building blocks for machine learning: Opportunities and challenges.  Proceedings of the IEEE, 108(12):2276–2310, 2020.
  * [10] Shankar Ganesh Ramasubramanian, Rangharajan Venkatesan, Mrigank Sharad, Kaushik Roy, and Anand Raghunathan.  Spindle: Spintronic deep learning engine for large-scale neuromorphic computing.  In 2014 IEEE/ACM International Symposium on Low Power Electronics and Design (ISLPED), pages 15–20, 2014.
  * [11] Abu Sebastian, Tomas Tuma, Nikolaos Papandreou, Manuel Le Gallo, Lukas Kull, Thomas Parnell, and Evangelos Eleftheriou.  Temporal correlation detection using computational phase-change memory.  Nature Communications, 8(1):1115, 2017.
  * [12] 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.
  * [13] Hiroyuki Akinaga and Hisashi Shima.  Resistive random access memory (ReRAM) based on metal oxides.  Proceedings of the IEEE, 98(12):2237–2251, 2010.
  * [14] Jimmy J. Kan, Chando Park, Chi Ching, Jaesoo Ahn, Yuan Xie, Mahendra Pakala, and Seung H. Kang.  A study on practically unlimited endurance of stt-mram.  IEEE Transactions on Electron Devices, 64(9):3639–3646, 2017.
  * [15] Ahmet Fatih Inci, Mehmet Meric Isgenc, and Diana Marculescu.  Deepnvm: A framework for modeling and analysis of non-volatile memory technologies for deep learning applications.  In 2020 Design, Automation and Test in Europe Conference and Exhibition (DATE), pages 1295–1298, 2020.
  * [16] Baohua Sun, Daniel Liu, Leo Yu, Jay Li, Helen Liu, Wenhan Zhang, and Terry Torng.  Mram co-designed processing-in-memory cnn accelerator for mobile and iot applications.  arXiv preprint arXiv:1811.12179, 2018.
  * [17] Insik Yoon, Malik Aqeel Anwar, Rajiv V. Joshi, Titash Rakshit, and Arijit Raychowdhury.  Hierarchical memory system with stt-mram and sram to support transfer and real-time reinforcement learning in autonomous drones.  IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 9(3):485–497, 2019.
  * [18] Kaniz Mishty and Mehdi Sadi.  Designing efficient and high-performance ai accelerators with customized stt-mram.  IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 29(10):1730–1742, 2021.
  * [19] Seungchul Jung, Hyungwoo Lee, Sungmeen Myung, Hyunsoo Kim, Seung Keun Yoon, Soon-Wan Kwon, Yongmin Ju, Minje Kim, Wooseok Yi, Shinhee Han, et al.  A crossbar array of magnetoresistive memory devices for in-memory computing.  Nature, 601(7892):211–216, 2022.
  * [20] Ameya D Patil, Haocheng Hua, Sujan Gonugondla, Mingu Kang, and Naresh R Shanbhag.  An mram-based deep in-memory architecture for deep neural networks.  In 2019 IEEE International Symposium on Circuits and Systems (ISCAS), pages 1–5. IEEE, 2019.
  * [21] Zhezhi He, Yang Zhang, Shaahin Angizi, Boqing Gong, and Deliang Fan.  Exploring a sot-mram based in-memory computing for data processing.  IEEE Transactions on Multi-Scale Computing Systems, 4(4):676–685, 2018.
  * [22] Aqeel Anwar, Arijit Raychowdhury, Ryan Hatcher, and Titash Rakshit.  Xbaropt - enabling ultra-pipelined, novel stt mram based processing-in-memory dnn accelerator.  In 2020 2nd IEEE International Conference on Artificial Intelligence Circuits and Systems (AICAS), pages 36–40, 2020.
  * [23] J. Doevenspeck, K. Garello, B. Verhoef, R. Degraeve, S. Van Beek, D. Crotti, F. Yasin, S. Couet, G. Jayakumar, I. A Papistas, P. Debacker, R. Lauwereins, W. Dehaene, G. S. Kar, S. Cosemans, A. Mallik, and D. Verkest.  Sot-mram based analog in-memory computing for dnn inference.  In 2020 IEEE Symposium on VLSI Technology, pages 1–2, 2020.
  * [24] Xiangyu Dong, Cong Xu, Yuan Xie, and Norman P Jouppi.  Nvsim: A circuit-level performance, energy, and area model for emerging nonvolatile memory.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 31(7):994–1007, 2012.
  * [25] N. Muralimanohar et al.  Optimizing NUCA Organizations and Wiring Alternatives for Large Caches with CACTI 6.0.  In Proc., MICRO, pages 3–14, Washington, DC, USA, 2007. IEEE Computer Society.
  * [26] Yannan N. Wu, Joel S. Emer, and Vivienne Sze.  Accelergy: An Architecture-Level Energy Estimation Methodology for Accelerator Designs.  In IEEE/ACM International Conference On Computer Aided Design (ICCAD), 2019.
  * [27] Werner Scholz, Thomas Schrefl, and Josef Fidler.  Micromagnetic simulation of thermally activated switching in fine particles.  Journal of Magnetism and Magnetic Materials, 233(3):296–304, 2001\.
  * [28] Guohan Hu, MG Gottwald, Q He, JH Park, G Lauer, JJ Nowak, SL Brown, B Doris, D Edelstein, ER Evarts, et al.  Key parameters affecting stt-mram switching efficiency and improved device performance of 400° c-compatible p-mtjs.  In 2017 IEEE International Electron Devices Meeting (IEDM), pages 38–3. IEEE, 2017.
  * [29] Guenole Jan, Yu-Jen Wang, Takahiro Moriyama, Yuan-Jen Lee, Mark Lin, Tom Zhong, Ru-Ying Tong, Terry Torng, and Po-Kang Wang.  High spin torque efficiency of magnetic tunnel junctions with mgo/cofeb/mgo free layer.  Applied physics express, 5(9):093008, 2012.
  * [30] K Ikegami, H Noguchi, C Kamata, M Amano, Keiko Abe, K Kushida, E Kitagawa, T Ochiai, N Shimomura, S Itai, et al.  Low power and high density stt-mram for embedded cache memory using advanced perpendicular mtj integrations and asymmetric compensation techniques.  In 2014 IEEE International Electron Devices Meeting, pages 28–1. IEEE, 2014.