# Distributed Inference Models and Algorithms for Heterogeneous Edge Systems Using Deep Learning
## 4 Convolution-Layer Partitioning Algorithm
### Convolutional-Layer Partitioning Method Based on the OD-FTP Algorithm  
The OD-FTP algorithm first obtains the optimal workload partitioning strategy, namely the \"worker-device-to-workload\" mapping, by invoking Algorithm 1. In this strategy, each worker device is assigned a portion of the original inference task. Subsequently, the OD-FTP algorithm computes the parallelizable partitions of the convolutional layers based on the workload. To enable distributed inference across heterogeneous edge devices, we integrated Algorithms 1 and 2 to formulate the LFP method. The pseudocode for the LFP method is presented in Algorithm 3. The objective of this method is to transform the workload-partitioning decision (\(\pi\)) into fused blocks that can be independently executed by edge devices. The LFP method first invokes Algorithm 1 to obtain the workload-partitioning decision (\(\pi\)). It then calls Algorithm 2, which calculates the \(pos_{start}^{new},len^{new}\) and padding \((p_{up},p_{down})\) for the sub-feature maps within the relevant range of DNN layers, including convolutional and max-pooling layers. Subsequently, the LFP method extracts the sub-intermediate feature map, \(X_{sub}\), from the original input feature map, \(X_{origin}\). Finally, the MD sends \(X_{sub}\) and paddings to the WDs, which participate in distributed inference.  
The computational overhead of the LFP method can be largely attributed to lines 5-14 of Algorithm 3. These lines correspond to the iterative calculation for the padding sizes of convolutional layers within fused blocks and the derivation of the position and length of the sub-intermediate feature map. Therefore, the time complexity of the LFP method is O(NH).  
```
1:Edge Device: \(\mathcal{N}=\{U_{1},U_{2},...,U_{i},...,U_{N}\}\)
2:DNN Model: \(\mathbb{G}=\{\mathcal{L}_{1},\mathcal{L}_{2},...,\mathcal{L}_{j},...,\mathcal{L}_ {L}\}\)
3:Configuration tuples: \(\mathbb{C}=(K,\mathcal{C}_{in},C_{out},S,P)_{j},\forall j\in L\)
4:Resources tuples: \((P_{comp},P_{comm})_{i},\forall i\in N\)
5:Bandwidths:  Dividing point:\(p,p\in L\)
6:Layer Fused Tile Scope: \((s,e),\forall s,e\in L\)
7:Start Position: \(pos_{start}\)
8:Feature Map: \(X_{origin}\)
9:Sub-feature Map:\(X_{sub}\)
10:Padding Configuration:\(p\)_addings_
11:\(\pi\gets WPA(\mathcal{N},\mathbb{G},\mathbb{C},(P_{comp},P_{comm}),B,p)\)//*Algorithm 1 is invoked to calculate the optimal workload partition decision
12:\(a_{i}\leftarrow\pi\)//*Get the workload of the edge device \(U_{i}\)
13:\(p\)_addings_\(\leftarrow\)\(||\)//*Stores the padding of multiple network layers
14:\((pos_{start},len^{new},p_{up},p_{down})\leftarrow(pos_{start},a_{i},0,0)\)
15:for\(\mathbf{k}=e-1\) to \(\mathbf{s}-1\)do
16:if\(\mathcal{L}_{k}\in(Conv2d,Maxpool2d)\)then
17:\((pos_{start},len^{new},p_{up},p_{down})\gets OD-FTP(\mathcal{L}_{k}, \mathcal{C}_{k},pos_{start}^{new},len^{new})\)//*Algorithm 2 is called to calculate the relative position, length, and padding size
18:add \(p_{up}\) to \(p\)_addings_
19:add \(p_{down}\) to \(p\)_addings_
20:else
21:add 0 to \(p\)_addings_
22:add 0 to \(p\)_addings_
23:endif
24:endfor
25:reverse \(p\)_addings_ list //*Since the padding size for each layer is calculated from back to front, the list needs to be reversed after the calculation
26:extract \(X_{sub}\) from \(X_{origin}\) using \(pos_{start}^{new}\) and \(len^{new}\)
27:return\((X_{sub},\)_paddings_) //*MD sends \(X_{sub}\) and \(p\)_addings_ to the edge device for parallel execution
```  
**Algorithm 3** Layer Fused Partitioning Algorithm (LFP)