# Artificial intelligence and machine learning generated
conjectures with TxGraffiti

1,2Randy Davila
1Research and Development
RelationalAI
Berkeley, CA 94704, USA
Email<EMAIL_ADDRESS>

2Department of Computational Applied
Mathematics & Operations Research
Rice University
Houston, TX 77005, USA
Email<EMAIL_ADDRESS>

###### Abstract

_TxGraffiti_ is a machine learning and heuristic based artificial intelligence
designed to automate the task of conjecturing in mathematics. Since its
inception, TxGraffiti has generated many surprising conjectures leading to
publication in respectable mathematical journals. In this paper we outline the
machine learning and heuristic techniques implemented by TxGraffiti. We also
recall its contributions to the mathematical literature and announce a new
online version of the program available for anyone curious to explore
conjectures in graph theory.

Keywords: Automated conjecturing; machine learned conjecturing; _TxGraffiti_.
AMS subject classification: 05C69

##  1 Introduction

The ability of carefully designed computer programs to generate meaningful
mathematical conjectures has been demonstrated since the late 1980s, notably
by Fajtlowicz’s GRAFFITI program [23]. Indeed, this heuristic-based program
was the first artificial intelligence to make significant conjectures in
matrices, number theory, and graph theory, attracting the attention of
renowned mathematicians like Paul Erdős, Ronald Graham, and Odile Favaron.
Inspired by the pioneering work of Fajtlowicz, and by interactions with
mathematicians who considered conjectures of GRAFFITI, we developed the
_TxGraffiti_ program, a modern conjecturing artificial intelligence named in
homage to this rich history of conjectures made by GRAFFITI and now available
as an interactive website. While our program TxGraffiti draws inspiration from
GRAFFITI and its successor Graffiti.pc by DeLaViña [19], it was developed
independently and features several distinct design elements and conjecturing
capabilities, which we detail in this paper.

When discussing computer-assisted conjecturing, we remark that it is easy for
a computer to generate many plausible conjectures. For example, one might
gather a set of mathematical objects and test various functions applied to
these objects to identify potential relationships (inequalities). If a
relationship holds across all objects in the database, it becomes a plausible
conjecture. For instance, given a database of graphs and the ability to
compute various parameters on said graphs, a computer might quickly discover
the relation:

$\alpha(G)\leq n(G),$ (1)

where $\alpha(G)$ is the _independence number_ (the cardinality of a maximum
set of pairwise non-adjacent vertices in $G$) and $n(G)$ is the _order_ (the
number of vertices in $G$). A more refined bound for $\alpha(G)$ in
nontrivial, connected graphs is:

$\alpha(G)\leq n(G)-1.$ (2)

Both inequalities 1 and 2 hold under specific conditions, and TxGraffiti is
designed to consider various hypotheses to form such conjectures. The
mechanism for considering different hypotheses is a heuristic called _Theo_ ,
detailed in Section 3.

To discover relationships like inequalities 1 and 2, TxGraffiti employs a
machine learning, data-driven approach using linear optimization methods. This
approach allows the program to find optimal parameters $m,b\in\mathbb{R}$ for
example conjecturing on $\alpha(G)$ in terms of another graph invariant, say
$i(G)$, presenting conjectures in the form:

######  Conjecture 1.

If $G$ satisfies certain boolean conditions, then

$\alpha(G)\leq m\cdot i(G)+b,$

where this bound is sharp.

By integrating machine learning techniques with the Theo and _Dalmation_
heuristics (see Section 2), TxGraffiti generates novel conjectures suitable
for publication in mathematical journals. In Section 2, we discuss the
historical development of AI-assisted conjecturing and relevant techniques.
Section 3 details TxGraffiti’s implementation, Section 4 presents conjectures
produced by TxGraffiti that have led to mathematical publications, and Section
5 provides concluding remarks.

##  2 Related Work

In 1948, Turing proposed that intelligent machines could be a significant
asset in mathematical research, requiring substantial intelligence while
involving _“minimal interaction with the external world”_ [33]. Following this
vision, early work in computer-assisted mathematics includes Newell and
Simon’s _Logic Theorist_ program developed in the 1950s. This program was
capable of proving some theorems in first-order logic, and they boldly
predicted that a computer would eventually discover and prove a crucial
mathematical theorem [32]. This program, among others, focused heavily on
theorem proving, including a notable achievement in 1996 being the computer
proof of the Robbins Conjecture [30].

Artificial intelligent conjecture-making is the other side of computer-
assisted mathematics and began with Wang’s work in the late 1950s [34]. Wang’s
_Program II_ generated numerous statements in propositional logic, which could
be considered conjectures or potential theorems. Despite the program’s
innovative approach, it struggled to filter the vast number of generated
statements to identify those of significant interest, highlighting a key
challenge in automated conjecture-making. Indeed, as mentioned prior, a
computer may easily generate thousands of plausible relationships on a given
database of mathematical objects.

A breakthrough in computer assisted conjecture-making was achieved with
Fajtlowicz’s _GRAFITTI_ program, the first to produce conjectures that led to
published mathematical research [20, 23]. Early versions of Graffiti faced the
”Sorcerer’s Apprentice Problem,” where the challenge was to manage the
overwhelming number of generated conjectures. This issue was mitigated by
Fajtlowicz’s _Dalmatian_ heuristic, which limited both the quantity and
ensured the quality of the output conjectures [24]. This heuristic ensured
that each conjecture was significant concerning at least one object in the
program’s database, and by doing so, also removed any new potential conjecture
that followed by transitivity from another potential conjecture.

GRAFITTI and its successor, _Graffiti.pc_ , developed by DeLaVina, have been
instrumental in advancing computer assisted conjecture-making and have
resulted in numerous publications [19]. These programs, although not widely
distributed, have paved the way for modern automated conjecturing systems.
TxGraffiti, while inspired by these programs, was developed independently and
incorporates unique design elements and conjecturing capabilities. Namely,
TxGraffiti employs a machine learning, data-driven approach using linear
optimization methods to generate plausible conjectured inequalities,
thereafter, implementing two heuristics for filtering conjectures found;
details to be described in Section 3.

Other notable programs in the domain of automated conjecturing include Lenat’s
_AM_ [25, 26, 27], Epstein’s _GT_ [21, 22], Colton’s _HR_ [9, 10, 11], Hansen
and Caporossi’s  _AGX_ [3, 4], and Mélot’s _Graphedron_ [31]. These programs
have significantly contributed to various mathematical domains and have
demonstrated the potential of automated systems in aiding mathematical
discovery.

##  3 Methodology

In designing a computer program that generates mathematical conjectures, the
first requirement is a database of mathematical objects. In the case of
TxGraffiti, these objects are edge lists of simple connected graphs. It is
crucial to underscore the importance of data quality. An extensive database is
optional for the computer to identify non-trivial relationships among object
properties. Instead, what is needed is a collection of unique instances of the
objects in question, such as special counter-examples or interesting families
of graphs from the literature. In our implementations, we utilized databases
of several hundred objects, though we have also experimented with thousands
with little to no meaningful returns in conjecture quality.

###  3.1 Feature Generation

After a collection of mathematical objects is collected, the next step in the
design of TxGraffiti is to generate a table (a csv file representing a
database) of various precomputed functions on the objects in this database.
Our framework mandates that at least two of these functions return numerical
values (for pairwise comparison), while others can return numerical or Boolean
values. See Figure 1 for an illustration of this process; numerical properties
are denoted by $P_{i}$, and Boolean properties are denoted by $H_{i}$.

Figure 1: A mapping of a collection of $N$ mathematical objects to a table of
numerical and Boolean properties.

Indeed, once a table of data like the one is available, TxGraffiti may
conjecture on the data; regardless if the data represents graph object data.
Thus, if one were to generate conjectures on different types of data, one
would first create such a table and then implement the steps in the following
subsections.

###  3.2 Inequality Generation

In this section, we propose and implement a simplified version of the
following steps for a computer program to generate inequalities relating
properties of the objects under consideration, with an emphasis on conjecture
simplicity and on conjecture strength.

  1. 1.

Select a target property $P_{i}$ – a precomputed and numerically valued
function on the objects in the database.

  2. 2.

Choose an inequality direction (upper or lower) to bound the property $P_{i}$.

  3. 3.

For each precomputed numerical function $P_{j}$, with $j\neq i$, use a
supervised machine learning technique or linear program to find a function $f$
such that $P_{i}(\mathcal{O})\leq f((P_{j}(\mathcal{O}))$ holds for each
object $\mathcal{O}$ in the database, _and_ the number of instances where the
inequality is an equality is maximized.

  4. 4.

If $P_{i}(\mathcal{O})\neq f((P_{j}(\mathcal{O}))$ for all objects
$\mathcal{O}$ in the database, disregard $f$ as a conjectured upper (or lower)
bound on $P_{i}$. Otherwise, $f$ is called a _sharp bounding function_ ; store
$f(P_{j})$ as a conjectured upper (or lower) bound on $P_{i}$ and record the
set of objects $\mathcal{O}$ where $P_{i}(\mathcal{O})=f(P_{j}(\mathcal{O}))$;
the size of this set is the _touch number_ of the conjecture.

$\text{Target }P_{i}$$P_{j\neq i}$Sharp bounding
function$y=mP_{j}+b$CONJECTURE:If $\mathcal{O}$ is an object, then
$P_{i}(\mathcal{O})\leq mP_{j}(\mathcal{O})+b$,and this bound is sharp.
Figure 2: Finding a possible (linear) upper bound on the target property
$P_{i}$ in terms of property $P_{j}$.

TxGraffiti follows these steps at each instance of a user requesting a desired
conjecture, with conjectured upper and lower bounds computed automatically
through linear programming formulations. For example, consider producing one
conjectured upper bound on $P_{i}(\mathcal{O})$ in terms of another numerical
valued function $P_{j}(\mathcal{O})$). This is achieved by solving a linear
optimization problem, and in the simplest case, TxGraffiti aims to minimize a
some linear function $f(m,b)$ subject to a set of constraints.

$\displaystyle\underset{m,b}{\text{minimize}}$ $\displaystyle f(m,b)$ subject
to $\displaystyle P_{i}(\mathcal{O})\leq mP_{j}(\mathcal{O})+b,$
$\displaystyle\forall\mathcal{O}\in\text{Database},$

The goal is to find the line with the slope $m$ and y-intercept $b$ that
satisfies all the inequalities and maximizes the number of times these
inequalities hold with equality. In this way, TxGraffiti searches for the best
linear upper bound on $P_{i}(\mathcal{O})$ in terms of $P_{j}(\mathcal{O})$
that holds for all objects $\mathcal{O}$ in the database given some hypothesis
for the objects to satisfy; see Figure 2 for a graphical illustration of the
linear upper bound.

$\text{Target }P_{i}$$P_{j\neq i}$Sharp bounding
function$y=mP_{j}+b$CONJECTURE:If $\mathcal{O}$ is an object and
$\mathcal{O}\in H_{1}$, then $P_{i}(\mathcal{O})\leq
mP_{j}(\mathcal{O})+b$,and this bound is sharp.  Figure 3: Finding a possible
(linear) upper bound on the target property $P_{i}$ in terms of property
$P_{j}$ for objects in $H_{1}$. Data points associated with containment in
$H_{1}$ shown by orange dots, whereas instances no in $H_{1}$ shown by green
dots.

The above process is done on each numerical column of the feature data; that
is, each pair of numerical functions is compared against each other and given
a proposed inequality conjectured between them. Each conjecture generated by
the above steps applies to all types of objects in the database. However, we
can generate even more conjectures. By applying the same steps to a subset of
objects in the database that satisfy a particular Boolean property (or
combination of Boolean properties), we may obtain conjectures that are less
general but potentially stronger; see Figure 3 for an illustration of this
process.

###  3.3 Sorting and Filtering

Once the optimal bounding functions for a given target invariant are found, we
are left with a list of possible conjectures, along with detailed data for
each conjecture. This data includes the set of objects that satisfy the
conjecture’s hypothesis, the graphs that attain equality, and the count of
these graphs. At this point, our program implements a sorting procedure. That
is, the list of conjectures is then sorted in nonincreasing order with respect
to the touch number of the conjectures. Thus, the conjectures at the top of
the list hold with equality more than the conjectures towards the bottom of
the list. Thus, this sorting aspect implemented by our program insures the
conjectures at the top of the list are _“stronger”_ than those at the bottom
of the list.

After the conjectures have been sorted according to their respective touch
numbers, our program then implements the first of two filtering heuristics,
called _Theo_. This heuristic checks if any proposed inequality relation
appears more than once in the list of conjectures, and then only selects the
proposed conjectures with this inequality that have the most general
hypothesis statement. For example, consider the following two conjectures.

######  Conjecture 2.

If $G$ is a connected and cubic graph, then

$\alpha(G)\leq\mu(G),$

and this bound is sharp.

######  Conjecture 3.

If $G$ is a connected and $r$-regular graph with $r>0$, then

$\alpha(G)\leq\mu(G),$

and this bound is sharp.

The Theo heuristic would automatically detect that the inequality
$\alpha(G)\leq\mu(G)$ appears in both Conjecture 2 and in Conjecture 3, and
thereafter, check if the set of graphs in the database that satisfy the
hypothesis of Conjecture 2 also satisfy the hypothesis of Conjecture 3. Since
every cubic graph is also a regular graph, but not vice versa, Theo would
remove Conjecture 2 from the possible conjectures to present to the user. The
reasoning for this heuristic is to put more emphasize on the more general
conjecture, and thus, remove any conjecture that may follow from a more
general statement.

The list of conjectures is (optionally) further filtered by a variation of the
Dalmation heuristic which we call _Dalmation-static_. Unlike the original
Dalmation heuristic used by GRAFFITI [24], our version of Dalmation takes as
input a _static list_ of conjectures and works as following:

Dalmation-Static Heuristic:

  1. 1.

Let $\mathcal{G}$ be the set of graphs attaining equality in Conjecture 1 in
the current list of conjectures, recalling that the conjectures are sorted
according to their respective touch number.

  2. 2.

For $i=2,\dots,N$, if the set of graphs attaining equality in Conjecture $i$
does not contain a which is also graph not contained in $\mathcal{G}$, then
remove Conjecture $i$ from the list of conjectures, otherwise, let
$\mathcal{G}=\mathcal{G}\cup\mathcal{G}_{i}$, where $\mathcal{G}_{i}$ is the
set of graphs attaining equality in Conjecture $i$.

Finally, the conjectures are further filtered by removing any known
conjectures. This aspect of TxGraffiti requires maintenance and is one area
where the program would benefit from many mathematicians contributing to.
Moreover, since conjectures are computed at each prompt to the program,
anytime a new counter-example is added to the database, new conjectures
appear. This aspect motivated further development of the program, where users
may enter in counter-examples to better the conjectures of the program. This
functionality is available by emailing the author via the online website, but
will in the future allow for a more straight-forward approach.

The resulting set of conjectures is a set of conjectures that can be viewed as
_“mathematical strong”_. That is, the linear optimization methods first find
proposed inequalities that are guaranteed to be sharp on a maximum number of
graph instances, thereafter, the Theo heuristic insures generality of the
hypothesis for a conjectures inequality, then the Dalmation-static heuristic
insures presented conjectures only consist of inequalities providing _“new”_
information, and finally the touch number sorting insures conjectures at the
beginning of a list are sharper than ones that follow. In the following
section we demonstrate how these processes show promise for new mathematical
insight in the realm of graph theory.

###  3.4 Code and Reproducibility

For readily available examples of this process, see the GitHub repository
associated with the interactive website [12].

##  4 Results

In this section we present some results stimulated by conjectures of
TxGraffiti. More specifically, we highlight the following results inspired by
conjectures of TxGraffiti and listed in Table 1. Of the results listed in
Table 1, we now focus on the result pertaining to the _independence number_
and _matching number_ of regular graphs. The originial conjecture that
stimulated this result states that for any 3-regular and connected graph $G$,
the independence number $\alpha(G)$ is at most the matching number $\mu(G)$.

######  Conjecture 4.

If $G$ is a connected and cubic (3-regular) graph, then

$\alpha(G)\leq\mu(G),$

where $\alpha(G)$ is the independence number and $\mu(G)$ is the matching
number.

Conjecture | Graph Family | Authors and Publication
---|---|---
$\alpha(G)\leq\mu(G)$ | cubic graphs | Caro et al. [6]
$Z(G)\leq\beta(G)$ | claw-free graphs | Brimkov et al. [2]
$\alpha(G)\leq\frac{3}{2}\gamma_{t}(G)$ | cubic graphs | Caro et al. [7]
$\alpha(G)\leq\gamma_{2}(G)$ | claw-free graphs | Caro et al. [7]
$\gamma_{e}(G)\geq\frac{3}{5}\mu(G)$ | cubic graphs | Caro et al. [7]
$Z(G)\leq 2\gamma(G)$ | cubic graphs | Davila and Henning [17]
$Z_{t}(G)\leq\frac{3}{2}\gamma_{t}(G)$ | cubic graphs | Davila and Henning [15]
$Z(G)\leq\gamma(G)+2$ | cubic claw-free graphs | Davila [13]
Table 1: Notable conjectures in graph theory generated by TxGraffiti and their
corresponding publications.

Notably, Conjecture 4 relates three of the oldest studied properties in graph
theory; namely, independent sets, matching sets, and regular graphs. For this
reason, the author did not share Conjecture 4 for many months, believing it to
be trivial known. However, once shared with collaborators, it became apparent
that not only was this conjecture not known in the literature, but was also
true. Indeed, this conjecture was then generalized and proven, resulting in
the following theorem; the proof of which appears in [6], but is also given
below to demonstrate this simple and meaningful result.

######  Theorem 5 (Caro et al. [6]).

If $G$ is an $r$-regular graph with $r>0$, then

$\alpha(G)\leq\mu(G),$

and this bound is sharp.

###### Proof.

Let $G$ be an $r$-regular graph with $r>0$. Let $X\subseteq V(G)$ be a maximum
independent set, and let $Y=V(G)\setminus X$. By removing edges from $G$ that
have both endpoints in $Y$, we form a bipartite graph $H$ with partite sets
$X$ and $Y$.

Since the removed edges were only those with both endpoints in $Y$, any vertex
in $X$ will have the same open neighborhood in $H$ as it does in $G$. Given
that $G$ is $r$-regular and $X$ is an independent set, each vertex in $X$ will
have exactly $r$ neighbors in $Y$.

Let $S\subseteq X$ be chosen arbitrarily, and let $e(S,N_{H}(S))$ denote the
number of edges from $S$ to $N_{H}(S)$. Since each vertex in $S$ has exactly
$r$ neighbors in $Y$, it follows that $e(S,N_{H}(S))=r|S|$. Additionally,
since each vertex in $N_{H}(S)$ has at most $r$ neighbors in $X$, we also have
$e(S,N_{H}(S))\leq r|N_{H}(S)|$. Thus, $r|S|\leq r|N_{H}(S)|$, implying that
$|S|\leq|N_{H}(S)|$. By Hall’s Theorem; see West [35], there exists a matching
$M$ that can match $X$ to a subset of $Y$. Since $X$ is a maximum independent
set and $M$ is also a matching in $G$, we conclude that
$\alpha(G)=|M|\leq\mu(G)$, proving the theorem. ∎

Notably, by confirming Conjecture 2 with Theorem 5, we were inspired to
include the more general hypothesis of regular graphs in conjectures presented
by TxGraffiti, and this resulted in the more general statement of Theorem 5
being presented as a conjecture by the program. From an application point of
view, the resulting theorem due to Conjecture 2 is further interesting since
the computation of the matching number $\mu(G)$ is computable in polynomial
time, whereas the computation of the independent number $\alpha(G)$ is NP-
hard. Thus, the resulting theory gathered from investigating Conjecture 2 has
practical applications in graph theory and the sciences.

##  5 Conclusion

In this paper, we have described the artificial intelligence program
TxGraffiti and also provided evidence for its usefulness in mathematical
research as its conjectures span various areas of graph theory; many leading
to significant publications. Moreover, we provide a new web-based interaction
for TxGraffiti which may lead to even further mathematical insight. We
anticipate that further development and application of the ideas underpinning
TxGraffiti will lead to further insights into computer assisted mathematics.

## References

  * [1] AIM Special Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl., 428 (7) (2008), 1628–1648.
  * [2] B. Brimkov, R. Davila, H. Schuerger, and M. Young, Computer assisted discovery: Zero forcing vs vertex cover, available at https://arxiv.org/pdf/2209.04552.pdf, (2022).
  * [3] G. Caporossi and P. Hansen, Variable neighborhood search for extremal graphs: 1 The autographix system, _Discrete Math._ 212(1–2) (2000), 29–44.
  * [4] G. Caporossi and P. Hansen, Variable neighborhood search for extremal graphs: 5 Three ways to automate finding conjectures, _Discrete Math._ 276(1–3) (2004), 81–94.
  * [5] M. Aouchiche, G. Caporossi, P. Hansen, and M. Laffay, Autographix: A survey, _Electron. Notes Discrete Math._ 22 (2005), 515–520.
  * [6] Y. Caro, R. Davila, and R. Pepper, New results relating matching and independence, Discuss. Math. Graph Theory 42 (2020), 921–935.
  * [7] Y. Caro, R. Davila, M.A. Henning, and R. Pepper, Conjectures of TxGraffiti: Independence, domination, and matchings, _Australas. J. Comb._ 84(2) (2022), 258–274.
  * [8] C. Chekuri and N. Korula, A graph reduction step preserving element-connectivity and applications, _Automata, Languages, and Programming,_ (2009) 254–265.
  * [9] S. Colton, A. Bundy and T. Walsh, Automated concept formation in pure mathematics, _Proc. of the 16th Int. Jt. Conf. on Artif. Intell.,_ vol. 2, IJCAI’99, Morgan Kaufmann Publishers (1999), 786–791.
  * [10] S. Colton, Refactorable numbers—a machine invention, _J. Integer Seq._ 2 (1999), Article 99.1.2.
  * [11] S. Colton, Automated Theory Formation in Pure Mathematics, Springer, Heidelberg (2002).
  * [12] R. Davila, _TxGraffiti_ , https://txgraffiti.streamlit.app, accessed 2024-06-19.
  * [13] R. R. Davila, Another conjecture of TxGraffiti concerning zero forcing and domination in graphs, _arXiv preprint arXiv:2406.19231_ , (2024). Available at https://doi.org/10.48550/arXiv.2406.19231.
  * [14] R. Davila, Total and Zero Forcing in Graphs, _University of Johannesburg_ , PhD Thesis (2019).
  * [15] R. Davila and M. A. Henning, Total forcing versus total domination in cubic graphs, Appl. Math. Comput., 354 (2019), 385–395.
  * [16] R. Davila and M.A. Henning, Zero forcing in claw-free cubic graphs, _Bull. Malays. Math. Sci. Soc._ , 43 (2020), 673–688.
  * [17] R. Davila and M. A. Henning, Zero forcing versus domination in cubic graphs, _J. Comb. Optim._ , 41 (2021), 553–577.
  * [18] A. Davies, P. Veličković, L. Buesing, S. Blackwell, D. Zheng, N. Tomašev, R. Tanburn, P. Battaglia, C. Blundell, A. Juhász, M. Lackenby, G. Williamson, D. Hassabis, and P. Kohli, Advancing mathematics by guiding human intuition with AI, _Nature_ , 600 (2021), 70–74.
  * [19] E. DeLaViña, Graffiti.pc: A variant of Graffiti, _DIMACS Ser. Discret. Math. Theor. Comput. Sci._ 69 (2005), p. 71.
  * [20] E. DeLaViña, Some history of the development of Graffiti, _Graphs and Discovery, DIMACS Ser. Discret. Math. Theor. Comput. Sci._ 69, Amer. Math. Soc., Providence, RI (2005), 81–118.
  * [21] S.L. Epstein, On the discovery of mathematical theorems, _IJCAI_ (1987), 194–197.
  * [22] S.L. Epstein, Learning and discovery: One system’s search for mathematical knowledge, _Comput. Intell._ 4(1) (1988), 42–53.
  * [23] S. Fajtlowicz, On conjectures of GRAFFITI, _Discret. Math._ , 72 (1988), 113–118.
  * [24] C. E. Larson and N. Van Cleemput. Automated conjecturing I: Fajtlowicz’s Dalmatian heuristic revisited, _Artif. Intell._ 231 (2016), 17–38.
  * [25] D.B. Lenat, The ubiquity of discovery, _Artif. Intell._ 9(3) (1977), 257–285.
  * [26] D.B. Lenat, On automated scientific theory formation: A case study using the am program, _Mach. Intell._ 9 (1979), 251–286.
  * [27] D.B. Lenat, The nature of heuristics, _Artif. Intell._ 19(2) (1982), 189–249.
  * [28] E. Flandrin, R. Faudree, and Z. Ryjáček, Claw-free graph - a survey, _Discrete Math._ 214 (2016), 196–200.
  * [29] D. Nakamura and A. Tamura, A Revision of Minty’s Algorithm for Finding a Maximum Weight Stable Set of a Claw-Free Graph, _J. Oper. Res. Soc. Japan_ 44 (2001), 194–204.
  * [30] W. McCune, Solution of the Robbins problem, _J. Autom. Reason._ , 19(3) (1997), 263–276.
  * [31] H. Mélot, Facet defining inequalities among graph invariants: The system graphedron, _Discrete Appl. Math._ 156(10) (2008), 1875–1891.
  * [32] H.A. Simon, A. Newell, Heuristic problem solving: the next advance in operations research, _Oper. Res._ , 6(1) (1958), 1–10.
  * [33] A. Turing, Intelligent machinery. _The Essential Turing_ , (2004), 395–432.
  * [34] H. Wang, Computer theorem proving and artificial intelligence, _Computation, Logic, Philosophy_ , Springer (1990), 63–75.
  * [35] D. B. West, Introduction to Graph Theory 2nd Edition. Prentice-Hall (20010. ISBN: 0-13-014400-2 (print)


# ACCO: Automated Causal CNN Scheduling Optimizer for Real-Time Edge
Accelerators

Jun Yin1, Linyan Mei1, Andre Guntoro2, Marian Verhelst1 This project has been
partly funded by the MSCA program under grant agreement No. 956962, the
European Research Council (ERC) under grant agreement No. 101088865, the
European Union’s Horizon 2020 programme under grant agreement No. 101070374
and the Flanders AI Research Program. 1ESAT-MICAS KU Leuven, 2Robert Bosch
GmbH 1{jun.yin, linyan.mei<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Spatio-Temporal Convolutional Neural Networks (ST-CNN) allow extending CNN
capabilities from image processing to consecutive temporal-pattern
recognition. Generally, state-of-the-art (SotA) ST-CNNs inflate the feature
maps and weights from well-known CNN backbones to represent the additional
time dimension. However, edge computing applications would suffer tremendously
from such large computation/memory overhead. Fortunately, the overlapping
nature of ST-CNN enables various optimization methods, such as the dilated
causal convolution structure and Depth-First (DF) layer fusion to reuse the
computation between time steps and CNN sliding windows, respectively. Yet, no
hardware-aware approach has been proposed that jointly explores the optimal
strategy from a scheduling as well as a hardware point of view.

To this end, we present ACCO, an automated optimizer that explores efficient
Causal CNN transformation and DF scheduling for ST-CNNs on edge hardware
accelerators. By cost-modeling the computation and data movement on the
accelerator architecture, ACCO automatically selects the best scheduling
strategy for the given hardware-algorithm target. ACCO’s time-dimension
optimization reaches a 8.4$\times$ better Energy-Delay-Product compared to the
fixed dilated causal conversion, while ACCO’s spatial DF optimization improves
$\sim$20% compared to the SotA DF exploration toolchain. When jointly
optimizing ST-CNN spatially and temporally, ACCO’s scheduling outcomes are on
average 19$\times$ faster and 37$\times$ more energy-efficient than spatial DF
schemes.

©2023 IEEE. Personal use of this material is permitted. Permission from IEEE
must be obtained for all other uses, in any current or future media, including
reprinting/republishing this material for advertising or promotional purposes,
creating new collective works, for resale or redistribution to servers or
lists, or reuse of any copyrighted component of this work in other works. DOI:
10.1109/ICCD58817.2023.00065.

##  I Introduction

Over the past decade, Convolutional Neural Networks (CNNs) have become an
essential workhorse for computer vision tasks. Carrying forward its success,
CNNs have been extended from the image processing field to spatio-temporal
reasoning tasks. Recently, many successful models have been developed in
different application domains, such as visual tracking [1, 2], acoustic
perception [3, 4], biomedical information extraction [5, 6], etc. As shown in
Fig. 1a, these designs typically include the time axis as an additional
dimension of the input feature map which then allows to leverage conventional
SotA CNN structures with a reshaped spatio-temporal input. However, adding the
required time dimension to these CNNs inflates the CNN models with massive but
unnecessary hardware overhead that hinders real-time edge processing.

Figure 1: The overview of ACCO: a) illustration of spatio-temporal input
features; b) the conventional execution of ST-CNN; c) the DF execution of
dilated causal CNN on input-feature updates; d) ACCO’s accelerator modeling
and scheduling design space exploration (DSE).

Several algorithm-oriented optimization methods are available to ease such
hardware pressure, such as quantization and pruning for DNN compression, as
well as advanced spatio-temporal structures like convolutional recurrent
neural networks (CRNN). Yet, all these optimizations require additional model
re-training steps to avoid accuracy loss. Spatio-temporal CNN (ST-CNN) can,
however, exploit another optimization pass which does not require retraining.
Due to (shifted) data repetition across the spatio-temporal input feature
maps, there exists repeated intermediate activations throughout the network
across subsequent frames. These can be cached and reused between adjacent
frames, while only the newly updated input lines need to be propagated through
the CNN (Fig. 1c). This becomes possible by combining principles from dilated
causal CNN topologies [7] and depth-first (DF) CNN execution [8].

A large amount of computations can be saved from such joint workload topology-
scheduling optimization without the need for any network retraining. Yet, this
brings new efficiency challenges: On the one hand, CNN’s parallelism within a
single input frame is reduced because the temporal dimension is replaced by
intermediate-result caching. As a result, the hardware accelerator could be
under-utilized, and the weight loading will become more dominant. On the other
hand, the cached data puts additional pressure on the memory system, even more
so when execution is progressing in batches of several input frames.

This results in a huge optimization space stemming from multiple potential DNN
transformations due to the newly introduced caching and scheduling options. To
tackle this enlarged design space, we propose a unified optimization
framework, ACCO, to perform joint design space exploration (DSE) on the
workload transformation, hardware computation scheduling, and memory
allocation (Fig. 1d). The optimization is based on comprehensive hardware cost
modeling in terms of energy and latency. The contributions of ACCO can be
highlighted as:

  1. 1.

The formal extension of the DF design space towards ST-CNN workloads with an
automatic layer-fusion transformation (Section III);

  2. 2.

The open-source111https://github.com/KULeuven-MICAS/ACCO. implementation of
the DSE on this formalized design space towards optimal latency and energy
based on precise hardware cost modeling (Section IV);

  3. 3.

The conduction of four case studies, including ablation studies and SotA
comparisons to demonstrate ACCO’s strength, optimizing representative ST-CNN
models for both the single and batch frame(s) (Section V).

##  II Background and Motivation

###  II-A Dilated Causal CNNs

Temporal data can be efficiently processed through dilated causal convolutions
[7]. As shown in Fig. 2a, these extend the receptive field of a CNN through
dilation and causality, without increasing the number of parameters. By
introducing gaps in the filters, the dilation factor controls the spacing
between the filter elements, enabling larger receptive fields. Causality
ensures that information flows only from the past to the future, making it
suitable for sequential data processing. This combination allows the model to
capture long-range dependencies efficiently, making dilated causal convolution
popular in tasks such as natural language processing, audio processing, and
time series analysis. For example, the TCN [9] structure leverages such
structure to efficiently process sequential data, such as time series or
temporal sequences.

###  II-B Depth-First DNN Execution

Spatial CNNs can exploit DF execution (a.k.a layer fusion [8]). In contrast to
layer-by-layer execution, this technique breaks each layer into multiple
individually schedulable tiles and schedules them across layers, while either
caching or recomputing data required by multiple tiles (Fig. 2b). DF
scheduling can largely benefit in terms of energy efficiency and latency
because of the its reduced memory footprint stemming from in-place consumption
of intermediate DNN activations between layers. Since the smaller intermediate
activation tiles can be stored and reused at a lower memory level (e.g., the
global buffer) they save a lot of costly memory fetches from higher memory
levels (e.g., DRAM).

DF execution contains various scheduling options and leads to a large design
space, such as different tile sizes, number of fused layers, cross-tile
overlapped data handling, etc. Different DF schemes can be observed in many
DNN accelerators published recently [10, 11, 12, 13, 14].  Yet, all these
implementations have ad-hoc and pre-defined tile sizes, fusing depth, and
overlap data storing modes. It is challenging to justify whether a design
choice is optimal for target workloads due to the immense DF design space,
necessitating automatic and fast DSE frameworks.

###  II-C Automatic Scheduling Exploration Frameworks

In exploring the DNN scheduling space automatically and quickly, two key
aspects are highlighted: evaluation and exploration. The former aspect models
different scheduling options while rapidly evaluating their hardware costs.
The latter aspect explores the DNN scheduling space and automatically
generates candidate schedules for cost evaluation. This search-evaluation loop
can iterate multiple times to converge towards the Pareto-optimal scheduling
points.

Several DF scheduling exploration frameworks have been developed recently,
such as [15, 16, 17, 18], each with a different focus. For example, DNNFuser
[15] focuses on the DF space search and proposes a one-shot Transformer-based
DF scheduler; DNNVM [16] transforms DNN models into DAG and enumerates all
potentially profitable fusion opportunities by a heuristic subgraph
isomorphism algorithm; MCUNetV2 [18] introduces patch-based inference and
jointly optimizes the neural architecture and DF scheduling so as to reduce
the peak memory usage; DeFiNES [17] constructs a 3-axis DF scheduling design
space and proposes a unified analytical modeling approach for fast hardware
cost evaluation.

Yet, such automatic exploration remains unaware of the causal input
relationship as mentioned in Section II-A.

Figure 2: The background concept diagrams: (a) the dilated causal convolution
structure [7]; (B) the Depth-First DNN execution scheduling [17].

###  II-D Motivation

Fig. 2 shows the similarity in dataflow between the dilated causal convolution
structure and the DF execution scheduling. This sheds light on efficiently
optimizing ST-CNN workloads in a common framework, as indicated in Fig. 3c and
3d, for further performance/efficiency boosting.

To do so, new challenges can be identified as follows:

  1. 1.

to convert the causal overlap across the time-dimension into a DF schedulable
workload while maintaining mathematical equivalence with the original ST-CNN;

  2. 2.

to handle the difference in cost modeling and optimization between a single
causal input frame and the entire flattened spatio-temporal batch of frames;

  3. 3.

to jointly manage the increased size of the intermediate activation cache as
well as the weights under the limited on-chip memory resources.

ACCO tackles these challenges and enables to automatically explore the
enlarged scheduling space (Section III).

##  III Design of ACCO

This section details the ACCO concepts and components for the scheduling
optimization of causal CNNs. Firstly, Section III-A introduces the
relationship between the core concepts on which ACCO is based, such as the ST-
CNN, dilated causal CNN structure, and DF scheduling. Next, Section III-B
proposes a general methodology to transform a ST-CNN into a dilated causal CNN
structure compatible with DF scheduling. Section III-C summarizes the design
parameters that form ACCO’s design space, while Section III-D identifies the
corresponding trade-offs.

In the following sections, we focus on 2D ST-CNNs with a row-major execution
order. The concepts are also expandable towards higher dimensionality. As
shown in Fig. 3a and 3c, the feature map’s $\mathbf{X}$ dimension is for the
spatial, and $\mathbf{Y}$ dimension is for the temporal dimension.

###  III-A Core Concepts of ACCO

As introduced in Section I, conventional ST-CNNs treat the temporal feature
dimension in the same way as the spatial dimension. However, as visualized in
Fig. 3a, the overlap between values in the feature map of subsequent input
frames indicates the potential reuse of previously computed CNN activations.

As introduced in Section II-A, a dilated causal CNN structure can exploit such
intermediate result caching and reuse it across sequential ST-CNN input
frames. This is illustrated in Fig. 3b. Only the latest row of the current
input is computed across the CNN. In contrast, the remainder of the input
feature map is already calculated in previous time steps and thus reused
according to the causal dependency of different layers. Chronologically, such
execution can be seen as the continuous processing of the CNN on a temporal-
flattened input feature map, as shown in Fig. 3c.

With such causal overlapping embedded in the flattened feature map, DF
execution along the temporal feature dimension (Fig. 3d) can be exploited.
Both the DF and dilated causal CNN are designed to minimize the size and
lifetime of every layer’s input data by serializing the computation and
reusing shared intermediate results. That is, each input feature or
intermediate activation only persists in the system until all the dependent
computations have been completed for all outputs. Unlike the algorithm-
oriented dilated causal CNN, the DF scheduling considers both the hardware
cache prefill phase (“Warm-Up”) and the cache update phase (“Stable”).

For the real-time single-frame update, only one temporal slice has to be
computed (Fig. 3d). Likewise, the batched update is for trigger-based
processing on collected snippets (e.g., sound events [4] and biomedical
sequences [5, 6]).

Figure 3: ACCO’s basic concept relationship: a) the original input feature map
for ST-CNNs; b) the dilated causal CNN transformation that reduces temporally-
overlapped computation; c) the input flattening that embeds such temporal-
overlapping information for scheduling optimization; d) the hardware-oriented
DF scheduling that optimizes the flattened ST-CNN.

###  III-B ST-CNN Transformation

Yet, DF execution so far has only been developed for frame-based processing,
lacking the ability to track temporal relationships across different
sequential input frames of the original ST-CNN (Fig. 3a). Therefore, ACCO
introduces a workload transformation step to enable the automated scheduling
optimization exploiting both temporal computational reuse, as well as DF
execution. ACCO first performs a transformation on the original ST-CNN to
obtain, on the one hand, a temporally-flattened input feature map (Fig. 3c)
and, on the other hand, an equivalent causal CNN operating on that input map
for DF scheduling (Fig. 3d). This transformation is possible for any network
consisting of sliding-window-based kernels (CONV, POOL, Residual, etc.). Other
kernels, such as the Fully-Connected layers, are left for future research.

For the transformed input, we denote its temporal stride as $\mathcal{S}_{0}$,
which links the temporally-flattened input (Fig. 3c) back to its original form
(Fig. 3a). That is, with each new original input, the flattened input map
grows with $\mathcal{S}_{0}$ in size at the temporal dimension.

Figure 4: A 2-pooling example on how ACCO fixes the layer-stride mismatch at
the ST-CNN Transformation by converting strides to dilations. The diagram
explains the processing of 4 consecutive ST-CNN input frames in the original
and flattened manner. Such conversion is meant for result equivalence after
the frame flattening. The colorized data alignment highlights unique values.

Further, for the ST-CNN model transformation, special care has to be given to
layers whose temporal stride size $\mathcal{S}_{k}$ mismatches with the global
input’s $\mathcal{S}_{0}$. Fig. 4 provides an $\mathcal{S}_{0}=1$ example for
such temporal stride mismatch and how it is resolved after transformation. If
any intermediate layer has $stride\neq\mathcal{S}_{0}$ in the same dimension,
the overlapping pattern of input data would be changed at the output. For
example, after a Stride-2 POOL-2 layer, the overlapping frames 1 and 2 in Fig.
4a become mutually exclusive in Fig. 4b, while frame 1 and 3 keeps their
overlapping. In our flattened model, we first align all these data in the
chronological order of sliding-window computation to ensure no data is missing
during the DF scheduling. Then, we perform the stride-to-dilation
transformation to help the next layers correctly fetch their corresponding
input from these flattened feature maps.

More formally, considering a Layer-$k$ in an $N$-layer ST-CNN model, we denote
its original temporal-dimension stride and dilation factor as
$\boldsymbol{\mathcal{S}}_{k}$ and $\boldsymbol{\mathcal{D}}_{k}$,
respectively. The original input frame updates on the temporal dimension with
stride size $\boldsymbol{\mathcal{S}}_{0}$. Therefore, the equivalent
Layer-$k$ of the flattened model after transformation is defined as:

$\left\\{\begin{aligned}
(\boldsymbol{\mathcal{S}}_{k})_{new}&=\gcd(\boldsymbol{\mathcal{S}}_{0},\boldsymbol{\mathcal{S}}_{k})&\\\
(\boldsymbol{\mathcal{D}}_{k})_{new}&=\frac{(\boldsymbol{\mathcal{I}}_{input})_{k}}{(\boldsymbol{\mathcal{S}}_{k})_{new}}\times\boldsymbol{\mathcal{D}}_{k}&,k\in[1,N]\\\
(\boldsymbol{\mathcal{I}}_{output})_{k}&=\frac{(\boldsymbol{\mathcal{I}}_{input})_{k}}{(\boldsymbol{\mathcal{S}}_{k})_{new}}\times\boldsymbol{\mathcal{S}}_{k}\end{aligned}\right.$
(1)

where the $\boldsymbol{\mathcal{I}}_{input}$ and
$\boldsymbol{\mathcal{I}}_{output}$ denote the amount of interleaved original
frames in the transformed Layer-$k$’s flattened input and output,
respectively. As illustrated in Fig. 4b and 4c, this factor is passed down
into the successor layer (e.g., Layer-($k$+1)) as
$(\boldsymbol{\mathcal{I}}_{input})_{k+1}=(\boldsymbol{\mathcal{I}}_{output})_{k}$.

In practice, we normalize to $\boldsymbol{\mathcal{S}}_{0}\equiv
1,\boldsymbol{\mathcal{I}}_{0}\equiv 1$ as the global input’s generation rate.
Therefore, according to Eq.(1), the new stride and dilation factors can be
computed:

$\left\\{\begin{aligned} (\boldsymbol{\mathcal{S}}_{k})_{new}&\equiv 1&\\\
(\boldsymbol{\mathcal{D}}_{k})_{new}&=\boldsymbol{\mathcal{D}}_{k}\times\prod_{i}\boldsymbol{\mathcal{S}}_{i}&,i\in\mathbf{P}\\\
\end{aligned}\right.$ (2)

with $\mathbf{P}$ the index set of all the predecessor layers to Layer-$k$.

With this transformation, temporal features of the ST-CNN computation are
fully embedded into one spatially-defined model and can be exploited during DF
scheduling.

###  III-C DF Scheduling Design Space

Compared to the original frame-by-frame CNN execution, ACCO aims to find
Pareto-optimal DF scheduling strategies for the transformed ST-CNN workload.
Given a hardware accelerator architecture with a fixed spatial-unrolling and
limited on-chip memory resources, ACCO explores the design space with two key
exploration parameters:

####  III-C1 Computation Tiling Size

CNN kernels can be described as nested for-loops across all kernel and output
tensor dimensions. Splitting any of these for-loops into an inner for-loop and
an outer for-loop and reordering them allows for workload tiling to optimize
memory usage. ACCO performs a tiling exploration for each layer’s output
dimensions, exploring loop splitting with configurable Spatial Tiling Size and
the Temporal Tiling Size along the spatial and temporal dimensions of the
temporal-flattened feature map of Fig. 3c. The tiling along these two
dimensions directly influences the DF scheduling granularity, impacting the
computing and caching overhead, as introduced in Section II-B. DF scheduling
partitions the last layer’s output features based on these tiling sizes and
automatically collects dependent computation from previous layers.

####  III-C2 Depth-First Layer Fusion Range

A DNN workload can be cut and fused in multiple ways into a set of sub-stacks
on which DF scheduling is performed separately. The location of these stack
cuts, i.e., the Layer Fusion Range, is the second exploration parameter of
ACCO.

###  III-D Design Space Trade-off Identification

Figure 5: A 3-layer workload example on the ACCO scheduling trade-offs. The
tile-wise computation of three manually-chosen corner cases is illustrated: a)
DF fusion of all layers, 100% tiling at output; b) DF fusion of all layers,
50% tiling at output; c) DF fusion into 2 sub-stacks, 50% tiling at each sub-
stack’s output. Their hardware overheads are qualitatively visualized assuming
the ideal data localization. Abbreviations: W/I/O = Weights/Inputs/Outputs; GB
= Global Buffer; LB = Local Buffer; PE = Processing Elements.

Based on the introduced exploration parameters, ACCO explores the Pareto-
optimal solutions for any CNN workload-accelerator pair.

Intuitively, one should tile as much as possible and fuse layers as deep as
possible to maximize the computational parallelism and the reuse of cached
data, just like the traditional dilated causal CNN of Fig. 2a. However, the
actual situation is much more complex.

To illustrate this entangled design space, Fig. 5 shows an example with 1d
input data and a 3-layer dummy CNN workload (Conv3-s2, Pool2-s2, and
Conv3-s1). The input and output sizes are set to 1$\times$12 and 1$\times$2,
respectively. Three manually-chosen corner cases with typical tiling and layer
fusion are visualized on their tile-wise computation complexity and
qualitative hardware overhead.

To begin with, Fig. 5a represents the aforementioned baseline case, where all
layers are fused into one DF stack without tiling the output (tile size =
output size). In this case, the scheduling falls back into normal layer-by-
layer frame-by-frame execution, where no intermediate result is cached. Of
course, the resulting parallelism within each layer allows the weights to be
reused or consumed locally.

Fig. 5b opts for a smaller output tile size under the same end-to-end layer
fusion to exploit DF processing benefits. Intermediate feature maps are cached
and consumed as soon as possible, leading to more efficient IO memory usage.
This comes at the expense of reduced intra-layer parallelism, leading to poor
weight data reuse and low PE utilization.

Finally, Fig. 5c pursues tiled DF execution with shallower layer fusion that
cuts the workload into two separate sub-stacks. In the Stack-1 with wider
output size, a higher tiling size can be chosen while still preserving DF
features.  Compared to Fig. 5b, the active data cache (green) in the IO memory
stays the same because of the same 50% DF tiling ratio, while more computation
parallelism (orange) and weight reuse (red) are obtained. Of course, this
solution comes with additional data movement to transfer cached data between
these sub-stacks. Therefore, ACCO performs a DRAM Skipping (DS) check to
improve inter-sub-stack data locality.

In short, the actual Pareto-optimal strategy might vary for different
workloads and accelerator architectures. A careful exploration with a reliable
cost model is required to explore the complete design space. This will be
realized in the ACCO implementation (Section IV).

Figure 6: The overview of ACCO’s implementation.  TABLE I: Workload parameter
relationship between the three ST-CNN execution modes.

Execution Mode | Baseline | Real-Time2 | Batch2
---|---|---|---
Spatial Output | $OX{\textsuperscript{1}}$ | $OX$ | $OX$
Temporal Output | $OY{\textsuperscript{1}}$ | 1 | $OY\times\prod\boldsymbol{\mathcal{S}}_{i}$
Temporal Frames | $\prod\boldsymbol{\mathcal{S}}_{i}$ | ${{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}}$ | ${{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}}$

  * 1

The original ST-CNN’s output size. X/Y for spatial/temporal features as
defined in the prologue of Section III.

  * 2

The real-time/batch mode which represents the workload of single-frame/batched
update in Fig. 3d. Hence, one Batch-mode temporal frame is equivalent to
$\prod\boldsymbol{\mathcal{S}}_{i}$ Baseline-mode frames.

TABLE II: The parameters of the evaluated DNN workloads.

##  IV Implementation of ACCO

To enable automatic workload transformation and scheduling exploration on the
formalized design space from Section III, we build ACCO as an extension to
DeFiNES [17]. DeFiNES is a silicon-verified scheduling exploration tool that
enables the rapid DF optimization on DNN workloads given the accelerator PE
architecture and on-chip memory hierarchy.

The overview of ACCO’s DSE workflow is shown in Fig. 6. The system is built
with new stages on top of DeFiNES to implement Section III’s concept
accordingly: a) The tiling exploration, b) the layer fusion exploration, c)
the ST-CNN transformation, d) the inter-sub-stack data transfer optimization.
For each fused DF sub-stack, the DeFiNES toolchain is invoked for intra-sub-
stack DSE. To speed up the enlarged DSE process, an early-stopping module is
added to prevent exploring schedules with activation tiles that do not fit
into on-chip memory. Finally, all evaluated layer sub-stacks are collected and
aggregated for end-to-end cost modeling. In Section V, ablation studies are
carried out to show the efficacy of each module.

##  V Experiments and Discussions

We carry out four case studies in this section to verify the effectiveness of
ACCO. Section V-A introduces our experiment setups. Section V-B and V-C
conducts two ablation studies on ACCO’s DSE tradeoffs and overall results.
Section V-D compares ACCO with its SotA baseline DeFiNES [17]. Section V-E
demonstrates ACCO’s benefits for ST-CNNs in real-time scenarios against other
SotA solutions.

TABLE III: The parameters of the evaluated hardware accelerator architectures.

Figure 7: The ablation study of ACCO’s design space trade-offs across 7
spatio-temporal tiling cases and 3 layer-fusion scenarios (w/o cut, cut at
Layer-7, and cut at Layer-5,9), with batch-mode STFT-CNN workload on the Meta-
Edge accelerator. Two aspects are studied: 1) how the design parameters of
tiling and layer fusion impact the data size of Peak I+O+Cache and Inter-
Substack transfer; 2) how the overall latency-energy trade-off reacts to these
design parameters. Abbreviation: GB = Global Buffer.

###  V-A Experiment Setups

We evaluate three execution modes for ST-CNN workloads: Baseline, Real-time,
and Batch, computing on the original input, single time-step input update, and
the temporal-flattened input, respectively. Following to the transformation
discussed in Section III-B, the workload parameters are listed in Table I.
Note that such Real-time computation is mathematically equivalent to the
Baseline single-frame execution.

We define four workloads for our case studies in Table II. These workloads
leverage the following backbone structures: VGG [19], MobileNetV1 [20], and
ResNet18 [21], which are widely adopted for feature extraction in spatio-
temporal applications [5, 6, 3, 4, 1, 2]. The data bit width is set to 8 bits
in accordance with quantized edge CNNs. Each model excludes its final fully-
connected layers, as explained in Section III-B.

As the DSE hardware target, we select three well-known DNN accelerator
architectures: Meta’s architecture [22], the Edge TPU [23], and the Tesla NPU
[24]. To mimic edge execution context and ensure a fair comparison, we
normalize their compute array dimension to 1024 MAC units with an on-chip
global buffer capacity of 2 MiB, while maintaining each accelerator’s spatial
unrolling strategy and memory hierarchy. The resulting architectures are
summarized in Table III. All hardware modeling follows the setup in the
baseline toolchain [17] with CACTI-based [25] memory models.

For convenience, we list common term abbreviations used throughout this
section for result discussion as follows:

  1. 1.

LBL: the basic Layer-by-Layer DNN execution;

  2. 2.

DF: the Depth-First DNN scheduling [8]

  3. 3.

FT: the Fixed-Tiling strategy that tiles each DF computation by HW
architecture’s unrolling factors (Table III);

  4. 4.

TE: ACCO’s spatial/temporal Tiling Exploration;

  5. 5.

LFE: ACCO’s DF Layer Fusion Exploration;

  6. 6.

DS: ACCO’s inter-sub-stack DRAM Skipping strategy;

  7. 7.

Best-LAT/ENE/EDP: DSE cost functions that optimize for the best Latency,
Energy or Energy-Delay-Product;

###  V-B Case Study 1: The Ablation Study of ACCO DSE Tradeoffs

To quantify the trade-off discussion of Fig. 5, we design this ablation study
to manifest the trade-offs of each ACCO DSE component by optimizing the batch-
mode STFT-CNN workload on Meta-Edge hardware.

The exploration results across ACCO’s degree of freedom (tiling size and DF
stack depth) are shown in Fig. 7. The results can be interpreted as:

####  V-B1 Tiling Exploration (TE)

Generally, all 3 scenarios in Fig. 7 prove the benefits of workload
parallelization from increased tiling sizes. However, larger tiles also
increase the input and output data volume of each tile, which is further
magnified by the caching requirement in DF execution (i.e. the Peak I+O+Cache
in Fig. 7).

For the STFT-CNN, the tiling benefit saturates around the tile size (16,16)
after achieving about 8$\times$ latency and 6$\times$ energy savings on
average. This testifies to the case in Fig. 5a because when the tiling
increases beyond the STFT-CNN’s output shape (16$\times$16), the entire layer
is processed in one go, thus the DF computation falls back to be layer-by-
layer. Especially, the energy overhead of Tiling-(64,64) in Fig. 7a worsens by
40% because DF still tries to manage all layers’ data movement as a layer-
fused block so that the LB overflows at this corner.

####  V-B2 Layer-Fusion Exploration (LFE)

The direct benefit of cutting the entire CNN into multiple sub-stacks is the
reduction in active data volume. Comparing Fig. 5c to 5a, the data engaged by
the tile-unit computation reduces after cutting the workload into 2 sub-stacks
(more non-dependent data).

Comparing the Peak I+O+Cache overhead of Fig. 7b&7c to 7a, an average
reduction of 20.5% can be observed. However, the latency-energy benefits from
LFE would be neutralized by the additional inter-sub-stack data transfer via
DRAM.

####  V-B3 Inter-sub-stack DRAM Skipping (DS)

ACCO’s baseline design, DeFiNES [17], synchronizes inter-sub-stack
intermediate results through DRAM. Yet, from the analysis in 2), the Peak
I+O+Cache of the entire workload can be within the size of Global Buffer (1
MiB) if performing the TE and LFE wisely (scenarios in Fig. 7b&7c with
below-(32,32) tiling).

That is, in these cases, the intermediate activations could reside in GB to be
used by the next sub-stack, skipping the DRAM detour. Hence, the additional
latency and energy overhead of such data transfer can be saved, marked by the
red and blue shades in Fig. 7b&7c, with varying benefits across different
choices in TE and LFE.

Figure 8: The ACCO DSE result ensemble for batch-mode STFT-CNN workload on the
Meta-Edge accelerator. The maximal Layer-Fusion sub-stack amount explored is 3
(Cut #0/1/2). Under each layer-fusion scenario, the best combination of tiling
strategy for each sub-stack is explored towards the DSE target metrics (e.g.,
Latency and Energy-Delay-Product (EDP)). The best trade-off from Fig. 7 is
shown as the sub-optimal reference case (c).

###  V-C Case Study 2: The Best Outcome from Joint DSE

Figure 9: The energy-latency ablation study of batch-mode STFT-CNN DSE on all
three accelerators, together with the best scheduling solutions found by ACCO.
Compared with the ACCO scheduling, the Layer-By-Layer (LBL) and basic DF (DF)
execution patterns are shown as the baseline.

Fig. 8 plots a range of ACCO exploration results for best latency and best
energy explorations in batch mode, highlighting also the best results analyzed
in Fig. 7. It is clear that more optimal solutions can be found with ACCO’s
complete DSE strategy (TE+LFE+DS). The Pareto-optimal frontier can be pushed
forward by 3.3% for Best-LAT (Fig. 8a) and 4.1% for Best-EDP (Fig. 8b)
compared to the reference case (Fig. 8c).

Next, we perform the joint DSE for batch-mode STFT-CNN on all the modeled
hardware architectures. As the baseline comparison and proof of concept, we
also evaluate Layer-by-Layer execution and basic DF optimization on the same
temporal-flattened workload. The results are summarized in Fig. 9, where the
best overall scheduling strategy given by ACCO, shows to be on average, 14.3%
faster and 24.2% more energy-efficient compared to the DF baseline. Compared
with the LBL baseline, this benefit further increases to 30.6% for latency and
73.3% for energy.

###  V-D Case Study 3: SotA Comparison with Baseline Toolchain

As introduced in Section II-C, ACCO’s baseline toolchain, DeFiNES [17], is an
advanced DF auto-scheduler with silicon verification. Therefore, to verify the
efficacy of ACCO’s upgraded DSE, this case study compares the Pareto-optimal
scheduling results between ACCO and DeFiNES.

We conduct experiments across three batch-mode workloads (STFT-CNN,
MobileNet-1.0, and ResNet) on TPU-Edge. Fig. 10 summarizes the results across
different workloads. For STFT-CNN and MobileNet-1.0, ACCO’s updated TE, LFE,
and DS strategies show step-by-step advances from DeFiNES’ optimums.
Considering of the best EDP, ACCO achieves 22% and 16.2% in latency and energy
reduction for the two workloads on average. Note that for MobileNet-1.0, the
trend is a bit scattered, showing that ACCO discovers new Pareto-optimal
corners untouched by DeFiNES before.

On the contrary, the outcome of ResNet’s DSE are almost identical across the
two toolchains, stemming from the large weight volume of ResNet. From
Layer-18, each single layer’s weights in ResNet exceeds the on-chip memory
capacity of the modeled hardware accelerators. Hence, even if fused together
by ACCO’s TE+LFE+DS strategies, loading these layers’ weights during depth-
first execution is always the critical bottleneck dominating energy and
latency efficiency.

Figure 10: The SotA comparison of Pareto-optimal scheduling results between
ACCO and DeFiNES [17] on TPU-Edge. Three batch-mode workloads are considered:
a) STFT-CNN, b) MobileNet-1.0, c) ResNet.

###  V-E Case Study 4: SotA Comparison for Real-time Execution

Finally, we benchmark ACCO against SotA published CNN scheduling approaches
for spatio-temporal real-time input updates in Table I. We explore real-time-
mode STFT-CNN and MobileNet-0.5 workloads, whose DNN Weights are small enough
for the target hardware’s on-chip GB.

Three SotA approaches are used for comparison. As specified in Table IV, DNNVM
[16] and DeFiNES [17] are designed for fully-spatial DNN optimization and
cannot resolve the time-dimension causal relationship between spatio-temporal
workloads.  On the contrary, the TCN [9] is a dedicated DNN for time-sequence
reasoning. Its dilated causal structure is a corner case of ACCO when fusing
all layers into one DF block, hence only spatially scheduled here.

During comparison, DNNVM and DeFiNES tune the inference execution based on
original ST-CNN input frames (Baseline mode, Table I), while TCN and ACCO
explore the equivalent computation that yields a single row of causal output
from the temporally-flattened input frame (Real-time mode, Table I).

From the results shown in Fig. 11, it is clear that ST-CNNs benefit much from
the causal transformation. Even though weight reuse is suppressed in the
causal form of the workload, the vast reduction in computation requirements
surpasses the benefits of plain DF computation reduction on the original
workload. Putting together both advantages, ACCO DSE makes STFT-CNN
22.9$\times$ faster with 51.5$\times$ less energy consumption. On
MobileNet-0.5, the efficiency gain is 15.1$\times$ and 23.2$\times$,
respectively. The significant efficiency boost compared to the spatially-
scheduled TCN approach (3.5$\times$ in energy and 2.4$\times$ in latency) on
MobileNet-0.5 further confirms ACCO DSE’s advantage in optimizing deep-and-
narrow ST-CNN workloads.

TABLE IV: SotA ST-CNN optimizer Comparison |  Optimization Target |  Causal Awareness |  Schedulable Dimension
---|---|---|---
DNNVM [16] | LAT | $\times$ | Spatial
DeFiNES [17] | LAT, ENE | $\times$ | Spatial
TCN [9] | - | $\checkmark$ | Spatial
ACCO (ours) | LAT, ENE, EDP | $\checkmark$ | Spatial+Temporal

##  VI Conclusion

This paper presents ACCO, an automated Causal CNN scheduling optimizer, which
explores more efficient ST-CNN execution by leveraging the computational reuse
across time steps and CNN sliding windows. It embeds a general causal
transformation method to automatically flatten ST-CNNs and identify the
previously-computed results. Meanwhile, it extends the SotA DF scheduling
toolchain to automatically optimize the transformed spatio-temporal workload
across one or multiple frames. In this way, for the causal-specific
optimization, ACCO reaches 8.4$\times$ better EDP compared to the fixed
dilated-causal conversion. For the DF-only optimization, ACCO pushes forward
the Pareto-optimal frontier by $\sim$20% compared to the SotA DF DSE
toolchain. For the joint optimization of ST-CNNs, the best solutions from ACCO
are 19$\times$ faster and 37$\times$ more energy-efficient than single spatial
DF schemes on average.

Figure 11: The SotA comparison of Real-Time mode overhead for STFT-CNN and
MobileNet-0.5. Four SotA research are considered: a) DNNVM [16] and b) DeFiNES
[26] for the original spatio-temporal input; c) TCN [9] and d) ACCO (this
work) for the transformed causal input. The target accelerator architectures
are Meta-Edge and TPU-Edge.

## References

  * [1] B. Yan et al., “Learning spatio-temporal transformer for visual tracking,” in ICCV, 2021.
  * [2] S. Kumawat et al., “Depthwise spatio-temporal STFT convolutional neural networks for human action recognition,” IEEE Trans. Pattern Anal., 2021.
  * [3] Y. Zhang et al., “Hello edge: Keyword spotting on microcontrollers,” arXiv, 2017.
  * [4] Q. Kong et al., “Cross-task learning for audio tagging, sound event detection and spatial localization: Dcase 2019 baseline systems,” arXiv, 2019.
  * [5] J. Cho et al., “Spatio-temporal representation of an electoencephalogram for emotion recognition using a three-dimensional convolutional neural network,” Sensors, 2020.
  * [6] A. Shoeibi et al., “An overview of deep learning techniques for epileptic seizures detection and prediction based on neuroimaging modalities: Methods, challenges, and future works,” Comput. Biol. Med., 2022.
  * [7] A. v. d. Oord et al., “Wavenet: A generative model for raw audio,” arXiv, 2016.
  * [8] M. Alwani et al., “Fused-layer cnn accelerators,” in MICRO, IEEE, 2016.
  * [9] C. Lea et al., “Temporal convolutional networks: A unified approach to action segmentation,” in Computer Vision–ECCV Workshops, 2016.
  * [10] M. Alwani, , et al., “Fused-layer CNN accelerators,” in MICRO, 2016.
  * [11] J. Lee et al., “A full hd 60 fps cnn super resolution processor with selective caching based layer fusion for mobile devices,” in VLSI, 2019.
  * [12] H. Mo et al., “A 12.1 TOPS/W Quantized Network Acceleration Processor With Effective-Weight-Based Convolution and Error-Compensation-Based Prediction,” IEEE JSSC, 2022.
  * [13] K. Goetschalckx and M. Verhelst, “DepFiN: A 12nm, 3.8TOPs depth-first CNN processor for high res. image processing,” in VLSI, 2021.
  * [14] C.-T. Huang et al., “ECNN: A Block-Based and Highly-Parallel CNN Accelerator for Edge Inference,” in MICRO, 2019.
  * [15] S.-C. Kao et al., “DNNFuser: Generative pre-trained transformer as a generalized mapper for layer fusion in dnn accelerators,” arXiv, 2022.
  * [16] Y. Xing et al., “DNNVM: End-to-end compiler leveraging heterogeneous optimizations on fpga-based cnn accelerators,” IEEE TCAD, 2019.
  * [17] L. Mei et al., “DeFiNES: Enabling fast exploration of the depth-first scheduling space for dnn accelerators through analytical modeling,” in HPCA, 2023.
  * [18] J. Lin et al., “MCUNetV2: Memory-Efficient Patch-based Inference for Tiny Deep Learning,” arXiv, 2021.
  * [19] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” arXiv, 2014.
  * [20] A. G. Howard et al., “Mobilenets: Efficient convolutional neural networks for mobile vision applications,” arXiv, 2017.
  * [21] K. He et al., “Deep residual learning for image recognition,” in CVPR, 2016.
  * [22] H. E. Sumbul et al., “System-level design and integration of a prototype ar/vr hardware featuring a custom low-power dnn accelerator chip in 7nm technology for codec avatars,” in IEEE CICC, 2022.
  * [23] A. Yazdanbakhsh et al., “An evaluation of edge tpu accelerators for convolutional neural networks,” arXiv, 2021.
  * [24] E. Talpes et al., “Compute solution for tesla’s full self-driving computer,” IEEE Micro, 2020.
  * [25] R. Balasubramonian et al., “Cacti 7: New tools for interconnect exploration in innovative off-chip memories,” ACM TACO, 2017.
  * [26] L. Mei et al., “ZigZag: Enlarging joint architecture-mapping design space exploration for dnn accelerators,” IEEE Trans. on Comp., 2021.