Opara: Exploiting Operator Parallelism for Expediting DNN Inference on GPUs

After being scheduled on GPUs, a DNN operator is actually recognized as a kernel. In general, a kernel comprises multiple thread blocks, which are the smallest scheduling granularity in CUDA. A thread block is scheduled to a Streaming Multiprocessor (SM) once the SM has sufficient resources to meet its resource demands [14]. In particular, an SM can concurrently execute multiple thread blocks, and each SM is constrained by a limited number of threads, shared memory, and registers.

To enable parallel executions of operators, we launch operators on multiple CUDA Streams. Each stream is actually a task queue that executes tasks sequentially. The execution order of kernels in different CUDA Streams is determined by their arrival order at the stream head. In general, the kernel execution time is considerably short as the batch size is typically small (i.e., ranging from $1$ to $16$) in latency-critical inference scenarios [15, 9]. Accordingly, the kernel launch overhead constitutes the primary time cost for DNN inference, which negatively impacts the performance gains achieved by the parallel executions of kernels in multiple CUDA Streams. To reduce such overhead, CUDA Graph is a key feature introduced from CUDA 10 that allows scheduling multiple DNN operators on a GPU device at a time.

Mainstream DL frameworks execute DNN operators sequentially in topological sorting order, which cannot fully utilize GPU resources. To illustrate that, we conduct motivation experiments using the stock PyTorch 2.0 and ONNX Runtime 1.12¹¹1https://onnxruntime.ai/ with the operator fusion [9] enabled. We serve three typical DNN inference models including GoogLeNet²²2https://pytorch.org/hub/pytorch_vision_googlenet/, Inception-v3 [5], and BERT³³3https://huggingface.co/google-bert on both an NVIDIA A100-PCIE-40GB GPU and an NVIDIA RTX 2080 SUPER GPU. In particular, we adopt the SM efficiency measured using NVIDIA Nsight Compute CLI⁴⁴4https://docs.nvidia.com/nsight-compute/NsightComputeCli/index.html to evaluate the GPU utilization.

As shown in Fig. 2, DNN inference on the mainstream DL frameworks achieves relatively low to medium GPU utilization even with the operator fusion technique enabled. Specifically, the SM efficiency of GoogLeNet, Inception-v3, and BERT with the batch size as $1$ is merely $2.53\%$, $12.04\%$, and $18.5\%$, respectively, achieved in the stock PyTorch on an A100 GPU. Even when the batch size is increased to $16$ and serving DNN inference in the ONNX Runtime, the SM efficiency of the three workloads is moderately increased to $57.21\%$, $39.9\%$, and $76.37\%$, respectively. Moreover, we repeat our experiments on a less powerful GPU (i.e., RTX 2080 SUPER), and the SM efficiency of the three workloads ranges from $10.47\%$ to $82.98\%$. Such experiment results above indicate that (1) the sequential execution of DNN operators is the root cause of low GPU utilization for serving DNN inference; (2) The operator fusion technique can only combine a certain number of parallelizable operators based on the pre-defined fusion rules [9], resulting in moderate GPU utilization. Accordingly, there still exists enough room to exploit the operator parallelism for improving the GPU utilization of DNN inference on GPUs.

Apart from the sequential execution of DNN operators, the inadequate operator launch order (i.e., the topological sorting order of the model DAG) in mainstream DL frameworks can also lead to idle GPU resource usage and performance interference, thereby prolonging the inference latency. We conduct two motivation experiments to identify why the operator launch order can impact the inference latency.

GPU blocking. As each operator has a different number of blocks requiring three types of resources for execution, i.e., threads, shared memory, and registers, a resource-unaware operator launch order can easily block the execution of operators until enough resources become available on the GPU. Such GPU blocking can severely waste the available GPU resources. As shown in Fig. 2, changing the operator launch order from order $1$ (i.e., depth-first topological sorting) to order $2$ (i.e., Opara designed in Sec. 3) for GoogLeNet can reduce the inference latency by up to $29\%$ with different batch sizes. Furthermore, we repeat such an experiment on the A100 GPU, and the experiment results show around $10.3\%$ of performance improvement by optimizing the operator launch order for GoogLeNet.

Performance interference. As the performance interference among operators can prolong the inference latency [8], we further conduct another experiment on A100 to illustrate the effectiveness of overlapping the execution of compute-intensive and memory-intensive operators in mitigating the inference. As depicted in Fig. 3 (case 1), prioritizing the parallel execution of ReLU and Conv operators can cause less severe interference, compared with parallelizing two ReLU operators, leading to a $13.6\%$ reduction in the inference latency. Similarly, prioritizing the launch order of Add operator in case 2 can increase the inference performance by $12.7\%$, simply because the execution of compute-intensive and memory-intensive operators is overlapped.

Summary. Low GPU utilization of DNN inference is mainly caused by two factors: First, the sequential execution of DNN operators cannot fully utilize the GPU resources, even with the operator fusion enabled. Second, the default topological sorting order of operator launch is commonly resource- and interference-unaware. Accordingly, judiciously parallelizing DNN operators with an adequate operator launch order is compelling for accelerating DNN inference on GPUs while improving the GPU utilization.

To parallelize the execution of operators in CUDA Streams, we leverage the computation graph (i.e., DAG) of DNN models to determine how many streams to launch and how to allocate operators to the streams.

Definition of a model DAG. DNN computation graph can be represented as a DAG $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ denotes the set of operators in the model, and $\mathcal{E}$ denotes the operator dependencies. Each vertex ${v}\in\mathcal{V}$ denotes a DNN operator (e.g., Conv, MaxPool). Each edge $\langle u,v\rangle\in\mathcal{E}$ denotes the operator dependency, where $u$ is a predecessor of ${v}$ and ${v}$ is a successor of ${u}$. The set of all predecessors of an operator ${v}$ are denoted as $\mathcal{N}_{pred}$. The set of all successors of an operator ${v}$ are denoted as $\mathcal{N}_{succ}$.

Problem formulation and analysis. As a maximum of $|\mathcal{V}|$ streams can be launched for a DAG, we simply use a matrix $\mathcal{A}$ of size $|\mathcal{V}|\times|\mathcal{V}|$ to represent the stream allocation plan, which determines how the DNN operators are parallelized and synchronized. Each element $a_{ij}\in\mathcal{A}$ is a boolean value, indicating whether the $i$-th operator is executed in the $j$-th stream. We formulate the inference latency $T_{inf}$ as

where $T_{para}$ denotes the parallelized execution time of a DNN model and $T_{overhead}$ denotes the operator synchronization overhead given a stream allocation plan $\mathcal{A}$. In more detail, as the plan $\mathcal{A}$ can parallelize the execution of DNN operators, $T_{para}$ can further be formulated as

where $T_{seq}$ denotes the inference latency of sequential execution of DNN operators and $h(\mathcal{A})\in(0,1]$ denotes the inference acceleration factor achieved by operator parallelism with the plan $\mathcal{A}$. To ensure the parallelized execution of the model, a certain number of synchronization operators [16] require to be inserted into the model DAG. Such a process introduces significant operator synchronization overhead $T_{overhead}$, which can be formulated as

where $t_{overhead}$ is the time overhead caused by one synchronization operator and $g(\mathcal{A})$ is positively correlated with the number of synchronization operators in approximation.

By substituting Eq. (3) and Eq. (2) into Eq. (1), we aim to minimize the inference latency $T_{inf}$ by identifying an optimal stream allocation plan $\mathcal{A}$. Accordingly, we formulate the stream allocation optimization problem as

where Constraint $(\ref{cons-operator-placement})$ mandates that each operator must be allocated to and only to one stream. $t_{overhead}$ and $T_{seq}$ can be considered as constant values given a DNN model. Actually, our optimization problem in Eq. (4) (i.e., minimizing $h(\mathcal{A})$ and $g(\mathcal{A})$) can be considered as scheduling DAGs with dependency constraints (i.e., adjusting the matrix $\mathcal{A}$) to minimize the makespan, which has been proven to be an NP-hard problem [17]. Accordingly, we turn to devising a heuristic algorithm to acquire an appropriate (i.e., sub-optimal) solution to our stream allocation problem.

Stream allocation algorithm. The key idea of Alg. 1 is to allocate parallelizable operators to multiple CUDA Streams as much as possible (i.e., minimizing the value of $h(\mathcal{A})$). Moreover, we greedily put non-root nodes (i.e., operators) in the same CUDA stream as one of their predecessor operators, so as to avoid excessive synchronization operators (i.e., minimizing the value of $g(\mathcal{A})$). Specifically, given a computation graph $\mathcal{G}$, Opara first initializes a set of streams to be launched $\mathcal{S}$ and the $\mathtt{SYNC}$ $flag$ of each $v\in\mathcal{V}$. It then enumerates operators in $\mathcal{V}$ in topological sorting order (lines $1$-$2$). For each operator ${v}\in\mathcal{V}$, it iterates over all of its predecessors $p\in\mathcal{N}_{pred}$ (line $3$). If the current predecessor $p$ has not yet contributed to reducing the synchronization overhead (i.e., $flag$ is $\mathtt{False}$), it allocates $v$ to the same stream of $p$, and set the $flag$ of $p$ as $\mathtt{True}$ (lines $4$-$7$). If $v$ does not find a predecessor that satisfies such a condition above, we allocate the operator $v$ to a newly launched stream (lines $8$-$10$). In particular, the parallelized execution of streams does not impact each other as long as operators are not executed on GPUs. To ease the understanding of Alg. 1, we present an illustrative example in Appendix .1.

As discussed in Sec. 2.3, the blocks in an operator execute the same instructions even with different data, which indicates that the GPU resources required by the blocks in an operator are the same. Accordingly, we obtain the resource demands of each operator by simply profiling the resource consumption (i.e., the amount of shared memory, the number of registers and GPU threads) of a block in an operator. Such resource demands of operators will be used by Operator Launcher to determine an adequate operator launch order. In particular, we implement our Model Profiler utilizing the torch.profiler.profile() API, and it requires profiling each DNN inference only once to acquire the resource demands information for each operator, thereby bringing acceptable profiling overhead. We will examine the inference profiling overhead of Opara in Sec. 5.3.

Problem analysis. As illustrated in Sec. 2.3, inadequate operator launch orders can significantly affect the DNN inference latency. To identify an optimal launch order, a naive solution is iterating through all possible topological sorting orders of a model DAG and choosing the order with the lowest inference latency. However, such a method involves selecting nodes with zero indegree and deleting the corresponding vertices and their connected edges. By assuming $n$ operators exist in a model DAG, the time complexity of traversing all topological sorting orders is $\mathcal{O}(n!)$, which is also an NP-hard problem [17]. As a result, we turn to designing a heuristic operator launch algorithm to solve such a complex problem.

Resource- and interference-aware operator launch algorithm. Launching operators with heavy resource demands first to the GPU is likely to cause resource fragmentation, hindering the GPU executions of subsequent operators. Moreover, the GPU can thus be blocked due to the non-preemptive feature of kernel execution [12]. To maximize the GPU utilization, the key idea of Alg. 2 is to greedily prioritize launching the operators with the least amount of GPU resource demands, aiming at maximizing the parallel executions of multiple operators within a model. To further mitigate the performance interference among operators [8], we simply overlap the execution of compute-intensive operators and memory-intensive operators, as classified by our offline-collected operator table.

Specifically, it first initializes and maintains a priority queue $\mathcal{Q}$ of operators in resource- and interference-aware operator launch order (line $1$). It then retrieves all operators to be launched with an indegree of $0$ in a list $\mathcal{L}$, which alternates between the non-empty lists for memory-intensive operators $\mathcal{L}_{mem}$ and for compute-intensive operators $\mathcal{L}_{comp}$ (lines $2$-$4$). Each time the operator requiring the least amount of GPU resources (e.g., shared memory, threads, registers) is chosen from $\mathcal{L}$ and then put into the queue $\mathcal{Q}$ (lines $5$-$6$). In particular, the potential GPU blocking issue faced by the remaining large operators is noncritical in our scenario, as $\mathcal{L}$ is dynamic and can be compensated for the upcoming small operators to be launched. Finally, $\mathcal{L}_{mem}$ and $\mathcal{L}_{comp}$ are continuously updated by adding new operators with an indegree of $0$ (lines $7$-$13$).

To eliminate the overhead caused by kernel launches and function calls, the Graph Capturer first sets the CUDA Streams obtained from the Stream Allocator to the capture mode, and then it launches the operators of the DNN model to these streams according to the operator launch order specified by the Operator Launcher. To ensure the dependencies among operators, the Graph Capturer also launches the necessary synchronization operators to the streams. Consequently, a CUDA Graph is generated to enable operator parallelization while improving the GPU utilization. Such a graph capture process is lightweight and non-intrusive to PyTorch, as it has been exposed as a high-level API in PyTorch officially. We simply use the PyTorch API to capture and then generate the CUDA Graph.

Hardware configuration and workloads. We conduct our experiments on an NVIDIA A100-PCIe-40GB GPU and an NVIDIA GeForce RTX 2080 SUPER-8GB GPU. We implement Opara based on CUDA 11.7, cuDNN 8.5.0, and as a plug-in module of PyTorch 2.0. Our experiments employ $6$ representative DNN models, including Inception-v3 [5], GoogLeNet, DeepFM [18], NASNet⁵⁵5https://huggingface.co/timm/nasnetalarge.tf_in1k, BERT, and T5⁶⁶6https://huggingface.co/google-t5. The first three models are executed on the RTX 2080 GPU, while the latter three are run on the A100 GPU.

Baselines and metrics. We compare DNN inference performance of Opara with that of the stock PyTorch (with CUDA Graph disabled), default sequential CUDA Graph, ONNX Runtime (with operator fusion enabled), Rammer [9], and Nimble [11]. Specifically, we implement Rammer’s BFS-based operator scheduling algorithm (named Wavefront) into PyTorch 2.0. Nimble transforms the computation graph into a bipartite graph and identifies its maximum matching to determine an appropriate stream for each operator. In particular, we focus on $4$ key metrics including DNN inference latency, SM efficiency, and GPU memory consumption, as well as DNN inference throughput. All the experiment results are averaged over $1,000$ runs.

End-to-end inference latency. As shown in Fig. 5, Opara consistently outperforms the five baselines for six representative DNN models. Specifically, Opara can achieve $1.80\times$ to $10.97\times$ speedup compared to the stock PyTorch. This is because Opara utilizes CUDA Graph to eliminate the operator launch and function call overhead. Opara surpasses the default CUDA Graph by up to $1.68\times$, simply because of the parallel execution of DNN operators in Opara. Though the operator fusion technique outperforms the stock PyTorch, Opara achieves a higher speedup by up to $2.97\times$ and $1.18\times$, compared with ONNX Runtime and Rammer, respectively. Such performance improvements above are mainly due to two facts: First, the operator fusion cannot combine all parallelizable operators based on the pre-defined fusion rules, which cannot fully utilize the GPU resources. Second, Opara accelerates model inference through operator parallelization, while the Wavefront scheduling algorithm in Rammer introduces additional synchronization overhead (i.e., the unnecessary operator waiting time during wave executions). Furthermore, Opara outperforms Nimble by up to $1.29\times$ because it judiciously alternates the scheduling of different types of operators with the lowest GPU resource consumption for each kernel launch time. Moreover, Opara initiates enough streams to increase parallelism (e.g., $28$ streams with Opara versus $4$ streams with Nimble for GoogLeNet), thereby maximizing the operator parallelism.

GPU utilization and memory consumption. To unveil the performance gains of Opara, we proceed to look into the GPU utilization (i.e., SM efficiency) and memory consumption during the model inference. As shown in Fig. 5, Opara exhibits a similar improvement in GPU utilization compared to the five baselines as in Fig. 5. Specifically, Opara significantly improves the GPU utilization compared to the stock PyTorch, because Opara mitigates the scheduling overhead of the stock PyTorch. When compared with the default CUDA Graph, Opara increases the GPU utilization of Inception-v3, GoogLeNet, DeepFM, NASNet, BERT, and T5 by $36\%$, $58\%$, $126\%$, $48\%$, $20\%$, and $19\%$, respectively. Such performance gains mainly come from the parallelized execution of operators. When compared to ONNX Runtime, Rammer, and Nimble, Opara boosts the GPU utilization by up to $3.86\times$, $1.36\times$ and $1.42\times$ mainly because (1) maximizing stream allocations in Opara can increase operator parallelism opportunities, and (2) optimizing the operator launch order in Opara further minimizes the GPU idle time. Furthermore, the parallel execution of operators requires an increased amount of data to reside in the GPU memory simultaneously, thereby leading to a higher peak GPU memory consumption of Opara than that of sequential executions.

Timeline of operator executions. We further illustrate the operator execution timeline by taking a segment of inference process of GoogLeNet as an example. In particular, we leverage NVIDIA Nsight System CLI⁷⁷7https://docs.nvidia.com/nsight-systems/UserGuide/index.html to track the timeline of operator executions. As depicted in Fig. 6, we observe that CUDA Graph executes the $4$ operators sequentially in a stream, and only operators $4$ and $1$ appear within the time window. The remaining operators $2$ and $3$ are forced to queue up, which leads to a long inference time. Though Nimble can parallelize operators in the order of $1$, $2$, $3$, and $4$, it only schedules $2$ operators on two streams, causing a long GPU idle time. In contrast, Opara prioritizes operator $4$ and initiates more streams than Nimble, so that operators $4$, $1$, and $2$ can be executed in parallel to maximize the operator parallelism. Accordingly, Opara can achieve the shortest inference latency by exploring operator parallelism compared with CUDA Graph and Nimble.

Effectiveness of Opara on Transformer-based models. We conduct experiments with T5 and BERT model, and Opara outperforms Nimble by $9.3\%$ for the T5 model as shown in Fig. 5. This is because Opara optimizes the launch order of operators in T5 and schedules them into $6$ streams compared with $3$ streams in Nimble. Moreover, the operator diversity in T5 offers Opara overlap the compute-intensive Arange operators and the memory-intensive To and Ones operators, as shown in Fig. 7(a). For BERT, however, Opara achieves a similar operator launch order and the same number of streams as Nimble as depicted in Fig. 7(b). This is because the parallelizable operators of BERT are always the Embedding operators or the Sgemm operators, which reduces the opportunity for operator overlapping and launch order optimization. Accordingly, Opara achieves marginal performance gains for BERT compared with Nimble, yet $1.08\times$ to $4.06\times$ speedup compared to the stock PyTorch and CUDA Graph as shown in Fig. 5.

Throughput under different batch sizes. As depicted in Fig. 9, we observe that Opara consistently surpasses the five baselines except for ONNX Runtime by varying the batch size from $1$ to $32$. Nevertheless, the performance gains of Opara gradually diminish as the batch size increases. As an example, Opara outperforms the default CUDA Graph by $1.41\times$ and $1.09\times$ when the batch size is $1$ and $32$, respectively. This is because the amount of GPU resources occupied by a single operator increases when dealing with larger batch sizes, resulting in fewer GPU resources available for the execution of parallelized operators. This also explains why Opara exhibits marginal throughput improvement for large batch sizes of $16$ and $32$. The results above also show that maximizing the operator parallelism can also improve the inference throughput.

Effectiveness of Opara on high-end GPUs with sufficient resources. We repeat the inference experiment of Inception-v3 on a high-end GPU (i.e., A100). As shown in Fig. 9, we observe that Opara consistently outperforms the five baselines by varying the batch size from $2$ to $32$, mainly because operator parallelism works well for high-end GPUs with sufficient resources. In more detail, Opara achieves an inference speedup by up to $2.08\times$, $1.29\times$, and $1.15\times$ compared to ONNX Runtime, Rammer, and Nimble, respectively. In particular, Opara achieves speedups of $1.47\times$ and $1.18\times$ relative to ONNX Runtime for batch sizes of $16$ and $32$, which is larger than the results achieved on the RTX 2080 GPU. This is because the A100 GPU provides sufficient resources, which allows the operator parallelism to achieve more performance gains than the operator fusion.

We evaluate the runtime overhead of Opara in terms of algorithm computation time and inference profiling overhead. As listed in Table I, Opara can reduce the computation time of the stream allocation algorithm by up to two orders of magnitude compared with Nimble [11]. This is because Nimble requires a graph transformation together with an exhaustive search in the bipartite graph. Such a process is time-consuming with a complexity in the order of $\mathcal{O}({n}^{3})$, where $n$ is the number of operators in a model DAG. In contrast, the time complexity of Opara can be reduced to the order of $\mathcal{O}({n})$, simply because the inner loop of Alg. 1 (lines $3$-$10$) in Opara only depends on the maximum width (i.e., typically below $20$) of the computation graph. Accordingly, as DNN models become increasingly complex [19], the number of operators $n$ gets even larger, while the algorithm computation overhead of Opara can still be well contained. In addition, as the Model Profiler needs to run the DNN inference only once, Opara requires several (i.e., $4.25$) milliseconds of profiling overhead in our experiment. In sum, the runtime overhead of Opara is practically acceptable.