# Distributed Inference Models and Algorithms for Heterogeneous Edge Systems Using Deep Learning
## 4 Convolution-Layer Partitioning Algorithm
### Od-Ftp  
(1) Height-Dimension Partitioning and Residual Blocks  
Convolution-layer partitioning typically involves a two-dimensional grid-partitioning method for feature maps, as depicted in Figure 2a. In this approach, the feature map is divided into \(N\times M\) partitions, with the workload distributed across \(N\times M\) edge devices. However, this two-dimensional partitioning approach often results in computational redundancy. In this case, the workload of each edge device overlaps with those of three/four neighboring devices, leading to a decrease in inference performance. To overcome this limitation, we propose the height-dimension partitioning strategy illustrated in Figure 2b. In this approach, the feature map is divided into N partitions along the height, with each partition corresponding to the workload of one of the N edge devices. Because the feature map is partitioned along its height, the workload of each edge device creates computational redundancy with only one/two neighboring devices. This results in more efficient computation of the fused blocks. In the ResNet architecture, the execution order of network layers is structured as residual blocks instead of a simple sequential chain, as shown in Figure 3a. Residual blocks are essentially directed acyclic graphs (DAGs), where a layer can receive inputs from multiple preceding layers and provide outputs to several subsequent layers. Traditional distributed inference methods [12; 14; 15] require separately handling these DAG structures, which can degrade performance. To address this, we consider residual blocks as new convolutional layers, as displayed in Figure 3b. Converting residual blocks into sub-fused blocks avoids the complex layer dependencies within them and eliminates the need to handle each block individually. In this strategy, the ResNet model's execution order becomes a simple sequential model of layers. In the experiments conducted, the convolutional layers in ResNet18 and ResNet34 are transformed into 12- and 20-layer sequential networks, respectively. Figure 2: Different convolutional-layer partitioning strategies. (2) OD-FTP  
Typical partitioning algorithms, such as the FTP algorithm, suffer from the issue of high computational redundancy within fused blocks. To address this issue, our proposed algorithm is used to calculate the transformation relationships between the input and output feature maps within the convolutional layers, and specifically, the padding size for each layer. After the partitioning strategy (\(\pi\)) is determined, the convolutional layer at partition point \(j\) on an edge device must compute a sub-intermediate feature map having the \(C_{j}\times a_{i}\times W_{j}\) dimension and send the result to the MD. To validate this sub-intermediate feature map, the padding size for each convolutional layer within the fused block, denoted as \((p_{up},p_{down})\), must be calculated based on the shape of the sub-intermediate feature map. Additionally, the relative position and length of the sub-intermediate feature map within the original feature map, represented as \((pos_{start},length)\), must be determined. The concept underlying Algorithm 2 is calculating \(pos_{start}^{new}\) and \(pos_{end}\) through the stride of the convolutional layer and updating \((p_{up},p_{down})\) by validating the \(pos_{start}^{new}\) and \(pos_{end}\) indices. The pseudocode of the proposed OD-FTP algorithm is presented in in in Algorithm 2. The inputs for the OD-FTP algorithm include the configuration information related to the DNN layers and the shape of the original feature map after it passes through the current convolutional layer. The output consists of the relative position and length of the sub-intermediate feature map within the next convolutional layer and the padding size for that layer. The main computational overhead of Algorithm 2 results from lines 2 and 3, and specifically from the computation of \(pos_{start}\) and \(length\). The time complexity of Algorithm 2 is O(H).