Deep Neural Networks are enabling several of the most exciting and innovative applications that are executed on a variety of computing devices, ranging from servers to edge and mobile devices. From a systems research viewpoint, this had led to a large set of ongoing projects on optimizing DNN inference (and training) tasks [1,21,23,26,32,34,61,66,69] as well as tensor compilers [31,33,54].
Most of the work on optimizing DNNs considers static models that are characterized by the following two properties: 1) input and output shapes and sizes for each layer are known a prior, and 2) the execution path is fixed, i.e., independent of the input. In dynamic models, in contrast, one or both of the above two properties are no longer true, and such models are now becoming prevalent. For example, Skipnet [63] decides, based on the input, whether to include or exclude certain operators (or layers). A different form of dynamism seen in transformers for NLP like BERT [13] or cuttingedge computer vision models [29,55,56] can take inputs with different shapes and/or apply variable portions of filter kernels during the execution. Consider a commonly used dataset like Wikipedia. The length of input sequences typically varies from 32 to 512 [71], creating significant dynamism in text processing. Similarly, neural networks for image/video processing often deal with images/videos of varying resolutions that dynamically change based on network conditions and player settings. At least three factors have contributed to the popularity of dynamic models and this trend is expected to continue: the need for adapting to computational capacities of different devices, the need for supporting different types of input (e.g. images of different resolutions), and the need for achieving high accuracy for different scenarios.
Dynamic shapes, sizes, and control flow in these models pose many challenges for the optimizations that have been key to obtaining high efficiency. For example, loop fusion [19,42,46,59] cannot be applied [57,73,74] if we do not know that the index space of two loops (which likely is the same as the dimensions of respective input tensors) is identical. Planning the execution order [2] to reduce memory requirements or otherwise planning memory allocation [51] is, similarly, not possible if tensor sizes are not statically known.
While many of the existing systems for DNN execution can support dynamic models, they do with high overheads due to very conservative assumptions and/or expensive analyses at the runtime. For example, TFLite [1] and MNN [26] perform re-initialization (equivalent of recompilation) when the input shape to the model changes.
This paper presents the first nuanced approach for optimizing DNN inference in the presence of dynamic features. Our approach emphasizes reducing inference latency as well as memory requirements -the latter being quite important on the mobile devices we Table 1: Inference overhead for shape dynamism w/ execution re-initialization. SL: shape propagation and layout selection. ST: schedule and tuning. Alloc: memory allocation. Infer: inference time. Experiments are conducted on a Samsung Galaxy S21 w/ MNN [26].
CPU latency (ms) GPU latency (ms) SL ST Alloc Infer SL ST Alloc Infer YOLO-V6 [36] 6. 9 target. The foundation of our approach is an in-depth study of operators that form the basis for modern DNNs. These operators are classified into several groups on the basis of how the output shapes relate to input shapes and values. Based on such a classification, we present a data-flow analysis framework, called Rank 1 and Dimension Propagation (RDP) that infers shapes and dimensions of intermediate tensors. RDP analysis considers known constants, symbolic constants, and expressions involving these. RDP analysis results are then used for enabling a number of optimizations, which includes operator fusion and fused code generation, static execution planning, runtime memory allocation, and multi-version code generation. This work integrates RDP and optimizations enabled by it together and builds a comprehensive framework for optimizing Dynamic DNNs, called SoD 2 . SoD 2 is extensively evaluated on 10 cutting-edge DNN models with shape dynamism and/or control-flow dynamism. Specifically, these models include the ones for emerging Artificial General Intelligence (AGI) [18] such as StableDiffusion [56] and Segmen-tAnything [29]. Our evaluation results show that SoD 2 saves 27% to 88% memory consumption and results in 1.7× to 3.9× execution speedup compared with four state-of-the-art product-level DNN execution frameworks (such as ONNX Runtime [12], MNN [26], TVM [5] with Nimble extension [57], and TensorFlow Lite [1]) that support dynamic DNNs. In all, this paper makes the following contributions. DNN Operator Classification. We classify the operators used for modern DNNs (specifically 150 operators used in ONNX (Open Neural Network Exchange)) into 4 categories, which are Input Shape Determined Output, Input Shape Determined Output Shape, Input Shape & Value Determined Output Shape, Execution Determined Output. We formally define these operators and explain their significance for inferring ranks and dimensions for the DNNs where the input can be of different sizes and the execution is data dependent. Data-Flow Analysis for Rank and Dimension Propagation. Building on the operator classification, we have developed a static analysis framework for propagating shape and size information through a computational graph. This framework, called RDP, considers both known and symbolic constants as well as expressions involving these values. Though somewhat similar to the well-known constant propagation analysis [4], our work is different in having transfer functions specific to the operator (types), supporting both backward and forward analyses, and considering not only known and symbolic constants but also expressions involving them. 1 Rank denotes the number of dimensions in a tensor.
Comprehensive Set of Static and Dynamic Optimizations. Using results from RDP analysis, we enable a series of optimizations. First, we enable code fusion, including generating multiple versions when sufficient static information is not available. Next, we perform execution planning, using the results of RDP to partition the original graph, and further using several heuristics based on RDP output. Finally, we enable runtime plan generation for memory allocation and also generate multiple versions of optimized implementations for individual operators.
Existing DNN inference engines on mobile devices use two common approaches when handling dynamic DNNs. Static Solutions. Many existing DNN inference engines for mobile platforms (specifically, TFLite [1] and MNN [26]) support dynamic features by extending their static model execution. For handling dynamic input shapes, this involves either execution re-initialization when the input shape changes or, alternatively, conservative (maximum) memory allocation when the input shapes are unknown. To handle dynamic control flow, it typically requires the execution of all possible paths, and stripping out invalid results. Not surprisingly, such simplistic handling of dynamic features incurs significant execution and/or memory overhead. To further illustrate, Table 1 shows a performance study of three models (YOLO-V6 [36], Conformer [20], and CodeBERT [16]) that can take input with dynamic shapes. MNN [26] runs these models on a Samsung Galaxy S21 with execution re-initialization to handle varied input shapes. These results show that the re-initialization usually takes even significantly longer time than the inference itself. This approach might be acceptable for cases where the overhead of re-initialization can be amortized over a number of inference tasks (e.g., certain video processing scenarios). However, many application scenarios (across the image, audio, and language processing) involve continuously changing inputs. An alternative way, as also indicated above, is to conservatively allocate large memory spaces. However, it incurs significant memory wastage, which can limit the ability to execute large models or to do so efficiently, especially on mobile (or edge) devices with limited memory. Runtime Solutions. TVM (with Nimble extension) [5,57] improves on the limitations of static solutions by providing a set of optimizations within a virtual machine. An example of this functionality is a shape function to infer the output tensor shape and use this information for dynamic memory allocation. However, such functions and the subsequent dynamic memory allocation introduces significant execution overhead. Background and Notation. It is common to represent a DNN as a Computational Graph, which happens to be a Directed Acyclic Graph (DAG). Each tensor (which can be an input and/or output) can be categorized by a shape (including dimensions) and the contents or values. Each operator is denoted as L l , where l is the operator index. Assume L l has m input tensors (of which, 1, k are constant tensors while k, m are output tensors from previous operators) and n output tensors. The shape of the input tensor i for the l th operator is denoted as IS l i and the corresponding tensor value can be denoted as IV l i , Similarly, each output tensor's shape and value are OS l i and OV l i , respectively. Now, intuitively, a class of functions relates the output shapes and values to the input shapes and values -F f s for the shapes and F v for the values.
• Input Shape Determined Output: The output (tensor), which is characterized by both its shape and value, has the following dependence on the input. The output tensor shapes are dependent on the input tensor shapes, whereas the output tensor values are determined by the input tensor shapes and possibly some of the constant tensors -input values do not impact the output. Examples include Shape and EyeLike. Formally, there is a pair of functions F f s , F v , such that:
where 1 f k f m.
• Input Shape & Value Determined Output Shape: Similar to the previous category, the output values rely on the input shapes and all the input values. The difference is that the output shapes also rely on partial set of input values. Examples include Extend and Range). Formally, there is a pair of functions F f s , F v and a subset of input tensors (p, . . . , q) whose values specify the output shape, such that:
, where 1
← -IS l 1 , . . . , IS l m , IV l 1 , . . . , IV l m , and the shape of i-th output tensor can only be measured after materializing its value:
, which means it is not able to know the output shapes until materializing the output tensors (i.e., after executing the layer). Only partial optimization with conservative analysis can be applied to this operator, and full optimizations need dynamic execution results.
Although these operator types are defined according to forward transfer , i.e. an output tensor shape and value are related to the input tensor shape and/or value. In practice, Backward transfer is also used, i.e., we can (and need to) backward propagate the known output shapes (either rank or dimension or both) to the unknown input shapes. For instance, if we know the output shape of Add, its input dimension might be 1 or identical to the corresponding output dimension due to broadcasting rules [11]. We define backward transfer functions as:
Table 2 shows typical operators in ONNX [48] categorized by the above classification. As further illustration, Figure 1 shows four sub-graphs that represent operators with different dynamism degrees (marked with red boundary) and their connections. Figure 1 (a) shows an Input Shape Determined Output operator Shape. Once its input shape is known, its value result can be directly inferred (and in fact, this value can be propagated from Shape to BiasAdd because all following operators belong to the Input Shape Determined Output Shape group). Similarly, Figure 1 (b) implies that if the input shape to Conv is known, this shape information could be propagated to the entire sub-graph because all operators in this sub-graph belong to the Input Shape Determined Output Shape group. For the cases represented in both (a) and (b), even if the exact shape is unknown, it is still possible for us to perform compiler optimizations such as operator fusion and fused code generation, execution order optimization, and memory optimization, which will be elaborated in the next Section. In Figure 1 (c), the output shape of TopK depends on its input value (which is the left predecessor's branch in the example), i.e., the output shape of TopK (and its successors) is unknown until its left predecessor branch is executed. Figure 1
Based on the DNN operator classification introduced above, SoD 2 introduces a new static data-flow analysis framework to infer the intermediate result tensor shape. Such an analysis is the enabler of several optimizations, which are dynamic DNN operator fusion, execution path planning, memory planning, and multi-version code generation. All of these optimizations ensure a deterministic running sequence and a consistent output, given a particular input. At a high level, our approach does not require conservative static assumptions or runtime overheads, thus providing significant improvement over the existing state-of-the-art.
To facilitate static optimizations for dynamic DNNs, a critical requirement is knowing (possibly symbolically) the intermediate result tensor shape (i.e., rank and dimension). Our key observation is that for many operators and operator combinations (e.g., an Input Shape Determined Output operator and an Input Shape Determined Output Shape operator), even without knowing the input tensor shape, it is still possible to infer the shape of the intermediate result tensor to a certain degree. Our framework is based on this observation and is called operator Rank and Dimension Propagation, or RDP. While RDP has certain similarities with the classical (symbolic) constant propagation frameworks [4], it needs to deal with nuances of the DNN operations and the computational graph. RDP also considers operations over multiple (symbolic) constants as a possibility in its lattice and requires iterative forward and backward analysis.
• G is an extended computational graph (a DAG), with controlflow operators <Switch, Combine>). If this extended computational graph involves multiple branches that all need to be executed, we assume the execution order is always from left to right. It is easy to prove that G is equivalent to a controlflow graph on operators, which serves as the foundation of this data-flow analysis. d) indicate the location where transfer functions apply and their applying orders for a forward transfer (a backward transfer reverses this order). S and V equations map values in the RDP domain to the shape and value of each tensor, in which, F denotes the transfer function. fs and bs of F denote forward and backward, and F's subscript is a short form of its type (e.g., ISDOS means Input Shape Determined Output Shape).
until the results converge. This is because the shape of a tensor could be inferred from its producing operator and/or consuming operator, and their inference results should be the same to guarantee the correctness of this DNN execution.
values (also shown in Figure 2) and includes known constants, symbolic constants, and operation-inferred constants that form a lattice. The lattice also includes undefined (unde f ) as the top (¦) of the lattice and Bottom ( §) which is nota-constant (nac). ' is a meet operator, which follows the common definition for product lattice. m is a map function mapping values in lattice to two variables, Shape (S) and Value (V), representing these for the intermediate tensor.
More specifically, RDP is a type of data-flow analysis, where L ′ describes its analysis scope, i.e., how to map each shape and value property to a kind of constant that forms a lattice structure (in Figure 2). This lattice guarantees that the analyzed properties of RDP follow lattice theory, so RDP analysis will converge with a unique solution. 3 illustrates several common ones. The left-hand side (Figure 3 (a)) shows an example with four forward transfers that employ three types of Update transfer functions. Similarly, the right-hand side (Figure 3 (b)) shows an example with two backward transfer functions that belong to the same type. A point worth noting is that the appropriate transfer function to apply to an operator depends not only on the computational graph but also on the constants inferred during the RDP analysis process, which determines the dynamism classification of the operator. The Merge transfer function is straightforward -it merges the S-map and V-map from multiple control-flow branches based on the lattice in Figure 2. RDP Solution. The method is shown as Alg. 1 and involves applying the transfer functions (F) to the extended computational graph (G) along the two directions iteratively. Elaborating on Alg. 1, it first sorts the nodes (i.e., operators) in the computational graph G with the dept-first order and initializes the output shape-and valuemaps of each node as undef (Line 1 to Line 2). It next processes each node (n) by applying forward transfer functions to n's predecessors' output shape-and value-maps (i.e., n's input shape-and value-maps) (Line 13). Moreover, it propagates n's output shape-and value-maps to n's predecessors' output shape-and value-maps by backward transfer functions if any predecessors have undef analysis results (Line 14 to Line 15). These forward and backward transfer functions are defined based on the dynamism classification of DNN operators (as shown in Line 20 to Line 32). Alg. 1 needs to process two specific types of nodes (operators): i) control-flow nodes (like Combine or
General cases: I' = 1 or I, J' =1 or J, K' =1 or K If we know:
Figure 4: Operator fusion with dynamic shapes. The top code snippet shows that fusion is not feasible because of broadcasting [11]. Specifically, Add requires A's indices I ′ , J ′ , and K ′ to be either 1 or I, J, and K, resulting in 8 fusion scenarios. With RDP, such fusion is feasible (shown in the below code snippet). This fusion significantly reduces intermediate result materialization requirements.
Switch), for which, it needs to call the Merge function to merge analysis results from multiple control-flow paths (Line 9 to Line 10), and ii) Input Shape Determined Output nodes, for which, it assigns a symbolic constant to the value map to facilitate subsequent analysis (Lines 16 to 18). Alg. 1 continues processing nodes in G until no updates happen on any node's shape-/value-maps. Similarly to other data-flow analysis, RDP follows Lattice Theory [28], so an optimized chaos implementation (based on worklist) is guaranteed to converge.
Though fusion has been a successful optimization on DNNs [46], it is also known to be very hard to implement on dynamic DNNs [57].
A frequent issue is that without knowing the tensor shape of two operators, the DNN compiler either cannot fuse them at all or has to generate a large number of code versions, each for a possible combination of shapes for the two operators. In fact, as often more than two operators are merged, the possible combinations for which separate code should be generated increase rapidly. Our proposed RDP analysis can address this issue by using (possibly symbolic) shape information. Information such as the two operators having tensors of the same shape can enable and/or simplify fusion, even if the exact dimensions are not known till runtime.
Figure 4 shows a simplified example with two common DNN operators (Sigmod and Add) on tensors with shapes not known till runtime. Sigmod takes an input tensor A with a dynamic shape of [I', J', K']. Add performs an element-wise addition on Sigmod's output and another input tensor B, whose shape happens to be [I, J, K]. Now, if A and B are of different shapes, a shape broadcast operation on the output tensor of Sigmod needs to be conducted immediately before the element-wise addition. Without our RDP analysis, the dynamic shape of A and B (and the possible shape broadcast operation) prevents the DNN compiler from fusing these two operators in an efficient way, i.e., the compiler either generates code without fusion (as shown in the blue box of Figure 4), or generates multiple code versions (8 versions for this example) and selects a version during the runtime. Assuming our RDP analysis result is I' = I, J' = 1, and K' = 1, i.e., a mix of symbolic constant (I) and known constant, the DNN compiler can further generate a unique version of fused code (as shown in the green box of Figure 4). SoD 2 incorporates RDP and the above operator fusion based on RDP into a state-of-the-art operator fusion for static DNNs (DNNFusion [46] ) to generate the fusion plan and optimized fused code.
A computational graph (DAG) typically allows for several different orderings for the execution of operators. The choice of ordering has an impact on the peak memory usage (for intermediate results), which further has consequences for cache performance and the execution latency. There has been previous work on this problem, which has in fact shown that generating an optimal execution plan (by a metric like memory consumption) is an NP-complete problem [2]. Thus, choosing an optimal plan can be difficult for modern large DNNs with hundreds or even thousands of operators.
The dynamic properties (e.g., dynamic shapes and control flow) further complicate this problem. In SoD 2 , we develop a series of heuristics driven by the use of proposed RDP analysis. The overall idea is that since a globally optimal solution is almost infeasible, an approach based on graph partitioning is justified. It turns out that the results of RDP are able to guide both graph partitioning and choice of solution within each sub-graph. Particularly, we observe that known constants, symbolic constants, op-inferred constants, and § or nac progressively increase the impediment on the generation of an optimal execution plan. More specifically, for a sub-graph sg with a limited number of operators:
First, if the shape of all tensors in sg are known constants, the optimal execution plan for sg can be obtained statically by an exhaustive search -a limited size of sg can further make such a search feasible. Second, if the shape of tensors in sg are mixed known constants, symbolic constants, and op-inferred constants, it is still possible to compare the memory requirements and thus generate a (close to) optimal execution plan. This is especially true if these shapes are derived from the same set of symbolic constants. Third, if an operator has an nac output tensor shape, it disables further analysis and execution planning. Such operators, it turns out, provide an opportunity to partition the original graph into sub-graphs that can be independently analyzed.
4.4.1 Memory Allocation Plan. Besides execution (order) planning, memory planning of DNNs is also a critical step [2,51]. A memory allocation plan, which decides where in a linear memory space each intermediate tensor is allocated, and when it is deallocated, can restrict peak memory usage and improve execution performance -the latter by reducing memory fragmentation, avoiding memory movement, and limiting memory allocation/de-allocation. In contrast to execution planning that (even for dynamic DNNs) can be carried out at compilation time, memory planning for dynamic DNNs can only be performed at execution time when all tensor sizes are known. Memory planning of static DNN execution has also been proved NP-complete [2], while DNN model dynamism further complicates memory planning.
Existing memory planning methods for dynamic DNN execution (e.g., Nimble [57]) have addressed this. Without knowing the exact tensor shapes, the methods usually rely on a greedy strategy [51], (e.g., finding the minimal memory slot currently available that can hold the new tensor). In comparison, we use RDP results and the following two key insights. First, we base our approach on subgraphs generated by our static execution planning method. It turns out that for sub-graphs with known constant shapes, as well as those with symbolic/op-inferred constant shapes that are defined solely by the input tensor of the sub-graph, the peak memory requirement can be inferred from static RDP analysis results and subsequent execution plan generation.
Second, we have observed that for most sub-graphs, the memory requirement decreases monotonically in both forward and backward directions from the location in the graph with peak memory usage. Therefore, initiating memory planning from the peak memory consumption location and traversing in the forward and backward directions, and picking the available memory slots for reuse works as a good strategy, and does not lead to the need for extra memory space.
Based on these insights, a lightweight greedy approach that starts from the peak memory requirement location can help to find optimal memory usage for many/most sub-graphs. Our evaluation (details omitted because of space limits) on ConvNet-AIG [62] shows that our RDP-based memory allocation plan requires 1.05× of optimal peak memory consumption (that results from an exhaustive search); while the one based on the greedy strategy mentioned above (MNN) requires 1.16× of optimal peak memory consumption.
As we discussed in Section 4.2, RDP analysis enables and/or simplifies operator fusion by revealing (possibly symbolically) tensor shapes. In cases where a single (fused) version is not feasible, one of the advantages of the information obtained through RDP is that the number of different versions of the fused code generated can be reduced significantly.
SoD 2 further benefits from this property of RDP by generating multi-version code to optimize hotspot operators (e.g., CONV and GEMM) that dominate the DNN execution. Prior efforts [1,26] have shown that the optimization opportunities for these operators depend on the shapes and sizes of the input/output tensors. Therefore, for static DNN executions, existing frameworks (such as TensorFlow Lite [1] and MNN [26]) usually employ multi-version codes that involve different optimizations (e.g., tiling, unrolling, choice of the number of thread blocks, etc.). However, this optimization is challenging for dynamic DNNs because an unknown tensor shape and/or tensor size implies that too many versions will be needed. The tensor shape (or shape relations) provided by RDP help to generate code for more specific tensor shapes only, thus resulting in fewer code versions.
More specifically, SoD 2 relies on an auto-tuner based on Genetic Algorithm to generate the exploration space (e.g., tiling shapes, loop permutation, and unrolling settings) for kernel code generation as DNNFusion [46]. One feature of this auto-tuner is the more effective exploitation of parallelism available in the hardware. To tackle the challenge of dynamic shapes, SoD 2 employs a multi-version approach, where the versions are chosen based on empirical evidence relating to the impact of different shapes on performance. For instance, our auto-tuner considers fat, regular, and skinny matrices for both GEMM and CONV kernels.
SoD 2 is implemented by extending an existing DNN execution framework (DNNFusion [46]) that supports static DNN execution only. This section evaluates the performance of SoD 2 by comparing it with four state-of-the-art frameworks. These frameworks are ONNX Runtime (ORT) [12] (V1.14.1), MNN [26] (Vdcb080c), TVM [5] w/ Nimble extension (TVM-N) [57] (V7831a79), and TFLite [1] (V2.11.1). ORT, MNN, and TVM-N support shape dynamism, while for DNNs with control flow, they execute all possible branches and strip out invalid ones. For fairness, this section also shows a performance comparison between SoD 2 and MNN by disabling SoD 2 's <Combine, Switch> control-flow support and adopting the same "execute-all, strip-out-invalid" strategy. TFLite supports dynamic input shapes with memory re-initialization; however, it cannot run most of our dynamic models properly because it usually fails on some input shapes. It does not support dynamic control flow either as required by most of the models we target. Thus, we use TFLite as a baseline for comparing DNN executions with fixed inputs and paths only.
Our evaluation has four objectives: 1) demonstrating that SoD 2 outperforms other frameworks with respect to both memory requirements and execution latency (Section 5.2), 2) studying the performance effect of our key optimizations based on RDP (Section 5.3), 3) further confirming the performance advantage of SoD 2 by evaluating it under different situations (Section 5.4), and 4) showing that SoD 2 performs well on different mobile platforms (i.e., SoD 2 has good portability).
Dynamic Models and Datasets. Our evaluation is conducted on three types of dynamic models: 1) models with shape dynamism, 2) models with control-flow dynamism, and 3) models with both shape and control-flow dynamism. The first category comprises five cutting-edge DNN models, which are StableDiffusion [56] (covering the Encoder part, referred to as SDE), SegmentAnything [29], Conformer [20], CodeBERT [16], and YOLO-V6 [36] (referred to as YL-V6). The second category includes DGNet [37]. The third category consists of four models, including SkipNet [63] (referred to as SNet), ConvNet-AIG [62] (referred to as CNet), RaNet [68], and BlockDrop [65] (referred to as BDrop).
Table 5 characterizes these models by showing the nature of dynamism, target input types, model size, and the total number of layers. Because the choice of training datasets has a negligible impact on the final inference latency or memory consumption (since the model size and structure are the same), this section reports results from one training dataset for each model. StableDiffusion-Encoder, SkipNet, DGNet, ConvNet-AIG, RaNet, and BlockDrop are trained on Ima-geNet dataset [9]; YOLO-V6 is trained on MS COCO dataset [40]; SegmentAnything is trained on SA-1B dataset [29]; CodeBERT is pre-trained on [10]; and finally, Conformer is trained on Librispeech dataset [49]. Since the model accuracy is the same across all frameworks, our evaluation focuses only on execution time and memory consumption. Test Samples and Setup. Our inference performance evaluation randomly selects 50 input samples from the corresponding validation dataset for each model. Specifically, for models that take images as input, i.e., YOLO-V6, SkipNet, ConvNet-AIG, RaNet, and Block-Drop, our evaluation randomly selects 50 input images from the ImageNet dataset, with the size of dimensions ranging from 224 to 640. DGNet does not support dynamic input shapes, but it does support dynamic control flow. Therefore, we only tested images with a dimension of 224 for DGNet. As YOLO-V6 only accepts images with dimensions that are multiples of 32, only a subset of inputs could be used. For StableDiffusion-Encoder and SegmentAnything, the 50 randomly selected input images have dimensions ranging from 64 to 224. For CodeBERT and Conformer, our evaluation randomly selects 50 input samples with sequential lengths ranging from 32 to 384. ⋆ This normalized geo-mean execution latency is calculated by 1) averaging the execution latency of runs with all input samples for each model, 2) calculating the geo-mean of the average execution latency of all models, and 3) normalizing with SoD 2 's geo-mean execution latency.
The experiments are performed on a Samsung Galaxy S21 smartphone powered by a Snapdragon 888 processor [53]. This processor features an octa-core Kryo 680 CPU, comprising one large core, three middle cores, and four small cores, and a Qualcomm Adreno 660 GPU with 1024 ALUs. Additionally, to demonstrate the portability of our approach, SoD 2 is also tested on an earlier generation of Snapdragon platform with more constrained resources, specifically the Snapdragon 835 [52] equipped with a Qualcomm Kryo 280 octa-core CPU, consisting of four middle cores and four small cores, and a Qualcomm Adreno 540 GPU with 384 ALUs. Our evaluation employs 8 threads on mobile CPUs and pipelined execution on mobile GPUs. The GPU execution uses a 16-bit floating-point representation, while the CPU execution uses a 32-bit floating-point representation. Each experiment is executed 50 times and only the average numbers are reported -as the variance was negligible, it is not reported for readability.
This section focuses on the end-to-end memory reduction and execution latency gains of SoD 2 . Overall Memory Consumption Comparison. Table 5 presents a comparison of end-to-end memory consumption on a mobile CPU using SoD 2 , ONNX Runtime (ORT), MNN, and TVM with Nimble extension (TVM-N). As the results on mobile GPU show a similar trend, they are not included here. '-' implies that a model is not supported by a given framework. The 'Min' and 'Max' columns indicate the minimum and maximum memory consumption (excluding the memory for holding the model itself because this part is the same for all frameworks). The last row of the table shows the geometric mean memory consumption of each framework normalized by SoD 2 . Its detailed calculation method is shown below the table and is over the cases where execution is possible. Among other frameworks, only MNN can support Conformer. SegmentAnything is not supported by other frameworks as either certain key operators are missing, and/or there are limitations in optimization, leading to large model execution footprints.
Table 7: Latency impact of input distribution on YOLO-V6. Each cell shows the latency speedup of SoD 2 over a corresponding baseline of ORT, MMN, or TVM-N.
Compared with other frameworks, SoD 2 has significantly lower memory consumption. Specifically, ORT, MNN, and TVM-N need to use 3.64×, 1.37×, and 8.62× memory, respectively, over SoD 2 . SoD 2 results in a greater reduction in memory consumption for image models (compared to other models) because image models generally have larger memory footprints, allowing for more significant optimization opportunities. It is worth noticing that TVM-N executes models as its own Android RPC application, which is one of the causes of higher memory requirements. Overall Latency Comparison. Table 6 presents a comparison of end-to-end latency for SoD 2 against other frameworks on both mobile CPU and GPU. The table includes the minimum and maximum latency observed across different input samples for each model. On mobile CPU, SoD 2 achieves an average speedup of 2.5×, 1.7×, and 2.7× compared to ONNX Runtime, MNN, and TVM-N, respectively. TVM-N does not support dynamic models on a mobile GPU. Compared against the other two frameworks on mobile GPU, SoD 2 achieves a speedup of 3.9× and 2.3× over ORT and MNN, respectively. Notably, the minimum latency achieved by SoD 2 on mobile GPU is significantly lower than other frameworks for ConvNet-AIG, RaNet, and BlockDrop models. This is because our optimizations can handle different cases and mitigate the effect of execution path variations. It is worth pointing out that the distribution of inputs could impact results. However, it does not change our conclusion. To show this impact more explicitly, we conduct a set of experiments on YOLO-V6 by selecting 50 input samples from different percentiles ranging from 1st to 100th, and our results are as shown in Table 7.
This section studies the individual impact of the key optimizations in SoD 2 on both memory consumption and latency. Memory Reduction w/ Different Optimizations. Figure 5 evaluates the memory reduction achieved through different optimizations for 4 models (StableDiffusion-Encoder, CodeBERT, RaNet, and BlockDrop), including RDP-enabled operator fusion (Fusion), static execution planning (SEP), and dynamic memory planning (DMP). The results for other models exhibit a similar trend and are excluded due to space limitations. The baseline version is referred to as No opt -despite the name, it includes general static optimizations, such as static operator fusion and constant folding. Building on this version, we study the benefits of optimizations enabled by RDP analysis. On mobile CPU, operator fusion, static execution planning, and dynamic memory planning bring 18% to 30%, an extra 22% to 37%, and another extra 3% to 7% memory reduction, respectively. Multi-version code generation (MVC) is primarily designed for latency improvement, its impact on memory reduction is negligible. The memory reduction on mobile GPU is omitted because our optimizations are general to both CPU and GPU, and the results are similar. Latency Reduction w/ Different Optimizations. Figure 6 presents the speedup breakdown of our key optimizations on the same 4 models. On mobile CPU, our RDP-based operator fusion yields 1.3× to 1.9× speedup compared to No opt. Additionally, static execution planning provides 1.1× to 1.3× speedup, and dynamic memory planning gains 1.04× to 1.1× speedup, and Multi-version code generation brings an extra 1.3× to 1.6× speedup. On mobile GPU, these numbers are 1.4× to 2.3×, 1.2× to 1.3×, 1.06× to 1.2×, and 1.4× to 1.7×, respectively. Our optimizations provide more benefits for mobile GPU since GPU is more sensitive to memory and data movement and supports a higher degree of parallelism. We further study each optimization with more profiling results. RDP-enabled Operator Fusion. Figure 7 further breaks down the effect of existing operator fusion for static DNNs only (SFusion) and our RDP-enabled operator fusion (RDP Fusion) on these four dynamic DNNs. These results are normalized by the original DNN without fusion (Original). SFusion reduces the layer counts by 26% to 61%; while RDP Fusion further reduces the layer counts by 16% to 46% additionally by leveraging RDP analysis results.
In terms of intermediate result (IR) size, RDP Fusion saves an additional 13% to 40% on top of SFusion. Subgraph Data. To better understand execution and memory planning, this part studies how many sub-graphs can benefit from RDP analysis results. Figure 8 (a) shows the percentage of different subgraphs, i.e. those with all known constant shapes, with mixed constant shapes, and with statically unknown (nac) only for 2 representative models. The numbers (1, 2-4, and 5-8) after Mixed const denote the number of code versions that are required to optimize this sub-graph (the lower the better). This result shows that over 90% of the sub-graphs belong to all known constant or mixed constant categories whose execution plan and memory plan can be optimized by our framework. To further confirm this, Figure 8 (b) shows the latency percentage of each kind of sub-graphs.
This section further studies SoD 2 under different cases.
Latency Comparison with the Same Execution Path. To provide an apple-to-apple comparison for control-flow dynamism, this test disables the control-flow logic in 4 models (SkipNet, RaNet, ConvNet-AIG, and BlockDrop) that have control-flow dynamism.
Our execution included all paths, including all branches in the <Switch, Combine> pairs. Figure 9 11 presents a latency comparison between SoD 2 and TFLite with the same memory budget. Specifically, TFLite fixes its memory consumption to match SoD 2 's, and uses the XLA rematerialization policy [19] to handle the out-of-memory cases. SoD 2 outperforms TFLite by an even greater margin. Additionally, SoD 2 demonstrates a higher speedup on mobile GPU compared to mobile CPU due to the longer time required for mobile GPU to materialize intermediate tensors from its cache into main memory because of memory mapping.
Latency Comparison with Static Models. Figure 12 examines the latency overhead of SoD 2 in contrast to our baseline, DNNFusion [46], for static models. Specifically, we evaluate the latency in SkipNet and RaNet where dynamic values were fixed statically and fully propagated, ensuring the absence of unknown values and dynamic control flows. As shown in Figure 12, SoD 2 incurs an average overhead of 3% and 7% performance slowdown when compared to the completely optimized static DNNFusion. This is attributed to the fact that DNNFusion, with full information available, results in a more comprehensive fusion optimization and does not include dynamic memory planning overhead.
To further investigate the effectiveness of portability, Figure 13 shows the execution speedup of SoD 2 over other frameworks on another mobile device -Snapdragon 835, and 5 models (StableDiffusion-Encoder, YOLO-V6, SkipNet, ConvNet-AIG, and BlockDrop). SoD 2 achieves similar speedup trends, and interestingly, it achieves higher speedups on this earlier generation of SoC because this SoC has more restricted resources (e.g., cache size and memory throughput).
The RDP-based optimizations employed in SoD 2 significantly reduce memory requirements, leading to improved performance on these platforms.
Dynamic Neural Network Optimizations. Type analysis and type inference [8,22,33,44,58] are widely used to analyze tensor shapes, thus assisting in Dynamic Neural Network optimizations. Nimble [57], which has been integrated into TVM, is a compilation-based Dynamic DNN framework. This framework relies on expensive dynamic functions to interpret dynamic shapes at the runtime. This implementation, which we have extensively compared against, limits the opportunities for optimized code generation, such as performing operator fusion. DISC [74] extends MLIR-HLO [33] and propagates the shape information for operators that have certain constraints, e.g. same dimensions ( the case of Activation) and same size (the case of Transpose). SoD 2 provides a more comprehensive operator classification based on dynamism degrees, bringing in significantly enhanced optimization opportunities. Axon [6] is a programming language that allows specification of symbolic shapes for input and output tensors for computational graphs. It uses a constraint solver to find shapes whereas SoD 2 uses a forward and backward dataflow analysis (RDP), which also alleviates additional programmer involvement. In addition, SoD 2 includes a set of opts enabled by RDP.
Less closely related to SoD 2 , DietCode [73] proposes an autoscheduler framework based on TVM for dynamic shapes. The framework builds a cost model to predict runtime performance and reduces the search space to find optimal runtime parameters (e.g., loop tiling). Cortex [15], Cavs [67], and another effort [25] mainly aim to address recursive dynamism of neural networks, different from SoD 2 's focus. Other efforts focus on dynamic batching for inference [14,17,41,72] or are designed for dynamic DNN training [45]. DNN Execution and Memory Optimizations. Several studies exist for operator execution order scheduling, such as [2,38,39]. Among these efforts [38,39] focus on minimizing peak memory consumption by reordering operators for resource-constrained devices (e.g., MCUs), and effort [2] proposes an optimized scheduling framework for complex models (irregularly wired neural networks). These approaches rely on static shapes only. There have aldo been recent efforts on optimizing memory allocation planning and memory management for DNNs. Works such as [35,51] have designed various heuristic memory planning algorithms for static DNNs only. Tela-Malloc [43] performs memory management on the fly for static control-flow graphs with known intermediate tensor shapes and sizes. It does not fully consider the DNN control-flow dynamism and dynamic shapes. A possible future work can be to integrate our RDP analysis and TelaMalloc's combination of heuristics with a solver-based approach to further improve our memory planning. When the available memory is limited, rematerialization [24,30] and recomputation [3] methods achieve a trade-off between memory consumption and execution latency. These aspects can be considered for dynamic DNNs in the future. DNN Inference Engines on Mobile. Support for DNN inference on mobile devices has become an area of active research in recent years. Efforts such as MCDNN [21], DeepX [32], DeepMon [23], DeepSense [69], and DeepCache [66] have primarily concentrated on optimizing the execution of static DNNs with static shapes and control flow. TensorFlow Lite (TFLite) [1], Pytorch-Mobile [50], TVM [5], and MNN [26] provide support for dynamic shapes relying on reinitialization or conservative (maximum) memory allocation. They either do not support dynamic control flow or require executions of all paths with a stripping of invalid results. As shown in our evaluation, these methods introduce high runtime overhead. One of the previous systems for static DNNs, DNNFusion [46], also involved a classification of DNN operators, however, the classification introduced here is orthogonal.
Generalizing to Other Platforms. The proposed techniques, such as RDP analysis, RDP-enabled fusion, and execution and memory planning, have broad applicability to various platforms, including data-center GPUs. This is particularly true for single-input inference scenarios. One potential nuance that may arise is the distinction between data-center GPUs and mobile GPUs in terms of their ability to perform batched inference. Unlike mobile GPUs, data-center GPUs have the capacity to process multiple inputs concurrently, thereby maximizing their computational power. However, it is possible that different input samples within a batch may necessitate the use of different execution paths. Therefore, the integration of dynamic batching with dynamic neural networks presents a potential direction for future research. Scalability of Handling LLMs. The optimizations in SoD 2 can also be applied to massive large language models (LLMs). One of the primary procedures we employ is graph partitioning, as elaborated in Section 4.3. This procedure involves dividing the entire computational graph into a collection of sub-graphs, each of which encompasses a restricted number of layers. The optimal solution is determined offline for each sub-graph. However, Language Models (LLMs) have been characterized by an incredibly large number of parameters, numbering in the billions [7,60,70]. This poses a significant challenge for mobile devices in terms of computation and resource requirements. Our future work will enhance SoD 2 by combining it with the model pruning and quantization advances [27,47,64] to achieve an even better performance. Extending beyond ONNX. Operator classification and associated optimization designs are also not limited to ONNX or other inference formats (e.g., TFLite, Caffe2). This is because our proposed analysis is based on the degree of dynamism defined by the computation logic of an operator and the relationship between its input and output, rather than relying on the specific representation or format of the operator. Some formats have yet to fully support dynamic computational graphs. For instance, PyTorch supports exporting models with dynamic shapes (such as Input Shape Determined Output, Input Shape Determined Output Shape, and Input Shape & Value Determined Output Shape) to ONNX. However, it is unable to convert models with dynamic control flow to ONNX. To address this limitation, we added a customized ONNX operator pair <Switch, Com-bine> (as shown in Figure 1d) and registered a customized export routine on PyTorch specifically for models with a dynamic control flow. SoD 2 does have limitations in handling very complicated (or user-defined) dynamic models (such as Graph Neural Networks or DNNs involving recursive executions) that can be represented well in PyTorch. We leave this further optimization as a future work.
This paper has presented a comprehensive framework, SoD 2 , for optimizing DNNs. SoD 2 classifies common operators of Dynamic DNNs into four types, and comprises a novel static dataflow analysis (RDP). This is followed by a set of optimizations enabled by RDP for Dynamic DNNs, including operator fusion, static execution (order) planning, dynamic memory allocation planning, and multi-version code generation. SoD 2 is extensively evaluated on a mobile system with 10 emerging dynamic DNNs and the evaluation results show that it saves up to 88% memory consumption and brings up to 3.9× execution speedup over four state-of-the-art DNN execution frameworks. As the underlying techniques are general and applicable to other devices as well, our future work will evaluate SoD 2 's efficacy on other devices (e.g., edge GPUs and Raspberry Pi).