ASPEN: Breaking Operator Barriers for Efficient Parallelization of Deep Neural Networks
Authors: Jongseok Park
Kyungmin Bin
Gibum Park
Sangtae Ha
Kyunghan Lee
Venue: NeurIPS 2023 poster (2023)
Keywords: Deep Neural Network
Deep Learning
Parallel Execution Algorithm
Parallelization
Deep Learning Parallelism
Dynamic
Asynchronous
Scheduling
Dynamic Scheduling
Dynamic Execution
tile
tiling
dataflow
dataflow graph
tile-based dataflow graph
opportunistic parallelism
TL;DR: ASPEN uncovers a novel source of parallelism in DNNs by breaking the synchronization barriers in operators and leverages them by letting each parallel resource dynamically locate and execute the fine-grained parallel computation opportunities.

Abstract: Modern Deep Neural Network (DNN) frameworks use tensor operators as the main building blocks of DNNs. However, we observe that operator-based construction of DNNs incurs significant drawbacks in parallelism in the form of synchronization barriers. Synchronization barriers of operators confine the scope of parallel computation to each operator and obscure the rich parallel computation opportunities that exist across operators. To this end, we present ASPEN, a novel parallel computation solution for DNNs that achieves fine-grained dynamic execution of DNNs, which (1) removes the operator barriers and expresses DNNs in dataflow graphs of fine-grained tiles to expose the parallel computation opportunities across operators, and (2) exploits these opportunities by dynamically locating and scheduling them in runtime. This novel approach of ASPEN enables opportunistic parallelism, a new class of parallelism for DNNs that is unavailable in the existing operator-based approaches. ASPEN also achieves high resource utilization and memory reuse by letting each resource asynchronously traverse depthwise in the DNN graph to its full computing potential. We provide challenges and solutions to our approach and show that our proof-of-concept implementation of ASPEN on CPU shows exceptional performance, outperforming state-of-the-art inference systems of TorchScript and TVM by up to 3.2$\times$ and 4.3$\times$, respectively.

ASPEN: Breaking Operator Barriers for Efficient Parallel Execution of Deep Neural Networks
Jongseok Park Seoul National University cakeng@snu.. kcr
Kyungmin Bin Seoul National University kmbin@snu ac. ac.kr kr
Gibum Park
Sangtae Ha
Kyunghan Lee Scoul National University kyunghanlee@ann eeeaan ac kr
Scoul National University gi gibumpark@snu.c ac
University of Colorado Boulder sangtae ha@colorado .dd
Abstract
Modern Deep Neural Network (DNN) frameworks use tensor operators as the main building blocks of DNNs. However, we observe that operator-basee construction of DNNs incurs significant drawbacks in parallelism in the form of synchronization barriers. Synchronization barriers operators confine the scope of parallel com- putation to each operator and obscure the rich parallel computation opportunities that exist across operators. To this end, we present ASPEN, a novel parallel com- putation solution for DNNs that allows fine- fine-grained dynamic execution of DNNs, which (1) removes the operator barriers and expresses DNNs in dataflow graphs fine-grained tiles to expose the parallel computation opportunities across operators, and (2) exploits these opportunities by dynamically locating and scheduling them in runtime. This novel approach of ASPEN enables opportunistic parallelism, new class of parallelism for DNNs that is unavailable in the cxisting operator-based based approaches. ASPEN also achieves high resource utilization and memory reuse by letting each resource asynchronously traverse depthwise the DNÑ graph its full computing potential. We provide challenges and solutions our ap- proach and show that our proof-of-concept implementation of ASPEN on CPU shows exceptional performance, outperforming state-of-the-art inference systems of TorchScript and TVM by up to 3.2x and 4.3x, respectively.
1
Introduction
Deep Neural Networks (DNNs) are dataflow graphs of artificial neurons, each of which computes mathematical function using the outputs of other artificial neurons as inputs. However, artificial neurons are rarely treated as individual units of computation, as their role as building blocks of neural networks has largely been replaced by tensor operators. tensor operator, or simply an operator, refers to large group of artificial neurons with the same functionality. These operators take inputs from the outputs of other operators, and the multi-dimensional arrays data transferred between the operators are referred to as tensors. Modern DNN frameworks, such as TensorFlow [1. PyTorch (35), and MXNet all utilize these operators as the main building blocks of DNNs, as grouping many identical artificial neurons into single computation unit allows for easier construction, representation, and execution DNNs that are becoming increasingly complex.
However, we find that the operator-based based expression of DNNs incurs significant drawbacks in parallelism. Grouping artificial neurons into operators separates the computation DNN into two hierarchical layers of inter-operator and intra-operator computations (30)) [51]. Inter-operator computations of a DNN represented by a dataflow graph of operators, and frameworks such as Tensorflow or PyTorch delegate the execution of each operator to vendor- provided DNN acceleration vendor-provided
libraries such as oneDNN 19 cuDNN (7) or ARMNN B These libraries handle intra-operator
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(a) Operator-based DNN Graph (b) Tile-based DNN Graph
(c) With Operator Barriers
(d) Without Operator Barriers
Full Scope of Computaton
Operator
Operator 2
Limited
Scope
Operator
7 Dependency unresolved
Dependency resolved
Scheduled Resource 1,
N-1. N Resource Computation Path
Figure I:
Depiction of DNN as (a) operator-based dataflow graph and (b) tile-based DNN dataflow
graph, and its execution using N parallel computation resources, (c) with operator barriers, and (d) without operator barriers.
computations by partitioning the computations of operator into fixed-shape computation units known as files [14 28, 30 [54,, that exploit key features of the hardware such as the number of registers, vector processing width, and cache sizes. For instance, oneDNN may partition single- precision matrix multiplication of 1024x 1024 square matrices into 16384 8 x 8 matrix multiplication tiles, which align with the vector width of 256-bit AVX2 registers of x86 CPUs. The tiles are then scheduled to the parallel processing resources of the given hardware, and the execution of an operator considered complete when all tiles have been computed by the parallel resources.
Unfortunately, this two-level exccution of DNNs inevitably introduces synchronization barrier between operators. As intra-level computations are treated as black boxes by DNN frameworks, synchronization barriers are necessary at the end of each operator execution to ensure that all computations within an operator completed before scheduling the next operator that depends on its predecessor [45]. These barriers make the computation flow simpler and the development of execution frameworks easier, but they also completely obscure the rich parallel computation opportunities that exist across the barriers.
For example, Figure (a) illustrates traditional operator-based dataflow graph of DNN at the inter-operator level. However, when we apply tile-wise partitioning at the intra-operator level and express the dataflow graph with tile-based granularity shown in Figure (b). we discover the presence of multiple parallel paths of computation across the operators. Unfortunately, the traditional two-level execution of DNNs depicted in Figure 1 (c) hinders the utilization of these computation opportunities, due to the synchronization barriers that confine the scope of computation within each operator. The synchronization barrier forces the resources to remain idle until all tiles within an operator are executed before allowing the execution of new tiles, resulting in an underutilization of available resources. A more efficient parallel execution could be achieved by removing the barriers and enabling each resource to asynchronously execute new parallel computations as soon as they become ready for computation, depicted in the parallel computation paths of Figure (d).
To utilize this untapped source of parallelism over the synchronization barriers, we propose fine- grained dynamic execution of DNNs, where we (I) remove the barriers and express DNNs in dataflow graphs of fine- fine-grained tiles to expose the parallel computation opportunities across operators, and (2) exploit these opportunities by dynamically locating and scheduling them in runtime. This fine-grained dynamic execution of DNNs enables opportunistic parallelism [29] 26) 25) for DNNs, a new class of parallelism that is unavailable in the existing operator-based approaches. In opportunistic parallelism, each resource asynchronously traverses down a distincl computation path in the graph as depicted in Figure
I (d). As there no barriers halt the execution of computation resources, each resource can execute its computation path to its maximal computational capabilities, leading to maximum system utilization and efficient load balancing. Also, as parallel resources are now computing down path in the graph, data reuse is maximized as the computation output is reused as input for the next computation on each resource.
To fully leverage the potential of opportunistic parallelism in DNNs, we find three technical challenges that must be addressed. The first challenge lies in expressing the tile-wise dataflow graphs, from designing a partitioning approach that is general enough to be applicable to all DNNs, to determining the dimensions of the tiles that would allow the most efficient parallelism across the operators.
The second challenge involves developing a runtime system that can enable dynamic tracking of com- putation opportumitics and asynchronous scheduling of many parallel resources over complex DNN

---

dataflow graph. While the concept is straightforward, creating a parallel solution that achieves such asynchronous graph traversal and execution of many computation resources, without encountering race conditions or data hazards, while also maintaining high scalability and efficiency, is a formidable task. As existing operator-bast based frameworks can neither enable nor manage such asynchronous and dynamic execution of DNNs, a novel algorithm for DNN scheduling must be created to achieve efficient opportunistic parallelism.
The third challenge entails creating a solution that facilitates concurrent information exchange among massive numbers of asynchronous parallel resources. Even when each parallel resource executes an independent computation path, there inevitably comes a need for resource to know the progression status of other nodes, for instance when a resource must select new path to traverse. However, using synchronization for information exchange would halt the resources and compromise the effectiveness of opportunistic parallelism. Therefore, information exchange between resources must be performed asynchronously without impeding the progression of other resources.
To tackle these challenges, we present ASPEN, a novel DNN computation solution comprising three key components: (1) a tile-based graph partitioning unit that transforms operator-based DNN dataflow graphs into tile-based dataflow graphs unlocking rich parallel computation opportunities, (2) a distributed scheduling algorithm that enables each resource to asynchronously track and compute a distinct computation path without encountering any data hazards or race conditions, and (3) highly concurrent data structure that facilitates asynchronous information exchange among parallel resources. These three components of ASPEN work in unison address the aforementioned challenges and achieve efficient utilization of parallel computing opportunities across operators. Our proof-of-com conccet- implementation of ASPEN on CPU demonstrates remarkable performance gains on various CNN and transformer- based model inference, achieving up to 3,2x and 4.3x speedup against state-of-the-arr inference systems such as TorchScript [ and TVM [6] respectively.
2 Background and Related Works
Limited parallelism of the current operator-based approach, particularly in the domain of DNN inference, has become a significant issue in recent years. In DNN training where an abundant number of inputs are provided, data parallelism or pipeline parallelism [8 [8 extensively used to leverage the inherent concurrency between inputs and achieve highly-paralled DNN computation. However, in DNN inference, the number of inputs is often limited which restricts the parallelism available from concurrent input data 30). To address this limitation, several solutions propose manipulating the operators of the DNN to expose more parallelism within the given DNN model structure.
31 12 47 34 [5 44 are
One approach is Operator Fusion, which aims to merge computations from neighboring operators into a single, larger operator, creating a more substantial intra-operator computation space. This expanded computation space allows for greater parallelism opportunities, such as increased utilization of the vector processing hardware or batched memory accesses. Many gigh-performance DNN frameworks and acceleration libraries, such as TVM [6), TorchScript 191. XNNPACK [3] and oneDNN 19), have already integrated rule-based operator fusion and fused computation kernels to accelerate parallel DNN execution. Systems like TASO (22), Rammer 300 Apollo 49] and AStitch [52] introduce an advanced fusion technique which combines computation from independent operators into single fused operator, unlike conventional fusions where only parent-child operators of graph are fused. This technique can be understood as fusing inter-operator parallelism space into larger, unified parallelism space, enabling much broader computation space for optimizations.
Another avenue to increase the parallelism opportunitics is Model Slicing [50] 17 53 21), which takes opposite approach to operator fusion stitching. Model slicing decomposes tensors and operators of CNNs into smaller ones, thus increasing inter-operator parallelism while reducing intra- operator parallelism. This approach is particularly utilized on edge clusters, where large number of cluster nodes with limited computation capabilities synergy well with the increased number of operators and reduced per-operator computation.
Unlike existing works that focus on the manipulation of operators, ASPEN explores tile-based dynamic execution of DNNs for increased parallelism. Expressing DNNs in a tile-granularity effec- tively combines the separate inter- and intra-operator computation spaces into a single unified space of tile-based dataflow graph. This provides a holistic view of the DNN and enables a finer-grained
3

---

Offline:
Runtime
Distributed Stheduling Engine
DSE (Section 3.2)
Parallel Resource
Automated Parallelism
Ready Nodes
Kerne Dispatch
Matrix Muliptcction
Ready Pool (Section 3.3)
Convolution
Unit (Section 3.1)
DSE (Section 3.2)
Parallel
ReLU
Ready Nodes
Kernel
Resource
ASPEN Graph
Dispatch
Operator-based DNN
ASPEN Runtime
Hardware
Figure 2: The overall workflow of ASPEN. APU compiles operator-based DNNs into ASPEN graphs to expose parallel computation opportunities across operators. ASPEN runtime, composed of Ready Pool and DSEs, utilizes opportunistic parallelism to achieve efficient parallel execution of DNNs.
analysis and management of both computation and data, allowing contributions that previously impossible with the operator-bar based dataflow graphs. Recent works on tile- base understanding of DNNs focus on applying tile-based analysis and optimizations on topics such as DNN schedulers (30)
graph compilers [54], or reducing memory overhead [40]
In contrast, ASPEN explores the benefits of biled DNNs during runtime. ASPEN combines (1) tile-based expression of DNNs, with (2) dynamic parallelism and execution approaches developed enable fine-graine dynamic parallelism and execution of DNNS. Finer granularity allows more parallelism opportunities to be expressed on the dataflow graph, and dynamic execution allows these opportunities to be located and scheduled right away during runtime, enabling a novel parallelism DNNs which we call opportunistic parallelism.
for irregular programs 22 26 25
24 [3
32 33
To our knowledge, ASPEN is the first to explore the benefits of tile-based DNNs during runtime using dynamic scheduling and execution approaches. While we mainly focus on parallelism this paper, we find that the benefits of fine-gre fine-grained dynamic execution of DNNs are not limited to parallelism, and extend to dynamic
balancing,, reduced memory traffic, and novel functionalities that are impossible in operator granularity static scheduling approaches. We cover these additional benefits in detail in Section 4 and S
3 ASPEN Design
To achieve efficient utilization of opportunistic parallelism in DNNs, we design ASPEN with three key components: the Automated Parallelism Unit (APU), the Distributed Scheduling Engine (DSE), and the Ready Pool. Each component is designed to overcome the three challenges described in Section D namely exposing computation opportunities across operators, creating an efficient runtime to leverage these opportunities, and enabling asynchronous information exchange between parallel resources. The following subsections provide a detailed explanation how each component tackles its respective challenge.
Figure 2 depicts an overall workflow of ASPEN. The APU takes a traditional operator-based de- scription of a DNN and automatically generates a computation tile-wise dataflow graph, which we call the ASPEN graph. The ASPEN runtime, which consists of DSEs and Ready Pool, initializes the computation by loading the graph and input data. DSE is scheduler that exists separately for each parallel resource and handles the asynchronous traversal and execution of parallel paths of the designated resource. As the execution progresses, information the path progression of the DNN by each resource is updated in the Ready Pool as ready nodes. Ready nodes are nodes that have all their parent nodes computed but have not been computed themselves, and they represent the tail ends of execution paths. The DSEs can refer to the Ready Pool whenever they need information about other paths, enabling asynchronous information exchange between parallel resources.
3.1 Automated Parallelism Unit
The goal of APU is to transform an operator- based DNN into tile-wise dataflow graph that exposes finer-grained parallel computation opportunities across operators. As mentioned in Section [ existing computation kernels partition and execute operators using computation tiles [ 43 30 54
with synchronization barriers to ensure the completion of all tile execution within operator. APU removes these barriers and expresses dependencies between individual tiles to expose more parallelism. To create a generalized method applicable to any operator, we propose partitioning the

---

(a) description (b) Tile-wise Tensor Partitioning (c) Graph Reconstruction (d) Node Merging
(e) ASPEN Greph
Input
Matrix Multiplication
Matmul Tiles
WVW
Convolution
Channels
ReLUU
Width
Convolution Tiles
wise Node Dependency Graph Simplifictioo
Figure Illustration of the three-step APU operation on an example DNN.
output tensor of each operator into fine units to maximize parallelism and then merging them into graph nodes. Merging reduces scheduling overhead and allows for increased weight data reuse and better utilization of computation resources.
We observe that many DNN computations kernels are executed using matrix multiplication. Naturally, DNN computations form a chain of matrix multiplications where the output of one multiplication serves as the input for the next. We focus on the property that in matrix multiplication x B = C, only a single column-wise vector of matrix B required for the computation of the column-wise vector of matrix C' with the matching row index. If we fix the weight matrices as A, the chain of matrix multiplication in DNNs can be understood vector multiplication chains. Therefore, we conclude that partitioning operators into column-wise matrix tiles exposes the most parallel path within the DNN graph.
set of independent, parallel-running matrix-
ASPEN leverages this insight by splitting output tensors into fine-graine matrix tiles aligned with the smallest hardware features such SIMD register length L1 cache size, and then merging them column-wise and subsequently row-wise. APU automates this process using a three-step approach illustrated in Figure (b) to (d). First, (a) APU parses the given DNN and (b) partitions the output tensors into fine-grained matrix tiles. (c) It merges the tiles column-wise into graph nodes, creating a directed acyclic graph (DAG) based on the element-wise dependencies. (d) The performance of the resulting graph is evaluated, and nodes are further merged or split column-wise and then row-wise until a sufficient level of parallelism exposed. (c) The resulting ASPEN graph now represents computation opportunities across operators as separate dataflow edges between nodes. The ASPEN graph saved as a file and later loaded into the ASPEN runtime for execution.
3.2 Distributed Scheduling Engine
DSE aims to maximize the utilization of parallel resources by continuously scheduling putation opportunities while dynamically traversing a barrier-free path the DNN graph. Each parallel resource has its own DSE, operating in isolation to eliminate idling and loss of utilization due to synchronization. This decentralized approach distributes scheduling and graph overhead among the resources, enabling high scalability. We show our novel DNN scheduling algorithm ensures the correctness and completeness of DNN execution while operating in complete isolation.
In the ASPEN runtime, graph nodes transition between three states: executed, ready, and not-ready. An executed node is a node that has been processed by a computation backend after all of its parent nodes have been executed, or is input (source) node of the DAG. A ready node has all its parent nodes executed but has not been processed itself. A not-ready node has one or more parents that are not executed. The state transitions always occur in the order of not-ready, ready, executed.
DSE executes Algorithm]] 1 The idea of Algorithm iis that the DSE only needs to be aware of the ready nodes for its traversal, as ready nodes are always at the tail end of execution paths. Executing ready node may turn one or more of its child nodes into ready nodes. If so, DSE selects one node for further traversal and stores the rest in the Ready Pool node is created, the DSE fetches a new path head from the Ready Pool. Algorithm | is also designed to be DNN-agnostic. That is, DSE will continuously fetch and execute new computations from the ready pool regardless of the layer or DNN graph it belongs to, to maximize resource utilization.
computation heads. If new ready
Figure Sesurefillin iillustrates an example of DSE execution. When DNN is loaded into the ASPEN runtime, the nodes from the first operator are always ready, as input nodes are always executed. These ready nodes are pushed into the Ready Pool to initiate execution.
(a) DSES of resources A and B fetch ready nodes as the heads of their execution paths. (b) Resource reaches a dead end without any new ready nodes. (c) Resource A fetches a new path head from the pool, while resource B also hits
5

---

Algorithm/ DSE's asynchronous graph traversal and scheduling algorithm
Require: Computation Resource C, Current ready node N, Ready Pool
I: struct GRAPH NODE
2: K: COMPUTATION KERNEL OF THE NODE
3: A. ARRAY OF CHILD NODES
4: P. : NUMBER OF PARENT NODES
5:
P. NUMBER OF EXECUTED PARENT NODES
6: end struct
7:
while True do
8: if N NULL then
9:
+ pop( (R)
Pop a new path head from pool. NULL returned empty.
10:
else
11:
Execute N.K on C
> Execute current node. N.X denotes the struct member X of N.
12:
de
N.
13:
+ NULL
14:
for n. in a. do
Iterate through all children of current node
15:
Pe f @hoomc__ftch..e aeddeffeehhhhheeeee ade(n..Pee)))
> Atomic post cost-increment If child is ready
16:
if is n.. Pr. then
17:
is is NULL then
18:
N+ + Re
D Traverse to first readied child
19:
else
20:
push(R, ne)
Push remaining readied children to pool
21:
end for
22:
end while
(a)
(b)
Resource A execution path
Resource execution path
nim
out m parents executed
Input Nodes (Executed)
Not-ready Nodes
O
Ready Nodes
Executed Nodes
| on the example DNN from Figure Resource A is assumed to be faster than B for demonstration purposes.
Figure 4: Two parallel DSEs for Resource A and B executing Algorithm
dead-end. (d) On its second computation path, resource A finds that both children of the executed node become ready. It proceeds with the first ready child while pushing the other child into the pool as new computation head. (e) After all executions, the DNN computation is completed with five different computation paths taken by the resources. This novel execution enables asynchronous and continuous scheduling of new computation nodes to parallel resources, achieving highly efficient parallel execution of DNNs.
Algorithm D can be further optimized to certain DNNs hardware. For instance, we find that dependency patterns in DNN graphs formed by pooling or strided layers create tiles of higher importance, and executions of child nodes on each DSE decreases the access to shared memory, which increases throughput. However, to focus on providing general solution that first enables the novel approach of tile-basee opportunistic parallelism, we leave optimizations for future work.
be accelerated by prioritizing these tiles. Also, having cache
Correctness: We now show the correctness of the asynchronous parallel execution of ASPEN. We first show that race conditions are impossible. Let e be ready node. From Algorithm[1 [[] node is considered ready when Pe Pn. Since the increment of Pe is atomic, the DSE whose increment resulted in P: P. for u is uniquely determined. The said DSE can choose to either set v as its N or push to the Ready Pool. If the former option is chosen, exclusiveness is guaranteed during the execution of v as the DSE responsible for e is unique. If the latter option is chosen, v is stored in the Ready Pool until it is eventually popped by DSE. As the Ready Pool is concurrent data structure, only single DSE can pop v. ensuring exclusiveness during the execution of v. Therefore, exclusiveness is guaranteed in all node executions of ASPEN.
Furthermore, all executed nodes of ASPEN yield correct execution output as long as correct input to the DNN is provided. From Algorithm |
a ready node v becomes executed node when it is

---

Row-wise multi-level priority queue in papl
Batched Ready Nodes
Queue
Queue 1_N
DSE
HBg N
DSE
O
Hash Function
Queue 2_1
2_N
H(K)
DSE M-1
DSE M
H[R)
Queue M_1
Queue M_N
Node stolen from DSE
Ready Pool
k: Hash Key (Node depth) m: Column index of target queue ........ push( data movement
popl) data movement
Figure 5: Illustration of concurrent access to Ready Pool queue matrix.
executed on a computation resource R using kernel K. We assume R and K are correct, as they externally supplied the runtime. By the definition of ready node, all parent nodes of executed nodes. Since DSEs can only execute a ready node, no other DSE can modify the parent nodes of v, the input of v, during the execution of This eliminates data hazards during execution and, when combined with exclusiveness in execution, guarantees correct execution results as long as the parent nodes of have correct execution results. Therefore, through recursion, ASPEN computes correct execution results for all nodes as long as a correct input to the DNN is provided.
Completeness: We show that all graph nodes become executed in ASPEN. Suppose there exists node e in the DAG that is never exccuted. a cannot be a ready node since a ready node will be either executed
it is created, or stored in the Ready Pool until it is eventually popped and executed. Therefore, e must be not-ready node, and by definition of a not-ready node, at least one parent of v is also node that is never executed. By recursion, there must exist path from some source node to u where all nodes on the path are not-ready nodes. However, this leads to a contradiction as source node is an executed node by definition. Therefore, v cannot exist in ASPEN.
3.3 Ready Pool
Ready Pool is our fast, flexible, and scalable solution for managing dependencies among a large number of computation nodes and parallel resources. It acts barrier, separating nodes that can be computed from those that cannot, similar to existing synchronization barriers in operator-basee based approaches. However, Ready Pool offers significant advantage barriers in that the dependency information exchange happens on-demand, and only between the producer and consumer of the information, without involving other resources.
traditional synchronization
Synchronization barriers inserted in compile time are unaware of which computation tile is scheduled to which resources runtime. As a result, they must synchronize all resources to ensure the correctness of dependent computations, which limits parallelization scope and hampers the utilization of faster resources. In contrast, Ready Pool allows resources dynamically update the satisfaction of dependencies to the pool and enables asynchronous retrieval by other resources when they require new computations, minimizing the overhead of data exchange.
However, if not properly designed, Ready Pool can be bottleneck in the system. To ensure constant access time, flexible scheduling policies, and scalability over many parallel resources regardless of DNNs used, we design Ready Pool using matrix of concurrently accessible FIFO queues, as shown in Figure 5 Each DSE is assigned row of queues, and accesses from DSE are prioritized within its assigned row to minimize conflicts between DSEs. simple hash function determines the column index of the accessed queue during the push() operation, while a multi-level priority queue is used during the pop() operation to facilitate fast accesses and support scheduling policies.
To be specific, during push(). ready nodes from each DSE are batched to reduce overhead. The target queue's 's column index determined using user-defined hash function H (k). In our proof-of-concep code, key & is the depth of the pushed nodes, and (kk) returns smaller column index if the depth is shallow, and larger index if the depth deep. When combined with row-wis wise priority queue access of pop(), this implementation enables the scheduling policy of prioritizing nodes of shallower depth, which accelerates execution by allowing DSES to traverse longer computation paths. During pop(). a DSE first pops nodes from its assigned row to maximize data reuse. If the assigned row is empty, the DSE searches rows of other DSEs similarly to work-stealing queues 4 to automatically load balance and improve resource utilization. When DNN enters the ASPEN runtime, ready nodes
7

---

ToroNScripe
1577mm
Rau Spoethop
passigu
2.2 2.000mr
22.27 22mm
147mm
4
47tara
2,203mm
2 tidmio
3
7200m
57Nmma
25
VGG16
VOD16
Reamet-S5 B1
50
Reanwt-50
YOLO-w3
YOLOws
BERTibase
BERT--base $480 B8
BERT-large 5128 B1
BERT-large 5480 BE
GPT-
GPT-2 5182481
B1
B12
B128
B1
B12
B128
B256
Figure 6:
Relative latency speedup and latency of ASPEN and other frameworks compared to
TensorFlow [ on Threadripper 3990X. Latency mcasurements are annotated on each bar. B refers to the batch size, and S the NLP models refers to the number of input tokens.
360
16k
1.0
Inferncekecc
2.0-
TVM
ASPEN
Tohenloec
12k
TVM
ABPEN
Farellal Fraction
0.9
Paraltal Fradion
0.9
8k
0.8
120-
1F
XLA
TVM
ASPEN
0-
32
64
(a) ResNet-50, B128
(b) BERRT-aase, $480 B8
(a) ResNet-50, B128
(b) BERT-base, $480
Figure 7: Throughput scaling of ASPEN and other frameworks over Resnet-50 and BERT-base using the full core range of Threadripper 3990X.
Figure 8: Experimental parallel fraction Pe over Resnet-50 and BERT-base using the full core range of Threadripper 3990X. Higher is better.
uniformly distributed among the rows. This design of Ready Pool ensures fast and concurrent access while enabling scheduling policies and automatic load balancing throughout the DNN execution.
4 Evaluations
Implementation Details: As existing DNN framework supports the use of opportunistic parallelism, we implement our proof-of-concept code ASPEN targeting CPUs with approximately 12k lines of C code from scratch. We create our tile-wise GEMM kernels using AVX2 extensions and conv2D kernels using the GEMM kernels and im2col. The remaining operators are computed using simple C for-loops. For memory, output tensors for each operator created in NHWC order as in the existing approaches, and each tile holds a pointer to its respective location in each tensor. Our implementation publicly available at
/S
Experimental Setup: Our evaluations are conducted on an AMD Threadripper 3990X 64-core processor and Intel i9-12900K 16-core processor using Ubuntu 22.04. We compare ASPEN against the popular DNN framework of TensorFlow (v2.7) 1 as well as highly-optimized inference solutions of TorchScript (v2.0.0) [9. TensorFlow XLA (v2.6.2) [39, and TVM (v0. (v0.11.0) 1.0) (6), all using C/C++ API. We evaluate inference latency various CNN and Transformer based [46] NLP models. namely VGG-16 (2). ResNet-50 [16). Yolo-v3 (416) (38, BERT-base, BERT-large [10], and GPT-2 (124M) (37]. For the GPT-2 model, we evaluate the first model iteration, where no past attention values provided. We measure the end-to-end latency of DNN model execution, which excludes pre- or post-processing such as image cropping or text tokenization. We average the measurements 100 runs obtain representative values.
4.1 Execution Latency
presents the inference latency speedup of ASPEN and other frameworks compared to TensorFlow on Threadripper 3990X for various DNN models. Overall, ASPEN demonstrates strong performance, achieving speedups up 6.2x against TensorFlow (BERT-base S480 B8) and 4.3 against TVM (GPT-2 S1024 B1). We find ASPEN performs better when more layers with multiple execution paths, such residual connections or multi-head attention layers, contained within the model. These network designs provide multiple computation paths across operators, which synergize effectively with the opportunistic parallelism of ASPEN.
Figure 6
ASPEN also exhibits amplified speedup with larger batch sizes, as larger batches further facilitate the isolation of computation between DSEs. In existing operator- based solutions, dependent compu-
8

---

180
24
9k
0k-
XLA ASPEN
Inforencelsec
TVM
Inforence/seo
18
TVM
ASPEN
Tolontsec
6k-
TVM
ASPEN
Tokenisc
6k
TVM
ASPEN
12-
4k-
60
3k-
16
16
Threads
Threads
Threads
Threads
ResNet-50, B128
(b) Yolov3, B1
BERT-base, S480 B8
(d) GPT2, S256 B1
Figure 9: Heterogeneous resource utilization of ASPEN and other frameworks over various DNNs on Intel 19- 19-1K2 B refers the batch size, and S on the NLP models refers the number of input tokens. Both the performance cores and efficiency cores are utilized after 8 threads.
tations across operators are not guaranteed to be scheduled to the same resource. This necessitates scatter/gathher-lik data exchanges between resources causing memory overheads, and this overhead only increases with larger batch sizes and more resources used. In contrast, depth-fire -irstt computation of ASPEN allows dependent tiles to be scheduled to the same resource as much as possible, achieving effects similar operator fusion. With large enough batch sizes, each DSE is allocated paths in different batch indexes similar to data parallelism, greatly reducing the memory overhead. Also, even when there are data exchanges between resources, only few resources are involved simultaneously, relieving the pressure on the memory system.
4.2 Parallel Scaling
7 presents the strong scaling throughput results of ASPEN against other frameworks on Threadripper 3990X, detailing the results of Figurelo We observe that ASPEN exhibits superior per- resource scaling performance over other frameworks, thanks its asynchronous design and distributed scheduling. To quantitatively evaluate the scaling performance, we introduce the experimental parallel fraction, denoted as Pe, in Figure g8 Pe represents the proportion of computation executed in parallel, which directly influences the scaling and upper limit of parallel speedup according to Amdahl's
Figure
law 22. We use Karp-Flatt metric (23] P. 1 1/4-1/N 1-1/N to calculate Pe, N being the number of parallel resources, and v being the measured speedup while using parallel resources. ASPEN achieves remarkably high Pe. values ranging from 0.97 to 0.99 across all cases, indicating that more than 97% of ASPEN computations are performed in parallel, which allows ASPEN exhibit exceptional scaling performance following Amdahl's law.
4.3 Resource Utilization
Figure presents the resource utilization of ASPEN and other frameworks on Intel's 19- 12900K heterogeneous processor for various DNN models. 19-12900K has 8 performance cores (P-cores) and efficiency cores (E-cores) with different computing capabilities. We observe that ASPEN shows linear summation of all utilized core performance, clearly highlighting the higher performance inclination of P-cores on I to threads and the lower performance inclination of E-cores on 9 to 16 threads. In contrast, existing solutions exhibit sub-optimal resource utilization when using both the P- cores and E-cores, suffering from stale performance increases (TensorFlow, XLA), sharp performance drops (TorchScript, XLA), performance bottlenecks to the slower E-cores (TorchScript, TVM). ASPEN, on the other hand, effectively utilizes all available resources to their full potential, thanks to its dynamic scheduling and automatic load-bat balancing capabilities provided by the ASPEN runtime.
4.4 Ablation Studies
Figure (a) (a) provides the execution throughput of ASPEN in FLOP/s against the number of ASPEN tiles per layer. The throughputs of other frameworks are presented in dotted horizontal lines. The throughput of ASPEN increases on to 128 tiles, as increasing the number of tiles provides more parallelism. The throughput drops after 128, there not enough resources in the machine to utilize the increased parallelism, while the smaller tiles increase overhead and reduce computation efficiency. As such, ASPEN shows concave performance characteristic against the number of tiles.
Figure TO (b) to (d) provides the execution throughput scaling of ASPEN and other solutions against various DNN parameters, normalized to the throughput on the smallest parameter size. ASPEN shows

---

TVM - ASPEN
TVM
ASPEN
TVM
ASPEN
TYM
ASPEN
TPlops
Speeechpp
Spenckup
Spenshup
-00
10
32
128
512
16
256
32
128
256
512
1024
64
128
256
512
1024
(a) Tiles per Layer
(b) Number of Layers
(c) Height and Width
(d) Channel Size
Figure 10: Performance and scaling against differing parameter sizes, on Threadripper 3990X using 64 cores. All tests are executed with batch size of 1, using synthetic DNN with 32 identical convolution layers. All layers have 64x64 inputs, 3x3 filters, input and output channels of 128, padding and stride of I, and a fixed 128 tiles per layer for ASPEN, except for the specified parameters.
noticeable speedup with an increasing number of layers, owing to the utilization of computation opportunities and depthwise computation across the layer boundaries. Against height, width, and channel sizes, existing frameworks except TVM exhibit large performance speedup as larger tensor sizes allow more parallelism in each layer for these solutions. The performance of TVM is largely unaffected as creates optimized kernels for each of the given parameter sizes, achieving constant performance across tensor sizes. The performance of ASPEN is also less affected by tensor sizes as ASPEN is able to source its parallelism from other sources.
Limitations and Discussions
While our current proof-of-concept implementation of ASPEN targets CPUs, we expect ASPEN to be easily applicable to GPUs as well if given proper tile-level kernel support. For example, Nvidia GPUs can leverage the CUDA Streams and CUDA Events API to dispatch tile-level kernel calls asynchronously, while DSEs on the CPU perform graph traversal to identify computation opportunities. Using ASPEN on GPUs would allow for seamless interleaving of data movement, kernel launches, and tile executions. This would greatly reduce the host-device scheduling and communication overhead, which are often reported as a limiting factor of GPU utilization 30 27). The asynchronous nature also means that the computing resources would be at differing stages of kernel execution, which distributes memory access requests across the temporal domain and mitigates the limitations in memory bandwidth that DNN executions on GPUs often face [51) 40).
ASPEN on GPUs:
ASPEN on DNN training: ASPEN can potentially be used for DNN training it offers general solution for leveraging opportunistic parallelism on DNNs. However, as DNN training can exploit the abundant input data as alternative source of parallelism. it is unlikely that ASPEN's dynamic ap- proach would outperform static optimization solutions [4] due to runtime overhead. Nonetheless, ASPEN remains appealing in environments with varying capabilities, such edge computing.
ASPEN for diverse applications: Fine- graineraiddd dynamic DNN execution of ASPEN also brings several novel functionalities to DNN execution. Since the execution of DSEs is DNN-agnostic, different DNNs can be co-executed easily for increased system utilization (0) by simply placing them in the same Ready Pool. Parallel resources can be dynamically added removed from the ASPEN system without disrupting the execution of other resources, allowing for enhanced flexibility. For DNN applications that operate continuous input streams like videos, ASPEN's dynamic dependency tracking enables the execution of only the relevant tiles affected by the changes in the input, significantly reducing computation requirements. In computation offloading, ASPEN can interleave computation and transmission at the tile level to hide most of the networking overhead. In inference servers, inference requests can be immediately pushed into the Ready Pool and executed concurrently with other users' requests, reducing turnaround time and improving system utilization.
Conclusion
We present ASPEN, novel parallel computation approach for DNNs that aims to (1) eliminate the synchronization barriers of tensor operators and (2) leverage opportunistic parallelism on the tile-wise dependency graph of DNNs. This allows ASPEN dynamically locate and execute any parallel computation opportunities, resulting in high scalability and efficient utilization of parallel resources. Through evaluation, validate that ASPEN outperforms the existing solutions and delivers exceptional parallel computing performance for DNNs.
10

---

Acknowledgments and Disclosure of Funding
This research was supported in part by the IITP grant (2022-0-00420) and National Research and No. 2022RIA5A1027646 funded
Foundation of Korea (NRF) grant No. by the Ministry of Science and ICT (MSIT) in Korea. Kyunghan Lee is the corresponding author.
References
[1] Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. Tensorflow: a system for large-scale machine learning. In Proceedings of the 12th USENIX Symposium Operating Systems Design and Implementation, pages 265-283, 2016.
[2] Gene M Amdahl. Validity of the single processor approach to achieving large scale computing capabilities. In Proceedings of the April 18-20, 1967, spring joint computer conference, pages 483-485, 1967.
[3] ARM. Armnn: Performant machine learning (ML) inference engine for Android and Linux, accelerating ML on Arm Cortex-A CPUs and Arm Mali GPUs. htttp:///githbb com/ last accessed on 2023-10-27, 2023.
ARM sof /armna armmn
[4] Robert D Blumofe and Charles E Leiserson. Scheduling multithreaded computations by work stealing. Journal of the ACM (JACM), 46(5):720-748, 1999.
[5] Tianqi Chen, Mu Li, Yutian Li, Min Lin, Naiyan Wang, Minjie Wang, Tianjun Xiao, Bing Xu, Chiyuan Zhang, and Zheng Zhang. Mxnet: A flexible and efficient machine learning library for heterogeneous distributed systems. CoRR, abs/1512.011.
2015.
[6] Tianqi Chen, Thierry Moreau, Ziheng Jiang. Lianmin Zheng, Eddie Yan, Haichen Shen, Meghan Cowan, Leyuan Wang, Yuwei Hu, Luis Ceze, et al. Tvm: An automated end-to-end optimizing compiler for deep learning. In Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation, pages 578-594, 2018.
[7] Sharan Chetlur, Cliff Woolley, Philippe Vandermersch, Jonathan Cohen, John Tran, Bryan Catanzaro, and Evan Shelhamer. cudnn: Efficient primitives for deep learning. arXiv preprint 11X1v:1410.0759, 2014.
[8] Trishul Chilimbi, Yutaka Suzue, Johnson Apacible, and Karthik Kalyanaraman. Project adam: Building an efficient and scalable deep learning training system. In Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation, pages 571-582, 2014.
[9] Py Contributors. Torchscript: Just-in-time compiler for creating serialized and optimized models from pytorch code. on 2023-10-21 2023.
htmlllmml html
last accessed
[10] Jacob Devlin, Ming-Wes Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: arXiv:1810.044 080000 2018.
[11] Jack Dongarra, Jeremy Du Croz, Sven Hammarling, and lain S Duff. A set of level 3 basic linear algebra subprograms. ACM Transactions on Mathematical Software, 16(1):1-17, 1990.
[12] Shiqing Fan, Yi Rong, Chen Meng, Zongyan Cao, Siyu Wang, Zhen Zheng, Chuan Wu, Guoping Long, Jun Yang, Lixue Xia, et al. Dapple: A pipelined data parallel approach for training large models. In Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 431 445, 2021.
[13) Google. Xnnpack: Highly optimized library of floating-point neural network inference operators for ARM, WebAsseemly, and x86 platforms. accessed on 1023-10-220 2023.
http:/hhwww..cooggggg//////c../t last
[14] Kazushige Goto and Robert van de Geijn. Anatomy perf-ppefo matrix multiplication. ACM Transactions on Mathematical Software, 34(3):1-25, 2008.
11

---

[15] Tim Harris, Yossi Lev, Victor Luchangco, Virendra J Marathe, and Mark Moir. Constrained data-driven parallelism. In Sth USENIX Workshop on Hot Topies in Parallelism, 2013.
[16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 770-778, 2016.
[17] Xueyu Hou, Yongjie Guan, Tao Han, and Ning Zhang. Distredge: Speeding up convolutional neural network inference on distributed edge devices. In 2022 IEEE International Parallel and Distributed Processing Symposium, pages 1097-1107. IEEE, 2022.
[18] Yanping Huang, Youlong Cheng, Ankur Bapna, Orhan Firat, Dehao Chen, Mia Chen, Hy- oukJoong Lee, Jiquan Ngiam, Quoe V Le, Yonghui Wu, et al. Gpipe: Efficient training of giant neural networks using pipeline parallelism. Advances in Neural Information Processing Systems, 32, 2019.
[19] Intel. Intel oneAPI Deep Neural Network Library (oneDNN): Library of optimized implemen- tations of deep learning building blocks. sttpp://www, intel. . wwwm/onntet..../ommoommmm wwtpeteetttwttteeeeeeeeeeeeeeeee www/us// /n/ html last accessed on 1022-10-27, 2023.
deveeoope//tools/ooee wttpa////eeapi//oioeo
[20] Joo Seong Jeong, Jingyu Lee, Donghyun Kim, Changmin Jeon, Changjin Jeong, Youngki Lee, and Byung-Gon Chun. Band: coordinated multi-dnn inference on heterogeneous mobile processors. In Proceedings of the 20th Annual International Conference on Mobile Systems, Applications and Services, pages 235-247, 2022.
[21] Fucheng Jia, Deyu Zhang, Ting Cao, Shiqi Jiang, Yunxin Liu, Ju Ren, and Yaoxue Zhang. Codl: efficient epu-gpu co-execution for deep learning inference on mobile devices. In Proceedings of the 20th Annual International Conference on Mobile Systems, Applications and Services, pages 209-221, 2022.
[22] Zhihao Jia, Oded Padon, James Thomas, Todd Warszawski, Matei Zaharia, and Alex Aiken. Taso: optimizing deep learning computation with automatic generation of graph substitutions. In Proceedings of the 27th ACM Symposium on Operating Systems Principles, pages 47-62, 2019.
[23] Alan H Karp and Horace P Flatt. Measuring parallel processor performance. Communications of the ACM, 33(5)533--543, 1990.
[24] Milind Kulkarni, Martin Burtscher, Rajeshkar Inkulu, Keshav Pingali, and Calin Casçaval. How much parallelism there in irregular applications? ACM sigplan notices, 44(4):3 14, 2009.
[25] Milind Kulkarni, Patrick Carribault, Keshav Pingali, Ganesh Ramanarayanan, Bruce Walter, Kavita Bala, and L Paul Chew. Scheduling strategies for optimistic parallel execution of irregular programs. In Proceedings of the twentieth annual symposium on Parallelism in algorithmss and architectures, pages 217 -28, 2008
[26] Milind Kulkarni, Keshav Pingali, Bruce Walter, Ganesh Ramanarayanan, Kavita Bala, and Paul Chew. Optimistic parallelism requires abstractions. In Proceedings of the 28th ACM SIGPLAN Conference Programming Language Design and Implementation, pages 211-222, 2007.
pages
[27] Woosuk Kwon, Gyeong-In Yu, Eunji Jeong, and Byung-Gon Chun. Nimble: Lightweight and parallel gpu task scheduling for deep learning. Advances in Neural Information Processing Systems, 33:8343-8333 2020.
[28] Tze Meng Low, Francisco D Igual, Tyler M Smith, and Enrique Quintana-Orti, Analytical modeling is enough for high-performance blis. ACM Transactions Mathematical Software, 4382):1-18, 2016.
[29] Steven Lucco. A dynamic scheduling method for irregular parallel programs. In Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, pages 200-211, 1992.
12

---

[30] Lingxiao Ma, Zhiqiang Xie, Zhi Yang, Jilong Xue, Youshan Miao, Wei Cui, Wenxiang Hu, Fan Yang, Lintao Zhang, and Lidong Zhou. Rammer: Enabling holistic deep learning compiler optimizations with rtasks. In Proceedings of the 14th USENIX Symposium Operating Systems Design and Implementation, pages 88 881-897, 2020.
[31] Deepak Narayanan, Aaron Harlap, Amar Phanishayee, Vivek Seshadri, Nikhil R Devanur, Gregory R Ganger, Phillip B Gibbons, and Matei Zaharia. Pipedream: generalized pipeline parallelism for dnn training. In Proceedings of the 27th ACM Symposium on Operating Systems Principles, pages 1-15, 2019.
[32] Quan M Nguyen and Daniel Sanchez. Pipette: Improving core utilization on irregular applica- tions through intra-core pipeline parallelism. In 2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture, pages 396-608. IEEE, 2020.
[33] Quan M Nguyen and Daniel Sanchez. Phloem: Automatic acceleration of irregular applica- tions with fine-grain pipeline parallelism. In 2023 IEEE International Symposium on High- Performance Computer Architecture, pages 1274.1774. IEEE, 2023.
[34] Hyungjun Oh, Junyeol Lee, Hyeongju Kim, and Jiwon Seo. Out-of-order backprop: an effective scheduling technique for deep learning. In Proceedings of the Seventeenth European Conference on Computer Systems, pages 435-452, 2022.
[35] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zach VeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems, 2019.
[36] Aurick Qiao, Sang Keun Choe, Suhas Jayaram Subramanya, Willie Neiswanger, Qirong Ho, Hao Zhang, Gregory R Ganger, and Eric P Xing. Pollux: Co-adaptive cluster scheduling for goodput-optmizzed deep learning. In Proceedings of the 15th USENIX Symposium on Operating Systems Design and Implementation, 2021.
[37] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 18)):, 2019.
[38] Joseph Redmon and Ali Farhadi. Yolov3: An incremental improvement. arXiv preprint 1804.0180 2018.
[39] Amit Sabne. Xla Compiling machine learning for peak performance, 2020.
[40] Yining Shi, Zhi Yang, Jilong Xue, Lingxiao Ma, Yuqing Xia, Ziming Miao, Yuxiao Guo, Fan Yang, and Lidong Zhou. Welder: Scheduling deep learning memory access via tile- tile-graph. In 17th USENIX Symposium on Operating Systems Design and Implementation, pages 701-718, 2023.
[41] Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro. Megatron-Im: Training multi-billion parameter language models using model parallelism. arXiv preprint arXiv: 1009000000. 2019.
[42] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 1=XXiv1440.11555 2014.
[43] Tyler M Smith, Robert Van De Geijn, Mikhail Smelyanskiy, Jeff R Hammond, and Field G Van Zee. Anatomy of high-performance many-threaded matrix multiplication. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium, pages 1049-1059. IEEF, 2014.
[44] Colin Unger, Zhihao Jia, Wei Wu, Sina Lin, Mandeep Baines, Carlos Efrain Quintero Narvaez, Vinay Ramakrishnaiah, Nirmal Prajapati, Pat McCormick, Jamaludin Mohd- Yusof, et al. Unity Accelerating dnn training through joint optimization of algebraic transformations and paral- lelization. 16th USENIX Symposium on Operating Systems Design and Implementation, pages 267-284, 2022.
13

---

[45] Leslie G Valiant. A bridging model for parallel computation. Communications of the ACM, 33(8):103-111, 1990.
[46] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 30, 2017.
[47] Yuanzhong Xu, HyoukJoong Lee, Dehao Chen, Blake Hechtman, Yanping Huang, Rahul Joshi, Maxim Krikun, Dmitry Lepikhin, Andy Ly, Marcello Maggioni, al. Gspmd: general and scalable parallelization for ml computation graphs. arXiv preprint arXiv:2105, 04663, 2021.
[48] Shuai Zhang, Sheng Zhang, Zhuzhong Qian, Jie Wu, Yibo Jin, and Sanglu Lu. Deepslicing: collaborative and adaptive enn inference with low latency. IEEE Transactions on Parallel and Distributed Systems, 32(9):2175-21 2021.
[49] Jie Zhao, Xiong Gao, Ruijie Xia, Zhaochuang Zhang, Deshi Chen, Lei Chen, Renwei Zhang, Zhen Geng, Bin Cheng, and Xuefeng Jin. Apollo: Automatic partition- operator fusion through layer by layer optimization. Proceedings of Machine Learning and Systems, 4: 1-1,, 2022.
[50] Zhuoran Zhao, Kamyar Mirzazad Barijough, and Andreas Gerstlauer. Deepthings: Distributed adaptive deep learning inference esource-constrained iot edge clusters. JEEE Transactions on Computer-Aider Design of Integrated Circuits and Systems, 37(1 37(11))2348-233 2018.
[51] Lianmin Zheng. Zhuohan Li, Hao Zhang, Yonghao Zhuang, Zhifeng Chen, Yanping Huang, Yida Wang, Yuanzhong Xu, Danyang Zhuo, Eric P. Xing. Joseph Gonzalez, and Ion Stoica. Alpa: Automating inter-and intra-operator parallelism for distributed deep learning. In Proceedings of the 16th USENIX Symposium on Operating Systems Design and Implementation, 2022.
[52] Zhen Zheng, Xuanda Yang, Pengzhan Zhao, Guoping Long, Kai Zhu, Feiwen Zhu, Wenyi Zhao, Xiaoyong Liu, Jun Yang, Jidong Zhai, et al. Astitch: enabling a new multi-dimensional optimization space for memory-intensive ml training and inference on modern simt architec- tures. In Proceedings of the 27th ACM International Conference Architectural Support for Programming Languages and Operating Systems, pages 359-373, 2022.
[53] Huan Zhou, Mingze Li, Ning Wang, Geyong Min, and Jie Wu. Accelerating deep learning inference via model parallelism and partial computation offloading. IEEE Transactions Parallel and Distributed Systems, 4455):475555 488, 2022.
[54] Hongyu Zhu, Ruofan Wu, Yijia Diao. Shanbin Ke, Haoyu Li, Chen Zhang. Jilong Xue, Lingxiao Ma, Yuging Xia, Wei Cui, al. Roller: Fast and efficient tensor compilation for deep learning. In Proceedings of the 16th USENIX Symposium on Operating Systems Design and Implementation. pages 233-248, 2022.
14


Reviews:
[{"review_id": "QHFJik9wa5", "reviewer": "Reviewer_zpkQ", "summary": "Inference performance is one of the key metrics driving the commercial adoption and integration of modern DNNs into user-facing applications. In the paper, the authors propose a framework, ASPEN, to improve the inference performance of DNNs by exploiting a novel strategy to extract maximal parallelism, called opportunistic parallelism, during the forward pass. Opportunistic parallelism dynamically locates and executes ready units of computational maximally based on the minimization of the number of synchronization barriers introduced by different operators. Synchronization barriers are removed based on a tile-wise decomposition of the input data and weights to produce parallel execution sequences capable of taking advantage of more hardware. Orchestration of the computational work is performed by 2 processes, the automated parallelism unit (APU), lowers the input graph from an operator-centric synchronization strategy to a tile-wise dataflow graph suitable for parallel execution with a small number of synchronization barriers. The lowered dataflow graph is then placed on the compute units by the distributed scheduling engine to assign available processors to units of work as the availability, or ready state, of the dataflow graph dictates. Based on these optimizations the authors demonstrate significant performance improvements over competing inference engine systems as the number of cores is increased.", "questions": "- Though the results presented are CPU-based I wonder if comparing with GPU inference results, based on something like TensorRT, would be useful?", "limitations": "The limitations were adequately addressed by the authors in the text.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The significance of the work to the community is clear as exploiting the maximal efficiency of hardware during the deployment of DNNs is of paramount importance for industrial applications.\n- The lowering of the operator-oriented DNN to a dataflow representation that exposes ample parallelism is interesting and the necessity of the authors to reimplement a large number of the lower primitives to achieve this feat speaks to the novelty of the approach. This also brings into question the current strategies employed by existing libraries/frameworks to execute DNNs and whether they should be extended to allow for a finer level of granularity required to facilitate the parallelism exposed by ASPEN.\n- The ASPEN dataflow graph combined with the DSE runtime system is shown to achieve substantial performance over competing implementations for a number of different DNNs and multiple CPU architectures.", "weaknesses": "- The evaluation section focuses on comparisons with other CPU architectures and ignores providing any data on competing implementations optimized for GPUs.\n- It is not clear the insights regarding the tensor decompositions and the resulting dataflow graph would easily generalize to GPU architectures or for the training phase. These concerns are acknowledged by the authors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments and feedback! In this response, we will address your individual concerns one by one in addition to the general response. We hope this clarifies your concerns about our work.\n\n---\n\n> **Issue 1** The evaluation only focuses on CPUs and does not contain GPU results or comparisons against GPU inference results.\nIt is also not clear if the tile-based dataflow graph would easily generalize to GPUs. \n\nAs explained in the general response, due to the unique nature of ASPEN’s approach, a suitable computation backend for GPU is not currently available. Consequently, our evaluation results are presently confined to CPUs. However, we have observed a growing availability of tile-based kernels, and therefore we expect that the performance benefits of ASPEN on GPUs will soon be corroborated, which is rather obvious according to the principles of ASPEN. \n\nAlso, the tile-based dataflow graph and its execution of ASPEN is generalizable to GPUs, as operator-based GPU kernels already use tile-based parallel executions internally. The asynchronous per-tile kernel launches of ASPEN can be efficiently achieved using CUDA Streams and CUDA Events API, by assigning different CUDA Streams to each DSE and enabling asynchronous tile scheduling and dependency updates with CUDA Events. By constantly keeping scheduled kernels in the CUDA Stream queues through opportunistic parallelism, ASPEN can fully utilize the SMs of the given GPU through the whole DNN execution. Also, ASPEN provides additional benefits such as the interleaving of host-device data movement and tile execution, and better utilization of memory bandwidth.\n\nIt is important to note that GPU implementation results would not make any change to the core logic and design of ASPEN, implying that our contributions in this work are orthogonal to the results.\n\n> **Issue 2** Will tile-based dataflow graphs easily generalize to DNN training?\n\nWe also expect that ASPEN can be readily applicable to DNN training, given that the backward propagation in DNNs primarily involves matrix multiplication, which ASPEN already supports. Gradient computations can be partitioned into tiles and the dependencies between each gradient tiles can be encoded into a graph, to create an ASPEN graph for DNN training. This graph can be fed into the ASPEN runtime to automatically perform forward and backward propagation without any modification in the ASPEN runtime. In Section 5 (Limitations and Discussions), we explain that existing approaches may use higher batch sizes to compensate for the limited parallelism of operator-based approaches, but this does not imply that ASPEN’s efficacy reduces in training. Rather, ASPEN enables additional parallelism in situations where increasing the batch size is unfavorable or impossible, such as training with limited device memory or datasets.\n\nIn order to improve the readability and clarity, we will be updating Section 5 with more details regarding GPU execution and DNN training in our final manuscript.\n\n---\n\nThank you again for your valuable feedback and suggestions on our work!"}, {"review_id": "xtbq5xnl7S", "reviewer": "Reviewer_b91G", "summary": "In this paper, authors proposed ASPEN, a parallel computation solution for DNNs, which utilizes a new class of parallelism for DNNs, namely opportunistic parallelism, to dynamically locate and execute any parallel computation opportunities during runtime. More specifically, the authors have presented three main key points in ASPEN:\n(1) a tile-based graph partitioning unit that transforms operator-based DNN dataflow graphs into tile-based dataflow graphs unlocking rich parallel computation opportunities,(2) a distributed scheduling algorithm that enables each resource to asynchronously track and compute a distinct computation path without encountering any data hazards or race conditions, and (3) a highly concurrent data structure that facilitates asynchronous information exchange among parallel resources.\nThe evaluation of ASPEN on various CNN and transformer-based model inferences on CPU have shown performance gains.", "questions": "N/A", "limitations": "The hardware platform is limited to CPU, which is the biggest limitation for the proposed ASPEN. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is clear and organized. The authors presented ASPEN in three key components: the Automated Parallelism Unit (APU), the Distributed Scheduling Engine (DSE), and the Ready Pool. each component is well introduced and analyzed. The overall workflow of ASPEN is clear. \n2. ASPEN has shown strong performance on various DNN architectures, achieving speedups up to 6.2× against TensorFlow and 4.3× against TVM (GPT-2 S1024 B1).", "weaknesses": "1. As mentioned in the paper, ASPEN is targeted at CPUs. The motivation is not quite strong if only applicable to CPUs. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments and feedback! In this point-to-point response, we will address and hopefully clarify your concern with our work.\n\n---\n\n> **Issue 1** The hardware platform is limited to CPUs.\n\nAs explained in detail in the general response, ASPEN is not necessarily limited to CPUs. ASPEN provides a general concept and solution to enabling a novel DNN scheduling and execution system that allows higher parallelism resource utilization, not confined to certain hardware architecture. However, due to its novelty, we were unable to find a suitable computation backend for GPUs. Consequently, we were only able to provide evaluation results based on CPUs. Fortunately, we find that tile-based kernels are becoming more widely available, and therefore we expect the GPU backend for ASPEN to be soon available.\nWe will make this clearer in our final manuscript and explain in more detail how ASPEN is applicable to other hardware architecture, as explained in the general response.\n\n---\n\nThank you again for your valuable feedback and suggestions on our work!\n"}, {"review_id": "ZOwXEwCCDI", "reviewer": "Reviewer_qSHs", "summary": "DNN is composed of multiple computational blocks, each using different tensor operators. However, due to the nature of the computational graph, there are internal dependencies among the blocks and operators. Consequently, the synchronization barrier results in considerable overhead for modern high-parallelism hardware. This paper introduces ASPEN, which aims to mitigate the synchronization barriers between operators and to uncover parallel computation opportunities across operators. ASPEN consists of two stages of optimizations: offline and runtime. In the offline optimization stage, an Automated Parallelism Unit (APU) is employed to convert operators into a tile-based fine-grained data-flow graph. Then, during runtime, the workloads are distributed across the hardware. The results demonstrate the efficient performance of ASPEN compared to other frameworks.", "questions": "- Algorithm 1 appears to be ad-hoc and heuristic, as it relies on the status of node execution. However, this heuristic cannot guarantee optimality and is not always effective. Have the authors considered other algorithms?\n- Have the results from TVM been tuned?\n- How does the memory consumption compare to other baselines? Do the optimizations incur any additional overhead?\n- While it is good for this paper to compare with different frameworks, including DNN primitive framework and compiler-based framework, TensorFlow is a general training framework, whereas ONNXRuntime and oneDNN generally perform better in the inference domain. It would be better if the authors could provide a performance comparison for these frameworks.\n- Is the improvement in speed mainly due to the Convolution and GEMM kernels?", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- This paper addresses a well-motivated problem and is easy to follow.\n- The proposed techniques are generally making sense and effective.\n- It includes a performance comparison of different model structures and significantly outperforms other frameworks for extreme deep model structures (such as GPT-2).", "weaknesses": "- The optimizations proposed in the paper appear heuristic and do not guarantee optimal performance.\n- The evaluation is not thorough, lacking some details on memory consumption and comparisons with other state-of-the-art frameworks, such as TASO, ONNXRuntime, and oneDNN.\n- It is unclear how to remove the barrier in the APU optimization. Does this involve a trade-off in memory consumption by loading multiple weights into parallel units?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments and feedback! In this response, we will address your individual concerns in addition to the general response. We hope this clarifies any concerns about our work.\n\n---\n> **Issue 1** The optimizations/algorithm appear to be ad-hoc and heuristic.\n\nOur work aims to present a dynamic DNN scheduling and execution approach that can increase parallel resource utilization during runtime using tile-based opportunistic parallelism. Therefore, the main algorithm (Algorithm 1) is not designed to optimize the execution of certain DNNs or environments. Instead, it focuses on enabling opportunistic parallelism and dynamically increasing resource utilization by continuously scheduling any newly available computations during runtime. This strategy permits each computation resource to accommodate as many computations as the DNN offers throughout the runtime. By keeping every resource maximally utilized, the algorithm can collectively achieve high throughput, regardless of the DNN or hardware used.\n\nWe agree that maximal utilization of the resources does not guarantee optimality, and there exists room for improvement in our algorithm. For instance, we find that some tiles are more important than others, and prioritizing them can accelerate the execution, due to the dependency patterns in the DNN formed from pooling and strided layers. In this work, however, in order to focus on providing a general solution that first enables the novel approach of tile-based opportunistic parallelism, we left optimizations for future work. Nonetheless, we will include more details on the optimality of our algorithm, and other dynamic scheduling approaches that can lead to optimality in executions.\n\n> **Issue 2** Removal of the barrier in the APU optimization is unclear. Does this involve loading multiple weights?\n\nThe key to removing synchronization barriers is in both the tile-based decomposition of DNNs in the APU and the dynamic dependency tracking in the runtime. Partitioning each operator and creating tile-based DNN which allows each tile to be managed as a graph node. Dependency is atomically updated for each node in runtime, allowing resources to check dependency states without synchronization. Through this, ASPEN removes the need for synchronization barriers and allows for much higher parallel resource utilization.\n\nThis also means that there is loading of multiple weights, as the computation remains the same. The details of ASPEN memory usage are further explained in the next response. In our final manuscript, we will make it clear that our contribution is not an optimization or trade-off on the existing algorithms, but a new approach to scheduling and parallelization of DNN computation.\n\n> **Issue 3** How does memory consumption compare? Do the optimizations incur any additional overhead?\n\nWe must first make it clear that ASPEN improves the parallel scheduling of DNN computations and does not alter the computation process of the DNN. Additional memory required by ASPEN is for creating tile-based graphs, and its nodes act only as instructions to compute the given tile location in a tensor. As such, it only holds references (pointers) to its respective tile locations and the tile locations referenced by the nodes are still a part of the original input/output tensors, as in the conventional operator-based approach.\n\nThe memory overhead of the tile-based graph used by ASPEN is minimal, as each node requires only ~100 bytes of memory. For example, in the ResNet-50 batch 1 case, ASPEN graph requires 836 kilobytes of additional memory, which is minuscule compared to the weights of ResNet-50, which is ~100 megabytes.\n\nOur submitted supplementary material of ASPEN may use a relatively larger amount of memory, due to the more relaxed memory allocations we used in our implementation. This is not reflective of the memory use required by the ASPEN algorithm itself. We will update our code to manage its memory as tightly as possible.\n\nIn our final manuscript, we will include explanations of how data are stored and managed in ASPEN, along with a detailed decomposition of ASPEN memory usage over different devices and DNNs. We also plan to fully release the ASPEN source code, so any details of ASPEN and its inner workings would become transparent.\n\n> **Issue 4** Are results from TVM tuned? It would be better if there are comparisons against more frameworks.\n\nWe use AutoTVM, following the instructions provided in the official TVM documentation. We compile our model in Python and export the model to C++ based TVM API for a fair comparison. We tried to include as many comparison baselines as possible, available in the C/C++ domain. However, some inference solutions include optimizations such as caching, approximations, or data modifications, which are largely orthogonal to the parallelism and scheduling contributions of ASPEN and make them unfair to compare to. \n\nHowever, we plan to include the suggested frameworks such as ONNXRuntime and oneDNN in our final manuscript, as these frameworks provide options to adjust the level of optimization and allow for a fair comparison.\n\n> **Issue 5** Is the speedup mainly from the computation kernels?\n\nOur improvement comes from the higher device utilization from the removal of synchronization barriers, increased parallelism, and data reuse from depth-first node execution, which allows better parallel scaling and increased per-resource throughput. As explained in the general response, our tile-based kernels are less performant than those of existing operator-based solutions. \n\nWe will include a more detailed decomposition of the performance contributions of ASPEN, including the performance of ASPEN kernels. However, it must be noted that contributions of ASPEN such as increased parallelism over operator boundaries, asynchronous interleaving of scheduling and computation, or data reuse from depth-first execution are most prominent in full end-to-end execution."}, {"review_id": "ctCR8RSeiy", "reviewer": "Reviewer_yggz", "summary": "When we run a deep neraul network, a sequence of operators are executed. The existing deep learning framework/compiler would wait for the completion of the prior operator (A) before launching the subsequent one (B). The authors of this paper observe that some computation in operator B only depends on part of the computation of operator A. Thus, the authors propose to decompose the operators into more fine-granularity and utilize the fine-grained dependency to expose more parallelism (they called it opportunitic parallelism). They implemented this idea and experiments show that it achieves up to 3.2x to 4.3x speedup compared with prior work TorchScript and TVM, respectively. ", "questions": "1. Could you please provide more case study to get the contributing factors of speedup?\n2. Could you elaborate more details of the ASPEN implementation?\n\n[Minor] \n\nIt's better to also cite and compare with Graphi[1], Nimble [2] and IOS [3] in Section 2 when discuss inter-operator parallelization. \n\n- [1] Graphi: Scheduling Computation Graphs of Deep Learning Models on Manycore CPUs\n- [2] Nimble: Lightweight and Parallel GPU Task Scheduling for Deep Learning\n- [3] IOS: Inter-Operator Scheduler for CNN Acceleration\n", "limitations": "1. Currently, only validated the effectiveness on CPU.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The authors observed the unnecessary barrior between operators and observe a new kind of parallelism.\n2. The authors implemented a prototype system (ASPEN) and experiments show that the new parallelism is benefitial to CPU inference on a multi-core CPU.\n", "weaknesses": "1. More case study is needed to justify where the speedup comes from. \n\nFrom Figure 6, we can see that ASPEN can achieve 4x (GPT-2 S1024 B1) and 2x (ResNet50 B128) speedup. I am quite interested in where the speedup come from. Usually, a new kind of paralleism (in this case, opportunistic parallelism) can have a good speedup when the existing parallelism is not enough to saturate the device. For example, parallelizing two operators would have a good speedup if each operator is not large enough to fully-utlize the device. However, the operators in the two models with large sequence length or batch size should be already large enough to highly utlize the device (rely on intra-operator parallelism), then how can the opportunistic parallelism gain more speedup? Does other factors contribute to the speedup? For example, C++ implemented runtime, statically allocated memory (instead of dynamic allocated as in PyTorch), more efficient kernels for other operators like batch norm, group norm, and softmax, better micro kernels for gemm. Thus, I would suggest to add more case study to decompose the speedup. For example, do some operator-level and sub-graph-level experiments, use profilers to analyze the CPU utilization, use ASPEN's microkernels but do not use opportunitic parallelism (e.g., keep the operator barrier) to get the performance change.\n\nBTW, I have tried the ResNet50 example and observed good speedup on my workstation. \n\n2. More dtails for ASPEN implementation and baselines are needed\n\nFor the TVM baseline, what scheduler have you used: AutoTVM or AutoScheduler (Ansor)? What tuning configuration did you choose? For ASPEN, did you write all kernels by yourself, or based on any existing BLAS library? \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments and feedback! In this response, we will address your individual concerns one by one in addition to the general response. We hope this clarifies your concerns about our work.\n\n___\n\n> **Issue 1** More case study is needed to justify where the speedup comes from.\n\nWe agree that ablations studies on the operator or sub-graph level would be helpful to further understand the speedup of ASPEN. However, it must be noted that contributions of ASPEN such as increased parallelism over operator boundaries, asynchronous interleaving of scheduling and computation, or data reuse from depth-first execution are most prominent in a full end-to-end execution and are not easily visible in microbenchmarks with a limited number of operators or computations. Nevertheless, we plan to add kernel-level performance evaluations and memory and CPU utilization profiling results to our final manuscript, to more clearly show where the benefits of ASPEN come from.\n\nFor the increased speedup in large input sizes, we attribute the cause of the speedup to the isolation of each computation resource in ASPEN. In a traditional two-layered operator-based computation, it cannot be guaranteed that dependent computation tiles will be scheduled to the same parallel resource during subsequent operators, as operator calls are implemented as separate function calls. As such, scatter-gather memory movements between resources are required to share their computation data, which causes increased memory overhead and loss of computation utilization, whose impact increases as the number of parallel resource scales.\n\nDepth-first computation algorithm of DSEs and the two-dimensional Ready Pool allows dependent computation tiles to be scheduled to the same computation resource as much as possible, achieving effects like that of operator fusion, but in an implicit way. This reduces memory traffic between resources and allows data to be reused as much as possible. With large enough input sizes, it becomes possible that each resource never has to share its computation outputs with other resources, as each DSE is automatically allocated computation paths with different batch indexes, greatly reducing the memory overhead of the computation. Also, it should be noted that even when there are data shared between resources, only a few resources are involved simultaneously, which relieves the pressure on the memory system.\n\nIn our final manuscript, we will add a clear and explicit explanation of what isolated computation paths from large input sizes mean, and how it improves the execution of ASPEN in terms of scalability, data movement, and resource utilization.\n\n> **Issue 2** More details for ASPEN implementation and baselines are needed.\n\nWe will include more implementation details such as memory layout and access patterns of ASPEN, as well as details on computation kernel implementations and evaluation environments in our final manuscript. We also plan to fully release the ASPEN source code, so any details of ASPEN and its inner workings will be very transparent.\n\nFor the TVM baseline, we used AutoTVM following the instructions provided on the official TVM documents. We compiled the TVM programs in Python and exported them to C++ based API of TVM for fair comparison. We wrote all our kernels by ourselves. We used simple for-loops for our kernels except for the matrix multiplication kernels of tile sizes 1x8 to 12x8, for which we used AVX2 intrinsic for vectorization. These matrix multiplication tiles were also used inside other kernels, such as convolutions or linear layers.\n\n> **Issue 3** It is better to also cite Graphi, Nimble, and IOS in Section 2.\n\nThank you for mentioning this! We will include them in our final manuscript.\n"}, {"review_id": "5oN4yCKDs7", "reviewer": "Reviewer_Cexe", "summary": "The authors proposed ASPEN, an opportunistic parallelism method that breaks the synchronization barriers of each operator presented in a DNN graph so that parallel compute resources can tranverse and execute multiple data-paths independently with much less synchronization overhead in a **shared memory** system. This is achieved by: \n* Split the operators/tensors to multiple tiles thus multiple data-paths along the dataflow graph\n* Implements **decentralized** executors to tranverse these data-paths indepently with only in-demand synchronization with a **centralized** information pool that captures the dependencies of the split graph", "questions": "In addition to the questions mentioned in Weakness, here are a few more:\n1. As author mentioned, column-wise (aka on batch-size) graph partitions typically expose most parallel paths (line 173) that doesn't require synchronization with the pool. But do you also partition row-wise/image-wise? Since these partitions may incur reduce-scatter/all-gather operations (even batch-partitioned Resnet have similar issue due batch-norm), are they handled by ASPEN? Even if it is a shared memory system, would it introduce high overhead? And if so, how do ASPEN decide which dimension to tile and to what degree?\n\n2. in line 281, the authors mentioned GPT2 is only evaluated for prompt/question encoding which usually has large sequence length. However the majority of a generative inference task is a per token infernece where Batchsize = SequenceSize = 1, how is ASPEN's performance on this? have you considered head tiling to speed it up?", "limitations": "The authors have discussed the limitations which are plausible, however there are still a few more to address:\n1. Efficacy on GPUs. The authors mentioned similar ideas can be implemented with CUDA Streams and Events, however as mentioned earlier, GPUs don't have such high threading overhead, so its efficacy is quesitonable compared to un-tiled but well vectorized GPU kernels.\n2. Though the implementaiton of DSE and Ready Pool looks robust, due to it is still a runtime/software managed data dependency controller, its efficiency can't be compared to a native dataaflow architectures with hardware managed data dependency, e.g, IPU/RDU/WSEs from GraphCore/SambaNova/Cerebras.\n3. As authors suggested, ASPEN can improve system utilization when shared with users, however this comes at the cost of higher per user latency even though overall system utilization can be higher.\n4. As is mentioned in weakness, it is limited to a shared memory system so can't be leveraged in a distributed system.\n5. The authors said ASPEN is orthogonal to existing fusion and slicing techniques (line 138), however, fusion and slicing would either amortize barrier overhead or fight for slicing/splitting degrees with ASPEN, which diminishes the performance gain of ASPEN.\n\nNevertheless, ASPEN still shines on the exploratory works it has conducted for opportunisitic parallellism in ML, despite all the limitations above.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The authors explored opportunisitic parallelism, a less studied/adopted parallelsm in modern machine learning frameworks/infrastructures, which is particularly helpful when three scenarios are present, namely:\n  1.  The hardware system has significant threading (barrier overheads) like CPUs\n  2. The ML models enbrace multiple data-paths (like residual connecitons or multihead attention)\n  3. The input data has limited fully independent dimension like batch dim during inference\n\n* The implementation of ASPEN is intuitive/efficient with correctness/completeness proves\n\n* The evaluation of ASPEN on Resnet and Bert demonstrated its effificacy (significant speedup) compared to popular frameworks implemented with operator barriers.\n\n* ASPEN could be helpful on inference environment with heterogeneous/edge devices", "weaknesses": "* While the authors explored opportunisitic parallelism and demonstrated its efficacy on a single CPU with multi-cores, its application is limited as the three scenarios mentioned in Strengths hardly coexist in modern ML workloads, e.g,.\n  1. GPUs don't have such high threading overheads, thus has much higher intra-operator parallel efficiency. GPU systems are usually bottlenecked by device memory bandwidth or interconneciton bandwidth, which can't be solved by opportunisitic parallelism.\n  2. When the app has abundant input data (e.g., large batchsize) like in training or batched inference, ASPEN is not likely to provide performance margin over other frameworks (line 328)\n\n* ASPEN is only valid for a shared memory system, e.g, multi-threading on a single CPU, when scaled to multiple CPUs or multiple hosts (e.g., multi-processing), the IPC or interconnections could introduce significant memory overhead\n\n* Some of the implementations are not very clear, e.g,.\n  1. in line 176, the authors metioned the graph is split/merged column-wise and row-wise, but on line 178 it said \"It merges the tiles column-wise\" and nothing is mentioned for row-wise, so is in Figure 3.\n  2. The explanation of Ready Pool in section 3.3 is not very intuitive. On a high level I understand it tries to prioritize ready nodes with shallower depth and data reuse, but I am not sure why it has to be a matrix with hashing to column indices, e.g., why is a row-wise priority queue not enough\n  3. The authors didn't explain how memory allocation/deallocation is handled, e.g., is splitting operatos results in memory fragmentation? When is the time to garbage collect and who handles it, etc.\n\n* Evaluations are not comprehensive or a bit contradictory to the claims:\n  1. ASPEN should provide more values when the input size is small (line 109/328) compared to other frameworks, however Figure 6 shows that ASPEN demonstrates higher speedup when input/batchsize is larger, and authors attributed to larger inputs faciliate an increased number of isolated computation paths across operators, however, other frameworks should also benefit from it as it amortizes barrier overhead (line 328)\n  2. Related to 1, therefore an ablation study on how batch/sentence/image size affects ASPEN should be provided to understand where ASPEN really outperforms other platforms. Addtionally since the authors mentioned models with more execution paths are likely to benefit (line 290), it is worth breaking down ASPEN formance on MHA and MLP(FFN) of a transformer layer to see which provides more performance gain. Other than MHA, artificial graph with various execution pass may also serve as a good ablation study.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments and feedback! In this response, we will address and clarify your individual concerns one by one. \n\n___\n\n> **Issue 1** Applications of ASPEN are limited.\n\n* GPUs don't have high threading overheads and are bottlenecked by memory bandwidth\n\nOvercoming the threading overheads is one of the main contributions of opportunistic parallelism, but its dynamic and asynchronous nature provides additional benefits. We explain the detailed benefits of ASPEN on GPU in the general response.\n\n* ASPEN is not likely to be useful with abundant inputs.\n\nAs shown in the evaluations, this is clearly not true. We explain this in detail in Issue 4.\n\n> **Issue 2**  ASPEN does not scale to multiple hosts.\n\nWe are currently extending ASPEN to a multi-host system as a separate work. We first separate the ASPEN graph into subgraphs that belong to different hosts. Once a DSE computes a node, it checks if its child belongs to a different host, and sends its data to the child’s host if so. The receiving host marks the node as complete and updates its child nodes. A child node enters the ready pool only when it belongs to the current host. ASPEN also brings benefits to such multi-host scenarios as the host computations and data transfers are effortlessly interleaved with one another, allowing for high utilization of both the hosts and the network.\n\nThis is clearly beyond the scope of proposing the concept and implementation of opportunistic parallelism in this paper, but to provide an insight into the potential of ASPEN, we will include a discussion on the multi-host extension.\n\n> **Issue 3** Some implementations are unclear.\n\n* Row-wise split/merge is missing on line 178 and Figure 3.\n\nRow-wise split/merge happens in stage (d) of the given example. We will make this explicit.\n\n* Why is a row-wise priority queue not enough?\n\nThe hashing and priority queue is combined to facilitate fast access times. By using hashing and priority queues, we can place shallower/deeper nodes in higher/lower priority queues in constant time and retrieve them in constant time. If we used sorted structures such as heaps, the access times would have scaled to the number of nodes, which would possibly be a bottleneck in the system.\n\n* How is memory handled?\n\nNodes of ASPEN graphs act only as instructions to compute the given tile in a tensor. As such, it only holds pointers to its respective tile location. These tile locations are still a part of the original input/output tensors, as in the conventional operator-based approach. As such, no fragmentation exists, and memory allocation works in the same way in existing solutions. While we currently do not have runtime memory management, its implementation is trivial. Tensors are allocated when one of its tiles becomes ready and is deallocated when all dependent tiles of the tensor are computed. The allocation is handled by the DSE which updated the tensor’s first readied tile, and deallocation by the DSE which computed the last dependent tile.\n\nWe will include the above explanations in our final manuscript. We also plan to fully release the ASPEN source code, so any details of its inner workings will be transparent.\n\n> **Issue 4** ASPEN is faster with a larger input size, which is not comprehensive to the claims. Ablation studies are needed.\n\nIncreased batch sizes benefit ASPEN execution as it enables much greater data isolation between resources. In a traditional two-layered operator-based computation, it cannot be guaranteed that dependent computation tiles will be scheduled to the same parallel resource, as each operator computations are separate function calls. This requires scatter-gather memory operations between the parallel resources, which causes increased memory overhead and loss of computation utilization, whose impact increases as the number of parallel resource scales.\n\nDepth-first computation and the Ready Pool allow dependent tiles to be scheduled to the same resource as much as possible, achieving effects like that of operator fusion. This increases data reuse and reduces memory traffic between resources. With large enough input sizes, it becomes possible that each resource never has to share its outputs with other resources, as each DSE is automatically allocated paths in different batch indexes, greatly reducing the memory overhead. Also, even when there are data shared between resources, only a few resources are involved simultaneously, which relieves the pressure on the memory system.\n\nIn our final manuscript, we will add a clear and explicit explanation of what isolated computation paths from large input sizes mean.\n\nWe also agree that ablation studies such as varying input sizes, and sub- or artificial-graph level experiments can help understand the speedup of ASPEN. However, contributions of ASPEN such as increased parallelism over operator boundaries, or asynchronous interleaving of scheduling and computation are most prominent in an end-to-end execution and are not easily visible in microbenchmarks. Nevertheless, we plan to add the mentioned evaluations.\n\n> **Issue 5** Partitioning row/image-wise would incur high overhead.\n\nAs explained in Issue 3, tiles are referenced as pointers, and the tensors are not actually partitioned in memory. Therefore, scatter/gather or other memory operations that are not present in operator-based computations are unnecessary.\n\n> **Issue 6** How is ASPEN’s performance on per-token inference? \n\nAs per-token transformer inference is similar to a single chain of matrix-vector multiplications, there is limited room for opportunistic parallelism, and thus the performance is quite limited. However, additional optimizations such as head tiling or iteration-level scheduling proposed by Orca (Yu et al., OSDI 2022), can be integrated for increased performance. We believe that these techniques would bring novel and intriguing prospects when combined with fine-grained dynamic scheduling and execution of ASPEN."}]

Author rebuttal:
General Response
---

Thank you for taking your time to review our paper! In this response, we will explain the essential value of ASPEN and the reasons behind our selection of evaluations. Then, we will clarify individual questions and concerns one by one.

As an exploratory work on fine-grained dynamic parallelism of DNNs, ASPEN aims to provide insights and solutions to the novel computation approach of applying tile-based opportunistic parallelism to DNNs. As explained in the paper, available DNN computations are scheduled in two hierarchical layers of inter-operator and intra-operator computations using a dataflow graph of operators. However, this two-layer approach limits the available parallelism within each operator in the form of synchronization barriers. This limitation in parallelism has been identified as a major bottleneck in resource utilization by previous studies such as Rammer (Ma et al., OSDI 2020).

As described in Section 2, many solutions have been proposed to alleviate this issue. However, they still rely on the use of operators, which inevitably limits parallelism to some extent. On the other hand, ASPEN opts to take a completely new approach by removing the use of operators entirely and dynamically scheduling any parallel tiles that are available for computation. This effectively combines the separate inter- and intra-operator computation spaces into a single unified space of tile-based dataflow graph. This approach has yet been explored in the literature and enables the complete removal of the limited parallelism caused by the operator-based approach. In this framework, any computation tile can be assigned to a computation resource as soon as it becomes available, independent of which operator it belongs to, leveraging the concept of opportunistic parallelism.

Unfortunately, due to the uniqueness of our work, only a limited array of existing software infrastructure is available, curtailing its potential for the incorporation of tile-based computation kernels. For this reason, we wrote our tile-based kernels in C and left the optimizations to GCC in our evaluations on CPUs. While these kernel implementations may not be as finely optimized as the existing high-performance computation libraries, they still allow us to demonstrate the capability of ASPEN’s novel parallelism and scheduling approach in achieving substantial parallel resource utilization on CPUs. However, it is worth noting that such kernel generation is not applicable to less programmable hardware such as GPUs, as their code is much more hardware dependent with proprietary software stacks, and their kernel compilers are not versatile enough to be applicable to tile-based kernels. As a result, our demonstration of the efficacy of ASPEN is limited to its maximal available scope (as of now).

Nonetheless, we believe that with the appropriate computation kernels, the novel approach proposed by ASPEN will greatly benefit DNN executions on GPUs, for the following reasons. One of the limiting factors to a high GPU utilization is the host-device scheduling and communication overhead in both data movement and kernel launches, as reported in studies such as Rammer and Nimble (Kwon et al., NeurIPS 2020). The dynamic and asynchronous nature of ASPEN allows for the seamless interleaving of data movement, kernel launches, and tile executions, enabling concurrent scheduling and processing. As a result, ASPEN greatly reduces the overhead of host-device communications. This asynchronous nature also means that the computing resources are at different stages of kernel execution during computation, which leads to the distribution of memory access requests across the temporal domain. This decreases the pressure on the shared memory bus and allows better utilization of the memory system, which mitigates the limitations in memory bandwidth that DNN executions on GPUs often face, as mentioned in studies such as Alpa (Zheng et al., OSDI 2022) and Welder (Shi et al., OSDI 2023).

Furthermore, we find that tile-based GPU kernels for DNNs are becoming available soon. To be specific, we find that Welder, a memory optimization work released a few weeks ago (July 2023), constructs a tile-based dataflow graph during its offline optimization stage, which can be used as an ASPEN graph with minor modifications. Although Welder still uses conventional operator-based execution during runtime, thus keeping ASPEN’s contributions untouched, we find that its GPU kernels can be decomposed to its offline tile-based form and be modified into a computation backend suitable for ASPEN. Leveraging these kernels, an effective extension of ASPEN for (Nvidia) GPUs is feasible using CUDA Streams and CUDA Events API. A separate CUDA Stream allocated to each DSE allows kernels launched by different DSEs to run concurrently, and DSEs can asynchronously check the completion of a kernel and update its child nodes using CUDA Events. Regardless, GPU support for ASPEN would not alter the core logic and design of ASPEN in any way, and therefore the contributions and benefits of ASPEN presented in our paper remain intact.

Tile-based understanding of DNNs has gained significant traction in recent years, as it provides a holistic view of the DNN and allows for a finer-grained analysis and management of both computation and data, which enables contributions that were previously impossible with the operator-based dataflow graphs. ASPEN is the first to explore the benefits of tile-based DNNs during runtime. Unlike previous tile-based works which focused on offline analysis and optimizations such as graph compilers (Roller, Zhu et al., OSDI 2022) or memory usage (Welder), ASPEN focuses on the benefits of tile-based DNNs on parallel resource utilization during execution using opportunistic parallelism. We hope that this clarifies the core value of ASPEN as an exploratory work providing insights and algorithms for tile-based dynamic scheduling and computation of DNNs.

Meta-review: This paper presents a framework for exploiting fine-grained parallelism to improve the performance of neural networks, particularly on CPUs. All of the reviewers supported acceptance and agreed that the results were promising. There seems to still be a long way to go in fully proving out the approach in this paper in practice (e.g., for multiple CPUs, larger batch sizes, single and multiple GPUs, etc.), but the promise of the work merits publication in my mind. I expect the authors (and many others) to build on this work toward making it practically impactful.
Decision: Accept (poster)