# Inference Acceleration with Adaptive Distributed DNN Partition over Dynamic Video Stream
## 3 Preliminary
### Optimization Model  
A total of \(m\) devices perform the same task with an inference model of \(n\) layers for that task. The terminal device \(D_{i}\) has a task \(Task_{i}\) with task size \(P_{i}\). The total inference time \(T_{total}\sim O(T_{computation}+T_{communication})\) of the model for the collaborative completion of \(Task_{i}\) between devices without considering the tasks on other devices. Because the inference process of the model is limited by the sequential structure of the layers, when multiple devices perform the same layer in concert, the required input may be partially present on other devices. Therefore, the device \(D_{j}\) needs to wait for the required input data to be inferred or transferred to \(D_{j}\) when reasoning about the \(l\)th layer of the model.  
\begin{table}
\begin{tabular}{c c c c} \hline \hline - & \(\mathbf{\pi}\) & \(\mathbf{\beta}\) & \(\mathbf{\gamma}\) \\ \hline Conv & 1 & 1 & 1 \\ FC & 1 & 1 & 1 \\ Norm & 1 & 1 & 0 \\ Pool & 1 & 1 & 0 \\ ReLU & 1 & 1 & 0 \\ Concat & 2 & 1 & 0 \\ EltWise Add & 2 & 1 & 0 \\ \hline \hline \end{tabular}
\end{table}
Table 1: The operator data traffic reference.  
Figure 3: Estimated and actual value of inference time for each layer of DNN.  
We aimed to build the inference latency of all tasks on multiple ends with respect to the communication bandwidth, the layer where the cut point was located, and the quantity of data to be processed by the device, and to minimize the total inference latency of the DNN model through edge-end collaboration. Specifically, for a DNN model, the DNN logic layers in the model were used as edges to construct the computational graph, assuming a total of \(n\) layers in the model, and a unique identifier \(v_{k}^{l}\), where \(v_{k}\in\mathbb{D}\cup\mathbb{E}\), was set for the \(l\)th layer in the device \(v_{k}\) according to the order of execution of the logic layers. Then, according to the data dependencies between the DNN layers, the relation \((v_{i}^{l},v_{j}^{l+1})\) was defined as the edge \(e_{i,j}^{l}\) when the output of the device \(v_{i}\) layer \(l\) was used as the input of the device \(v_{j}\) layer \(l+1\). All the logical layers of the DNN model \(v_{1}^{1},v_{1}^{2},\ldots,v_{n}^{n}\) and the data association between the logical layers were used to construct a DAG \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) as shown in Figure 4, where \(\mathcal{V}=v_{1}^{1},v_{1}^{2},\ldots,v_{n}^{n}\) represents the vertices of the graph, and \(\mathcal{E}^{l}\subset\mathcal{V}^{l}\times\mathcal{V}^{l+1}\) represents the data dependencies between adjacent DNN layers.  
We used \(tv_{k}^{l}\) to denote the inference time of the model on layer \(l\) on the end device \(v_{k}\) as the weights of all vertices in the DAG. For node pairs with data dependencies \((v_{i}^{l},v_{j}^{l+1})\), we used \(te_{i,j}^{l}\) to denote the transmission time of data between devices as the weights of all edges in the DAG. The weights of different edges varied greatly, and the data transfer on the same device was achieved through memory access, which was much smaller than the transfer time between devices and therefore negligible, with the constraint \(te_{i,j}^{l}=0\). The transfer time between end devices was smaller than the communication time from end devices to edge servers with the constraint \(te_{i,k}^{l}>te_{i,j}^{l},\forall v_{i},v_{j}\in\mathbb{D},\forall v_{k}\in \mathbb{E}\).