## 3 Problem Formulation
### Partitioning Model  
Firstly, it should be pointed out that our partitioning method is not only designed for specific CNN architectures but is applicable to all neural networks with convolutional neural network layer structures, such as RNN and Transformer. For complex and numerous convolutional neural network architectures, our method is also applicable, as long as the granularity of partitioning is designed to be smaller, or large CNN networks can be first partitioned into vertical layers and then parallelized through our method. In DNN architectures, multiple convolutional and pooling layers are usually stacked together to gradually extract hidden features from input data. In a CNN with L layers, for layer \(l=1\ldots L\), the input feature map dimensions for each layer are \(W_{l-1}*H_{l-1}\), and each layer has corresponding learnable filters with dimensions \(F_{l}*F_{l}*D_{l-1}\). The filters slide across \(D_{l-1}\) input feature maps with a stride of \(S_{l}\) to perform convolution calculations and then generate \(D_{l}\) output feature maps with dimensions \(W_{l}*H_{l}\), which, in turn, form the input maps for layer \(1+1\). Note that in such convolution chains of CNN, due to the large dimensions of the input and intermediate feature maps, the data and computational complexity of each layer are very large. This results in extremely large memory footprints. Ordinary edge devices are unable to meet such memory and computing power requirements. However, we can observe that each output data element only depends on a local region in the input feature maps. Thus, each original convolutional layer can be partitioned  
Figure 1: A multi-user multi-edge server-edge computing system. into multiple parallel execution tasks with smaller input and output regions and hence a reduced memory footprint for each layer. Inspired by [17], we decided to adopt a method based on matrix convolution for the division of DNN/CNN inference to parallelize the convolutional operation and reduce the memory footprint. In our method, the original CNN is divided into tiled stacks of convolution and pooling operations. The feature maps of each layer are divided into small tiles in a grid fashion, where corresponding feature map tiles and operations across layers are vertically fused together to constitute an execution partition and stack. Figure 2 shows the DAG of the partitioned CNN process. As shown in Figure 3, the original set of layers is thus partitioned into M \(\times\) M independent execution stacks. By dividing the fusion stack along the grid, the size of the intermediate feature maps associated with each partition can be reduced to any desired footprint based on the grid granularity. Then, multiple partitions can be iteratively executed within one device, reducing memory requirements to a maximum of one partition at a time instead of the entire convolutional feature map. In order to distribute the inference operations and input data, each partition's intermediate feature tiles' size and input region's size need to be correctly calculated based on the output partition's size. In our method, the region's size for a tile in the output map of layer 1 is represented by \(t_{l}*t_{l}\). During the process, the output data are first partitioned equally into nonoverlapping grid tiles with a given grid dimension. Then, with the output offset parameters, a recursive backward traversal is performed for each partition to calculate the required tile region's size in each layer as follows:  
\[t_{l-1}=(t_{l}-1)*S_{l}+F_{l} \tag{1}\]  
For a CNN with L layers, the final input offsets for each partition in the CNN input map at \(l=1\) can be obtained by applying (1) recursively starting from partition offsets in  
Figure 3: Partitioning method for CNN. Figure 2: DAG for the partitioning process of the general CNN network framework. the output map at \(l=L\) with an initial size of \(t_{L}=W_{L}/M\).