# Fault tolerant controller design for a class of affine nonlinear systems
based on adaptive virtual actuator

S. Narges Mahdian Zadeh, Reza Ghasemi S.N. Mahdian Zadeh with MSc student of
Electrical Engineering, University of Qom, Qom,Iran, e-mail:
<EMAIL_ADDRESS>Ghasemi with the Department of Electrical
Engineering, University of Qom, Qom, Iran, e-mail<EMAIL_ADDRESS>
###### Abstract

An Adaptive Fault-tolerant Controller procedure for a class of the affine
nonlinear system is developed in this paper. This methodology hides both the
faults and external disturbances. Compare to the procedure that require
separate fault detection, isolation, and identification units, the suggested
method concentrates on fault hiding to reduce the units. The main merits of
the proposed method are 1) guaranteed stability of the closed loop system, 2)
convergence of the states of nominal and faulty systems to zero, and 3)
convergence of the tracking error to the origin. The robustness of presented
method is assured against external disturbances. Simulation results illustrate
the effectiveness of proposed fault tolerant control.

###### Index Terms:

fault tolerant control, adaptive virtual actuator,fault hiding.

##  I Introduction

The demand for more productivity has challenged many modern industrial
systems. Such conditions increase the probability of system faults and change
in system dynamics[1]. A fault is described as an unpermitted deflection of at
least one characteristic feature or parameter of the system from the standard
condition[2]. A fault usually involves a sensor or an actuator, which results
in the loss of their correct performance. In order to improve the reliability
of a system, the Fault Tolerant Control(FTC) is expressed. A fault-tolerant
control system is automatically compensating the effects of faults which is
kept the acceptable performance of the closed loop system[1]. Actuallyَ, the
main aim of FTC approaches is to preserve the demanded performance of the
system or at least its stability when the faults occur[3]. The FTC design
techniques mainly can be classified to passive or the active approach[4]. In
the passive FTC techniques, the control laws take into account the fault as a
system perturbation [5]. Thus, they have a fixed parameter in order to keep
the performance of the closed-loop system in an acceptable level when the
presence known structure faults[3]. For example in FTC research, Fekih and
Pilla designed a passive FTC approach for an F-18 aircraft model. They used a
sliding surface to eliminate the faults [6]. In active FTC approaches,
parameters and structure of the nominal controller are reconfigured according
to the occurred fault[3]. In this cases, a fault diagnosis, detection and
isolation (FDI)unit is used. The model-based is the example of this unit’s
design. But with using a model-based approach, there will be a difference
between the actual system and its mathematical model[5]. Another class of
active FTC approaches are based on an adaptive control which doesn’t require
an FDI unit[7]. A successful example in this design, is fault hiding method.
This block that hides the fault, is adding between the controller and the
system. This method doesn’t need to the readjusting of the controller[5] .
When faults of sensors and actuators occur, the virtual sensors and actuators
are well known fault hiding blocks.[8]. In [9], the fault tolerant control
(FTC) is investigated for linear systems using the fault-hiding approach.
Fault hiding approach is used for nonlinear systems,too. In[10], virtual
actuator synthesis is presented for Lipschitz non-linear systems.

In [11], is studied a dual-timescale aircraft flight control problem with
using the Sliding Mode Control (SMC). SMC is the well-known robust control
technique, because has been used to improve the stability and performance in
the presence of uncertainties[2]. In [12], a sliding mode-based FTC is
designed for the Boeing 747 that is a civilian fixed-wing aircraft. Also,
in[13], a passive actuator FTC is investigated for the MIMO affine class of
nonlinear systems with using Sliding Mode Control.
For identifying unknown nonlinear characteristics, neural networks and fuzzy
logic systems are effective,too[14]. For example, an adaptive fuzzy control
method for strict-feedback systems is provided in[15].[16] has extended the
results in [15], with using an adaptive neural network controller for
nonlinear systems. Also, in[17], for systems with unknown control directions
and unmodeled dynamics is proposed an adaptive fault-tolerant controller which
is based on fuzzy approximation. In [18] is designed a neural networks-based
adaptive Finite-time fault-tolerant control for a class of switched nonlinear
systems in lower-triangular form under arbitrary switching signals. A neural-
adaptive output-feedback controller is designed for apply to transportation
vehicles based on wheeled inverted pendulum in [19],too. Also, the observer-
based adaptive neural fault-tolerant tracking control for nonlinear systems in
non-strict feedback form has been presented in[14]. Another example of a
controller design in[20] is presented which an adaptive neural
network(NN)-based fault-tolerant control is studied for the compensation of
actuator failures in nonlinear systems with time-varying delay.

Compare to the researches which concentrate on system with constant input
gain, this paper deals with the system with nonlinear input gain. the virtual
adaptive actuator design is developed for a class on affine nonlinear system
in presence of the actuator fault. The most important goals of the proposed
methodology are as: 1) guaranteed stability of the closed loop system, 2)
promising performance of fault hiding in the presence of disturbance and
uncertain dynamic, 3) convergence of tracking error to zero, 4) convergence of
the error between health and the faulty system.

The remainder of the paper is organized as follows. The section 2 presents
problem formulation and required theories. The Adaptive virtual actuator is
derived in section 3. Then, section 4 states the results of the simulation.
Finally, this paper ends with conclusion in Section 5.

##  II  Problem Formulation

Consider the following nominal plant:

$\left\\{\begin{matrix}\dot{\hat{x}}(t)=A\hat{x}(t)+b[f(\hat{x}(t))+g(\hat{x}(t))u(t)]\\\
\hat{y}=C\hat{x}(t).\\\ \end{matrix}\right.$ (1)

where $\hat{x}\in\mathbb{R}^{n}$ is the state vector, $u(t)\in\mathbb{R}^{m}$
is the control input and $\hat{y}\in\mathbb{R}^{l}$is the output vector.
$A\in{{\mathbb{R}}^{n\times n}},b\in{{\mathbb{R}}^{n\times 1}}$ and
$C\in{{\mathbb{R}}^{l\times n}}$ are known constant matrices such that the
system is controllable. $f(.):{{\mathbb{R}}^{n}}\to{{\mathbb{R}}}$ is a
Lipschitz function with respect to ${\hat{x}}(t)$ and
$g(.):{{\mathbb{R}}^{n}}\to{{\mathbb{R}}}$ is continuously derivative; so
$g(0)\neq 0$.

One of the goals of this paper is that the states of nominal system track the
states of desire system. The dynamic of desire plant is as follows:

${{\dot{x}}_{d}}(t)=A_{d}{{x}_{d}}(t)+B_{d}r(t),$ (2)

where $A_{d}\in{{\mathbb{R}}^{n\times n}},B_{d}\in{{\mathbb{R}}^{n\times 1}}$
are known constant matrices, $x_{d}(t)\in\mathbb{R}^{n}$ is the desire state
vector and $r(t)$ is the reference input.

So,the nominal controller for the nominal plant is given as equation(3) until
This closed-loop system is stable.

$u(t)=\frac{1}{{g(\hat{x}(t))}}[-f(\hat{x}(t))+{k_{1}}r(t)+{k_{2}}\hat{x}(t)],$
(3)

where $k_{1}$ and $k_{2}$ is as follows:

${k_{1}}={({b^{T}}b)^{-1}}{b^{T}}({A_{d}}-A),$ (4)
${k_{2}}={({b^{T}}b)^{-1}}{b^{T}}{B_{d}}.$ (5)

Theorem1:Consider the dynamic of the nominal system in equations(1). The
proposed nominal control input in equations(3) through (5), makes this system
asymptotically stable and $e(t)$ achieve to the zero, if there exist a matrix
the positive definite matrix ${{p}_{1}}\in{{\mathbb{R}}^{n\times n}}$ which is
satisfied in the following inequalities:

$-{{Q}_{1}}={{A}^{T}}{{p}_{1}}+{{p}_{1}}A<0.$ (6)

proof: The difference between the states of nominal and desire is as(7):

$e(t)=\hat{x}(t)-{x_{d}}(t).$ (7)

The time derivative of this error is as follows:

$\begin{array}[]{l}\dot{e}(t)=A\hat{x}(t)+bf\left({\hat{x}(t)}\right)+bg\left({\hat{x}(t)}\right)u\\\
\\\ -{A_{d}}{x_{d}}(t)-{B_{d}}r(t).\end{array}$ (8)

That according to the definition of error, the following equation holds.

$\begin{array}[]{l}\dot{e}(t)=A\hat{x}(t)+bf\left({\hat{x}(t)}\right)+bg\left({\hat{x}(t)}\right)u\\\
\\\ -{A_{d}}(\hat{x}(t)-e(t))-{B_{d}}r(t).\end{array}$ (9)

Using equation (3), the above can be rewritten as:

$\dot{e}(t)=(A-{A_{d}}+b{k_{2}})\hat{x}(t)+{A_{d}}e(t)+(b{k_{1}}-{B_{d}})r.$
(10)

Then, the following lyapunov function is candidate as below.

$V_{1}(t)=\frac{1}{2}{e^{T}}(t){p_{1}}e(t),$ (11)

where ${p_{1}}\in{\mathbb{R}^{n\times n}}$ is a constant matrix.

The time derivative of the equation (11) is as:

$\begin{array}[]{l}\dot{V}_{1}(t)=\frac{1}{2}e{(t)^{T}}{p_{1}}\dot{e}(t)+\frac{1}{2}\dot{e}{(t)^{T}}{p_{1}}e(t),\end{array}$
(12)

Based on the equation(10), we have:

$\begin{array}[]{*{20}{l}}\begin{array}[]{l}{{\dot{V}}_{1}}(t)=\frac{1}{2}e{(t)^{T}}({A_{d}}^{T}{p_{1}}+{p_{1}}{A_{d}})e(t)+\frac{1}{2}{e^{T}}(t){p_{1}}A\hat{x}(t)\\\
{}\end{array}\\\
\begin{array}[]{l}-\frac{1}{2}{e^{T}}(t){p_{1}}{A_{d}}\hat{x}(t)+\frac{1}{2}{e^{T}}(t){p_{1}}bg(\hat{x}(t)){k_{2}}\hat{x}(t)\\\
{}\end{array}\\\
\begin{array}[]{l}+\frac{1}{2}{{\hat{x}}^{T}}(t){A^{T}}{p_{1}}e(t)-\frac{1}{2}{{\hat{x}}^{T}}(t){A_{d}}^{T}{p_{1}}e(t)+\\\
{}\end{array}\\\
{+\frac{1}{2}{{\hat{x}}^{T}}(t){k_{2}}^{T}{g^{T}}(\hat{x}(t)){b^{T}}{p_{1}}e(t)+{e^{T}}(t){p_{1}}bg(\hat{x}(t)){k_{1}}r}\\\
\\\ {-{e^{T}}(t){p_{1}}{B_{b}}r(t).}\end{array}$ (13)

The above equation can be arranged as follows:

$\begin{array}[]{*{20}{l}}\begin{array}[]{l}{{\dot{V}}_{1}}(t)=-\frac{1}{2}{e^{T}}(t){Q_{1}}e(t)+\\\
{}\end{array}\\\
\begin{array}[]{l}\frac{1}{2}{e^{T}}(t){p_{1}}(A-{A_{d}}+bg(\hat{x}(t)){k_{2}})\hat{x}(t)+\\\
{}\end{array}\\\
\begin{array}[]{l}\frac{1}{2}{x^{T}}(t)(k_{2}^{T}{g^{T}}(\hat{x}(t)){b^{T}}+{A^{T}}-A_{d}^{T}){p_{1}}e(t)\\\
{}\end{array}\\\
{+{e^{T}}(t){p_{1}}(bg(\hat{x}(t)){k_{1}}-{B_{d}})r(t).}\end{array}$ (14)

Using (4) and (5), the equation(14) is rewritten as (15)

$\dot{V}_{1}(t)=-\frac{1}{2}{e^{T}}(t){Q_{1}}e(t)<0.$ (15)

So, this theory proves the asymptotically stability of the closed loop system.

Now, consider the following faulty plant:

$\left\\{{\begin{array}[]{*{20}{c}}\begin{array}[]{l}{{\dot{x}}_{f}}(t)=A{x_{f}}(t)+bf({x_{f}}(t))+\\\
{b_{f}}[g({x_{f}}(t))({u_{f}}(t)+{d_{f}}(t))]+\\\ Ed(t)\end{array}\\\
{}\hfil\\\ {{y_{f}}(t)=C{x_{f}}(t),}\end{array}}\right.$ (16)

where ${{x}_{f}}(t)\in{{\mathbb{R}}^{n}}$ ,${{x}_{f}}(0)={{x}_{0}}$, is the
state of faulty plant, ${{u}_{f}}(t)\in{{\mathbb{R}}^{m}}$ is the control
input and ${{y}_{f}}(t)\in{{\mathbb{R}}^{l}}$ is the faulty plant output.
${{\left\|{d(t)}\right\|}_{2}}\leq{{d}_{\max}}$ and
${{\left\|\dot{d}(t)\right\|}_{2}}\leq{{\dot{d}}_{\max}}$ ,$t\geq 0$ where
$d_{max}$ and ${{\dot{d}}_{\max}}$ are constants and
$E\in{{\mathbb{R}}^{n\times q}}$ is known constant matrix. It should be
emphasized that ${{u}_{f}}(t)$ is used to distinguish the control input in the
faulty plants and the loss of effectiveness actuator fault is formulated as
the change in the input matrix b as follows[3]:

${{b}_{f}}=b\Theta\,,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\Theta\overset{\Delta}{\mathop{=}}\,\,diag({{\theta}_{1}},{{\theta}_{2}},...,{{\theta}_{m}})$

where ${{\theta}_{i}}\,,\,\,i=1,...,m$ is unknown constants such that
$0<{{\theta}_{i}}\leq 1$ and ${{\theta}_{i}}=1$ is defined for the healthy
actuator.

The following theories and lemma will be used in next section.

Theorem2[21]: Assume that $f:{R^{n}}\times{R^{m}}\to{R^{n}}$ is continuously
differentiable at each point $(x,y)$ of an open set
$S\subset{R^{n}}\times{R^{m}}$. Let $({x_{0}},{y_{0}})$ be a point in $S$ for
which $f({x_{0}},{y_{0}})=0$ and for which the Jacobian matrix
$\left[{\frac{{\partial f}}{{\partial x}}}\right]({x_{0}},{y_{0}})$ is
nonsingular.Then there exist neighborhoods $U\subset{R^{n}}$ of ${x_{0}}$ and
$V\subset{R^{m}}$ of ${y_{0}}$ such that for each $y\in V$ the equation
$f(x,y)=0$ has a unique solution $x\in U$. Moreover, this solution can be
given as $x=g(y)$, where $g$ is continuously differentiable at $y={y_{0}}$.
This theory has been proven in [21].

Theorem3[21]:Assume that $f:{R^{n}}\times{R^{m}}\to{R^{n}}$ is continuously
differentiable at each point $x$ of an open set $S\subset{R^{n}}$. Let $x$ and
$y$ be two points of $S$ such that the line segment $L(x,y)\subset S$. Then
there exists a point $z$ of $L(x,y)$ such that

$f(y)-f(x)=\frac{{\partial f}}{{\partial x}}\left|{{}_{x=z}\,(y-x)}\right.$

The proof of this theory is mentioned in [21].

The ”Lemma 1” is result from the Theory 3, too.

Lemma1[21]: Let $f:\,\left[{a,b}\right]\times D\to{R^{m}}$ be continuous for
some domain $D\subset{R^{n}}$. Suppose that $\frac{{\partial f}}{{\partial
x}}$ exists and is continuous on $\left[{a,b}\right]\times D$. If, for a
convex subset $V\subset D$, there is a constant $L\geq 0$ such that

$\left\|{\frac{{\partial f}}{{\partial x}}(t,x)}\right\|\leq L$

on $\left[{a,b}\right]\times V$ then

$\left\|{f(t,x)-f(t,y)}\right\|\leq L\left\|{x-y}\right\|$

for all $t\in\left[{a,b}\right]\,,\,x\in V\,,\,and\,y\in V$.

Theorem4[21]: Let $D\subset{R^{n}}$ be a domain that contains the origin and
$V:\left[{0,\infty}\right)\times D\to R$ be a continuously differentiable
function sush that

${\alpha_{1}}(\left\|x\right\|)\leq V(t,x)\leq{\alpha_{2}}(\left\|x\right\|)$

$\frac{{\partial V}}{{\partial t}}+\frac{{\partial V}}{{\partial
x}}f(t,x)\leq-{W_{3}}(x)\,\,,\,\,\,\forall\left\|x\right\|\geq\mu>0$

$\,\forall t\geq 0$ and $\,\forall x\in D$, where ${\alpha_{1}}$ and
${\alpha_{2}}$ are class $\mathcal{K}$ functions and ${W_{3}}(x)$ is a
continuous positive definite function. Take $r>0$ such that ${B_{r}}\subset D$
and suppose that

$\mu<\alpha_{2}^{-1}({\alpha_{1}}(r))$

then, there exists a class $\mathcal{KL}$ function $\beta$ and for every
initial state $x({t_{0}})$, satisfying
$\left\|{x({t_{0}})}\right\|\leq\alpha_{2}^{-1}({\alpha_{1}}(r))$, there
is$T\geq 0$(dependent on $x({t_{0}})$ and $\mu$) such that the solution of
$\dot{x}(t)=f(t,x)$ satisfies

$\left\|{x(t)}\right\|\leq\beta(\left\|{x({t_{0}})}\right\|,t-{t_{0}}),\,\,\,\forall{t_{0}}\leq
t\leq{t_{0}}+T$

$\left\|{x(t)}\right\|\leq\alpha_{1}^{-1}({\alpha_{2}}(\mu)),\,\,\,\forall
t\geq{t_{0}}+T$,

moreover, if $D={R^{n}}$ and ${\alpha_{1}}$ belongs to class
${\mathcal{K}_{\infty}}$, then the above inequalities hold for any initial
state $x({t_{0}})$, with no restriction on how large $\mu$ is. This theory has
been proven in [21].

##  III Adaptive Virtual Actuator Design

In this section, an adaptive virtual actuator controller is designed. It can
recover the performance of the close-loop system after the occurrence of
actuator faults and external disturbancees. In this method, the applied fault-
hiding approach does not need to change the nominal controller when the faults
have occurred.

The dynamic of the difference system between the nominal and faulty systems is
definded as follows:

$\left\\{{\begin{array}[]{*{20}{c}}{\dot{\tilde{x}}(t)=A\tilde{x}(t)+bf({x_{f}}(t))+{b_{f}}g({x_{f}}(t)){u_{f}}(t)}\\\
\begin{array}[]{l}+{b_{f}}g({x_{f}}(t)){d_{f}}(t)-bf(\hat{x}(t))-bg(\hat{x}(t))u(t)\\\
+Ed(t)\end{array}\\\ {}\hfil\\\ {\tilde{y}=C\tilde{x}(t),}\end{array}}\right.$
(17)

where $\tilde{x}(t)\overset{\Delta}{\mathop{=}}\,{{x}_{f}}(t)-\hat{x}(t)$ and
$\tilde{y}(t)\overset{\Delta}{\mathop{=}}\,{{y}_{f}}(t)-\hat{y}(t)$.

Proposition1:Based on theory 2, there exist an ideal controller as
$u_{f}^{*}(t)$ in which satisfy the following equation.

$bf({{x}_{f}}(t))+bg({{x}_{f}}(t))u_{f}^{*}(t)=0$ (18)

In this approach, there exist ${M^{*}}(t)\in{\mathbb{R}^{m\times n}}\,$ and
${N^{*}}(t)\in{\mathbb{R}^{m\times m}}$ such that $u_{f}^{*}(t)$ is defined
as:

$u_{f}^{*}(t)={{M}^{{{*}^{T}}}}(t)\tilde{x}(t)+{{N}^{{{*}^{T}}}}(t)u(t).$ (19)

The faulty plant control input ${{u}_{f}}(t)$, is considered to be an
estimation of ${{u}_{f}^{*}}(t)$,

${{u}_{f}}(t)=M(t)\tilde{x}(t)+N(t)u(t)-\hat{d}(t),$ (20)

where $M(t)\in{{\mathbb{R}}^{m\times n}},N(t)\in{{\mathbb{R}}^{m\times m}}$
and $\hat{d}(t)\in{{\mathbb{R}}^{m}}$ are obtained from:

$\dot{M}(t)=-{{\gamma}_{1}}{{\tilde{x}}^{T}}(t){{g}^{T}}({{x}_{f}}(t)){{b}^{T}}{{p}_{1}}\tilde{x}(t)$
(21)
$\dot{N}(t)=-{{\gamma}_{2}}{{u}^{T}}(t){{g}^{T}}({{x}_{f}}(t)){{b}^{T}}{{p}_{1}}\tilde{x}(t)$
(22)
${{\dot{\hat{d}}}}(t)={{\gamma}_{3}}{{g}^{T}}({{x}_{f}}(t)){{b}^{T}}{{p}_{1}}\tilde{x}(t)$
(23)

where ${{\gamma}_{1}}\in{{\mathbb{R}}^{n\times n}}$ and
${{\gamma}_{2}}\in{{\mathbb{R}}^{m\times m}}$ are positive definite gain
matrices. ${{\gamma}_{3}}$ is a positive constant and $p_{1}$ is a positive
definite matrix to be designed.

Theorem5: Consider the dynamic of reconfigured closed-loop system delivered in
equations (3) and (16). The proposed faulty plant control input in equation
(20) and update laws(21) through (23), makes this system uniformly ultimately
bounded, if there exist a positive definite matrix
${{p}_{2}}\in{{\mathbb{R}}^{n\times n}}$ which is satisfied in the following
inequalities:

$-{{Q}_{2}}={{A}^{T}}{{p}_{2}}+{{p}_{2}}A<0$ (24)

Proof: The difference between $u_{f}^{*}(t)$ and $u_{f}(t)$ is as follows:

${{e}_{u}}=u_{f}^{*}(t)-u_{f}(t)={{\tilde{M}}^{T}}(t)\tilde{x}(t)+{{\tilde{N}}^{T}}(t)u(t)+\hat{d}(t)$
(25)

where $\tilde{M}(t)={{M}^{*}}(t)-M(t)$ and $\tilde{N}(t)={{N}^{*}}(t)-N(t)$.

Paying attention to that there exists ${{Q}^{*}}\in{{\mathbb{R}}^{m\times q}}$
such that $b_{f}g({{x}_{f}}(t)){{Q}^{*}}=E$, the equation(17) is rewritten as
(26):

$\begin{array}[]{*{20}{l}}\begin{array}[]{l}\dot{\tilde{x}}(t)=A\tilde{x}(t)+bf({x_{f}}(t))+{b_{f}}g({x_{f}}(t)){u_{f}}(t)\\\
{}\end{array}\\\
\begin{array}[]{l}+{b_{f}}g({x_{f}}(t)){d_{f}}(t)+{b_{f}}g({x_{f}}(t)){Q^{*}}d(t)-bf(\hat{x}(t))\\\
{}\end{array}\\\ {-bg(\hat{x}(t))u(t).}\end{array}$ (26)

Using ${{d}_{f}}(t)+{{Q}^{*}}d(t)={{d}_{t}}(t)$, the equation (26) is
rewritten as follows.

$\begin{array}[]{*{20}{l}}\begin{array}[]{l}\dot{\tilde{x}}(t)=A\tilde{x}(t)+bf({x_{f}}(t))+{b_{f}}g({x_{f}}(t)){d_{t}}\\\
{}\end{array}\\\
\begin{array}[]{l}+{b_{f}}g({x_{f}}(t))[{u_{f}}(t)-u_{f}^{*}(t)+u_{f}^{*}(t)]-bf(\hat{x}(t))\\\
{}\end{array}\\\
\begin{array}[]{l}-bg(\hat{x}(t))u(t)=A\tilde{x}(t)-{b_{f}}g({x_{f}}(t)){e_{u}}(t)+\\\
{}\end{array}\\\
{{b_{f}}g({x_{f}}(t)){d_{t}}-bf(\hat{x}(t))-bg(\hat{x}(t))u(t).}\end{array}$
(27)

According to the equation (18), we have:

$\begin{array}[]{*{20}{l}}\begin{array}[]{l}\dot{\tilde{x}}(t)=A\tilde{x}(t)-{b_{f}}g({x_{f}}(t)){e_{u}}(t)+\\\
{}\end{array}\\\
{{b_{f}}g({x_{f}}(t)){d_{t}}-bf(\hat{x}(t))-bg(\hat{x}(t))u(t).}\end{array}$
(28)

Also, with using(25), the following equation is obtained:

$\begin{array}[]{*{20}{l}}\begin{array}[]{l}\dot{\tilde{x}}(t)=A\tilde{x}(t)-{b_{f}}g({x_{f}}(t)){{\tilde{M}}^{T}}(t)\tilde{x}(t)-\\\
{}\end{array}\\\
\begin{array}[]{l}{b_{f}}g({x_{f}}(t)){{\tilde{N}}^{T}}(t)u(t)-{b_{f}}g({x_{f}}(t))\hat{d}(t)+\\\
{}\end{array}\\\
{{b_{f}}g({x_{f}}(t)){d_{t}}-bf(\hat{x}(t))-bg(\hat{x}(t))u(t).}\end{array}$
(29)

Then $\tilde{d}(t)={{d}_{t}}(t)-\hat{d}(t)$ is defined and the above equation
is rewritten as follows.

$\displaystyle\dot{\tilde{x}}(t)=A\tilde{x}(t)+b_{f}g({{x}_{f}}(t))\tilde{d}(t)-bf(\hat{x}(t))-bg(\hat{x}(t))u(t)-$
$\displaystyle
b_{f}g({{x}_{f}}(t)){{{\tilde{M}}}^{T}}\tilde{x}(t)-b_{f}g({{x}_{f}}(t)){{{\tilde{N}}}^{T}}u(t).$

To prove the stability of the closed-loop system, the following lyapunov
function is candidate.

$\begin{array}[]{l}{V_{2}}(t)=\frac{1}{2}{{\tilde{x}}^{T}}(t){p_{2}}\tilde{x}(t)+\frac{1}{2}\frac{{{{\tilde{d}}^{2}}(t)}}{{{\gamma_{1}}}}+\\\
\\\
\frac{1}{2}\frac{{{{\tilde{M}}^{T}}(t)\tilde{M}(t)}}{{{\gamma_{2}}}}+\frac{1}{2}\frac{{{{\tilde{N}}^{T}}(t)\tilde{N}(t)}}{{{\gamma_{3}}}}\end{array}$
(31)

where ${{\gamma}_{1}},{{\gamma}_{2}},{{\gamma}_{3}}$ are scalar values.

The time derivative of the equation(31) is as below.

$\begin{array}[]{*{20}{l}}\begin{array}[]{l}{{\dot{V}}_{2}}(t)=\frac{1}{2}{{\dot{\tilde{x}}}^{T}}(t){p_{2}}\tilde{x}(t)+\frac{1}{2}{{\tilde{x}}^{T}}(t){p_{2}}\dot{\tilde{x}}(t)+\frac{{\tilde{d}(t)\dot{\tilde{d}}(t)}}{{{\gamma_{1}}}}\\\
{}\end{array}\\\
{+\frac{{{{\tilde{M}}^{T}}(t){{\dot{\tilde{M}}}^{T}}(t)}}{{{\gamma_{2}}}}+\frac{{{{\tilde{N}}^{T}}(t)\dot{\tilde{N}}(t)}}{{{\gamma_{3}}}},}\end{array}$
(32)

that based on (30),we have:

$\begin{array}[]{*{20}{l}}\begin{array}[]{l}{{\dot{V}}_{2}}(t)=\frac{1}{2}{{\tilde{x}}^{T}}(t)({A^{T}}{p_{2}}+{p_{2}}A)\tilde{x}(t)-\\\
\\\
{{\tilde{x}}^{T}}(t){p_{2}}{b_{f}}g({x_{f}}(t)){{\tilde{M}}^{T}}(t)\tilde{x}(t)\\\
{}\end{array}\\\
\begin{array}[]{l}-{{\tilde{x}}^{T}}(t){p_{2}}{b_{f}}g({x_{f}}(t)){{\tilde{N}}^{T}}(t)u(t)+\\\
\\\ {{\tilde{x}}^{T}}(t){p_{2}}{b_{f}}g({x_{f}}(t))\tilde{d}(t)-\\\
{}\end{array}\\\
\begin{array}[]{l}{{\tilde{x}}^{T}}(t){p_{2}}bf(\hat{x}(t))-{{\tilde{x}}^{T}}(t){p_{2}}bg(\hat{x}(t))u(t)+\frac{{\tilde{d}(t)\dot{\tilde{d}}(t)}}{{{\gamma_{1}}}}\\\
{}\end{array}\\\
{-\frac{{{{\tilde{M}}^{T}}(t)\dot{M}(t)}}{{{\gamma_{2}}}}-\frac{{{{\tilde{N}}^{T}}(t)\dot{N}(t)}}{{{\gamma_{3}}}}}\end{array}$
(33)

Using (3), (21) through (23), the equation (33) is expressed as follows.

$\begin{array}[]{*{20}{l}}{\dot{V}_{2}(t)=-\frac{1}{2}{{\tilde{x}}^{T}}(t){Q_{2}}\tilde{x}(t)-{{\tilde{x}}^{T}}(t){p_{2}}b{k_{1}}r-{{\tilde{x}}^{T}}(t){p_{2}}b{k_{2}}\hat{x}(t)}\\\
\\\
{\begin{array}[]{*{20}{l}}{+\frac{{\tilde{d}(t){{\dot{d}}_{t}}(t)}}{{{\gamma_{2}}}}}\\\
{}\end{array}}\\\ \end{array}$ (34)

After some mathematical manipulations, the following inequality is obtained.

$\begin{array}[]{*{20}{l}}\begin{array}[]{l}{{\dot{V}}_{2}}(t)\leq-\frac{1}{2}{{\tilde{x}}^{T}}(t){Q_{2}}\tilde{x}(t)+\left\|{\tilde{x}(t)}\right\|\left\|{{p_{2}}b{k_{1}}r}\right\|+\\\
{}\end{array}\\\
{\left\|{\tilde{x}(t)}\right\|\left\|{{p_{2}}b{k_{2}}\hat{x}(t)}\right\|+\frac{{{{\tilde{d}}_{\max}}(t){{\dot{d}}_{t\max}}(t)}}{{{\gamma_{2}}}}+\theta{{\left\|{\tilde{x}(t)}\right\|}^{2}}-\theta{{\left\|{\tilde{x}(t)}\right\|}^{2}},}\end{array}$
(35)

that for
$\left\|{\tilde{x}(t)}\right\|>\frac{1}{{2\theta}}(\beta+\sqrt{{\beta^{2}}-4\theta\mu}$
the following inequality is established, where
$0<\theta<1\,\,,\,\mu=\frac{{{{\tilde{d}}_{\max}}{{\dot{d}}_{t\max}}}}{{{\gamma_{2}}}}$
and
$\beta=\left\|{{p_{2}}b{k_{1}}r}\right\|+\left\|{{p_{2}}b{k_{2}}\hat{x}}\right\|$
are scalar values and according to theory 1,
$\left\|{\hat{x}}\right\|<\varepsilon$.

$\dot{V}_{2}(t)\leq\frac{1}{2}{\tilde{x}^{T}}(t)[-{Q_{2}}+\theta]\tilde{x}(t)+\beta\left\|{\tilde{x}(t)}\right\|-\theta{\left\|{\tilde{x}(t)}\right\|^{2}}+\mu<0$
(36)

So, the uniformly ultimately bounded of the closed loop system is achieved.

Figure 1: The block diagram FTC with the virtual actuator.

##  IV Simulation result

In this paper, the dynamics of the simulated system is considered as follows.

$\begin{array}[]{l}\dot{x}(t)=\left[{\begin{array}[]{*{20}{c}}0&1&0\\\
0&0&1\\\
{-1}&{-2}&{-3}\end{array}}\right]x(t)+\left[{\begin{array}[]{*{20}{c}}0\\\
0\\\ 1\end{array}}\right][f(x(t))+\\\ \\\ g(x(t))u(t)]+Ed(t)\\\ \\\
y(t)=[\begin{array}[]{*{20}{c}}1&1&{1]x(t)}\end{array}\end{array}$ (37)

where $g(x(t))=0.5sin(t)+4\,\,,\,f(x(t))=0.05\sin({{x}_{3}}(t))\,$ and
$E=0.5bg(x(t))\,\,\,$ .Then a loss of effectiveness actuator fault with
$\Theta=0.65{{I}_{3}}$ occurs at ${{t}_{f}}=15s$. A disturbance applied in
${{t}_{d}}=20s$ and a time-varying additive actuator fault occurs at
${{t}_{fd}}=25s$.

To design the proposed virtual actuator given by(21) through (23),we
set${{\gamma}_{1}}=20\,,\,\,{{\gamma}_{2}}=200\,,\,\,{{\gamma}_{3}}=1000$ .
Also,$\theta=0.5$.

The dynamics of desire agent is considered as follows.

${\dot{x}_{d}}(t)=\left[{\begin{array}[]{*{20}{c}}0&1&0\\\ 0&0&1\\\
{-1}&{-2}&{-4}\end{array}}\right]{x_{d}}(t)+\left[{\begin{array}[]{*{20}{c}}0\\\
0\\\ 1\end{array}}\right]r(t),$ (38)

where $r(t)$ is a reference input and it can be the step function. Also,
matrices ${{p}_{1}}$ and ${{p}_{2}}$ as

${{p}_{1}}=\begin{bmatrix}2.5000&2.5000&0.5000\\\ 2.5000&6.5000&1.5000\\\
0.5000&1.5000&0.5000\end{bmatrix},$ (39)

${{p}_{2}}=\begin{bmatrix}2.8000&2.6000&0.5000\\\ 2.6000&7.1000&1.8000\\\
0.5000&1.8000&1.1000\end{bmatrix}.$ (40)

Fig. 2 shows difference between the states of desire and nominal system, and
consequently the nominal system track well the desire system. So, the nominal
controller is worked correctly and $e$ achieve to zero, too.

Figure 2: The error between states of the desire and nominal system.

The output of nominal close-loop system without using the adaptive virtual
actuator and desire system output are shown in Fig. 3.

Figure 3: The output of close-loop system without using the adaptive virtual
actuator.

Now, the output with using the proposed adaptive virtual actuator is shown in
Fig. 4.

Figure 4: The output of close-loop system with using the adaptive virtual
actuator.

As shown in Fig. 4, after the fault occurred, the output tracks the desire
one.
Fig. 5, Fig. 6 and Fig. 7 show the states of faulty and nominal system, too.

Figure 5: The first states of the faulty system and nominal system. Figure 6:
The second states of the faulty system and nominal system. Figure 7: The third
states of the faulty system and nominal system.

Also, Figure 7 is zoomed in to show the fault, disturbance and time-varying
additive actuator fault occurrence.

Figure 8: Zoom in when the fault occurs in 15 second. Figure 9: Zoom in when
the disturbance occurs in 20 seconds. Figure 10: Zoom in when the time-varying
actuator fault occurs in 25 seconds.

Fig.11 and Fig.12 show the control input in the nominal mode and the faulty
mode.

Figure 11: The control input in the nominal mode. Figure 12: The control input
in the faulty mode.

Also, the adaptive Controller Coefficients are shown in Fig. 11, Fig. 12 and
Fig. 13.

Figure 13: Update parameter of ${M}(t)$. Figure 14: Update parameter of
${N}(t)$. Figure 15: Update parameter of ${\hat{{d}_{t}}}(t)$.

##  V Conclusion

In this paper, An Adaptive Fault-tolerant Controller has been considered for a
class of the affine nonlinear system with nonlinear input gain. This is based
on fault-hiding and does not require a separate FDI unit. Also, the design of
virtual actuator is based on the feasible solution of LMI. The convergence of
faulty and the desire system is guaranteed. The faults affect and external
disturbances are hidden and furthermore, the system is robust against faults.
Finally, the simulation result shows the promising performance of the proposed
methodology.

## References

  * [1] Xiaodong.Zh, Parisini.Th, and Polycarpou.M, ”Adaptive fault-tolerant control of nonlinear uncertain systems: an information-based diagnostic approach”, IEEE Transactions on automatic Control 49, no.8 ,pp.1259-1274, 2014.
  * [2] Li.T, Zhang.Y, and Gordon.B, ”Passive and active nonlinear fault-tolerant control of a quadrotor unmanned aerial vehicle based on the sliding mode control technique”, Proceedings of the Institution of Mechanical Engineers, Part I: Journal of Systems and Control Engineering 227, no.1 ,pp.12-23, 2013.
  * [3] Yadegar.M, Afshar.A, and Meskin.N, ”Fault-tolerant control of non-linear systems based on adaptive virtual actuator”, IET Control Theory and Applications 11, no.9 ,pp.1371-1379, 2017.
  * [4] Zhang.X, Parisini.T, and Polycarpou.M. M, Adaptive fault-tolerant control of nonlinear uncertain systems: An information-based diagnostic approach, IEEE Trans. Autom. Control, vol.49, no.8, pp.1259-1274, 2004.
  * [5] Alexandru.S, Codres.E, and Puig.V, ”A fault hiding approach for the sliding mode fault-tolerant control of a non-holonomic mobile robot”, 3rd Conference on Control and Fault-Tolerant Systems (SysTol), pp.7-14, 2016.
  * [6] Fekih.R and Pilla.P, ”A passive fault-tolerant control strategy for the uncertain MIMO aircraft model F-18”, 39th Southeastern symposium on system theory, pp.320-325, 2007.
  * [7] Li.H, Shi.P, Yao.D, ”Adaptive sliding mode control of Markov jumpnonlinear systems with actuator faults”, IEEE Trans. Autom. Control,inpress, 2016.
  * [8] Blanke.M, Kinnaert.M, Lunze.J, and Staroswiecki.M, ”Diagnosis and Fault-Tolerant Control Springer-Verlag”, Berlin Heidelberg, 2006.
  * [9] Yadegar.M, Meskin.N, and Afshar.A, ”Fault-tolerant control of linear systems using adaptive virtual actuator”, International Journal of Control 92, no.8, pp.1729-1741, 2019.
  * [10] Khosrowjerdi.M, and Barzegary.S, ”Fault tolerant control using virtual actuator for continuous‐time Lipschitz nonlinear systems”, International Journal of Robust and Nonlinear Control 24, no.16, pp.2597-2607, 2014.
  * [11] Shtessel.Y, Buffington.J and Banda.S, ”Multiple timescale flight control using reconfigurable sliding modes”, J Guid Contr Dyn , pp.873–883, 1999.
  * [12] Alwi.H and Edwards.C, ”Fault-tolerant control of a civil aircraft using a sliding mode based scheme”, 44th IEEE conference on decision and control and European control conference, pp.1011-1016, 2005.
  * [13] Nasiri.A, Nguang.S, Swain.A and Almakhles.D, ”Passive actuator fault tolerant control for a class of MIMO nonlinear systems with uncertainties”, International Journal of Control 92, no.3, pp.693-704, 2019.
  * [14] Wu.Ch, Liu.J, Xiong.Y, and Wu.L, ”Observer-based adaptive fault-tolerant tracking control of nonlinear nonstrict-feedback systems”, IEEE transactions on neural networks and learning systems 29, no.7 ,pp.3022-3033, 2017.
  * [15] Lee.H and Tomizuka.M, ”Robust adaptive control using a universal approximator for SISO nonlinear systems”, IEEE Trans. Fuzzy Syst, vol.8, no.1, pp.95-106, 2000.
  * [16] Ge.S and Wang.C, ”Direct adaptive NN control of a class of nonlinear systems”, IEEE Trans. Neural Netw, vol.13, no.1, pp.214-221, 2002.
  * [17] Yin.Sh, Gao.H, Qiu.J, and Kaynak.O, ”Adaptive fault-tolerant control for nonlinear system with unknown control directions based on fuzzy approximation”, IEEE Transactions on Systems, Man, and Cybernetics: Systems 47, no.8, pp.1909-1918, 2016.
  * [18] Liu.L, Liu.Y, and Tong.D, ”Neural networks-based adaptive finite-time fault-tolerant control for a class of strict-feedback switched nonlinear systems”, IEEE transactions on cybernetics 49, no.7, pp.2536-2545, 2018.
  * [19] Li.H, Gao.H, Shi.P, and Zhao.X, ”Fault-tolerant control of Markovian jump stochastic systems via the augmented sliding mode observer approach”, Automatica, vol.50, no.7, pp.1825-1834, 2014.
  * [20] Yin.SH, Yang.H , Gao.H, Qiu.J, and Kaynak.O, ”An adaptive NN-based approach for fault-tolerant control of nonlinear time-varying delay systems with unmodeled dynamics.” IEEE Transactions on Neural Networks and Learning Systems 28, no.8 ,pp.1902-1913, 2016.
  * [21] Khalil.H, ”Nonlinear systems”,3 edition, 2001.


# S3: Increasing GPU Utilization during Generative Inference for Higher
Throughput

Yunho Jin
Harvard University
Chun-Feng Wu
National Yang Ming
Chiao Tung University
David Brooks
Harvard University
Gu-Yeon Wei
Harvard University

(April 2023)

###### Abstract

Generating texts with a large language model (LLM) consumes massive amounts of
memory. Apart from the already-large model parameters, the key/value (KV)
cache that holds information about previous tokens in a sequence can grow to
be even larger than the model itself. This problem is exacerbated in one of
the current LLM serving frameworks which reserves the maximum sequence length
of memory for the KV cache to guarantee generating a complete sequence as they
do not know the output sequence length. This restricts us to use a smaller
batch size leading to lower GPU utilization and above all, lower throughput.
We argue that designing a system with a priori knowledge of the output
sequence can mitigate this problem. To this end, we propose S3, which predicts
the output sequence length, schedules generation queries based on the
prediction to increase device resource utilization and throughput, and handle
mispredictions. Our proposed method achieves 6.49$\times$ throughput over
those systems that assume the worst case for the output sequence length.

##  1 Introduction

Text generation has become increasingly popular in various services, leading
to a surge in the use of large language models (LLMs) known for their high
accuracy. LLMs have distinct features that differentiate them from non-
Transformer-based models, including a requirement for massive amounts of
compute and memory resources. Specifically, we observe that Transformer-based
LLMs are often limited by memory capacity and bandwidth, resulting in
significant underutilization of compute resources. When serving GPT-J on an
NVIDIA A100 GPU, the utilization of GPU compute resources can be as low as
0.4%. This highlights the memory-bound nature of the LLMs and the need for
efficient memory utilization to increase the utilization of GPU compute
resources.

A common approach to boost GPU utilization and enhance throughput is to
increase batch size. This is due to the fact that inputs within a batch share
the same model weights, thus the GPU only needs to load the model weight from
its high bandwidth memory (HBM) to the on-chip SRAM once and reuse it for all
inputs within the batch. The GPU uses more of its compute resources when
processing the same model weights. Increasing batch size is a simple
optimization technique and is, therefore, commonly used in serving
convolutional and fully-connected neural network models [1, 2].

However, the self-attention layer in Transformer-based text generation LLMs
presents a challenge to this simple optimization due to its autoregressive
nature. Specifically, when generating a new token in a sequence, the model
needs to attend to all previous tokens in the sequence, requiring the model to
retain all information from previous tokens and store them in HBM. We call
this region in the HBM holding the information key/value cache (KV cache). The
size of the KV cache grows with larger batch sizes and longer sequences, which
limits the maximum batch size, thereby lowering GPU utilization and ultimately
reducing throughput. To support the growing KV cache size, Huggingface’s
Transformers library [3] constantly allocates new memory at each token
generation and incurs latency overhead associated with memory allocation. This
improves usability since users do not have to know the output sequence length
but suffers long inference latency. Alternatively, NVIDIA’s FasterTransformer
library [4] pre-allocates memory for the maximum sequence length, which ends
up wasting memory by allocating more than is necessary. This approach limits
batch size and prioritizes latency over throughput. The trend towards long
maximum sequence lengths in recent models (e.g., 8K or 32K) [5] amplifies the
KV cache overhead, demanding more efficient memory utilization in serving
Transformer-based text generation models.

In light of these challenges, we propose S3, scheduling sequences with
speculation, a framework that maximizes throughput via predicting the output
sequence length and reducing memory waste. The frequent memory allocations in
Huggingface’s Transformers and the limited batch size in FasterTransformer
stem from the fact that we lack prior knowledge of the output sequence length.
S3 addresses these issues by predicting the expected output sequence length
and allocating the corresponding amount of memory for each query. It also
schedules sequences to increase the GPU utilization. Finally, S3 runs a
supervisor in the background that detects mispredictions and adjusts the size
of allocated memory to be more accurate. By integrating these components
together, S3 optimizes memory usage and scheduling to maximize throughput
during deployment of Transformer-based LLMs for text generation on GPUs.

Figure 1: Latency versus throughput trade-off among different models (left)
and the number of GPUs (right, distributing GPT-3 to 6, 8, and 10 GPUs) when
generating 60 tokens, inspired by FlexGen [6]. The markers in the lines
represent batch sizes, from 1 to the maximum batch size that can be loaded on
an A100 GPU, incrementing by the power of two. Allocating the exact amount of
memory for each sequence expands the curve to higher throughput at the cost of
higher latency. The solid lines show the trade-off that vanilla systems face
and dotted lines show how much S3 can expand the trade-off. The numbers
represent the maximum batch sizes for S3 and vanilla system. The vertical line
in the left figure denotes the latency SLO for reading a 60-token long
sequence.

There are two types of LLM deployment scenarios: online and offline. Online
scenarios such as chatbots [7, 8] require service providers to generate a
sequence within a tight latency service level objective (SLO) constraint.
Offline scenarios include applications such as scoring [9] or data wrangling
[10], and have loose latency SLOs, emphasizing throughput over end-to-end
latency. In contrast, FaterTransformers [4] and xFormers [11] prioritize
reducing latency. We argue that ensuring the latency remains below the SLO
constraint renders it unnecessary to prioritize further latency reduction. To
this end, we design S3 to achieve higher throughput under those latency SLOs.
Figure 1 highlights how much S3 can improve throughput when trading off
latency. For online scenarios, we assume a latency SLO set to the average
reading speed of English readers, 4 words per second [12] and 0.1875 second
per token [13]. The models on the left figure that are smaller than 100
billion parameters satisfy this SLO for all possible batch sizes. This SLO
offers service providers to improve throughput over all models. In fact, for
LLAMA-33B [14], there are opportunities to get throughput benefits with no
latency penalties. The right figure, sweeping over different number of GPUs,
shows opportunities to maximize throughput in offline scenarios that have
loose latency SLO.

We evaluate S3, assessing both its throughput and cost-efficiency. Our
analysis includes both offline and online scenarios. In online scenarios under
the average reading speed latency SLO constraint, we find that S3 can generate
up to 6.49× more sequences while adhering to the same SLO constraint. In
offline scenarios, we observe that S3 achieves a speedup up to 6.49$\times$
for different models. S3 does not affect the models’ perplexity as it does not
change the models’ architectures. Furthermore, we evaluate the cost-efficiency
of S3 and find that using 6 GPUs, S3 provides almost identical throughput
compared to a vanilla system with 10 GPUs.

To summarize, we make the following contributions:

  * •

We increase the achievable batch size under longer latency SLO and allow
service providers to serve with higher throughput in both online and offline
scenarios by using larger batch sizes.

  * •

We fine-tune a Distillbert model to predict output sequence lengths given an
input prompt.

  * •

We provide a mechanism to recover from mispredictions. S3 preempts sequences
that exceed their allocated memory and retrain the predictor to learn from its
mistakes.

##  2 Background and Motivation

###  2.1 Generative AI Models

A Transformer-based generative model is autoregressive. It predicts the most
probable token based on past tokens. Since the model generates one token at a
time, it has to iterate over itself $n$ times to generate a sequence that is
$n$-tokens long. One iteration involves an input token traversing through the
model which is a stack of transformer layers containing one attention, two
layer norm, and two feed-forward layers. Especially, the self-attention layer
uses information on the past tokens to generate the next token.

For example, the model at the $i^{th}$ iteration attends the current token
($t_{i}$) with every token it already generated ($t_{0},...t_{i-1}$) in the
self-attention layer. We can express the self-attention layer as:

$h_{out}=softmax(\frac{q_{i}\cdot K^{T}}{\sqrt{d_{h}}})\cdot V$

where $d_{h}$ is hidden dimension of the model,
$h_{out},q_{i}\in{\mathbb{R}^{d_{h}}}$ are output hidden vector, current query
vector, respectively, and $K,V\in{\mathbb{R}^{i\times d_{h}}}$ are key and
value matrices. The $j_{th}$ rows in the $K$ and $V$ matrices represent key
and value vectors of $t_{j}$, respectively. The two dot products attend
$t_{i}$ to all the key and value vectors in the current sequence.

The model stores $K$ and $V$ matrices as the key/value (KV) cache to avoid
having to generate key and value vectors at each iteration. Otherwise, it has
to store hidden states of every previous token and multiply it with a weight
matrix $W_{QKV}\in{\mathbb{R}^{d_{h}\times 2d_{h}}}$ at every transformer
layer. This would require $2(i-1)d_{h}$ FLOPs per layer almost identical to
$2id_{h}$ FLOPs for the self-attention layer at $t_{i}$. The size of the KV
cache is $4ld_{h}$ bytes per token when using half-precision numbers. The
cache uses 2 bytes for every number for both the key and value cache where $l$
is the number of transformer layers in a model. For example, GPT-NEOX [15], a
20 billion parameter model, has 44 layers and 6144 hidden dimensions and thus
uses 1MB per KV cache per token.

Figure 2: (a) GPT-J’s and (b)GPT-NEOX’s NVIDIA A100 compute utilization.

###  2.2 KV Cache Management on GPUs

The KV cache is relatively small (e.g., several MBs) and can be easily stored
in the GPU HBM (high-bandwidth memory) when the sequence is short as the cache
stores information about the previous tokens in the sequence. It grows as the
model generates more tokens. Using this dynamic nature, Huggingface’s
Transformers [3] (HF-Transformers) constantly allocates more memory to the KV
cache and stalls the computation until it is complete. This approach allows
the library to allocate the exact amount of memory for each cache at the cost
of frequent memory accesses.

To mitigate this, NVIDIA’s FasterTransformer library reserves the maximum
sequence length of memory for every sequence [4, 16]. It removes redundant
memory accesses by simply filling in the reserved memory in an append-only
fashion. However, this approach comes with its own drawback as it reserves
more than strictly-necessary memory for sequences. For GPT-NEOX with a maximum
sequence length of 2048 tokens, FasterTransformer reserves 2048 tokens even
for sequences that end up being 50 tokens long. The maximum batch size that
FasterTransformer can use for this model with a 80GB A100 GPU is less than 20
with the 40GB model size and 2.2GB per sequence. The small batch size
underutilizes the massive compute resources in the GPU. The rationale for
reserving the maximum sequence length amount of memory even with the
underutilization problem is to ensure that it generates full sequences and
enhances user experience.

###  2.3 Observation

#### Language models are memory bound

We demonstrate the extent of GPU resource underutilization when we run GPT-J
with 6B parameters on an A100 GPU. The relatively smaller model shows a wider
spectrum of different batch sizes and sequence lengths since we can fit larger
batches with longer sequences in the GPU. Fig. 2 (a) shows the GPU utilization
swept over different batch sizes and sequence lengths. As the figure denotes,
increasing the batch size achieves a higher utilization but eventually faces a
memory cliff, where an out-of-memory (OOM) error kills the process. Take the
batches with 1024 sequence length for example. 8 sequences are the maximum
batch size and thus 12.19% is the maximum utilization that we can achieve with
this sequence length. Fig. 2 (b) shows similar underutilization in the larger
GPT-NEOX model due to the memory cliff problem. This model faces the memory
cliff with smaller batch sizes and shorter sequences since the model consumes
more of the GPU memory. Please note that HF-Transformers still needs to know
the output sequence length before batching inputs to avoid the memory cliff.

As the figures illustrate, increasing the batch size can enhance throughput in
neural networks. This approach does not require intricate optimizations and
enables the GPU to load the model weight from its HBM to the on-chip SRAM only
once and share it among a larger number of inputs. By doing so, the GPU can
activate its idle compute resources and concurrently handle multiple inputs.
Nevertheless, the memory cliff poses a challenge, limiting the utilization of
additional resources. However, as we elaborate, this issue can be resolved.

#### Reasons behind the inefficiencies

Both the frequent memory allocations in HF-Transformers and the limited batch
size in FasterTransformer come from the fact that we are not aware of the
generated sequence length. If we know the precise length of the generated
sequence, we can allocate exact memory to each sequence and resolve the
repetitive memory reservation and the unnecessary memory allocation problems
in HF-Transformers and FasterTransformer, respectively.

##  3 S3 Design

Figure 3: Overview of S3. The boxes in yellow denote new components proposed
by S3.

S3 is a system-algorithm co-design framework that maximizes GPU utilization
with sequence length prediction to achieve higher throughput. S3 has three
components as shown in Fig. 3: 1) predictor, 2) scheduler, and 3) supervisor.
A text generation query arrives in a request pool in the host DRAM. The
predictor then predicts its output sequence length which the scheduler uses to
batch requests. The scheduler dispatches the batch to the GPU and the text
generator model generates texts in the batch. The supervisor oversees the GPU
utilization and handles mispredictions. We describe each component in detail
and how they interact with each other in this section.

#### Output sequence length predictor

We use a predictor to predict the output sequence length and resolve the
frequent and redundant memory allocation problems. Specifically, we fine-tune
a Distilbert [17] model that was trained for sequence classification to
classify which length bucket the output sequence length falls into. We
bucketize the sequence lengthes since it is known that machine learning models
are not as capable of the “last mile” search compared to narrowing the
candidates down to the last mile. Each bucket is allocated the range of
$\frac{max\ sequence\ length}{number\ of\ buckets}$ and we use 10 buckets.

To this end, we fine-tune the model on the Alpaca dataset [18], one of the
representative question-and-answering datasets, and use the questions as
inputs and the lengthes of the answers as labels. We observe that this
predictor predicts the correct bucket with 98.61% accuracy. The average
distance between the wrong predictions and the correct bucket is 1.03 meaning
that the error converges to 0 when we double the bucket size. We also evaluate
the predictor on a model fine-tuned with Google Natural-Question dataset [19]
and observe an accuracy of 77.13%. It makes smaller mistakes more often than
larger ones. For completeness, we fine-tune a model on the Pile dataset [20],
a non-question-and-answering dataset, and see 65.6% accuracy. The predictor
shows surprisingly high accuracy compared to randomly guessing the bins as the
latter is correct only 10% of the time.

We choose Distilbert, a 66 million parameter model for its small size and fast
inference. The model size is negligible since it is smaller than even a single
transformer layer in the billion-scale models (e.g., 214 million for 6 billion
GPT-J [21] model). The latency is also negligible since the predictor model
runs only once when a request arrives at the server while the text generation
model runs $n$ times to generate an $n$-token long output sequence. We measure
that Distilbert takes 3.7ms to run compared to several seconds for the text
generation models on an NVIDIA A100 GPU.

#### Length-aware sequence scheduler

The scheduler batches and schedules sequences based on the predicted results
to maximize the GPU utilization without exceeding the GPU HBM capacity. We can
formulate this problem as a variant of the bin packing problem with a single
bin. The capacity constraint of the bin is the HBM capacity and the item
weight is the size of the KV cache for each sequence.

We use the decreasing first fit algorithm [22] as the solution to the bin
packing problem for its simplicity. The scheduler first sorts the sequences in
the request pool which contains the sequences to be scheduled in a decreasing
order. It iterates through the pool and checks if the KV cache of the current
sequence does not exceed the available HBM. If so, it includes the sequence in
the current batch and reduces the available HBM by the size of the KV cache.
The scheduler continues this process until either there is no available HBM or
it has iterated through the entire request pool.

The resulting batch is irregularly shaped where some sequences are longer than
others. Unfortunately, current frameworks either do not support irregularly
shaped batch [4, 3] or support it with limited performance [23]. Those that do
not support this functionality pad the short sequences with padding tokens to
match the length of sequences in the same batch. The padding tokens waste both
computation and memory since they do not hold any useful information. ORCA
[16] introduces an interesting solution to this problem. It first identifies
that inputs to certain layers (e.g., feed-forward) in the Transformer are of
the same shape regardless of the sequence length and batches them without
padding the short sequences. It serializes the inputs for layers (i.e., self-
attention) that require identically shaped inputs instead of batch-processing
them. ORCA shows that this has a negligible impact on the latency since the
inputs to the self-attention layers do not share weights and do not benefit
from batching. As such, we follow ORCA and use its selective batching
technique.

Also borrowing from ORCA the iteration-level scheduling technique, S3 does not
wait until all sequences in the current batch finish generation. Instead, it
checks if any sequence in the batch has finished generation at every
iteration. This grants S3 higher scheduling flexibility and removes any
redundant waiting time. Finally, if a model cannot fit in one GPU, S3 uses
pipeline parallelism and shard the models in Transformer layer granularity.

#### Supervisor

The supervisor is in charge of supervising the GPU utilization and handling
mispredictions. The supervisor runs in the background to check for the
available space in the HBM and passes the information to the scheduler. The
scheduler then appends a sequence to the running batch if the available memory
is large enough for the sequence.

The supervisor is also responsible for handling mispredictions. In the case of
short predictions, the supervisor preempts those sequences that exceed their
reserved memory. It monitors the length of the current output sequences and
evicts them if they are not finished but used up its reserved memory. It
asynchronously moves the current state of those sequences including the KV
cache and the generated tokens to the request pool and frees up the GPU
memory. Now the K and V matrices are fragmented with blank rows where the
evicted KV cache was originally stored in. The supervisor shifts the rows
below the blank one so that all rows are stored contiguously. This memory
format is required by current libaries [24, 25] and also resolves the
fragmentation issue. Finally, the supervisor doubles the assigned memory for
the evicted sequences to fix the short misprediction.

Finally, the supervisor constantly trains the predictor in the background. It
uses the sequences that the predictor mistook to train the predictor so that
it can learn from its mistakes. This training time is relatively short and our
measurement shows that each training iteration takes 11ms on average while
sequence generation takes several seconds or more. This implies that the
retraining overhead is less than 10% even if we train the predictor for 10
epochs.

#### Putting it all together

We summarize this section with an explanation of how S3 uses each component to
serve a sequence-generation request. First, text-generation requests arrive at
the request pool. The predictor predicts the output sequence length of the
sequences in the pool. The supervisor runs in the background and checks the
current HBM usage. Next, the scheduler uses both the predictions and the
available HBM to batch requests for maximum GPU utilization. It finishes its
job by scheduling that batch to the GPU which generates the scheduled
sequences.

##  4 Evaluation

Table 1: Model architecture used in the evaluations Model | Num Params | Num layers | Model dim | Num heads
---|---|---|---|---
GPT-J [21] | 6B | 28 | 5120 | 16
LLAMA 13B [14] | 13B | 40 | 4096 | 40
GPT-NEOX [15] | 20B | 44 | 6144 | 64
LLAMA 33B [14] | 30B | 60 | 6656 | 52
GPT3 175B [26] | 175B | 96 | 12288 | 96
|  |  |  |

We show that S3 achieves higher throughput by predicting the output sequence
length. We also show that S3 can reduce the cost of serving models by using
fewer GPUs.

#### Environment

We run our evaluation on an NVIDIA 80GB A100 GPU connected to the host DRAM
via PCIe 4.0$\times$8 in a Lenovo ThinkSystem SD650-N V2 Server [27].

#### Baselines

We compare with ORCA [16], a Transformer serving system that increases
throughput by iteration level scheduling and selective batching. ORCA has to
allocate the maximum sequence length of memory when it is not aware of the
output sequence length to guarantee full sequence generation. S3 predicts the
output sequence length and allocates memory based on the prediction. We
implement the systems on top of FasterTransformer [4] since this library is
faster than HF-Transformers [3] due to more optimizations. We also compare S3
with an ideal system with a perfect predictor which we term Oracle.

#### Models

We use models ranging from 6 billion parameters to 175 billion parameters for
the evaluation. The specifics of these models are explained in table 1.

###  4.1 Throughput Analysis

(a) Maximum throughput

(b) Generated sequences under latency SLO

Figure 4: Latency and throughput of different models. Table 2: Average batch size and number of iterations for different models Model | ORCA | S3 | Oracle
---|---|---|---
Batch size | Num iter | Batch size | Num iter | Batch size | Num iter
GPT-J | 69.94 | 7988 | 530 | 1054 | 564.88 | 989
LLAMA 13B | 31.61 | 17675 | 274.66 | 2034 | 527.04 | 1060
GPT-NEOX | 16.89 | 33069 | 157.59 | 3545 | 292.19 | 1912
LLAMA 33B | 4 | 139790 | 42.47 | 13155 | 77.35 | 7223
|  |  |  |  |  |

We evaluate S3’s throughput using Alpaca [18] dataset, a popular open-sourced
question-and-answering dataset. Specifically, we query S3 with questions and
ask it to generate the answers.

#### Offline scenario: Maximum throughput

Fig. 4 (a) reports the maximum throughput in sequences per second for
different models. We measure the throughput using the maximum batch size of
each configuration. It shows that S3 outperforms ORCA by 1.13$\times$ and up
to 6.49$\times$ and closely matches Oracle, differing from 9.34% and up to
40.52%. The difference is magnified with larger models because the batch size
is limited even for S3 2 since most of the HBM is used to hold model weights.
The batch size in S3 gets cut off before saturating the throughput as shown in
Fig. 1.

We can notice that the maximum throughput increases by 6.49$\times$ while the
batch size increase by nearly 10$\times$ for every model. This comes from the
unique behavior of Transformers. Feed-forward layers in the models benefit
from batching layers while self-attention layers do not. This is because
inputs in feed-forwards share the same weight while inputs in self-attentions
attend to their own sequences. S3’s performance benefit is increased when the
parallelized portion is larger than the serialized portion. However,
increasing the batch size entails adding more serialized inputs thereby
growing the serialized portion. GPT-J is a good example of this characteristic
which shows a similar throughput jump of 1.13$\times$ from ORCA to S3 and
1.09$\times$ from S3 and Oracle while the batch size differs by 8.69$\times$
and 1.97$\times$, respectively.

#### Online scenario: SLO-aware throughput

We now consider a scenario with a latency SLO constraint. We set the SLO as
0.1875 seconds to generate one token given that average English readers can
read at 4 words per second [12] or 0.25 second per word, and 0.75 words per
token [13]. We next calculate the latency SLO for each sequence by multiplying
0.1875 by its sequence length (e.g., 11.25s for a sequence with 60 tokens).

Fig. 4(b) reports the number of sequences that each model generates using
ORCA, S3, and Oracle. Oracle exceeds the SLO for GPT-J, LLAMA 13B, and GPT-
NEOX when it chooses the maximum batch size. So we limit the batch size for
these models during this evaluation. S3 generates a similar number of
sequences with the ideal case and 1.13$\times$ to 6.49$\times$ more sequences
compared to ORCA. The throughput increase is similar to the offline scenario
since S3 meets the SLO in most cases with its maximum batch size. However, the
difference between S3 and Oracle reduces by 10% compared to the offline
scenarios because we limit the batch size hence the throughput of Oracle.

###  4.2 Cost Analysis

Figure 5: Maximum throughput of GPT3 running on different numbers of GPUs.

Figure 6: Latency breakdown of S3.

Table 3: Average batch size and number of iterations for different system configurations Num GPUs | ORCA | S3 | Oracle
---|---|---|---
Batch size | Num iter | Batch size | Num iter | Batch size | Num iter
6 | 11.95 | 46734 | 114.22 | 4891 | 209.47 | 2667
8 | 28.68 | 19482 | 247.85 | 2254 | 470.65 | 1187
10 | 48.99 | 11403 | 399.62 | 1398 | 564.88 | 989
|  |  |  |  |  |

We evaluate S3with different numbers of GPUs. We partition GPT-3 into 6 and 8
GPUs in a pipeline-parallel manner, allocating 16 and 12 transformer layers
per GPU for each configuration, respectively. We also evaluate on 10 GPU
setting where we allocate 10 layers to 9 GPUs and 6 to the remaining GPU. S3
pipelines each batch and schedules the a batch whenever the GPU processing the
first partition passes its result to the next batch. This reduces GPU idle
time by having every GPU processing batches concurrently.

Fig. 6 reports the maximum throughput using the different numbers of GPUs.
First, we can see that S3 achieves similar throughput using 6 GPUs compared to
ORCA with 10 GPUs. ORCA shows 0.92% higher throughput than S3 to be specific.
More GPUs shard the model into finer pieces and leave more space for storing
the KV cache, allowing us to increase the batch size. Table 3 supports this
claim by reporting larger batch sizes with more GPUs. S3 can achieve similar
effect with fewer GPUs by optimizing memory allocation strategy.

Naturally, it leads to a similar question with the one in the throughput
evaluation on why S3 with 6 GPUs shows similar throughput with ORCA with 10
GPUs even with 2.33$\times$ the batch size. The answer is in the pipelined
execution and the sequential nature of self-attention layers in Transformer-
based models as explained in 4.1. The systems complete a batch at every
$\lceil\frac{l}{number\ of\ GPUs}\rceil$ instead of at every $l$ layers. For
example, S3 with 6 GPUs completes a batch at every 16 layers instead of 96 for
GPT3. Similarly, ORCA with 10 GPUs completes at every 10 layers and thus
processes more quickly. The increase in the latency negates the throughput
benefit from S3 such that the two systems show almost identical throughput
even with the 2.33$\times$ larger batch size when using S3.

###  4.3 Overhead: Latency Breakdown

We evaluate runtime latency of each component in S3. We classify the runtime
latency into three categories: generation, penalty, and overhead. Generation
is the time S3 spent on processing the model to generate tokens. Penalty
denotes the time it took for S3 to preempt the KV cache and hidden states from
the GPU and load it back to the GPU. Overhead includes the time it took for
predictor, scheduler, and supervisor, combined. Fig. 6 show that penalty and
overhead combined are negligible (i.e., 11% on average) compared to the
generation. Of course, the penalty would increase if the predictor is less
accurate and triggers more data traffic between the GPU and the host. In
contrast, the overhead will increase if we employ a more accurate but heavier
predictor. With a decent predictor, this overhead will be amortized as the
text generation model generates longer sequences.

##  5 Related Works

#### Machine learning serving systems

The high interest in machine learning has sparked numerous research in its
service platforms [28, 29, 16, 30, 31, 4, 32, 33, 34, 1, 35, 36, 6, 37, 38].
Especially, the surprising performance of Transformer-based language models
has directed many researchers to develop Transformer-specific serving systems
[34, 4, 6, 38, 37]. Most of the systems focus on reducing the latency without
much concern for throughput with the exceptions of [6, 31, 39]. The
throughput-oriented systems use memory hierarchy to store parts of the model
in slower memory and to increase the batch size. However, they all allocate
the same memory to every sequence and do not consider preempting a sequence
based on a prediction. S3 can improve these systems by reducing the required
memory size. This will remove the need for larger but slower memories such as
SSDs and also reduce the fiscal cost of memory overall.

#### Reducing the KV cache overhead

The issue of attention layers in Transformers requiring quadratic computation
and memory with respect to the sequence length has been extensively studied.
Various approaches have been proposed to address this problem. Low-rank
approximation [40, 41] and exploiting sparsity [42, 43, 44] are among the
methods that aim to mitigate the issue. Another approach, known as multi-query
attention [37, 45], suggests reducing the cache size by utilizing one
attention head per key-value (KV) cache instead of employing multiple
attention heads, as illustrated in Table 1. Additionally, works focusing on
model size reduction through compression [46] and quantization [6, 47, 48] can
also contribute to reducing the size of the KV cache. These approaches are
complementary to our work and can be employed to reduce the penalty caused by
mispredictions, allowing for the use of a less accurate but lighter predictor.

#### Sequence length prediction

While there are limited works that predict output sequence length based on an
input sequence, Yan et al. [49] propose a convolution-based small network with
embedding layers to forecast output sequence length in machine translation. In
our approach, we employ a similar strategy but utilize a small Transformer-
based predictor to estimate the output sequence lengths in text generation
tasks. This predictor allows us to accurately predict the output sequence
length for text generation workloads.

##  6 Limitations and Conclusion

#### Limitations

We make the following assumptions in this work. We assume that text generation
request traces mimic the publicly available question-and-answering datasets
since there are no publicly-available traces. Analyzing the actual trace would
facilitate deploying S3 in commercial workloads. Similarly, text generation
task does not have any standardized latency SLO constraint as in other machine
learning workloads [50] since it is a relatively new service. So we assume
average reading speed of an English reader as our SLO. We will be able to
evaluate S3 in broader scenarios if organizations publicly release different
SLOs for different text generation applications.

#### Conclusion

In summary, we introduce S3, a framework designed to achieve high throughput
in serving Transformer-based generative models. S3 leverages a predictor to
estimate the output length of generated sequences and schedules them
accordingly to maximize throughput. Additionally, S3 handles potential
prediction errors to guarantee reliability. By allocating varying memory sizes
to different inputs, S3 acknowledges that not all sequences should be treated
equally. This approach expands the conventional trade-off between latency and
throughput frontier, paving the way for new possibilities in optimizing the
latency-throughput trade-off.

## References

  * [1] D. Crankshaw, X. Wang, G. Zhou, M. J. Franklin, J. E. Gonzalez, and I. Stoica, “Clipper: A Low-Latency online prediction serving system,” in _14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17)_. Boston, MA: USENIX Association, Mar. 2017, pp. 613–627. [Online]. Available: https://www.usenix.org/conference/nsdi17/technical-sessions/presentation/crankshaw
  * [2] R. Chard, Z. Li, K. Chard, L. Ward, Y. Babuji, A. Woodard, S. Tuecke, B. Blaiszik, M. J. Franklin, and I. Foster, “Dlhub: Model and data serving for science,” in _2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS)_ , 2019, pp. 283–292.
  * [3] H. Face, “Transformers,” https://github.com/huggingface/transformers.
  * [4] NVIDIA, “FasterTransformer,” https://github.com/NVIDIA/FasterTransformer.
  * [5] OpenAI, “OpenAI research GPT4,” https://openai.com/research/gpt-4.
  * [6] Y. Sheng, L. Zheng, B. Yuan, Z. Li, M. Ryabinin, D. Y. Fu, Z. Xie, B. Chen, C. Barrett, J. E. Gonzalez, P. Liang, C. Ré, I. Stoica, and C. Zhang, “High-throughput Generative Inference of Large Language Models with a Single GPU,” _arXiv e-prints_ , p. arXiv:2303.06865, Mar. 2023.
  * [7] Google, “Bard,” https://bard.google.com/.
  * [8] OpenAI, “ChatGPT,” https://chat.openai.com/.
  * [9] P. Liang, R. Bommasani, T. Lee, D. Tsipras, D. Soylu, M. Yasunaga, Y. Zhang, D. Narayanan, Y. Wu, A. Kumar, B. Newman, B. Yuan, B. Yan, C. Zhang, C. Cosgrove, C. D. Manning, C. Ré, D. Acosta-Navas, D. A. Hudson, E. Zelikman, E. Durmus, F. Ladhak, F. Rong, H. Ren, H. Yao, J. Wang, K. Santhanam, L. Orr, L. Zheng, M. Yuksekgonul, M. Suzgun, N. Kim, N. Guha, N. Chatterji, O. Khattab, P. Henderson, Q. Huang, R. Chi, S. M. Xie, S. Santurkar, S. Ganguli, T. Hashimoto, T. Icard, T. Zhang, V. Chaudhary, W. Wang, X. Li, Y. Mai, Y. Zhang, and Y. Koreeda, “Holistic Evaluation of Language Models,” _arXiv e-prints_ , p. arXiv:2211.09110, Nov. 2022.
  * [10] A. Narayan, I. Chami, L. Orr, S. Arora, and C. Ré, “Can Foundation Models Wrangle Your Data?” _arXiv e-prints_ , p. arXiv:2205.09911, May 2022.
  * [11] B. Lefaudeux, F. Massa, D. Liskovich, W. Xiong, V. Caggiano, S. Naren, M. Xu, J. Hu, M. Tintore, S. Zhang, P. Labatut, and D. Haziza, “xformers: A modular and hackable transformer modelling library,” https://github.com/facebookresearch/xformers, 2022.
  * [12] M. Brysbaert, “How many words do we read per minute? a review and meta-analysis of reading rate,” _Journal of Memory and Language_ , vol. 109, p. 104047, 2019. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0749596X19300786
  * [13] OpenAI, “OpenAI API Documentation,” https://help.openai.com/en/articles/4936856-what-are-tokens-and-how-to-count-them.
  * [14] H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro, F. Azhar, A. Rodriguez, A. Joulin, E. Grave, and G. Lample, “Llama: Open and efficient foundation language models,” _arXiv preprint arXiv:2302.13971_ , 2023.
  * [15] S. Black, S. Biderman, E. Hallahan, Q. Anthony, L. Gao, L. Golding, H. He, C. Leahy, K. McDonell, J. Phang, M. Pieler, U. S. Prashanth, S. Purohit, L. Reynolds, J. Tow, B. Wang, and S. Weinbach, “GPT-NeoX-20B: An open-source autoregressive language model,” in _Proceedings of BigScience Episode #5 – Workshop on Challenges & Perspectives in Creating Large Language Models_. virtual+Dublin: Association for Computational Linguistics, May 2022, pp. 95–136. [Online]. Available: https://aclanthology.org/2022.bigscience-1.9
  * [16] G.-I. Yu, J. S. Jeong, G.-W. Kim, S. Kim, and B.-G. Chun, “Orca: A distributed serving system for Transformer-Based generative models,” in _16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22)_. Carlsbad, CA: USENIX Association, Jul. 2022, pp. 521–538. [Online]. Available: https://www.usenix.org/conference/osdi22/presentation/yu
  * [17] V. Sanh, L. Debut, J. Chaumond, and T. Wolf, “DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter,” _arXiv e-prints_ , p. arXiv:1910.01108, Oct. 2019.
  * [18] R. Taori, I. Gulrajani, T. Zhang, Y. Dubois, X. Li, C. Guestrin, P. Liang, and T. B. Hashimoto, “Stanford alpaca: An instruction-following llama model,” https://github.com/tatsu-lab/stanford_alpaca, 2023.
  * [19] T. Kwiatkowski, J. Palomaki, O. Redfield, M. Collins, A. Parikh, C. Alberti, D. Epstein, I. Polosukhin, M. Kelcey, J. Devlin, K. Lee, K. N. Toutanova, L. Jones, M.-W. Chang, A. Dai, J. Uszkoreit, Q. Le, and S. Petrov, “Natural questions: a benchmark for question answering research,” 2019.
  * [20] L. Gao, S. Biderman, S. Black, L. Golding, T. Hoppe, C. Foster, J. Phang, H. He, A. Thite, N. Nabeshima, S. Presser, and C. Leahy, “The Pile: An 800GB Dataset of Diverse Text for Language Modeling,” p. arXiv:2101.00027, Dec. 2020.
  * [21] B. Wang and A. Komatsuzaki, “GPT-J-6B: A 6 Billion Parameter Autoregressive Language Model,” https://github.com/kingoflolz/mesh-transformer-jax, May 2021.
  * [22] D. S. Johnson, “Near-optimal bin packing algorithms,” Ph.D. dissertation, Massachusetts Institute of Technology, 1973.
  * [23] PyTorch, “Pytorch Nested Tensor,” https://pytorch.org/docs/stable/nested.html.
  * [24] 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. [Online]. Available: http://papers.neurips.cc/paper/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf
  * [25] M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard _et al._ , “Tensorflow: A system for large-scale machine learning,” in _12th $\\{$USENIX$\\}$ Symposium on Operating Systems Design and Implementation ($\\{$OSDI$\\}$ 16)_, 2016, pp. 265–283.
  * [26] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert-Voss, G. Krueger, T. Henighan, R. Child, A. Ramesh, D. M. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei, “Language Models are Few-Shot Learners,” _arXiv e-prints_ , p. arXiv:2005.14165, May 2020.
  * [27] Lenovo, “Lenovo ThinkSystem SD650-N V2 Server,” https://lenovopress.lenovo.com/lp1396-thinksystem-sd650-n-v2-server.
  * [28] F. Romero, Q. Li, N. J. Yadwadkar, and C. Kozyrakis, “INFaaS: Automated model-less inference serving,” in _2021 USENIX Annual Technical Conference (USENIX ATC 21)_. USENIX Association, Jul. 2021, pp. 397–411. [Online]. Available: https://www.usenix.org/conference/atc21/presentation/romero
  * [29] A. Gujarati, R. Karimi, S. Alzayat, W. Hao, A. Kaufmann, Y. Vigfusson, and J. Mace, “Serving DNNs like clockwork: Performance predictability from the bottom up,” in _14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20)_. USENIX Association, Nov. 2020, pp. 443–462. [Online]. Available: https://www.usenix.org/conference/osdi20/presentation/gujarati
  * [30] S. Choi, S. Lee, Y. Kim, J. Park, Y. Kwon, and J. Huh, “Serving heterogeneous machine learning models on Multi-GPU servers with Spatio-Temporal sharing,” in _2022 USENIX Annual Technical Conference (USENIX ATC 22)_. Carlsbad, CA: USENIX Association, Jul. 2022, pp. 199–216. [Online]. Available: https://www.usenix.org/conference/atc22/presentation/choi-seungbeom
  * [31] R. Yazdani Aminabadi, S. Rajbhandari, M. Zhang, A. A. Awan, C. Li, D. Li, E. Zheng, J. Rasley, S. Smith, O. Ruwase, and Y. He, “DeepSpeed Inference: Enabling Efficient Inference of Transformer Models at Unprecedented Scale,” _arXiv e-prints_ , p. arXiv:2207.00032, Jun. 2022\.
  * [32] U. Gupta, S. Hsia, V. Saraph, X. Wang, B. Reagen, G.-Y. Wei, H.-H. S. Lee, D. Brooks, and C.-J. Wu, “DeepRecSys: A System for Optimizing End-To-End At-scale Neural Recommendation Inference,” _arXiv e-prints_ , p. arXiv:2001.02772, Jan. 2020.
  * [33] S. Hsia, U. Gupta, B. Acun, N. Ardalani, P. Zhong, G.-Y. Wei, D. Brooks, and C.-J. Wu, “Mp-rec: Hardware-software co-design to enable multi-path recommendation,” in _Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3_ , ser. ASPLOS 2023. New York, NY, USA: Association for Computing Machinery, 2023, p. 449–465. [Online]. Available: https://doi.org/10.1145/3582016.3582068
  * [34] J. Fang, Y. Yu, C. Zhao, and J. Zhou, “TurboTransformers: An Efficient GPU Serving System For Transformer Models,” _arXiv e-prints_ , p. arXiv:2010.05680, Oct. 2020.
  * [35] C.-F. Wu, C.-J. Wu, G.-Y. Wei, and D. Brooks, “A joint management middleware to improve training performance of deep recommendation systems with ssds,” in _Proceedings of the 59th ACM/IEEE Design Automation Conference (DAC 22)_ , 2022, pp. 157–162.
  * [36] C. Olston, N. Fiedel, K. Gorovoy, J. Harmsen, L. Lao, F. Li, V. Rajashekhar, S. Ramesh, and J. Soyke, “TensorFlow-Serving: Flexible, High-Performance ML Serving,” _arXiv e-prints_ , p. arXiv:1712.06139, Dec. 2017.
  * [37] R. Pope, S. Douglas, A. Chowdhery, J. Devlin, J. Bradbury, A. Levskaya, J. Heek, K. Xiao, S. Agrawal, and J. Dean, “Efficiently scaling transformer inference,” _arXiv preprint arXiv:2211.05102_ , 2022.
  * [38] X. Wang, Y. Xiong, Y. Wei, M. Wang, and L. Li, “LightSeq: A High Performance Inference Library for Transformers,” _arXiv e-prints_ , p. arXiv:2010.13887, Oct. 2020.
  * [39] Huggingface, “Hugginface Accelerate,” https://huggingface.co/docs/accelerate/index.
  * [40] K. Choromanski, V. Likhosherstov, D. Dohan, X. Song, A. Gane, T. Sarlos, P. Hawkins, J. Davis, A. Mohiuddin, L. Kaiser, D. Belanger, L. Colwell, and A. Weller, “Rethinking Attention with Performers,” _arXiv e-prints_ , p. arXiv:2009.14794, Sep. 2020.
  * [41] V. Likhosherstov, K. Choromanski, J. Davis, X. Song, and A. Weller, “Sub-Linear Memory: How to Make Performers SLiM,” _arXiv e-prints_ , p. arXiv:2012.11346, Dec. 2020.
  * [42] I. Beltagy, M. E. Peters, and A. Cohan, “Longformer: The Long-Document Transformer,” _arXiv e-prints_ , p. arXiv:2004.05150, Apr. 2020.
  * [43] M. Zaheer, G. Guruganesh, A. Dubey, J. Ainslie, C. Alberti, S. Ontanon, P. Pham, A. Ravula, Q. Wang, L. Yang, and A. Ahmed, “Big Bird: Transformers for Longer Sequences,” _arXiv e-prints_ , p. arXiv:2007.14062, Jul. 2020.
  * [44] H. Wang, Z. Zhang, and S. Han, “SpAtten: Efficient Sparse Attention Architecture with Cascade Token and Head Pruning,” _arXiv e-prints_ , p. arXiv:2012.09852, Dec. 2020.
  * [45] N. Shazeer, “Fast Transformer Decoding: One Write-Head is All You Need,” _arXiv e-prints_ , p. arXiv:1911.02150, Nov. 2019.
  * [46] J. W. Rae, A. Potapenko, S. M. Jayakumar, and T. P. Lillicrap, “Compressive Transformers for Long-Range Sequence Modelling,” _arXiv e-prints_ , p. arXiv:1911.05507, Nov. 2019.
  * [47] S. Kim, A. Gholami, Z. Yao, M. W. Mahoney, and K. Keutzer, “I-BERT: Integer-only BERT Quantization,” _arXiv e-prints_ , p. arXiv:2101.01321, Jan. 2021.
  * [48] Z. Liu, Y. Wang, K. Han, W. Zhang, S. Ma, and W. Gao, “Post-training quantization for vision transformer,” in _Advances in Neural Information Processing Systems_ , M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, Eds., vol. 34. Curran Associates, Inc., 2021, pp. 28 092–28 103. [Online]. Available: https://proceedings.neurips.cc/paper_files/paper/2021/file/ec8956637a99787bd197eacd77acce5e-Paper.pdf
  * [49] Z. Yang, Y. Gao, W. Wang, and H. Ney, “Predicting and using target length in neural machine translation,” in _Proceedings of the 1st Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics and the 10th International Joint Conference on Natural Language Processing_. Suzhou, China: Association for Computational Linguistics, Dec. 2020, pp. 389–395. [Online]. Available: https://aclanthology.org/2020.aacl-main.41
  * [50] V. Janapa Reddi, C. Cheng, D. Kanter, P. Mattson, G. Schmuelling, C.-J. Wu, B. Anderson, M. Breughe, M. Charlebois, W. Chou, R. Chukka, C. Coleman, S. Davis, P. Deng, G. Diamos, J. Duke, D. Fick, J. S. Gardner, I. Hubara, S. Idgunji, T. B. Jablin, J. Jiao, T. St. John, P. Kanwar, D. Lee, J. Liao, A. Lokhmotov, F. Massa, P. Meng, P. Micikevicius, C. Osborne, G. Pekhimenko, A. Tejusve Raghunath Rajan, D. Sequeira, A. Sirasao, F. Sun, H. Tang, M. Thomson, F. Wei, E. Wu, L. Xu, K. Yamada, B. Yu, G. Yuan, A. Zhong, P. Zhang, and Y. Zhou, “MLPerf Inference Benchmark,” _arXiv e-prints_ , p. arXiv:1911.02549, Nov. 2019.