{'fraction_non_alphanumeric': 0.026062073519700638, 'fraction_numerical': 0.010213515298261061, 'mean_word_length': 4.693233082706767, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Communication-Efficient Separable Neural Network for Distributed Inference on Edge Devices

The inference of Neural Networks is usually restricted by the resources (e.g., computing power, memory, bandwidth) on edge devices. In addition to improving the hardware design and deploying efficient models, it is possible to aggregate the computing power of many devices to enable the machine learning models. In this paper, we proposed a novel method of exploiting model parallelism to separate a neural network for distributed inferences. To achieve a better balance between communication latency, computation latency, and performance, we adopt neural architecture search (NAS) to search for the best transmission policy and reduce the amount of communication. The best model we found decreases by 86.6% of the amount of data transmission compared to the baseline and does not impact performance much. Under proper specifications of devices and configurations of models, our experiments show that the inference of large neural networks on edge clusters can be distributed and accelerated, which provides a new solution for the deployment of intelligent applications in the internet of things (IoT).


Introduction
In these years, deep learning has been widely used in lots of areas such as computer vision, natural language processing, and audio recognition. To obtain state-of-the-art results, models become much larger and deeper. However, large neural networks are so computationally intensive that the loadings are heavy for general low power edge devices. For example, NoisyStudent [1] proposed by Xie et al. has achieved a state-of-the-art performance of 88.4% top-1 accuracy on ImageNet. Their model EfficientNet-L2 is extremely large with 480 million parameters, making the model unsuitable for deploying on edge devices. To trade-off between accuracy and latency, many lightweight models such as MobileNet [2] and SqueezeNet [3] have been proposed. Many model compression techniques are also widely used [4]. Nevertheless, the performance of lightweight models is still far from the state-of-the-art models and model compression techniques suffer from dramatic accuracy drop once reaching the limit.
Distributed inference seems to be a solution to take care of both accuracy and latency. With the development of the internet of things (IoT), many edge devices can join a network and compose a cluster. Making good use of the idle devices in the cluster has become an issue and is still under discussion [5]. If we can distribute the inference process properly on these devices, we can make the inference of a large model much faster without a performance drop. There are two typical distributed methods usually being considered, data parallelism [6] and model parallelism [7]. However, in many inference scenarios on edge devices, such as object detection, devices receive streaming data of images and make inferences with a pre-trained model. This kind of data must be input one by one instead of batch by batch, so it lacks the mechanism of data parallelism. In this case, model parallelism seems to be a better solution to deal with this problem.
In this paper, we proposed an architecture, Separable Neural Network (SNN), with a new model parallelism method to make distributed inference on edge devices efficiently. With our approach, we can parallelize a class of very deep neural network models, such as ResNet and ResNeXt, to a cluster of edge devices and reduce the costs and overheads of transmission. It not only speeds up the inference but also reduces the memory usage and computation per device. Fig. 1 shows the pipeline of our approach. We separate the original model and introduce an RL-based neural architecture search method to find the best communication policy from an extremely large searching space. Finally, we fine-tune the best model according to decisions made by the policy and deploy it on edge devices. Our method is more suitable for the models with residual connections and group convolutions.

Multi-path structures
Benchmark convolutional neural networks such as AlexNet [6], VGG [8] are in general designed as a sequence of convolution layers to extract features from low level to high level. GoogLeNet [9] and the series of Inception networks [10] [11] controller policy reward present a concept of parallelism, which extracts features with different size of filters at the same time and merge them together.
ResNet [12] introduced residual connections to make features and gradients propagate more unimpededly, and lots of works follow the thought. ResNeXt [13] is one of the following works. It splits the layers into multi-paths and all the paths can compute in parallel. The multi-path structure can be implemented by group convolution, which divides input channels and output channels into several groups. The number of paths is controlled by cardinality C, representing the number of groups. If there are M input channels, N output channels in a group and the cardinality number is C, the kernel size is K, then the total number of input channels is C × M, and the total number of output channels is C × N. The total number of parameters is C × (K × K × M × N), which is C times smaller than normal convolution under the same number of input channels and output channels.

Model parallelism
Model parallelism [7] aims to split the model into several parts and distribute them on different compute nodes. Since each node only computes part of the entire model, it doesn't need to synchronize the weights and gradients with other nodes. However, this kind of parallelism increases the dependency between the nodes [14]. That is, one node needs to wait for the results from previous nodes to run the computation. The extra data transmission between layers should also be considered.

Distributed inference for neural networks
Distributed inference is a way to improve inference on edge devices. Teerapittayanon et al. [15] proposed a hierarchical model, distributed deep neural network (DDNN), to distribute the components of the model on the cloud, the edge, and the end devices. The end-to-end DDNN can be jointly trained and minimizes transmission costs. DDNN can use the swallow portions in the edge to make inference faster or send the data to the cloud if the local aggregator determines that the information is insufficient to classify accurately. Edgent [16] is a framework to adaptively partition DNN on edge and end devices according to the bandwidth. After well-trained partitioning, Edgent can make a co-inference on the hybrid resources. It also introduces an early exit mechanism to balance latency and accuracy. DeepThings [17] is a framework for adaptively distributed CNN models on edge devices. It can divide convolutional layers into several parts to process and minimize memory usage to reduce communication costs. Furthermore, it can be used in dynamic application scenarios with an adaptive partition method to prevent synchronization overheads.

Neural architecture search
Since rule-based design architectures reach the performance limit, neural architecture search, a method of automatically searching for the best model, becomes more and more popular. However, the searching space of architecture candidates is huge, which makes random searching not practical. Zoph et al. [18] proposed Neural Architecture Search (NAS), which constructs an RNN controller to sample models from searching space and updates the controller based on Reinforcement Learning (RL). This method successfully found a state-of-the-art model but still spent lots of time and computation power. Pham et al. [19] proposed Efficient Neural Architecture Search (ENAS) to improve NAS by sharing models' weight, omitting the process of training sample models from scratch, using mini-batch data to evaluate performance. Finally, ENAS finds a model with similar performance and achieves 1000 times speedup compared to the original NAS.

Separable Neural Network
Started from a model with sequential layers, we denote the feature in layer l as X l . If we separate X l into C groups, then X l can be seen as the concatenation of C components.
To get the feature in the next layer, each of the component has to do the following computation: where i denotes the i-th component, T denotes a transformation such as convolution, and D denotes the feature received from other component. After we get the new feature, a function F with quantization and sparsification further reduces the size of X to make it more efficient for transmission. Another pre-defined function s then decides to send the feature to a set of receivers. We can simply define this process with following equation: parameters, where M is the number of input channels, N is the output channels and K is the filter size. ResNeXt [13] further modifies the blocks into multi-path structures, and the number of parameters become: where the number of paths C and the number of channels in middle layer d can be adjusted to make amount of parameters as close as possible to the original ResNet for comparison. We can further rewrite Equation 5 as follows: It is clear to see that the first layer of the block has M input channels, C · d output channels, and the middle layer is a group convolutional layer with C · d input channels, C · d output channels and C convolutional groups.
To construct Separable ResNeXt, we first decide G, the maximum number of compute nodes used to deploy the distributed inference system on, then we divide the C paths into G groups.
Again, we rewrite Equation 7 as follows: Comparing with Equation 6, the first layer becomes group convolutional layer, so the number of convolutional group is G and the number of input channels becomes G · M. The middle layer is exactly the same. As a result, the total number of parameters is theoretically the same as ResNeXt. However, since every group has to maintain its own batch normalization and downsampling operations, the size of separable models may increase by about 1% ∼ 6%. Table 1 compares ResNeXt-56 and Sep-ResNeXt-56, and their corresponding amount of parameters, where Sep-ResNeXt-56 denotes separable ResNeXt-56. The most different is that in Sep-ResNeXt we concatenate G replications of the output feature maps of the first layer when training to simulate the synchronization of data on G devices in the first transmission step when deployment. Additionally, to avoid large transmission overhead when aggregating all the results on all devices, we tend to make the device use local feature maps to run classification. Therefore, we only keep the first 1/G feature maps in the last convolutional layer, and these feature maps become the input to the final classifier.
The setting of G is related to the number of compute nodes and gives some flexibility of deployment. For example, if we set G as 4, we expect the model to be used in a cluster with four devices. Additionally, the model can also be deployed on less than four compute nodes. We can put four parts together or put two parts on two compute nodes, respectively. These scenarios of deployment perform the same on accuracy.

Neural Architecture Search for the best communication policy
After we separate the model, parts of the model are detached from each other. If all the parts transmit their information to each other, there would be a large amount of data transmission and cause large overheads. We make use of neural architecture search (NAS) to deal with this problem. With the method of neural architecture search, we can just keep the transmissions that are critical for the model's performance. The search method contains two components: a separable network and a controller network. We use a computational graph to represent a neural network model -the nodes are the convolutional layers of the model, and the edges denote the data flow. In this perspective, the separable network contains the nodes of the graph and the controller network control the edges. Since the edges determine the transmissions, every decision sampled from the controller in a step determines a transmission scheme. The controller is only used in the training stage. After getting the best model from the controller, we no longer use it in the inference stage.
Since the models are encoded as sequences and recurrent neural network (RNN) is suitable for dealing with the sequence data, we construct the controller network using RNN. In the first step, the RNN controller uses default input and default hidden state to generate an output, representing every possible communication's probability. We sample a decision in this step according to the probability. The decision and the current hidden state then become the input and hidden state to the next step. We repeat the process until all the decisions have been made. Furthermore, we expect that every compute node only deals with one sending process and one receiving process, so the destination of data to be sent should not be duplicated. Based on this premise, the number of choices of each step can be specified as G!, where G is the number of compute nodes.
The training process can be divided into three stages: (1) training the separable network, (2) training the controller network, (3) sampling the best model from the controller, and finetuning. Fig 2 shows the overview of these three stages. We use different sets of data to train different networks in different stages. In the following, we will describe the details in order.
(1) Training the separable network To train the separable network, we repeat the following steps: first, we fix the parameter θ π of controller network π, then sample decisions from the policy output by the controller to determine a model m with the parameters of separable network θ s . The expected loss E m∼π [L(m; θ s )] can be estimated by the Monte Carlo method. According to the expected loss, gradients can be computed as and finally, the separable network can be updated using stochastic gradient descent algorithm. (2) Training the controller network As for controller network π, we fix the parameters of the separable network θ s , then sample decisions to determine a model m. With the sampled model, we make inference on validation data and take the accuracy as reward R. In this stage we try to maximize the expected reward E m∼π [R] by using reinforcement learning. We can compute the gradient with the policy gradient method and update parameters θ π . (3) Sampling the best model from the controller network After the training on separable network and controller network, we simply sample some models with the method in the training stage to measure the performance on both two networks and find the best models. We keep the best weights and decisions of the separable network model every epoch and fine-tune with a small learning rate to get the best result.

Transmission overhead reduction
To make the process perform computation and transmission at the same time, we use a staleness factor denoted by α to control the tolerant delay between sending and receiving. The staleness factor α can be defined as the ratio the of number of block computing to block transmission. In default, the staleness factor α is assumed to 1, which means one block computing and one transmission. If we let the staleness factor α > 1, during transmission, compute nodes do not wait for the data arrived but keep computing. After the transmission done, compute nodes finally aggregate the current result with the data they received. So in the optimal scenario, the transmission time can fully overlap with the computation time. If we set α to 2, it means that on average there would be one transmission every two blocks being computed, and it would save half of the transmission. Fig.  3 illustrates the concept of the staleness factor, where With staleness factor α > 1, we can do more block computations and save the transmission at the same time.
Moreover, we try to add a sparsification decision to control how much data need to be sent at every transmission. We set K levels between P min % ∼100% to control the percentage of feature maps to be sent. So the amount of data to be sent can be The compute node only needs to send the first N send channels of features at the transmission step. Additionally, casting the data type from Float32 to Float16 before transmission also helps to reduce data size.

Dataset
CIFAR-10 and CIFAR-100 are datasets that contain 10 classes and 100 classes of images respectively. Both of them have 50000 training images and 10000 testing images. Every image has a size of 32×32 and RGB three channels. It is more general than MNIST, so we do all the experiments on these datasets. Furthermore, we preprocess the images with Autoaugment [20], a bunch of data augmentation policies searching by reinforcement learning, in the training stage. The operators in Autoaugment include shearing, rotation, contrast, brightness, sharpness, etc., and the policies are the combination of operators.10% of the training images are chosen randomly to be validation data.

Implementation details
First we use stochastic gradient descent (SGD) optimizer to train all the original models for 200 epochs from scratch. The learning rate is initially set as 0.1, with a decay schedule of dividing the learning rate by 10 every 50 epochs. The batch size is fixed to 128. As for SNN, we construct an RNN controller with 100 LSTM cells. In the first stage, we train the separable networks through the entire training dataset. Then we train the controller network through the validation dataset for 500 steps in the second stage. In the third stage, we fix all the parameters and sample 100 architectures. Every architecture makes inference on a mini-batch of the testing dataset and the one with the highest accuracy will be kept. These three stages are repeated for 60 times iteratively. Finally, we fine-tune the best model with a learning rate of 0.0001 for 45 epochs.

Searching for high-performance models
We construct an RNN controller with 100 LSTM cells to learn the policy for sampling communication decisions. The possible number of choices in every transmission step is 4! = 24, when G = 4. Table 3 shows all decisions and their corresponding id. The searching spaces for separable ResNeXt-56 (α = 2, G = 4) and ResNeXt-110 (α = 2, G = 4) are 24 9 ≈ 2.64 × 10 12 and 24 18 ≈ 6.98 × 10 24 , respectively. Furthermore, Table 4 lists all the sparsification decisions when K = 9 if we additionally consider reducing amount of transmission data. The best decisions learned by the controller under different settings are listed in Table 6, and the results compare with original models are shown in Table 2, Table 5. We notice that a well-trained controller tends to sample communicationintensive decisions, which proves that the connections between separated parts are important. However, some decisions which are not communication-intensive are still sampled. These decisions help reduce the loading of transmission because at least one node do not need to transmit data.

Reduction of transmission data
To further reduce the amount of transmission data, we add decisions as described previously to control the sparsity of data. The sparsity level K is set as 9, so there are 9 levels between 50% and 100% and we simply use 0∼8 to stand for the nine levels. We also discuss the impact if we cast full floating-point to half floating-point when transmission. The performance is shown in Table 5. We found that there is only a little accuracy drop with these techniques, and the total amount of transmission data can be reduced to only 14   . The order in a decision means the destination node of transmission from node 0, 1, 2 and 3. For example, decision no.7 represents that node 0 sends to node 1, node1 sends to node 0, node 2 sends to node 3 and node 3 sends to node 2. The choices in red are communication-intensive, which means every node has to send data to other node.

The benefit of the controller in neural architecture search
In this section we discuss if the controller really learned to sample better policies. We reproduce the experiment in the previous section by replacing the RNN controller with a random sampler. To reduce the effect of how well a separable network is trained, we also design a control group that uses the pre-train weight from the case with the controller to initialize the separable network. The training loss and average testing accuracy are shown in Fig. 4. It is clear to see that the case with the controller outperforms cases without a controller, showing that the controller really helps to achieve better decisions.

Deployment analysis
To deploy our model on edge clusters, we further specify the relation between our settings and specifications of devices. With appropriate setting of staleness α, we can theoretically mitigate transmission overhead. That is, if there is a given separable model, the computation and amount of transmission data are known, and the upper bound of the ratio can be determined. Fig. 5   For example, we evaluate our target device Raspberry pi 3b+, which has computing power of 1.7 × 10 8 FLOPS and 300Mbps transmission speed. The result indicates that the specification is sufficient to deploy our model. As for the implementation in real scenario, we use 4 devices with quad-core ARM A57 to deploy separable ResNeXt-56(4×16d, G = 4) model. The time measurement of different components is shown in Fig. 6. Although there are some overheads on memory copies, first transmission and aggregation of feature maps, we can speed up inference about 3X.

Conclusion
We proposed a new approach of parallelizing machine learning models to enable the deployment on edge clusters and make inference efficiently. Different from traditional parallelism methods, we focus on the reduction of transmission costs through the architecture design to solve the problem of transmission overheads. With our approach, the latency of inference and the model size on one device can be decreased greatly. The communication overheads can be balanced by setting the proposed staleness factor. We also apply the techniques of the neural architecture search to find the best performing models and further reduce transmission. Overall, our work provides a solution to aggregate computing power of edge devices in a cluster. Large models can be deployed properly without significant performance drops. For future research, our work can combine with model compression techniques to further decrease latency. The support of heterogeneous networks should also be considered to fit the scenario in real life more precisely.

Method
Acc.