# Using the Abstract Computer Architecture Description Language to Model AI
Hardware Accelerators

Mika Markus Müller* Embedded Systems, Department of Computer Science
Eberhard Karls Universität Tübingen, Tübingen, Germany  Alexander Richard
Manfred Borst* Embedded Systems, Department of Computer Science
Eberhard Karls Universität Tübingen, Tübingen, Germany  Konstantin Lübeck*
Embedded Systems, Department of Computer Science
Eberhard Karls Universität Tübingen, Tübingen, Germany  Alexander Louis-
Ferdinand Jung  Embedded Systems, Department of Computer Science
Eberhard Karls Universität Tübingen, Tübingen, Germany  and Oliver Bringmann
Embedded Systems, Department of Computer Science
Eberhard Karls Universität Tübingen, Tübingen, Germany

##  1 Introduction

The recent advances in Artificial Intelligence (AI) have resulted in an
exponential increase in performance and energy demands for the inference of
Deep Neural Networks (DNN). To keep up with those increased demands,
specialized AI hardware accelerators are needed, which offer better
performance and energy-efficiency compared to CPUs and general-purpose GPUs
[1, 2, 3, 4]. However, evaluating and comparing different AI hardware
accelerator architectures is a time-consuming task that often relies on
simulators with poor simulation performance or data sheets with questionable
performance claims. The Abstract Computer Architecture Description Language
(ACADL) provides a concise modeling of arbitrary computer architectures along
with a timing semantic that allows for inferring performance characteristics
from modeled AI hardware accelerators.

In this paper, we present how to use ACADL to model AI hardware accelerators
on different abstraction levels and how to map DNN operators onto those models
to infer performance characteristics to speed-up accelerator selection and
design, hardware-aware Neural Architecture Search (NAS), and DNN/HW Co-Design
[5, 6, 7, 8].

This paper makes the following contributions:

  * •

An introduction to ACADL,

  * •

practical examples that demonstrate how to use ACADL to model AI hardware
accelerators,

  * •

an overview on how to map DNNs on to the AI hardware accelerators described in
ACADL,

  * •

and, an explanation of the timing simulation semantics to infer performance
metrics from DNN mappings.

##  2 Related Work

Several methods for modeling AI hardware accelerators and general computer
architectures for performance estimation have been proposed.

ScaleSim [9] presents a DNN accelerator simulation framework based on a coarse
accelerator template. This accelerator template is parameterizable using a set
of ten parameters which specify the number of multiply accumulate units, the
memory sizes, the data flow, etc. The authors conduct several experiments
showing the performance and energy estimations for a range of different DNNs
and hardware configurations.

Timeloop [10] introduces a domain-specific language for DNN accelerators,
focusing on the memory hierarchy and the supported data flows. They validate
their proposed approach by modeling three real-world accelerator architectures
and estimating their performance and power.

DNN-Chip Predictor [11] also proposes a domain-specific language which
expresses how a DNN layer is computed by a hardware accelerator using nested
loops and memory hierarchy. The authors validate their modeling and estimation
framework with an FPGA implementation.

SimPyler [12] provides a Python-based methodology for composing hardware
templates with embedded analytical models into complete accelerator platforms.
Using the TVM [13] compiler framework, the authors can transform and map DNN
operators onto an accelerator platform, which is then simulated as a Petri-Net
calling the analytical models to infer performance results.

HDPython [14] is a Python-based Hardware Description Language (HDL) which uses
Python as a source language which is then converted into VHDL. While HDPython
facilitates object-orientation and generic programming, it does not allow the
analysis of the described hardware on an abstraction level above the register-
transfer level.

IP-XACT [15] provides a standard for the integration and verification of
intellectual property (IP) in the context of System-on-Chip (SoC) designs. IP-
XACT enables the use of virtual prototypes for early design phases, including
software compilation and debugging, which allows for the integration of AI
hardware accelerator models.

While the works mentioned above either use register-transfer implementations,
parameterizable accelerator templates, or introduce a domain-specific
language, this paper presents a flexible modeling methodology for AI hardware
accelerators implemented in C++ with a Python front-end that enables modeling
at different operator abstraction levels for arbitrary computer architectures
without relying on proprietary software and complex tool flows.

##  3 Abstract Computer Architecture Description Language

Figure 1: Class diagram of the Abstract Computer Architecture Description
Language.

Computer Architectures are almost exclusively communicated using block
diagrams, where blocks describe how data is transformed and edges signify
dependencies and data flow between different blocks. However, those computer
architecture block diagrams are often ambiguous and therefore need textual
explanation to be understood, which forbids an automated analysis. The
Abstract Computer Architecture Description Language (ACADL) [16] solves this
problem by formalizing computer architecture block diagrams by providing a set
of basic building blocks and their relations together with a concise modeling
and timing semantic, enabling both human and machine-readable representations,
allowing higher-level system descriptions.

Using Prabhat’s and Dutt’s taxonomy [17] ACADL can be classified as a
behavioral architecture description language (ADL). ACADL ignores register-
transfer and gate-level details and focuses on the timing semantics of
operations on the scalar, tensor, and fused-tensor abstraction level using an
object-oriented paradigm.

ACADL is an instruction-centric ADL, which means that any architectural state
change is triggered by an instruction being processed. ACADL consists of a
virtual base class, twelve classes, and two interfaces as presented in the UML
[18] class diagram in Fig. 1. ACADL classes are instantiated into objects when
building computer architecture models, which is presented in section 4.

The following section provides a brief overview of all ACADL elements:

bool, int, str, List, Set, Union, Tuple, Any, Callable, Enum, … are the
primitive types of ACADL based on the Python 3.10 typing system [19].

latency describes a time delta in clock cycles. It can be specified as an
integer value or a string containing a function that is evaluated during the
performance estimation.

Association describes the relation between two or more instantiated objects of
classes that allows one object (caller) to cause another one to perform an
action (callee), while :call() signifies the callee’s function that is called
by the caller.

Inheritance allows a class to base its implementation and attributes upon
another class (base class).

Composition defines a relationship between instantiated objects of classes
that implies that one or more objects are part of a single composite object.

ACADLObject is the virtual base class for every computer architecture module
modeled in ACADL. It only has the attribute name, the unique identifier for
each object.

Data represents any data stored in memories, registers, and immediate values
of instructions. size is the data size in bits. payload is the data itself,
which is used for the functional simulation.

Instruction has several attributes describing which registers (read_registers,
write_registers) and memory addresses (read_addresses, write_addresses) and
immediate values (immediates) are accessed when it is executed. operation is
the instruction’s mnemonic, while function contains how data is manipulated.
execute() calls function when the instruction is processed by a
FunctionalUnit. Furthermore, an instruction is not limited to fine-grained
operations such as addition or multiplication. An instruction can also carry
out complex operations like matrix-matrix multiplication or Fourier
transformations. This enables modeling at different abstraction levels.

PipelineStage is responsible for forwarding instructions inside a computer
architecture. receive() is called by forward() of another PipelineStage which
forwards an instruction between two PipelineStages. An Instruction can only be
forwarded if the receiving PipelineStage is ready(). The amount of clock
cycles an Instruction resides inside a PipelineStage before it is forwarded is
indicated by latency.

RegisterFile contains registers that maps the unique register name to a value.
data_width is the size of each register in bits, while read() and write()
provide access to the stored values.

FunctionalUnit executes an Instruction that is passed to process() and changes
the architectural state by changing register contents using read() and write()
of RegisterFiles. A RegisterFile can be read-only, write-only, or readable and
writable depending on the :read()/:write() associations connecting
FunctionalUnits and RegisterFiles. FunctionalUnits can only process
Instructions whose operation is in to_process and if the FunctionalUnit has
read/write access to the read_registers and write_registers. Processing a
supported Instruction takes latency clock cycles after all data dependencies
from previous Instructions are resolved.

ExecuteStage inherits from PipelineStage and overrides receive() and
additionally contains FunctionalUnits. When an ExecuteStage receives an
Instruction, it checks all its contained FunctionalUnits if one of them
supports processing the Instruction. The check involves if operation is in
to_process and if the read_registers and write_registers are accessible by the
FunctionalUnit. When a contained FunctionalUnit supports the Instruction, the
ExecuteStage passes the Instruction to process() and the ExecuteStage’s
latency is not accumulated.

DataStorage is the virtual base class for all data storages. data_width
describes the bit-length of one data word. max_concurrent_requests is the
maximum amount of read and write requests that can be handled at the same
time, while read_write_ports describes how many MemoryAccessUnits can be
connected to the DataStorage. port_width is the amount of data words that can
be accessed during a single memory transaction. A $\texttt{port\\_width}>1$
allows for reading or writing several data words at once. data maps a memory
address to a data word.

MemoryInterface adds read_latency, write_latency, and address_ranges to
DataStorage which describe how many clock cycles a read or write transaction
takes when read() or write() are called and which addresses are associated
with a memory.

DRAM and SRAM override read_latency and write_latency with stateful functions
for accurate memory timing simulation. Additionally, DRAM contains the
attributes bank_address_ranges, t_RCD, t_RP, and t_RAS which are used by the
latency functions.

CacheInterface adds write_allocate, write_back, miss_latency, hit_latency,
cache_line_size, and replacement_policy to DataStorage which are common
attributes of a cache.

SetAssociativeCache extends CacheInterface and adds sets and ways.

MemoryAccessUnit inherits from FunctionalUnit and overrides process() to
access RegisterFiles and objects that inherit from DataStorage.

InstructionMemoryAccessUnit inherits from MemoryAccessUnit and adds fetch(),
which reads length Instructions starting at address from a DataStorage that
contains instructions, which we call instruction memory for the remainder of
this paper.

InstructionFetchStage inherits from ExecuteStage and overrides forward(),
which forwards an instruction residing in the issue_buffer. It is possible to
forward multiple Instructions in the same clock cycle. issue_buffer_size
describes how many instructions fit into the issue_buffer, and thereby marks
the maximum number of instructions that can be issued in a single clock cycle.
fetch_instructions() is called in each clock cycle as long as the issue_buffer
is not full.

Using those classes and their dependencies, a wide variety of computer
architectures can be modeled using ACADL. ACADL’s object-oriented design
facilitates expendability and composition. We implemented ACADL in C++ with a
Python front-end and a functional instruction set simulation, which enables a
seamless interaction with popular AI frameworks and tool flows such as PyTorch
[20] and TVM [13]. We chose Python as a front-end language because, according
to the "TIOBE Index for January 2024" [21] Python is the most popular
programming language, and according to the "Stack Overflow 2023 Developer
Survey" [22] is placed third as the most commonly used programming language
among developers. This combination of formalization and practical usability
empowers researchers and engineers to accurately describe and analyze AI
hardware accelerators and make informed decisions.

##  4 Modeling Examples

To model a computer architecture using ACADL, objects of the twelve classes
must be instantiated and connected to each other according to the class
diagram depicted in Fig. 1. For the remainder of this paper, we call the UML
object diagram describing a computer architecture the architecture graph (AG).
In the following sections, modeling examples for different AI hardware
accelerator architectures are shown for different abstraction levels, starting
at the scalar operations level and ending with fused-tensor operations.

###  4.1 One MAC Accelerator

As an introductory example, we present the One MAC Accelerator (OMA) which is
modeled on the scalar operations level. It is designed to accelerate the
execution of DNN models using the built-in multiply-accumulate (MAC)
operation. The OMA is composed out of a single data memory, a data cache, a
register file, and an execution unit responsible for data manipulation and
memory access. Furthermore, the OMA is only capable of processing one
operation at a time in its execution unit. Fig. 2 shows the block diagram of
the One MAC Accelerator.

Figure 2: Block diagram of the One MAC Accelerator (OMA).

From the OMA block diagram, we can construct the AG in Fig. 3. All hardware
elements from the block diagram can be found in the AG. Additionally, the AG
contains a RegisterFile for the program counter register pc and the fetch
stage is split into an InstructionFetchStage imau0 and an
InstructionMemoryAccessUnit ifs0 while the arithmetic logic unit is
represented by the FunctionalUnit fu0 and the MemoryAccessUnit mau0.

Figure 3: Architecture graph of the One MAC Accelerator (OMA).

We can use the ACADL Python front-end to implement the AG of a computer
architecture.

Listing 1 shows the Python implementation of the OMA. Each computer
architecture implementation is encapsulated in a Python function decorated
with @generate, which implicitly checks the validity of all edges when the
function is called. Afterward, the ACADL built-in function create_ag() is
called, which instantiates the AG of the modeled architecture. The
instantiation of the hardware elements as ACADL objects is straightforward. To
connect the instantiated objects, the class ACADLEdge is used, which takes the
references of objects and the edge type.

To execute operations on the OMA, an operator implementation in the form of
ACADL instructions is needed. Listing 5 presents an example of ACADL
instructions implementing a general matrix multiplication on the OMA
architecture, which is detailed in section 5.

⬇

1from acadl import *

2

3@generate

4def generate_architecture()

5 # instruction fetch

6 imem0 = SRAM(name="imem0", ...)

7 imau0 = InstructionMemoryAccessUnit(

8 name="imau0", ...)

9 pcrf0 = RegisterFile(name="pcrf0", ...)

10 ifs0 = InstructionFetchStage(

11 name="ifs0", ...)

12 # instruction processing

13 ds0 = PipelineStage(name="ds0", ...)

14 ex0 = ExecuteStage(name="ex", ...)

15 fu0 = FunctionalUnit(

16 name="fu0",

17 to_process={"mov", "addi", ...},

18 latency=latency_t(1)

19 )

20 mau0 = MemoryAccessUnit(

21 name="mau0",

22 to_process={"load", "store"},

23 latency=latency_t(1)

24 )

25 rf0 = RegisterFile(

26 name="rf0",

27 data_width=32,

28 registers={"r0": Data(32, 0), ...}

29 )

30 dmem0 = SRAM(name="dmem0", ...)

31 dcache0 = SetAssociativeCache(

32 name="dcache0", ...

33 )

34

35 # edges

36 ACADLEdge(imem0, imau0, READ_DATA)

37 ACADLEdge(pcrf0, imau0, READ_DATA)

38 ACADLEdge(imau0, pcrf0, WRITE_DATA)

39 ACADLEdge(ifs0, imau0, CONTAINS)

40 ACADLEdge(ifs0, ds0, FORWARD)

41 ACADLEdge(ds0, ex0, FORWARD)

42 ACADLEdge(ex0, fu0, CONTAINS)

43 ACADLEdge(fu0, rf0, WRITE_DATA)

44 ACADLEdge(rf0, fu0, READ_DATA)

45 ACADLEdge(ex0, mau0, CONTAINS)

46 ACADLEdge(mau0, rf0, WRITE_DATA)

47 ACADLEdge(rf0, mau0, READ_DATA)

48 ACADLEdge(mau0, dcache0, WRITE_DATA)

49 ACADLEdge(dcache0, mau0, READ_DATA)

50 ACADLEdge(dcache0, dmem0, WRITE_DATA)

51 ACADLEdge(dmem0, dcache0, READ_DATA)

52

53def __name__ == "__main__":

54 generate_architecture()

55 ag = create_ag()

Listing 1: ACADL Python front-end implementation of the One MAC Accelerator
(OMA).

###  4.2 Parameterizable Systolic Array

While modeling the OMA is straightforward, ACADL also allows modeling more
complex and flexible architectures whose structure depends on specific
parameters. In the following, we demonstrate this capability by modeling a
parameterizable systolic array using ACADL.

Systolic arrays are the go-to architecture for the accelerated and efficient
executions of general matrix multiplication (GeMM) operations, which are
heavily employed by DNNs. Fig. 4 shows the block diagram of the modeled
systolic array architecture. It consists of a 2D grid structure of processing
elements (PEs) responsible for performing scalar operations. Each PE
communicates only with its adjacent neighbors in such a manner that data is
passed only vertically down and horizontally right to the next PE. Data from
the data memory can be loaded only into the first row and column of PEs and
then flows through the systolic array. This is done by load units. The same
applies to the last row and column of PEs to store results into the data
memory by using store units.

Figure 4: Block diagram of the systolic array architecture (excluding
instruction memory and fetch unit).

As already mentioned, the systolic array, more specifically the size of the PE
grid, is parameterizable. This means that when creating the architecture, the
parameters rows and columns are passed such that based on those parameters,
the corresponding AG of the systolic array is instantiated. However, to
accomplish this, statically instantiating all of the ACADL objects is not
suitable anymore due to the parameter dependent amount of ACADL objects and
edges. Therefore, we introduce templates which represent parts of the overall
architecture that can be reused. This means instead of instantiating all ACADL
objects and edges individually, we instantiate templates which create all the
objects and edges belonging to the corresponding part of the architecture
automatically. Listing 2 shows the implementation of the template representing
a PE. Templates are implemented as Python classes in which all objects and
edges belonging to the template are instantiated. Fig. 5 shows the
corresponding AG of the PE template. Templates allow us to model computer
architectures using less code, facilitate the introduction of hierarchy, and
increase reusability.

Figure 5: Architecture graph of the template for a PE of the parameterizable
systolic array.

Every PE consists of a RegisterFile, an ExecuteStage and a FunctionalUnit,
including the edges connecting these objects. One can also observe some edges
without source or target in Listing 2, we call these kinds of edges dangling
edges. Their purpose is to provide an interface for ACADL objects within a
template to ACADL objects outside the template or inside other template
instances. For example, each PE is connected with its adjacent neighbor and
therefore edges between them are needed later on. For that reason, dangling
edges keep the implementation more understandable and readable. When a
dangling edge is not connected later on, no edge will be instantiated. To
implement dangling edges, we use the class ACADLDanglingEdge.

⬇

1class ProcessingElement:

2 def __init__(self, regs, row, col):

3 # acadl objects

4 self.ex = ExecuteStage(

5 name=f"ex[{row}][{col}]", ...

6 )

7 self.fu = FunctionalUnit(

8 name=f"fu[{row}][{col}]", ...

9 )

10 self.rf = RegisterFile(

11 name=f"rf[{row}][{col}]", ...

12 )

13

14 # edges

15 ACADLEdge(self.ex, self.fu, CONTAINS)

16 ACADLEdge(self.rf, self.fu, READ_DATA)

17 ACADLEdge(self.fu, self.rf, WRITE_DATA)

18

19 # dangling edges

20 self.ex_ingoing_forward = DanglingEdge(

21 edge_type=FORWARD, target=self.ex

22 )

23 self.rf_ingoing_write = DanglingEdge(

24 edge_type=WRITE_DATA, target=self.rf

25 )

26 self.rf_outgoing_read = DanglingEdge(

27 edge_type=READ_DATA, source=self.rf

28 )

29 self.fu_outgoing_write = DanglingEdge(

30 edge_type=WRITE_DATA, source=self.fu

31 )

Listing 2: ACADL Python front-end implementation of the parameterizable
systolic array PE template.

Listing 2 shows an example of how dangling edges are instantiated. One can
either specify the source or the target of the edge, depending on the
necessary edge later on, including the type of the edge. Later, dangling edges
can be connected with each other by using the ACADL Python front-end function
connect_dangling_edge(), whose output is an instance of ACADLEdge. It is also
possible to pass a dangling edge and an ACADL object to this function, which
might be helpful during the generation of the whole AG to maintain better
readability or to avoid unnecessary instantiations of dangling edges outside a
template. In either case, it is checked wether or not the resulting ACADL edge
is valid with respect to the ACADL class diagram.

⬇

1@generate

2def generate_architecture(rows, columns)

3 ...

4 # instantiate array that holds all PEs

5 pes = [

6 [None]*columns for i in range(rows)

7 ]

8 ...

9 # instantiate and connect PEs

10 for row in range(rows):

11 for col in range(columns):

12 ...

13 pes[row][col]

14 = ProcessingElement(

15 regs=4, row=row, col=col)

16 ...

17 connect_dangling_edge(

18 pes[row-1][col]

19 .fu_outgoing_write,

20 pes[row][col]

21 .rf_ingoing_write

22 )

23 ...

24 ...

25 ...

Listing 3: ACADL Python front-end implementation of the parameterizable
systolic array using templates and dangling edges.

With the help of templates and dangling edges, we can now generate the AG of
the parameterizable systolic array in ACADL efficiently. Listing 3 shows how
PE templates are instantiated and how conntect_dangling_edge() is used to
connect instantiated templates. In addition to the template for the PE which
has been presented in detail, we also implemented templates for the load
units, store units and the fetch unit. The load and store units consist of an
ExecuteStage and a MemoryAccessUnit which supports the load and store
operations respectively. The fetch unit consists of the same objects and edges
as already described in the OMA, including the instruction memory. Note that
the DRAM object is not instantiated in any template. This will be done when
generating the whole AG. It would be unnecessary to create a template for just
one single ACADL object. In that case, it would also be unnecessary to
instantiate a dangling edge, i.e. pass the DRAM object directly into the
connect_dangling_edge() function.

Finally, the whole AG of the systolic array is composed by instantiating and
connecting the templates and dangling edges. The parameters rows and columns
can be set arbitrarily such that we can instantiate systolic array
architecture of any desired shape.

###  4.3 $\ddot{\Gamma}$ [gœna]

Figure 6: Block diagram of the $\ddot{\Gamma}$ architecture, where the dashed
lines enclose architecture templates.

In contrast to the OMA and the parameterizable systolic array which represent
AI hardware accelerators modeled on the scalar operations level, the General
Operationally Extendable Neural Network Accelerator ($\ddot{\Gamma}$
[gœna]111While $\Gamma$ (Gamma) represents the generalizability, the second
derivative of the position with respect to time is the acceleration:
$\frac{d^{2}x}{dt^{2}}=\ddot{x}$) is modeled on the fused tensor operations
level. Fig. 6 shows the block diagram of the $\ddot{\Gamma}$ architecture. It
is composed out of templates (enclosed in dashed lines) which contain a
load/store unit, a compute unit, and a scratchpad. The compute units carry out
fused tensor operations such as computing tiles of a general matrix
multiplication (GeMM) with an optional activation function applied to the
outputs or pooling while the matrix rows and columns are stored in vector
registers. The scratchpad is an SRAM used to store partial results that can be
shared with adjacent compute units. The load/store units move input and output
data of operations between the DRAM data memory and the compute unit or the
scratchpad. Instructions intended for different hardware components are issued
in parallel and executed out-of-order, which facilitates an efficient and
parallel computation of AI workloads.

⬇

1load [0x3000] => r[0].0

2load [0x3030] => r[0].1

3...

4load [0x3080] => r[0].8

5load [0x4000] => r[0].9

6...

7load [0x4080] => r[0].15

8gemm r[0].0, r[0].9, 1 => r[0].16 ; 1: ReLU

9store r[0].16 => [0x5000]

10...

11store r[0].23 => [0x5080]

Listing 4: $\ddot{\Gamma}$ ACADL instruction for an 8$\times$8 matrix
multiplication where the input matrices are loaded from a scratchpad into the
the compute unit vector registers and the output matrix of the gemm
instruction is stored in the scratchpad (the 1 parameter of the gemm
instruction enables the ReLU activation function applied to the output
matrix).

Fig. 7 presents the architecture graph of $\ddot{\Gamma}$ using a template for
the load/store, compute, and scratchpad complex. the to_process attribute of
the matMulFu and matAddFu contains the fused tensor operations that are
carried out by those FunctionalUnits. E.g. the gemm operation calculates the
matrix multiplication of two 8$\times$8 matrices with an optional activation
such as rectified linear unit (ReLU) function applied to the output matrix
using 16bit integer elements stored in 128bit wide vector registers. Listing 4
shows an example for an 8$\times$8 matrix multiplication where the input
matrices are loaded from the scratchpad into the compute unit vector registers
and the result matrix from the gemm instruction is stored in the scratchpad.

Figure 7: Architecture graph of the $\ddot{\Gamma}$ architecture using a
template for a compute and scratchpad pair.

Those three AI hardware accelerator modeling examples show the versatility of
ACADL. Using templates and dangling edges in the Python front-end allows us to
model computer architectures in an object-oriented fashion, while modeling at
different abstraction levels enables fast prototyping and iterative refinement
with explicit hardware parallelism.

##  5 Operator Mapping

To infer performance characteristics for an AI hardware accelerator modeled in
ACADL, a DNN operation schedule is needed. As mentioned above, ACADL allows us
to model computer architectures on different abstraction levels, from scalar
operations up to fused tensor operations. We propose the use of Apache TVM
[13] and the Universal Modular Accelerator Interface (UMA) [23] to map
operations from a DNN onto the accelerator model. "Apache TVM is an open-
source machine learning compiler framework for CPUs, GPUs, and machine
learning accelerators. […]" [24] that facilitates code generation to offload
typical machine learning workloads onto specialized hardware for accelerated
execution.

This section gives an overview of how a tiled general matrix multiplication
(GeMM) is implemented on the OMA ACADL model and how we expose this tiled GeMM
operator to TVM using the UMA interface.

The OMA ACADL model is modeled on the scalar operations level. This means we
need to implement the tiled GeMM operation with scalar operations represented
by ACADL instructions. Listing 5 constitutes a naive example implementation of
GeMM as a list of OMA ACADL instructions. Most notable among these
instructions is the built-in multiply-and-accumulate (mac) instruction, which
multiplies the contents of two input registers and adds them onto an
accumulator register. Regarding caching and locality, we want to offer various
ways to compute the GeMM operation, e.g. via employing tiled matrix
multiplication. This method utilizes a divide-and-conquer approach for matrix
multiplication, which is based on partitioning the input matrices into
submatrices called tiles, which are then multiplied and added:

$\displaystyle\begin{bmatrix}A_{00}&A_{01}\\\
A_{10}&A_{11}\end{bmatrix}\begin{bmatrix}B_{00}&B_{01}\\\
B_{10}&B_{11}\end{bmatrix}$ $\displaystyle=\begin{bmatrix}C_{00}&C_{01}\\\
C_{10}&C_{11}\end{bmatrix}$ (1)
$\displaystyle\text{where}\;\;A_{00}B_{00}+A_{01}B_{10}$
$\displaystyle=C_{00}$ (2) $\displaystyle A_{00}B_{01}+A_{01}B_{11}$
$\displaystyle=C_{01}$ (3) $\displaystyle A_{10}B_{00}+A_{11}B_{10}$
$\displaystyle=C_{10}$ (4) $\displaystyle A_{10}B_{01}+A_{11}B_{11}$
$\displaystyle=C_{11}.$ (5)

The above equation set details the tiled computation of the multiplication of
matrices $A$ and $B$, divided into four tiles $A_{ij}$ and $B_{ij}$ as shown
in equation (1). Equations (2) through (5) detail which input tiles must be
multiplied to obtain which output tile. Fig. 8 visualizes the computation of a
single output value of matrix $C$ using a tiled GeMM.

There are various execution orders in which a tiled GeMM can be computed,
which has a significant impact on the execution time depending on the target
computer architecture [25]. For example, first computing $A_{00}B_{00}$ and
$A_{00}B_{01}$ before moving on in a similar way, we only have to load the
elements of $A_{00}$ into the target architecture’s cache once for both sub-
computations.

In the case of the OMA, we offer a mapping for a parameterizable
implementation of the tiled GeMM. To be able to use this tiled GeMM mapping on
the OMA accelerator, we propose the usage of the Universal Accelerator
Interface (UMA) of TVM. With UMA, accelerator architectures can be easily
integrated into the TVM DNN compilation flow by registering an interface
function which implements a DNN operator such as GeMM. This GeMM interface
function expects the input matrices along with their shapes, as well as the
chosen tile size as arguments. To accelerate, e.g. a convolution operation,
one needs to define the necessary input data transformations and computation
schedules such that TVM can match and transform the convolution operations and
insert the calls to the accelerator interface function into a C program.

⬇

1mov z0 => r8

2load [r9] => r6

3load [r10] => r7

4mac r6, r7 => r8

5addi r3, #-1 => r3

6beqi r3, z0, #16 => pc

7add r9, r14 => r9

8add r10, r14 => r10

9jumpi #-28

10beqi r4, z0, #64 => pc

11store r8 => [r11]

12mov r1 => r3

13beqi r4, z0, #20 => pc

14mov r12 => r9

15add r10, r14 => r10

16add r11, r14 => r11

17jumpi #-64

18addi r5, #-1 => r5

19mov r2 => r4

20beqi r5, z0, #24 => pc

21add r9, r14 => r9

22mov r13 => r10

23add r11, r14 => r11

24mov r9 => r12

25jumpi #-96

Listing 5: OMA ACADL instruction list example showing an implementation of
GeMM. Registers r0 , r1 and r2 hold dimensions $m$, $n$ and $l$ of the input
matrices $A$ ($m\times n$) and $B$ ($n\times l$). These indices are
decremented until they reach zero, and then possibly reset in case of $n$ and
$l$. The reset values for $n$ and $l$ are held in registers r3 and r4
respectively. Registers r9 and r10 hold the current input matrix element
addresses, while r11 holds the currently computed output matrix element’s
address. The initial input matrix addresses, intended as reset values for r10
and r11, are held in registers r12 and r13. Figure 8: Illustration of tiled
GeMM showing how single output matrix elements are computed. Purple tiles are
inputs required to compute the red output tile, while the green row of input
elements is processed to obtain the green output element. [25]

In the case of an AI hardware accelerator modeled in ACADL such as the OMA,
the interface function for GeMM oma_tiled_gemm(…) may generate ACADL
instructions as presented in Listing 5 according to the arguments passed, and
then runs a functional and optional timing simulation to validate the DNN
operator mapping and infer performance results.

##  6 Timing Simulation Semantics

Section 3 already gives a brief overview of the timing semantics of ACADL,
this section provides a detailed description of the ACADL timing simulation
semantics. These semantics have been implemented in [16] using an
Architectural Instruction Dependency Graph (AIDG) for fast performance
estimation of DNN operators mapped onto the systolic array architecture
introduced in section 4, an Eyeriss v1 [26] derived accelerator, and a
Plasticine derived architecture [27] using a fixed point analysis of
consecutive loop iterations.

To infer performance characteristics, an AG and ACADL instructions for a
modeled computer architecture are necessary. When initializing a timing
simulation, each ACADL object in the AG which has the latency attribute is
initialized with an integer variable t:=0 representing a latency counter in
clock cycles and a boolean variable ready:=True indicating the readiness of a
hardware module. The overall simulation is initialized with an integer
variable T:=0 representing the simulation time. We visualize the behavior of
selected ACADL classes using state diagrams [28]. Nodes in a state diagram
represent different states, while edges signify a state transition. The edge
label contains the condition under which a state transition occurs (before /)
and the actions triggered by a state transition (after /). All presented state
transitions in this paper can only occur at the end of a clock cycle when T is
incremented.

At T==0 the InstructionFetchStage starts fetching instructions from the
instruction memory through its contained InstructionMemoryAccessUnit. The
number of instructions fetched is equal to the port_width of the instruction
memory. The InstructionFetchStage continuously fetches instructions and stalls
when the issue buffer has no space left for port_with instructions. After the
instructions have been loaded from memory, they reside in the issue buffer and
are forwarded to connected and ready PipelineStages. Multiple instructions can
be forwarded out-of-order at the same time, which facilitates the simulation
of parallel computer architectures. Fig. 9 shows the state diagram of the
InstructionFetchStage.

fetchstall$\bigvee_{\texttt{ps}}$
ps.ready()/ps.forward(),insts:=insts-1issue_buffer_has_space =
insts+imem.port_width<=
issue_buffer_sizeimau.ready()$\wedge$!issue_buffer_has_space/insts:=insts+imem.port_widthimau.ready()$\wedge$issue_buffer_has_space/insts:=insts+imem.port_widthpt$\bigvee_{\texttt{ps}}$
ps.ready()/ps.forward(),insts:=insts-1ptimau.ready()$\wedge$issue_buffer_has_space/insts:=insts+imem.port_widthpt
Figure 9: State diagram of the ACADL InstructionFetchStage class where imau is
the contained InstructionMemoryAccessUnit object, imem is the instruction
memory object, ps stands for any connected PipelineStage, and insts is the
number of instructions residing in the issue buffer. The double arrow
signifies that multiple instructions can be forwarded out-of-order to
PipelineStages in the same clock cycle.
idlebufferprocessstallpt:receive()$\wedge$ no fu
found/t:=latency,ready:=Falset==0$\wedge$ps.ready()/:forward(ps),ready:=Truept:receive()$\wedge$fu
found/fu.process(),ready:=Falsefu.ready()/ready:=Trueptt==0$\wedge$!ps.ready()/ptps.ready()/:forward(ps),ready:=Truet!=0/t:=t-1!fu.ready()/
Figure 10: State diagram of the ACADL ExecuteStage class, where fu represents
any of the contained FunctionalUnits, and ps represents any of the connected
PipelineStages.

When an ExecuteStage receives an instruction, it is checked if any of the
contained FunctionalUnits can process it. If a FunctionalUnit is found which
supports the instruction, the ExecuteStage sends the instructions to the
FunctionalUnit and waits until the processing is finished. If no
FunctionalUnit is found, the instruction is buffered for latency cycles and
afterward forwarded to a ready and connected PipelineStage. While buffering an
instruction or waiting on a FunctionalUnit processing, the ExecuteStage is not
ready and cannot receive new instructions, which facilitates the simulation of
structural hazards. The behavior of a PipelineStage is identical to the
behavior of an ExecuteStage without any contained FunctionalUnits. Fig. 10
presents the state diagram for the ExecuteStage class.

When a FunctionalUnit or MemoryAccessUnit receives an instruction, it becomes
unready. Before processing an instruction in latency clock cycles, it is
checked if all previous in-order instructions modifying the accessed registers
and memory addresses are finished. This is facilitated by a global hash map
which contains the last user for each register and memory address and ensures
correct simulation of data dependencies. Fig 11 visualizes the behavior of the
MemoryAccessUnit and FunctionalUnit classes in a state diagram.

idleprocess:process()/t:=latency,ready:=Falset==0/ready:=Trueptall
previousdata users have finished/t:=t-1,update last data users Figure 11:
State diagram of the ACADL FunctionalUnit and MemoryAccessUnit classes.

Classes inheriting from the virtual DataStorage class support up to
max_concurrent_requests requests at the same time. Each request slot has its
own t and ready variables. When read() or write() is called, it is checked if
any request slot is ready. If no request slot is ready, the access is buffered
in a FIFO queue and is assigned to the next request slot that becomes ready.
For classes inheriting from MemoryInterface Fig. 12 shows the state diagram.
When data is read from or written to an address, the latency counter t is
initialized with the respective latency value, which is either static or can
be provided by a memory simulator such as DRAMsim3 [29].

idlereadwrite:read()/t:=read_latency,ready:=Falseptt==0/ready:=Truet!=0/t:=t-1:write()/t:=write_latency,ready:=Falset==0/ready:=Truet!=0/t:=t-1
Figure 12: State diagram of the ACADL MemoryInterface request slot.

The timing semantics for classes inheriting from CacheInterface is very
similar to classes inheriting from MemoryInterface. Each request slot has its
own set of variables and requests are processed in a FIFO fashion. In addition
to classes inheriting from MemoryInterface it is checked if an accessed
address resides in the cache, which is facilitated by using a cache simulator
such as pycachesim [30]. When a miss occurs, t is set to the miss_latency.
After miss_latency clock cycles have passed, the cache simulator is updated
and t is set to the hit_latency and the request slot becomes ready again after
miss_latency clock cycles have passed. Fig. 13 details the behavior of a
CacheInterface request slot.

idle read miss read hit write miss write hit :read()$\wedge$ address not in
cache/t:=miss_latency,ready:=Falseptt!=0/t:=t-1ptt==0/t:=hit_latency,:update_cache()ptt!=0/t:=t-1t==0/ready:=True
:write()$\wedge$ address no in
cache/t:=miss_latency,ready:=Falseptt==0/t:=hit_latency,:update_cache()ptt!=0/t:=t-1ptt!=0/t:=t-1ptt==0/ready:=True:read()$\wedge$
address in cache/t:=hit_latency,ready:=False:write()$\wedge$ address in
cache/t:=hit_latency,ready:=False Figure 13: State diagram of the ACADL
CacheInterface request slot.

The above ACADL timing semantics have been implemented in [16] using an
Architectural Instruction Dependency Graph (AIDG) which enables fast
performance estimation of DNN operators.

##  7 Conclusion

This paper presented how ACADL can be used to model AI hardware accelerators
and outlines how DNN operators can be mapped to these modeled computer
architectures using TVM, along with an introduction to the timing simulation
semantics of ACADL. This allows researchers and engineers to quickly evaluate
AI hardware accelerator designs on different abstraction levels, from scalar
operations up to fused tensor operations. Additionally, the timing simulation
can be used in the optimization loop of hardware-aware NAS and DNN/HW Co-
Design to find close to optimal design points.

##  8 Acknowledgement

This work has been funded by the German Federal Ministry of Education and
Research (BMBF) under grant number 16ES0876 (GENIAL!).

## Literature

  * [1] S. Chakradhar, M. Sankaradas, V. Jakkula, and S. Cadambi, “A Dynamically Configurable Coprocessor for Convolutional Neural Networks,” in _Proceedings of the 37th annual international symposium on Computer architecture_ , 2010, pp. 247–257.
  * [2] E. Nurvitadhi, G. Venkatesh, J. Sim, D. Marr, R. Huang, J. Ong Gee Hock, Y. T. Liew, K. Srivatsan, D. Moss, S. Subhaschandra _et al._ , “Can FPGAs beat GPUs in Accelerating Next-Generation Deep Neural Networks?” in _Proceedings of the 2017 ACM/SIGDA international symposium on field-programmable gate arrays_ , 2017, pp. 5–14.
  * [3] K. Lübeck and O. Bringmann, “A Heterogeneous and Reconfigurable Embedded Architecture for Energy-Efficient Execution of Convolutional Neural Networks,” in _Architecture of Computing Systems–ARCS 2019: 32nd International Conference, Copenhagen, Denmark, May 20–23, 2019, Proceedings 32_. Springer, 2019, pp. 267–280.
  * [4] J. Siegel. (2023) With a systems approach to chips, Microsoft aims to tailor everything ‘from silicon to service’ to meet AI demand. [Online]. Available: https://news.microsoft.com/source/features/ai/in-house-chips-silicon-to-service-to-meet-ai-demand/
  * [5] M. S. Abdelfattah, L. Dudziak, T. Chau, R. Lee, H. Kim, and N. D. Lane, “Best of Both Worlds: AutoML Codesign of a CNN and Its Hardware Accelerator,” in _Proceedings of the 57th ACM/EDAC/IEEE Design Automation Conference_ , ser. DAC ’20. IEEE Press, 2020.
  * [6] W. Jiang, L. Yang, E. H.-M. Sha, Q. Zhuge, S. Gu, S. Dasgupta, Y. Shi, and J. Hu, “Hardware/Software Co-Exploration of Neural Architectures,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , vol. 39, no. 12, p. 4805–4815, Dec. 2020.
  * [7] Y. Zhou, X. Dong, B. Akin, M. Tan, D. Peng, T. Meng, A. Yazdanbakhsh, D. Huang, R. Narayanaswami, and J. Laudon, “Rethinking Co-design of Neural Architectures and Hardware Accelerators,” 2021.
  * [8] C. Gerum, A. Frischknecht, T. Hald, P. B. Palomero, K. Lübeck, and O. Bringmann, “Hardware Accelerator and Neural Network Co-Optimization for Ultra-Low-Power Audio Processing Devices,” in _2022 25th Euromicro Conference on Digital System Design (DSD)_. IEEE, Aug. 2022.
  * [9] A. Samajdar, Y. Zhu, P. Whatmough, M. Mattina, and T. Krishna, “SCALE-Sim: Systolic CNN Accelerator Simulator,” 2019.
  * [10] A. Parashar, P. Raina, Y. S. Shao, Y.-H. Chen, V. A. Ying, A. Mukkara, R. Venkatesan, B. Khailany, S. W. Keckler, and J. Emer, “Timeloop: A Systematic Approach to DNN Accelerator Evaluation,” in _2019 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS)_. IEEE, Mar. 2019\.
  * [11] Y. Zhao, C. Li, Y. Wang, P. Xu, Y. Zhang, and Y. Lin, “DNN-Chip Predictor: An Analytical Performance Predictor for DNN Accelerators with Various Dataflows and Hardware Architectures,” in _ICASSP 2020 \- 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, May 2020.
  * [12] Y. Braatz, D. S. Rieber, T. Soliman, and O. Bringmann, “SimPyler: A Compiler-Based Simulation Framework for Machine Learning Accelerators,” in _2023 IEEE 34th International Conference on Application-specific Systems, Architectures and Processors (ASAP)_. IEEE, Jul. 2023.
  * [13] T. Chen, T. Moreau, Z. Jiang, H. Shen, E. Q. Yan, L. Wang, Y. Hu, L. Ceze, C. Guestrin, and A. Krishnamurthy, “TVM: End-to-End Optimization Stack for Deep Learning,” _CoRR_ , vol. abs/1802.04799, 2018.
  * [14] R. Peschke, K. Nishimura, and G. Varner, “HDPython: A High Level Python Based Object-Oriented HDL Framework,” 2023.
  * [15] W. Kruijtzer, P. van der Wolf, E. de Kock, J. Stuyt, W. Ecker, A. Mayer, S. Hustin, C. Amerijckx, S. de Paoli, and E. Vaumorin, “Industrial IP integration flows based on IP-XACT™ standards,” in _Proceedings of the conference on Design, Automation, and Test in Europe_ , ser. DATE ’08. ACM, Mar. 2008.
  * [16] K. Lübeck, A. L.-F. Jung, F. Wedlich, and O. Bringmann, “Work-in-Progress: Ultra-fast yet Accurate Performance Prediction for Deep Neural Network Accelerators,” in _2022 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES)_ , 2022, pp. 27–28.
  * [17] P. Mishra and N. Dutt, _Processor Description Languages_. Elsevier, 2008.
  * [18] S. Cook, C. Bock, P. Rivett, T. Rutt, E. Seidewitz, B. Selic, and D. Tolbert, “Unified Modeling Language (UML) Version 2.5.1,” Object Management Group (OMG), Standard, Dec. 2017.
  * [19] The Python Software Foundation. (2023) Python 3: typing - Support for type hints. [Online]. Available: https://docs.python.org/3/library/typing.html
  * [20] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala, “PyTorch: An Imperative Style, High-Performance Deep Learning Library,” in _Advances in Neural Information Processing Systems 32_. Curran Associates, Inc., 2019, pp. 8024–8035.
  * [21] TIOBE, “TIOBE Index for January 2024.” [Online]. Available: https://www.tiobe.com/tiobe-index/
  * [22] S. Overflow, “Stack Overflow Developer Survey 2023.” [Online]. Available: https://survey.stackoverflow.co/2023
  * [23] M. J. Klaiber, C. Gerum, and P. P. Bernardo. (2022) Making your Hardware Accelerator TVM-ready with UMA. [Online]. Available: https://tvm.apache.org/docs/tutorial/uma.html
  * [24] Apache Foundation. Apache TVM. [Online]. Available: https://tvm.apache.org/
  * [25] A. Matthes, R. Widera, E. Zenker, B. Worpitz, A. Huebl, and M. Bussmann, “Tuning and Optimization for a Variety of Many-Core Architectures Without Changing a Single Line of Implementation Code Using the Alpaka Library,” in _High Performance Computing_ , 10 2017, pp. 496–514.
  * [26] Y.-H. Chen, T. Krishna, J. S. Emer, and V. Sze, “Eyeriss: An Energy-Efficient Reconfigurable Accelerator for Deep Convolutional Neural Networks,” _IEEE Journal of Solid-State Circuits_ , vol. 52, no. 1, pp. 127–138, Jan. 2017.
  * [27] R. Prabhakar, Y. Zhang, D. Koeplinger, M. Feldman, T. Zhao, S. Hadjis, A. Pedram, C. Kozyrakis, and K. Olukotun, “Plasticine: A Reconfigurable Architecture For Parallel Patterns,” in _Proceedings of the 44th Annual International Symposium on Computer Architecture_. ACM, Jun. 2017.
  * [28] D. Harel, “Statecharts: A Visual Formalism for Complex Systems,” _Science of Computer Programming_ , vol. 8, no. 3, pp. 231–274, 1987.
  * [29] S. Li, Z. Yang, D. Reddy, A. Srivastava, and B. Jacob, “DRAMsim3: A Cycle-Accurate, Thermal-Capable DRAM Simulator,” _IEEE Computer Architecture Letters_ , vol. 19, no. 2, pp. 106–109, Jul. 2020.
  * [30] J. Hammer, J. Eitzinger, G. Hager, and G. Wellein, “Kerncraft: A Tool for Analytic Performance Modeling of Loop Kernels,” in _Tools for High Performance Computing 2016_. Cham: Springer International Publishing, 2017, pp. 1–22.


# Word maps with constants on symmetric groups

Jakob Schneider  Jakob Schneider, TU Dresden, 01062 Dresden, Germany
<EMAIL_ADDRESS>and  Andreas Thom  Andreas Thom, TU Dresden,
01062 Dresden, Germany<EMAIL_ADDRESS>To Doris, Hannah, Torsten,
Jonathan, and Paul who supported me
during the long time of my sickness. J. Schneider

###### Abstract.

We study word maps with constants on symmetric groups. Even though there are
non-trivial mixed identities of bounded length that are valid for all
symmetric groups, we show that no such identities can hold in the limit in a
metric sense. Moreover, we prove that word maps with constants and non-trivial
content, that are short enough, have an image of positive diameter, measured
in the normalized Hamming metric, which is bounded from below in terms of the
word length. Finally, we also show that every self-map $G\to G$ on a finite
non-abelian simple group is actually a word map with constants from $G$.

## Introduction

Recently, there has been increasing interest in word maps and laws on finite,
algebraic, and topological groups [avnigelanderkassabovshalev2013word,
bandmangariongrunewald2012surjectivity, elkasapythom2014goto,
garionshalev2009commutator, gordeev1997freedom,
gordeevkunyavskiiplotkin2016word, gordeevkunyavskiiplotkin2018word,
guralnickliebeckobrienshalevtiep2018surjective, guralnicktiep2015effective,
huilarsenshalev2015waring, klyachkothom2017new, larsen2004word,
larsenshalev2009word, larsenshalev2016distribution, larsenshalev2017words,
larsenshalevtiep2012waring, lubotzky2014images, schneider2019phd,
tomanov1985generalized]. Here, every word $w\in\mathbf{F}_{r}=\langle
x_{1},\ldots,x_{r}\rangle$ induces a word map $w\colon G^{r}\to G$ on every
group $G$ by substitution, where $\mathbf{F}_{r}$ denotes the free group in
the $r$ generators $x_{1},\ldots,x_{r}$ and we set $w(g_{1},\ldots,g_{r})$ to
be the image of $w$ under the unique homomorphism $\mathbf{F}_{r}\to G$ which
maps $x_{i}\mapsto g_{i}$ ($i=1,\ldots,r$). The word $w$ is called an
_identity_ or a _law_ for $G$ iff $w(g_{1},\ldots,g_{r})=1_{G}$ for all
choices of the $g_{i}\in G$ ($i=1,\ldots,r$). It is an interesting question to
study the length of the shortest non-trivial law of a given finite group $G$.
This was done in [thom2017length, bradford2019short]. A bit less
restrictively, one can ask when the image of a word map is small in a metric
sense, see for example [thom2013convergent, lubotzky2014images,
larsen2004word].

In this article we study word maps with constants. A word with constants in
$G$ is an element of the free product $\mathbf{F}_{r}\ast G$. We get an
associated map $G^{n}\to G$ in a similar way as before by replacing the
variables with elements from $G$. The word is called a _mixed identity_ or a
_law with constants_ iff $w(g_{1},\ldots,g_{r})=1_{G}$ for all choices of the
$g_{i}\in G$ ($i=1,\ldots,r$).

Following [klyachkothom2017new, nitschethom2022universal], for
$w\in\mathbf{F}_{r}\ast G$, we study the _augmentation_
$\varepsilon(w)\in\mathbf{F}_{r}$, which replaces all constants by the neutral
element. We call $\varepsilon(w)\in\mathbf{F}_{r}$ the _content_ of $w$. It
has been observed in different circumstances [klyachkothom2017new,
nitschethom2022universal] that word maps with constants which have a non-
trivial content, tend to have a large image. We prove a corresponding result
for symmetric groups with respect to the normalized Hamming metric. For
$\sigma\in S_{n}$, we write

$\operatorname{fix}(\sigma)\coloneqq\\{x\,|\,x.\sigma=x\\}$

for the set of _fixed points_ of $\sigma$,

$\operatorname{supp}(\sigma)\coloneqq\\{x\,|\,x.\sigma\neq x\\}$

for its _support_ , and

$\lvert\sigma\rvert\coloneqq\left\lvert\operatorname{supp}(\sigma)\right\rvert$

for its (unnormalized) _Hamming norm_. The _normalized Hamming norm_ on
$S_{n}$ is then defined as $\lvert\sigma\rvert_{\rm
H}\coloneqq\frac{1}{n}\lvert\sigma\rvert$. Also, for $\sigma,\tau\in S_{n}$
let $d(\sigma,\tau)\coloneqq\lvert\sigma^{-1}\tau\rvert$ be their _Hamming
distance_ and $d_{\rm
H}(\sigma,\tau)\coloneqq\frac{1}{n}\lvert\sigma^{-1}\tau\rvert$ be their
_normalized Hamming distance_. For $S\subseteq S_{n}$ write

$\operatorname{diam}(S)\coloneqq\max_{\sigma,\tau\in S}{d(\sigma,\tau)}$

for the _diameter_ of the set $S$.

We say that $w\in\mathbf{F}_{r}\ast G$ is _strong_ if, when written in normal
form, removing the constants does not lead to any cancellation among the
variables – in particular, if $w$ is strong, then either the content is non-
trivial or the word was a constant from $G$.

There are some obvious mixed identities for $S_{n}$. E.g. take $\tau$ a
transposition, then $[x,\tau]^{6}$ is such an identity, since
$[g,\tau]=\tau^{-g}\tau$ is the product of two transpositions and so either a
$3$-cycle, the product of two disjoint transpositions, or trivial, where $g\in
S_{n}$ is arbitrary. We notice here that the word with constants
$[x,\tau]^{6}$ has a trivial content. It is one consequence of our main
result, Theorem 1, that this must be the case for any mixed identity on
$S_{n}$ of _small_ length. However, there are long words with non-trivial
content that are an identity for $S_{n}$, e.g. take $x^{n!}$. We show that a
non-trivial word map with constants coming from a short word can have a small
image (i.e. with small diameter) only if there are constants involved with
small support.

Fix a group $G$ of possible constants. Every word $w\in\mathbf{F}_{r}\ast G$
can be written uniquely in the form

$w=c_{0}x_{i(1)}^{\varepsilon(1)}c_{1}\cdots
c_{l-1}x_{i(l)}^{\varepsilon(l)}c_{l}\in\mathbf{F}_{r}\ast G,$

where $x_{1},\ldots,x_{r}$ are the free generators of $\mathbf{F}_{r}$,
$\varepsilon(j)=\pm 1$, $i(j)\in\\{1,\ldots,r\\}$ ($j=1,\ldots,l$), and
$c_{j}\in G$ ($j=0,\ldots,l$) are such that there is no cancellation, i.e.
$x_{i(j)}^{\varepsilon(j)}=x_{i(j+1)}^{-\varepsilon(j+1)}$ implies that
$c_{j}\neq 1_{G}$ for $j=1,\ldots,l-1$. Then, we set $\ell(w)=l$ and call it
the _length_ of $w$. Note that $\ell$ is just the word length where we give
elements from $G$ length zero.

Our main result is the following theorem.

######  Theorem 1.

Let $w\in\mathbf{F}_{r}\ast S_{n}$ and consider the associated word map with
constants $w\colon S_{n}^{r}\to S_{n}$. Then the following holds:

  1. (i)

If $w$ has non-trivial content, then

$\frac{\operatorname{diam}(w(S_{n}^{r}))+1}{n}\geq\frac{1}{2}\exp(-\log(5\ell(w))\ell(w)/2).$

  2. (ii)

If $w$ is strong and $w\notin S_{n}$, then

$\frac{\operatorname{diam}(w(S_{n}^{r}))+1}{n}\geq\frac{1}{2\ell(w)}.$

More precisely, if $w\notin S_{n}$ is arbitrary and the inequality in $(ii)$
is violated, then a constant of size at most
$2(\operatorname{diam}(w(S_{n}^{r}))+1)\ell(w)$ can be found, so that the
removal of that constant leads to cancellation of variables.

######  Corollary 1.

Assume that $w\in\mathbf{F}_{r}\ast S_{n}$ ($n\geq 2$) is strong and induces a
constant map $S_{n}^{r}\to S_{n}$. Then either $w\in S_{n}$ or
$\ell(w)\geq\frac{n}{2}$.

The shortest known strong mixed identities are the laws constructed in
[kozmathom2016divisibility], they are of length
$\exp(C\log(n)^{4}\log\log(n)).$ It is an interesting open problem to close
this gap.

The second part of Theorem 1 implies the following corollary which is of
independent interest.

######  Corollary 2.

A metric ultraproduct of symmetric groups $S_{n}$ equipped with the normalized
Hamming metric, with $n$ tending to infinity along the chosen ultrafilter,
does not satisfy any non-trivial mixed identity.

For completeness, let us briefly recall the notion of the _metric
ultraproduct_ of a family of metric groups $(G_{n},d_{n})_{n\in\mathbb{N}}$
with respect to an _ultrafilter_ $\mathcal{U}$ on $\mathbb{N}$. Here $d_{n}$
is a bi-invariant metric on $G_{n}$ ($n\in\mathbb{N}$). It is defined as the
quotient $\prod_{n\in\mathbb{N}}{G_{n}}\big{/}N_{\mathcal{U}}$, where
$N_{\mathcal{U}}\coloneqq\\{(g_{n})_{n\in\mathbb{N}}\,|\,d_{n}(g_{n},1_{G_{n}})\to_{\mathcal{U}}0\\}$
is the normal subgroup of null sequences, and is itself a metric group when
equipped with the limit metric.

For more on metric ultraproducts of symmetric groups, see [elekszabo2003sofic,
pestov2008hyperlinear, nikolovschneiderthom2018some]. Note that the previous
corollary is in contrast to the usual ultraproduct of symmetric groups, which
satisfies a mixed identity $[x,\tau]^{6}$, where $\tau$ is an ultraproduct of
transpositions as discussed above.

Despite the restrictions on images of word maps with constants given by the
length of the words and the structure of the constants involved, we prove in
the Appendix that every self-map of a non-abelian simple group is a word map
with constants.

##  1\. Basic definitions

In this short section, we make some basic definitions, which are needed later.
Let $G$ be a group, the group of possible constants. As above, write the fixed
word $w\in\mathbf{F}_{r}\ast G$ uniquely in the form

$w=c_{0}x_{i(1)}^{\varepsilon(1)}c_{1}\cdots
c_{l-1}x_{i(l)}^{\varepsilon(l)}c_{l}\in\mathbf{F}_{r}\ast G,$

where $\varepsilon(j)=\pm 1$, $i(j)\in\\{1,\ldots,r\\}$ ($j=1,\ldots,l$), and
$c_{j}\in G$ ($j=0,\ldots,l$) are such that there is no cancellation.

We define the sets of indices
$J_{0}(w),J_{+}(w),J_{-}(w)\subseteq\\{1,\ldots,l-1\\}$ by

$J_{0}(w)\coloneqq\\{j\,|\,i(j)\neq i(j+1)\\},$
$J_{+}(w)\coloneqq\\{j\,|\,i(j)=i(j+1)\mbox{ and
}\varepsilon(j)=\varepsilon(j+1)\\},$

and

$J_{-}(w)\coloneqq\\{j\,|\,i(j)=i(j+1)\mbox{ and
}\varepsilon(j)=-\varepsilon(j+1)\\}.$

Note that $J_{0}(w),J_{+}(w),J_{-}(w)$ partition the set $\\{1,\ldots,l-1\\}$.
We call $J_{-}(w)$ the set of _critical indices_ of $w$ since the removal of a
constant $c_{j}$ for $j\in J_{-}(w)$ leads to cancellation among the
variables. The constant $c_{j}$ is then called a _critical constant_. We call
$v$ an _elementary reduction_ of $w\in\mathbf{F}_{r}\ast G$, if it is obtained
from $w$ by deleting a critical constant and reducing the outcome.

Now, we focus on word maps with constants in symmetric groups. Keep the
notation from above and set $G\coloneqq S_{n}$. For simplicity, we assume that
$c_{0}=1_{G}=\operatorname{id}$. Keep the definition of the sets $J_{-}(w)$,
$J_{+}(w)$, and $J_{0}(w)$. Define

$w_{j}\coloneqq x_{i(1)}^{\varepsilon(1)}c_{1}\cdots
x_{i(j)}^{\varepsilon(j)}c_{j}$

to be the $j$th prefix of $w$ ($j=0,\ldots,l$). Note that $w_{l}=w$ by
construction. For a reduced word $v\in\mathbf{F}_{r}\ast S_{n}$, write $\lvert
v\rvert_{i}$ for its _$i$ -length_, i.e. the number of occurrences of $x_{i}$
and $x_{i}^{-1}$ in its reduced representation ($i=1,\ldots,r$). Let
$w(S_{n}^{r})\subseteq S_{n}$ denote the _image_ of the _word map_ $w\colon
S_{n}^{r}\to S_{n}$ induced by $w$.

##  2\. Proof of the main result

We are now ready to state the main technical lemma:

######  Lemma 1.

In this setting, assume that $l>0$ and let $d\geq 1$ be an integer such that
the following hold:

  1. (i)

$n\geq(d-1)(\lvert w\rvert_{i(j)}+\lvert w\rvert_{i(j+1)})+\lvert
w_{j}\rvert_{i(j)}+\lvert w_{j+1}\rvert_{i(j+1)}-1$ for all $j\in J_{0}(w)$;

  2. (ii)

$n\geq 2((d-1)\lvert w\rvert_{i(j)}+\lvert w_{j+1}\rvert_{i(j)}-1)$ for $j\in
J_{+}(w)$;

  3. (iii)

$\lvert c_{j}\rvert\geq 2((d-1)\lvert w\rvert_{i(j)}+\lvert
w_{j+1}\rvert_{i(j)})-3$ for all $j\in J_{-}(w)$;

  4. (iv)

$n\geq d\lvert w\rvert_{i(l)}+1$.

Then, we have that $\operatorname{diam}(w(S_{n}^{r}))\geq d$.

To prove this lemma and the results thereafter, we need some additional graph-
theoretical terminology: By a _directed graph_ $G$, we mean an object that
consists of a set of _vertices_ $V(G)$ and a set of _edges_ $E(G)$ together
with maps $\alpha_{+1},\alpha_{-1}\colon E(G)\to V(G)$. For an edge $e$ of
$G$, we call $\alpha_{+1}(e)$ its _source_ and $\alpha_{-1}(e)$ its _target_ ;
also for $\varepsilon\in\\{\pm 1\\}$, we call $\alpha_{\varepsilon}(e)$ the
_$\varepsilon$ -source_ and $\alpha_{-\varepsilon}(e)$ the _$\varepsilon$
-target_ of $e$. Let $S$ be a set of _labels_. By an edge-labeling of $G$ by
$S$ we mean a mapping $\lambda\colon E(G)\to S$. If $G$ is equipped with such
a labeling, we call it a _directed $S$-edge-labeled graph_. In this case, an
edge $e$ of $G$ which is labeled by $s\in S$ is called an _$s$ -arrow_. In
this situation, if we exhibit a particular vertex $v$ of $G$, we call $(G,v)$
a _pointed directed $S$-edge-labeled graph_.

We will also make use of the following notation for partially defined maps: If
$a\colon A\to B$ and $b\colon B\to C$ are such maps, then their _composition_
$ab\colon A\to C$ is the partially defined map given by $x.ab=(x.a).b$ if
$x.a$ exists and $(x.a).b$ exists, and is undefined otherwise.

Here comes the proof of the previous lemma:

###### Proof of Lemma 1.

We have to prove that, under the assumptions of the lemma, there exist two
elements $\sigma,\tau\in w(S_{n}^{r})$ such that $d(\sigma,\tau)\geq d$. So
let $\tau\in w(S_{n}^{r})$ be an arbitrary element. In the following, we
construct $\sigma\in w(S_{n}^{r})$ such that $d(\sigma,\tau)\geq d$:

Let $S_{n}$ act on the $n$-element set $\Omega$ and fix $d$ arbitrary distinct
points $\omega_{1},\ldots,\omega_{d}\in\Omega$ (this is certainly possible by
condition (iv) in the lemma, since $n\geq d\lvert w\rvert_{i(l)}+1>d$ as
$l\geq 1$). Now we inductively construct a family
$(G_{k}^{j},\omega_{k}^{j})_{j,k}$ of pointed directed $S$-edge-labeled graphs
on the fixed vertex set $V(G_{k}^{j})\coloneqq\Omega$ where
$S=\\{x_{1},\ldots,x_{r}\\}$ is the set of generators of $\mathbf{F}_{r}$
($j=0,\ldots,l$, $k=1,\ldots,d$). The graphs $G_{k}^{j}$ will be constructed
in the following lexicographic order:

$G_{1}^{0},G_{1}^{1},G_{1}^{2},\ldots,G_{1}^{l}=G_{2}^{0},G_{2}^{1},G_{2}^{2}\ldots,G_{2}^{l}=G_{3}^{0},G_{3}^{1},G_{3}^{2},\ldots\ldots,G_{d}^{l}.$

Each such graph $G_{k}^{j}$ will be a _partial Schreier graph_ of
$\mathbf{F}_{r}$ (i.e. a graph that can be completed to a Schreier graph of
$\mathbf{F}_{r}$) which is obtained from its predecessor by adding a single
$x_{i(j)}$-arrow $e_{k}^{j}$, starting from the empty graph $G_{1}^{0}$, i.e.
the graph with $E(G_{1}^{0})=\emptyset$. Therefore, there will be precisely
$((k-1)\lvert w\rvert_{i}+\lvert w_{j}\rvert_{i})$-many $x_{i}$-arrows in
$G_{k}^{j}$ which encode partial injective maps
$\pi_{k,i}^{j}\colon\Omega\to\Omega$ ($i=1,\ldots,r$). With this notation, the
points $\omega_{k}^{j}$ will be chosen in such a way that

$\omega_{k}^{j}=\omega_{k}.w_{j}(\pi_{k,1}^{j},\ldots,\pi_{k,r}^{j})\quad\text{and}\quad\omega_{k}.w_{l}(\pi_{k,1}^{l},\ldots,\pi_{k,r}^{l})\neq\omega_{k}.\tau$

for $j=0,\ldots,l$ and $k=1,\ldots,d$, i.e. if $j\geq 1$ we have

$\alpha_{\varepsilon(j)}(e_{k}^{j})=\omega_{k}^{j-1}\quad\text{and}\quad\alpha_{-\varepsilon(j)}(e_{k}^{j}).c_{j}=\omega_{k}^{j}.$

Hence, setting $\pi_{1},\ldots,\pi_{r}\in S_{n}$ to be extensions of
$\pi_{d,1}^{l},\ldots,\pi_{d,r}^{l}$, the points $\omega_{k}^{j}$
($j=0,\ldots,l$) will be precisely the _trajectory_ of $\omega_{k}$ under the
prefixes of $w(\pi_{1},\ldots,\pi_{r})$. Thus, setting $\sigma\coloneqq
w(\pi_{1},\ldots,\pi_{r})$, we will have that
$\omega_{k}.\sigma\neq\omega_{k}.\tau$ for all $k=1,\ldots,d$, so that
$d(\sigma,\tau)\geq d$ as desired.

We are left to carry out the construction of the family
$(G_{k}^{j},\omega_{k}^{j})_{j,k}$ of pointed $S$-edge-labeled graphs. Recall
that we start with $G_{1}^{0}$ being the empty graph, hence
$E(G_{1}^{0})=\emptyset$ and
$\omega_{1}^{0}\coloneqq\omega_{1},\ldots,\omega_{d}^{0}\coloneqq\omega_{d}$.
Assume that we are to construct $(G_{k}^{j},\omega_{k}^{j})$ out of the
previous data. If $j=0$, there is nothing to do. So assume $j\geq 1$ and we
are to add the $x_{i(j)}$-arrow $e^{j}_{k}.$ We assume by induction that we
are already given an admissible ‘starting point’
$\alpha_{\varepsilon(j)}(e_{k}^{j})=\omega_{k}^{j-1}$ of our edge $e_{k}^{j}$,
i.e. $\omega_{k}^{j-1}\neq\alpha_{\varepsilon(j)}(e)$ for any $x_{i(j)}$-arrow
$e\in E(G_{k}^{j-1})$. Our task is to find an admissible ‘end point’
$\alpha_{-\varepsilon(j)}(e_{k}^{j})$ of $e_{k}^{j}$. This means, we have to
ensure that the following conditions are satisfied:

  1. (a)

$\alpha_{-\varepsilon(j)}(e_{k}^{j})\neq\alpha_{-\varepsilon(j)}(e)$ for any
$x_{i(j)}$-arrow $e\in E(G_{k}^{j-1})$;

  2. (b)

if $i(j)=i(1)$ and $\varepsilon(j)=-\varepsilon(1)$, then
$\alpha_{-\varepsilon(j)}(e_{k}^{j})\neq\omega_{m}$ for all $m=k+1,\ldots,d$;

  3. (c)

if $j<l$, then
$\omega_{k}^{j}\coloneqq\alpha_{-\varepsilon(j)}(e_{k}^{j}).c_{j}\neq\alpha_{\varepsilon(j+1)}(e)$
for any $x_{i(j+1)}$-arrow

$e\in E(G_{k}^{j})\coloneqq E(G_{k}^{j-1})\cup\\{e_{k}^{j}\\};$

  4. (d)

if $j=l$, then
$\omega_{k}^{j}\coloneqq\alpha_{-\varepsilon(j)}(e_{k}^{j}).c_{j}\neq\omega_{k}.\tau$.

Let us briefly explain this: (a) means that $e_{k}^{j}$ will not have the same
$\varepsilon(j)$-target as any $x_{i(j)}$-arrow in $G_{k}^{j-1}$, ensuring
that $G_{k}^{j}$ remains a partial Schreier graph. (b) is necessary, since the
$\varepsilon(1)$-sources of the $x_{i(1)}$-arrows $e_{m}^{1}$ are already
fixed to be $\omega_{m}$ from the beginning (for all $m=1,\ldots,d$), so these
cannot be used by another $x_{i(1)}$-arrow as its $\varepsilon(1)$-source. (c)
is necessary to ensure that $e_{k}^{j+1}$ will have a valid ‘starting point’
$\omega_{k}^{j}=\alpha_{\varepsilon(j+1)}(e_{k}^{j+1})$ (when $j<l$) which is
not already in use as the $\varepsilon(j+1)$-source of another
$x_{i(j+1)}$-arrow in $G_{k}^{j}$. Finally, (d) ensures that
$\omega_{k}.\sigma\neq\omega_{k}.\tau$.

Now we count the number of possibilities to choose the $\varepsilon(j)$-target
$\alpha_{-\varepsilon(j)}(e_{k}^{j})$ of $e_{k}^{j}$ according to (a)–(d): As
$G_{k}^{j-1}$ is a partial Schreier graph, no two of its $x_{i(j)}$-arrows
have the same $\varepsilon(j)$-target. Hence there are precisely

$n-((k-1)\lvert w\rvert_{i(j)}+\lvert w_{j-1}\rvert_{i(j)})=n-((k-1)\lvert
w\rvert_{i(j)}+\lvert w_{j}\rvert_{i(j)}-1)$

possible $\varepsilon(j)$-targets for $e_{k}^{j}$ that satisfy (a). In the
following three cases, we assume that $j<l$, so that (d) is irrelevant.

_Case (i): $i(j)\neq i(j+1)$._ This means that $j\in J_{0}(w)$. Then
$G_{k}^{j}$ has precisely

$(k-1)\lvert w\rvert_{i(j+1)}+\lvert w_{j}\rvert_{i(j+1)}=(k-1)\lvert
w\rvert_{i(j+1)}+\lvert w_{j+1}\rvert_{i(j+1)}-1$

$x_{i(j+1)}$-arrows, none of which is $e_{k}^{j}$, so (c) rules out as many
vertices for the $\varepsilon(j)$-target of $e_{k}^{j}$. In the worst case,
the condition in (b) is satisfied, so that (b) rules out at most $d-k$ more
vertices. In total, we get at least

$\displaystyle n-((k-1)(\lvert w\rvert_{i(j)}+\lvert w\rvert_{i(j+1)})+\lvert
w_{j}\rvert_{i(j)}+\lvert w_{j+1}\rvert_{i(j+1)}-2+d-k)$ $\displaystyle=$
$\displaystyle n-((k-1)(\lvert w\rvert_{i(j)}+\lvert
w\rvert_{i(j+1)}-1)+\lvert w_{j}\rvert_{i(j)}+\lvert
w_{j+1}\rvert_{i(j+1)}+d-3)$ $\displaystyle\geq$ $\displaystyle
n-((d-1)(\lvert w\rvert_{i(j)}+\lvert w\rvert_{i(j+1)}-1)+\lvert
w_{j}\rvert_{i(j)}+\lvert w_{j+1}\rvert_{i(j+1)}+d-3)$ $\displaystyle=$
$\displaystyle n-((d-1)(\lvert w\rvert_{i(j)}+\lvert w\rvert_{i(j+1)})+\lvert
w_{j}\rvert_{i(j)}+\lvert w_{j+1}\rvert_{i(j+1)}-2)$

possible choices for the $\varepsilon(j)$-target of $e_{k}^{j}$, which is a
positive number by assumption (i) in the lemma.

_Case (ii): $i(j)=i(j+1)$ and $\varepsilon(j)=\varepsilon(j+1)$._ This means
that $j\in J_{+}(w)$. Considering (c), there are precisely

$(k-1)\lvert w\rvert_{i(j)}+\lvert w_{j-1}\rvert_{i(j)}=(k-1)\lvert
w\rvert_{i(j)}+\lvert w_{j+1}\rvert_{i(j)}-2$

$x_{i(j+1)}=x_{i(j)}$-arrows $e$ different from $e_{k}^{j}$ in $G_{k}^{j}$
(namely the ones in $G_{k}^{j-1}$) which admit as many vertices as their
$\varepsilon(j+1)=\varepsilon(j)$-sources, and the condition
$\alpha_{-\varepsilon(j)}(e_{k}^{j}).c_{j}\neq\alpha_{\varepsilon(j)}(e_{k}^{j})$
rules out the vertex
$\alpha_{\varepsilon(j)}(e_{k}^{j}).c_{j}^{-1}=\omega_{k}^{j-1}.c_{j}^{-1}$.
In the worst case, the condition in (b) is satisfied, so that (b) rules out at
most $d-k$ further vertices. In total, we get at least

$\displaystyle n-(2((k-1)\lvert w\rvert_{i(j)}+\lvert
w_{j+1}\rvert_{i(j)}-2)+1+d-k)$ $\displaystyle=$ $\displaystyle
n-((k-1)(2\lvert w\rvert_{i(j)}-1)+2\lvert w_{j+1}\rvert_{i(j)}-4+d)$
$\displaystyle\geq$ $\displaystyle n-((d-1)(2\lvert w\rvert_{i(j)}-1)+2\lvert
w_{j+1}\rvert_{i(j)}-4+d)$ $\displaystyle=$ $\displaystyle n-(2((d-1)\lvert
w\rvert_{i(j)}+\lvert w_{j+1}\rvert_{i(j)})-3)$

possible choices for $\alpha_{-\varepsilon(j)}(e_{k}^{j})$, which is positive
by assumption (ii) in the lemma.

_Case (iii): $i(j)=i(j+1)$ and $\varepsilon(j)=-\varepsilon(j+1)$._ This means
that $j\in J_{-}(w)$. As in the previous case, (c) splits into two parts: The
$x_{i(j+1)}=x_{i(j)}$-arrows different from $e_{k}^{j}$ in $G_{k}^{j}$ rule
out

$(k-1)\lvert w\rvert_{i(j)}+\lvert w_{j-1}\rvert_{i(j)}=(k-1)\lvert
w\rvert_{i(j)}+\lvert w_{j+1}\rvert_{i(j)}-2$

vertices for the $\varepsilon(j)$-target of $e_{k}^{j}$, and the condition
$\alpha_{-\varepsilon(j)}(e_{k}^{j}).c_{j}\neq\alpha_{-\varepsilon(j)}(e_{k}^{j})$
rules out the $n-\lvert c_{j}\rvert$ fixed points of $c_{j}$. In the worst
case, the condition in (b) is satisfied, and (b) rules out $d-k$ further
vertices. Hence we have at least

$\displaystyle n-(2((k-1)\lvert w\rvert_{i(j)}+\lvert
w_{j+1}\rvert_{i(j)}-2)+n-\lvert c_{j}\rvert+d-k)$ $\displaystyle=$
$\displaystyle\lvert c_{j}\rvert-((k-1)(2\lvert w\rvert_{i(j)}-1)+2\lvert
w_{j+1}\rvert_{i(j)}-5+d)$ $\displaystyle\geq$ $\displaystyle\lvert
c_{j}\rvert-((d-1)(2\lvert w\rvert_{i(j)}-1)+2\lvert
w_{j+1}\rvert_{i(j)}-5+d)$ $\displaystyle=$ $\displaystyle\lvert
c_{j}\rvert-(2((d-1)\lvert w\rvert_{i(j)}+\lvert w_{j+1}\rvert_{i(j)})-4)$

choices for $\alpha_{-\varepsilon_{j}}(e_{k}^{j})$, which is positive by
assumption (iii) in the lemma.

_Case (iv): $j=l$._ Then (c) is irrelevant, (b) can rule out at most $d-k$
vertices for $\alpha_{-\varepsilon_{l}}(e_{k}^{l})$ if ($\ast$) holds, and (d)
rules out one further vertex. Hence in total we have at least

$n-((k-1)\lvert w\rvert_{i(l)}+\lvert w_{l}\rvert_{i(l)}-1+d-k+1)\geq
n-d\lvert w\rvert_{i(l)}$

vertices remaining. This is a positive number by assumption (iv) of the lemma.
Hence the proof is complete. ∎

######  Remark 1.

The condition on $\operatorname{diam}(w(S_{n}^{r}))$ is almost sharp: Take $g$
to be the $c$-cycle $(1\cdots c)$ and set $w=g^{x_{1}}$. Then
$\operatorname{diam}(w(S_{n}^{r}))=\min\\{2c,n\\}$ and the bound in the lemma
gives $\operatorname{diam}(w(S_{n}^{r}))\geq\left\lfloor c/4\right\rfloor$.

We set

$\lvert w\rvert_{\infty}\coloneqq\max_{i\in\\{1,\ldots r\\}}{\lvert
w\rvert_{i}}\quad\mbox{and}\quad\lvert w\rvert_{\rm
crit}\coloneqq\min\left\\{n,\min_{j\in J_{-}(w)}\lvert c_{j}\rvert\right\\}.$

The four assumptions in Lemma 1 can obviously by strengthened to the single
inequality $\lvert w\rvert_{\rm crit}\geq 2d\lvert w\rvert_{\infty}$. It
follows that

$\operatorname{diam}(w(S_{n}^{r}))\geq\left\lfloor\frac{\lvert w\rvert_{\rm
crit}}{2\lvert w\rvert_{\infty}}\right\rfloor>\frac{\lvert w\rvert_{\rm
crit}}{2\lvert w\rvert_{\infty}}-1$

for $n\geq 2$. Note that $\lvert w\rvert_{\infty}$ is obviously bounded by the
length $\ell(w)$. We will use the above inequality in the form

$\lvert w\rvert_{\rm crit}\leq
2\cdot(\operatorname{diam}(w(S_{n}^{r}))+1)\cdot\ell(w).$

We interpret this inequality as follows: If the diameter of the word image is
small, then either there is a small critical constant or the word length is
large.

######  Remark 2.

We suppose that a similar lemma can be proved for families like
$\operatorname{PSL}_{n}(p)$ for a fixed prime $p$ and $n$ growing, leading to
results comparable to our main theorem. However, we note that for example for
the family $\operatorname{PSL}_{2}(q)$ for $q$ growing, the length of the
shortest mixed identity grows linearly in $q$. Note that in this case, the
fact that the length of the shortest mixed identity must tend to infinity is
already a consequence of the results in [gordeevkunyavskiiplotkin2016word].
This will be the subject of further work.

###### Proof of Theorem 1.

The bound in (ii) directly follows from the inequality $\lvert w\rvert_{\rm
crit}\leq 2(\operatorname{diam}(w(S_{n}^{r}))+1)\ell(w)$, since when $w$ is
strong we have $\lvert w\rvert_{\rm crit}=n$ as there is no critical constant.
The assertion about existence of small critical constants is also an immediate
consequence of the inequality above.

In order to prove (i) we study the effect of removal of critical constants in
more detail. Let $v$ be an elementary reduction of $w\in\mathbf{F}_{r}\ast G$,
i.e. it is obtained from $w$ by deleting a critical constant and reducing the
outcome. Note that removing the smallest critical constant $c$ does not change
the diameter of the word image by more than $2\lvert c\rvert=2\lvert
w\rvert_{\rm crit}$, so that given a small diameter, we can try to iterate
elementary reductions. Let $w$ have non-trivial content and let
$w=w_{0},\ldots,w_{m}$ be a chain of words, where $w_{i}$ is an elementary
reduction of $w_{i-1}$ ($i\geq 1$) by a smallest critical constant, so that
there is no such reduction for $w_{m}$, i.e. $w_{m}$ is strong. Note that
$w_{i}$ no longer denotes the $i$th prefix of $w$. Then
$\ell(w_{i})\leq\ell(w_{i-1})-2\leq\ell(w)-2i$. We have

$\lvert w_{i-1}\rvert_{\rm crit}\leq
2\ell(w_{i-1})(\operatorname{diam}(w_{i-1}(S_{n}^{r}))+1)$

and so

$\displaystyle\operatorname{diam}(w_{i}(S_{n}^{r}))$ $\displaystyle\leq$
$\displaystyle\operatorname{diam}(w_{i-1}(S_{n}^{r}))+2\lvert
w_{i-1}\rvert_{\rm crit}$ $\displaystyle\leq$
$\displaystyle\operatorname{diam}(w_{i-1}(S_{n}^{r}))+4\ell(w_{i-1})(\operatorname{diam}(w_{i-1}(S_{n}^{r}))+1).$

It follows that

$\operatorname{diam}(w_{i}(S_{n}^{r}))+1\leq(1+4\ell(w_{i-1}))(\operatorname{diam}(w_{i-1}(S_{n}^{r}))+1).$

Hence, we obtain

$\operatorname{diam}(w_{i}(S_{n}^{r}))+1\leq(1+4\ell(w))^{i}(\operatorname{diam}(w(S_{n}^{r}))+1)$

by induction on $i=0,\ldots,m$, since $\ell(w_{i})\leq\ell(w)$. By assumption,
$w_{m}$ is not a constant from $G=S_{n}$. Then by the above inequality

$\displaystyle n=\lvert w_{m}\rvert_{\rm crit}$ $\displaystyle\leq
2(\operatorname{diam}(w_{m}(S_{n}^{r}))+1)\ell(w_{m})$ $\displaystyle\leq
2(1+4\ell(w))^{m}(\operatorname{diam}(w(S_{n}^{r}))+1)\ell(w)$
$\displaystyle\leq
2(1+4\ell(w))^{\left\lfloor\ell(w)/2\right\rfloor}\ell(w)(\operatorname{diam}(w(S_{n}^{r}))+1)$
$\displaystyle\leq
2\exp(\log(5\ell(w))\ell(w)/2)(\operatorname{diam}(w(S_{n}^{r}))+1)$

as $m\leq\ell(w)/2$ and $\ell(w)\geq 1$. This is the bound in (i) of Theorem
1. ∎

We now turn to metric ultraproducts of symmetric groups and Corollary 2.
Assume that $l\geq 1$ and let

$w_{n}=x_{i(1)}^{\varepsilon_{1}}c_{1,n}\cdots
x_{i(l)}^{\varepsilon_{l}}c_{l,n}\in\mathbf{F}_{r}\ast S_{n}$

be a sequence of reduced words of the same structure, but with different
constants $c_{j,n}$ ($j=1,\ldots,l$, $n\in\mathbb{N}$, $n\geq 2$). Let
$\mathcal{U}$ be an ultrafilter on $\mathbb{N}$ such that
$\operatorname{diam}(w_{n}(S_{n}^{r}))/n\to_{\mathcal{U}}0$ as
$n\to_{\mathcal{U}}\infty$, i.e.

$w=x_{i(1)}^{\varepsilon(1)}\overline{(c_{1,n})}_{n}\cdots
x_{i(l)}^{\varepsilon(l)}\overline{(c_{l,n})}_{n}$

induces a constant map on the metric ultraproduct of the $S_{n}$’s equipped
with the normalized Hamming norm $\lvert g\rvert_{\rm H}=\lvert g\rvert/n$. We
claim, that then there is an index $j\in\\{1,\ldots,l-1\\}$ such that
$i(j)=i(j+1)$ and $\varepsilon(j)=-\varepsilon(j+1)$, such that $\lvert
c_{j,n}\rvert/n\to_{\mathcal{U}}0$ as $n\to_{\mathcal{U}}\infty$. In
particular, $w$ is trivial.

###### Proof of Corollary 2.

By the above $2\lvert
w\rvert_{\infty}(\operatorname{diam}(w_{n}(S_{n}^{r}))+1)\geq\lvert
w\rvert_{\mathrm{c}}$, so that $\lvert w\rvert_{\rm c}/n\to_{\mathcal{U}}0$ as
$n\to_{\mathcal{U}}\infty$ by the assumption. Hence, by finiteness, there
exists an index $j\in J_{-}(w)$ such that $\lvert
c_{j,n}\rvert/n\to_{\mathcal{U}}0$ as $n\to_{\mathcal{U}}\infty$. In
particular, starting with a potential mixed identity in the metric
ultraproduct, the previous argument implies that a critical constant must be
trivial. This is a contradiction and the proof is complete. ∎

## Appendix

It is well-known that every map $\mathbb{F}_{q}\to\mathbb{F}_{q}$ is realized
by a polynomial from $\mathbb{F}_{q}[X]$ of degree less than $q$ – in fact
this is a characterization of fields among finite rings, see
[istingerkaiser1979characterization]. We prove the analogous result for non-
abelian simple groups. We denote by the _covering number_
$\operatorname{cn}(G)$ of $G$ the minimal $m$, such that $C^{\ast m}=G$ for
all non-trivial conjugacy classes $C$. Various bounds on
$\operatorname{cn}(G)$ for finite simple groups $G$ can be found in the
literature, see for example the seminal work of Liebeck-Shalev
[liebeckshalev2001diameters] and the references therein.

######  Theorem 2.

A non-abelian finite group is simple if and only if every map $G\to G$ is a
word map with constants. Every such map can be represented by a word of length
at most $O(\left\lvert G\right\rvert^{3}\operatorname{cn}(G))$.

######  Remark 3.

An abelian group $G$ has the above property (i.e. each map $G\to G$ comes from
a word with constants) if and only if $\left\lvert G\right\rvert\leq 2$.

######  Remark 4.

In the theorem, the term $\operatorname{cn}(G)$ can also be replaced by the
_covering diameter_ $\operatorname{cd}(G)$ of $G$, which is the minimal number
$m$ such that $(\\{1_{G}\\}\cup C\cup C^{-1})^{\ast m}=G$ for all non-trivial
conjugacy classes $C$ of $G$. Clearly,
$\operatorname{cd}(G)\leq\operatorname{cn}(G)$.

###### Proof.

The evaluation map $\operatorname{ev}\colon\mathbf{F}_{1}\ast G=\langle
x\rangle\ast G\to G^{G}$ is a homomorpism. Also, if $\pi_{\\{g,h\\}}\colon
G^{G}\to G^{\\{g,h\\}}$ is the projection onto $g$ and $h$, then
$\pi_{\\{g,h\\}}\circ\operatorname{ev}$ is surjective: Indeed, by Goursat’s
lemma and since $G$ is assumed to be simple, it is enough to show that its
image is not the graph of an automorphism. However, this cannot be the case,
since the constants $G$ map to the diagonal subgroup, and $x$ maps to a non-
diagonal subgroup. This implies that $\operatorname{ev}$ must be surjective
too.

By using iterated commutators, one can give a more explicit construction: We
prove that for any subset $S\subseteq G$ of size $m\leq 2^{e}$ and an element
$g\in G\setminus S$, there is a commutator word $w_{g,S}\in\mathbf{F}_{1}\ast
G$ of length $4^{e}$ such that the induced map $w_{g,S}\colon G\to G$
satisfies $w_{g,S}(s)=1_{G}$ for all $s\in S$ and $w_{g,S}(g)\neq 1_{G}$.

Indeed, this is true when $e=0$ and $S=\\{s\\}$: Simply take
$w_{g,\\{s\\}}=xs^{-1}$. For $e\geq 1$, write $S=S_{1}\cup S_{2}$ as a union
of the subsets $S_{1}$ and $S_{2}$ such that $\left\lvert
S_{1}\right\rvert,\left\lvert S_{2}\right\rvert\leq 2^{e-1}$. Then set
$w_{g,S}\coloneqq[w_{g,S_{1}}^{a},w_{g,S_{2}}^{b}]$ where $a,b\in G$ are
chosen such that $[w_{g,S_{1}}(g)^{a},w_{g,S_{2}}(g)^{b}]\neq 1_{G}$. This is
possible since $(w_{g,S_{2}}(g))^{G}$ generates the whole $G$ by simplicity as
$w_{g,S_{2}}(g)\neq 1_{G}$, whereas $\mathbf{C}_{G}(w_{g,S_{1}}(g))$ is a
proper subgroup. Hence

$w_{g,S_{2}}^{G}(g)\not\subseteq\mathbf{C}_{G}(w_{g,S_{1}}(g)).$

We have that $\ell(w_{g,S})\leq 2(\ell(w_{g,S_{1}})+\ell(w_{g,S_{1}}))\leq
4^{e}$.

Then setting $e\coloneqq\left\lceil\log_{2}(\left\lvert
G\right\rvert-1)\right\rceil$, one can take $S=G\setminus\\{g\\}$, so that
$w_{g,S}(s)=1_{G}$ for $s\in S$ and $w_{g,S}(g)\neq 1_{G}$ as desired. Now we
can multiply together conjugates of the map $w_{g,S}$ to get a map
$\delta_{g,h}\in\mathbf{F}_{1}\ast G$ such that $\delta_{g,h}(s)=1_{G}$ for
$s\in S=G\setminus\\{g\\}$ and $\delta_{g,h}(g)=h$ for a chosen $h\in G$. Then
$w=\prod_{g\in G}{\delta_{g,f(g)}}=f$ as maps $w,f\colon G\to G$ where $f$ is
arbitrary. So $f$ is a word map. Here

$\ell(w)\leq\left\lvert G\right\rvert 4^{\left\lceil\log_{2}(\left\lvert
G\right\rvert-1)\right\rceil}\operatorname{cn}(G)\leq 4\left\lvert
G\right\rvert(\left\lvert
G\right\rvert-1)^{2}\operatorname{cn}(G)<4\left\lvert
G\right\rvert^{3}\operatorname{cn}(G).$

Conversely, if any map $f\colon G\to G$ is a word map, then for $g\neq 1_{G}$,
the map $\delta_{g,h}\colon G\to G$ given by

$\delta_{g,h}(x)=\begin{cases}1_{G}&\text{if $x\neq g$}\\\ h&\text{if
$x=g$}\end{cases}$

is induced by some word $w\in\mathbf{F}_{1}\ast G$. Since
$w(1_{G})=\delta_{g,h}(1_{G})=1_{G}$, we have that
$w(g)=\delta_{g,h}(g)=h\in\langle\\!\langle g\rangle\\!\rangle$. But since $h$
was arbitrary, we have $\langle\\!\langle g\rangle\\!\rangle=G$, so that $G$
is simple, since $g\neq 1_{G}$ was arbitrary as well. ∎

By [aradstaviherzog1985powers], Chapter 3, we have
$\operatorname{cn}(A_{n})=\left\lfloor n/2\right\rfloor$ for $n\geq 6$. Thus,
we get the following estimate for alternating groups.

######  Corollary 3.

For $n\geq 5$, every map $A_{n}\to A_{n}$ can be represented by a word map
with constants of length $O((n!)^{3}n)$.

######  Remark 5.

There are at most $3^{l}\left\lvert G\right\rvert^{l+1}$ words with constants
of length at most $l$ in $\mathbf{F}_{1}\ast G=\langle x\rangle\ast G$. So in
order that all self-maps $G\to G$ can be represented as word maps coming from
words of length at most $l$, we must have

$\left\lvert G\right\rvert^{\left\lvert G\right\rvert}\leq 3^{l}\left\lvert
G\right\rvert^{l+1}.$

This implies a linear lower bound on the minimal length of words with
constants that can represent all possible maps.

######  Remark 6.

It was pointed out to us by Ben Steinberg and Anton Klyachko, that the
qualitative aspect of Theorem 2 is a well-known result
[maurerrhodes1965property]. Similar but weaker bounds have been obtained in
[horvathnehaniv2015length]. Using methods similar to the ones in the proof of
Theorem 2 one can show that every map $G^{r}\to G$ arises as a word map with
constants of length $O(\left\lvert
G\right\rvert^{r+2}r^{2}\operatorname{cn}(G))$. Indeed, one can use the maps
of length at most $O(\left\lvert G\right\rvert^{2})$ to get maps that see just
one coordinate of $G^{r}$. Taking $\left\lceil\log_{2}(r)\right\rceil$
commutators of those maps, one gets a map that sees just one element of
$G^{r}$. This then has length $O(r^{2}\left\lvert G\right\rvert^{2})$. Hence,
we get a bound

$O(\left\lvert G\right\rvert^{r+2}r^{2}\operatorname{cn}(G)).$

This is exactly the bound in [horvathnehaniv2015length] for $A_{n}$, but the
authors do not write it out for other non-abelian simple groups.

## Acknowledgments

We thank Robert Kaak for his friendship. Moreover, we thank Christoph Schulze
and Vadim Alekseev for discussions on the topic. We thank Ben Steinberg and
Anton Klyachko for comments on a first draft of this paper. This research was
supported by the ERC Consolidator Grant No. 681207.

## References