# NUDIF: A Non-Uniform Deployment Framework for Distributed Inference in Heterogeneous Edge Clusters
## 3 Non-Uniform Deployment Framework
### MINLP-Based Deployment Optimization Modeling  
The modeling of the optimization problem in the deployment planning stage is the core step of the entire system, which we detail as follows. Consider a heterogeneous edge cluster with \(N\) devices, each exhibiting distinct computational power, memory capacity, and communication bandwidth. A complete model is partitioned into \(M\) sub-models. Our objective is to allocate one or multiple devices to each sub-model, forming M instance clusters that sequentially execute the inference pipeline to maximize system throughput. For the convenience of description, the main symbols used are shown in Table 1.  
We use a binary variable \(x_{i,j}\) to represent whether the sub-model \(i\) is executed on device \(j\). It is 1 if so, and 0 otherwise. We use a binary variable \(y_{j,s}\) to represent whether device \(j\) belongs to stage \(s\). It is 1 if so, and 0 otherwise. We use \(T_{comp}^{i,j}\) to represent the computation time of the \(i\)-th sub-model on device \(j\). Assume that the \((i-1)\)-th sub-model is executed on device \(j\) and the \(i\)-th sub-model is executed on device \(j\). We use \(T_{comm}^{i-1,j,i^{\prime}}\) to represent the communication time for transmitting the output of the \((i-1)\)-th sub-model from device \(j\) to device \(j^{\prime}\). The data transmission time is determined by the output size of the sub-task and the bandwidth between the two devices. Since the constraint requires that only one sub-model can be deployed on a device, the \((i-1)\)-th sub-model and the \(i\)-th sub-model are not on the same device. Then the communication time for transmitting the output of the \((i-1)\)-th sub-model from device \(j\) to device \(j^{\prime}\) is:  
\[T_{comm}^{i-1,j,i^{\prime}}=\frac{O_{i-1}}{B_{i,j^{\prime}}}. \tag{1}\]  
We use \(T_{j,s}\) to represent the total time for device \(j\) to perform the inference of sub-model \(s\), which includes the computation time and the communication time, and it can be expressed by the formula as:  
\[T_{j,s}=\sum_{i=0}^{M-1}T_{comp}^{i,j}\cdot x_{i,j}\cdot y_{j,s}+\sum_{i=1}^{M -1}\sum_{j^{\prime}=0}^{N-1}x_{i-1,j}\cdot y_{j,s}\cdot x_{i,i^{\prime}}\cdot y _{j^{\prime},s+1}\cdot T_{comm}^{i-1,j,i^{\prime}}\,\forall s\in\{0,1,2,\ldots,M-1\}. \tag{2}\]  
The throughput of each device is the reciprocal of its execution time. For each stage, the throughput of that stage is the sum of the throughputs of all the devices in that stage. The throughput of stage \(s\) can be expressed by the formula as:  
\[Th_{s}=\sum_{j=0}^{N-1}\frac{1}{T_{j,s}}\,\forall s\in\{0,1,2,\ldots,M-1\}. \tag{3}\] \begin{table}
\begin{tabular}{c l} \hline \hline
**Notations** & **Explanations** \\ \hline
**N** & Number of devices \\
**M** & Number of sub-models \\ \(O_{i}\) & Output size of sub-model \(i\) \\ \(Req_{i}\) & Memory requirement of sub-model \(i\) \\ \(Mem_{j}\) & Memory capacity of device \(j\) \\ \(B_{j,j^{\prime}}\) & Bandwidth between device \(j\) and device \(j^{\prime}\) \\ \(T_{comp}^{i,j}\) & Computation time of the \(i\)-th sub-model on device \(j\) \\ \(T_{comm}^{i-1,j,i^{\prime}}\) & Communication time for the output of the \((i-1)\)-th sub-model from device \(j\) to device \(j^{\prime}\) \\ \(T_{j,s}\) & Total inference time for sub-model \(s\) executed by device \(j\) \\ \(Th_{s}\) & Throughput of stage \(s\) \\ \(Th_{min}\) & Throughput of the stage with the minimum throughput \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Notations and their explanations. Our optimization objective is to make full use of the device resources in the cluster, enabling the devices in each stage to execute collaboratively, complete the inference of the entire model, and maximize the throughput of the entire system.