# Fast Prototyping Next-Generation Accelerators for New ML Models using MASE:
ML Accelerator System Exploration

Jianyi Cheng, Cheng Zhang, Zhewen Yu, Alex Montgomerie-Corcoran, Can Xiao,
Christos-Savvas Bouganis and Yiren Zhao  Imperial College London, UK
{jianyi.cheng17, cheng.zhang122, zhewen.yu18, alexander.montgomerie-
corcoran15, can.xiao22,
christos-savvas.bouganis<EMAIL_ADDRESS>
###### Abstract

Machine learning (ML) accelerators have been studied and used extensively to
compute ML models with high performance and low power. However, designing such
accelerators normally takes a long time and requires significant effort.

Unfortunately, the pace of development of ML software models is much faster
than the accelerator design cycle, leading to frequent and drastic
modifications in the model architecture, thus rendering many accelerators
obsolete. Existing design tools and frameworks can provide quick accelerator
prototyping, but only for a limited range of models that can fit into a single
hardware device, such as an FPGA. Furthermore, with the emergence of large
language models, such as GPT-3, there is an increased need for hardware
prototyping of these large models within a many-accelerator system to ensure
the hardware can scale with the ever-growing model sizes.

In this paper, we propose an efficient and scalable approach for exploring
accelerator systems to compute large ML models. We developed a tool named MASE
that can directly map large ML models onto an efficient streaming accelerator
system. Over a set of ML models, we show that MASE can achieve better energy
efficiency to GPUs when computing inference for recent transformer models. Our
tool will open-sourced upon publication.

##  I Introduction

Figure 1: An overview of the MASE tool flow. We propose MASE IR as an
intermediate representation that can exploit both software and hardware
optimization at the same level.

Machine Learning (ML) has demonstrated state-of-the-art performance in domains
such as Computer Vision (CV) [38, 35] and Natural Language Processing (NLP)
[15, 7]. ML has now been widely deployed in many applications, such as
autonomous driving [23, 44], recommendation systems [2], healthcare [22], and
more. Often, ML applications necessitate a substantial amount of energy for
computation due to the craving for superior performance and the ever-growing
model sizes. To facilitate meeting the demand for low-energy computing, ML
hardware accelerators are proposed as they utilize a particular architecture
designed for ML computation, consuming significantly less energy than general-
purpose processors while attaining a similar performance level [34, 20].

Designing an efficient ML accelerator requires a tremendous amount of
knowledge and effort from hardware experts. It could take years to implement
an ML accelerator in an application-specific integrated circuit (ASIC) and
months for prototyping on a reconfigurable device such as a field-programmable
gate array (FPGA). The gap between the development cycles of software ML
models and hardware acceleration has been rapidly widening due to the
increasing size and complexity of models. Furthermore, new models may
significantly alter their program behaviour, making the hardware architecture
obsolete and necessitating a complete redesign from scratch.

In order to address these challenges, two traditional approaches have been
studied. The first approach involves transforming the ML model using software
compilers, enabling efficient mapping onto a pre-existing accelerator
architecture [31]. However, the fixed accelerator architecture imposes a
performance upper bound. The second approach focuses on fast prototyping of
hardware accelerators using high-level synthesis (HLS) tools, targeting ASICs
[8, 33] or FPGAs [17, 6]. However, these tools primarily keep the software
model unchanged and aim to explore solely an efficient hardware accelerator
architecture. This naturally raises the question of how we can systematically
explore the opportunities for concurrent co-optimization of software and
hardware?

Previous research has explored the co-optimization of software and hardware
for Deep Neural Networks (DNNs) from an Automated Machine Learning (AutoML)
perspective. The general idea is to include hardware design parameters in the
canonical AutoML search space. However, this approach is still relatively
limited in terms of hardware architecture exploration. Co-design AutoML
typically focuses on a small set of parameters in a Processing Element (PE)
array-based architecture [1, 9], such as buffer sizes and PE array dimensions.
Additionally, existing Co-design AutoML strategies are constrained to a single
type of network, such as Convolutional Neural Networks (CNNs), due to the
hindrance posed by the underlying ‘template’ hardware accelerator when
exploring alternative network architectures, like transformers [7]. Therefore,
the aim of this work is to develop a system-level flow that facilitates the
mapping of various networks to custom silicon.

Many prior DNN hardware accelerator design frameworks [39, 6, 18, 36] focus on
automating the design of single-device accelerators. This implies that DNNs
must either fit within the designated device or be reused on the same
hardware. However, the emergence of large language models such as GPT and OPT
[7, 42], which consist of millions or even billions of parameters, has
necessitated the exploration of multi-accelerator systems instead of
traditional single-accelerator systems. Multi-accelerator systems are better
suited to accommodate the ever-growing models, which raises the question of
how can we automatically partition available hardware resources across
multiple devices for different types of DNNs with varying runtime constraints.

In this paper, we are interested in exploiting custom hardware computing for a
wide variety of ML models with optimization in both software and hardware on a
many-accelerator system. Our work aims to solve the following challenges:

1) Unified Abstraction for Software and Hardware

The development flows for ML models and hardware design are currently
separate. The ML models are treated as a ‘read-only’ input to the hardware
synthesis tools.  How can we lift this restriction by enabling ML model
optimization in the hardware flow?

2) Efficiency and Scalability

Most new ML models are large and contain millions of operations and cannot be
efficiently mapped onto a single hardware device.  How can we efficiently
exploit parallelism in a scalable hardware system?

3) Hardware Reusability

Hardware designers may have already implemented efficient hardware blocks that
could be reused for computing new ML models.  How can we efficiently explore
hardware optimization with these user-defined blocks?

4) Correctness

The user-defined blocks might not work correctly or efficiently with the
synthesised blocks using MASE. How to test and verify the final hardware
design by making use of the software ML model?

We propose a novel hardware architecture exploration tool termed MASE, which
stands for ML Accelerator System Exploration. MASE enables fast prototyping of
efficient hardware accelerator systems for state-of-the-art ML models. The
main contributions are:

  * •

A novel intermediate representation that describes both software and hardware
at module level;

  * •

A scalable hardware synthesis flow with automated and cross-device design
space exploration that maps the state-of-the-art of ML models into efficient
many-accelerator systems;

  * •

Two case studies demonstrating how to use MASE to automatically quantize and
accelerate the latest large-language models using custom arithmetic; and

  * •

Over a set of ML models, MASE can achieve comparable performance and energy
efficiency to GPUs when accelerating recent and large ML models.

The rest of the paper is organised as follows. Section II provides an overview
of the MASE framework. Section III provides the background of recent trends in
ML model designs, design tools for streaming ML accelerator and AutoML
methods. Section IV explains how MASE realises the four challenges explained
before. Section V provides two case studies on how MASE can be used for
prototyping efficient accelerators for new transformer models.

TABLE I:  Comparison between our IR and other existing IRs. MASE IR is the
first trainable IR that both describes the software model architecture and its
hardware accelerator architecture.

Features |  TorchScript [14] |  Torch FX [32] |  ONNX [4] | MASE IR |  MLIR [25] |  LLVM [24]
---|---|---|---|---|---|---
Granularity | module | module | module | module | tensor/vector/scalar | scalar
Executing in software | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
Hardware mapping | $\times$ | $\times$ | $\times$ | ✓ | ✓ | ✓
Training | ✓ | ✓ | ✓ | ✓ | $\times$ | $\times$

##  II Overview

This section presents an overview of MASE. MASE is integrated into PyTorch and
can directly interface with PyTorch modules without requiring any rewriting.
The top right of Figure 1 illustrates an example of how MASE can be used. In
MASE, an ML model can undergo analysis and transformation in both software and
hardware domains. The black edges in Figure 1 depict the fundamental tool flow
of MASE.

  1. 1.

A user-defined model in PyTorch with pre-trained weights is translated into an
intermediate representation (IR) in MASE, named MASE IR. The MASE IR of an ML
model encompasses both the software algorithm and its corresponding hardware
implementation.

  2. 2.

Similar to most compiler frameworks, a model in MASE IR can undergo software
transformations such as post-training quantization using MASE compiler passes
(explained in Section IV-A).

  3. 3.

The MASE IR contains comprehensive model information and can be trained or
fine-tuned after transformation (explained in Section IV-B).

  4. 4.

MASE IR also describes the accelerator architecture for the model, enabling
efficient and scalable hardware transformations using MASE compiler passes,
akin to software development (explained in Section IV-B).

  5. 5.

At the backend of MASE, the optimized hardware design can be generated for a
scalable accelerator system.

  6. 6.

MASE incorporates an efficient testing framework to verify the equivalence
between the software model and the hardware implementation.

The tool flow depicted in Figure 1 serves as an example development flow in
MASE. In MASE, all the MASE passes can be applied out-of-order, similar to
other compiler frameworks like LLVM [24] and MLIR [25].

In this paper, we demonstrate how MASE enables rapid prototyping of next-
generation ML accelerators for new ML models. The red dashed edges in Figure 1
illustrate the proposed techniques for software and hardware co-optimization.
Firstly, we show the efficient transformation of new ML models by leveraging
the implementations of existing models in both software and hardware.
Secondly, we present how the hardware can be further customized in a scalable
manner in interactive coordination with software transformations.

##  III Background

In this section, we will first introduce the automated toolflows for ML
hardware accelerators. Secondly, we compare the existing IR designs in the ML
community. Finally, we review the related works on software and hardware co-
design.

###  III-A HLS for Hardware Accelerators

Early research on hardware accelerators manually translated software models to
HLS code [8, 33]. The results are often promising, but it takes a significant
amount of effort and time to interpret the software model and perform manual
hardware translation. Such engineering effort is usually repeated when
accelerating a new model architecture.

There have been interests in fast prototyping hardware accelerators using HLS
tools. High-level synthesis is a process that automatically translates high-
level software programs into low-level hardware descriptions [12]. This
enables software engineers without hardware background to  customize their own
hardware accelerators, or hardware engineers to efficiently and rapidly
prototype hardware accelerators.

HLS4ML [18] is proposed for translating ML models into HLS code, resulting in
custom hardware designs. AMD Xilinx FINN [6] supports hardware acceleration of
CNN models. However, these tools keep the ML model unchanged and only exploit
parallelism for hardware designs that produce the same results as the software
ML model.

MASE aims to solve these problems as an efficient and scalable  system-level
HLS tool for ML. First, MASE utilises an efficient abstraction that enables
software and hardware co-optimization. This allows the software model to be
modified during hardware synthesis to generate better-quality designs. Second,
MASE supports direct lowering from PyTorch to hardware accelerator systems,
significantly reducing the development time for accelerator design.

Figure 2:  An example of MASE IR being transformed by a sequence of transform
passes. The changed parts between two consecutive IRs are highlighted in  red.
MASE passes can change an ML model in both IR and attributes. These passes can
be run out of order because of the same abstraction, which opens up
opportunities for software and hardware co-design.

###  III-B Machine Learning and HLS IR

There are a variety of tools for ML training and inference. These tools often
use an intermediate representation (IR) to represent a model architecture. For
instance, various IRs are widely used in software ML communities, including
TorchScript [14], ONNX [4] and FX Torch [32]. Such an IR represents the model
at the module level, where each operation is a predefined module or function
in PyTorch. However, these IRs are designed specifically for processors and
cannot describe custom hardware designs. MASE IR extends these IRs and enables
custom hardware modelling for efficient hardware synthesis.

In hardware acceleration, the software model is often represented in a target-
independent software IR, such as MLIR [25] or LLVM [24]. This IR is then
translated into a hardware design. MLIR is an IR that can express a program at
different abstractions, also known as dialects, enabling efficient
optimization at the appropriate level of abstraction. It supports both
software and hardware abstractions [11]. LLVM, originally designed as a
target-independent IR for software programs, has also been used to express HLS
programs [40]. However, these IRs represent an ML model at a lower granularity
than the module level and cannot be easily transformed back to the original
model. This poses challenges for training models at this level of abstraction.
In contrast, MASE IR retains the model trainability, which creates
opportunities for software and hardware co-design. A detailed comparison
between MASE IR and existing IRs is presented in Table I.

###  III-C Software and Hardware Co-Design

The field of Automated Machine Learning (AutoML) has made significant progress
in recent years, aiming to achieve high accuracy and hardware performance.
From a software perspective, this involves discovering state-of-the-art models
through Neural Architecture Search (NAS) [29, 45]. On the hardware side, the
NAS process incorporates performance metrics like latency and power, and it
also integrates the hardware metrics with the model architecture for a joint
search [1].

HW-NAS-BENCH [26] investigated co-design for small datasets such as CIFAR-10
and CIFAR-100. The study measured hardware performance on edge devices and
developed device-specific performance models. EDD [27] focused on searching
for the optimal combination of parallelism, loop-tiling factors, and
quantization strategies for a given model. The authors formulated the co-
design problem as a differentiable loss function, which was then optimized
using gradient descent. Similar works in this field include Auto-NBA [19], HAO
[16], and Co-Exploration [21].

These related works primarily focused on mapping neural networks to a single
device, and their evaluations often involved small or outdated models. In
contrast, MASE offers node-level hardware generation and integration with
arbitrary user-defined components across a multi-accelerator system. This
capability enables MASE to support the deployment of large and state-of-the-
art models. In Section V-A, we provide a case study to demonstrate how MASE
efficiently searches for both efficient quantization and hardware mapping for
these models. In the future, the MASE tool flow can be easily extended to
other use cases, such as zero-shot NAS [28].

TABLE II:  A model in MASE IR contains two constructs, operations and
attributes. Each operation has a set of attributes for presenting both
software and hardware parameters. MASE IR works with a set of actions and
passes, which perform analysis and transformation. Actions are either a
sequence of MASE passes or preprocess operations directly on torch.nn.Module.

Categories | Types |  Descriptions
---|---|---
Node/Ops | Conv2d |  Standard Pytorch operations
Linear |  Standard Pytorch operations
ReLU |  Standard Pytorch operations
Softmax |  Standard Pytorch operations
Layernorm |  Standard Pytorch operations
… |
| View |  Memory transformation
| Size |  Memory transformation
| Flatten |  Memory transformation
| … |
Attributes | args |  Input data shapes and types
results |  Output data shapes and types
interface |  Data interface with its predecessor and successor, e.g. handshake or no back pressure.
| tiling |  Tiling parameters for each data interface
| toolchain |  Synthesis flow for this node, e.g. vanilla MLIR HLS, optimised HLS or RTL kernels, user-defined kernels.
| param_map |  Resource mapping of internal parameters.
| device_id |  ID of hardware accelerator to map.
| rate |  Estimated input and output throughput of the node.
| area |  Estimated hardware resources of the node.

Categories | Types |  Descriptions
---|---|---
Actions | train |  Standard model training
eval_sw |  Standard software model evaluation for performance, accuracy and GPU power
optimise_sw |  Mixed-precision quantization (MPQ), Block-arithemtic quantization (BAQ)
optimise_hw |  Rate balancing, Resource partitioning
emit_hw |  Hardware design and test bench generation
test_hw |  Software hardware cosimulation
eval_hw |  Hardware evaluation for hardware resouces, performance and power
Passes | Init |  Traverse the IR and initialise attributes
Quantize |  Perform quantization using the provided methods, e.g. MPQ or BAQ
DSE |  Explore hardware parameters and search for a good hardware mapping for given resources
EmitVerilog |  Translate subgraphs in MASE IR to Verilog as the final hardware design
EmitTB |  Generate Verilog test bench for the given hardware design
Simulate |  Perform software and hardware co-simulation
Synthesis |  Run back end synthesis tool for hardware implementation to bitstream

##  IV Methodology

This section provides a detailed explanation of the MASE framework. Firstly,
we present the specifications for the proposed MASE IR. Then, we demonstrate
how software transformations can be performed on the MASE IR using MASE
passes. Next, we elaborate on the process of hardware optimization and
generation within the MASE IR. Finally, we describe the implementation of the
testing framework, which enables co-simulations between the software model and
the hardware design.

###  IV-A Unified IR for Software and Hardware

We seek an efficient IR that provides a high-level description of ML models
and can be transformed back into the PyTorch model. Designing an efficient and
trainable IR for hardware accelerator design is crucial for effectively
exploring both software and hardware aspects. By using the term “trainable”,
we mean that the IR can be converted back into a trainable module within a
high-level framework like PyTorch, enabling the re-training of a modified IR.

In this work, we introduce a novel software and hardware co-design IR at the
module level, called MASE IR. A MASE IR is a directed graph representation of
an ML model and its accelerator architecture, consisting of multiple vertices
connected by edges. Each vertex is referred to as a ‘MASE node’.  A MASE node
represents the computation of an operation at the module level for software
(an event) and a custom computation kernel for hardware (an instance). Each
edge between two MASE nodes represents data dependence for software and data
interface in wires for hardware. MASE IR preserves the original PyTorch model
within the IR by associating it with the nodes and edges, enabling analysis,
transformation, training, and execution of the model.

Figure 2 provides several examples of MASE IR. The leftmost part of the figure
shows the initial representation of an input model. The IR consists of six
nodes, where the orange nodes represent nodes that do not alter the tensor
values, and the blue nodes compute tensors and generate new values. The
colours of the nodes serve as annotations, and all the nodes are treated the
same by the tool. The node types in MASE IR are a superset of the types
supported by PyTorch built-in modules and functions, enabling a direct
translation between MASE and PyTorch. A list of the supported node types can
be found in the top left of Table II.

Each instance of a node in MASE IR is associated with a set of attributes that
model both software and hardware behaviour. In the figure, we show the key
attributes for the sake of simplicity. Attributes denoted by black text in the
figure are general and applicable to every node, such as input and output
types. Certain attributes are specific to individual node types, highlighted
in blue text in the figure. These node-specific attributes correspond to
parameters specific to different types of nodes, such as convolutional layers
and linear layers as depicted in the figure. The information regarding edges
in the IR is captured by the attributes of the preceding and succeeding nodes.
A list of key attributes used in this work can be found in the bottom left of
Table II.

MASE interacts with MASE IR through two forms: actions and passes. An action,
also referred to as a pass manager, carries out coarse-grained transformations
of MASE IR. It consists of a sequence of passes and can be directly utilised
by general users, as depicted in Figure 1. A pass performs analysis or
transformation at a finer grain and is employed during development. A
comprehensive list of actions and passes is provided in Table II. In the
following sections, we will delve into the process of transforming MASE IR in
both software and hardware through a series of MASE passes.

###  IV-B Software & Hardware Transformation

The software transformation passes can be classified into two categories:
architecture-level and node-level. In Figure 2, a pipeline of transformations
is demonstrated using a sequence of three MASE passes. The first pass (fusion
pass) conducts software transformation on the model architecture, while the
second pass (quantization pass) performs software transformation on the model
parameters.

Firstly, the fusion pass merges a BatchNorm layer following a Conv2d layer
into the Conv2d layer by updating the weights within the Conv2d layer. A key
benefit of such a transformation is that it reduces the hardware area due to
the removal of a BatchNorm kernel, at the cost of preprocessing the weights.
The fusion pass is an architecture-level transformation that modifies the
model architecture.

Secondly, the quantization pass replaces the Conv2d and Linear nodes in
floating-points with the quantized ones in integer types.  The forward and
backward passes of each node are updated so the node is still trainable. A key
benefit of such a transformation is that it reduces the area occupied by each
hardware kernel by utilising efficient arithmetic for hardware computation, at
the cost of potential accuracy loss. The quantization pass operates at the
node level, as it solely modifies the node locally. As depicted in the second
rightmost IR in Figure 2, the values are quantized from float32 to small
integers. Our quantization pass has the capability to conduct a mixed-
precision search for each parameter in the model, which allows for fine-
grained optimization of parameters and maximizes the benefits of quantization
at scale. A detailed case study on mixed-precision quantization is presented
in Section V-A.

The hardware transformation can also be conducted at both levels. In Figure 2,
we show an example of a design space exploration (DSE) pass. This pass
explores the hardware design metrics using the provided specifications, such
as available hardware resources, and establishes efficient constraints for
hardware mapping. There are various design constraints to be explored for each
node. For simplicity, we will only highlight the key hardware attributes of a
linear layer:

  * •

The toolchain attribute specifies the hardware synthesis approach used, which
currently employs pre-defined hardware components provided by MASE.

  * •

MASE offers a range of IP cores, and the IP core attribute indicates the
specific component to be utilised if a pre-defined hardware component is used.

  * •

Tensors computed by this linear layer are large. To maintain high throughput,
matrices are partitioned into tiles and processed in a pipelined manner. The
size and depth attributes specify the tile size and the number of partitions
for each parameter, input, and output.

  * •

The order attribute defines the order of tiles fed into the hardware kernel
across multiple dimensions.

  * •

The interface attribute determines the hardware interface for each data port,
with the current configuration mapping inputs and outputs to handshake
interfaces.

  * •

The internal parameters can be stored in BRAM or DRAM, depending on the use
cases. The map attribute specifies how weights are stored for the linear
layer.

A detailed explanation of the DSE approach on how to determine these
attributes is explained in Section IV-C2.

As a software and hardware co-design tool, MASE facilitates the interleaving
of software and hardware co-optimization by utilizing the same MASE IR for
both abstractions. The passes shown in Figure 2 can be executed in any order,
allowing for efficient transformation and creating opportunities for
synergistic effects between different passes.

###  IV-C System Synthesis

In order to synthesize an efficient accelerator system, MASE explores the
hardware parameters within the MASE IR and optimizes the hardware design using
several optimization passes. Firstly, we demonstrate three possible approaches
for synthesizing ML accelerators in MASE: utilizing  pre-defined parameterized
blocks available in MASE (in either RTL or HLS code), incorporating user-
defined blocks, or directly utilizing HLS-generated blocks through MLIR and
Vivado HLS [40]. Secondly, we explain how MASE explores the hardware
architecture using these blocks. Lastly, we illustrate how the exploration
engine in MASE determines the optimized accelerator design.

####  IV-C1 Hardware Back End

The hardware backend of MASE takes a model in MASE IR and translates it into a
hardware system. In the MASE IR, each MASE node can be mapped into hardware
using one of three approaches. First, MASE contains a set of predefined
parameterized blocks in its internal hardware library. Each block has a set of
inputs and a set of outputs with handshake interfaces. These blocks are
parameterized and manually implemented as templates in RTL or HLS code. If an
operation has been defined in the internal hardware library, it could be
directly synthesized into one of the pre-defined components with custom
parameters. An advantage of such a component is that these components have
been optimized for high performance and area efficiency. However, the internal
hardware library requires manpower to develop and takes a long time to support
new operations in state-of-the-art ML models.

(a) MASE HLS flow

(b) HLS wrapper

Figure 3:  New models often contain new or custom ops. In order to solve the
synthesis ability challenge, MASE supports lowering MASE IR to MLIR so
arbitrary ML models can be mapped to hardware with the help of HLS. MASE has a
set of MLIR passes shown on the left that automatically wraps the HLS hardware
shown on the right for integration into a data flow architecture.

1) Enabling reusability by supporting external block

A second approach is to import user-defined hardware components. There have
been a variety of ML accelerator designs that show high performance and energy
efficiency for a particular ML model. These accelerators often contain
reusable hardware blocks. To use these blocks, MASE enables the integration of
external hardware blocks if each data port is implemented using a handshake
interface. A user-defined hardware block is treated as a black box. With the
parameters of the custom blocks provided, the parallelism of these blocks can
be explored with other blocks in the DSE pass.

2) Enabling synthesizability by supporting MLIR-HLS end

However, new models often contain new or custom ops. Manual hardware
development is slow and cannot catch up with the software model evolution. The
absence of a single operation can fail the hardware synthesis of the entire
model. To overcome this challenge, MASE supports the hardware synthesis of
arbitrary ML models by mapping new operations into hardware using the MLIR-HLS
flow. Figure 3 illustrates the HLS flow from MASE IR to hardware.  In MASE,
each MASE node can be transformed by the Torch-MLIR front end [30] into MLIR,
specifically the linalg abstraction at the tensor level. It can then be
successively transformed into the affine abstraction using open-sourced MLIR
passes and then translated into HLS code using MASE emit-c pass. These HLS
blocks are modularised and connected to other hardware blocks using the
handshake interface.

Here we use AMD Xilinx Vivado HLS [40] as MASE HLS back end. Vivado HLS
generates hardware with a block interface by default, also called latency-
sensitive design. Directives of synthesising a handshake interface for the
input and output require human efforts. MASE currently has two passes on the
MLIR end: 1) automatically inserting such directives using static analysis; 2)
HLS code and wrapper generation from MLIR.

Here, we use AMD Xilinx Vivado HLS [40] as our HLS backend. By default, Vivado
HLS generates hardware with a block interface, which is referred to as a
latency-sensitive design. However, directives for synthesising a handshake
interface for the input and output necessitate manual intervention. In MASE,
we currently have two passes on the MLIR end for enabling hardware generation:
1) the automatic insertion of these handshake directives, and 2) the
generation of HLS code and wrappers from MLIR.

TABLE III: Hardware block types in this work. Hardware Module Class | Percentage
---|---
Pre-defined | 75.5%
Directly through MLIR-HLS | 10.8%
User-defined | 13.7%

The MLIR-HLS stage is considered as an exit point in the MASE flow, as it
generates HLS code to enable the hardware synthesis capability of MASE.
Ongoing research efforts on HLS optimization in MLIR [43, 41] can be applied
in MASE for further improving the design quality of the HLS hardware.
However, these optimizations are beyond the scope of this paper, as our focus
is primarily on software and hardware optimization in the MASE IR. The
hardware generated by vanilla MLIR-HLS still exhibits a significant
performance gap compared to manually optimized RTL or HLS hardware.
Nonetheless, during our experiments, we observed that the proportion of such
hardware is minimal, as most operations are directly supported by MASE, as
indicated in Table III. The performance overhead is limited and is expected to
be further reduced with dedicated engineering efforts.

$10^{5}$$10^{6}$$10^{7}$$10^{0}$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$#
device# device$\leq$ 45-32AreaPerformance (a) resnet50

$10^{6}$$10^{7}$$10^{8}$$10^{9}$$10^{0}$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$#
device# device# device$\leq$ 45-3233-600AreaPerformance (b) bert-base-uncased

$10^{6}$$10^{7}$$10^{8}$$10^{9}$$10^{0}$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$#
device# device# device$\leq$ 45-3233-600AreaPerformance (c) facebook/opt-350m

Figure 4: Design space exploration of each model over different resources. The
x-axis represents area (in LUTs) and the y-axis represents performance (in
FPS). The blue dots represent the Pareto front design points.  The Pareto
front designs are defined as the design where the throughput between every two
consecutive nodes is balanced.

####  IV-C2 Design Space Exploration

Here we introduce the DSE engine in MASE. The DSE problem can be formalised
using the following terms:

  * •

$M=\\{n_{0},n_{1},n_{2}...\\}$ denotes the set of all the nodes;

  * •

$S:n\rightarrow\\{s_{0},s_{1}...\\}$ denotes the search space of node $n$;

  * •

$O\subseteq M\times S$ denotes a single design point of $M$;

MASE takes a model and explores all the search space $S$ for each MASE node.
Given a budget for hardware resources and cross-device memory bandwidth, the
optimiser searches for an efficient $O$ to maximise the system throughput  in
a greedy form.

As mentioned, MASE contains a set of pre-defined components. The throughput
and area of nodes that use these components can be directly obtained using the
internal regression model in MASE. The user-defined and HLS-generated
components need to be analyzed from synthesis reports. The synthesis time
overhead is relatively small because there were a small number of user-defined
and HLS-generated components, as shown in Table III.

1) Maximise throughput

The DSE process can be divided into five steps. It starts with the fully
parallelized design and aims to efficiently reduce the area to a size that can
fit onto the given devices. Let $\theta(n,s)$ represent the maximum achievable
throughput of a node instance $(n,s)$. Then the fully parallelized design $O$
satisfies the following conditions:

$\displaystyle\theta_{n}=\max_{s\in S(n)}\theta(n,s)$ (1)
$\displaystyle\forall n\in M\Rightarrow\theta(n,s)=\theta_{n}\wedge(n,s)\in O$
(2)

These conditions ensure that all nodes are paired with the configuration that
provides maximum throughput.

2)  Rate balancing

The nodes are fully parallelized, but some of them may underperform, meaning
that the actual throughput at runtime is significantly lower than the target
throughput. To address this, we can reduce the parallelism of these nodes
without affecting the overall throughput. This approach is known as rate
balancing. We adopt the analysis provided by Venieris and Bouganis [36] for
estimating the actual throughput in dataflow hardware. Let $\theta_{r}(n,s)$
represent the actual throughput of a node instance $(n,s)$. After rate
balancing, each node in the balanced design $O^{\prime}$ is configured with a
parallelism level close to its actual throughput.

$\displaystyle\theta_{n}^{\prime}=\min\\{\theta(n,s^{\prime})|\theta(n,s^{\prime})\geq\theta_{r}(n,s)\\}$
(3) $\displaystyle\forall n\in M\wedge(n,s)\in
O\Rightarrow\theta(n,s^{\prime})=\theta_{n}^{\prime}\wedge(n,s^{\prime})\in
O^{\prime}$ (4)

Constraint 4 ensures that all nodes in the design are computing efficiently in
a pipeline. We define such design points as Pareto-front hardware designs.

TABLE IV:  Area estimation error for internal hardware blocks.

Node Types | Errors
---|---
Linear | 8.1%
Conv2d | 11.3%
ReLU | 2.7%
Softmax | 4.1%
Layernorm | 3.7%

3)  Partitioning and bandwidth check

However, these design points are target-independent. MASE searches among these
points and identifies an efficient design that can be implemented on the
target hardware system, taking into account two constraints: resource and
bandwidth. Here are the definitions of the terms used:

  * •

$B$ denotes the maximum cross-device bandwidth.

  * •

$R$ denotes the area budget per device.

  * •

$N$ denotes the number of devices.

Firstly, MASE attempts to map a balanced design point onto the system by
partitioning the MASE IR, represented as a graph, into $N$ subgraphs. Our pass
traverses from the input nodes towards the output nodes and constructs a set
of subgraphs $D$ from $M$, where $|D|=N$ and $\forall d\in D\ldotp d\subseteq
O^{\prime}$. Let $A(n,s)$ denote the area of a node instance $(n,s)$. The
resource constraint, where each subgraph must fit onto a single device, is
expressed as follows:

$\displaystyle\forall d\in D\ldotp(n,s)\in d\Rightarrow\sum_{n\in
d}A(n,s)+\delta\leq R$ (5)

Here, $\delta$ represents the area of the cross-device interconnect
components, which can be obtained from the regression model in MASE, along
with other predefined components.

Secondly, MASE also verifies whether the cross-device communication bandwidth
can accommodate the data throughput between subgraphs. Let $I(d)\subseteq d$
and $I^{\prime}(d)\subseteq d$ represent the sets of input and output nodes of
a subgraph $d$. The bandwidth constraint can be expressed as follows:

$\displaystyle\forall d\in D\ldotp(n,s)\in I(d)\Rightarrow\sum_{n\in
I(d)}\theta_{r}(n,s)\leq B$ (6) $\displaystyle\forall d\in D\ldotp(n,s)\in
I^{\prime}(d)\Rightarrow\sum_{n\in I^{\prime}(d)}\theta_{r}(n,s)\leq B$ (7)

If both the resource and bandwidth constraints are satisfied, then the design
point $O^{\prime}$ is considered efficient.

Figure 5: An example of mapping a model onto two devices. TABLE V: The
specifications for the ML models evaluated in this work. float32 = 32-bit
floating-point. int8 = 8-bit fixed point. ft = fine-tuned. ∗The accuracy of
models for language modelling was measured in perplexity (smaller is better).

| Category | Task | Name | Sub-style | Dataset | FLOPs (G) | Parameters (M) | Accuracy/perplexity
---|---|---|---|---|---|---|---|---
f32 | f32 ft | int8 | int8 ft
1 | CNN | Classification | ResNet | resnet18 | ImageNet | 3.64 | 11.7 | 69.6 | - | 58.6 | 68.5
2 | resnet50 | 8.21 | 25.6 | 75.8 | - | 69.4 | 78.1
3 | MobileNetV2 | mobilenetv2 | 0.615 | 3.50 | 72.0 | - | 58.8 | 70.8
4 | MobileNetV3 | mobilenetv3_small | 0.117 | 2.54 | 67.4 | - | - | 60.1
5 | mobilenetv3_large | 0.445 | 5.48 | 75.2 | - | - | 69.9
6 | Transformers | Question Answering | BERT | bert-base-cased | QNLI | 22.4 | 108 | 90.5 | - | 49.5 | 75.3
7 | bert-large-cased | 79.0 | 334 | 92.7 | - | 51.3 | 56.0
8 | Language Modelling | OPT | facebook/opt-125m | WikiText2 | 32.3 | 125 | 60.3∗ | 21.4∗ | 553∗ | 27.9∗
9 | facebook/opt-350m | 85.8 | 331 | 48.7∗ | 18.3∗ | 7.42k∗ | 26.0∗
10 | facebook/opt-1.3b | 339 | 1316 | 32.1∗ | - | 8.28k∗ | -

5) Decrement parameters

If either of the constraints fails to be satisfied, MASE employs a strategy to
gradually decrease the parallelism of the design. This process involves
reducing the parallelism of an input node $n$ in $M$ by a small step. MASE
then iterates through the re-balancing process described in step 2) until a
valid design point is achieved. This iterative approach allows MASE to find a
design that fulfills the resource and bandwidth requirements.

Our DSE approach allows us to thoroughly examine the entire design space
across all numbers of devices and efficiently maps the model onto any number
of devices for acceleration. We utilise QSFP28 as the interface for
communication between FPGA devices, ensuring that the communication throughput
and latency between every device are consistent and predictable. Figure 4
depicts the design spaces for three ML models. The blue points indicate the
Pareto front design points defined by Constraint 4. The figure demonstrates
that MASE can map these models onto hundreds of FPGAs for high-performance
computing and onto a small number of FPGAs for area-efficient computing. The
throughput of the model increases exponentially with the total area. However,
a saturation point exists for the throughput when the area reaches a certain
size, suggesting that the hardware system is memory-bound.

The accuracy of our regression model is high. Table IV shows the errors in the
estimated area of the key components used for our experiments. This enables
the design to be efficiently mapped onto each device based on the given
resource budget. The throughput model is cycle accurate as there is no input-
dependent control flow in the hardware, and all the hardware behaviour is
predictable. Figure 5 shows an example of bert-base-uncased being mapped onto
two U250 FPGA devices. The small blue blocks represent the QSFP28 component
for data transmission. The point-to-point cross-device link between two
devices has a maximum bandwidth of 100 Gbps. The area of the first device is
efficiently utilised, and the second device only uses 32% because all the
kernels have been mapped.

###  IV-D Testing Framework

Figure 6: Software and Hardware Co-simulation.

Most HLS tools do not need a hardware testing framework if the tool is
correctly implemented and the software model has been verified. However, MASE
needs a testing framework because the correctness of the user-defined hardware
block might cause errors. In order to test and verify the correctness of the
generated hardware system, MASE runs software and hardware co-simulation to
check the equivalence of software and hardware implementation.

Figure 6 illustrates the co-simulation flow in MASE. The left side of the
figure shows the software testing flow, and the right side of the figure shows
the hardware testing flow. For the software testing flow, the model in MASE IR
takes a set of data from the validation dataset and runs inference on GPUs.
For the hardware testing flow, the model in MASE IR is translated into a
hardware system. The hardware testbench is also generated, taking the same
test data as the software flow for hardware simulation. MASE calls an external
hardware simulator (AMD Xilinx Vivado XSIM simulator [3]). Both the software
model and the corresponding hardware system should return the same results or
results with small discrepancies.111Small discrepancies between the software
and hardware results might happen when the model contains floating-point
operations. MASE compares the results for correctness check.  The hardware
testbench tests the whole system, including cross-device components. MASE also
provides a user option to simulate without these components for a fast
behaviour simulation.

##  V Experiments

We evaluated MASE on ten ML models, including classic CNN models and new
transformer models. The detailed specifications of these models are shown in
Table V. We obtained the total clock cycles from the MASE co-simulator, and
the area results were extracted from the Post Synthesis report in Vivado. The
FPGA family we used for the result measurements is Alveo U250, and the version
of Xilinx software employed is 2020.2.

###  V-A Mixed-Precision Quantization Co-design

As mentioned in Section IV-B, MASE explores model quantization before
deploying the models on hardware. We adopt the 8-bit fixed-point
representation [10] as the default setup, referred to as “int8” in the rest of
this paper. We report the accuracy of the quantized model in Table V,
including both post-training and fine-tuning results.

It is well-known that applying a uniform bit width to the entire network may
not be optimal. Previous literature [37] has highlighted that the dynamic
range of data varies significantly across different layers of the same
network. This observation motivates the exploration of mixed-precision
arithmetic. MASE provides users with the ability to investigate mixed-
precision arithmetic through our efficient IR.

In this example, we demonstrate how MASE can be utilized to automatically
search for the optimal bit width of each layer in a hardware-aware manner. We
employ the Tree-structured Parzen Estimator (TPE) [5] as the searching
algorithm. For each explored design point, MASE automatically collects
information on both the model accuracy and hardware resource utilisation.

$3.16$$3.98$$5.01$$6.31$$7.94$$1$$1.5$$2$LossFPS/WMASEGPU Figure 7:
Traditional mixed-precision quantization search only targets minimum loss.
This returns a set of solutions for facebook/opt-125m, shown as green points,
but they may not be efficient in hardware. MASE uses the model in DSE and
determines the one (the top-right green point) that has comparable energy
efficiency with GPU. The large loss between MASE and GPU is due to post-
training quantization.

Traditional mixed-precision quantization searches for small total numbers of
bits with minimum loss. For this example, the analyser returns 23 optimal-like
designs at minimal loss. However, these designs might not be all hardware
efficient. Figure 7 illustrates the search results for facebook/opt-125m. From
the figure, we observe the following:

  * •

The loss of our work is worse than GPU because we only do standard
quantization without fine-tuning.

  * •

The total bits of the model might be the same for all the searched results but
they have shown different energy efficiency.

  * •

The best design point at the top right of the figure has better energy
efficiency than the GPU.

Particularly, Figure 8 shows the distribution of the bits over different
layers in the top-right design point in Figure 7. The layers are repeated
because there are 12 building blocks. More than half of the bit widths have
been quantized to less than 4 bits, which significantly improves energy
efficiency.

###  V-B Exploring Efficient Custom Arithmetic

Algorithm 1 A Transformer Layer in OPT.

1:$X$ $\triangleright$ Input features

2:$H$ $\triangleright$ Number of heads

3:$X_{n}\leftarrow LayerNorm(X)$

4:for $i\in[0,H)$ do

5: $Q_{i}\leftarrow W_{Q_{i}}X_{n}$

6: $K_{i}\leftarrow W_{K_{i}}X_{n}$

7: $V_{i}\leftarrow W_{V_{i}}X_{n}$

8: $A_{i}\leftarrow\frac{K_{i}^{T}{Q_{i}}}{\sqrt{d_{k}}}$

9: $\hat{A}_{i}\leftarrow softmax(A_{i},axis\leftarrow-1)$

10: $B_{i}\leftarrow V_{i}\hat{A}_{i}$

11:end for

12:$B_{c}\leftarrow concat(B_{0}..B_{H-1})$

13:$B_{0}\leftarrow W_{0}B_{c}+b_{0}$

14:$B_{n}\leftarrow LayerNorm(B_{0}+X_{n})$

15:$B_{1}\leftarrow act(W_{1}B_{n}+b_{1}))$

16:$B_{2}\leftarrow W_{2}B_{1}+b_{2}$

17:$O\leftarrow B_{2}+B_{n}$

18:return $O$

$0$$0.2$$0.4$$0.6$$0.8$$1$$X$$W_{Q}$$Q$$W_{K}$$K$$W_{V}$$V$$\hat{A}$$B$$W_{0}$$B_{0}$$B_{n}$$W_{1}$$B_{1}$$W_{2}$$B_{2}$Percentage
$\times$100%Up to 4 bits5 or 6 bits7 or 8 bits Figure 8:  The distribution of
operation precision across different building blocks in facebook/opt-125m.

Here we show how to use custom arithmetic operations as user-defined blocks
and integrate them into MASE for hardware architecture exploration. We use
Microsoft Floating Point (MSFP) [13] in this section. It is a floating point
representation sharing an exponent across vector elements. An MSFP vector
takes the form as follows:

$\displaystyle
2^{e_{shared}}[(-1)^{s_{0}}m_{0},(-1)^{s_{1}}m_{1},\dots,(-1)^{s_{n-1}}m_{n-1}]$
(8)

where $n$ signed mantissa $(-1)^{s_{i}}m_{i}$, $i=0,1,\dots,n-1$ scaled by the
same exponent ${e_{shared}}$ ($n$ is the so-called bounding box size) [13].
The shared exponent enables efficient data size by reducing the average bit
width. Additionally, it reduces the number of bits when computing matrix
multiplication, leading to potentially better energy efficiency. An example of
an 8-bit exponent and 4-bit value MSFP value is shown in Figure 9.

In this example, we seek to exploit MSFP operations in BERT using MASE. We
provide similar tunable parameters as shown in Figure LABEL:fig:linear_example
so it can be explored in the MASE DSE. The sharing constraint is set to 16,
and the bit width is configured to 4. That means every 16 4-bit values share
an 8-bit exponent.

Figure 9:  An example of MSFP format, where multiple numbers in the same block
share the same exponent. TABLE VI: Evaluation of MASE on transformers. ∗means
perplexity. We highlight the best results in comparison.

Model | bert-base-cased | bert-large-cased | facebook/opt-125m | facebook/opt-350m | facebook/opt-1.3b
---|---|---|---|---|---
Device Class | GPU | FPGA | FPGA | GPU | FPGA | FPGA | GPU | FPGA | FPGA | FPGA | GPU | FPGA | GPU | FPGA
Platform | RTX 3090 | U250 | U250 | RTX 3090 | U250 | U250 | RTX 3090 | U250 | U250 | U250 | RTX 3090 | U250 | RTX 3090 | U250
Device Count | 1 | 27 | 25 | 1 | 20 | 21 | 1 | 29 | 32 | 32 | 1 | 22 | 1 | 30
Quantization | float32 | int8 | MSFP | float32 | int8 | MSFP | float32 | int8 | MSFP | mixed | float32 | int8 | float32 | int8
Accuracy | 90.5 | 75.3 | 90.0 | 92.7 | 56.0 | 91.3 | 21.4∗ | 27.9∗ | 22.9∗ | 255∗ | 18.3∗ | 26.0∗ | 32.1∗ | 8.28k∗
MLUTs | - | 45 | 43 | - | 34 | 36 | - | 50 | 55 | 54 | - | 38 | - | 51
Fmax - MHz | - | 267 | 267 | - | 267 | 267 | - | 267 | 267 | 267 | - | 267 | - | 345
Power (W) | 341 | 1683 | 1482 | 343 | 1248 | 1288 | 343 | 1812 | 1901 | 1934 | 334 | 1372 | 340 | 1872
Frame Rate (FPS) | 1090 | 2716 | 6953 | 60 | 1019 | 1273 | 706 | 2716 | 6953 | 7243 | 106 | 509 | 28 | 164
Throughput (GOPS) | 24381 | 60740 | 155493 | 4734 | 80423 | 100553 | 15801 | 87594 | 224241 | 233584 | 9161 | 43709 | 9335 | 55708
GOPS/kLUT | - | 1.3 | 3.6 | - | 2.4 | 2.8 | - | 1.8 | 4.1 | 4.3 | - | 1.2 | - | 1.1
GOPS/W | 71.5 | 36.1 | 104.9 | 13.8 | 64.4 | 78.1 | 46.1 | 48.3 | 118.0 | 120.8 | 27.4 | 31.9 | 27.5 | 29.8
FPS/W | 3.2 | 1.6 | 4.7 | 0.2 | 0.8 | 1.0 | 2.1 | 1.5 | 3.7 | 3.8 | 0.3 | 0.4 | 0.08 | 0.09

TABLE VII: Evaluation of MASE on CNN models. We highlight the best results in
each dimension.

Model | resnet18 | resnet50 | mobilenetv2 | mobilenetv3_small | mobilenetv3_large
---|---|---|---|---|---
Work | [34] | - | Ours | [34] | - | Ours | [34] | - | Ours | - | Ours | - | Ours
Device Class | FPGA | GPU | FPGA | FPGA | GPU | FPGA | FPGA | GPU | FPGA | GPU | FPGA | GPU | FPGA
Platform | ZCU102 | RTX 3090 | U250 | ZCU102 | RTX 3090 | U250 | ZCU102 | RTX 3090 | U250 | RTX 3090 | U250 | RTX 3090 | U250
Device Count | 1 | 1 | 6 | 1 | 1 | 13 | 1 | 1 | 2 | 1 | 1 | 1 | 2
Quantization | Mixed | float32 | int8 | Mixed | float32 | int8 | Mixed | float32 | int8 | float32 | int8 | float32 | int8
Accuracy | 70.5 | 69.6 | 68.5 | 77.3 | 75.8 | 78.1 | 65.7 | 72.0 | 70.8 | 67.4 | 60.1 | 75.2 | 69.9
DSP | 2092 | - | - | 2092 | - | - | 2092 | - | - | - | - | - | -
kLUTs | 180.1 | - | 6535 | 180.1 | - | 11437 | 180.1 | - | 1768 | - | 792 | - | 1856
Area Factor | 389.3 | - | 6535 | 389.3 | - | 11437 | 389.3 | - | 1768 | - | 792 | - | 1856
Fmax - MHz | 150 | - | 250 | 150 | - | 250 | 150 | - | 250 | - | 280 | - | 240
Power (W) | 13 | 153 | 427 | 13 | 262 | 890 | 13 | 211 | 137 | 126 | 56 | 204 | 131
Frame Rate (FPS) | 215 | 4940 | 4725 | 109 | 1665 | 4340 | 538 | 4550 | 4893 | 16308 | 5488 | 5958 | 1813
Throughput (GOPS) | 779 | 17963 | 17182 | 891 | 13675 | 35635 | 320 | 2798 | 3009 | 1902 | 640 | 2651 | 807
GOPS/Area Factor | 2.0 | - | 2.6 | 2.3 | - | 3.1 | 0.8 | - | 1.7 | - | 0.8 | - | 0.4
GOPS/W | 60.4 | 117.4 | 40.2 | 69.1 | 52.2 | 40.0 | 24.8 | 13.3 | 22.0 | 15.1 | 11.4 | 13.0 | 6.2
FPS/W | 16.7 | 32.3 | 11.1 | 8.5 | 6.4 | 4.9 | 41.7 | 21.6 | 35.8 | 129.4 | 98.0 | 29.2 | 13.8

The results of MSFP integration for BERT are shown in Table VI. From the
table, we made the following observations:

  * •

Quantizing BERT to fixed-point has lost significant accuracy. This is because
the variation of the data is huge and cannot fit into the 8-bit range.

  * •

The accuracy of using MSFP is comparable with the floating point version. That
is because the MSFP still preserves a large range of data values benefiting
from its floating point representation, although the average bit widths are
smaller than 8 bits.

  * •

The performance of the MSPF implementation is significantly higher than the
GPU results and has shown the best energy efficiency. That is because the low
bit widths enable more data transfer to the FPGA, which was the performance
bottleneck of the hardware system. Also, the arbitrary precision enables more
power efficiency compared to the fixed architecture of GPUs.

As shown above, MASE enables users to fast prototype new arithmetic components
and integrate them into a large model for systematical exploration. This eases
the complexity in large hardware system design and significantly improves the
hardware development process.

###  V-C Overall Results

Table VI shows the overall results for transformers. From the table, we made
the following observations:

  * •

The accuracy of quantized facebook/opt-1.3b is significantly worse than the
floating point results. This is because the accuracy was not fine-tuned
because of out-of-memory  errors in our GPU server.

  * •

Overall, MSFP has shown the best performance and energy efficiency. This could
improve hardware performance if integrated into the next generation of ML
accelerators.

  * •

The results produced by vanilla MASE  show high throughput with extremely
large resources. This shows that the many accelerator systems generated by
MASE can scale well with the number of devices as the cross-device
communication does not have interconnect restrictions.

  * •

The bit width used by vanilla MASE is 8 bits, which is inefficient for some
models. This reduces the energy efficiency of the hardware. Quantization
search could be used for further improvements, but it takes a long time for
large models.

Table VII shows the overall results for CNN models. From the table, we made
the following observations:

  * •

The ML accelerators for CNN have been widely studied and have shown
competitive results. Here we can show that MASE can still generate efficient
hardware with competitive performance.

  * •

The results for mobilenetv3 models are not as competitive as related works,
because the model is relatively small, and there are fewer opportunities to
exploit model parallelism.

##  VI Conclusions

ML models today are evolving rapidly and growing significantly. This makes
designing the next ML accelerators for new and large models challenging. In
order to reduce the gap between the development speed of software ML models
and hardware accelerators, we propose an efficient and scalable hardware
system exploration tool named MASE.

We propose an efficient IR called MASE IR that allows the software model and
the hardware architecture to be expressed at the same abstraction level. This
work represents the initial step of the MASE framework, enabling ML
accelerator system exploration within a software compiler flow. MASE presents
various opportunities for next-generation ML accelerator exploration,
including hardware-aware network architecture search (NAS) and custom
quantization scheme search.

As examples of these use cases, we present two case studies demonstrating how
to utilize MASE for exploring  efficient quantization of ML models and
incorporating newly proposed arithmetic operators to enhance the efficiency of
an existing accelerator system. MASE facilitates end-to-end hardware synthesis
flow for large models. Our aim is for MASE to contribute to accelerating the
process of designing next-generation accelerators from months to weeks.

## References

  * [1] M. S. Abdelfattah, Ł. 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 _2020 57th ACM/IEEE Design Automation Conference (DAC)_. IEEE, 2020, pp. 1–6.
  * [2] L. Adolphs, C. Buck, M. Chen Huebscher, M. Ciaramita, L. Espeholt, T. Hofmann, Y. Kilcher, S. Rothe, P. G. Sessa, L. Sestorain Saralegui _et al._ , “Boosting Search Engines with Interactive Agents,” _Transactions on Machine Learning Research_ , 2022.
  * [3] AMD Xilinx, “Vivado,” 2023. [Online]. Available: https://www.xilinx.com/products/design-tools/vivado.html
  * [4] J. Bai, F. Lu, K. Zhang _et al._ , “Onnx: Open neural network exchange,” _GitHub repository_ , p. 54, 2019.
  * [5] J. Bergstra, R. Bardenet, Y. Bengio, and B. Kégl, “Algorithms for hyper-parameter optimization,” _Advances in neural information processing systems_ , vol. 24, 2011.
  * [6] M. Blott, T. B. Preußer, N. J. Fraser, G. Gambardella, K. O’brien, Y. Umuroglu, M. Leeser, and K. Vissers, “Finn-r: An end-to-end deep-learning framework for fast exploration of quantized neural networks,” _ACM Trans. Reconfigurable Technol. Syst._ , vol. 11, no. 3, dec 2018. [Online]. Available: https://doi.org/10.1145/3242897
  * [7] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell _et al._ , “Language models are few-shot learners,” _Advances in neural information processing systems_ , vol. 33, pp. 1877–1901, 2020.
  * [8] Cadence, “Stratus High-Level Synthesis,” 2023. [Online]. Available: https://www.cadence.com/en_US/home/tools/digital-design-and-signoff/synthesis/stratus-high-level-synthesis.html
  * [9] K. Choi, D. Hong, H. Yoon, J. Yu, Y. Kim, and J. Lee, “Dance: Differentiable accelerator/network co-exploration,” in _2021 58th ACM/IEEE Design Automation Conference (DAC)_. IEEE, 2021, pp. 337–342.
  * [10] Y. Choukroun, E. Kravchik, F. Yang, and P. Kisilev, “Low-bit quantization of neural networks for efficient inference,” in _2019 IEEE/CVF International Conference on Computer Vision Workshop (ICCVW)_. IEEE, 2019, pp. 3009–3018.
  * [11] C. contributors, “Circt-based hls compilation flows, debugging, and cosimulation tools.” https://github.com/circt-hls/circt-hls, 2023.
  * [12] P. Coussy, D. D. Gajski, M. Meredith, and A. Takach, “An introduction to high-level synthesis,” _IEEE Design Test of Computers_ , vol. 26, no. 4, pp. 8–17, July 2009.
  * [13] B. Darvish Rouhani, D. Lo, R. Zhao, M. Liu, J. Fowers, K. Ovtcharov, A. Vinogradsky, S. Massengill, L. Yang, R. Bittner _et al._ , “Pushing the limits of narrow precision inferencing at cloud scale with microsoft floating point,” _Advances in neural information processing systems_ , vol. 33, pp. 10 271–10 281, 2020.
  * [14] Z. DeVito, “Torchscript: Optimized execution of pytorch programs,” _Retrieved January_ , 2022.
  * [15] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” _arXiv preprint arXiv:1810.04805_ , 2018.
  * [16] Z. Dong, Y. Gao, Q. Huang, J. Wawrzynek, H. K. So, and K. Keutzer, “Hao: Hardware-aware neural architecture optimization for efficient inference,” in _2021 IEEE 29th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)_. IEEE, 2021, pp. 50–59.
  * [17] J. Duarte, S. Han, P. Harris, S. Jindariani, E. Kreinar, B. Kreis, J. Ngadiuba, M. Pierini, R. Rivera, N. Tran _et al._ , “Fast inference of deep neural networks in fpgas for particle physics,” _Journal of Instrumentation_ , vol. 13, no. 07, p. P07027, 2018.
  * [18] F. Fahim, B. Hawks, C. Herwig, J. Hirschauer, S. Jindariani, N. Tran, L. P. Carloni, G. Di Guglielmo, P. Harris, J. Krupa _et al._ , “hls4ml: An open-source codesign workflow to empower scientific low-power machine learning devices,” _arXiv preprint arXiv:2103.05579_ , 2021.
  * [19] Y. Fu, Y. Zhang, Y. Zhang, D. Cox, and Y. Lin, “Auto-nba: Efficient and effective search over the joint space of networks, bitwidths, and accelerators,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 3505–3517.
  * [20] J. Gao, Y. Qian, Y. Hu, X. Fan, W.-S. Luk, W. Cao, and L. Wang, “Leta: A lightweight exchangeable-track accelerator for efficientnet based on fpga,” in _2021 International Conference on Field-Programmable Technology (ICFPT)_ , 2021, pp. 1–9.
  * [21] 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, pp. 4805–4815, 2020.
  * [22] D. M. Korngiebel and S. D. Mooney, “Considering the possibilities and pitfalls of generative pre-trained transformer 3 (gpt-3) in healthcare delivery,” _NPJ Digital Medicine_ , vol. 4, no. 1, p. 93, 2021.
  * [23] A. Kouris, S. I. Venieris, M. Rizakis, and C.-S. Bouganis, “Approximate LSTMs for time-constrained inference: Enabling fast reaction in self-driving cars,” _IEEE Consumer Electronics Magazine_ , vol. 9, no. 4, pp. 11–26, 2020.
  * [24] C. Lattner and V. Adve, “Llvm: A compilation framework for lifelong program analysis & transformation,” in _International symposium on code generation and optimization, 2004. CGO 2004._ IEEE, 2004, pp. 75–86.
  * [25] C. Lattner, M. Amini, U. Bondhugula, A. Cohen, A. Davis, J. Pienaar, R. Riddle, T. Shpeisman, N. Vasilache, and O. Zinenko, “Mlir: A compiler infrastructure for the end of moore’s law,” _arXiv preprint arXiv:2002.11054_ , 2020.
  * [26] C. Li, Z. Yu, Y. Fu, Y. Zhang, Y. Zhao, H. You, Q. Yu, Y. Wang, and Y. Lin, “Hw-nas-bench: Hardware-aware neural architecture search benchmark,” in _The 9th International Conference on Learning Representations 2021 (ICLR 2021)_ , 2021.
  * [27] Y. Li, C. Hao, X. Zhang, X. Liu, Y. Chen, J. Xiong, W.-m. Hwu, and D. Chen, “Edd: Efficient differentiable dnn architecture and implementation co-search for embedded ai solutions,” in _2020 57th ACM/IEEE Design Automation Conference (DAC)_. IEEE, 2020, pp. 1–6.
  * [28] M. Lin, P. Wang, Z. Sun, H. Chen, X. Sun, Q. Qian, H. Li, and R. Jin, “Zen-nas: A zero-shot nas for high-performance image recognition,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 347–356.
  * [29] H. Liu, K. Simonyan, and Y. Yang, “Darts: Differentiable architecture search,” _arXiv preprint arXiv:1806.09055_ , 2018.
  * [30] LLVM, “Torch-MLIR,” 2023. [Online]. Available: https://github.com/llvm/torch-mlir
  * [31] W. Niu, J. Guan, X. Shen, Y. Wang, G. Agrawal, and B. Ren, “Gcd2: A globally optimizing compiler for mapping dnns to mobile dsps,” in _2022 55th IEEE/ACM International Symposium on Microarchitecture (MICRO)_ , 2022, pp. 512–529.
  * [32] J. Reed, Z. DeVito, H. He, A. Ussery, and J. Ansel, “torch. fx: Practical program capture and transformation for deep learning in python,” _Proceedings of Machine Learning and Systems_ , vol. 4, pp. 638–651, 2022\.
  * [33] Siemens, “Catapult High-Level Synthesis and Verification,” 2023. [Online]. Available: https://eda.sw.siemens.com/en-US/ic/catapult-high-level-synthesis/
  * [34] M. Sun, Z. Li, A. Lu, Y. Li, S.-E. Chang, X. Ma, X. Lin, and Z. Fang, “Film-qnn: Efficient fpga acceleration of deep neural networks with intra-layer, mixed-precision quantization,” in _Proceedings of the 2022 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays_ , ser. FPGA ’22. New York, NY, USA: Association for Computing Machinery, 2022, p. 134–145. [Online]. Available: https://doi.org/10.1145/3490422.3502364
  * [35] M. Tan and Q. Le, “Efficientnet: Rethinking model scaling for convolutional neural networks,” in _International conference on machine learning_. PMLR, 2019, pp. 6105–6114.
  * [36] S. I. Venieris and C.-S. Bouganis, “fpgaconvnet: A framework for mapping convolutional neural networks on fpgas,” in _2016 IEEE 24th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)_ , 2016, pp. 40–47.
  * [37] K. Wang, Z. Liu, Y. Lin, J. Lin, and S. Han, “Haq: Hardware-aware automated quantization with mixed precision,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 8612–8620.
  * [38] W. Wang, E. Xie, X. Li, D.-P. Fan, K. Song, D. Liang, T. Lu, P. Luo, and L. Shao, “Pvt v2: Improved baselines with pyramid vision transformer,” _Computational Visual Media_ , vol. 8, no. 3, pp. 415–424, 2022.
  * [39] Q. Xiao and Y. Liang, “Towards agile dnn accelerator design using incremental synthesis on fpgas,” in _Proceedings of the 2022 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays_ , 2022, pp. 42–48.
  * [40] Xilinx Vivado HLS, 2022. [Online]. Available: https://www.xilinx.com/support/documentation-navigation/design-hubs/dh0012-vivado-high-level-synthesis-hub.html
  * [41] R. Xu, Y. Xiao, J. Luo, and Y. Liang, “Hector: A multi-level intermediate representation for hardware synthesis methodologies,” in _Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design_ , ser. ICCAD ’22. New York, NY, USA: Association for Computing Machinery, 2022. [Online]. Available: https://doi.org/10.1145/3508352.3549370
  * [42] S. Zhang, S. Roller, N. Goyal, M. Artetxe, M. Chen, S. Chen, C. Dewan, M. Diab, X. Li, X. V. Lin, T. Mihaylov, M. Ott, S. Shleifer, K. Shuster, D. Simig, P. S. Koura, A. Sridhar, T. Wang, and L. Zettlemoyer, “Opt: Open pre-trained transformer language models,” 2022.
  * [43] R. Zhao, J. Cheng, W. Luk, and G. A. Constantinides, “Polsca: Polyhedral high-level synthesis with compiler transformations,” in _2022 32nd International Conference on Field-Programmable Logic and Applications (FPL)_ , 2022, pp. 235–242.
  * [44] W. Zheng, W. Tang, L. Jiang, and C.-W. Fu, “SE-SSD: Self-ensembling single-stage object detector from point cloud,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2021, pp. 14 494–14 503.
  * [45] B. Zoph and Q. V. Le, “Neural architecture search with reinforcement learning,” _arXiv preprint arXiv:1611.01578_ , 2016.


On the Strong Ratio Limit Property for Discrete-Time Birth-Death Processes

On the Strong Ratio Limit Property
for Discrete-Time Birth-Death Processes††This paper is a contribution to the
Special Issue on Orthogonal Polynomials, Special Functions and Applications
(OPSFA14). The full collection is available at
https://www.emis.de/journals/SIGMA/OPSFA2017.html

Erik A. VAN DOORN

E.A. van Doorn

Department of Applied Mathematics, University of Twente,
P.O. Box 217, 7500 AE Enschede, The Netherlands<EMAIL_ADDRESS>http://wwwhome.math.utwente.nl/~doornea/

Received January 03, 2018, in final form May 13, 2018; Published online May
15, 2018

A sufficient condition is obtained for a discrete-time birth-death process to
possess the strong ratio limit property, directly in terms of the one-step
transition probabilities of the process. The condition encompasses all
previously known sufficient conditions.

(a)periodicity; birth-death process; orthogonal polynomials; random walk
measure; ratio limit; transition probability

60J80; 42C05

##  1 Introduction

In what follows $\mathcal{X}\equiv\\{X(n),\,n=0,1,\ldots\\}$ is a discrete-
time birth-death process on $\mathcal{N}\equiv\\{0,1,\dots\\}$, with
tridiagonal matrix of one-step transition probabilities

$\displaystyle P:=\begin{pmatrix}r_{0}&p_{0}&0&0&0&\ldots\cr
q_{1}&r_{1}&p_{1}&0&0&\ldots\cr
0&q_{2}&r_{2}&p_{2}&0&\ldots\cr\ldots&\ldots&\ldots&\ldots&\ldots&\ldots\cr\ldots&\ldots&\ldots&\ldots&\ldots&\ldots\cr\end{pmatrix}.$

Following Karlin and McGregor [6] we will refer to $\mathcal{X}$ as a random
walk. We assume throughout that $p_{j}>0$, $q_{j+1}>0$, $r_{j}\geq 0$, and
$p_{j}+q_{j}+r_{j}=1$ for $j\geq 0$, where $q_{0}:=0$. We let

$\displaystyle\pi_{0}:=1,\qquad\pi_{n}:=\frac{p_{0}p_{1}\cdots
p_{n-1}}{q_{1}q_{2}\cdots q_{n}},\qquad n\geq 1,$ (1.1)

and define the polynomials $Q_{n}$ via the recurrence relation

$\displaystyle xQ_{n}(x)=q_{n}Q_{n-1}(x)+r_{n}Q_{n}(x)+p_{n}Q_{n+1}(x),\qquad
n>1,$ $\displaystyle Q_{0}(x)=1,\qquad p_{0}Q_{1}(x)=x-r_{0}.$ (1.2)

Karlin and McGregor [6] have shown that the $n$-step transition probabilities

$\displaystyle P_{ij}(n):=\Pr\\{X(n)=j\,|\,X(0)=i\\}=(P^{n})_{ij},\qquad n\geq
0,\qquad i,j\in\mathcal{N},$

may be represented in the form

$\displaystyle P_{ij}(n)=\pi_{j}\int_{[-1,1]}x^{n}Q_{i}(x)Q_{j}(x)\psi(dx),$
(1.3)

where $\psi$ is the (unique) Borel measure on the interval $[-1,1]$, of total
mass 1 and with infinite support, with respect to which the polynomials
$Q_{n}$ are orthogonal. Adopting the terminology of [3] we will refer to the
measure $\psi$ as a random walk measure. Of particular interest to us is
$\eta:=\sup\operatorname{supp}(\psi)$, the largest point in the support of the
random walk measure $\psi$, which may also be characterized in terms of the
polynomials $Q_{n}$ by

$\displaystyle x\geq\eta\ \Longleftrightarrow\ Q_{n}(x)>0\qquad\mbox{for all}\
\ n\geq 0$ (1.4)

(see, for example, Chihara [1, Theorem II.4.1]). We will see in the next
section that $\eta>0$.

The random walk $\mathcal{X}$ is said to have the strong ratio limit property
$($SRLP$)$ if the limits

$\displaystyle\lim_{n\to\infty}\frac{P_{ij}(n)}{P_{kl}(n)},\qquad
i,j,k,l\in\mathcal{N},$ (1.5)

exist simultaneously. The SRLP was introduced in the more general setting of
discrete-time Markov chains on a countable state space by Orey [8] and Pruitt
[9], but the problem of finding conditions for the limits (1.5) to exist in
the specific setting of random walks had been considered before in [6]. A
satisfactory and comprehensive solution to the problem of finding conditions
for the SRLP is still lacking, even in the relatively simple setting at hand.
So it remains a challenge to find necessary and/or sufficient conditions. For
more information on the history of the problem we refer to [5] and [7].

In [5, Theorem 3.1] a necessary and sufficient condition for the random walk
$\mathcal{X}$ to have the SRLP has been given in terms of the associated
random walk measure $\psi$. Namely, letting

$\displaystyle
C_{n}(\psi):=\frac{\int_{[-1,0)}(-x)^{n}\psi(dx)}{\int_{(0,1]}x^{n}\psi(dx)},\qquad
n\geq 0,$ (1.6)

the limits (1.5) exist simultaneously if and only if

$\displaystyle\lim_{n\to\infty}C_{n}(\psi)=0,$ (1.7)

in which case we have

$\displaystyle\lim_{n\to\infty}\frac{P_{ij}(n)}{P_{kl}(n)}=\frac{\pi_{j}Q_{i}(\eta)Q_{j}(\eta)}{\pi_{l}Q_{k}(\eta)Q_{l}(\eta)},\qquad
i,j,k,l\in\mathcal{N}.$

Note that the denominator in (1.6) is positive since $\eta>0$, so that
$C_{n}(\psi)$ exists and is nonnegative for all $n$. Some sufficient
conditions for (1.7) – and, hence, for $\mathcal{X}$ to possess the SRLP – are
also given in [5]. In particular, [5, Theorem 3.2] tells us that

$\displaystyle\lim_{n\to\infty}|Q_{n}(-\eta)/Q_{n}(\eta)|=\infty\ \Rightarrow\
\lim_{n\to\infty}C_{n}(\psi)=0.$ (1.8)

The reverse implication is conjectured in [5] to be valid as well.

In this paper we will prove a sufficient condition for $\mathcal{X}$ to have
the SRLP directly in terms of the one-step transition probabilities.
Concretely, we will establish the following result.

######  Proposition 1.1.

If the random walk $\mathcal{X}$ satisfies

$\displaystyle\sum_{j\geq
0}\frac{1}{p_{j}\pi_{j}}\sum_{k=0}^{j}r_{k}\pi_{k}=\infty,$ (1.9)

then $\lim\limits_{n\to\infty}|Q_{n}(-\eta)/Q_{n}(\eta)|=\infty$.

Together with (1.8) this result immediately leads to the following.

######  Theorem 1.2.

If the random walk $\mathcal{X}$ satisfies (1.9) then $\mathcal{X}$ possesses
the SRLP.

We will see that Theorem 1.2 encompasses all previously obtained sufficient
conditions for the SRLP.

The proof of Proposition 1.1 will be based on three lemmas. Lemma 2.1 and a
number of preliminary results related to the polynomials $Q_{n}$ and the
orthogonalizing measure $\psi$ are collected in the next section. Two further
auxiliary lemmas are established in Section 3. The actual proof of Proposition
1.1 and some concluding remarks can be found in Section 4, which also contains
an example showing that (1.9) is not necessary for the SRLP.

##  2 Preliminaries

Whitehurst [11, Theorem 1.6] has shown that the random walk measure $\psi$
satisfies

$\displaystyle\int_{[-1,1]}xQ_{n}^{2}(x)\psi(dx)\geq 0,\qquad n\geq 0,$ (2.1)

and, conversely, that any Borel measure $\psi$ on the interval $[-1,1]$, of
total mass 1 and with infinite support, is a random walk measure if it
satisfies (2.1) (see also [3, Theorem 1.2]). Evidently, (2.1) implies
$\eta=\sup\operatorname{supp}(\psi)>0$, but it can actually be shown (see, for
example, [1, Corollary 2 to Theorem IV.2.1]) that

$\displaystyle\eta>r_{j},\qquad j\in\mathcal{N}.$

By [4, Lemma 2.3] we also have

$\displaystyle\inf_{j}\\{r_{j}+r_{j+1}\\}\leq\inf\operatorname{supp}(\psi)+\eta\leq\sup_{j}\\{r_{j}+r_{j+1}\\},\qquad
j\in\mathcal{N},$

so that $\inf\operatorname{supp}(\psi)\geq-\eta$, and hence
$\operatorname{supp}(\psi)\subset[-\eta,\eta]$.

The measure $\psi$ is symmetric about $0$ if (and only if) the random walk
$\mathcal{X}$ is periodic, that is, if $r_{j}=0$ for all $j$ (see [6, p. 69]).
In this case we also have

$\displaystyle(-1)^{n}Q_{n}(-x)=Q_{n}(x),\qquad n\geq 0,$

and it follows from (1.3) that $P_{ij}(n)=0$ if $n+i+j$ is odd. Hence the
limits in (1.5) will not exist if $\mathcal{X}$ is periodic, which is also
reflected by the fact that $C_{n}(\psi)=1$ for all $n$ in this case.

$\mathcal{X}$ is called aperiodic if it is not periodic. From Whitehurst [10,
Theorem 5.2] we have the subtle result

$\displaystyle\mathcal{X}\mbox{~{}is~{}aperiodic}\ \Rightarrow\
\int_{[-\eta,\eta]}\frac{\psi(dx)}{\eta+x}<\infty,$

so that $\psi(\\{-\eta\\})=0$ if $\mathcal{X}$ is aperiodic.

We continue with some useful observations from the recurrence relations (1.2).
The first one is the Christoffel–Darboux identity

$\displaystyle
p_{n}\pi_{n}(Q_{n}(x)Q_{n+1}(y)-Q_{n}(y)Q_{n+1}(x))=(y-x)\sum_{j=0}^{n}\pi_{j}Q_{j}(x)Q_{j}(y)$

(see, for example, [1, Theorem I.4.5]). Hence, by (1.4),

$\displaystyle\eta\leq x<y\ \Rightarrow\
Q_{n}(x)Q_{n+1}(y)>Q_{n}(y)Q_{n+1}(x)>0\qquad\mbox{for all}\ \ n\geq 0.$ (2.2)

Since $p_{j}+q_{j}+r_{j}=1$ for all $j$ it follows readily from (1.2) that
$Q_{n}(1)=1$ for all $n$, so (2.2) leads to

$\displaystyle\eta\leq x<1\ \Rightarrow\
0<Q_{n+1}(x)<Q_{n}(x)<Q_{0}(x)=1\qquad\mbox{for all}\ \ n\geq 1.$ (2.3)

Next, writing $\bar{Q}_{n}(x):=(-1)^{n}Q_{n}(x)$, we see from (1.2) that

$\displaystyle
p_{n}\pi_{n}(\bar{Q}_{n+1}(x)-\bar{Q}_{n}(x))=p_{n-1}\pi_{n-1}(\bar{Q}_{n}(x)-\bar{Q}_{n-1}(x))$
$\displaystyle\hphantom{p_{n}\pi_{n}(\bar{Q}_{n+1}(x)-\bar{Q}_{n}(x))=}{}+(2r_{n}-1-x)\pi_{n}\bar{Q}_{n}(x),\qquad
n\geq 1,$ $\displaystyle
p_{0}\pi_{0}(\bar{Q}_{1}(x)-\bar{Q}_{0}(x))=(2r_{0}-1-x)\pi_{0}\bar{Q}_{0}(x),$

from which we readily obtain

$\displaystyle\bar{Q}_{n+1}(x)=1+\sum_{j=0}^{n}\frac{1}{p_{j}\pi_{j}}\sum_{k=0}^{j}(2r_{k}-1-x)\pi_{k}\bar{Q}_{k}(x),\qquad
n\geq 0,$

and hence

$\displaystyle\bar{Q}_{n+1}(-1)=1+2\sum_{j=0}^{n}\frac{1}{p_{j}\pi_{j}}\sum_{k=0}^{j}r_{k}\pi_{k}\bar{Q}_{k}(-1),\qquad
n\geq 0.$ (2.4)

This equation, observed already by Karlin and McGregor [6, p. 76], leads to
the first of our three lemmas.

######  Lemma 2.1.

The sequence $\\{(-1)^{n}Q_{n}(-1)\\}_{n}$ is increasing, and strictly
increasing for $n$ sufficiently large, if $($and only if$)$ $\mathcal{X}$ is
aperiodic. Moreover,

$\displaystyle\sum_{j\geq
0}\frac{1}{p_{j}\pi_{j}}\sum_{k=0}^{j}r_{k}\pi_{k}=\infty\
\Longleftrightarrow\ \lim_{n\to\infty}(-1)^{n}Q_{n}(-1)=\infty.$ (2.5)

###### Proof.

Since $\bar{Q}_{0}(-1)=1$, while, by (2.4),

$\displaystyle\bar{Q}_{n+1}(-1)=\bar{Q}_{n}(-1)+\frac{2}{p_{n}\pi_{n}}\sum_{k=0}^{n}r_{k}\pi_{k}\bar{Q}_{k}(-1),\qquad
n\geq 0,$ (2.6)

the first statement is obviously true. So we have $\bar{Q}_{n}(-1)\geq 1$,
which, in view of (2.4) implies the necessity in the second statement. To
prove the sufficiency we let

$\displaystyle\beta_{j}:=\frac{2}{p_{j}\pi_{j}}\sum_{k=0}^{j}r_{k}\pi_{k},\qquad
j\geq 0,$

and assume that $\sum_{j}\beta_{j}$ converges. By (2.6) we then have

$\displaystyle\bar{Q}_{n+1}(-1)\leq\bar{Q}_{n}(-1)(1+\beta_{n}),\qquad n\geq
0,$

since $\bar{Q}_{n}(-1)$ is increasing in $n$. It follows that

$\displaystyle\bar{Q}_{n+1}(-1)\leq\prod_{j=0}^{n}(1+\beta_{j}),\qquad n\geq
0.$

But since $\prod_{j}(1+\beta_{j})$ and $\sum_{j}\beta_{j}$ converge together,
we must have $\lim\limits_{n\to\infty}\bar{Q}_{n}(-1)<\infty$. ∎

The above lemma also plays a central role in [2], where the conditions in
(2.5) are shown to be equivalent to asymptotic aperiodicity of the random
walk. For completeness’ sake we have included the proof.

We recall from [6] that $\mathcal{X}$ is recurrent, that is, the probability,
for any state, of returning to that state is one, if and only if

$\displaystyle L:=\sum_{j\geq 0}\frac{1}{p_{j}\pi_{j}}=\infty.$ (2.7)

$\mathcal{X}$ is called transient if it is not recurrent. It has been shown in
[6] that

$\displaystyle\int_{[-\eta,\eta]}\frac{\psi(dx)}{1-x}=L,$

so we must have $\eta=1$ if $\mathcal{X}$ is recurrent. From Lemma 2.1 we now
obtain

$\displaystyle\mathcal{X}\ \mbox{is~{}aperiodic~{}and~{}recurrent}\
\Rightarrow\ \lim_{n\to\infty}(-1)^{n}Q_{n}(-1)=\infty,$ (2.8)

a result noted earlier by Karlin and McGregor [6, p. 76]. Considering (1.8)
and the fact that $\eta=1$ if $\mathcal{X}$ is recurrent, the conclusion in
(2.8) implies the SRLP, so that we have regained [6, Theorem 2]. (This result
was later generalized to symmetrizable Markov chains by Orey [8, Theorem 2].)
For later use we also note that

$\displaystyle\sum_{j\geq
0}\frac{1}{p_{j}\pi_{j}}\sum_{k=0}^{j}r_{k}\pi_{k}\geq\sum_{j\geq
0}\frac{r_{j}}{p_{j}},$ (2.9)

so that, by Lemma 2.1,

$\displaystyle\sum_{j\geq 0}\frac{r_{j}}{p_{j}}=\infty\ \Rightarrow\
\lim_{n\to\infty}(-1)^{n}Q_{n}(-1)=\infty.$ (2.10)

##  3 Two auxiliary lemmas

Throughout this section $\theta$ is a fixed number satisfying
$\theta\geq\eta$. Defining $q_{0}(\theta):=0$ and

$\displaystyle
p_{j}(\theta):=\frac{Q_{j+1}(\theta)}{Q_{j}(\theta)}\frac{p_{j}}{\theta},\qquad
r_{j}(\theta):=\frac{r_{j}}{\theta},\qquad
q_{j+1}(\theta):=\frac{Q_{j}(\theta)}{Q_{j+1}(\theta)}\frac{q_{j+1}}{\theta},\qquad
j\in\mathcal{N},$ (3.1)

the parameters $p_{j}(\theta)$, $q_{j}(\theta)$ and $r_{j}(\theta)$ satisfy
$p_{j}(\theta)>0$, $q_{j+1}(\theta)>0$, $r_{j}(\theta)\geq 0$, and
$p_{j}(\theta)+q_{j}(\theta)+r_{j}(\theta)=1$, so that they may be interpreted
as the one-step transition probabilities of a random walk
$\mathcal{X}_{\theta}$ on $\mathcal{N}$. Denoting the corresponding
polynomials by $Q_{n}(\cdot;\theta)$ it follows readily that

$\displaystyle Q_{n}(x;\theta)=\frac{Q_{n}(\theta x)}{Q_{n}(\theta)},\qquad
n\geq 0,$ (3.2)

so that the associated measure $\psi_{\theta}$ satisfies

$\displaystyle\psi_{\theta}([-1,x])=\psi([-\theta,x\theta]),\qquad-1\leq x\leq
1.$

Evidently, we have

$\displaystyle\eta(\theta):=\sup\operatorname{supp}(\psi_{\theta})=\eta\theta^{-1}\leq
1,$

while the analogues $\pi_{n}(\theta)$ of the constants $\pi_{n}$ of (1.1) are
easily seen to satisfy

$\displaystyle\pi_{n}(\theta)=\pi_{n}Q_{n}^{2}(\theta),\qquad n\geq 0.$ (3.3)

(In [4, Appendix 2]) the special case $\theta=\eta$ is considered.) Obviously,
$\mathcal{X}_{\theta}$ is periodic if and only if $\mathcal{X}$ is periodic.
Note that by choosing $\theta=1$ we return to the setting of the previous
sections.

We have seen in Lemma 2.1 that $(-1)^{n}Q_{n}(-1;\theta)$ is increasing, and
strictly increasing for $n$ sufficiently large, if $\mathcal{X}_{\theta}$ is
aperiodic, or, equivalently, $\mathcal{X}$ is aperiodic. It thus follows from
(3.2) that $|Q_{n}(\theta)/Q_{n}(-\theta)|$ is decreasing, and strictly
decreasing for $n$ sufficiently large, if $\mathcal{X}$ is aperiodic. Since
$Q_{n}(-x;\theta)=(-1)^{n}Q_{n}(x;\theta)$ if $\mathcal{X}_{\theta}$ is
periodic, we conclude the following.

######  Lemma 3.1.

Let $\theta\geq\eta$. If $\mathcal{X}$ is periodic then
$|Q_{n}(\theta)/Q_{n}(-\theta)|=1$ for all $n$. If $\mathcal{X}$ is aperiodic
then $|Q_{n}(\theta)/Q_{n}(-\theta)|$ is decreasing and tends to a limit
satisfying

$\displaystyle 0\leq\lim_{n\to\infty}|Q_{n}(\theta)/Q_{n}(-\theta)|<1.$

In what follows we let

$\displaystyle
M_{n}(\theta):=\sum_{j=0}^{n}\frac{1}{p_{j}(\theta)\pi_{j}(\theta)}\sum_{k=0}^{j}r_{k}(\theta)\pi_{k}(\theta),\qquad
0\leq n\leq\infty,$ (3.4)

so that in particular $M_{\infty}(1)$ equals the left-hand side of (1.9). In
combination with Lemma 2.1, interpreted in terms of $\mathcal{X}_{\theta}$,
Lemma 3.1 gives us the next result.

######  Corollary 3.2.

For $\theta\geq\eta$ we have

$\displaystyle M_{\infty}(\theta)=\infty\ \Longleftrightarrow\
\lim_{n\to\infty}|Q_{n}(\theta)/Q_{n}(-\theta)|=0.$ (3.5)

In view of (1.8) it follows in particular that the random walk $\mathcal{X}$
possesses the SRLP if $M_{\infty}(\eta)=\infty$, which readily leads to some
further sufficient conditions. Indeed, choosing $\theta=\eta$ and defining
$L(\eta)$ in analogy with (2.7) we have

$\displaystyle L(\eta)=\sum_{j\geq
0}\frac{1}{p_{j}\pi_{j}Q_{j}(\eta)Q_{j+1}(\eta)},$

so, in analogy with (2.8), Corollary 3.2 leads to

$\displaystyle\mathcal{X}\ \mbox{is~{}aperiodic~{}and}\ L(\eta)=\infty\
\Rightarrow\ \lim_{n\to\infty}|Q_{n}(\eta)/Q_{n}(-\eta)|=0.$ (3.6)

By (2.3) we have $L(\eta)\geq L(1)\equiv L$ so the premise in (3.6) certainly
prevails if $\mathcal{X}$ is aperiodic and recurrent. When $L(\eta)=\infty$
the random walk $\mathcal{X}$ is called $\eta$-recurrent (see [4] for more
information). The conclusion that $\eta$-recurrence is sufficient for an
aperiodic random walk to possess the SRLP is not surprising, since Pruitt [9,
Theorem 2] already established this result in the more general setting of
symmetrizable Markov chains.

Another sufficient condition for the conclusion in (3.5) is obtained in
analogy with (2.10), namely

$\displaystyle\sum_{j\geq
0}\frac{r_{j}Q_{j}(\eta)}{p_{j}Q_{j+1}(\eta)}=\infty\ \Rightarrow\
\lim_{n\to\infty}|Q_{n}(\eta)/Q_{n}(-\eta)|=0.$

Since, by (2.3), $Q_{j+1}(\eta)\leq Q_{j}(\eta)$ it follows in particular that

$\displaystyle\sum_{j\geq 0}\frac{r_{j}}{p_{j}}=\infty\ \Rightarrow\
\lim_{n\to\infty}|Q_{n}(\eta)/Q_{n}(-\eta)|=0.$ (3.7)

Interestingly, we have thus verified a passing remark by Karlin and McGregor
[6, p. 77] to the effect that the premise in (3.7) is sufficient for the SRLP.

We now turn to the third lemma needed for the proof of Proposition 1.1, which
concerns the behaviour of $M_{n}(\theta)$ as a function of $\theta$.

######  Lemma 3.3.

Let $\eta\leq\theta_{1}\leq\theta_{2}$, then, for all $n$,
$M_{n}(\theta_{1})\geq M_{n}(\theta_{2})$.

###### Proof.

First consider an arbitrary random walk with parameters $p_{j}$, $q_{j}$, and
$r_{j}$, $j\in\mathcal{N}$. Let $n$ be fixed and write

$\displaystyle
M_{n}=\sum_{j=0}^{n}\frac{1}{p_{j}\pi_{j}}\sum_{k=0}^{j}r_{k}\pi_{k},\qquad
n=0,1,\dots.$

Suppose that in the single state $\ell$, $0\leq\ell\leq n$, the transition
probabilities $p_{\ell}$, $q_{\ell}$ and $r_{\ell}$ are changed into the one-
step (random walk) transition probabilities $p^{\prime}_{\ell}$,
$q^{\prime}_{\ell}$ and $r^{\prime}_{\ell}$ satisfying, besides the usual
requirements,

$\displaystyle p^{\prime}_{\ell}\leq p_{\ell},\qquad q^{\prime}_{\ell}\geq
q_{\ell}\qquad\mbox{and}\qquad r^{\prime}_{\ell}\geq r_{\ell}.$ (3.8)

Let $M_{n}^{\prime}$ denote the value of $M_{n}$ after the change. A somewhat
tedious but straightforward calculation then yields that

$\displaystyle
M^{\prime}_{n}=M_{n}+\left\\{(c_{1}-1)\sum_{k=0}^{\ell-1}r_{k}\pi_{k}+(c_{1}c_{2}-1)r_{\ell}\pi_{\ell}\right\\}\sum_{j=\ell}^{n}\frac{1}{p_{j}\pi_{j}},$

where $c_{1}$ and $c_{2}$ are constants satisfying

$\displaystyle
q_{\ell}c_{1}=\frac{p_{\ell}q^{\prime}_{\ell}}{p^{\prime}_{\ell}}\qquad\mbox{and}\qquad
r_{\ell}c_{2}=\frac{p_{\ell}r^{\prime}_{\ell}}{p^{\prime}_{\ell}}.$

The values of $c_{1}$ when $\ell=0$ and $c_{2}$ when $r_{\ell}=0$ are clearly
irrelevant, but let us choose $c_{1}=1$ and $c_{2}=1$ in these cases. Then,
under the given circumstances, we always have $c_{1}\geq 1$ and $c_{2}\geq 1$,
and hence $M^{\prime}_{n}\geq M_{n}$.

Back to the setting of the lemma we note that if
$\eta\leq\theta_{1}<\theta_{2}$, then $r_{j}(\theta_{1})\geq
r_{j}(\theta_{2})$, and, by (2.2),

$\displaystyle
q_{j}(\theta_{1})=\frac{Q_{j-1}(\theta_{1})}{Q_{j}(\theta_{1})}\frac{q_{j}}{\theta_{1}}>\frac{Q_{j-1}(\theta_{2})}{Q_{j}(\theta_{2})}\frac{q_{j}}{\theta_{1}}>\frac{Q_{j-1}(\theta_{2})}{Q_{j}(\theta_{2})}\frac{q_{j}}{\theta_{2}}=q_{j}(\theta_{2}),\qquad
j>0.$

Since $p_{j}(\theta)+q_{j}(\theta)+r_{j}(\theta)=1$, it follows that

$\displaystyle p_{j}(\theta_{1})<p_{j}(\theta_{2}).$ (3.9)

Now let $p_{j}=p_{j}(\theta_{2})$, $q_{j}=q_{j}(\theta_{2})$,
$r_{j}=r_{j}(\theta_{2})$ for all $j\in\mathcal{N}$ and suppose we perform the
change operation with $p^{\prime}_{\ell}=p_{\ell}(\theta_{1})$,
$q^{\prime}_{\ell}=q_{\ell}(\theta_{1})$ and
$r^{\prime}_{\ell}=r_{\ell}(\theta_{1})$ (so that (3.8) is satisfied)
successively for $\ell=0,1,\dots,n$. Letting $M^{(\ell)}$ be the value into
which $M^{(0)}:=M_{n}(\theta_{2})$ has been transformed after the $\ell$th
change operation, we then obviously have

$\displaystyle M_{n}(\theta_{1})=M^{(n)}\geq M^{(n-1)}\geq\cdots\geq
M^{(1)}\geq M^{(0)}=M_{n}(\theta_{2}),$

which was to be proven. ∎

We have now gathered sufficient information to draw our conclusions in the
final section, after noting as an aside that (3.9) leads to a strengthening of
(2.2), namely

$\displaystyle\eta\leq x<y\ \Rightarrow\
xQ_{n}(x)Q_{n+1}(y)>yQ_{n}(y)Q_{n+1}(x).$

##  4 Proof of Theorem 1.2 and concluding remarks

Choosing $\theta_{1}=\eta$ and $\theta_{2}=1$ in Lemma 3.3 we conclude that
$M_{n}(\eta)\geq M_{n}(1)$ for all $n$. Hence $M_{\infty}(\eta)\geq
M_{\infty}(1)$, so that

$\displaystyle M_{\infty}(1)=\sum_{j\geq
0}\frac{1}{p_{j}\pi_{j}}\sum_{k=0}^{j}r_{k}\pi_{k}=\infty\ \Rightarrow\
M_{\infty}(\eta)=\infty,$

which, by Corollary 3.2, leads to Proposition 1.1.

It seems unlikely that there are values of $\theta_{1}$ and $\theta_{2}$ such
that $\eta<\theta_{1}<\theta_{2}$ and $M_{\infty}(\theta_{1})=\infty$, but
$M_{\infty}(\theta_{2})<\infty$, since there do not seem to be values of
$x>\eta$ that are “special” in any sense. So we conjecture that
$M_{\infty}(\theta_{1})$ and $M_{\infty}(\theta_{2})$ converge or diverge
together. It is tempting to go one step further by extending this conjecture
to $\eta\leq\theta_{1}<\theta_{2}$. Maintaining the conjecture in [5] that
also the reverse implication in (1.8) is valid, we would then arrive at the
conjecture that (1.9) is not only sufficient but also necessary for
$\mathcal{X}$ to possess the SRLP. However, this not correct, since it is
possible to have $M_{\infty}(\eta)=\infty$ and $M(1)<\infty$ simultaneously,
as the next example shows.

######  Example 4.1.

Consider a random walk $\mathcal{\tilde{X}}$ determined by one-step transition
probabilities $\tilde{p}_{j}$, $\tilde{q}_{j}$ and $\tilde{r}_{j}$ with
$\tilde{r}_{0}>0$ and $\tilde{r}_{j}=0$ for $j>0$. Quantities associated with
$\mathcal{\tilde{X}}$ will be indicated by a tilde. We will assume that
$\mathcal{\tilde{X}}$ is recurrent, so that $\tilde{\eta}=1$. Now let
$\alpha>1$ and define

$\displaystyle
p_{j}:=\frac{\tilde{Q}_{j+1}(\alpha)}{\tilde{Q}_{j}(\alpha)}\frac{\tilde{p}_{j}}{\alpha},\qquad
r_{j}:=\frac{\tilde{r}_{j}}{\alpha},\qquad
q_{j+1}:=\frac{\tilde{Q}_{j}(\alpha)}{\tilde{Q}_{j+1}(\alpha)}\frac{\tilde{q}_{j+1}}{\alpha},\qquad
j\in\mathcal{N}.$ (4.1)

These quantities, like those in (3.1), can be interpreted as the one-step
transition probabilities of a new random walk $\mathcal{X}$, say. In what
follows we associate quantities without tilde with $\mathcal{X}$. In analogy
with (3.2) and (3.3) we thus have $Q_{n}(x)=\tilde{Q}_{n}(\alpha
x)/\tilde{Q}(\alpha)$ and $\pi_{n}=\tilde{\pi}_{n}\tilde{Q}_{n}^{2}(\alpha)$.
Also, $\eta=\tilde{\eta}\alpha^{-1}=\alpha^{-1}<1$, so that $\mathcal{X}$ must
be transient. Next, letting $M_{n}(\theta)$ be defined as in (3.4) and (3.1)
where $p_{j}$, $q_{j}$ and $r_{j}$ are given by (4.1), we have

$\displaystyle M_{\infty}(1)=r_{0}\sum_{j\geq
0}\frac{1}{p_{j}\pi_{j}}<\infty,$

since $\mathcal{X}$ is transient. But on the other hand

$\displaystyle
M_{\infty}(\eta)=M_{\infty}\big{(}\alpha^{-1}\big{)}=r_{0}\sum_{j\geq
0}\frac{1}{p_{j}\pi_{j}Q_{j}\big{(}\alpha^{-1}\big{)}Q_{j+1}\big{(}\alpha^{-1}\big{)}}=\tilde{r}_{0}\sum_{j\geq
0}\frac{1}{\tilde{p}_{j}\tilde{\pi}_{j}}=\infty,$

since $\mathcal{\tilde{X}}$ is recurrent.

We have already encountered several known sufficient conditions for the random
walk $\mathcal{X}$ to possess the SRLP. In particular, $\eta$-recurrence – and
thus recurrence, which is simply $1$-recurrence – was shown to be sufficient
in (3.6). Also, in view of (2.9) we regain directly from Theorem 1 Karlin and
McGregor’s claim on [6, p. 77]

$\displaystyle\sum_{j\geq 0}\frac{r_{j}}{p_{j}}=\infty\ \Rightarrow\
\mathcal{X}~{}\mbox{possesses~{}the~{}SRLP},$

referred to after (3.7). Several authors (see [6, p. 77], [5, Corollary 3.2])
have shown that for the SRLP to prevail it is sufficient that $r_{j}>\delta>0$
for $j$ sufficiently large, but this condition is evidently weaker than the
previous one.

## References

  * [1] Chihara T.S., An introduction to orthogonal polynomials, Mathematics and its Applications, Vol. 13, Gordon and Breach Science Publishers, New York – London – Paris, 1978.
  * [2] van Doorn E.A., Asymptotic period of an aperiodic Markov chain, arXiv:1712.10199.
  * [3] van Doorn E.A., Schrijner P., Random walk polynomials and random walk measures, J. Comput. Appl. Math. 49 (1993), 289–296.
  * [4] van Doorn E.A., Schrijner P., Geometric ergodicity and quasi-stationarity in discrete-time birth-death processes, J. Austral. Math. Soc. Ser. B 37 (1995), 121–144.
  * [5] van Doorn E.A., Schrijner P., Ratio limits and limiting conditional distributions for discrete-time birth-death processes, J. Math. Anal. Appl. 190 (1995), 263–284.
  * [6] Karlin S., McGregor J., Random walks, Illinois J. Math. 3 (1959), 66–81.
  * [7] Kesten H., A ratio limit theorem for (sub) Markov chains on $\\{1,2,\dots\\}$ with bounded jumps, Adv. in Appl. Probab. 27 (1995), 652–691.
  * [8] Orey S., Strong ratio limit property, Bull. Amer. Math. Soc. 67 (1961), 571–574.
  * [9] Pruitt W.E., Strong ratio limit property for $R$-recurrent Markov chains, Proc. Amer. Math. Soc. 16 (1965), 196–200.
  * [10] Whitehurst T.A., On random walks and orthogonal polynomials, Ph.D. Thesis, Indiana University, Bloomington, 1978.
  * [11] Whitehurst T.A., An application of orthogonal polynomials to random walks, Pacific J. Math. 99 (1982), 205–213.