Dzina Zomwe AI Yanu Sizingafunikirenso Mtambo Kuti Amathamanga Mofulumira

Authors: Thomas Feltin Léo Marchó Juan-Antonio Cordero-Fuertes Frank Brockners Thomas H. Clausen Abstract: Deep neural network (DNN) inference on streaming data requires computing resources to satisfy inference throughput requirements. However, latency and privacy sensitive deep learning applications cannot afford to offload computation to remote clouds because of the implied transmission cost and lack of trust in third-party cloud providers. Among solutions to increase performance while keeping computation on a constrained environment, hardware acceleration can be onerous, and model optimization requires extensive design efforts while hindering accuracy. DNN partitioning is a third complementary approach, and consists of distributing the inference workload over several available edge devices, taking into account the edge network properties and the DNN structure, with the objective of maximizing the inference throughput (number of inferences per second). This paper introduces a method to predict inference and transmission latencies for multi-threaded distributed DNN deployments, and defines an optimization process to maximize the inference throughput. A branch and bound solver is then presented and analyzed to quantify the achieved performance and complexity. This analysis has led to the definition of the acceleration region, which describes deterministic conditions on the DNN and network properties under which DNN partitioning is beneficial. Finally, experimental results confirm the simulations and show inference throughput improvements in sample edge deployments. DNN partitioning at the edge enables acceleration of the inference throughput while lowering the bandwidth usage and latency to centralized servers, e.g., in the cloud. Introduction Connected devices generated an estimated 2.5 quintillion bytes of data every day in 2020. In this context, Artificial Intelligence (AI) is one of the technologies that can best cope with the always growing amount of produced data, in a range of fields such as object detection in computer vision, facial recognition, speech recognition, natural language processing, or autonomous driving. AI, and specifically Deep Learning (DL), requires, in addition to large amounts of data, significant capabilities in processing power and memory, which makes cloud computing the hosting solution for AI workloads. Consequently, in 2019, 96% of AI tasks were run in the cloud. 1 de facto 2 AI applications can have strong latency constraints, , in autonomous driving, manufacturing monitoring, or any real-time inference involving a real world interaction. For example, average response times in autonomous driving are required to be under 100 milliseconds , making round trip times to the cloud too long for such applications. Similarly, some applications may introduce a significant link usage on the network, , in the case of high quality video processing in computer vision, which prevents them from running in the cloud. Data privacy policies or data protection regulations may also prohibit data from leaving specific environments. This encourages AI deployments in edge computing, which consists of relocating computation tasks from data centers closer to edge devices, , in proximity to the data sources. e.g. [](javascript:void()) e.g. i.e. In comparison with public clouds, the edge is a resource-constrained environment with important limitations , and developing AI for the edge is therefore intrinsically different from developing AI for the cloud. Analyzing data close to its source can be challenging because of lower device capacities, inelasticity of the available resources, and heterogeneity of edge networks. Lowering the computing capacity implies lowering the achievable inference throughput, further complicating relocation of heavy workloads from the cloud to the edge. In some applications, the inference throughput, , the achievable inferences per second of a DNN, can be linked to the DNN accuracy, , with object tracking in video streams, where dropping the inference rate from 15 to 5 inferences per seconds has shown to lower the F1 score__3__ of an object detector by 10% . In other words, deployments with low inference throughput can cause critical information loss, , loss of detections in video surveillance applications. [](javascript:void()) i.e. e.g. [](javascript:void()) e.g. There are two main available methods to meet performance requirements on constrained edge networks: model compression or hardware acceleration. consists of reducing and optimizing neural networks to a light-weight, often under-performing, version of the model. Standard model compression methods include pruning , , removing unnecessary parameters in the model, quantization , , reducing the allocated memory to store the model, and knowledge distillation , , training a smaller neural network with knowledge extracted from a larger one. Model optimization requires extensive design efforts and can be an impediment to model accuracy. on edge devices implies finding hardware which can be both power efficient and light-weight, while still being able to run inference with sufficient performance. There are several types of candidate hardware for acceleration at the edge, varying in efficiency and specificity, but standard processing units fail to meet expectations and dedicated hardware such as ASICs have been found to be unpractical and expensive . Model compression [](javascript:void()) i.e. [](javascript:void()) i.e. [](javascript:void()) i.e. Hardware acceleration [](javascript:void()) DNN partitioning is a complementary method for accelerating inference by leveraging the multiplicity of existing devices on edge networks to distribute the inference computation– which can be used alone, or in conjunction with the two other methods. DNN partitioning consists of considering a neural network as a pipeline to segment into partitions, and distributing these partitions on edge devices. The placement of these partitions is based on both the DNN and the underlying network characteristics. DNN partitioning relies on the identification of split points, which are points in the model graph where the model is separated into partitions. During run-time, partitions are run sequentially, each sending intermediary inference results to the next partition. This allows each partition to start computing the next input data while the other devices continue processing the offloaded one, hereby improving the inference throughput, as shown in . In the remainder of this paper, DNN partitioning is illustrated through the example of real-time inference on video streams. figure 1 A. Related Work Methods for DNN partitioning, derived from mobile edge-cloud offloading, seek to optimize varying performance indicators, such as computing latency, energy consumption, resource utilization, cost, or throughput. DNN partitioning relies on the association of one or several of these metrics to define an optimization goal, and a method which exploits this metric to find partitioning schemes. For example, Neurosurgeon seeks a single split point, keeping the first partition at the edge and offloading the second partition to the cloud, to minimize latency and energy consumption. Applications in IoT have also considered the joint partitioning and offloading of several DNNs to optimize energy, delay, and/or cost, using different solvers such as SPSO-GA combining Particle Swarm Optimization (PSO) and Genetics Algorithm (GA), or DDPQN which uses Deep Reinforcement Learning to find partitioning schemes. Other examples include DINA , which defines an Integer Non Linear Programming (INLP) problem, and uses a matching theory based solver, to optimize delay and resource utilization in fog networks. Methods optimizing inference throughput include DNN surgery , which uses the lower size of intermediary DNN layer outputs to partition the inference computation between the edge and the cloud. Both algorithms create two partitions, one at the edge and the other in the cloud. Other studies in the field of mobile edge-cloud also include multi-threaded computation in the cloud to further accelerate the overall inference throughput. Relying on the cloud for the second partition inference computation assumes good network connectivity, which can be uncertain with the poor connectivity of some isolated edge deployments. Edgent adapts the previous methodology to mobile devices and available edge servers, relaxing the constraint of offloading to the cloud. This method is linked to a specific training and model architecture, and still limits the partitioning to two partitions. Other methods have considered multiple split points, , IONN , which describes the problem of partitioning to minimize latency and energy consumption, also taking into account the time to upload the models to edge servers. [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) [](javascript:void()) e.g. [](javascript:void()) These methods are either interacting with remote clouds, or are limited in the nature of the partitioning, , required to split in exactly two parts, with or without multi-threading. None of the listed DNN partitioning studies considers both multiple split points and multi-threading. e.g. B. Contributions This paper presents a distributed inference framework to maximize the inference throughput of real-time DNN computation on streaming data, with multiple split points and multi-threaded partitioning. The contributions of this paper are the following: A model for computing and transmission latencies of a distributed DNN, through which the expected inference throughput of a given partitioning scheme can be estimated. Formulation of the optimization problem for DNN partitioning, implementation of a branch and bound solver for this problem, and evaluation of its complexity. Simulations to explore the possible performance improvements with varying network and DNN properties. The identification of deterministic regions in the network and DNN properties leading to the existence of optimal partitionings and the cost to compute such solutions, , the conditions under which DNN partitioning is beneficial. i.e. Experimental results illustrating the regions defined in the simulations, as well as the prediction accuracy and final inference throughput acceleration for homogeneous and heterogeneous environments. For the remainder of this paper, to avoid confusion, the partitioned deep neural network will be referenced as , and the term will denote the underlying physical communications network. DNN network C. Paper Outline The remainder of this paper is organized as follows. presents background of Deep Learning and how DNNs are represented in this study. details the inference and transmission latency prediction methods required for which defines the optimization problem, as well as the branch and bound algorithm to take partitioning decisions. presents simulation results to quantify the performance and complexity of the branch and bound algorithm, as well as conditions leading to the existence of a partitioning which improves the inference throughput in a homogeneous network. presents experimental results confirming the simulations of , and shows inference throughput improvements on a heterogeneous experimental set-up. Finally, discusses the results and expands on the broader applicability of this method. Section II Section III Section IV Section V Section VI Section V Section VII SECTION II. Background: Deep Learning Within the field of Machine Learning, Deep Learning (DL) refers to methods relying on the use of DNNs, , artificial neural networks (or related machine learning methods) containing more than one hidden layer. One of the earliest references to deep learning architectures was published in 1967 , but it was not until the 2010s that DL gained traction, first in speech recognition, then in object detection in images, for the ability to capture complex relationships in high dimensional in data. Deep Learning is estimated to represent the majority of AI applications in 2022, with more than 75% of organizations using DNNs for applications that could use classical methods. DL methods have been defined as “ ” . These algebraic circuits are usually organized into layers, which form steps in the computation. The term refers to algorithms consisting of more than one layer. i.e. [](javascript:void()) 4 techniques for machine learning in which hypotheses take the form of complex algebraic circuits with tunable connection strengths [](javascript:void()) deep There are two main DNN structures: feed-forward neural networks and recurrent neural networks. Both types of DNNs can be represented as computation graphs, with the main difference being that feed-forward networks can be represented as direct acyclic graphs (DAGs), while recurrent neural networks may contain cycles. Recurrent neural networks are built for sequences of data, where each data point has a potential dependency with previous data points in the sequence, while feed-forward neural networks do not consider interactions between points in a data sequence. The remainder of this paper will consider the case of feed-forward DNNs. 5 SECTION III. Distributed Inference Modeling This Section presents a model to represent DNN and network properties in order to predict computation latencies, transmission latencies, and the final inference throughput of a given partitioning solution. A. DNN and Network Representation A feed-forward DNN of N layers is modeled as a DAG GA=(L,E) with L=(L1,…,LL) the layers of the DNN. Edges (Li,Lj)∈E are the connections between layers Li and Lj . Each layer Li has an associated compute consumption ci , measured in the number of floating-point operations required to compute a forward pass through the layer. Edges (Li,Lj) are assigned a weight si,j corresponding to the size of the data transiting between layers Li and Lj in bytes. The physical network is modeled as a fully connected graph G=(N,V) where N=(N1,…,NN) is the set of compute nodes and V is the set of links between nodes. It is assumed that compute nodes N1,…,NN have processing rates η1,…,ηN , respectively, measured in floating-point operations per second. Finally, the link throughput between two adjacent nodes Na and Nb is denoted as θa,b , measured in bytes per second. Every node Ni is connected to itself with infinite throughput to represent the loopback link, and links are assumed to be symmetrical, , θa,b=θb,a . i.e. Partitionings are defined as maps P:L→N , , a partitioning assigns a node number to each layer in the DNN. A partitioning can be described as a matrix P of dimension (N×L) , N being the number of nodes on the network and L the number of DNN layers and, with Pa,i=1 if layer Li is placed on node Na , 0 otherwise. With the example given in , L=7 layers and N=2 compute nodes, the displayed partitioning with layers {L1,L2,L3,L6,L7} on node N1 , and layers {L4,L5} on node N2 , is represented as: i.e. figure 2 Given a partitioning, a is defined as a group of consecutive layers between two split points, run sequentially on the same node. In the example above, node N1 will run two threads, the first containing layers {L1,L2,L3} and the second one containing {L6,L7} . thread With these notations defined, the remainder of this Section derives a closed expression of the inference throughput achieved by a given partitioning, as a function of the inference ( ) and transmission ( ) latencies. section III-B section III-C B. Inference Latency Prediction Given a partitioning, this Section looks at inference latency prediction on an isolated node. The latency induced by the computation of a layer Li with consumption ci , to be computed on node Na , with processing rate ηa is expressed as Tci(Na)=ci/ηa . Given a set of layers L′⊂L across all threads running on node Na with processing rate ηa , the inference latency can be expressed as: This expression is a first order approximation of an inference latency estimation based on the number of floating-point operations (FLOPs) required to process the DNN, , the number of multiply-add operations in the model. i.e. Estimation of inference latency on edge devices is complicated by run-time optimizations. Existing solutions such as nn-Meter predict inference latency based on FLOPs. Other solutions rely on a look-up table with pre-computed inference times for latency inference. For example, BRP-NAS uses a pre-trained graph convolutional network to predict inference latencies, while taking run-time model optimizations into account. [](javascript:void()) [](javascript:void()) In , it is further assumed that processors use their full capacity, which implies that multi-core processors are modeled as single-core processors with a processing rate equal to the sum of their core processing rates. It is also assumed that the computing resource is shared evenly across threads, , a processor allocates the same proportion of its time to each thread. equation 1 i.e. Across all nodes, the thread with highest latency sets the inference throughput for the distributed DNN. Omitting transmission latencies, this implies that once this limiting thread is done computing a data frame, it directly starts processing the next one. Other threads will have idle time before processing the next data frame because their inference latency is lower than this maximum latency, as shown on . figure 1 Given a partitioning matrix P , the inference latencies can be expressed as a single vector Tc of size N where the a -th component is the highest thread inference latency on node Na , , Tca=Tc(Na) : i.e. where H is the diagonal matrix of inverse node processing rates diag(η−11,…,η−1N) and c is the column vector of individual layer consumptions (c1,…,cL) . C. Transmission Latency Prediction The transmission latency can be predicted as follows: the time it takes to send the amount of data si,j between layers Li and Lj on edge (Na,Nb) over a link with measured throughput θa,b is Tti,j(Na,Nb)=si,j/θa,b . The time to achieve data transfers si,j∈E′⊂E over link (Na,Nb) is: Similarly to the inference latency prediction, this implies that the links are shared evenly between data transfers from Na to Nb . The transmission latency prediction relies on the estimation of the link throughput between nodes, more precisely the , , the amount of useful data transmitted per second. goodput i.e. Similarly to inference latency estimation, this is a first order approximation, which efficiently offers good prediction results, as shown in c, with a correlation coefficient of R2=0.9998 . The drawback of this method is its requirement to saturate the links to get a throughput estimation. figure 3 Given a partitioning matrix P , the transmission latency matrix Tt can be defined as a square matrix of size L , with Tta,b=Tt(Na,Nb) : where ° is the term by term product, or Hadamard product, Θ is the inverse throughput matrix, , a square matrix of size N with Θa,b=θ−1a,b and S is the transmission size matrix, , a square matrix of size L with Si,j=si,j if Li sends data to Lj , 0 otherwise. i.e. i.e. SECTION IV. DNN Partitioning The objective of DNN partitioning in this study is to maximize the inference throughput, denoted by C , which corresponds to the inverse of the maximum latency between all the different computation and transmission latencies. Given a partitioning P , the inference throughput is defined as: Maximizing the inference throughput amounts to finding the joint min-max between all the terms of Tc and Tt . This can be defined as a discrete optimization problem: with Ji,j being the all-ones matrix of size i×j , conditions and require that each layer be placed on one and only one node. (6) (7) This optimization problem is a Mixed Integer Non-linear Programming (MINLP) problem. The partitioning matrix can be seen as the one-hot encoded version of a vector of size (1×L) with values in [[1,N]] . MINLP problems are NP-hard, implying that the complexity of finding an optimal DNN partitioning is O(NL) since each of the L layers can be placed on N nodes. There are several heuristics to obtain optimal or sub-optimal solutions to this problem in less time than a brute force algorithm, , Genetic Algorithms (GA) , Particle Swarm Optimization (PSO) , or Branch and Bound (B&B) . The chosen methodology is an adapted B&B implementation, which is presented in . e.g. [](javascript:void()) [](javascript:void()) [](javascript:void()) Section IV-A A. Branch and Bound Algorithm This Section presents the branch and bound (B&B) adaptation to the DNN partitioning optimization problem defined in . Section IV In B&B algorithms, the solution space is represented by a tree. The process consists of eliminating entire branches in the tree based on the evaluation of the score of the root node. This implies the existence of a tree topology which creates a relationship between the score of a node in the tree and the bounds on the scores of all of its leaves. This tree representation of the solution space favors the use of the B&B algorithm in this study. Assuming ps is a partial list of size s , the children of the node ps in the tree topology are all lists which start with ps , , all partitionings where the first s layers are placed according to ps . The leaf node below ps corresponding to ps padded with the last value of ps is labeled ps~ . For example, if L=5 and p2=(2,1) , then p2~=(2,1,1,1,1) . Given Ttmax=maxTt(ps~) the maximum value of the transmission latency matrix for partitioning ps~ , all leaf nodes p below ps will have a higher maximum transmission latency than ps~ , , ∀p,maxTt(p)≥Ttmax . This is explained by the fact that given a partial partitioning, any displacement in the other layers will only add data transfers between nodes. i.e. i.e. During the process of looking for an optimal partitioning p , which maximizes the inference throughput C(p,GA,GN) , and given a current best achievable throughput best_throughput , the B&B optimization consists of eliminating entire branches of the tree representing the solution space by evaluating transmission times in partial partitionings. This process allows the B&B optimization to quickly eliminate numerous cases compared to a brute force algorithm. For example, if the throughput between nodes is low compared to the compute capacity, , with nodes connected through a low throughput wireless connection, the optimal solution is often to keep all computation on a single node. The advantage of the B&B algorithm is that it terminates after N operations in such simple cases by eliminating all partial partitionings in the first stage of the tree. Conversely, in cases where links have higher throughputs, the complexity of the B&B can be higher since it will be unable to eliminate large branches. e.g. B. Branch and Bound Complexity The overhead caused by the total number of partitions in a real world implementation is neglected in this approach. This added latency is correlated with the total number of partitions. With each partition, the data transfer from Network Interface Controller (NIC) to memory causes an additional latency, related to the PCIe throughput, memory throughput and size of the transferred data. Assuming that the data transfer throughput is limited by the memory throughput, a simplistic evaluation of this latency would change the computation latency in to: equation 1 In this expression, ν is the memory throughput, , the read/write speed to and from the memory, and (i,j)∈C are all the layers Li and Lj such that edge (Li,Lj) is a split point with associated data transfer si,j . i.e. 1) Early Stopping With an increasing number of partitions, both the performance and inference latency prediction accuracy will decrease. For this reason, and for the increase of complexity in cases with high available network throughput, an early stopping mechanism is added to limit the number of split points in the final partitioning, , B&B will only explore partial partitioning with a maximum of S split points, further limiting the size of the explored tree. The complete B&B algorithm with limited split points is shown in . i.e. algorithm 1 Algorithm 1 Branch and Bound Algorithm Limiting the number of split points lowers the complexity of this MINLP problem. For N the number of nodes, and L the number of DNN layers, the number of possible partitionings considered by the algorithm is now lowered to: instead of O(NL) for a brute force algorithm. SECTION V. Simulations This Section presents simulations to evaluate the impact of the algorithm parameters on the B&B algorithm performance and complexity. The worst case complexity for B&B is described in , when all of the transmission times computed in the partial partitionings exceed the best achieved time, but the effective B&B complexity varies according to the DNN and network properties. The following variables are explored: equation 9 The relationship between number of nodes N