$\pi({\bm{b}})=(b_{i_{1}},\ldots,b_{i_{K-1}})^{\top}$, where
$b_{i_{1}}\leq\ldots\leq b_{i_{K-1}}$ with $i_{1},\ldots,i_{K-1}\in[K-1]$
satisfying $i_{l}\neq i_{m}$ if $l\neq m$. Then, (a10) and (a11) hold with

$\displaystyle\begin{split}&(\hat{a},\hat{{\bm{b}}})\in\underset{a\in{\mathcal{A}},{\bm{b}}\in{\mathcal{B}}}{\operatorname{{arg\,min}}}\,\frac{1}{n}\sum_{i=1}^{n}\\{\phi(a({\bm{x}}_{i}),{\bm{b}},y_{i})+\Lambda(a,{\bm{b}},{\bm{x}}_{i},y_{i})\\},\\\
&(\bar{a},\bar{{\bm{b}}})\in\underset{a\in{\mathcal{A}},{\bm{b}}\in{\mathcal{B}}}{\operatorname{{arg\,min}}}\,\operatorname{{\mathbb{E}}}[\phi(a({\bm{X}}),{\bm{b}},Y)+\Lambda(a,{\bm{b}},{\bm{X}},Y)]\end{split}$
(39)

instead of (5) and (7).

As the regularization term $\Lambda(a,{\bm{b}},{\bm{x}},y)$, Shashua and Levin
[2003] use $\Lambda(a,{\bm{b}},{\bm{x}},y)\propto\|{\bm{w}}\|_{2}^{2}$ for a
linear 1DT $a({\bm{x}})={\bm{w}}^{\top}{\bm{x}}+w_{0}$ (with
${\bm{w}}\in{\mathbb{R}}^{d}$ and $w_{0}\in{\mathbb{R}}$), and Lin and Li
[2012] add the term proportional to $\|{\bm{b}}\|_{2}^{2}$, where
$\|\cdot\|_{2}$ is the $L_{2}$ norm. Corollary 1 covers these methods.

##### Proof of Theorem 2

Theorem 2 can be proved by the proof strategy by Yamasaki [2023]:

###### Proof of Theorem 2.

Proof of (b1) Yamasaki [2023, Theorem 2] showed the statement for the
Logistic-AT loss. Thus, we here describe the proof of the statement for the
Exponential-AT loss. According to (36), one has that, under the assumption
(8),

$\displaystyle\begin{split}&\operatorname{{\mathbb{E}}}[\phi(a({\bm{X}}),{\bm{b}},Y)]\\\
&=\operatorname{{\mathbb{E}}}\biggl{[}\sum_{y=1}^{K-1}\biggl{\\{}\frac{1}{1+e^{-(\tilde{b}_{y}-\tilde{a}({\bm{X}}))}}\varphi(b_{y}-a({\bm{X}}))+\frac{1}{1+e^{(\tilde{b}_{y}-\tilde{a}({\bm{X}}))}}\varphi(a({\bm{X}})-b_{y})\biggr{\\}}\biggr{]}.\end{split}$
(40)

Then, we consider the following optimization problem conditioned on
${\bm{X}}={\bm{x}}$:

$\displaystyle\begin{split}&\min_{a({\bm{x}})\in{\mathbb{R}},{\bm{b}}\in{\mathcal{B}}_{0}^{\rm
ord}}L(a({\bm{x}}),{\bm{b}})\\\
&\text{with~{}}L(a({\bm{x}}),{\bm{b}}):=\sum_{y=1}^{K-1}\biggl{\\{}\frac{1}{1+e^{-(\tilde{b}_{y}-\tilde{a}({\bm{x}}))}}e^{-(b_{y}-a({\bm{x}}))}+\frac{1}{1+e^{(\tilde{b}_{y}-\tilde{a}({\bm{x}}))}}e^{(b_{y}-a({\bm{x}}))}\biggr{\\}}.\end{split}$
(41)

The derivatives of the function $L$ become

$\displaystyle\begin{split}\frac{\partial L}{\partial
a({\bm{x}})}&=\sum_{y=1}^{K-1}\biggl{\\{}\frac{1}{1+e^{-(\tilde{b}_{y}-\tilde{a}({\bm{x}}))}}e^{-(b_{y}-a({\bm{x}}))}-\frac{1}{1+e^{(\tilde{b}_{y}-\tilde{a}({\bm{x}}))}}e^{(b_{y}-a({\bm{x}}))}\biggr{\\}},\\\
\frac{\partial L}{\partial
b_{y}}&=-\frac{1}{1+e^{-(\tilde{b}_{y}-\tilde{a}({\bm{x}}))}}e^{-(b_{y}-a({\bm{x}}))}+\frac{1}{1+e^{(\tilde{b}_{y}-\tilde{a}({\bm{x}}))}}e^{(b_{y}-a({\bm{x}}))}.\end{split}$
(42)

One can find $\frac{\partial L}{\partial a({\bm{x}})}=\frac{\partial
L}{\partial b_{1}}=\cdots=\frac{\partial L}{\partial b_{K-1}}=0$ at
$(a({\bm{x}}),{\bm{b}})=(\tilde{a}({\bm{x}})/2,\tilde{{\bm{b}}}/2)$. Since
$\tilde{a}({\bm{x}})/2\in{\mathbb{R}}$ and
$\tilde{{\bm{b}}}/2\in{\mathcal{B}}_{0}^{\rm ord}$ and (41) is a convex
optimization problem, this pair is a unique solution of (41). This solution is
valid for any ${\bm{x}}$ in the support of the probability distribution of
${\bm{X}}$, so it is ensured that
$(\bar{a}({\bm{X}}),\bar{{\bm{b}}})=(\tilde{a}({\bm{X}})/2,\tilde{{\bm{b}}}/2)$
almost surely.

Proof of (b2) The statement (b2) can be proved directly from Yamasaki [2023,
Theorems 3 and 4]: In general, the conditional task risk at
${\bm{X}}={\bm{x}}$ can be written as

$\displaystyle\operatorname{{\mathbb{E}}}[\ell(f({\bm{x}}),Y)]=\sum_{y=1}^{K}\Pr(Y=y|{\bm{X}}={\bm{x}})\ell(f({\bm{x}}),y).$
(43)

Thus, under the assumption (8) of this theorem, the following labeling
function becomes optimal in minimizing the task risk:

$\displaystyle h_{\rm
cl}(u;\hat{{\bm{b}}})\in\underset{k\in[K]}{\operatorname{{arg\,min}}}\,\sum_{y=1}^{K}P_{\rm
cl}(y;u,\bar{{\bm{b}}})\ell(k,y).$ (44)

Yamasaki [2023, Theorems 3 and 4] analyzed the labeling function (44), and
showed its relationships to the threshold labeling. Refer to those theorems
for a detailed proof of this statement. ∎

##### Proof of Theorem 3

We describe the proof of Theorem 3 (c6) and (c7) in the following:

###### Proof of Theorem 3.

Proof of (c1)–(c5) The results (c1) and (c2) can be shown from simple
calculations, and the results (c3)–(c5) are shown in Yamasaki [2023, Lemma 1].
Therefore, we omit the proof for these results.

Proof of (c6) (c3)–(c5) show this statement: On has

$\displaystyle P_{\rm cl}(k;u,{\bm{b}})=P_{\rm
cl}\bigl{(}k;\tfrac{b_{k-1}+b_{k}}{2}-\bigl{\\{}\tfrac{b_{k-1}+b_{k}}{2}-u\bigr{\\}},{\bm{b}}\bigr{)}=P_{\rm
cl}\bigl{(}k;\tfrac{b_{k-1}+b_{k}}{2}-\bigl{|}\tfrac{b_{k-1}+b_{k}}{2}-u\bigr{|},{\bm{b}}\bigr{)}$
(45)

from (c3). Under the assumption, it holds that
$|\tfrac{b_{1}+b_{2}}{2}-u|\geq\cdots\geq|\tfrac{b_{m-1}+b_{m}}{2}-u|$ and
$|\tfrac{b_{m-1}+b_{m}}{2}-u|\leq\cdots\leq|\tfrac{b_{K-2}+b_{K-1}}{K-1}-u|$.
These results, together with (c4) and (c5), show (c6).

Proof of (c7) Consider the comparison

$\displaystyle\begin{split}&P_{\rm
cl}(1;u,{\bm{b}})=\frac{1}{1+e^{-(b_{1}-u)}}=\frac{1}{1+e^{u}}\\\ &\gtrless
P_{\rm
cl}(2;u,{\bm{b}})=\frac{1}{1+e^{-(b_{2}-u)}}-\frac{1}{1+e^{-(b_{1}-u)}}=\frac{1}{1+e^{u-\Delta}}-\frac{1}{1+e^{u}}\end{split}$
(46)

with $b_{1}=0$. Then, one has that $\Delta_{1}=-\log\\{(1-e^{-u})/2\\}$ if
$u>0$ and $\Delta_{1}=0$ if $u<0$. Although $\Delta_{2}$ cannot be represented
explicitly, the similar calculation shows that
$\Delta_{2}=-\log\\{(1-e^{u-(K-2)\Delta_{2}})/2\\}$ if $u<(K-2)\Delta_{2}$,
and $\Delta_{2}=0$ if $u>(K-2)\Delta_{2}$. ∎

##### Proof of Theorem 4

The following is a proof of Theorem 4.

###### Proof of Theorem 4.

According to (36), one has

$\displaystyle\begin{split}&\operatorname{{\mathbb{E}}}[\phi(a({\bm{X}}),{\bm{b}},Y)]\\\
&=\operatorname{{\mathbb{E}}}\biggl{[}\sum_{y=1}^{K-1}\bigl{[}\Pr(Y\leq
y|{\bm{X}})\\{1-(b_{y}-a({\bm{X}}))\\}^{2}+\Pr(Y>y|{\bm{X}})\\{1+(b_{y}-a({\bm{X}}))\\}^{2}\bigr{]}\biggr{]}.\end{split}$
(47)

The stationary condition with respect to $a({\bm{x}})$,

$\displaystyle\begin{split}&\frac{\partial\operatorname{{\mathbb{E}}}[\phi(a({\bm{X}}),{\bm{b}},Y)]}{\partial
a({\bm{x}})}\biggr{|}_{a({\bm{X}})=\bar{a}({\bm{X}}),{\bm{b}}=\bar{{\bm{b}}}}\\\
&=\sum_{y=1}^{K-1}\bigl{[}\Pr(Y\leq
y|{\bm{X}}={\bm{x}})\\{1-(\bar{b}_{y}-\bar{a}({\bm{x}}))\\}-\Pr(Y>y|{\bm{X}}={\bm{x}})\\{1+(\bar{b}_{y}-\bar{a}({\bm{x}}))\\}\bigr{]}\\\
&=(K-1)\bar{a}({\bm{x}})-\biggl{\\{}(K-1)+\sum_{y=1}^{K-1}\bar{b}_{y}-2\sum_{y=1}^{K-1}\Pr(Y\leq
y|{\bm{X}}={\bm{x}})\biggr{\\}}=0,\end{split}$ (48)

shows

$\displaystyle\bar{a}({\bm{x}})=1+\frac{1}{K-1}\sum_{y=1}^{K-1}\bar{b}_{y}-\frac{2}{K-1}\sum_{y=1}^{K-1}\Pr(Y\leq
y|{\bm{X}}={\bm{x}}).$ (49)

Also, the stationary condition with respect to $b_{y}$,

$\displaystyle\begin{split}&\frac{\partial\operatorname{{\mathbb{E}}}[\phi(a({\bm{X}}),{\bm{b}},Y)]}{\partial
b_{y}}\biggr{|}_{a({\bm{X}})=\bar{a}({\bm{X}}),{\bm{b}}=\bar{{\bm{b}}}}\\\
&=\operatorname{{\mathbb{E}}}\bigl{[}\Pr(Y\leq
y|{\bm{X}})\\{1-(\bar{b}_{y}-\bar{a}({\bm{X}}))\\}-\Pr(Y>y|{\bm{X}})\\{1+(\bar{b}_{y}-\bar{a}({\bm{X}}))\\}\bigr{]}\\\
&=\operatorname{{\mathbb{E}}}\bigl{[}\\{2\Pr(Y\leq
y|{\bm{X}})-1\\}-(\bar{b}_{y}-\bar{a}({\bm{X}}))\bigr{]}=\bigl{\\{}2\Pr(Y\leq
y)-1+\operatorname{{\mathbb{E}}}\bigl{[}\bar{a}({\bm{X}})\bigr{]}\bigr{\\}}-\bar{b}_{y}=0,\end{split}$
(50)

shows

$\displaystyle\bar{b}_{y}=\frac{1}{K-1}\sum_{k=1}^{K-1}\bar{b}_{k}+2\Pr(Y\leq
y)-\frac{2}{K-1}\sum_{k=1}^{K-1}\Pr(Y\leq k).$ (51)

On can see that $(\bar{a},\bar{{\bm{b}}})=(\tilde{a},\tilde{{\bm{b}}})$ with
$(\tilde{a},\tilde{{\bm{b}}})$ in (9) satisfies (49) and (51). Since the
corresponding the surrogate risk minimization problem is a convex optimization
problem, $(\bar{a},\bar{{\bm{b}}})=(\tilde{a},\tilde{{\bm{b}}})$ is its unique
solution under the assumption
$(\tilde{a},\tilde{{\bm{b}}})\in{\mathcal{A}}\times{\mathcal{B}}$. ∎

##### Proof of Theorem 5

Theorem 5 can be proved similarly to Theorem 2:

###### Proof of Theorem 5.

Proof of (f1) The surrogate risk for the IT loss $\phi$ based on $\varphi$ is

$\displaystyle\begin{split}&\operatorname{{\mathbb{E}}}[\phi(a({\bm{X}}),{\bm{b}},Y)]\\\
&=\operatorname{{\mathbb{E}}}\biggl{[}\sum_{y=1}^{K-1}\bigl{\\{}\Pr(Y=y|{\bm{X}})\varphi(b_{y}-a({\bm{X}}))+\Pr(Y=y+1|{\bm{X}})\varphi(a({\bm{X}})-b_{y})\bigr{\\}}\biggr{]}.\end{split}$
(52)

Under the assumption on $\Pr(Y=y|{\bm{X}}={\bm{x}})$, one has

$\displaystyle\begin{split}&\Pr(Y=y|{\bm{X}}={\bm{x}})\varphi(b_{y}-a({\bm{x}}))+\Pr(Y=y+1|{\bm{X}}={\bm{x}})\varphi(a({\bm{x}})-b_{y})\\\
&=c_{y}\biggl{\\{}\frac{1}{1+e^{-(\tilde{b}_{y}-\tilde{a}({\bm{x}}))}}\varphi(b_{y}-a({\bm{x}}))+\frac{1}{1+e^{(\tilde{b}_{y}-\tilde{a}({\bm{x}}))}}\varphi(a({\bm{x}})-b_{y})\biggr{\\}}\end{split}$
(53)

with a positive constant $c_{y}$, because of Theorem 6 (g1). Letting
$R(a({\bm{x}}),{\bm{b}}):=\operatorname{{\mathbb{E}}}[\phi(a({\bm{x}}),{\bm{b}},Y)]$,
the derivatives of the function $R$ with $\varphi=\varphi_{\rm logi}$ are

$\displaystyle\begin{split}\frac{\partial R}{\partial
a({\bm{x}})}&=\sum_{y=1}^{K-1}c_{y}\biggl{\\{}\frac{1}{1+e^{-(\tilde{b}_{y}-\tilde{a}({\bm{x}}))}}\frac{1}{1+e^{(b_{y}-a({\bm{x}}))}}-\frac{1}{1+e^{(\tilde{b}_{y}-\tilde{a}({\bm{x}}))}}\frac{1}{1+e^{-(b_{y}-a({\bm{x}}))}}\biggr{\\}},\\\
\frac{\partial R}{\partial
b_{y}}&=-c_{y}\biggl{\\{}\frac{1}{1+e^{-(\tilde{b}_{y}-\tilde{a}({\bm{x}}))}}\frac{1}{1+e^{(b_{y}-a({\bm{x}}))}}-\frac{1}{1+e^{(\tilde{b}_{y}-\tilde{a}({\bm{x}}))}}\frac{1}{1+e^{-(b_{y}-a({\bm{x}}))}}\biggr{\\}},\end{split}$
(54)

and those with $\varphi=\varphi_{\rm expo}$ are

$\displaystyle\begin{split}\frac{\partial R}{\partial
a({\bm{x}})}&=\sum_{y=1}^{K-1}c_{y}\biggl{\\{}\frac{1}{1+e^{-(\tilde{b}_{y}-\tilde{a}({\bm{x}}))}}e^{-(b_{y}-a({\bm{x}}))}-\frac{1}{1+e^{(\tilde{b}_{y}-\tilde{a}({\bm{x}}))}}e^{(b_{y}-a({\bm{x}}))}\biggr{\\}},\\\
\frac{\partial R}{\partial
b_{y}}&=-c_{y}\biggl{\\{}\frac{1}{1+e^{-(\tilde{b}_{y}-\tilde{a}({\bm{x}}))}}e^{-(b_{y}-a({\bm{x}}))}-\frac{1}{1+e^{(\tilde{b}_{y}-\tilde{a}({\bm{x}}))}}e^{(b_{y}-a({\bm{x}}))}\biggr{\\}}.\end{split}$
(55)

Substituting $(a({\bm{x}}),{\bm{b}})=(\tilde{a}({\bm{x}}),\tilde{{\bm{b}}})$
into these derivatives with $\varphi=\varphi_{\rm logi}$ or
$(a({\bm{x}}),{\bm{b}})=(\tilde{a}({\bm{x}})/2,\tilde{{\bm{b}}}/2)$ into these
derivatives with $\varphi=\varphi_{\rm expo}$, one can find $\frac{\partial
R}{\partial a({\bm{x}})}=\frac{\partial R}{\partial
b_{1}}=\cdots=\frac{\partial R}{\partial b_{K-1}}=0$. Therefore, the
optimization problem
$\min_{a({\bm{x}})\in{\mathbb{R}},{\bm{b}}\in{\mathcal{B}}_{0}}R(a({\bm{x}}),{\bm{b}})$
conditioned on ${\bm{X}}={\bm{x}}$, which is a convex optimization problem,
has a unique solution, $(\tilde{a}({\bm{x}}),\tilde{{\bm{b}}})$ when
$\varphi=\varphi_{\rm logi}$ or $(\tilde{a}({\bm{x}})/2,\tilde{{\bm{b}}}/2)$
when $\varphi=\varphi_{\rm expo}$. This solution is valid for any ${\bm{x}}$
in the support of the probability distribution of ${\bm{X}}$, so the proof of
the statement (f1) is concluded.

Proof of (f2) Since the statement for the Exponential-IT loss can be proved in
the same way, here we describe the proof for the Logistic-IT loss only. Since
$\operatorname{{arg\,min}}_{f({\bm{x}})\in[K]}\operatorname{{\mathbb{E}}}[\ell(f({\bm{x}}),Y)]=\operatorname{{arg\,max}}_{k\in[K]}P_{\rm
acl}(k;\bar{a}({\bm{x}}),\bar{{\bm{b}}})$ when $\ell=\ell_{\rm zo}$ due to
(11) and the threshold labeling $h_{\rm thr}(u;{\bm{t}})$ is non-decreasing in
$u$, it is sufficient to show that $\operatorname{{arg\,max}}_{k\in[K]}P_{\rm
acl}(k;u_{1},\bar{{\bm{b}}})\leq\operatorname{{arg\,max}}_{k\in[K]}P_{\rm
acl}(k;u_{2},\bar{{\bm{b}}})$ if $u_{1}\leq u_{2}$ for (f2). This inequality
is guaranteed if it can be shown that there is no pair $(l,m)\in[K]^{2}$ such
that $l<m$ and $P_{\rm acl}(l;u_{1},\bar{{\bm{b}}})\leq P_{\rm
acl}(m;u_{1},\bar{{\bm{b}}})$ and $P_{\rm acl}(l;u_{2},\bar{{\bm{b}}})\geq
P_{\rm acl}(m;u_{2},\bar{{\bm{b}}})$ with $u_{1},u_{2}\in{\mathbb{R}}$ such
that $u_{1}<u_{2}$ (imagine $l=\operatorname{{arg\,max}}_{k\in[K]}P_{\rm
acl}(k;u_{1},\bar{{\bm{b}}})$ and $m=\operatorname{{arg\,max}}_{k\in[K]}P_{\rm
acl}(k;u_{2},\bar{{\bm{b}}})$). From Theorem 6 (g1), one has that $P_{\rm
acl}(m;u_{1},\bar{{\bm{b}}})/P_{\rm
acl}(l;u_{1},\bar{{\bm{b}}})=e^{-\sum_{k=l}^{m-1}(\bar{b}_{k}-u_{1})}<P_{\rm
acl}(m;u_{2},\bar{{\bm{b}}})/P_{\rm
acl}(l;u_{2},\bar{{\bm{b}}})=e^{-\sum_{k=l}^{m-1}(\bar{b}_{k}-u_{2})}=e^{-\sum_{k=l}^{m-1}(b_{k}-u_{1})}\cdot
e^{(m-l)(u_{2}-u_{1})}$. This result shows the absence of the above-described
pair $(l,m)$, which concludes the proof of (f2).

Proof of (f3) This is obvious from Theorem 6 (g2).

Proof of (f4) This is clear if considering Karush-Kuhn-Tucker conditions for
the constrained optimization problem. ∎

##### Proof of Theorem 6

Theorem 6 is on structural properties of the ACL model $(P_{\rm
acl}(y;u,{\bm{b}}))_{y\in[K]}$, and can be proved as follows:

###### Proof of Theorem 6.

Proof of (g1) For each $y\in[K-1]$, one has

$\displaystyle\begin{split}\frac{P_{\rm acl}(y+1;u,{\bm{b}})}{P_{\rm
acl}(y;u,{\bm{b}})}&=\frac{e^{-\sum_{k=1}^{y}(b_{k}-u)}}{\sum_{l=1}^{K}e^{-\sum_{k=1}^{l-1}(b_{k}-u)}}\biggr{/}\frac{e^{-\sum_{k=1}^{y-1}(b_{k}-u)}}{\sum_{l=1}^{K}e^{-\sum_{k=1}^{l-1}(b_{k}-u)}}\\\
&=e^{-(b_{y}-u)}=\biggl{(}\frac{1}{1+e^{(b_{y}-u)}}\biggr{)}\biggr{/}\biggl{(}\frac{1}{1+e^{-(b_{y}-u)}}\biggr{)}.\end{split}$
(56)

Proof of (g2) When $b_{1}\leq\cdots\leq b_{m-1}\leq u\leq b_{m}\leq\cdots\leq
b_{K-1}$, one has $b_{1}-u\leq\cdots\leq b_{m-1}-u\leq 0\leq
b_{m}-u\leq\cdots\leq b_{K-1}-u$, which, together with (g1), shows

$\displaystyle\begin{split}&\frac{P_{\rm acl}(2;u,{\bm{b}})}{P_{\rm
acl}(1;u,{\bm{b}})},\ldots,\frac{P_{\rm acl}(m;u,{\bm{b}})}{P_{\rm
acl}(m-1;u,{\bm{b}})}\geq e^{-0}=1,\\\ &\frac{P_{\rm
acl}(m+1;u,{\bm{b}})}{P_{\rm acl}(m;u,{\bm{b}})},\ldots,\frac{P_{\rm
acl}(K;u,{\bm{b}})}{P_{\rm acl}(K-1;u,{\bm{b}})}\leq e^{-0}=1.\end{split}$
(57)

This result implies that $(P_{\rm acl}(y;u,{\bm{b}}))_{y\in[K]}$ is unimodal
with a mode $m$.

Proof of (g3) (g3) gives a more general condition than (g2) for the ACL model
$(P_{\rm acl}(y;u,{\bm{b}}))_{y\in[K]}$ to be unimodal. Letting
$l_{1}=\max(\\{1\\}\cup\\{k\in[K-1]\mid b_{k}\leq u\\})$ and
$l_{2}=\min(\\{k\in[K-1]\mid b_{k}\geq u\\}\cup\\{K\\})$, one has (i)
$b_{l_{1}}-u\leq 0$, (ii) $b_{l_{1}+1}-u,\ldots,b_{K-1}-u\geq 0$ if $l_{1}\leq
K-2$, (iii) $b_{1}-u,\ldots,b_{l_{2}-1}-u\leq 0$ if $l_{2}\geq 2$, and (iv)
$b_{l_{2}}-u\geq 0$. When $l_{1}=l_{2}=m$, (iii) shows
$b_{1}-u,\ldots,b_{m-1}-u\leq 0$, (iv) shows $b_{m}-u\geq 0$, (ii) shows
$b_{m+1}-u,\ldots,b_{K-1}-u\geq 0$. Also, when $m=l_{1}<l_{2}$, (iii) shows
$b_{1}-u,\ldots,b_{m-1}-u(,\ldots,b_{l_{2}-1}-u)\leq 0$, (i) shows
$b_{m}-u\geq 0$, and (ii) shows $b_{m+1},\ldots,b_{K-1}-u\geq 0$. In both the
cases, (57) holds, and hence, $(P_{\rm acl}(y;u,{\bm{b}}))_{y\in[K]}$ becomes
unimodal with a mode $m$.

Proof of (g4) (g4) gives a sufficient condition that the ACL model $(P_{\rm
acl}(y;u,{\bm{b}}))_{y\in[K]}$ is not unimodal. When $b_{l}-u<0<b_{k}-u$ with
$k<l$, it holds that $P_{\rm acl}(k;u,{\bm{b}})>P_{\rm acl}(k+1;u,{\bm{b}})$
and $P_{\rm acl}(l;u,{\bm{b}})<P_{\rm acl}(l+1;u,{\bm{b}})$, namely, the ACL
model $(P_{\rm acl}(y;u,{\bm{b}}))_{y\in[K]}$ is not unimodal. ∎

##### Proof of Theorem 7

The following is a proof of Theorem 7.

###### Proof of Theorem 7.

According to (52), one has

$\displaystyle\begin{split}&\operatorname{{\mathbb{E}}}[\phi(a({\bm{X}}),{\bm{b}},Y)]\\\
&=\operatorname{{\mathbb{E}}}\biggl{[}\sum_{y=1}^{K-1}\bigl{[}\Pr(Y=y|{\bm{X}})\\{1-(b_{y}-a({\bm{X}}))\\}^{2}+\Pr(Y=y+1|{\bm{X}})\\{1+(b_{y}-a({\bm{X}}))\\}^{2}\bigr{]}\biggr{]}.\end{split}$
(58)

The stationary condition with respect to $a({\bm{x}})$,

$\displaystyle\frac{\partial\operatorname{{\mathbb{E}}}[\phi(a({\bm{X}}),{\bm{b}},Y)]}{\partial
a({\bm{x}})}\biggr{|}_{a({\bm{X}})=\bar{a}({\bm{X}}),{\bm{b}}=\bar{{\bm{b}}}}$
$\displaystyle=\sum_{y=1}^{K-1}\bigl{[}\Pr(Y=y|{\bm{X}}={\bm{x}})\\{1-(\bar{b}_{y}-\bar{a}({\bm{x}}))\\}-\Pr(Y=y+1|{\bm{X}}={\bm{x}})\\{1+(\bar{b}_{y}-\bar{a}({\bm{x}}))\\}\bigr{]}$
(59)
$\displaystyle=\Pr(Y=1|{\bm{X}}={\bm{x}})-\Pr(Y=K|{\bm{X}}={\bm{x}})-\sum_{y=1}^{K-1}\Pr(Y\in\\{y,y+1\\}|{\bm{X}}={\bm{x}})(\bar{b}_{y}-\bar{a}({\bm{x}}))=0,$

shows

$\displaystyle\bar{a}({\bm{x}})=\frac{\sum_{y=1}^{K-1}\Pr(Y\in\\{y,y+1\\}|{\bm{X}}={\bm{x}})\bar{b}_{y}-\Pr(Y=1|{\bm{X}}={\bm{x}})+\Pr(Y=K|{\bm{X}}={\bm{x}})}{\sum_{y=1}^{K-1}\Pr(Y\in\\{y,y+1\\}|{\bm{X}}={\bm{x}})}.$
(60)

The stationary condition with respect to $b_{y}$,

$\displaystyle\frac{\partial\operatorname{{\mathbb{E}}}[\phi(a({\bm{X}}),{\bm{b}},Y)]}{\partial
b_{y}}\biggr{|}_{a({\bm{X}})=\bar{a}({\bm{X}}),{\bm{b}}=\bar{{\bm{b}}}}$
$\displaystyle=\operatorname{{\mathbb{E}}}\bigl{[}\Pr(Y=y|{\bm{X}})\\{1-(\bar{b}_{y}-\bar{a}({\bm{X}}))\\}-\Pr(Y=y+1|{\bm{X}})\\{1+(\bar{b}_{y}-\bar{a}({\bm{X}}))\\}\bigr{]}$
(61)
$\displaystyle=\Pr(Y=y)-\Pr(Y=y+1)-\Pr(Y\in\\{y,y+1\\})\bar{b}_{y}+\operatorname{{\mathbb{E}}}[\Pr(Y\in\\{y,y+1\\}|{\bm{X}})\bar{a}({\bm{X}})]=0,$

shows

$\displaystyle\bar{b}_{y}=\frac{\Pr(Y=y)-\Pr(Y=y+1)+\operatorname{{\mathbb{E}}}[\Pr(Y\in\\{y,y+1\\}|{\bm{X}})\bar{a}({\bm{X}})]}{\Pr(Y\in\\{y,y+1\\})}.$
(62)

On can see that $(\bar{a},\bar{{\bm{b}}})=(\tilde{a},\tilde{{\bm{b}}})$ with
$(\tilde{a},\tilde{{\bm{b}}})$ in (12) satisfies (60) and (62). Since the
corresponding the surrogate risk minimization problem is a convex optimization
problem, $(\bar{a},\bar{{\bm{b}}})=(\tilde{a},\tilde{{\bm{b}}})$ is its unique
solution under the assumption
$(\tilde{a},\tilde{{\bm{b}}})\in{\mathcal{A}}\times{\mathcal{B}}$. ∎

##### Proof of Theorem 8

Theorem 8 is trivial because of the functional form of the AT and IT loss
functions. We omit its proof.

##### Theorem 9 and its Proof for Flat-Bottom (FB) Loss

Many of the function $\varphi$ used in the AT and IT losses are non-increasing
and zero on the side greater than a certain point, for example, $\varphi_{\rm
hing}$, $\varphi_{\rm ramp}$, $\varphi_{\rm sqhi}$, and $\varphi_{\rm smhi}$.
We say that such a function is _flat-bottom_ (_FB_):

######  Definition 2.

If a function $\varphi:{\mathbb{R}}\to{\mathbb{R}}$ is non-increasing and
satisfies that $\varphi(u)>0$ for $u\in(-\infty,c)$ and $\varphi(u)=0$ for
$u\in[c,\infty)$ with some $c\in{\mathbb{R}}$, we say that $\varphi$ is FB
with the edge $c$.

For the surrogate risk minimizer with AT and IT losses based on a FB function
$\varphi$, we found the following result, which we used in Example 1:

######  Theorem 9.

Let ${\mathcal{A}}=\\{a:{\mathbb{R}}^{d}\to{\mathbb{R}}\\}$ and
${\mathcal{B}}={\mathcal{B}}_{0}^{\rm ord}$. If $\phi$ is an AT loss (3) or IT
loss (4) with $\varphi$ that is FB with the edge $c>0$ (e.g.,
$\varphi=\varphi_{\rm hing},\varphi_{\rm ramp},\varphi_{\rm smhi},\varphi_{\rm
sqhi}$ with $c=1$), then there exists $\hat{{\bm{b}}}$ defined by (5) that
satisfies $\hat{b}_{k+1}-\hat{b}_{k}\in[0,2c]$ for all $k\in[K-2]$, and there
exists $\bar{{\bm{b}}}$ defined by (7) that satisfies
$\bar{b}_{k+1}-\bar{b}_{k}\in[0,2c]$ for all $k\in[K-2]$.

###### Proof of Theorem 9.

Here, we describe a proof for the population version only.

Assume any surrogate risk minimizer $(\bar{a},\bar{{\bm{b}}})$ satisfies

$\displaystyle\bar{b}_{l+1}-\bar{b}_{l}>2c\text{~{}for some~{}}l\in[K-2]$ (63)

as assumption for proof by contradiction, and let
$\delta=\bar{b}_{l+1}-\bar{b}_{l}-2c$ and

$\displaystyle\begin{split}&\check{a}({\bm{x}}):=\begin{cases}\bar{a}({\bm{x}})&\text{for~{}}{\bm{x}}\text{~{}s.t.~{}}\bar{a}({\bm{x}})\leq\bar{b}_{l}+c,\\\
\bar{b}_{l}+c&\text{for~{}}{\bm{x}}\text{~{}s.t.~{}}\bar{b}_{l}+c<\bar{a}({\bm{x}})<\bar{b}_{l-1}-c,\\\
\bar{a}({\bm{x}})-\delta&\text{for~{}}{\bm{x}}\text{~{}s.t.~{}}\bar{a}({\bm{x}})\geq\bar{b}_{l-1}-c,\end{cases}\\\
&\check{b}_{1}:=\bar{b}_{1},\cdots,\check{b}_{l}:=\bar{b}_{l},\;\check{b}_{l+1}:=\bar{b}_{l+1}-\delta,\ldots,\check{b}_{K-1}:=\bar{b}_{K-1}-\delta.\end{split}$
(64)

The surrogate risk $\operatorname{{\mathbb{E}}}[\phi(a({\bm{X}}),{\bm{b}},Y)]$
for the AT or IT loss $\phi$ based on $\varphi$ is a weighted mean of
$\varphi(a({\bm{x}})-b_{k})$’s and $\varphi(b_{k}-a({\bm{x}}))$’s with non-
negative weights. In the following, by studying the change in
$\varphi(a({\bm{x}})-b_{k})$’s and $\varphi(b_{k}-a({\bm{x}}))$’s when
changing from $(a,{\bm{b}})=(\bar{a},\bar{{\bm{b}}})$ to
$(a,{\bm{b}})=(\check{a},\check{{\bm{b}}})$, we prove that
$\operatorname{{\mathbb{E}}}[\phi(\bar{a}({\bm{X}}),\bar{{\bm{b}}},Y)]\geq\operatorname{{\mathbb{E}}}[\phi(\check{a}({\bm{X}}),\check{{\bm{b}}},Y)]$.

Consider the case $\bar{a}({\bm{x}})\leq\bar{b}_{l}+c$ Since
$\check{a}({\bm{x}})=\bar{a}({\bm{x}})$ and $\check{b}_{k}=\bar{b}_{k}$ for
$k=1,\ldots,l$, one has that

$\displaystyle\varphi(\bar{a}({\bm{x}})-\bar{b}_{k})=\varphi(\check{a}({\bm{x}})-\check{b}_{k})\text{~{}and~{}}\varphi(\bar{b}_{k}-\bar{a}({\bm{x}}))=\varphi(\check{b}_{k}-\check{a}({\bm{x}}))\text{~{}for~{}}k=1,\ldots,l.$
(65)

Since
$\bar{a}({\bm{x}})-\bar{b}_{k}<\bar{a}({\bm{x}})-\\{\bar{b}_{k}-\delta\\}=\check{a}({\bm{x}})-\check{b}_{k}$
for $k=l+1,\ldots,K-1$ and $\varphi$ is non-increasing, one has that

$\displaystyle\varphi(\bar{a}({\bm{x}})-\bar{b}_{k})\geq\varphi(\check{a}({\bm{x}})-\check{b}_{k})\text{~{}for~{}}k=l+1,\ldots,K-1.$
(66)

One has that $\bar{a}({\bm{x}})<\bar{b}_{l+1}-c$ since
$\bar{b}_{l}+c<\bar{b}_{l+1}-c$, and that
$\bar{a}({\bm{x}})\leq\\{\bar{b}_{l+1}-\delta\\}-c=\check{b}_{l+1}-c$ since
$\bar{b}_{l}+c=\\{\bar{b}_{l+1}-\delta\\}-c$. These imply that

$\displaystyle
c<\bar{b}_{l+1}-\bar{a}({\bm{x}})\leq\cdots\leq\bar{b}_{K-1}-\bar{a}({\bm{x}}),\text{~{}and~{}}c\leq\check{b}_{l+1}-\bar{a}({\bm{x}})\leq\cdots\leq\check{b}_{K-1}-\bar{a}({\bm{x}}),$
(67)

from the assumption $\bar{b}_{l+1}\leq\cdots\leq\bar{b}_{K-1}$ and
$\check{b}_{l+1}\leq\cdots\leq\check{b}_{K-1}$. Since $\varphi(u)=0$ for any
$u\geq c$, one has that

$\displaystyle\varphi(\bar{b}_{k}-\bar{a}({\bm{x}}))=\varphi(\check{b}_{k}-\check{a}({\bm{x}}))=0\text{~{}for~{}}k=l+1,\ldots,K-1.$
(68)

Consider the case $\bar{b}_{l+1}-c\leq\bar{a}({\bm{x}})$ Since
$c\leq\bar{a}({\bm{x}})-\bar{b}_{l}\leq\cdots\leq\bar{a}({\bm{x}})-\bar{b}_{1}$
because $\bar{b}_{l+1}-c\leq\bar{a}({\bm{x}})$ and
$\bar{b}_{1}+c\leq\cdots\leq\bar{b}_{l}+c\leq\bar{b}_{l+1}-c$,
$c\leq\\{\bar{a}({\bm{x}})-\delta\\}-\bar{b}_{l}\leq\cdots\leq\\{\bar{a}({\bm{x}})-\delta\\}-\bar{b}_{1}$
because $\bar{b}_{l+1}-c\leq\bar{a}({\bm{x}})$ and
$\bar{b}_{1}+c+\delta\leq\cdots\leq\bar{b}_{l}+c+\delta=\bar{b}_{l+1}-c$, and
$\varphi(u)=0$ for any $u\geq c$, one has that

$\displaystyle\varphi(\bar{a}({\bm{x}})-\bar{b}_{k})=\varphi(\check{a}({\bm{x}})-\check{b}_{k})=0\text{~{}for~{}}k=l+1,\ldots,K-1.$
(69)

Since
$\bar{b}_{k}-\bar{a}({\bm{x}})<\bar{b}_{k}-\\{\bar{a}({\bm{x}})-\delta\\}=\check{b}_{k}-\check{a}({\bm{x}})$
for $k=1,\ldots,l$ and $\varphi$ is non-increasing, one has that

$\displaystyle\varphi(\bar{b}_{k}-\bar{a}({\bm{x}}))\geq\varphi(\check{b}_{k}-\check{a}({\bm{x}}))\text{~{}for~{}}k=1,\ldots,l.$
(70)

Since $\check{a}({\bm{x}})=\bar{a}({\bm{x}})-\delta$ and
$\check{b}_{k}=\bar{b}_{k}-\delta$ for $k=l+1,\ldots,K-1$, one has that

$\displaystyle\varphi(\bar{a}({\bm{x}})-\bar{b}_{k})=\varphi(\check{a}({\bm{x}})-\check{b}_{k})\text{~{}and~{}}\varphi(\bar{b}_{k}-\bar{a}({\bm{x}}))=\varphi(\check{b}_{k}-\check{a}({\bm{x}}))\text{~{}for~{}}k=l+1,\ldots,K-1.$
(71)

Consider the case $\bar{b}_{l}+c<\bar{a}({\bm{x}})<\bar{b}_{l+1}-c$ If letting
$\epsilon=\bar{a}({\bm{x}})-\\{\bar{b}_{l}+c\\}$, then it holds that
$\check{a}({\bm{x}})=\bar{a}({\bm{x}})-\epsilon$. Since
$c\leq\bar{a}({\bm{x}})-\bar{b}_{l}\leq\cdots\leq\bar{a}({\bm{x}})-\bar{b}_{1}$,
one has that
$c=\\{\bar{a}({\bm{x}})-\epsilon\\}-\bar{b}_{l}\leq\cdots\leq\\{\bar{a}({\bm{x}})-\epsilon\\}-\bar{b}_{1}$
and

$\displaystyle\varphi(\bar{a}({\bm{x}})-\bar{b}_{k})=\varphi(\check{a}({\bm{x}})-\check{b}_{k})=0\text{~{}for~{}}k=1,\ldots,l.$
(72)

Since
$\bar{b}_{k}-\bar{a}({\bm{x}})<\bar{b}_{k}-\\{\bar{a}({\bm{x}})-\epsilon\\}=\check{b}_{k}-\check{a}({\bm{x}})$
for $k=1,\ldots,l$ and $\varphi$ is non-increasing, one has that

$\displaystyle\varphi(\bar{b}_{k}-\bar{a}({\bm{x}}))\geq\varphi(\check{b}_{k}-\check{a}({\bm{x}}))\text{~{}for~{}}k=1,\ldots,l.$
(73)

Since
$\bar{a}({\bm{x}})-\bar{b}_{k}<\\{\bar{a}({\bm{x}})-\epsilon\\}-\\{\bar{b}_{k}-\delta\\}=\check{a}({\bm{x}})-\check{b}_{k}$
for $k=l+1,\ldots,K-1$ because $\epsilon<\delta$, and since $\varphi$ is non-
increasing, one has that

$\displaystyle\varphi(\bar{a}({\bm{x}})-\bar{b}_{k})\geq\varphi(\check{a}({\bm{x}})-\check{b}_{k})\text{~{}for~{}}k=l+1,\ldots,K-1.$
(74)

Since
$c<\bar{b}_{l+1}-\bar{a}({\bm{x}})\leq\cdots\leq\bar{b}_{K-1}-\bar{a}({\bm{x}})$,
one has that
$c=\\{\bar{b}_{l+1}-\delta\\}-\\{\bar{a}({\bm{x}})-\epsilon\\}\leq\cdots\leq\\{\bar{b}_{K-1}-\delta\\}-\\{\bar{a}({\bm{x}})-\epsilon\\}$
and

$\displaystyle\varphi(\bar{b}_{k}-\bar{a}({\bm{x}}))=\varphi(\check{b}_{k}-\check{a}({\bm{x}}))=0\text{~{}for~{}}k=l+1,\ldots,K-1.$
(75)

Correcting these pieces, one can see
$\operatorname{{\mathbb{E}}}[\phi(\bar{a}({\bm{X}}),\bar{{\bm{b}}},Y)]\geq\operatorname{{\mathbb{E}}}[\phi(\check{a}({\bm{X}}),\check{{\bm{b}}},Y)]$,
which contradicts the optimality of $(\bar{a},\bar{{\bm{b}}})$ and shows that
the assumption (63) is false. This concludes the proof of this theorem. ∎


# BCEdge: SLO-Aware DNN Inference Services
with Adaptive Batching on Edge Platforms

Ziyang Zhang, , Huan Li, , Yang Zhao,
, Changyao Lin, and Jie Liu This work is partly supported by the National Key
R&D Program of China under Grant No. 2021ZD0110905, and An Open Competition
Project of Heilongjiang Province, China, on Research and Application of Key
Technologies for Intelligent Farming Decision Platform, under Grant No.
2021ZXJ05A03.Ziyang Zhang is with the Harbin Institute of Technology, Harbin,
Heilongjiang 150006 China (e-mail: zhangzy@stu.hit.edu.cn).
Huan Li is with the Harbin Institute of Technology, Shenzhen, Guangdong 518071
China (e-mail: huanli@hit.edu.cn).
Yang Zhao is with the Harbin Institute of Technology, Shenzhen, Guangdong
518071 China (e-mail: yang.zhao@hit.edu.cn).
Changyao Lin is with the Harbin Institute of Technology, Harbin, Heilongjiang
150006 China (e-mail: lincy@stu.hit.edu.cn).
Jie Liu is with the Harbin Institute of Technology, Shenzhen, Guangdong 518071
China (e-mail: jieliu@hit.edu.cn).

###### Abstract

As deep neural networks (DNNs) are being applied to a wide range of edge
intelligent applications, it is critical for edge inference platforms to have
both high-throughput and low-latency at the same time. Such edge platforms
with multiple DNN models pose new challenges for scheduler designs. First,
each request may have different service level objectives (SLOs) to improve
quality of service (QoS). Second, the edge platforms should be able to
efficiently schedule multiple heterogeneous DNN models so that system
utilization can be improved. To meet these two goals, this paper proposes
BCEdge, a novel learning-based scheduling framework that takes adaptive
batching and concurrent execution of DNN inference services on edge platforms.
We define a utility function to evaluate the trade-off between throughput and
latency. The scheduler in BCEdge leverages maximum entropy-based deep
reinforcement learning (DRL) to maximize utility by 1) co-optimizing batch
size and 2) the number of concurrent models automatically. Our prototype
implemented on different edge platforms shows that the proposed BCEdge
enhances utility by up to 37.6% on average, compared to state-of-the-art
solutions, while satisfying SLOs.

###### Index Terms:

Edge Computing, Inference Service, Scheduling, Reinforcement Learning, Service
Level Objective (SLO).

##  I Introduction

Model inference service systems deployed on cloud servers typically provide
multiple trained deep neural networks (DNNs) for users. These systems are
usually multi-tenant, meaning hosting one or more model instances per DNN
model to serve multiple inference applications, while making better use of the
abundant computing resources of servers. For instance, the multi-instance GPU
(MIG) in NVIDIA Ampere architecture enables the partitioning of a single
NVIDIA A100 GPU into up to seven independent GPU instances that can run
concurrently. In this way, the GPU achieves up to 7$\times$ utilization with
guaranteed quality of service (QoS). Furthermore, a single inference request
often leads to inefficient utilization. Therefore, prior works [1, 2, 3] batch
requests to better exploit the parallelism of GPUs. Batching refers to
aggregating arriving requests into a batch within a given time window, and DNN
service systems process the entire batch at a particular time, thereby
improving throughput (e.g., requests per second, rps). In batch systems,
throughput can be improved by increasing batch size. The more requests in a
batch, the longer the waiting time to be processed, latency, therefore, is
inevitably increased.

Increasing computational and memory capabilities open a new opportunity to
deploy model inference systems on edge accelerators (e.g., graphics processing
unit (GPU), tensor processing unit (TPU), and vision processing unit (VPU),
etc.). This emerging computing paradigm provides guarantee for edge
intelligent applications [4] with low-latency requirements, including the
object detection in autonomous driving [5], recommendation systems in
smartphones [6], and the metaverse in wearables [7], etc. On the other hand,
various lightweight techniques [8] (such as pruning, compression,
quantization, knowledge distillation, etc.) for DNN models enable batching and
concurrent inference of multiple model instances at the edge.

(a) Throughput (rps)

(b) Latency (ms)

Figure 1: The effects of batching and concurrent inference on (a) system
throughput and (b) end-to-end latency. Throughput is measured as requests-per-
second (rps). The x-axis represents the number of concurrent models, and the
y-axis represents batch size. We use YOLO-v5 [9] on NVIDIA Xavier NX edge
platform with 8GB RAM.

To better understand the performance implications of batching and concurrent
inference, we perform an experimental study, using YOLO-v5 [9] on NVIDIA
Xavier NX edge platform. Due to resource constraints on edge platforms, we
leverage TensorRT [10] to accelerate the original DNN models. Fig. 1 reports
the throughput and latency with various batch sizes and number of concurrent
models. We have the following critical observations that motivate this work:
_both batch size and number of concurrent models affect throughput and
latency, but larger batch size or number of models is not always better._ Fig.
1 illustrates that higher-throughput and lower-latency appear in moderate
batch size and number of concurrent models. Due to resource contention caused
by model interference, excessive batch size and number of concurrent models
significantly reduce throughput and increase latency or even cause memory
overflow, especially when batch size and number of concurrent models are
large, e.g., batch size is 128, model number is 8. Therefore, it is crucial
for the scheduler in DNN service system to 1) trade off throughput and latency
for optimal performance and 2) accurately predict the interference between
models.

Designing such a GPU-based inference servers must address different challenges
from batching- and concurrent-oriented processing. First, inference requests
have service level objective (SLO) to achieve quality of service (QoS) with
low-latency. Second, edge platforms usually deploy multiple heterogeneous DNN
models to improve throughput and resource utilization. Therefore, it is
critical to design an efficient scheduler to achieve the optimization goal for
both batching and concurrent inference on edge platforms. Conventional
heuristic-based methods are inefficient for multi-objective optimization [11].
In contrast, deep reinforcement learning (DRL) combines the powerful
representation of deep learning with the adaptive property of reinforcement
learning, which is capable of efficiently solving the above problems.
Therefore, we leverage DRL to transform a multi-objective (i.e., throughput
and latency) problem into a scheduling problem of batch size and number of
concurrent models.

Motivated by the above observation, we propose BCEdge, a learnable, adaptive,
and multi-tenant scheduling framework for SLO-aware DNN inference services.
BCEdge aims to automatically find a global optimum by adjusting both batch
size and number of concurrent models for throughput and latency tradeoffs. The
search space for scheduling becomes two-dimensional with batch size and number
of concurrent models, unlike the prior work with one-dimensional (i.g., batch
size) searches. The batching-concurrent scheduling can significantly improves
the SLO-preserved throughput. For each DNN model, its computational properties
are measured and registered into BCEdge. Based on the profile information of
each DNN model, the maximum entropy reinforcement learning-based scheduler in
BCEdge automatically adjust batch size and number of concurrent models, while
maintaining the SLO. Furthermore, BCEdge leverages a lightweight neural
network (NN)-based interference prediction model to reduce the impact of
concurrent inference.

Table I provides a summarized comparison of our work to related DNN service
frameworks. All previous studies are capable of adaptively adjusting batch
size at runtime, either automatically or manually, to achieve higher-
throughput. As more DNN inference services are consolidated into edge-based
GPU servers, although some previous studies provided multiple heterogeneous
DNN models for multi-tenancy, these works did not enable scheduling multiple
instances of the same model in DNN service system, which becomes more
important to make full use of edge servers with constantly increasing
computing resources. Regarding inter-model resource contention among multi-
tenants and requests with SLO, accurately predicting interference and
guaranteeing SLO can better guide the scheduler to automatically adjust batch
size and number of concurrent models to achieve moderate system throughput and
reduce latency. Only TF-Serving [2] considers model interference, and the
scheduler uses hedged backup requests to mitigate latency spikes caused by
inter-request or -model interference. On the other hand, except for Clipper
[1] and DeepRT [12], none of other previous works consider requests with
strict time constraints (i.e., SLO). Importantly, our study addresses all
challenges, executing multi-instance concurrently, guaranteeing SLO, and
predicting potential interference among multi-model.

TABLE I: Comparison with prior work Service Framework |  Adaptive Batching |  Concurrent Instance |  Multi Model |  Interference Prediction |  SLO Aware
---|---|---|---|---|---
TF-Serving [2] | ✓ | ✗ | ✓ | ✓ | ✗
Triton [3] | ✓ | ✓ | ✓ | ✗ | ✗
DeepRT [12] | ✓ | ✗ | ✓ | ✗ | ✓
Clipper [1] | ✓ | ✗ | ✓ | ✗ | ✓
Prema [13] | ✓ | ✗ | ✓ | ✗ | ✗
DVABatch [14] | ✓ | ✓ | ✓ | ✗ | ✗
BCEdge (Ours) | ✓ | ✓ | ✓ | ✓ | ✓

We evaluated the proposed DNN inference framework on edge platforms with three
heterogeneous edge GPUs, using six DNN models in Table IV that cover both CV
and NLP applications, such as object detection, image classification as well
as speech recognition. The evaluation shows that the proposed scheduling
technique with batching and concurrent model instance can improve the trade-
off with SLO constraints by 37.6%, compared to the state-of-the-art solutions.
The main contributions of this paper are as follows:

  * •

Through a motivational case study based on real-world batching and concurrent
inference of DNN models on edge platforms, we demonstrate that the trade-off
between throughput and latency should leverage both batching and concurrent
inference.

  * •

We present BCEdge, a learnable scheduling framework with adaptive batching and
concurrent model instance for inference service on edge platforms. The
scheduler in BCEdge leverages the maximum entropy reinforcement learning to
automatically adjust batch size and number of concurrent models to trade off
throughput and latency.

  * •

For accurate performance prediction, the lightweight NN-based prediction model
with negligible overhead in BCEdge reduces the effect of interference among
models for DNN concurrent inference.

The rest of the paper is organized as follows: Section II presents related
work. Section III describes system model and problem formulation. Section IV
illustrates our framework design in detail. Section V reports experimental
results. Section VI concludes our work.

##  II Related work

###  II-A Model-level DNN Inference Service

Prior works treated the DNN model as an indivisible whole, and proposed a
series of edge inference serving frameworks to provide the quality of DNN
inference services [2, 15, 12, 14, 16, 17, 18, 19, 1, 20]. Clipper [1],
TensorFlow-Serving [2], MArK [15], DeepRT [12], and BATCH [20] adopt the
traditional adaptive batching that use time window for efficient DNN
inference. None of these existing frameworks offer concurrent operation of
model instances to further improve throughput. There are also some prior works
research on SLO-aware DNN inference service. Gpulet[16] leverages spatio-
temporal sharing of computing resources for multiple heterogeneous DNN models
with SLO constraints. Clockwork [19] exploits predictable execution times to
achieve tight request-level SLO. INFaaS [18] reduces costs, better throughput,
and fewer SLO violations by choosing an adequate variation of a model. PSLO
[17] is a preempting SLO-aware scheduler based on minimum average expected
latency for edge platforms, which aims to trade-off response time, system
throughput, and SLO. Different from the above works, we foucs on reducing the
SLO violation rate caused by the interference of multi-model. In addition,
some edge inference frameworks involve privacy protection [21, 22] and edge-
cloud collaborative [23, 24], respectively. These works are orthogonal to
BCEdge that can alleviate privacy and resource constraints.

###  II-B Operator-level DNN Inference Service

There are some prior research on optimizing the operator scheduling of DNN
models to improve the quality of model service [25, 26, 13, 27]. REEF[25]
apopts a parallel mechanism based on dynamic kernel padding to improve the
overall throughput. VELTAIR [27] proposed an adaptive operator-level
compilation and scheduling to guarantee resource usage efficiency and reduce
interference-induced performance loss for multi-tenant DNN services. PREMA
[13] is a predictive multi-task scheduling algorithm for preemptible neural
processing unit to meet high-throughput. Abacus [26] leverages overlap-aware
latency prediction and deterministic scheduling of overlapped DNN operators
that improves throughput while maintaining the QoS for multi-tenant DNN
services. Since BCEdge exploits the computing power of accelerators on edge
platforms using batching and concurrent inference, these works are also
orthogonal to BCEdge and can be combined together to enable even higher-
throughput and lower-latency.

###  II-C Multi-tenant Scheduling on Edge Platforms

Multi-tenant scheduling is more challenging due to resource constrained on
edge platforms, compared with cloud computing. TVW-RL [28] exploit various
temporal resource usage patterns of time-varying workloads based on a deep
reinforcement learning (DRL) approach, to improve utilization in real
production traces. Likewise, KaiS[29], A3C-R2N2 [11], MILP [30], A3C-DO [31],
and MFRL [32] proposed different multi-agent reinforcement learning-based
scheduling strategies in edge-cloud cluster, to optimize throughput, latency,
energy consumption, cost, etc. MCDS [33] uses a tree-based search strategy and
a DNN-based prediction model to optimize QoS in edge-cloud testbeds. Similar
to MILP[30], DeEdge [34] proposed D-Deads, a distributed greedy scheduling
algorithm with task-deadline in edge computing, which maximize throughput
while minimizing latency. Note that the above works only schedule individual
tasks one by one, ignoring the benefits of batching and concurrent inference.
Inspired by these works, BCEdge can also be extended to an edge-cloud
collaborative inference framework to optimize specific objectives.

##  III System Model and Problem formulation

In this section, we first formulate system model, including request-,
scheduling-, computing-and networking model. Next, we present the optimization
problem formulation to show the trade-off between throughput and latency.

###  III-A System Model

####  III-A1 Request Model

We assume that the IoT devices (e.g., cameras, drones, smartphones, etc.)
share the computing resources of edge platforms. Before task scheduling, the
IoT devices generate a series of inference requests with different DNN model
types $\operatorname{m_{t}^{i}}$, input types $\operatorname{d_{t}^{i}}$
(i.e., image or text), input shapes $\operatorname{d_{s}^{i}}$, and service
level objectives $\operatorname{SLO_{i}}$. The $\operatorname{i}$-th request
$r_{i}$, therefore, could be denoted as
$\operatorname{r_{i}=\\{m_{t}^{i},d_{t}^{i},d_{s}^{i},SLO_{i}\\}}$. Note that
requests arrive at BCEdge online at random with a Poisson distribution. BCEdge
maintains a request queue for each model, and support dynamic batching by
aggregating multiple inference requests with the same model into corresponding
request queue $\operatorname{seq_{b}=\\{r_{1},r_{2},…,r_{b}\\}}$, where
$\operatorname{b}$ is the batch size of DNN models. Meanwhile, BCEdge
constructs multiple instances $\operatorname{m_{c}(c=1,2,…,n)}$ for each model
(i.e., concurrent instances), which is critical for edge platforms with GPU,
since batching and concurrent inference can effectively improve the
throughput. The model zoo in BCEdge backend executes DNN inference from the
request queue, and returns the prediction result
$\operatorname{O_{b}=\\{o_{1},o_{2},…,o_{b}\\}}$.

####  III-A2 Scheduling Model

Since the SLO is different for each request, a fixed scheduling time slot is
not suitable. On the other hand, it is not feasible to specify scheduling time
slots for each request individually, which significantly increases system
overhead. Therefore, we set the $\operatorname{i}$-th scheduling time slot
$\operatorname{t_{i}}$ as the ratio of the sum of $\operatorname{SLO_{i}}$ for
a batch requests to the number of concurrent models, which denoted as

$\operatorname{t_{i}=\sum_{i=1}^{b}SLO_{i}/m_{c}}$ (1)

In this way, BCEdge is capable of guaranteeing the SLO of each request and
provide efficient inference services with batching and concurrent inference.
Moreover, BCEdge starts the next scheduling immediately after finishing the
current scheduling to reduce the GPU idle.

####  III-A3 Computing and Networking Model

The end-to-end latency involves the communication between IoT devices and edge
platforms, as well as model inference time, which consists of the following
components:

  * •

_request transmission time_ $\operatorname{t_{t}^{i}}$: the time that IoT
devices send the $\operatorname{i}$-th inference request (e.g., image or text,
etc.) to edge platforms through the network, which depends on communication
bandwidth and the size of input data.

  * •

_request serialization time_ $\operatorname{t_{s}^{i}}$: the time to aggregate
multiple inference requests with the same model into a single request queue at
the edge platform, for batching and concurrent inference of model instances.

  * •

_request queuing time_ $\operatorname{t_{w}^{i}}$: the time that the request
is blocked on the request queue until it is scheduled, which relate to batch
size and the number of concurrent models.

  * •

_DNN inference time_ $\operatorname{t_{m}^{i}}$: the time that edge platform
execute model inference. Once inference is complete, the current request is
removed from the queue.

  * •

_result transmission time_ $\operatorname{t_{o}^{i}}$: the time that edge
platform sends the $\operatorname{i}$-th inference request to IoT devices
through the network, which is related to the network bandwidth, regardless of
the result size (usually negligible).

Thus, the overall latency $\operatorname{t_{r}^{i}}$ can be denoted as:

$\operatorname{t_{r}^{i}=t_{t}^{i}+t_{s}^{i}+t_{w}^{i}+t_{m}^{i}+t_{o}^{i}}$
(2)

###  III-B Problem Formulation

Our objective is to co-optimize both throughput and latency for each DNN model
by automatically exploring the feasible set of batch size and number of
concurrent models, while guaranteeing SLO. Inspired by the co-adaptive
scheduler named Pollux [35], we present a _utility function_
$\operatorname{U}$ in Eq. (3) to evaluate the trade-off between throughput and
latency.

$\operatorname{U}=\operatorname{log(T_{t_{i}}(b,m_{c})/\frac{L_{t_{i}}(b,m_{c})}{(\sum_{j=1}^{b}r_{j})/m_{c}})}$
(3)

where $\operatorname{b}$ is the batch size, and $\operatorname{m_{c}}$ is the
number of concurrent models. The throughput in the $\operatorname{i}$-th
scheduling time slot $\operatorname{t_{i}}$ can be denoted as
$\operatorname{T_{t_{i}}(b,m_{c})}$, and $\operatorname{L_{t_{i}}(b,m_{c})}$
represents the actual latency of the $\operatorname{i}$-th request.
$\operatorname{{(\sum_{j=1}^{b}r_{j})/m_{c}}}$ denotes the ratio of the sum of
SLOs for batch requests to the number of concurrent models. Notably,
$\operatorname{\frac{L_{t_{i}}(b,m_{c})}{(\sum_{j=1}^{b}r_{j})/m_{c}}\in(0,1]}$
avoids request scheduling failure as much as possible while ensuring real-time
performance.

The scheduler must consider the memory capacity of edge platforms
$\operatorname{M_{i}}$ and the SLO constraints $\operatorname{SLO_{i}}$, when
batching and concurrent executing requests. Therefore, the optimization
objective with above requirements is formulated as

$\begin{split}\operatorname{min.}&\operatorname{U}\\\
\operatorname{s.t.m_{i}}&\leq\operatorname{M_{i}}\\\
\operatorname{L_{i}}&\leq\operatorname{SLO_{i}}\end{split}$ (4)

where $\operatorname{m_{i}}$ is the actual used memory for the
$\operatorname{i}$-th request, and $\operatorname{L_{i}}$ is the end-to-end
latency of the $\operatorname{i}$-th request.

Table II provides mainly symbol definitions and corresponding descriptions.

TABLE II: Symbol Table and Description Notation | Description
---|---
$\operatorname{m_{t}^{i}}$ | DNN model type of the $\operatorname{i}$-th request
$\operatorname{d_{t}^{i}}$ | requested input type of the $\operatorname{i}$-th request
$\operatorname{d_{s}^{i}}$ | requested input shape of the $\operatorname{i}$-th request
$\operatorname{SLO_{i}}$ | service level objective of the $\operatorname{i}$-th request
$\operatorname{seq_{b}}$ | request queue with batch size $\operatorname{b}$
$\operatorname{m_{c}}$ | number of concurrent models
$\operatorname{O_{b}}$ | inference result
$\operatorname{t_{i}}$ | the $\operatorname{i}$-th scheduling time slot
$\operatorname{t_{r}^{i}}$ | end-to-end latency of the $\operatorname{i}$-th request
$\operatorname{u}$ | average resource utilization
$\operatorname{s_{i}}$ | batching slot of the $\operatorname{i}$-th queue
$\operatorname{T_{t_{i}}(b,m_{c})}$ | throughput
$\operatorname{L_{t_{i}}(b,m_{c})}$ | end-to-end latency
$\operatorname{U}$ | utility function

##  IV BCEdge Design

###  IV-A System Overiew

The goal of BCEdge is to devise a scheduling framework for multi-model DNN
inference serving, which aims to allocate a moderate batch size and number of
concurrent models for each incoming inference requests, while maintaining SLO.
To this end, the scheduling of DNN inference requests with SLO requirements
must consider two aspects: batching, and concurrent model instances. Unlike
the prior work which consider a subset of the two dimensions [12, 1], we
propose a scheduler that fully explores all two dimensions to find the most
effective point for scheduling.

Fig. 2 presents the overall architecture of our proposed scheduling framework,
namely BCEdge. The framework is composed of learning-based scheduler (Section
IV-B), dynamic batching module (Section IV-C), concurrent instance module
(Section IV-D), performance analyzer (Section IV-E), and SLO-aware
interference predictor (Section IV-F). BCEdge first ❶ maintain a request queue
for each DNN model. The requests with different DNN models generated by IoT
devices are merged to send the corresponding request queue. The performance
profiler ❷ periodically collects the information (e.g., utilization, SLO,
system throughput and end-to-end latency for a pair of batch size and number
of concurrent models) for each DNN model. Meanwhile, the SLO-aware
interference predictor ❸ analyzes the potential interference overhead caused
by concurrent model instances, which guides the scheduler to make more robust
decisions. The learning-based scheduler then ❹ finds the best batch size and
number of concurrent models by leveraging profiled information, and feeds back
to dynamic batch processing module and concurrent instance module,
respectively. The executor in the backend finally ❺ executes DNN inference
service with batching and number of concurrent models on the edge platform.

Figure 2: Overview of the scheduling framework for DNN service.

###  IV-B Learning-based Scheduler

_Search Space Challenge_ : The learning-based scheduler is the critical
component for BCEdge. Note that the scheduling in BCEdge is more complex
compared with prior work (e.g., TF-Serving [2], Clipper [1], and DeepRT [12]),
since it involves batching as well as concurrent inference. The challenge of
the two-dimensional scheduling space (batch size, and number of concurrent
models) for BCEdge is that the scheduling decision is affected by several
variables dependent on each other. Specifically, the best batch size and
number of concurrent models depends on the computing requirements of different
DNN models, the properties of input, the SLO constraints, as well as the
available computing resources of edge platforms. Therefore, the optimal trade-
off configuration would sit on the sweet spot in the search space built upon
the two dimensions, which creates a huge search space.

To this end, we tailor the learning-based scheduling algorithm for BCEdge.
Compared with traditional heuristic methods, deep reinforcement learning (DRL)
has great advantages in processing complex policy decision, which can be
applied to action spaces with high-dimensional. Thus, we design a novel DRL-
based scheduler for efficient DNN inference service with batching and
concurrent inference, in order to trade off throughput and latency. Since
batch size and number of concurrent models are discrete, we present a
learnable online scheduling algorithm with maximum entropy, based on discrete
soft actor-critic [36] framework, which maximizes the reward while maximizing
the entropy of the visited states compared with traditional DRL approaches.
The introduction of entropy makes our proposed scheduling algorithm have the
following benefits:

  * •

Enable the agent in DRL to learn more near-optimal actions to accelerate
training (i.e., the output is a policy distribution), compared with
deterministic policy-based DRL (i.e., the output is an action).

  * •

Enable the agent to has a stronger ability to explore the environment, and
avoid falling into local optimum.

  * •

Enable the system to be more robust.

Now we focus on how the scheduler in BCEdge finds batch size and number of
concurrent models for each inference request that optimizes the trade-off in
Eq. (3). We describe the details as follows:

####  IV-B1 Markov Decision Process Formulation

Firstly, we model batching and concurrent scheduling of inference requests as
a markov decision process (MDP). It can be denoted as a five-tuple ($\cal S$,
$\cal A$, $\pi$, $p$, $r$):

  * •

_State_ : $\cal S$ is the discrete state space. At each scheduling time slot
$t_{i}$, the agent in DRL constructs a state $s_{t}(s_{t}\in\cal S)$ to
periodically collect request information and the resource utilization of edge
platforms. $s_{t}$ consists of five parts: (I) The DNN model type $m_{t}^{i}$.
(II) The input type $d_{t}^{i}$ and input shape $d_{s}^{i}$. (III) The SLO of
each requests. (IV) The available computing resources of edge platforms
$m_{i}$. (V) The information of request queue $seq_{b}$.

  * •

_Action_ : $\cal A$ is the discrete action space. The action of the agent in
DRL is to find best batch size $b$ and number of concurrent models $m_{c}$.
The action $a_{t}(a_{t}\in\cal A)$ at scheduling time slot $t_{i}$ can be
denoted as $a_{t}=(b,m_{c})$. For instance, if a DNN model has $\cal M$
optional batch sizes and $\cal N$ optional number of concurrent models, the
size of the discrete action space $\cal A$ is $\cal M\times\cal N$.

  * •

_Policy_ : The policy $\pi\left(a_{t}\mid s_{t}\right)$ is a function that the
agent decides the next action $a_{t}$ according to the environment state
$s_{t}$ at timestamp _t_. In the maximum entropy-based DRL algorithm, we
maximize both the reward and the entropy of the visited states. The optimal
policy $\pi^{*}$ is denoted as follows:

$\begin{split}\pi^{*}=\operatorname{argmax}_{\pi}\sum_{t=0}^{T}E_{(s_{t},a_{t})\sim\rho_{\pi}}[\gamma^{t}r(s_{t},a_{t})\\\
+\alpha\mathcal{H}(\pi(\cdot\mid s_{t}))]\end{split}$ (5)

where $\gamma\in[0,1]$ is discount factor, $\rho_{\pi}$ represents the
distribution of action trajectory generated by the policy $\pi$, and $\alpha$
is a temperature parameter to express the relative importance of reward and
entropy. $\mathcal{H}\left(\pi\left(\cdot\mid
s_{t}\right)\right)=-\log\pi\left(\cdot\mid s_{t}\right)$, which is the
entropy with state $s_{t}$.

  * •

_State transition probability_ : $p\left(s_{t}^{\prime}\mid
s_{t},a_{t}\right)$ is the state transition probability that indicates the
probability of transitioning to the next state $s_{t}^{\prime}$ after taking
an action $a_{t}$ in the current state $s_{t}$ at timestamp _t_ , satisfying
$\sum_{s^{\prime}\in
S}p\left(\left.s_{t}^{\prime}\right|s_{t},a_{t}\right)=1$.

  * •

_Reward_ : $r:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ is the reward
function. The agent in DRL aims to maximize the accumulated expected reward
$\mathbb{E}\left[\sum_{t=0}^{T}\gamma^{t}r_{t}\right]$, where $r_{t}$ is the
instant reward when the agent selects batch size and number of concurrent
models at each scheduling time slot $t_{i}$. Since our objective is to
maximize the trade-off between throughput and latency, we migrate the
objective in Eq. (3) to the reward function:

$r_{t}=U$ (6)

In this way, the traditional scheduling problem is converted into the
maximization of reward in DRL. We further utilize efficient learning-based
algorithm to reduce the complexity.

####  IV-B2 Maximum Entropy DRL-based scheduling algorithm

We leverage soft policy iteration [37] to maximize both reward and entropy. To
be more specific, soft policy iteration consists of policy evaluation and
policy improvement, which alternates during training.

  * •

_Soft Q-Function (Critic Network)_ : We first compute the soft Q-value
$Q(s_{t},a_{t})$ in the policy evaluation step. The soft Q-function is denoted
as follows [37]:

$\mathcal{T}^{\pi}Q\left(\mathbf{s}_{t},\mathbf{a}_{t}\right)\triangleq
r\left(\mathbf{s}_{t},\mathbf{a}_{t}\right)+\gamma\mathbb{E}_{\mathbf{s}_{t+1}\sim
p}\left[V\left(\mathbf{s}_{t+1}\right)\right]$ (7)

where $\mathcal{T}^{\pi}$ is the modified bellman backup operator.

The soft state value function $V(s_{t})$ with the policy $\pi$ in discrete
state space $s_{t}$ is:

$V\left(s_{t}\right):=\pi\left(s_{t}\right)^{T}\left[Q\left(s_{t}\right)-\alpha\log\left(\pi\left(s_{t}\right)\right)\right]$
(8)

We train the soft Q-value in Eq. (7) by minimizing the soft bellman residual,
and the loss function is:

$\begin{split}J_{Q}(\theta)=E_{(s_{t},a_{t})\sim
D}[\frac{1}{2}(Q_{\theta}(s_{t},a_{t})\\\ -(r(s_{t},a_{t})+\gamma
E_{s_{t+1}\sim p(s_{t},a_{t})}[V_{\bar{\theta}}(s_{t+1})]))^{2}]\end{split}$
(9)

  * •

_Policy (Actor Network)_ : The policy improvement is used to update the policy
network, which is denoted as follows:

$\pi_{\text{new
}}=\arg\min_{\pi^{\prime}\in\Pi}\mathrm{D}_{\mathrm{KL}}\left(\pi^{\prime}\left(\cdot\mid\mathbf{s}_{t}\right)\|\frac{\exp\left(\frac{1}{\alpha}Q^{\pi_{\text{old
}}}\left(\mathbf{s}_{t},\cdot\right)\right)}{Z^{\pi_{\text{old
}}}\left(\mathbf{s}_{t}\right)}\right)$ (10)

where $\mathrm{D}_{\mathrm{KL}}$ is the Kullback-Leible (KL) divergence, and
$Z^{\pi_{\text{old }}}$ is the partition function.

We minimize the KL divergence in Eq. (11) to update the parameters of the
policy network:

$J_{\pi}(\phi)=E_{s_{t}\sim
D_{KL}}\left[\pi_{t}\left(s_{t}\right)^{T}\left[\alpha\log\left(\pi_{\phi}\left(s_{t}\right)\right)-Q_{\theta}\left(s_{t}\right)\right]\right]$
(11)

  * •

_Temperature parameter_ : We automatically adjust the temperature parameter
$\alpha$ in Eq. (5), according to [37]:

$J(\alpha)=E_{a_{t}\sim\pi_{t}}\left[-\alpha\left(\log\pi_{t}\left(a_{t}\mid
s_{t}\right)+\bar{H}\right)\right]$ (12)

where $\bar{H}$ is a constant vector that equals to the hyperparameters of the
target entropy.

Algorithm 1 provides the overall procedure of scheduling concurrent model
instances with dynamic batching. The scheduler first receives the information
of DNN model and resource utilization for each inference request. Before each
scheduling time slot, it initializes all networks, including soft Q-network,
target soft Q-network, policy network and temperature network with
corresponding parameters, respectively. Note that we use two soft Q-networks
and take the minimum value of them to alleviate the overestimation of soft
Q-value.

For each scheduling time slot, the scheduler first checks each request queue.
If the request queue is empty, it pushes incoming requests into the request
queue (_line 7_). The scheduler then takes an actions (e.g., determine the
best batch size and number of concurrent models for each request) based on Eq.
(5), and the agent in DRL obtains a instant reward as utility (_line 9_).
Meanwhile, the state changes from $s_{t}$ to $s_{t+1}$, and the current state,
action, reward and the next state are stored as a action transition in the
replay buffer $\mathcal{D}$. The scheduler pulls the request sequence from the
batching slot (Section IV-C) when the batch requests in the current request
sequence are executed (_line 12_). The scheduler finally update the parameters
of all networks, and repeat the above process (_line 14 $\sim$18_) until the
end of the iteration.

Input : The information ($m_{t}^{i}$, $d_{t}^{i}$, $d_{s}^{i}$, $SLO_{i}$) of
request $r_{i}$, resource utilization $u$

Output : batch size $b$, number of concurrent models $m_{c}$

1 Initialization all neural networks
$Q_{\theta_{1}},Q_{\theta_{2}},\hat{Q}_{\theta_{1}},\hat{Q}_{\theta_{2}},\pi_{\phi},T_{\alpha}$;

2 Randomly initialize network parameters $\theta_{1},\theta_{2},\phi,\alpha$;

3 Initialize an empty replay buffer $\mathcal{D}\leftarrow\emptyset$;

4 for  _each scheduling time slot $t_{i}$_ do

5 for  _each environment step_ do

6 if  _request queue $seq_{b}==\emptyset$_ then

7 Push requests $r_{i}$ to request queue $seq_{b}$;

8

9 end if

10 Take an action $a_{t}(b,m_{c})$ based on policy $\pi$ and get reward
$r_{t}\left(a_{t}\mid s_{t}\right)$ using Eq. (6);

11 $s_{t+1}\sim p\left(s_{t+1}\mid s_{t},a_{t}\right)$ ;

12
$\mathcal{D}\leftarrow\mathcal{D}\cup\left\\{\left(s_{t},a_{t},r\left(s_{t},a_{t}\right),s_{t+1}\right)\right\\}$;

13 Pull current request queue $seq_{b}$ from batching slot $s_{i}$;

14

15 end for

16 for  _each gradient step_ do

17 Update actor and target networks $\theta_{i}$ for $i\in\\{1,2\\}$ using Eq.
(9);

18 Update critic network $\phi$ using Eq. (11);

19 Update temperature network $\alpha$ using Eq. (12);

20

21 end for

22

23 end for

Algorithm 1 Learning-based scheduling algorithm

###  IV-C Dynamic Batching

BCEdge enables batch inferencing by allowing individual inference requests to
specify a batch of inputs. The inferencing for a batch of inputs is performed
at the same time which is especially important for GPUs, since it can greatly
increase inferencing throughput. As illustrated in Fig. 3, the dynamic
batching maintains a request queue separately for requests with different
models, and each batch size in a queue depends on the learning-based scheduler
in BCEdge. The dynamically created batches are distributed to all model
instances configured for the model, and dynamic batching module then
concurrently executes multiple batch request queues for each model. To be more
specific, dynamic batching first adds each requests to the corresponding
request queue based on the order of arrival. Meanwhile, it sorts the priority
based on the SLO of inference requests in each queue, the shorter the SLO, the
higher the priority. Dynamic batching then merges multiple requests to a
single large request, and assigns batch requests in the request queue to
multiple slots of corresponding models at runtime. Note that the batch
requests are scheduled in the order of arrival if have the same priority.

Figure 3: Dynamic batching module.

###  IV-D Model Instance Concurrency

BCEdge enables multiple models and multiple instances of the same model to
execution in parallel on single or multiple GPUs, and the DNN models executed
on CPU are handled similarly by BCEdge. Fig. 4 shows the pipeline of executing
model instance with batch requests in parallel for three DNN models, and each
model is assigned two instances. We assume that BCEdge is not currently
processing any requests. When the first three requests arrive at the same
time, each instance of the three models processes a corresponding request.
BCEdge then immediately dispatches both of them to the GPU, and the hardware
scheduler of GPU begins working on three inferences in parallel. Note that the
first three inference requests are immediately executed in parallel, and the
last three inference requests must wait until one of the first three requests
completes before beginning. In particular, if multiple inference requests for
the same model arrive at the same time, BCEdge serializes their execution by
scheduling only one at a time.

Figure 4: Concurrent instance module.

###  IV-E Performance Profiler

The profiler in BCEdge periodically collects the performance information
online, including the current utilization of CPU, GPU, memory, as well as
system throughput and end-to-end latency. Specifically, the profiler records
the performance information of each batch request with different input shapes
on the edge platform, and feeds the information back to the scheduler. The
scheduler learns the above information to schedule the next batch request,
i.e., determining the best batch size and number of concurrent models to
maximize the utility. Meanwhile, BCEdge can avoid system overload and improve
resource utilization by the performance profiler, which reflects the potential
advantage of BCEdge for dynamic resource management and allocation.

###  IV-F SLO-Aware Interference Predictor

Concurrent inference of multiple models or multiple instances of a single
model can process more requests simultaneously to improve throughput. However,
an important challenge is the interference performance caused by concurrent
inference of multiple models on a single GPU. As shown in Fig. 1, we observed
that concurrent inference significantly increases latency compared to
executing a single model independently, as multiple models compete for the
shared resources on edge platform, especially the memory. In such case, model
interference may cause the scheduler to make incorrect schedules, and may
violate the SLO.

A key challenge in mitigating interference is to predict latency increases
when multiple inferences are executed concurrently in the same GPU. To confine
the interference effect, we utilize a lightweight two-layer neural network
(NN) with negligible overhead as the predictive model, which directly learns
the interference latency of concurrently executing multiple inferences on a
single GPU. As shown in Fig. 5, the simple yet effective interference-
prediction model based on NN utilizes the currently available computing
resources (i.e., memory, CPU and GPU) and the number of concurrent models
learned by scheduler as the input of the neural network. We then compare the
estimated latency of the neural network output with the actual latency based
on performance feedback provided by the performance profiler, and the neural
network is trained by minimizing the standard deviation between the real
values and the estimation value. The trained neural network aims to improve
the stability of the scheduler and reduce the SLO violation rate.

Figure 5: SLO-aware interference predictor based on neural network.

##  V Evaluation

###  V-A Experiment setup

_BCEdge Prototype:_ We implement the prototype of BCEdge as a runtime backend
for Triton [3], a inference serving system from NVIDIA. Table III provides a
detailed description of the evaluated inference system and the used GPU
specification. The table also provides the versions of the operating system,
CUDA, runtime, and machine learning framework. As Fig. 6 shows, we use two IMX
cameras and a micorphone as IoT devices. The request arrival rate is set to 30
requests per second (rps), and follows the Poisson random distribution. Unless
otherwise indicated, all evaluations are reported on a NVIDIA Xavier NX edge
GPU.

Figure 6: BCEdge prototype implemented on NVIDIA Xavier NX edge platform. We
use two IMX cameras and a micorphone as IoT devices.

_DNN Models:_ We use six DNN models for three popular DNN families to process
image and speech data. Specifically, we use YOLO-v5 [9] for object detection
task, MobileNet-v3 [38], ResNet-18 [39], EfficientNet-B0 [40] and Inception-v3
[41] for image classification tasks, especially with TinyBERT [42] for speech
recognition tasks. We use TensorRT [10] to reduce memory footprint for better
batching and concurrent executing. Since the limited computing power of Xavier
NX, we downsample the input image to 224$\times$224 resolution. All images are
colored frames with the 3 RGB channels. Each corresponding SLO latency is
listed in Table IV.

_Training Details:_ Our proposed Algorithm 1 is based on the SAC [36]
framework. All networks are trained using the Adam optimizer with a learning
rate of $10^{-3}$. Each network has a two-layer ReLU neural network with 128
and 64 hidden units, respectively, and the buffer size is fixed to $10^{6}$.
We trained it offline on an off-the-edge device using four NVIDIA GeForce GTX
3080 GPUs with a mini-batch size of 512 for 500 epochs. We then deploy trained
algorithm online to edge platform.

TABLE III: The evaluated system specifications Edge Platform | NVIDIA Xavier NX
---|---
Operating System | Ubuntu: 18.04.6 (kernel 4.15.0)
Software | CUDA 10.2 and TensorRT 8.2 [10]
CPU | 6-core Carmel ARMv8.2
GPU | 384-core Volta GPU with 48 Tensor Cores
Memory Capacity | 8GB RAM
Runtime | NVIDIA Triton Inference Server 2.19.0 [3]
ML Framework | PyTorch 1.10
TABLE IV: List of DNN models used in the evaluation Model | Input Shape (Dimension) | SLO (ms)
---|---|---
YOLO-v5 (yolo) | VOC-2012 (3x224x224) | 138
MobileNet-v3 (mob) | ImageNet-2012 (3x224x224) | 86
ResNet-18 (res) | ImageNet-2012 (3x224x224) | 58
EfficientNet-B0 (eff) | ImageNet-2012 (3x224x224) | 93
Inception-v3 (inc) | ImageNet-2012 (3x224x224) | 66
TinyBERT (bert) | Speech Commands (1x14) | 114

###  V-B Baselines

####  V-B1 Edge inference service framework

We compare BCEdge with two SOTA edge inference service frameworks:

  * •

_DeepRT_ [12]: A soft real-time scheduler that adopts dynamic batching with
earliest-deadline-first (EDF) scheduling algorithm to execute batch requests.

  * •

_Triton with Actor-Critic (TAC)_ [3]: Since Triton only supports manually
setting a fixed batch size and number of concurrent models, we combine Triton
with Actor-Critic without entropy to compare with BCEdge.

####  V-B2 Various scheduling algorithms

We ported the traditional heuristics and other reinforcement learning methods
in BCEdge inference service framework to compare with our scheduling
algorithm, including:

  * •

_Genetic Algorithm (GA)_ [43]: As a search algorithm for optimization
problems, the main idea of GA is ”survival of the fittest” in the theory of
biological evolution. We take the fitness function in GA as our proposed
utility.

  * •

_Proximal Policy Optimization (PPO)_ [44]: PPO is an on-policy (the
optimization policy and behavior policy of agent in the learning process are
the same policy) DRL algorithm based on the Actor-Critic architecture.

  * •

_Double Deep Q Network (DDQN)_ [45]: As an off-policy (the optimization policy
and behavior policy of agent in the learning process are different policies)
DRL algorithm, DDQN eliminates overestimation by decoupling the selection of
actions in target Q-value and the calculation of target Q-value.

###  V-C Trade-off Performance

####  V-C1 Comparison of Edge Inference Frameworks

We first evaluate the performance of BCEdge in terms of the tradeoff between
throughput and latency. Fig. 7 reports the normalized utility for six DNN
models in Table IV. Our proposed BCEdge consistently outperforms TAC and
DeepRT for all models. The lower-utility of DeepRT is caused by the lack of
concurrent inference. Although TAC leverages a learning-based approach for
batching and concurrent scheduling, its agent lacks the entropy that
comprehensive explore the environment. In contrast, BCEdge introduces entropy
into our learning-based scheduling algorithm, so that the agent in DRL have
stronger exploration to obtain higher utility. In contrast, BCEdge provides a
better trade-off between throughput and latency by efficient scheduling as
well as SLO-aware interference prediction. To be more specific, BCEdge offers
higher utility than both DeepRT and TAC by an average of 37% and 25%,
respectively.

Figure 7: Comparison of the normalized utility with six DNN models.

We next demonstrate that how BCEdge performed six DNN models for a duration of
3,000 seconds in terms of throughput and latency, respectively. Fig. 8 shows a
stacked graph of the accumulated throughput of each model, and Fig. 9 reports
the end-to-end latency of each model over time. Both the throughput and
latency increase asymptotically between 0 and 1,500 seconds, which indicates
that BCEdge is continuously optimizing our proposed utility function to find
the appropriate batch size and number of concurrent models for each DNN model.
Starting from 1,500 seconds, both the throughput and latency are saturated,
which indicates that BCEdge has successfully fond the best batch size and
number of concurrent models within the constraint of resource and SLO. In
addition, we note that BCEdge tends to sacrifice higher-throughput for lower-
latency to achieve better utility.

Figure 8: Comparison of throughput with six DNN models. The scheduling
duration of each model for 3,000 seconds.

Figure 9: Comparison of average latency with six DNN models. The scheduling
duration of each model for 3,000 seconds.

####  V-C2 Comparison of Convergence Performance

We compare the convergence of three learning-based (PPO, DDQN and Ours) and
heuristic-based (GA) scheduling algorithms in BCEdge DNN inference service
framework. As shown in Fig. 10, our proposed scheduling algorithm has has the
convergence speed increase of 1.8$\times$$\sim$3.7$\times$ compared with
baseline methods. This is due to the entropy enables the agent in DRL to learn
more approximate optimal actions. That is, there may be multiple actions that
are optimal in some states, and our proposed scheduling algorithm makes these
actions have the same probability to being selected. Thus, the maximum entropy
can effectively speed up the learning process. Note that the genetic algorithm
(GA) has the disadvantage of being premature, that is, GA has limited ability
to explore the environment, therefore it inevitably converge to a local
optimal solution. Importantly, GA involves a large number of calculations,
such as crossover, mutation, and etc., resulting in slower convergence.

Figure 10: Comparison of training loss for DRL-based (PPO, DDQN and Ours) and
heuristics (GA) scheduling algorithms.

###  V-D Evaluation of Scalability

To evaluate scalability beyond our platform in Table III, we additionally
select two edge platforms with GPUs (e.g., NVIDIA Jetson Nano and TX2). Table
V provides the specific parameters of both two heterogeneous edge platforms
compared with Xavier NX. We evaluate the scalability of BCEdge using object
detection (YOLO-v5), image classification (ResNet-18) and speech recognition
(TinyBERT) DNN models, respectively. Fig. 11 reports the utility of BCEdge on
Jetson Nano/TX2 edge platforms compared with baselines. We can see that BCEdge
outperforms the baselines on both two heterogeneous edge platforms. Since the
image classification DNN model has the least computing resources, that is,
ResNet-18 has more batch size and number of concurrent models to be configured
than YOLO-v5 and TinyBERT, therefore BCEdge achieves better trade-off for
ResNet-18. There are similar results in Fig. 7. Even for Jetson nano with the
weakest computing power, the utility of BCEdge can increases by 30% and 19%
compared with DeepRT and TAC, respectively. Since Jetson TX2 has more
computing resources that configure more batch size and number of concurrent
models, BCEdge can achieve higher performance, and the utility is 39% and 27%
higher than DeepRT and TAC, respectively.

TABLE V: Performance parameters of edge platforms Edge Platform | Computility | Memory | CUDA Cores
---|---|---|---
Jetson Nano | 0.47 TFLOPS (FP16) | 4 GB | 128
Jetson TX2 | 1.33 TFLOPS (FP16) | 8 GB | 256
Xavier NX | 21 TOPS (INT8) | 8 GB | 384

Figure 11: The utility of heterogeneous edge platforms. The more computing
resources of the edge platform, the higher the utility.

Fig. 12 shows the throughput and latency of three edge platforms corresponding
to the utility in Fig. 11. The left y-axis in Fig. 12 represents peak
throughput, and the right y-axis represents corresponding average latency. As
we observed in Fig. 12, BCEdge also has more significant performance
improvement on the DNN models with fewer computing resources and the edge
platforms with more abundant computing resources. Even for the weakest Jetson
Nano, BCEdge can fully utilize computing resources for different DNN models to
optimize the trade-off between throughput and latency. In summary, BCEdge
exhibits flexible scalability that can be adapted to heterogeneous resource-
constrained edge platforms.

(a) YOLO-v5 (yolo)

(b) ResNet-18 (res)

(c) TinyBERT (bert)

Figure 12: The throughput and average latency of heterogeneous edge platforms.
The more computing resources of the edge platform, the higher the throughput
and the lower the average latency.

###  V-E Evaluation of Interference Model

In this experiment, we investigate the proposed interference prediction model
in BCEdge under different requests per second (rps) on SLO violation rate. The
interference prediction model records total 2000 inference interferences with
one second period for each DNN model. Among the 2000 pieces of collected data,
we randomly select 1600 pieces of execution data as training data and 400
pieces of data for validation. Fig. 13 presents the cumulative distribution of
the prediction error with our NN-based interference model, compared with the
linear regression model [46, 16]. The proposed model can predict up to 90% of
cases within 2.69% error rate and up to 95% if 3.25% of error is allowed,
which reduces the error rate by half compared to the linear regression model.
Since the model interference we observed in Fig. 1 is not a simple linear
relationship, the linear regression model has a higher prediction error. In
contrast, out proposed NN-based interference model considers the resource
utilization of edge platforms and the actual latency of DNN models, which can
accurately predict the interference latency.

Figure 13: Cumulative distribution of relative error rate. Our proposed NN-
based model can predict up-to 95% of cases with less than 3.25% error rate.

Fig. 14 shows the cumulative distribution of SLO violation rate at 30 rps for
BCEdge with/without the interference prediction model. We analyzed the SLO
violation rate for the scheduling duration of 3000 seconds in Fig. 8 and Fig.
9. The proposed model can reduce the SLO violation rate of BCEdge from 9.2% to
4.1%, compared to BCEdge without the interference prediction model. It
illustrates that the interference prediction model can improve the robustness
of BCEdge and effectively reduce SLO violation rate.

Figure 14: Cumulative distribution of SLO violation rate with 30rps. Our
proposed interference prediction model can achieve the SLO violation rate
within 4%, compared to up to 9.2% SLO violation rate without the interference
prediction model.

As shown in Fig. 15, we measure the SLO violation rate by gradually increasing
the requests per second (rps). It can be seen that BCEdge has the lowest SLO
violation rate for all rps, which is 53% and 25% lower than DeepRT and TAC on
average, respectively. The SLO violation rate of BCEdge does not exceed 5%
even at 40rps. Since the soft real-time scheduler in DeepRT [12] is only
suitable for the DNN models without strict SLO constraints, it has the highest
SLO violation rate with strict SLO constraints. In addition, TAC does not
consider the impact of model interference, therefore the SLO violation rate is
higher than BCEdge.

Figure 15: Comparison of service level objective (SLO) violation rate with
real-world six DNN model benchmarks under different rps. Benefit from the
interference prediction model, BCEdge has the lowest SLO violation rate.

###  V-F Scheduling Overhead

To measure the runtime overhead imposed by the scheduler, we compare BCEdge
with DeepRT and TAC in terms of the average scheduling latency. Fig. 16
depicts these scheduling overheads. As observed, BCEdge has a low scheduling
overhead due to the scheduler in BCEdge introduces maximum entropy that can
learn more approximate optimal actions to speed up learning in order to reduce
overhead. Specifically, the average scheduling overhead of BCEdge is 26% and
43% lower than that of DeepRT and TAC, respectively. It demonstrates that
BCEdge can efficiently schedule batching and concurrent requests with
extremely low overhead. Note that we did not evaluate the overhead of the
performance profiler and interference prediction model as they are negligible.

Figure 16: Comparison of scheduling overhead with six DNN models.

##  VI Conclusion

In this work, we present BCEdge, an adaptive, SLO-aware, and multi-tenant DNN-
serving scheduling framework. BCEdge enables batching and concurrent inference
for edge intelligent applications on edge platforms to achieve both high-
throughput and low-latency. The key to BCEdge is a maximum entropy deep
reinforcement learning-based scheduler, which automatically co-optimizes batch
size and number of concurrent models. Compared to the state-of-the-art
solutions, BCEdge achieves up to 37.6% average utility improvement, while
satisfying SLOs.

## 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 _NSDI_ , vol. 17, 2017, pp. 613–627.
  * [2] 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 preprint arXiv:1712.06139_ , 2017.
  * [3] “Nvidia triton inference server,” https://developer.nvidia.com/nvidia-triton-inference-server.
  * [4] S. Deng, H. Zhao, W. Fang, J. Yin, S. Dustdar, and A. Y. Zomaya, “Edge intelligence: The confluence of edge computing and artificial intelligence,” _IEEE Internet of Things Journal_ , vol. 7, no. 8, pp. 7457–7469, 2020.
  * [5] D. Feng, C. Haase-Schütz, L. Rosenbaum, H. Hertlein, C. Glaeser, F. Timm, W. Wiesbeck, and K. Dietmayer, “Deep multi-modal object detection and semantic segmentation for autonomous driving: Datasets, methods, and challenges,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 22, no. 3, pp. 1341–1360, 2020.
  * [6] X. Xie, F. Sun, Z. Liu, S. Wu, J. Gao, J. Zhang, B. Ding, and B. Cui, “Contrastive learning for sequential recommendation,” in _2022 IEEE 38th international conference on data engineering (ICDE)_. IEEE, 2022, pp. 1259–1273.
  * [7] Z. Liu, G. Lan, J. Stojkovic, Y. Zhang, C. Joe-Wong, and M. Gorlatova, “Collabar: Edge-assisted collaborative image recognition for mobile augmented reality,” in _2020 19th ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN)_. IEEE, 2020, pp. 301–312.
  * [8] S. Han, H. Mao, and W. J. Dally, “Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding,” _arXiv preprint arXiv:1510.00149_ , 2015.
  * [9] “Yolov5,” https://github.com/ultralytics/yolov5.
  * [10] “Nvidia tensorrt,” https://developer.nvidia.com/tensorrt.
  * [11] S. Tuli, S. Ilager, K. Ramamohanarao, and R. Buyya, “Dynamic scheduling for stochastic edge-cloud computing environments using a3c learning and residual recurrent neural networks,” _IEEE transactions on mobile computing_ , 2020\.
  * [12] Z. Yang, K. Nahrstedt, H. Guo, and Q. Zhou, “Deeprt: A soft real time scheduler for computer vision applications on the edge,” in _2021 IEEE/ACM Symposium on Edge Computing (SEC)_. IEEE, 2021, pp. 271–284.
  * [13] Y. Choi and M. Rhu, “Prema: A predictive multi-task scheduling algorithm for preemptible neural processing units,” in _2020 IEEE International Symposium on High Performance Computer Architecture (HPCA)_. IEEE, 2020, pp. 220–233.
  * [14] W. Cui, H. Zhao, Q. Chen, H. Wei, Z. Li, D. Zeng, C. Li, and M. Guo, “$\\{$DVABatch$\\}$: Diversity-aware $\\{$Multi-Entry$\\}$$\\{$Multi-Exit$\\}$ batching for efficient processing of $\\{$DNN$\\}$ services on $\\{$GPUs$\\}$,” in _2022 USENIX Annual Technical Conference (USENIX ATC 22)_ , 2022, pp. 183–198.
  * [15] C. Zhang, M. Yu, W. Wang, and F. Yan, “Mark: Exploiting cloud services for cost-effective, slo-aware machine learning inference serving.” in _USENIX Annual Technical Conference_ , 2019, pp. 1049–1062.
  * [16] 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)_ , 2022, pp. 199–216.
  * [17] W. Seo, S. Cha, Y. Kim, J. Huh, and J. Park, “Slo-aware inference scheduler for heterogeneous processors in edge platforms,” _ACM Transactions on Architecture and Code Optimization (TACO)_ , vol. 18, no. 4, pp. 1–26, 2021.
  * [18] F. Romero, Q. Li, N. J. Yadwadkar, and C. Kozyrakis, “Infaas: Automated model-less inference serving.” in _USENIX Annual Technical Conference_ , 2021, pp. 397–411.
  * [19] 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)_ , 2020, pp. 443–462.
  * [20] A. Ali, R. Pinciroli, F. Yan, and E. Smirni, “Batch: Machine learning inference serving on serverless platforms with adaptive batching,” in _SC20: International Conference for High Performance Computing, Networking, Storage and Analysis_. IEEE, 2020, pp. 1–15.
  * [21] X. Liu, B. Wu, X. Yuan, and X. Yi, “Leia: A lightweight cryptographic neural network inference system at the edge,” _IEEE Transactions on Information Forensics and Security_ , vol. 17, pp. 237–252, 2021.
  * [22] J. Hou, H. Liu, Y. Liu, Y. Wang, P.-J. Wan, and X.-Y. Li, “Model protection: Real-time privacy-preserving inference service for model privacy at the edge,” _IEEE Transactions on Dependable and Secure Computing_ , 2021.
  * [23] Y. G. Kim and C.-J. Wu, “Autoscale: Energy efficiency optimization for stochastic edge inference using reinforcement learning,” in _2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_. IEEE, 2020, pp. 1082–1096.
  * [24] W. Zhang, D. Yang, H. Peng, W. Wu, W. Quan, H. Zhang, and X. Shen, “Deep reinforcement learning based resource management for dnn inference in industrial iot,” _IEEE Transactions on Vehicular Technology_ , vol. 70, no. 8, pp. 7605–7618, 2021.
  * [25] M. Han, H. Zhang, R. Chen, and H. Chen, “Microsecond-scale preemption for concurrent $\\{$GPU-accelerated$\\}$$\\{$DNN$\\}$ inferences,” in _16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22)_ , 2022, pp. 539–558.
  * [26] W. Cui, H. Zhao, Q. Chen, N. Zheng, J. Leng, J. Zhao, Z. Song, T. Ma, Y. Yang, C. Li _et al._ , “Enable simultaneous dnn services based on deterministic operator overlap and precise latency prediction,” in _Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis_ , 2021, pp. 1–15.
  * [27] Z. Liu, J. Leng, Z. Zhang, Q. Chen, C. Li, and M. Guo, “Veltair: towards high-performance multi-tenant deep learning services via adaptive compilation and scheduling,” in _Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems_ , 2022, pp. 388–401.
  * [28] S. S. Mondal, N. Sheoran, and S. Mitra, “Scheduling of time-varying workloads using reinforcement learning,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 35, no. 10, 2021, pp. 9000–9008.
  * [29] Y. Han, S. Shen, X. Wang, S. Wang, and V. C. Leung, “Tailored learning-based scheduling for kubernetes-oriented edge-cloud system,” in _IEEE INFOCOM 2021-IEEE Conference on Computer Communications_. IEEE, 2021, pp. 1–10.
  * [30] X. Wang, Z. Ning, and S. Guo, “Multi-agent imitation learning for pervasive edge computing: A decentralized computation offloading algorithm,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 32, no. 2, pp. 411–425, 2020.
  * [31] J. Zou, T. Hao, C. Yu, and H. Jin, “A3c-do: A regional resource scheduling framework based on deep reinforcement learning in edge scenario,” _IEEE Transactions on Computers_ , vol. 70, no. 2, pp. 228–239, 2020.
  * [32] D. Shi, H. Gao, L. Wang, M. Pan, Z. Han, and H. V. Poor, “Mean field game guided deep reinforcement learning for task placement in cooperative multiaccess edge computing,” _IEEE Internet Things Journal_ , vol. 7, no. 10, pp. 9330–9340, 2020.
  * [33] S. Tuli, G. Casale, and N. R. Jennings, “Mcds: Ai augmented workflow scheduling in mobile edge cloud computing systems,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 33, no. 11, pp. 2794–2807, 2021.
  * [34] J. Meng, H. Tan, X.-Y. Li, Z. Han, and B. Li, “Online deadline-aware task dispatching and scheduling in edge computing,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 31, no. 6, pp. 1270–1286, 2019.
  * [35] A. Qiao, S. K. Choe, S. J. Subramanya, W. Neiswanger, Q. Ho, H. Zhang, G. R. Ganger, and E. P. Xing, “Pollux: Co-adaptive cluster scheduling for goodput-optimized deep learning,” in _15th $\\{$USENIX$\\}$ Symposium on Operating Systems Design and Implementation ($\\{$OSDI$\\}$ 21)_, 2021.
  * [36] P. Christodoulou, “Soft actor-critic for discrete action settings,” _arXiv preprint arXiv:1910.07207_ , 2019.
  * [37] T. Haarnoja, A. Zhou, K. Hartikainen, G. Tucker, S. Ha, J. Tan, V. Kumar, H. Zhu, A. Gupta, P. Abbeel _et al._ , “Soft actor-critic algorithms and applications,” _arXiv preprint arXiv:1812.05905_ , 2018.
  * [38] A. G. Howard, M. Zhu, B. Chen, D. Kalenichenko, W. Wang, T. Weyand, M. Andreetto, and H. Adam, “Mobilenets: Efficient convolutional neural networks for mobile vision applications,” _arXiv preprint arXiv:1704.04861_ , 2017.
  * [39] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770–778.
  * [40] M. Tan and Q. Le, “Efficientnet: Rethinking model scaling for convolutional neural networks,” in _International conference on machine learning_. PMLR, 2019, pp. 6105–6114.
  * [41] C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna, “Rethinking the inception architecture for computer vision,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 2818–2826.
  * [42] X. Jiao, Y. Yin, L. Shang, X. Jiang, X. Chen, L. Li, F. Wang, and Q. Liu, “TinyBERT: Distilling BERT for natural language understanding,” in _Findings of the Association for Computational Linguistics: EMNLP 2020_ , Nov. 2020, pp. 4163–4174.
  * [43] D. Whitley, “A genetic algorithm tutorial,” _Statistics and computing_ , vol. 4, no. 2, pp. 65–85, 1994.
  * [44] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” _arXiv preprint arXiv:1707.06347_ , 2017\.
  * [45] H. Van Hasselt, A. Guez, and D. Silver, “Deep reinforcement learning with double q-learning,” in _Proceedings of the AAAI conference on artificial intelligence_ , vol. 30, no. 1, 2016.
  * [46] Q. Chen, H. Yang, J. Mars, and L. Tang, “Baymax: Qos awareness and increased utilization for non-preemptive accelerators in warehouse scale computers,” _ACM SIGPLAN Notices_ , vol. 51, no. 4, pp. 681–696, 2016.

|  Ziyang Zhang Ziyang Zhang received the MS degrees in the School of
Electronic Information and Optical Engineering, Nankai University, Tianjin,
China, in 2020. He is currently working toward the PhD degree in the School of
Computer Science and Technology, Harbin Institute of Technology (HIT), Harbin,
China. His research interests include edge computing, machine learning system,
and deep learning.
---|---
|  Huan Li Dr. Huan Li obtained her PhD degree in Computer Science from the
University of Massachusetts at Amherst, USA in 2006. Her current research
interests include AIoT, Edge intelligence, distributed real-time systems, and
data science. She has served as program committee member for numerous
international conferences including IEEE RTAS, ICDCS, RTCSA, etc. She is now a
senior member of IEEE.
---|---
|  Yang Zhao Yang Zhao received the BS degree (2003) in electrical engineering
from Shandong University, the MS degree (2006) in electrical engineering from
the Beijing University of Aeronautics and Astronautics, and the PhD degree
(2012) in electrical and computer engineering from the University of Utah. He
was a lead research engineer at GE Global Research between 2013 and 2021.
Since 2021, he has been at Harbin Institute of Technology, Shenzhen, where he
is a research professor in the International Research Institute for Artificial
Intelligence. His research interests include wireless sensing, edge computing
and cyber physical systems. He is a senior member of the IEEE.
---|---
|  Changyao Lin Changyao Lin received the BS and MS degrees in the School of
Computer Science and Technology, Harbin Institute of Technology (HIT), Harbin,
China, in 2020 and 2022, respectively. He is currently working toward the PhD
degree at HIT. His research interests include edge computing, distributed
system, and deep learning.
---|---
|  Jie Liu Jie Liu is a Chair Professor at Harbin Institute of Technology
Shenzhen (HIT Shenzhen), China and the Dean of its AI Research Institute.
Before joining HIT, he spent 18 years at Xerox PARC and Microsoft. He was a
Principal Research Manager at Microsoft Research, Redmond and a partner of the
company. His research interests are Cyber-Physical Systems, AI for IoT, and
energy efficient computing. He received IEEE TCCPS Distinguished Leadership
Award and 6 Best Paper Awards from top conferences. He is an IEEE Fellow and
an ACM Distinguished Scientist, and founding Chair of ACM SIGBED China.
---|---