\section{Discussion}
\vspace{-1mm}

\textbf{One-shot NAS methods.}
Recently, one-shot NAS methods \citep{ofa,one-shot,nayman2021hardcorenas} are drawing much attention,
which trains the supernet only once and searches for a sub-network for a given purpose.
However, one-shot NAS method is not a directly satisfying solution for the constrained co-search task.
First,
hardware metrics of each network need to be measured on the whole hardware accelerator search space, then compared with each other, which is a non-trivial process that takes a long time.
Furthermore, cost for training the entire supernet itself is often multiple times more expensive than that of a conventional differentiable NAS, and searching for each subnetwork is also costly, making the break-even number of deployments very high.

Nonetheless, if multiple deployments are planned over diverse constraints, we believe HDX\xspace can utilize one-shot NAS as its backbone thanks to its differentiability.
One way to apply one-shot NAS method onto HDX\xspace is to attach differentiable architecture selector on pre-trained supernet.
Since both components are differentiable neural networks, gradient manipulation technique can be applied to them in a coherent manner.
Expanding our experiment further to include one-shot NAS as our network search backbone is left as future work.

\textbf{Expanding Design Space.} One might wonder whether the scheme used in HDX\xspace can be applied to other co-exploration methods.
For example, \citet{li2020edd} and \citet{fu2021autonba} optimize the quantization level of each layer in addition to the neural architecture.
We believe HDX\xspace can accommodate such additional design space into consideration.
Provided that there exists a analytic or simulation model for those additional spaces (which is not difficult to build),
satisfying hard-constraint through gradient manipulation is likely to work with little extra effort.

\section{Discussion}
\vspace{-1mm}

\textbf{One-shot NAS methods.}
Recently, one-shot NAS methods \citep{ofa,one-shot,nayman2021hardcorenas} are drawing much attention,
which trains the supernet only once and searches for a sub-network for a given purpose.
However, one-shot NAS method is not a directly satisfying solution for the constrained co-search task.
First,
hardware metrics of each network need to be measured on the whole hardware accelerator search space, then compared with each other, which is a non-trivial process that takes a long time.
Furthermore, cost for training the entire supernet itself is often multiple times more expensive than that of a conventional differentiable NAS, and searching for each subnetwork is also costly, making the break-even number of deployments very high.

Nonetheless, if multiple deployments are planned over diverse constraints, we believe HDX\xspace can utilize one-shot NAS as its backbone thanks to its differentiability.
One way to apply one-shot NAS method onto HDX\xspace is to attach differentiable architecture selector on pre-trained supernet.
Since both components are differentiable neural networks, gradient manipulation technique can be applied to them in a coherent manner.
Expanding our experiment further to include one-shot NAS as our network search backbone is left as future work.

\textbf{Expanding Design Space.} One might wonder whether the scheme used in HDX\xspace can be applied to other co-exploration methods.
For example, \citet{li2020edd} and \citet{fu2021autonba} optimize the quantization level of each layer in addition to the neural architecture.
We believe HDX\xspace can accommodate such additional design space into consideration.
Provided that there exists a analytic or simulation model for those additional spaces (which is not difficult to build),
satisfying hard-constraint through gradient manipulation is likely to work with little extra effort.

\section{Introduction}
The primary interest of most \emph{Deep Neural Network} (DNN) researches has been the application performance (i.e., accuracy).
However, it also led to the rapid growth in the network size that require immense computational resources for execution.
In recent years, numerous schemes have appeared to mitigate the resource problem, mostly belonging to one of these categories -- \emph{network-side optimization} and \emph{hardware-side optimization}.
Network-side optimization refers to refining the architecture of a neural network to reduce computations while maintaining a comparable accuracy~\citep{mobilenetv2, dorefa}.
Hardware-side optimization often involves improving DNN execution efficiency by using optimized hardware, also known as \emph{accelerator}s~\citep{eyeriss, tpu}.
Unfortunately, effort from one side often hinders the benefits coming from the other.
For example, the main advantage of depth-wise separable convolution operation used in MobileNet~\citep{mobilenetv2} comes from its structure which uses a single channel for its operation.
However, Google's TPU~\citep{tpu}, a renowned accelerator, mainly utilizes channel-level parallelism for gaining speedup. In consequence, MobileNet results in a poor execution time on TPUs~\citep{edgetpunas}.

Co-exploration of hardware accelerator and network architecture~\citep{li2020edd, fu2021autonba, dance, abdelfattah2020best, hao2019fpgadnn, lu2019neural, yang2020coexploration} is therefore a natural direction to fulfill both goals of accuracy and hardware metrics such as latency, energy consumption and silicon chip area.
To address the large search space of the co-exploration,
\emph{differentiable co-exploration} methods~\citep{dance, li2020edd, fu2021autonba} are considered as promising approaches due to their ability to quickly explore the search space compared to its reinforcement learning based counterparts~\citep{abdelfattah2020best, hao2019fpgadnn, lu2019neural, yang2020coexploration, lin2021naas}.

Unfortunately, differentiable co-exploration has a serious drawback of being unable to deal with hard constraints that are critical in many real-world scenarios.
For instance, an important constraint of object detection system~\citep{yolo} is to meet the frame rate of the camera (e.g., 30 frames per second).
In addition, a mobile subsystem running on a limited battery often has a power budget.
Because differentiable co-exploration methods rely on a single loss function, they often fail to satisfy the constraints, and have to blindly undergo a several repetitions of hyper-parameter tuning and re-exploration.

\sloppypar{
In order to address the problem, we present \emph
{HDX\xspace}
(\underline{\textbf{H}}ard-constrained \underline{\textbf{D}}ifferentiable
e\underline{\textbf{X}}ploration),
which enables hard-constrained differentiable co-exploration of neural architecture and hardware accelerator.
}
The key concept of our proposal
is a gradient manipulation method which ensures that the solution does not drift away from meeting the constraints.
In addition to the gradients from the global loss,
we calculate the gradient from the hardware constraints, which is used to manipulate gradient of the global loss, if any constraint violations, such that i) the dot product of the two are positive (i.e., they point to a similar direction), and ii) the direction can alleviate the violation of the constraints.

To the best of our knowledge, this is the first work that considers hard constraints in a differentiable co-exploration problem.
We conduct an extensive amount of evaluation to demonstrate that HDX\xspace can 1) satisfy the hardware constraints even under tight constraints and 2) search solutions without compromising the quality.

Our contributions can be summarized as follows.
\begin{itemize}
    \item We propose HDX\xspace, a hard-constrained differentiable co-exploration method for network and accelerator in order to find valid solutions without trial-and-errors.
    \item We propose using gradient manipulation to gradually move solutions towards the constraint-satisfying region.
    \item We provide an extensive evaluation for HDX\xspace to show its constraint-meeting capability and efficiency.
\end{itemize}

\vspace{-2mm}
\section{Background and Related Work}
\vspace{-1mm}
\subsection{Neural Architecture Search}
\vspace{-1mm}
Neural Architecture Search (NAS) refers to the technique of automating the neural network design process.
To mitigate its huge cost (thousands of GPU-hours), Differentiable NAS~\citep{liu2019darts} has been proposed as an efficient alternative, which converts the problem to training a supernet that reduces the time cost by a few digits.

Regardless, optimizing solely on network performance is insufficient as they do not take hardware efficiency into account.
Some recent works~\citep{cai2019proxylessnas} that address this issue consider hardware costs by adding loss terms, and
some attempt to reduce the network size for latency constraints using simple latency models~\citep{nayman2021hardcorenas,aows}.
However, they only consider the network design, and cannot be used for co-exploration since the relation between network accuracy and hardware structure is not reflected in the model.

\subsection{DNN-Accelerator Co-exploration}
The early work on the co-exploration utilize variants of reinforcement learning, or evolutionary algorithm to leverage its simplicity~\cite{hao2019fpgadnn,lu2019neural,jiang2019accuracy,abdelfattah2020best, yang2020coexploration,lin2021naas}.
Each candidate network is trained for evaluation, while the accelerator design is analyzed for hardware efficiency.
These values create rewards used by the agent to create the next candidate solution.
However, they all inherit the same problem from RL-based NAS methods in which they require expensive training to evaluate each candidate solution.
To worsen the matter, co-exploration requires even larger network/hardware search space than searching only for networks.

In such regard, differentiable approaches were adopted to co-exploration~\citep{li2020edd}.
Auto-NBA~\citep{fu2021autonba} used a differentiable accelerator search engine to build a joint-search pipeline, and
DANCE~\citep{dance} trained auxiliary neural networks for hardware search and cost evaluation.
However, none of the above properly addresses the hard constraint problem.
In this work, we propose a holistic method of handling hard constraints on differentiable co-exploration.

\begin{comment}

\subsection{Gradient Manipulation}
Directly managing gradients \JL{let's put these into 4.3}

\citep{lopez2017gradient} -- using exemplar, the gradients for old/new tasks should be same direction (g*g' >=0)

\citep{saha2021gradient} -- (Gradient Projection Memory) Continual. apply SVD to weights, and new gradients should be orthogonal to significant components

\citep{li2021large} -- similar to dpm aircraft

\citep{dpm} -- two goals
\end{comment}

\begin{comment}
In the real-world application, there often exists strict resource bounds.
In such cases, we need to be able to find the optimal network/accelerator pair that comply to such conditions. To solve the problem of resource-aware differentiable NAS, a concurrent work ~\citep{nayman2021hardcorenas} additionally sets a hardware constraint(e.g. latency) to satisfy strictly bounded resource demand. However, it relies on a predefined lookup table for resource measurements and thus does not search for optimal hardware implementation.
\end{comment}

\section{Motivational Experiment}
\label{sec:difficulty}

\begin{figure}[t]
    \centering
    \includegraphics[width=0.95\columnwidth]{iclr2022/motivation.png}
    \vspace{-3.5mm}
    \caption{A motivational experiment. In each plot, we swept the value $\lambda_{Cost}$ 0.001 to 0.010.
    It is clear that the trajectory is not strictly linear to $\lambda_{cost}$ with high variations. }
    \label{fig:motivational exp}
    \vspace{-3mm}
\end{figure}

The most straightforward and na\"ive way to handle hard constraints within differentiable co-exploration would be to tune the relative weight to the hardware cost.
For example, below is the loss function used in differentiable co-exploration~\citep{dance,fu2021autonba}.
\begin{align}

    \mathcal{L}oss &= \mathcal{L}oss_{CE} + \lambda_{Cost}Cost_{HW},
    \label{eq:danceloss}
\end{align}
which is designed co-optimize accuracy and hardware cost simultaneously, and $\lambda_{Cost}$ balances the two terms\footnote{It is different from hyperparameters of typical machine learning formulation where the two terms serve toward a single objective.}.
By increasing $\lambda_{Cost}$, one can indirectly instruct the search process to consider hardware metrics more.
However, giving a larger penalty
does not directly lead to reduction in the value of a constrained metric.
\figurename~\ref{fig:motivational exp} plots how changing $\lambda_{Cost}$ in \cref{eq:danceloss} from 0.001 to 0.010 affects the latency/energy and the classification error for CIFAR-10 dataset.
Searches were done three times for each setting and plotted with the same colors with large dots for their averages.
Even though some trend is observed that depends on $\lambda_{Cost}$, inconsistency in both direction and variance of the trajectory is more dominant.

Consider a scenario where a designer wants to design a neural network-accelerator architecture pair with latency under some constraint (e.g., \SI{33.3}{\milli\second}), using the conventional co-exploration methods.
The designer would try searching with some initial $\lambda_{Cost}$ and try adjusting the value over the course of multiple searches.
However, such inconsistency between $\lambda_{Cost}$ and the latency makes it extremely difficult to obtain the adequate solution, not to mention the huge time cost of performing the search numerous times.
Despite the difficulties that lie in tackling a hard-constrained co-exploration problem,
designing an effective strategy is necessary.

\section{Hard-Constrained Co-exploration}
\subsection{Problem Definition}
The mathematical formulation of hard-constrained differentiable co-exploration is as below:
\begin{align}
\small
    \argmin_{\alpha, \beta} &(\mathcal{L}oss_{NAS} (w^*, net(\alpha)) + \lambda_{Cost} Cost_{HW}(eval(\alpha, \beta))), \notag \\
    &\textrm{s.t.}\ \ w^* = \argmin_{w} (\mathcal{L}oss_{NAS}(w, net(\alpha))), \ \ \ t\leq T,
\label{eq:object}
\end{align}
where $t$ denotes the current value of constrained metric such as latency or energy, and $T$ is the target value (e.g., 33.3 \SI{}{\milli\second} for latency).
$\alpha$ and $\beta$ denote network architecture parameters and hardware accelerator configuration, respectively. ${w}$ is the weights of the NAS supernet and ${net(\alpha)}$ is the current dominant network architecture selected.
${eval(\alpha, \beta)}$ indicates the hardware metrics evaluated for $\alpha$ and $\beta$.
The objective of co-exploration is expressed using two distinct evaluation metrics, which are neural architecture loss ($\mathcal{L}oss_{NAS}$) and hardware cost ($Cost_{HW}$) defined from the user.

\subsection{Differentiable Co-exploration Framework}
Although our main contribution is that we enable hard constraints, we explain our framework for the co-exploration since they are closely related.
\figurename~\ref{fig:HDX} illustrates the overall architecture of the proposed method, being similar to existing methods~\cite{dance, fu2021autonba}.
\figurename~\ref{fig:HDX} (a) is the network search module.
This module searches for network architecture by choosing a path from the
supernet.
The network structure is then fed to the evaluator module.

The evaluator network $eval()$ is the key to the differentiable co-exploration that enables the gradient to flow into the supernet, considering the relation between the hardware accelerator.
It is a composition of two subnetworks: a hardware generator $gen()$ and an estimator $est()$.
The hardware generator takes the neural architecture parameters as inputs and uses them to output the optimal hardware implementation ($\beta$ from \eq{object}).
It is jointly trained during the co-exploration so that the generator does not depend on certain cost function, and can adapt to the constraint.
The estimator network outputs the hardware-related metrics by taking output of the generator and the network.
It is pre-trained according to the network and the accelerator search space.
For pre-training the estimator, traditional (non-differentiable) cost estimation frameworks such as MAESTRO~\citep{maestro_toppicks2020}, Timeloop~\citep{TimeLoop}, and Accelergy~\citep{iccad_2019_accelergy} are used as ground truth.
After pre-training, the estimator is frozen during the exploration and is only used to infer the hardware cost given a network architecture.
With these, we convert \eq{object} as below:
\begin{align}
\small
    \argmin_{\alpha} (\mathcal{L}oss_{NAS} &(w^*, net(\alpha)) + \lambda_{Cost} Cost_{HW}(est(\alpha, gen(v^*, \alpha)))), \notag \\
    \textrm{s.t.}\ \ w^* &= \argmin_{w} (\mathcal{L}oss_{NAS}(w, net(\alpha))), \notag \\
                 \ \ v^* &= \argmin_{v} (Cost_{HW}(est(\alpha, gen(v, \alpha)))),
\label{eq:cosearch}
\end{align}
where $v$ is the weights for the hardware generator.

\begin{comment}

The generator is also modeled as a five-layer perceptron.
However, unlike existing methods, we do not pre-train the generator.
This has two benefits: First, the generator does not depend on certain cost function. A pre-trained generator would be useless if different cost function is required.
Second, it can adapt to the constraint.
As the manipulated gradient from the hard-constraint is back-propagated, the generator learns to create accelerators that comply with the constraint on given neural network architecture.
Thus, we choose to randomly init the generator and train it simultaneously with the network search module.

\end{comment}

\begin{figure}[t]
    \centering
    \includegraphics[width=.4\textwidth]{iclr2022/figs/DAC_version.drawio.png}
    \vspace{-3mm}
    \caption{Overall structure of HDX.

    }\vspace{-4mm}
    \label{fig:HDX}
\end{figure}

\subsection{Enabling Hard-Constraints with Gradient Manipulation}
In addition to the differentiable co-exploration methodology, we suggest the novel idea of gradient manipulation as an effective solution to the hard constraint problem.
Direct manipulation of gradients is a strategy often used in achieving multiple goals,
such as in continual learning~\citep{saha2021gradient} or differential equations~\citep{dpm}.
In this paper, we present a solution to apply gradient manipulation to the co-exploration problem in the interest of satisfying hard constraints.

The diagrams on \figurename~\ref{fig:HDX} (b) and (c) show a high-level abstraction of our gradient manipulation method.
The main idea is to artificially generate a force that can push the gradient in the direction that \emph{agree}s with the constraint.
The conditions under which the method is applied to compute the new gradient $g$ are defined as below:
\begin{equation}
    g =
        \begin{cases}
            g_{\mathcal{L}oss} & \text{, if } t \leq T \\
            &\text{ or } t > T \wedge g_{\mathcal{L}oss} \cdot g_{\mathcal{C}onst} \geq \text{0,} \\

            m_{\alpha} + g_{\mathcal{L}oss} &  \text{, otherwise} \\
        \end{cases}
\end{equation}
\begin{equation}
    g_{\mathcal{C}onst} = \frac{\partial \max(t - T ,0)}{\partial \alpha}.
\end{equation}

In the above equation, $g_{\mathcal{L}oss}$ is the original gradient from the global loss function defined as
\begin{equation}
\label{eq:global_loss}
    \mathcal{L}oss = \mathcal{L}oss_{NAS} + \lambda_{Cost}\cdot Cost_{HW},
\end{equation}
as in \eq{cosearch}, and $g_{\mathcal{C}onst}$ is the gradient of constraint loss that we define as: $\mathcal{C}onst=max(t - T ,0)$.
\JL{I moved the def. of t and T to section 3}
Note that $t$ is a function of $\alpha$, and thus can be backpropagated to find the gradient with respect to $\alpha$.
In an ideal case where the $t$ $\leq$ $T$, the constraint is already met so we do nothing.
In the unfortunate case when the constraint is still not met, we calculate for the dot product of the two gradients to determine the agreement in their directions.
If $g_{\mathcal{L}oss} \cdot g_{\mathcal{C}onst} \text{$\geq$ 0}$ (i.e., the angle between two gradients is less than 90\textdegree), it means gradient descent update will contribute towards satisfying the constraint.
Thus it is interpreted as an agreement in direction and the same $g_{\mathcal{L}oss}$ is used unmodified.
\figurename~\ref{fig:HDX} (b) depicts this scenario.
However, if they disagree as illustrated in \figurename~\ref{fig:HDX} (c) (i.e., $g_{\mathcal{L}oss} \cdot g_{\mathcal{C}onst} \text{$<$ 0}$), we force the gradient to shift its direction by $m_{\alpha}$, which is obtained from $(m_{\alpha} + g_{\mathcal{L}oss}) \cdot g_{\mathcal{C}onst} \text{$\geq$ 0}$ to guarantee decrease in target cost after gradient descent.
It can be reformulated as $m_{\alpha} \cdot g_{\mathcal{C}onst} + g_{\mathcal{L}oss} \cdot g_{\mathcal{C}onst} = \delta$ where $\delta \text{$\geq$ 0}$ is a small value for ensuring gradual movement towards satisfying the constraint.

For updating $\alpha$ and $w$,
we solve for optimal $m_{\alpha}$ with respect to $\alpha$, which are the parameters for the network architecture.
To minimize the effect of $m_{\alpha}$ on $g_{\mathcal{L}oss}$, we use a pseudoinverse-based solution that is known to minimize the size of $||m_{\alpha}||_2^2$ as below:
\begin{equation}
\label{eq:optimal_m}
    m_\alpha^* = \frac{-(g_{\mathcal{L}oss} \cdot g_{\mathcal{C}onst})  + \delta}{||g_{\mathcal{C}onst}||_2^2} g_{\mathcal{C}onst}.
\end{equation}
In order to control the magnitude of the pull, we use a small multiplying factor $p>0$ on $\delta$. The policy for updating $\delta$ using $p$ is as follows: Some initial value $\delta_{0}$ exists for $\delta$. If the target metric fails to meet the constraint, $\delta$ is multiplied by $1+p$ to strengthen the pull ($\delta^{'} = (1+p)\delta$). In the other case when the constraint is satisfied, $\delta$ is reset to its initial value ($\delta^{'} = \delta_{0}$).

Note that we also train $v$, weights for the hardware generator using gradient descent.
Thus we compute for $m_v^*$ in the same manner, but use $g_{\mathcal{C}ost_{HW}}$ in place of $g_{\mathcal{L}oss}$ for updating the generator.

Although a single constraint is already a challenging target, our method can be further generalized to accommodate multiple constraints.
Now the gradient is modified only in the direction of individual constraints that do not comply. We provide a more generalized formulation:
\begin{equation}
    g =
        \begin{cases}
            g_{\mathcal{L}oss} & \text{, if } \bigwedge_{i=1}^{n}(t_{i} \leq T_{i}) \\
            &\text{ or } \bigvee_{i=1}^{n}(t_i > T_{i}) \wedge g_{\mathcal{L}oss} \cdot g_{\mathcal{C}onst} \geq \text{0,} \\
            m_{\alpha} + g_{\mathcal{L}oss} &  \text{, otherwise}
        \end{cases}
\end{equation}
\begin{equation}
    g_{\mathcal{C}onst} = \frac{\partial \sum_{i=1}^{n}\max(t_{i} - T_{i} ,0)}{\partial \alpha}.
\end{equation}

\subsection{Implementation Details}
\textbf{\ \ \ \ \ Hardware cost function.}
In this work, we choose the inference latency, energy, and the chip area as the widely used hardware metrics.
Considering all of them, a commonly used cost function is multiplying them (i.e., EDP, EDAP) as in \cite{dance, fu2021autonba}.
However, we found that the energy is usually easier to optimize for, and using such cost function unfairly favors energy-oriented designs.
Therefore, we use a balanced weighted sum for the cost function as below.
\begin{equation}
\small
    Cost_{HW} = C_EEnergy + C_LLatency + C_AArea.
\vspace{-1mm}
\label{eq:cost_hw}
\end{equation}

\textbf{Estimator and Generator Network.} Following \cite{dance}, we model both the estimator and generator with five-layer Multi-Layer Perceptron (MLP) with residual connections.
To train the estimator, we first build a dataset by randomly sampling 10.8M network-accelerator pairs ($2.95\mathrm{e}{-9}$ \% of the total search space) from our search space which are evaluated on hardware metrics using Timeloop~\citep{TimeLoop} and Accelergy~\citep{iccad_2019_accelergy}.
Using this dataset, the estimator is trained for 200 epochs with the batch size of 256. The weight update is done using Adam optimizer with the learning rate of 1e-4.
The accuracy of the estimator was over 99\% for all metrics, being powerful enough as an engine for co-exploration.
The generator is randomly initialized and jointly trained with the NAS supernet.
As the manipulated gradient from the hard-constraint is back-propagated, the generator learns to create accelerators that comply with the constraint on given neural network architecture.

\textbf{Search Space.}
We use ProxylessNAS \citep{cai2019proxylessnas} as a NAS backbone with path sampling to train $\alpha$.
It consists of multiple settings of MBConv operation with kernel size \{3, 5, 7\} and expand ratio \{3, 6\}.
The total number of layers is 18 and 21 for CIFAR-10~\cite{cifar} and ImageNet~\cite{imagenet} dataset, respectively.
However, our method is orthogonal to the NAS implementation and has the flexibility to choose from any differentiable NAS algorithms, such as DARTS~\cite{liu2019darts} or OFA~\cite{ofa}.

We use Eyeriss~\citep{eyeriss} as the accelerator's backbone architecture.
It is composed of a two-dimensional Processing Element~(PE) array where
each PEs has a Multiply-Accumulate~(MAC) unit attached to a register file.
Therefore, hardware accelerator design space comprises PE array size from 12$\times$8 to 20$\times$24, register file size per PE from 16B to 256B.
In addition, the search space includes dataflow of Weight-Stationary (WS) similar to \citep{tpu}, Output-Stationary (OS) similar to \citep{shidiannao} and Row-Stationary (RS) similar to \citep{eyeriss}.

\section{Experiments}
\subsection{Experimental Environment}
We have conducted experiments on HDX\xspace using CIFAR-10~\citep{cifar} and ImageNet~\citep{imagenet} dataset.
For all the hardware metrics (latency, energy, and chip area) reported, we have used the direct evaluation on the designed hardware from Timeloop~\cite{TimeLoop} and Accelergy~\cite{iccad_2019_accelergy} instead of the values outputted by the estimator to avoid any possible error in the learned model.
Evaluation of network accuracy is done by training the final network architecture, which we train from scratch for 300 epochs using the batch size of 64.
We use SGD optimizer with Nesterov momentum \citep{nesterov}, and cosine learning rate scheduling with 0.008 as its initial value, while weight decay term and momentum is 1e-3 and 0.9 respectively. Augmentation for the train data is adopted from AutoAugment \citep{Cubuk2019AutoAugmentLA}, on both dataset.

\subsection{Comparison with Existing Methods}
\label{sec:comparison}
\tablename~\ref{tbl:comparison} lists the existing differentiable co-exploration methods in comparison with HDX\xspace.
We compare the following methods:
\begin{itemize}[leftmargin=*]
    \item \textbf{NAS $\rightarrow$ HW}: A plain differentiable NAS~\cite{cai2019proxylessnas} only, followed by an exhaustive hardware search using Timeloop~\cite{TimeLoop}.

    \item \textbf{Auto-NBA~\cite{fu2021autonba}}: A differentiable co-exploration method that directly searches for hardware parameters using gradient descent, where the relation between hardware and the DNN is expressed as a lookup table.

    \item \textbf{DANCE~\cite{dance}}: State-of-the-art differentiable co-exploration method without hard constraints
    where the generator and estimator are modeled as neural networks.

    \item \textbf{DANCE + Soft Constraint}: To represent a reasonable approach for considering constraints with existing solutions, we have added a soft-constraint term $\lambda_{Soft} \cdot max(t/T-1,0)$ as in \citep{hu2020tf}.

    \item \textbf{HDX\xspace}: The proposed method with $p=1\mathrm{e}{-2}$.

\end{itemize}
As displayed in \tablename~\ref{tbl:comparison}, HDX\xspace is the only method that considers hard constraints with differentiable co-exploration.

For a quantitative comparison, we devised an algorithm for finding constrained solution using co-exploration without hard-constraints.
Because a constrained metric (e.g., latency) being too low often means an inefficient solution (in terms of other metrics (e.g., accuracy and energy), we set the criteria of having a solution of 50\%\textasciitilde 100\% of the target constraint.
A rough sketch of the algorithm similar to binary search is given below:
\begin{enumerate}
    \item Choose a control parameter ($\lambda_{Soft}$ and $\lambda_{Cost}$) that indirectly affects the metric under constraint (e.g., latency).
    \item Perform a search using the default control parameter value.
    \item Perform searches by doubling the control parameter each step until the metric is under the constraint.
    \item If the metric is under 50\% of the target value, shrink the control parameter in a binary search manner.
\end{enumerate}
Note that the problem cannot exactly be solved by binary search, because of huge per-search variations and non-linear relations as demonstrated in Section~\ref{sec:difficulty}.
In the actual implementation, more features are added to deal with corner cases and to avoid falling into wrong parameter region (which can happen from per-search variations).
We ran the algorithm 100 times and report the average.
We also report the average error as a proxy to the solution quality.

As presented in \tablename~\ref{tbl:comparison}, all baselines require multiple searches to find constraint-satisfying solutions.
For DANCE, it takes 6.6 searches with 12.2 GPU-hours on average and 4.9 searches and 9.1 GPU-hours on even with soft constraints.
On the other hand, HDX\xspace always searches for constraint-satisfying solutions in a single search.
Furthermore, the number of searches for baselines strongly depend on the choice of the default value of control parameter.
Guessing a right initial parameter is difficult, and could result in even larger repetition cost.
This advocates the need for HDX\xspace.

\begin{table}[t]
\vspace{-1mm}
    \centering

     \resizebox{\columnwidth}{!}
    {
    \begin{tabular}{lcccccccc}
     \toprule
  \multirow{2}{*}{Method} &  \multirow{2}{*}{\makecell{Hard \\ Constraint}} &  \multirow{2}{*}{\makecell{NN-HW \\Relation}} & \multicolumn{3}{c}{Search with 60 FPS Constraint}  \\
  \cmidrule(lr){4-6}
                          &                                   &                                  & \#Searches  & Cost*  & Avg. Err. (\%) \\
    \midrule

        NAS~\cite{cai2019proxylessnas} $\rightarrow$ HW search & \xmark & \xmark & 5.0 & 10.9h & 7.26 \\
        Auto-NBA~\cite{fu2021autonba} & \xmark & \cmark & 6.8 & 10.2h  & 5.67 \\
        DANCE~\cite{dance} & \xmark & \cmark & 6.6 & 12.2h & 5.32 \\

        DANCE + Soft const.~\cite{hu2020tf} & \xmark & \cmark & 4.9 & 9.1h  & 5.36 \\

        \midrule
       \textbf{ HDX\xspace (Proposed)} & \cmark & \cmark &  \textbf{1} & \textbf{2.0h} &  \textbf{4.65} \\
        \bottomrule
        \multicolumn{6}{r}{*GPU-hours}

    \end{tabular}
    }\\

\caption{Comparison of Differentiable Co-explorations}
\label{tbl:comparison}
\vspace{-10mm}
\end{table}

\subsection{Co-exploration Results}
\label{sec:results}

\figurename~\ref{fig:masterplot} plots the co-exploration experimental results from multiple techniques on CIFAR-10 dataset.
In the experiments, we have set two different constraints for the latency: 16.6\SI{}{\milli\second} (60 fps) and 33.3\SI{}{\milli\second} (30 fps).
For all co-exploration methods, we obtain five solutions by varying $\lambda_{Cost}$ from 0.001 to 0.005 to fairly compare the various design points obtained by each approach.
For $NAS\rightarrow HW$, we obtain 10 solutions of various range for reference, because directly applying $\lambda_{Cost}$ is infeasible.
For DANCE and Auto-NBA, the black markers are unconstrained, and colored markers are obtained with soft constraint of the corresponding colors.

\input{iclr2022/figs/master_three}

\input{iclr2022/figs/table_quality}

In all experiments, we have used $C_E=2.9$, $C_L=6.2$, and $C_A=1.0$ from \eq{cost_hw}, which makes the difference scale of each metric approximately the same to make a fair comparison.
For the NAS only method, $Cost_{HW}$ was used only for the hardware design phase.

\figurename~\ref{fig:masterplot} (left) and (mid) show the relation between error and latency.
The colored horizontal bars represent the two latency targets we applied.
It can be easily seen that all solutions found by HDX\xspace satisfy the given hard constraints regardless of the value of $\lambda_{Cost}$.
Furthermore, all solutions have the latency right below the constraint, showing that the solutions did not over-optimize for the constrained metric (latency).
DANCE~\citep{dance} and Auto-NBA~\cite{fu2021autonba} were able to exploit the trade-off between hardware metrics and accuracy, but has no control over meeting the constraint.
Even with soft-constraint terms, they mostly failed to obtain in-constraint solutions.
Auto-NBA at a glance seems to be slightly better at meeting the constraints, but it is because its baseline method favors hardware-efficient solutions over high-accuracy ones, not because of its ability to meet the constraint, exemplified by the fact that there is no solution with high accuracy, or latency under \SI{16.6}{\milli\second}.

\subsection{Solution Quality Found by HDX\xspace}
\label{sec:quality}
In this subsection, we demonstrate that HDX\xspace can 1) handle constraints from all three metrics (latency, energy, and chip area), 2) handle multiple constraints, and 3) obtain solutions of good overall quality.
\figurename~\ref{fig:masterplot} (right) plots $Cost_{HW}$ and error together, which allows evaluating quality of the solutions in terms of Pareto-optimality.
Because \figurename~\ref{fig:masterplot} (left) and (mid) overlook the other metrics, comparing the $Cost_{HW}$ together is required to be fair.

From the plot, it is clear that
quality of solutions from HDX\xspace is better than the NAS$\rightarrow$HW method, and has no degradation from the existing co-exploration methods.
In fact, the tightly constrained (16.6\SI{}{\milli\second}) solutions even find better solution than those of the existing solutions in terms of Pareto-optimality.

To further study the quality of the solutions found by HDX\xspace, we have conducted another set of experiments.
We selected a few solutions found from DANCE method as `Anchor' solutions and listed them in \tablename~\ref{tab:quality}.
From those, we chose either one or all three of the hardware metrics to be fixed as the hard constraint, and performed co-explorations using HDX\xspace.
Because it is guaranteed that such solution exists, a good method should be able to find a solution meeting the constraint, of at least a similar quality.
As in the Section~\ref{sec:results}, all of the 8 cases we have examined succeeded in finding a valid solution.
Furthermore, all the solutions show similar global loss values from the anchor solutions as shown in the rightmost column.

\vspace{-1mm}
\subsection{Results from ImageNet Dataset}
\vspace{-1mm}

\begin{table}[b]
\vspace{-3mm}
    \centering
    \scriptsize
    \caption{Experimental Results for ImageNet}
\vspace{-3mm}
    \label{tab:imgnet}
    \begin{tabular}{lccccc}
    \toprule

Method	&	in-const?	&	Lat. (ms)	&	Error (\%)	&	CostHW	&	Loss	\\
\midrule
\multirow{2}{*}{NAS$\rightarrow$HW}	&	\xmark	&	242.92	&	24.84	&	46.29	&	1.99	\\
	&	\xmark	&	135.39	&	28.83	&	24.26	&	2.17	\\
\midrule
\multirow{2}{*}{DANCE}	&	\xmark	&	165.98	&	25.46	&	29.37	&	2.04	\\
	&	\cmark	&	121.58	&	25.28	&	25.92	&	2.09	\\
\midrule
\multirow{2}{*}{DANCE+Soft Const.}	&	\xmark	&	188.69	&	25.09	&	33.14	&	1.99	\\

	&	\cmark	&	105.65	&	26.37	&	25.58	&	2.08	\\
\midrule

\multirow{2}{*}{\textbf{HDX (Proposed)}}	&	\cmark	&	92.06	&	25.01	&	24.48	&	1.98	\\

	&	\cmark	&	112.11	&	25.20	&	22.63	&	2.00	\\

\bottomrule
    \end{tabular}
\end{table}

\input{figs/sense}

\tablename~\ref{tab:imgnet} shows the co-exploration results from ImageNet dataset~\citep{imagenet}, under 125 ms constraint.
As displayed in the table, HDX\xspace always succeeded in finding a solution within constraint where the others often failed to satisfy.
Furthermore, the Top-1 error and the global loss shows that the quality of the solution found by HDX\xspace is not compromised at all, compared to DANCE or its variant.

\vspace{-1mm}
\subsection{Sensitivity Study on Pulling Magnitude}
\vspace{-1mm}

In HDX\xspace, the only hyperparameter is $p$ that controls the pulling magnitude.
\figurename~\ref{fig:sense} illustrates how the global loss and latency changes over latency-constrained (33.3 \SI{}{\milli\second}) explorations, with varying $p$ of 1e-2, 7e-3, and 4e-3.

Regardless of the value of $p$, the curve for the constrained value shows a similar trend.
At the beginning, the global loss becomes mainly optimized, while the latency stays steady.
During this phase the pulling magnitude $\delta$ (See \eq{optimal_m}) is still growing, and is not strong enough to make meaningful changes.
At certain point,
$\delta$ becomes strong enough to pull the solution towards lowering latency.
When the latency satisfies the constraint,
global loss starts to decrease while maintaining the latency.
There is no significant discrepancy between the final solution in the global loss and the latency, which shows that HDX\xspace is insensitive to the hyperparameter $p$.

\subsection{Analysis on the Searched Solutions}
\cref{fig:nn_hw_pair} visualizes the network and accelerator searched for 60 fps (a) and 30 fps (b) constraints.
For the found design pair (a), the design contains relatively smaller kernels, more layers, and a powerful accelerator.
To meet a tight constraint while maintaining accuracy, the network has small kernels, mainly of $3\times3$.
Using smaller kernels quadratically reduces the number of multiplications.
Therefore, decreasing the kernel size and increasing number of layers is a good choice for reducing inference latency.
Looking at the accelerator design, it has relatively large PE array (16$\times16$) to achieve low latency.
It takes weight stationary (WS) dataflow, which is known to have low latency.
In addition, there are some kernels with high channel expand ratio in the network.
WS exploits channel parallelism for fast execution, and thus has advantage over the found network.

On the other hand, in the design for 30 fps (b), the design settles at a solution that can optimize the energy consumption while satisfying the constraint.
The design uses larger kernels in the network and row stationary (RS) dataflow in the accelerator.
RS is known to have good energy efficiency~\cite{eyeriss}, and exploits parallelism from spatial dimensions of kernel and the activation.
Thus, having larger kernels have advantages on RS dataflow.
To reduce the energy consumption, the design has fewer PEs (12$\times$8), larger RFs to save off-chip access energy, and fewer layers in the network.

\vspace{-1mm}
\section{Conclusion}
\vspace{-1mm}
In this paper, we proposed HDX\xspace, a hard-constrained differentiable co-exploration method.
By conditionally applying gradient manipulation that moves the solution towards meeting the constraints,
hard constraints can be reliably satisfied with high-quality solutions.
We believe this proposal would ease the development of DNN based systems by a significant amount.

\begin{figure}
\begin{subfigure}[t]{0.4\columnwidth}
\includegraphics[width=\textwidth, trim={.3cm .1cm 1cm .1cm}, clip=true]{figs/nn_hw_60fps.pdf}
\vspace{-6.5mm}
\caption{}\label{fig:nn_hw_60fps}
\end{subfigure}
\hspace{3mm}
\begin{subfigure}[t]{0.4\columnwidth}
\includegraphics[width=\textwidth, trim={.3cm .1cm 1cm .1cm}, clip=true]{figs/nn_hw_30fps.pdf}
\vspace{-6.5mm}
\caption{}\label{fig:nn_hw_60fps}
\end{subfigure}
\vspace{-3mm}
\caption{Searched network and accelerator for 60 fps and 30 fps constraints. ($m$,$n$) refers MBConv block with $m\times m$ kernel and $n$ expand ratio.}
\vspace{-5mm}
\label{fig:nn_hw_pair}
\end{figure}

\begin{acks}
This work has been supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (2022R1C1C1008131,
2022R1C1C1011307),
and
Institute of Information \& communications Technology Planning \& Evaluation
(IITP) grant funded by the Korea government (MSIT)
(2020-0-01361,
Artificial Intelligence Graduate School Program (Yonsei University
).
\end{acks}

\bibliographystyle{ACM-Reference-Format-ks}

\section{Introduction}
ACM's consolidated article template, introduced in 2017, provides a
consistent \LaTeX\ style for use across ACM publications, and
incorporates accessibility and metadata-extraction functionality
necessary for future Digital Library endeavors. Numerous ACM and
SIG-specific \LaTeX\ templates have been examined, and their unique
features incorporated into this single new template.

If you are new to publishing with ACM, this document is a valuable
guide to the process of preparing your work for publication. If you
have published with ACM before, this document provides insight and
instruction into more recent changes to the article template.

The ``\verb|acmart|'' document class can be used to prepare articles
for any ACM publication --- conference or journal, and for any stage
of publication, from review to final ``camera-ready'' copy, to the
author's own version, with {\itshape very} few changes to the source.

\section{Template Overview}
As noted in the introduction, the ``\verb|acmart|'' document class can
be used to prepare many different kinds of documentation --- a
double-blind initial submission of a full-length technical paper, a
two-page SIGGRAPH Emerging Technologies abstract, a ``camera-ready''
journal article, a SIGCHI Extended Abstract, and more --- all by
selecting the appropriate {\itshape template style} and {\itshape
  template parameters}.

This document will explain the major features of the document
class. For further information, the {\itshape \LaTeX\ User's Guide} is
available from
\url{https://www.acm.org/publications/proceedings-template}.

\subsection{Template Styles}

The primary parameter given to the ``\verb|acmart|'' document class is
the {\itshape template style} which corresponds to the kind of publication
or SIG publishing the work. This parameter is enclosed in square
brackets and is a part of the {\verb|documentclass|} command:
\begin{verbatim}
  \documentclass[STYLE]{acmart}
\end{verbatim}

Journals use one of three template styles. All but three ACM journals
use the {\verb|acmsmall|} template style:
\begin{itemize}
\item {\texttt{acmsmall}}: The default journal template style.
\item {\texttt{acmlarge}}: Used by JOCCH and TAP.
\item {\texttt{acmtog}}: Used by TOG.
\end{itemize}

The majority of conference proceedings documentation will use the {\verb|acmconf|} template style.
\begin{itemize}
\item {\texttt{acmconf}}: The default proceedings template style.
\item{\texttt{sigchi}}: Used for SIGCHI conference articles.
\item{\texttt{sigchi-a}}: Used for SIGCHI ``Extended Abstract'' articles.
\item{\texttt{sigplan}}: Used for SIGPLAN conference articles.
\end{itemize}

\subsection{Template Parameters}

In addition to specifying the {\itshape template style} to be used in
formatting your work, there are a number of {\itshape template parameters}
which modify some part of the applied template style. A complete list
of these parameters can be found in the {\itshape \LaTeX\ User's Guide.}

Frequently-used parameters, or combinations of parameters, include:
\begin{itemize}
\item {\texttt{anonymous,review}}: Suitable for a ``double-blind''
  conference submission. Anonymizes the work and includes line
  numbers. Use with the \texttt{\acmSubmissionID} command to print the
  submission's unique ID on each page of the work.
\item{\texttt{authorversion}}: Produces a version of the work suitable
  for posting by the author.
\item{\texttt{screen}}: Produces colored hyperlinks.
\end{itemize}

This document uses the following string as the first command in the
source file:
\begin{verbatim}
\documentclass[sigconf]{acmart}
\end{verbatim}

\section{Modifications}

Modifying the template --- including but not limited to: adjusting
margins, typeface sizes, line spacing, paragraph and list definitions,
and the use of the \verb|\vspace| command to manually adjust the
vertical spacing between elements of your work --- is not allowed.

{\bfseries Your document will be returned to you for revision if
  modifications are discovered.}

\section{Typefaces}

The ``\verb|acmart|'' document class requires the use of the
``Libertine'' typeface family. Your \TeX\ installation should include
this set of packages. Please do not substitute other typefaces. The
``\verb|lmodern|'' and ``\verb|ltimes|'' packages should not be used,
as they will override the built-in typeface families.

\section{Title Information}

The title of your work should use capital letters appropriately -
\url{https://capitalizemytitle.com/} has useful rules for
capitalization. Use the {\verb|title|} command to define the title of
your work. If your work has a subtitle, define it with the
{\verb|subtitle|} command.  Do not insert line breaks in your title.

If your title is lengthy, you must define a short version to be used
in the page headers, to prevent overlapping text. The \verb|title|
command has a ``short title'' parameter:
\begin{verbatim}
  \title[short title]{full title}
\end{verbatim}

\section{Authors and Affiliations}

Each author must be defined separately for accurate metadata
identification.  As an exception, multiple authors may share one
affiliation. Authors' names should not be abbreviated; use full first
names wherever possible. Include authors' e-mail addresses whenever
possible.

Grouping authors' names or e-mail addresses, or providing an ``e-mail
alias,'' as shown below, is not acceptable:
\begin{verbatim}
  \author{Brooke Aster, David Mehldau}
  \email{dave,judy,steve@university.edu}
  \email{firstname.lastname@phillips.org}
\end{verbatim}

The \verb|authornote| and \verb|authornotemark| commands allow a note
to apply to multiple authors --- for example, if the first two authors
of an article contributed equally to the work.

If your author list is lengthy, you must define a shortened version of
the list of authors to be used in the page headers, to prevent
overlapping text. The following command should be placed just after
the last \verb|\author{}| definition:
\begin{verbatim}
  \renewcommand{\shortauthors}{McCartney, et al.}
\end{verbatim}
Omitting this command will force the use of a concatenated list of all
of the authors' names, which may result in overlapping text in the
page headers.

The article template's documentation, available at
\url{https://www.acm.org/publications/proceedings-template}, has a
complete explanation of these commands and tips for their effective
use.

Note that authors' addresses are mandatory for journal articles.

\section{Rights Information}

Authors of any work published by ACM will need to complete a rights
form. Depending on the kind of work, and the rights management choice
made by the author, this may be copyright transfer, permission,
license, or an OA (open access) agreement.

Regardless of the rights management choice, the author will receive a
copy of the completed rights form once it has been submitted. This
form contains \LaTeX\ commands that must be copied into the source
document. When the document source is compiled, these commands and
their parameters add formatted text to several areas of the final
document:
\begin{itemize}
\item the ``ACM Reference Format'' text on the first page.
\item the ``rights management'' text on the first page.
\item the conference information in the page header(s).
\end{itemize}

Rights information is unique to the work; if you are preparing several
works for an event, make sure to use the correct set of commands with
each of the works.

The ACM Reference Format text is required for all articles over one
page in length, and is optional for one-page articles (abstracts).

\section{CCS Concepts and User-Defined Keywords}

Two elements of the ``acmart'' document class provide powerful
taxonomic tools for you to help readers find your work in an online
search.

The ACM Computing Classification System ---
\url{https://www.acm.org/publications/class-2012} --- is a set of
classifiers and concepts that describe the computing
discipline. Authors can select entries from this classification
system, via \url{https://dl.acm.org/ccs/ccs.cfm}, and generate the
commands to be included in the \LaTeX\ source.

User-defined keywords are a comma-separated list of words and phrases
of the authors' choosing, providing a more flexible way of describing
the research being presented.

CCS concepts and user-defined keywords are required for for all
articles over two pages in length, and are optional for one- and
two-page articles (or abstracts).

\section{Sectioning Commands}

Your work should use standard \LaTeX\ sectioning commands:
\verb|section|, \verb|subsection|, \verb|subsubsection|, and
\verb|paragraph|. They should be numbered; do not remove the numbering
from the commands.

Simulating a sectioning command by setting the first word or words of
a paragraph in boldface or italicized text is {\bfseries not allowed.}

\section{Tables}

The ``\verb|acmart|'' document class includes the ``\verb|booktabs|''
package --- \url{https://ctan.org/pkg/booktabs} --- for preparing
high-quality tables.

Table captions are placed {\itshape above} the table.

Because tables cannot be split across pages, the best placement for
them is typically the top of the page nearest their initial cite.  To
ensure this proper ``floating'' placement of tables, use the
environment \textbf{table} to enclose the table's contents and the
table caption.  The contents of the table itself must go in the
\textbf{tabular} environment, to be aligned properly in rows and
columns, with the desired horizontal and vertical rules.  Again,
detailed instructions on \textbf{tabular} material are found in the
\textit{\LaTeX\ User's Guide}.

Immediately following this sentence is the point at which
Table~\ref{tab:freq} is included in the input file; compare the
placement of the table here with the table in the printed output of
this document.

\begin{table}
  \caption{Frequency of Special Characters}
  \label{tab:freq}
  \begin{tabular}{ccl}
    \toprule
    Non-English or Math&Frequency&Comments\\
    \midrule
    \O & 1 in 1,000& For Swedish names\\
    $\pi$ & 1 in 5& Common in math\\
    \$ & 4 in 5 & Used in business\\
    $\Psi^2_1$ & 1 in 40,000& Unexplained usage\\
  \bottomrule
\end{tabular}
\end{table}

To set a wider table, which takes up the whole width of the page's
live area, use the environment \textbf{table*} to enclose the table's
contents and the table caption.  As with a single-column table, this
wide table will ``float'' to a location deemed more
desirable. Immediately following this sentence is the point at which
Table~\ref{tab:commands} is included in the input file; again, it is
instructive to compare the placement of the table here with the table
in the printed output of this document.

\begin{table*}
  \caption{Some Typical Commands}
  \label{tab:commands}
  \begin{tabular}{ccl}
    \toprule
    Command &A Number & Comments\\
    \midrule
    \texttt{{\char'134}author} & 100& Author \\
    \texttt{{\char'134}table}& 300 & For tables\\
    \texttt{{\char'134}table*}& 400& For wider tables\\
    \bottomrule
  \end{tabular}
\end{table*}

Always use midrule to separate table header rows from data rows, and
use it only for this purpose. This enables assistive technologies to
recognise table headers and support their users in navigating tables
more easily.

\section{Math Equations}
You may want to display math equations in three distinct styles:
inline, numbered or non-numbered display.  Each of the three are
discussed in the next sections.

\subsection{Inline (In-text) Equations}
A formula that appears in the running text is called an inline or
in-text formula.  It is produced by the \textbf{math} environment,
which can be invoked with the usual
\texttt{{\char'134}begin\,\ldots{\char'134}end} construction or with
the short form \texttt{\$\,\ldots\$}. You can use any of the symbols
and structures, from $\alpha$ to $\omega$, available in
\LaTeX~\cite{Lamport:LaTeX}; this section will simply show a few
examples of in-text equations in context. Notice how this equation:
\begin{math}
  \lim_{n\rightarrow \infty}x=0
\end{math},
set here in in-line math style, looks slightly different when
set in display style.  (See next section).

\subsection{Display Equations}
A numbered display equation---one set off by vertical space from the
text and centered horizontally---is produced by the \textbf{equation}
environment. An unnumbered display equation is produced by the
\textbf{displaymath} environment.

Again, in either environment, you can use any of the symbols and
structures available in \LaTeX\@; this section will just give a couple
of examples of display equations in context.  First, consider the
equation, shown as an inline equation above:
\begin{equation}
  \lim_{n\rightarrow \infty}x=0
\end{equation}
Notice how it is formatted somewhat differently in
the \textbf{displaymath}
environment.  Now, we'll enter an unnumbered equation:
\begin{displaymath}
  \sum_{i=0}^{\infty} x + 1
\end{displaymath}
and follow it with another numbered equation:
\begin{equation}
  \sum_{i=0}^{\infty}x_i=\int_{0}^{\pi+2} f
\end{equation}
just to demonstrate \LaTeX's able handling of numbering.

\section{Figures}

The ``\verb|figure|'' environment should be used for figures. One or
more images can be placed within a figure. If your figure contains
third-party material, you must clearly identify it as such, as shown
in the example below.
\begin{figure}[h]
  \centering
  \includegraphics[width=\linewidth]{sample-franklin}
  \caption{1907 Franklin Model D roadster. Photograph by Harris \&
    Ewing, Inc. [Public domain], via Wikimedia
    Commons. (\url{https://goo.gl/VLCRBB}).}
  \Description{A woman and a girl in white dresses sit in an open car.}
\end{figure}

Your figures should contain a caption which describes the figure to
the reader.

Figure captions are placed {\itshape below} the figure.

Every figure should also have a figure description unless it is purely
decorative. These descriptions convey what’s in the image to someone
who cannot see it. They are also used by search engine crawlers for
indexing images, and when images cannot be loaded.

A figure description must be unformatted plain text less than 2000
characters long (including spaces).  {\bfseries Figure descriptions
  should not repeat the figure caption – their purpose is to capture
  important information that is not already provided in the caption or
  the main text of the paper.} For figures that convey important and
complex new information, a short text description may not be
adequate. More complex alternative descriptions can be placed in an
appendix and referenced in a short figure description. For example,
provide a data table capturing the information in a bar chart, or a
structured list representing a graph.  For additional information
regarding how best to write figure descriptions and why doing this is
so important, please see
\url{https://www.acm.org/publications/taps/describing-figures/}.

\subsection{The ``Teaser Figure''}

A ``teaser figure'' is an image, or set of images in one figure, that
are placed after all author and affiliation information, and before
the body of the article, spanning the page. If you wish to have such a
figure in your article, place the command immediately before the
\verb|\maketitle| command:
\begin{verbatim}
  \begin{teaserfigure}
    \includegraphics[width=\textwidth]{sampleteaser}
    \caption{figure caption}
    \Description{figure description}
  \end{teaserfigure}
\end{verbatim}

\section{Citations and Bibliographies}

The use of \BibTeX\ for the preparation and formatting of one's
references is strongly recommended. Authors' names should be complete
--- use full first names (``Donald E. Knuth'') not initials
(``D. E. Knuth'') --- and the salient identifying features of a
reference should be included: title, year, volume, number, pages,
article DOI, etc.

The bibliography is included in your source document with these two
commands, placed just before the \verb|\end{document}| command:
\begin{verbatim}
  \bibliographystyle{ACM-Reference-Format}

\section{Introduction}
The primary interest of most \emph{Deep Neural Network} (DNN) researches has been the application performance (i.e., accuracy).
However, it also led to the rapid growth in the network size that require immense computational resources for execution.
In recent years, numerous schemes have appeared to mitigate the resource problem, mostly belonging to one of these categories -- \emph{network-side optimization} and \emph{hardware-side optimization}.
Network-side optimization refers to refining the architecture of a neural network to reduce computations while maintaining a comparable accuracy~\citep{mobilenetv2, dorefa}.
Hardware-side optimization often involves improving DNN execution efficiency by using optimized hardware, also known as \emph{accelerator}s~\citep{eyeriss, tpu}.
Unfortunately, effort from one side often hinders the benefits coming from the other.
For example, the main advantage of depth-wise separable convolution operation used in MobileNet~\citep{mobilenetv2} comes from its structure which uses a single channel for its operation.
However, Google's TPU~\citep{tpu}, a renowned accelerator, mainly utilizes channel-level parallelism for gaining speedup. In consequence, MobileNet results in a poor execution time on TPUs~\citep{edgetpunas}.

Co-exploration of hardware accelerator and network architecture~\citep{li2020edd, fu2021autonba, dance, abdelfattah2020best, hao2019fpgadnn, lu2019neural, yang2020coexploration} is therefore a natural direction to fulfill both goals of accuracy and hardware metrics such as latency, energy consumption and silicon chip area.
To address the large search space of the co-exploration,
\emph{differentiable co-exploration} methods~\citep{dance, li2020edd, fu2021autonba} are considered as promising approaches due to their ability to quickly explore the search space compared to its reinforcement learning based counterparts~\citep{abdelfattah2020best, hao2019fpgadnn, lu2019neural, yang2020coexploration, lin2021naas}.

Unfortunately, differentiable co-exploration has a serious drawback of being unable to deal with hard constraints that are critical in many real-world scenarios.
For instance, an important constraint of object detection system~\citep{yolo} is to meet the frame rate of the camera (e.g., 30 frames per second).
In addition, a mobile subsystem running on a limited battery often has a power budget.
Because differentiable co-exploration methods rely on a single loss function, they often fail to satisfy the constraints, and have to blindly undergo a several repetitions of hyper-parameter tuning and re-exploration.

\sloppypar{
In order to address the problem, we present \emph
{HDX\xspace}
(\underline{\textbf{H}}ard-constrained \underline{\textbf{D}}ifferentiable
e\underline{\textbf{X}}ploration),
which enables hard-constrained differentiable co-exploration of neural architecture and hardware accelerator.
}
The key concept of our proposal
is a gradient manipulation method which ensures that the solution does not drift away from meeting the constraints.
In addition to the gradients from the global loss,
we calculate the gradient from the hardware constraints, which is used to manipulate gradient of the global loss, if any constraint violations, such that i) the dot product of the two are positive (i.e., they point to a similar direction), and ii) the direction can alleviate the violation of the constraints.

To the best of our knowledge, this is the first work that considers hard constraints in a differentiable co-exploration problem.
We conduct an extensive amount of evaluation to demonstrate that HDX\xspace can 1) satisfy the hardware constraints even under tight constraints and 2) search solutions without compromising the quality.

Our contributions can be summarized as follows.
\begin{itemize}
    \item We propose HDX\xspace, a hard-constrained differentiable co-exploration method for network and accelerator in order to find valid solutions without trial-and-errors.
    \item We propose using gradient manipulation to gradually move solutions towards the constraint-satisfying region.
    \item We provide an extensive evaluation for HDX\xspace to show its constraint-meeting capability and efficiency.
\end{itemize}

\vspace{-2mm}
\section{Background and Related Work}
\vspace{-1mm}
\subsection{Neural Architecture Search}
\vspace{-1mm}
Neural Architecture Search (NAS) refers to the technique of automating the neural network design process.
To mitigate its huge cost (thousands of GPU-hours), Differentiable NAS~\citep{liu2019darts} has been proposed as an efficient alternative, which converts the problem to training a supernet that reduces the time cost by a few digits.

Regardless, optimizing solely on network performance is insufficient as they do not take hardware efficiency into account.
Some recent works~\citep{cai2019proxylessnas} that address this issue consider hardware costs by adding loss terms, and
some attempt to reduce the network size for latency constraints using simple latency models~\citep{nayman2021hardcorenas,aows}.
However, they only consider the network design, and cannot be used for co-exploration since the relation between network accuracy and hardware structure is not reflected in the model.

\subsection{DNN-Accelerator Co-exploration}
The early work on the co-exploration utilize variants of reinforcement learning, or evolutionary algorithm to leverage its simplicity~\cite{hao2019fpgadnn,lu2019neural,jiang2019accuracy,abdelfattah2020best, yang2020coexploration,lin2021naas}.
Each candidate network is trained for evaluation, while the accelerator design is analyzed for hardware efficiency.
These values create rewards used by the agent to create the next candidate solution.
However, they all inherit the same problem from RL-based NAS methods in which they require expensive training to evaluate each candidate solution.
To worsen the matter, co-exploration requires even larger network/hardware search space than searching only for networks.

In such regard, differentiable approaches were adopted to co-exploration~\citep{li2020edd}.
Auto-NBA~\citep{fu2021autonba} used a differentiable accelerator search engine to build a joint-search pipeline, and
DANCE~\citep{dance} trained auxiliary neural networks for hardware search and cost evaluation.
However, none of the above properly addresses the hard constraint problem.
In this work, we propose a holistic method of handling hard constraints on differentiable co-exploration.

\begin{comment}

\subsection{Gradient Manipulation}
Directly managing gradients \JL{let's put these into 4.3}

\citep{lopez2017gradient} -- using exemplar, the gradients for old/new tasks should be same direction (g*g' >=0)

\citep{saha2021gradient} -- (Gradient Projection Memory) Continual. apply SVD to weights, and new gradients should be orthogonal to significant components

\citep{li2021large} -- similar to dpm aircraft

\citep{dpm} -- two goals
\end{comment}

\begin{comment}
In the real-world application, there often exists strict resource bounds.
In such cases, we need to be able to find the optimal network/accelerator pair that comply to such conditions. To solve the problem of resource-aware differentiable NAS, a concurrent work ~\citep{nayman2021hardcorenas} additionally sets a hardware constraint(e.g. latency) to satisfy strictly bounded resource demand. However, it relies on a predefined lookup table for resource measurements and thus does not search for optimal hardware implementation.
\end{comment}

\section{Motivational Experiment}
\label{sec:difficulty}

\begin{figure}[t]
    \centering
    \includegraphics[width=0.95\columnwidth]{motivation.png}
    \vspace{-3.5mm}
    \caption{A motivational experiment. In each plot, we swept the value $\lambda_{Cost}$ 0.001 to 0.010.
    It is clear that the trajectory is not strictly linear to $\lambda_{cost}$ with high variations. }
    \label{fig:motivational exp}
    \vspace{-3mm}
\end{figure}

The most straightforward and na\"ive way to handle hard constraints within differentiable co-exploration would be to tune the relative weight to the hardware cost.
For example, below is the loss function used in differentiable co-exploration~\citep{dance,fu2021autonba}.
\begin{align}

    \mathcal{L}oss &= \mathcal{L}oss_{CE} + \lambda_{Cost}Cost_{HW},
    \label{eq:danceloss}
\end{align}
which is designed co-optimize accuracy and hardware cost simultaneously, and $\lambda_{Cost}$ balances the two terms\footnote{It is different from hyperparameters of typical machine learning formulation where the two terms serve toward a single objective.}.
By increasing $\lambda_{Cost}$, one can indirectly instruct the search process to consider hardware metrics more.
However, giving a larger penalty
does not directly lead to reduction in the value of a constrained metric.
\figurename~\ref{fig:motivational exp} plots how changing $\lambda_{Cost}$ in \cref{eq:danceloss} from 0.001 to 0.010 affects the latency/energy and the classification error for CIFAR-10 dataset.
Searches were done three times for each setting and plotted with the same colors with large dots for their averages.
Even though some trend is observed that depends on $\lambda_{Cost}$, inconsistency in both direction and variance of the trajectory is more dominant.

Consider a scenario where a designer wants to design a neural network-accelerator architecture pair with latency under some constraint (e.g., \SI{33.3}{\milli\second}), using the conventional co-exploration methods.
The designer would try searching with some initial $\lambda_{Cost}$ and try adjusting the value over the course of multiple searches.
However, such inconsistency between $\lambda_{Cost}$ and the latency makes it extremely difficult to obtain the adequate solution, not to mention the huge time cost of performing the search numerous times.
Despite the difficulties that lie in tackling a hard-constrained co-exploration problem,
designing an effective strategy is necessary.

\section{Hard-Constrained Co-exploration}
\subsection{Problem Definition}
The mathematical formulation of hard-constrained differentiable co-exploration is as below:
\begin{align}
\small
    \argmin_{\alpha, \beta} &(\mathcal{L}oss_{NAS} (w^*, net(\alpha)) + \lambda_{Cost} Cost_{HW}(eval(\alpha, \beta))), \notag \\
    &\textrm{s.t.}\ \ w^* = \argmin_{w} (\mathcal{L}oss_{NAS}(w, net(\alpha))), \ \ \ t\leq T,
\label{eq:object}
\end{align}
where $t$ denotes the current value of constrained metric such as latency or energy, and $T$ is the target value (e.g., 33.3 \SI{}{\milli\second} for latency).
$\alpha$ and $\beta$ denote network architecture parameters and hardware accelerator configuration, respectively. ${w}$ is the weights of the NAS supernet and ${net(\alpha)}$ is the current dominant network architecture selected.
${eval(\alpha, \beta)}$ indicates the hardware metrics evaluated for $\alpha$ and $\beta$.
The objective of co-exploration is expressed using two distinct evaluation metrics, which are neural architecture loss ($\mathcal{L}oss_{NAS}$) and hardware cost ($Cost_{HW}$) defined from the user.

\subsection{Differentiable Co-exploration Framework}
Although our main contribution is that we enable hard constraints, we explain our framework for the co-exploration since they are closely related.
\figurename~\ref{fig:HDX} illustrates the overall architecture of the proposed method, being similar to existing methods~\cite{dance, fu2021autonba}.
\figurename~\ref{fig:HDX} (a) is the network search module.
This module searches for network architecture by choosing a path from the
supernet.
The network structure is then fed to the evaluator module.

The evaluator network $eval()$ is the key to the differentiable co-exploration that enables the gradient to flow into the supernet, considering the relation between the hardware accelerator.
It is a composition of two subnetworks: a hardware generator $gen()$ and an estimator $est()$.
The hardware generator takes the neural architecture parameters as inputs and uses them to output the optimal hardware implementation ($\beta$ from \eq{object}).
It is jointly trained during the co-exploration so that the generator does not depend on certain cost function, and can adapt to the constraint.
The estimator network outputs the hardware-related metrics by taking output of the generator and the network.
It is pre-trained according to the network and the accelerator search space.
For pre-training the estimator, traditional (non-differentiable) cost estimation frameworks such as MAESTRO~\citep{maestro_toppicks2020}, Timeloop~\citep{TimeLoop}, and Accelergy~\citep{iccad_2019_accelergy} are used as ground truth.
After pre-training, the estimator is frozen during the exploration and is only used to infer the hardware cost given a network architecture.
With these, we convert \eq{object} as below:
\begin{align}
\small
    \argmin_{\alpha} (\mathcal{L}oss_{NAS} &(w^*, net(\alpha)) + \lambda_{Cost} Cost_{HW}(est(\alpha, gen(v^*, \alpha)))), \notag \\
    \textrm{s.t.}\ \ w^* &= \argmin_{w} (\mathcal{L}oss_{NAS}(w, net(\alpha))), \notag \\
                 \ \ v^* &= \argmin_{v} (Cost_{HW}(est(\alpha, gen(v, \alpha)))),
\label{eq:cosearch}
\end{align}
where $v$ is the weights for the hardware generator.

\begin{comment}

The generator is also modeled as a five-layer perceptron.
However, unlike existing methods, we do not pre-train the generator.
This has two benefits: First, the generator does not depend on certain cost function. A pre-trained generator would be useless if different cost function is required.
Second, it can adapt to the constraint.
As the manipulated gradient from the hard-constraint is back-propagated, the generator learns to create accelerators that comply with the constraint on given neural network architecture.
Thus, we choose to randomly init the generator and train it simultaneously with the network search module.

\end{comment}

\begin{figure}[t]
    \centering
    \includegraphics[width=.4\textwidth]{figs/DAC_version.drawio.png}
    \vspace{-3mm}
    \caption{Overall structure of HDX.

    }\vspace{-4mm}
    \label{fig:HDX}
\end{figure}

\subsection{Enabling Hard-Constraints with Gradient Manipulation}
In addition to the differentiable co-exploration methodology, we suggest the novel idea of gradient manipulation as an effective solution to the hard constraint problem.
Direct manipulation of gradients is a strategy often used in achieving multiple goals,
such as in continual learning~\citep{saha2021gradient} or differential equations~\citep{dpm}.
In this paper, we present a solution to apply gradient manipulation to the co-exploration problem in the interest of satisfying hard constraints.

The diagrams on \figurename~\ref{fig:HDX} (b) and (c) show a high-level abstraction of our gradient manipulation method.
The main idea is to artificially generate a force that can push the gradient in the direction that \emph{agree}s with the constraint.
The conditions under which the method is applied to compute the new gradient $g$ are defined as below:
\begin{equation}
    g =
        \begin{cases}
            g_{\mathcal{L}oss} & \text{, if } t \leq T \\
            &\text{ or } t > T \wedge g_{\mathcal{L}oss} \cdot g_{\mathcal{C}onst} \geq \text{0,} \\

            m_{\alpha} + g_{\mathcal{L}oss} &  \text{, otherwise} \\
        \end{cases}
\end{equation}
\begin{equation}
    g_{\mathcal{C}onst} = \frac{\partial \max(t - T ,0)}{\partial \alpha}.
\end{equation}

In the above equation, $g_{\mathcal{L}oss}$ is the original gradient from the global loss function defined as
\begin{equation}
\label{eq:global_loss}
    \mathcal{L}oss = \mathcal{L}oss_{NAS} + \lambda_{Cost}\cdot Cost_{HW},
\end{equation}
as in \eq{cosearch}, and $g_{\mathcal{C}onst}$ is the gradient of constraint loss that we define as: $\mathcal{C}onst=max(t - T ,0)$.
\JL{I moved the def. of t and T to section 3}
Note that $t$ is a function of $\alpha$, and thus can be backpropagated to find the gradient with respect to $\alpha$.
In an ideal case where the $t$ $\leq$ $T$, the constraint is already met so we do nothing.
In the unfortunate case when the constraint is still not met, we calculate for the dot product of the two gradients to determine the agreement in their directions.
If $g_{\mathcal{L}oss} \cdot g_{\mathcal{C}onst} \text{$\geq$ 0}$ (i.e., the angle between two gradients is less than 90\textdegree), it means gradient descent update will contribute towards satisfying the constraint.
Thus it is interpreted as an agreement in direction and the same $g_{\mathcal{L}oss}$ is used unmodified.
\figurename~\ref{fig:HDX} (b) depicts this scenario.
However, if they disagree as illustrated in \figurename~\ref{fig:HDX} (c) (i.e., $g_{\mathcal{L}oss} \cdot g_{\mathcal{C}onst} \text{$<$ 0}$), we force the gradient to shift its direction by $m_{\alpha}$, which is obtained from $(m_{\alpha} + g_{\mathcal{L}oss}) \cdot g_{\mathcal{C}onst} \text{$\geq$ 0}$ to guarantee decrease in target cost after gradient descent.
It can be reformulated as $m_{\alpha} \cdot g_{\mathcal{C}onst} + g_{\mathcal{L}oss} \cdot g_{\mathcal{C}onst} = \delta$ where $\delta \text{$\geq$ 0}$ is a small value for ensuring gradual movement towards satisfying the constraint.

For updating $\alpha$ and $w$,
we solve for optimal $m_{\alpha}$ with respect to $\alpha$, which are the parameters for the network architecture.
To minimize the effect of $m_{\alpha}$ on $g_{\mathcal{L}oss}$, we use a pseudoinverse-based solution that is known to minimize the size of $||m_{\alpha}||_2^2$ as below:
\begin{equation}
\label{eq:optimal_m}
    m_\alpha^* = \frac{-(g_{\mathcal{L}oss} \cdot g_{\mathcal{C}onst})  + \delta}{||g_{\mathcal{C}onst}||_2^2} g_{\mathcal{C}onst}.
\end{equation}
In order to control the magnitude of the pull, we use a small multiplying factor $p>0$ on $\delta$. The policy for updating $\delta$ using $p$ is as follows: Some initial value $\delta_{0}$ exists for $\delta$. If the target metric fails to meet the constraint, $\delta$ is multiplied by $1+p$ to strengthen the pull ($\delta^{'} = (1+p)\delta$). In the other case when the constraint is satisfied, $\delta$ is reset to its initial value ($\delta^{'} = \delta_{0}$).

Note that we also train $v$, weights for the hardware generator using gradient descent.
Thus we compute for $m_v^*$ in the same manner, but use $g_{\mathcal{C}ost_{HW}}$ in place of $g_{\mathcal{L}oss}$ for updating the generator.

Although a single constraint is already a challenging target, our method can be further generalized to accommodate multiple constraints.
Now the gradient is modified only in the direction of individual constraints that do not comply. We provide a more generalized formulation:
\begin{equation}
    g =
        \begin{cases}
            g_{\mathcal{L}oss} & \text{, if } \bigwedge_{i=1}^{n}(t_{i} \leq T_{i}) \\
            &\text{ or } \bigvee_{i=1}^{n}(t_i > T_{i}) \wedge g_{\mathcal{L}oss} \cdot g_{\mathcal{C}onst} \geq \text{0,} \\
            m_{\alpha} + g_{\mathcal{L}oss} &  \text{, otherwise}
        \end{cases}
\end{equation}
\begin{equation}
    g_{\mathcal{C}onst} = \frac{\partial \sum_{i=1}^{n}\max(t_{i} - T_{i} ,0)}{\partial \alpha}.
\end{equation}

\subsection{Implementation Details}
\textbf{\ \ \ \ \ Hardware cost function.}
In this work, we choose the inference latency, energy, and the chip area as the widely used hardware metrics.
Considering all of them, a commonly used cost function is multiplying them (i.e., EDP, EDAP) as in \cite{dance, fu2021autonba}.
However, we found that the energy is usually easier to optimize for, and using such cost function unfairly favors energy-oriented designs.
Therefore, we use a balanced weighted sum for the cost function as below.
\begin{equation}
\small
    Cost_{HW} = C_EEnergy + C_LLatency + C_AArea.
\vspace{-1mm}
\label{eq:cost_hw}
\end{equation}

\textbf{Estimator and Generator Network.} Following \cite{dance}, we model both the estimator and generator with five-layer Multi-Layer Perceptron (MLP) with residual connections.
To train the estimator, we first build a dataset by randomly sampling 10.8M network-accelerator pairs ($2.95\mathrm{e}{-9}$ \% of the total search space) from our search space which are evaluated on hardware metrics using Timeloop~\citep{TimeLoop} and Accelergy~\citep{iccad_2019_accelergy}.
Using this dataset, the estimator is trained for 200 epochs with the batch size of 256. The weight update is done using Adam optimizer with the learning rate of 1e-4.
The accuracy of the estimator was over 99\% for all metrics, being powerful enough as an engine for co-exploration.
The generator is randomly initialized and jointly trained with the NAS supernet.
As the manipulated gradient from the hard-constraint is back-propagated, the generator learns to create accelerators that comply with the constraint on given neural network architecture.

\textbf{Search Space.}
We use ProxylessNAS \citep{cai2019proxylessnas} as a NAS backbone with path sampling to train $\alpha$.
It consists of multiple settings of MBConv operation with kernel size \{3, 5, 7\} and expand ratio \{3, 6\}.
The total number of layers is 18 and 21 for CIFAR-10~\cite{cifar} and ImageNet~\cite{imagenet} dataset, respectively.
However, our method is orthogonal to the NAS implementation and has the flexibility to choose from any differentiable NAS algorithms, such as DARTS~\cite{liu2019darts} or OFA~\cite{ofa}.

We use Eyeriss~\citep{eyeriss} as the accelerator's backbone architecture.
It is composed of a two-dimensional Processing Element~(PE) array where
each PEs has a Multiply-Accumulate~(MAC) unit attached to a register file.
Therefore, hardware accelerator design space comprises PE array size from 12$\times$8 to 20$\times$24, register file size per PE from 16B to 256B.
In addition, the search space includes dataflow of Weight-Stationary (WS) similar to \citep{tpu}, Output-Stationary (OS) similar to \citep{shidiannao} and Row-Stationary (RS) similar to \citep{eyeriss}.

\section{Experiments}
\subsection{Experimental Environment}
We have conducted experiments on HDX\xspace using CIFAR-10~\citep{cifar} and ImageNet~\citep{imagenet} dataset.
For all the hardware metrics (latency, energy, and chip area) reported, we have used the direct evaluation on the designed hardware from Timeloop~\cite{TimeLoop} and Accelergy~\cite{iccad_2019_accelergy} instead of the values outputted by the estimator to avoid any possible error in the learned model.
Evaluation of network accuracy is done by training the final network architecture, which we train from scratch for 300 epochs using the batch size of 64.
We use SGD optimizer with Nesterov momentum \citep{nesterov}, and cosine learning rate scheduling with 0.008 as its initial value, while weight decay term and momentum is 1e-3 and 0.9 respectively. Augmentation for the train data is adopted from AutoAugment \citep{Cubuk2019AutoAugmentLA}, on both dataset.

\subsection{Comparison with Existing Methods}
\label{sec:comparison}
\tablename~\ref{tbl:comparison} lists the existing differentiable co-exploration methods in comparison with HDX\xspace.
We compare the following methods:
\begin{itemize}[leftmargin=*]
    \item \textbf{NAS $\rightarrow$ HW}: A plain differentiable NAS~\cite{cai2019proxylessnas} only, followed by an exhaustive hardware search using Timeloop~\cite{TimeLoop}.

    \item \textbf{Auto-NBA~\cite{fu2021autonba}}: A differentiable co-exploration method that directly searches for hardware parameters using gradient descent, where the relation between hardware and the DNN is expressed as a lookup table.

    \item \textbf{DANCE~\cite{dance}}: State-of-the-art differentiable co-exploration method without hard constraints
    where the generator and estimator are modeled as neural networks.

    \item \textbf{DANCE + Soft Constraint}: To represent a reasonable approach for considering constraints with existing solutions, we have added a soft-constraint term $\lambda_{Soft} \cdot max(t/T-1,0)$ as in \citep{hu2020tf}.

    \item \textbf{HDX\xspace}: The proposed method with $p=1\mathrm{e}{-2}$.

\end{itemize}
As displayed in \tablename~\ref{tbl:comparison}, HDX\xspace is the only method that considers hard constraints with differentiable co-exploration.

For a quantitative comparison, we devised an algorithm for finding constrained solution using co-exploration without hard-constraints.
Because a constrained metric (e.g., latency) being too low often means an inefficient solution (in terms of other metrics (e.g., accuracy and energy), we set the criteria of having a solution of 50\%\textasciitilde 100\% of the target constraint.
A rough sketch of the algorithm similar to binary search is given below:
\begin{enumerate}
    \item Choose a control parameter ($\lambda_{Soft}$ and $\lambda_{Cost}$) that indirectly affects the metric under constraint (e.g., latency).
    \item Perform a search using the default control parameter value.
    \item Perform searches by doubling the control parameter each step until the metric is under the constraint.
    \item If the metric is under 50\% of the target value, shrink the control parameter in a binary search manner.
\end{enumerate}
Note that the problem cannot exactly be solved by binary search, because of huge per-search variations and non-linear relations as demonstrated in Section~\ref{sec:difficulty}.
In the actual implementation, more features are added to deal with corner cases and to avoid falling into wrong parameter region (which can happen from per-search variations).
We ran the algorithm 100 times and report the average.
We also report the average error as a proxy to the solution quality.

As presented in \tablename~\ref{tbl:comparison}, all baselines require multiple searches to find constraint-satisfying solutions.
For DANCE, it takes 6.6 searches with 12.2 GPU-hours on average and 4.9 searches and 9.1 GPU-hours on even with soft constraints.
On the other hand, HDX\xspace always searches for constraint-satisfying solutions in a single search.
Furthermore, the number of searches for baselines strongly depend on the choice of the default value of control parameter.
Guessing a right initial parameter is difficult, and could result in even larger repetition cost.
This advocates the need for HDX\xspace.

\begin{table}[t]
\vspace{-1mm}
    \centering

     \resizebox{\columnwidth}{!}
    {
    \begin{tabular}{lcccccccc}
     \toprule
  \multirow{2}{*}{Method} &  \multirow{2}{*}{\makecell{Hard \\ Constraint}} &  \multirow{2}{*}{\makecell{NN-HW \\Relation}} & \multicolumn{3}{c}{Search with 60 FPS Constraint}  \\
  \cmidrule(lr){4-6}
                          &                                   &                                  & \#Searches  & Cost*  & Avg. Err. (\%) \\
    \midrule

        NAS~\cite{cai2019proxylessnas} $\rightarrow$ HW search & \xmark & \xmark & 5.0 & 10.9h & 7.26 \\
        Auto-NBA~\cite{fu2021autonba} & \xmark & \cmark & 6.8 & 10.2h  & 5.67 \\
        DANCE~\cite{dance} & \xmark & \cmark & 6.6 & 12.2h & 5.32 \\

        DANCE + Soft const.~\cite{hu2020tf} & \xmark & \cmark & 4.9 & 9.1h  & 5.36 \\

        \midrule
       \textbf{ HDX\xspace (Proposed)} & \cmark & \cmark &  \textbf{1} & \textbf{2.0h} &  \textbf{4.65} \\
        \bottomrule
        \multicolumn{6}{r}{*GPU-hours}

    \end{tabular}
    }\\

\caption{Comparison of Differentiable Co-explorations}
\label{tbl:comparison}
\vspace{-10mm}
\end{table}

\subsection{Co-exploration Results}
\label{sec:results}

\figurename~\ref{fig:masterplot} plots the co-exploration experimental results from multiple techniques on CIFAR-10 dataset.
In the experiments, we have set two different constraints for the latency: 16.6\SI{}{\milli\second} (60 fps) and 33.3\SI{}{\milli\second} (30 fps).
For all co-exploration methods, we obtain five solutions by varying $\lambda_{Cost}$ from 0.001 to 0.005 to fairly compare the various design points obtained by each approach.
For $NAS\rightarrow HW$, we obtain 10 solutions of various range for reference, because directly applying $\lambda_{Cost}$ is infeasible.
For DANCE and Auto-NBA, the black markers are unconstrained, and colored markers are obtained with soft constraint of the corresponding colors.

\input{figs/master_three}

\input{figs/table_quality}

In all experiments, we have used $C_E=2.9$, $C_L=6.2$, and $C_A=1.0$ from \eq{cost_hw}, which makes the difference scale of each metric approximately the same to make a fair comparison.
For the NAS only method, $Cost_{HW}$ was used only for the hardware design phase.

\figurename~\ref{fig:masterplot} (left) and (mid) show the relation between error and latency.
The colored horizontal bars represent the two latency targets we applied.
It can be easily seen that all solutions found by HDX\xspace satisfy the given hard constraints regardless of the value of $\lambda_{Cost}$.
Furthermore, all solutions have the latency right below the constraint, showing that the solutions did not over-optimize for the constrained metric (latency).
DANCE~\citep{dance} and Auto-NBA~\cite{fu2021autonba} were able to exploit the trade-off between hardware metrics and accuracy, but has no control over meeting the constraint.
Even with soft-constraint terms, they mostly failed to obtain in-constraint solutions.
Auto-NBA at a glance seems to be slightly better at meeting the constraints, but it is because its baseline method favors hardware-efficient solutions over high-accuracy ones, not because of its ability to meet the constraint, exemplified by the fact that there is no solution with high accuracy, or latency under \SI{16.6}{\milli\second}.

\subsection{Solution Quality Found by HDX\xspace}
\label{sec:quality}
In this subsection, we demonstrate that HDX\xspace can 1) handle constraints from all three metrics (latency, energy, and chip area), 2) handle multiple constraints, and 3) obtain solutions of good overall quality.
\figurename~\ref{fig:masterplot} (right) plots $Cost_{HW}$ and error together, which allows evaluating quality of the solutions in terms of Pareto-optimality.
Because \figurename~\ref{fig:masterplot} (left) and (mid) overlook the other metrics, comparing the $Cost_{HW}$ together is required to be fair.

From the plot, it is clear that
quality of solutions from HDX\xspace is better than the NAS$\rightarrow$HW method, and has no degradation from the existing co-exploration methods.
In fact, the tightly constrained (16.6\SI{}{\milli\second}) solutions even find better solution than those of the existing solutions in terms of Pareto-optimality.

To further study the quality of the solutions found by HDX\xspace, we have conducted another set of experiments.
We selected a few solutions found from DANCE method as `Anchor' solutions and listed them in \tablename~\ref{tab:quality}.
From those, we chose either one or all three of the hardware metrics to be fixed as the hard constraint, and performed co-explorations using HDX\xspace.
Because it is guaranteed that such solution exists, a good method should be able to find a solution meeting the constraint, of at least a similar quality.
As in the Section~\ref{sec:results}, all of the 8 cases we have examined succeeded in finding a valid solution.
Furthermore, all the solutions show similar global loss values from the anchor solutions as shown in the rightmost column.

\vspace{-1mm}
\subsection{Results from ImageNet Dataset}
\vspace{-1mm}

\begin{table}[b]
\vspace{-3mm}
    \centering
    \scriptsize
    \caption{Experimental Results for ImageNet}
\vspace{-3mm}
    \label{tab:imgnet}
    \begin{tabular}{lccccc}
    \toprule

Method	&	in-const?	&	Lat. (ms)	&	Error (\%)	&	CostHW	&	Loss	\\
\midrule
\multirow{2}{*}{NAS$\rightarrow$HW}	&	\xmark	&	242.92	&	24.84	&	46.29	&	1.99	\\
	&	\xmark	&	135.39	&	28.83	&	24.26	&	2.17	\\
\midrule
\multirow{2}{*}{DANCE}	&	\xmark	&	165.98	&	25.46	&	29.37	&	2.04	\\
	&	\cmark	&	121.58	&	25.28	&	25.92	&	2.09	\\
\midrule
\multirow{2}{*}{DANCE+Soft Const.}	&	\xmark	&	188.69	&	25.09	&	33.14	&	1.99	\\

	&	\cmark	&	105.65	&	26.37	&	25.58	&	2.08	\\
\midrule

\multirow{2}{*}{\textbf{HDX (Proposed)}}	&	\cmark	&	92.06	&	25.01	&	24.48	&	1.98	\\

	&	\cmark	&	112.11	&	25.20	&	22.63	&	2.00	\\

\bottomrule
    \end{tabular}
\end{table}

\input{figs/sense}

\tablename~\ref{tab:imgnet} shows the co-exploration results from ImageNet dataset~\citep{imagenet}, under 125 ms constraint.
As displayed in the table, HDX\xspace always succeeded in finding a solution within constraint where the others often failed to satisfy.
Furthermore, the Top-1 error and the global loss shows that the quality of the solution found by HDX\xspace is not compromised at all, compared to DANCE or its variant.

\vspace{-1mm}
\subsection{Sensitivity Study on Pulling Magnitude}
\vspace{-1mm}

In HDX\xspace, the only hyperparameter is $p$ that controls the pulling magnitude.
\figurename~\ref{fig:sense} illustrates how the global loss and latency changes over latency-constrained (33.3 \SI{}{\milli\second}) explorations, with varying $p$ of 1e-2, 7e-3, and 4e-3.

Regardless of the value of $p$, the curve for the constrained value shows a similar trend.
At the beginning, the global loss becomes mainly optimized, while the latency stays steady.
During this phase the pulling magnitude $\delta$ (See \eq{optimal_m}) is still growing, and is not strong enough to make meaningful changes.
At certain point,
$\delta$ becomes strong enough to pull the solution towards lowering latency.
When the latency satisfies the constraint,
global loss starts to decrease while maintaining the latency.
There is no significant discrepancy between the final solution in the global loss and the latency, which shows that HDX\xspace is insensitive to the hyperparameter $p$.

\subsection{Analysis on the Searched Solutions}
\cref{fig:nn_hw_pair} visualizes the network and accelerator searched for 60 fps (a) and 30 fps (b) constraints.
For the found design pair (a), the design contains relatively smaller kernels, more layers, and a powerful accelerator.
To meet a tight constraint while maintaining accuracy, the network has small kernels, mainly of $3\times3$.
Using smaller kernels quadratically reduces the number of multiplications.
Therefore, decreasing the kernel size and increasing number of layers is a good choice for reducing inference latency.
Looking at the accelerator design, it has relatively large PE array (16$\times16$) to achieve low latency.
It takes weight stationary (WS) dataflow, which is known to have low latency.
In addition, there are some kernels with high channel expand ratio in the network.
WS exploits channel parallelism for fast execution, and thus has advantage over the found network.

On the other hand, in the design for 30 fps (b), the design settles at a solution that can optimize the energy consumption while satisfying the constraint.
The design uses larger kernels in the network and row stationary (RS) dataflow in the accelerator.
RS is known to have good energy efficiency~\cite{eyeriss}, and exploits parallelism from spatial dimensions of kernel and the activation.
Thus, having larger kernels have advantages on RS dataflow.
To reduce the energy consumption, the design has fewer PEs (12$\times$8), larger RFs to save off-chip access energy, and fewer layers in the network.

\vspace{-1mm}
\section{Conclusion}
\vspace{-1mm}
In this paper, we proposed HDX\xspace, a hard-constrained differentiable co-exploration method.
By conditionally applying gradient manipulation that moves the solution towards meeting the constraints,
hard constraints can be reliably satisfied with high-quality solutions.
We believe this proposal would ease the development of DNN based systems by a significant amount.

\begin{figure}
\begin{subfigure}[t]{0.4\columnwidth}
\includegraphics[width=\textwidth, trim={.3cm .1cm 1cm .1cm}, clip=true]{figs/nn_hw_60fps.pdf}
\vspace{-6.5mm}
\caption{}\label{fig:nn_hw_60fps}
\end{subfigure}
\hspace{3mm}
\begin{subfigure}[t]{0.4\columnwidth}
\includegraphics[width=\textwidth, trim={.3cm .1cm 1cm .1cm}, clip=true]{figs/nn_hw_30fps.pdf}
\vspace{-6.5mm}
\caption{}\label{fig:nn_hw_60fps}
\end{subfigure}
\vspace{-3mm}
\caption{Searched network and accelerator for 60 fps and 30 fps constraints. ($m$,$n$) refers MBConv block with $m\times m$ kernel and $n$ expand ratio.}
\vspace{-5mm}
\label{fig:nn_hw_pair}
\end{figure}

\begin{acks}
This work has been supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (2022R1C1C1008131,
2022R1C1C1011307),
and
Institute of Information \& communications Technology Planning \& Evaluation
(IITP) grant funded by the Korea government (MSIT)
(2020-0-01361,
Artificial Intelligence Graduate School Program (Yonsei University
).
\end{acks}

\bibliographystyle{ACM-Reference-Format}

\section{Introduction}
ACM's consolidated article template, introduced in 2017, provides a
consistent \LaTeX\ style for use across ACM publications, and
incorporates accessibility and metadata-extraction functionality
necessary for future Digital Library endeavors. Numerous ACM and
SIG-specific \LaTeX\ templates have been examined, and their unique
features incorporated into this single new template.

If you are new to publishing with ACM, this document is a valuable
guide to the process of preparing your work for publication. If you
have published with ACM before, this document provides insight and
instruction into more recent changes to the article template.

The ``\verb|acmart|'' document class can be used to prepare articles
for any ACM publication --- conference or journal, and for any stage
of publication, from review to final ``camera-ready'' copy, to the
author's own version, with {\itshape very} few changes to the source.

\section{Template Overview}
As noted in the introduction, the ``\verb|acmart|'' document class can
be used to prepare many different kinds of documentation --- a
double-blind initial submission of a full-length technical paper, a
two-page SIGGRAPH Emerging Technologies abstract, a ``camera-ready''
journal article, a SIGCHI Extended Abstract, and more --- all by
selecting the appropriate {\itshape template style} and {\itshape
  template parameters}.

This document will explain the major features of the document
class. For further information, the {\itshape \LaTeX\ User's Guide} is
available from
\url{https://www.acm.org/publications/proceedings-template}.

\subsection{Template Styles}

The primary parameter given to the ``\verb|acmart|'' document class is
the {\itshape template style} which corresponds to the kind of publication
or SIG publishing the work. This parameter is enclosed in square
brackets and is a part of the {\verb|documentclass|} command:
\begin{verbatim}
  \documentclass[STYLE]{acmart}
\end{verbatim}

Journals use one of three template styles. All but three ACM journals
use the {\verb|acmsmall|} template style:
\begin{itemize}
\item {\texttt{acmsmall}}: The default journal template style.
\item {\texttt{acmlarge}}: Used by JOCCH and TAP.
\item {\texttt{acmtog}}: Used by TOG.
\end{itemize}

The majority of conference proceedings documentation will use the {\verb|acmconf|} template style.
\begin{itemize}
\item {\texttt{acmconf}}: The default proceedings template style.
\item{\texttt{sigchi}}: Used for SIGCHI conference articles.
\item{\texttt{sigchi-a}}: Used for SIGCHI ``Extended Abstract'' articles.
\item{\texttt{sigplan}}: Used for SIGPLAN conference articles.
\end{itemize}

\subsection{Template Parameters}

In addition to specifying the {\itshape template style} to be used in
formatting your work, there are a number of {\itshape template parameters}
which modify some part of the applied template style. A complete list
of these parameters can be found in the {\itshape \LaTeX\ User's Guide.}

Frequently-used parameters, or combinations of parameters, include:
\begin{itemize}
\item {\texttt{anonymous,review}}: Suitable for a ``double-blind''
  conference submission. Anonymizes the work and includes line
  numbers. Use with the \texttt{\acmSubmissionID} command to print the
  submission's unique ID on each page of the work.
\item{\texttt{authorversion}}: Produces a version of the work suitable
  for posting by the author.
\item{\texttt{screen}}: Produces colored hyperlinks.
\end{itemize}

This document uses the following string as the first command in the
source file:
\begin{verbatim}
\documentclass[sigconf]{acmart}
\end{verbatim}

\section{Modifications}

Modifying the template --- including but not limited to: adjusting
margins, typeface sizes, line spacing, paragraph and list definitions,
and the use of the \verb|\vspace| command to manually adjust the
vertical spacing between elements of your work --- is not allowed.

{\bfseries Your document will be returned to you for revision if
  modifications are discovered.}

\section{Typefaces}

The ``\verb|acmart|'' document class requires the use of the
``Libertine'' typeface family. Your \TeX\ installation should include
this set of packages. Please do not substitute other typefaces. The
``\verb|lmodern|'' and ``\verb|ltimes|'' packages should not be used,
as they will override the built-in typeface families.

\section{Title Information}

The title of your work should use capital letters appropriately -
\url{https://capitalizemytitle.com/} has useful rules for
capitalization. Use the {\verb|title|} command to define the title of
your work. If your work has a subtitle, define it with the
{\verb|subtitle|} command.  Do not insert line breaks in your title.

If your title is lengthy, you must define a short version to be used
in the page headers, to prevent overlapping text. The \verb|title|
command has a ``short title'' parameter:
\begin{verbatim}
  \title[short title]{full title}
\end{verbatim}

\section{Authors and Affiliations}

Each author must be defined separately for accurate metadata
identification.  As an exception, multiple authors may share one
affiliation. Authors' names should not be abbreviated; use full first
names wherever possible. Include authors' e-mail addresses whenever
possible.

Grouping authors' names or e-mail addresses, or providing an ``e-mail
alias,'' as shown below, is not acceptable:
\begin{verbatim}
  \author{Brooke Aster, David Mehldau}
  \email{dave,judy,steve@university.edu}
  \email{firstname.lastname@phillips.org}
\end{verbatim}

The \verb|authornote| and \verb|authornotemark| commands allow a note
to apply to multiple authors --- for example, if the first two authors
of an article contributed equally to the work.

If your author list is lengthy, you must define a shortened version of
the list of authors to be used in the page headers, to prevent
overlapping text. The following command should be placed just after
the last \verb|\author{}| definition:
\begin{verbatim}
  \renewcommand{\shortauthors}{McCartney, et al.}
\end{verbatim}
Omitting this command will force the use of a concatenated list of all
of the authors' names, which may result in overlapping text in the
page headers.

The article template's documentation, available at
\url{https://www.acm.org/publications/proceedings-template}, has a
complete explanation of these commands and tips for their effective
use.

Note that authors' addresses are mandatory for journal articles.

\section{Rights Information}

Authors of any work published by ACM will need to complete a rights
form. Depending on the kind of work, and the rights management choice
made by the author, this may be copyright transfer, permission,
license, or an OA (open access) agreement.

Regardless of the rights management choice, the author will receive a
copy of the completed rights form once it has been submitted. This
form contains \LaTeX\ commands that must be copied into the source
document. When the document source is compiled, these commands and
their parameters add formatted text to several areas of the final
document:
\begin{itemize}
\item the ``ACM Reference Format'' text on the first page.
\item the ``rights management'' text on the first page.
\item the conference information in the page header(s).
\end{itemize}

Rights information is unique to the work; if you are preparing several
works for an event, make sure to use the correct set of commands with
each of the works.

The ACM Reference Format text is required for all articles over one
page in length, and is optional for one-page articles (abstracts).

\section{CCS Concepts and User-Defined Keywords}

Two elements of the ``acmart'' document class provide powerful
taxonomic tools for you to help readers find your work in an online
search.

The ACM Computing Classification System ---
\url{https://www.acm.org/publications/class-2012} --- is a set of
classifiers and concepts that describe the computing
discipline. Authors can select entries from this classification
system, via \url{https://dl.acm.org/ccs/ccs.cfm}, and generate the
commands to be included in the \LaTeX\ source.

User-defined keywords are a comma-separated list of words and phrases
of the authors' choosing, providing a more flexible way of describing
the research being presented.

CCS concepts and user-defined keywords are required for for all
articles over two pages in length, and are optional for one- and
two-page articles (or abstracts).

\section{Sectioning Commands}

Your work should use standard \LaTeX\ sectioning commands:
\verb|section|, \verb|subsection|, \verb|subsubsection|, and
\verb|paragraph|. They should be numbered; do not remove the numbering
from the commands.

Simulating a sectioning command by setting the first word or words of
a paragraph in boldface or italicized text is {\bfseries not allowed.}

\section{Tables}

The ``\verb|acmart|'' document class includes the ``\verb|booktabs|''
package --- \url{https://ctan.org/pkg/booktabs} --- for preparing
high-quality tables.

Table captions are placed {\itshape above} the table.

Because tables cannot be split across pages, the best placement for
them is typically the top of the page nearest their initial cite.  To
ensure this proper ``floating'' placement of tables, use the
environment \textbf{table} to enclose the table's contents and the
table caption.  The contents of the table itself must go in the
\textbf{tabular} environment, to be aligned properly in rows and
columns, with the desired horizontal and vertical rules.  Again,
detailed instructions on \textbf{tabular} material are found in the
\textit{\LaTeX\ User's Guide}.

Immediately following this sentence is the point at which
Table~\ref{tab:freq} is included in the input file; compare the
placement of the table here with the table in the printed output of
this document.

\begin{table}
  \caption{Frequency of Special Characters}
  \label{tab:freq}
  \begin{tabular}{ccl}
    \toprule
    Non-English or Math&Frequency&Comments\\
    \midrule
    \O & 1 in 1,000& For Swedish names\\
    $\pi$ & 1 in 5& Common in math\\
    \$ & 4 in 5 & Used in business\\
    $\Psi^2_1$ & 1 in 40,000& Unexplained usage\\
  \bottomrule
\end{tabular}
\end{table}

To set a wider table, which takes up the whole width of the page's
live area, use the environment \textbf{table*} to enclose the table's
contents and the table caption.  As with a single-column table, this
wide table will ``float'' to a location deemed more
desirable. Immediately following this sentence is the point at which
Table~\ref{tab:commands} is included in the input file; again, it is
instructive to compare the placement of the table here with the table
in the printed output of this document.

\begin{table*}
  \caption{Some Typical Commands}
  \label{tab:commands}
  \begin{tabular}{ccl}
    \toprule
    Command &A Number & Comments\\
    \midrule
    \texttt{{\char'134}author} & 100& Author \\
    \texttt{{\char'134}table}& 300 & For tables\\
    \texttt{{\char'134}table*}& 400& For wider tables\\
    \bottomrule
  \end{tabular}
\end{table*}

Always use midrule to separate table header rows from data rows, and
use it only for this purpose. This enables assistive technologies to
recognise table headers and support their users in navigating tables
more easily.

\section{Math Equations}
You may want to display math equations in three distinct styles:
inline, numbered or non-numbered display.  Each of the three are
discussed in the next sections.

\subsection{Inline (In-text) Equations}
A formula that appears in the running text is called an inline or
in-text formula.  It is produced by the \textbf{math} environment,
which can be invoked with the usual
\texttt{{\char'134}begin\,\ldots{\char'134}end} construction or with
the short form \texttt{\$\,\ldots\$}. You can use any of the symbols
and structures, from $\alpha$ to $\omega$, available in
\LaTeX~\cite{Lamport:LaTeX}; this section will simply show a few
examples of in-text equations in context. Notice how this equation:
\begin{math}
  \lim_{n\rightarrow \infty}x=0
\end{math},
set here in in-line math style, looks slightly different when
set in display style.  (See next section).

\subsection{Display Equations}
A numbered display equation---one set off by vertical space from the
text and centered horizontally---is produced by the \textbf{equation}
environment. An unnumbered display equation is produced by the
\textbf{displaymath} environment.

Again, in either environment, you can use any of the symbols and
structures available in \LaTeX\@; this section will just give a couple
of examples of display equations in context.  First, consider the
equation, shown as an inline equation above:
\begin{equation}
  \lim_{n\rightarrow \infty}x=0
\end{equation}
Notice how it is formatted somewhat differently in
the \textbf{displaymath}
environment.  Now, we'll enter an unnumbered equation:
\begin{displaymath}
  \sum_{i=0}^{\infty} x + 1
\end{displaymath}
and follow it with another numbered equation:
\begin{equation}
  \sum_{i=0}^{\infty}x_i=\int_{0}^{\pi+2} f
\end{equation}
just to demonstrate \LaTeX's able handling of numbering.

\section{Figures}

The ``\verb|figure|'' environment should be used for figures. One or
more images can be placed within a figure. If your figure contains
third-party material, you must clearly identify it as such, as shown
in the example below.
\begin{figure}[h]
  \centering
  \includegraphics[width=\linewidth]{sample-franklin}
  \caption{1907 Franklin Model D roadster. Photograph by Harris \&
    Ewing, Inc. [Public domain], via Wikimedia
    Commons. (\url{https://goo.gl/VLCRBB}).}
  \Description{A woman and a girl in white dresses sit in an open car.}
\end{figure}

Your figures should contain a caption which describes the figure to
the reader.

Figure captions are placed {\itshape below} the figure.

Every figure should also have a figure description unless it is purely
decorative. These descriptions convey what’s in the image to someone
who cannot see it. They are also used by search engine crawlers for
indexing images, and when images cannot be loaded.

A figure description must be unformatted plain text less than 2000
characters long (including spaces).  {\bfseries Figure descriptions
  should not repeat the figure caption – their purpose is to capture
  important information that is not already provided in the caption or
  the main text of the paper.} For figures that convey important and
complex new information, a short text description may not be
adequate. More complex alternative descriptions can be placed in an
appendix and referenced in a short figure description. For example,
provide a data table capturing the information in a bar chart, or a
structured list representing a graph.  For additional information
regarding how best to write figure descriptions and why doing this is
so important, please see
\url{https://www.acm.org/publications/taps/describing-figures/}.

\subsection{The ``Teaser Figure''}

A ``teaser figure'' is an image, or set of images in one figure, that
are placed after all author and affiliation information, and before
the body of the article, spanning the page. If you wish to have such a
figure in your article, place the command immediately before the
\verb|\maketitle| command:
\begin{verbatim}
  \begin{teaserfigure}
    \includegraphics[width=\textwidth]{sampleteaser}
    \caption{figure caption}
    \Description{figure description}
  \end{teaserfigure}
\end{verbatim}

\section{Citations and Bibliographies}

The use of \BibTeX\ for the preparation and formatting of one's
references is strongly recommended. Authors' names should be complete
--- use full first names (``Donald E. Knuth'') not initials
(``D. E. Knuth'') --- and the salient identifying features of a
reference should be included: title, year, volume, number, pages,
article DOI, etc.

The bibliography is included in your source document with these two
commands, placed just before the \verb|\end{document}| command:
\begin{verbatim}
  \bibliographystyle{ACM-Reference-Format}