s2fieldsofstudy:
Computer Science
Business

text:
Enhanced Minimal Scheduling Function for IEEE802.15.4e TSCH Networks

MAC layer protocol design in a WSN is crucial due to the limitations on processing capacities and power of wireless sensors. The latest version of the IEEE 802.15.4, referenced to as IEEE 802.15.4e, was released by IEEE and outlines the mechanism of the Time Slotted Channel Hopping (TSCH). Hence, 6TiSCH working group has released a distributed algorithm for neighbour nodes to agree on a communication pattern driven by a minimal scheduling function. A slotframe contains a specific number of time slots, which are scheduled based on the application requirements and the routing topology. Sensors nodes use the schedule to determine when to transmit or to receive data. However, IEEE 802.15.4e TSCH does not address the specifics on planning time slot scheduling. In this paper, we propose a distributed Enhanced Minimal Scheduling Function (EMSF) based on the minimal scheduling function, which is compliant with 802.15.4e TSCH. In this vein, we introduce a distributed algorithm based on a Poisson process to predict the following schedule requirements. Consequently, the negotiation operations between pairs of nodes to agree about the schedule will be reduced. As a result, EMSF decreases the exchanged overhead, the end-to-end latency and the packet queue length significantly. Preliminary simulation results have confirmed that EMSF outperforms the 802.15.4e TSCH MSF scheduling algorithm.

I. INTRODUCTION
The next industrial revolution is announced to be Industry 4.0, which will reduce cost and maximize flexibility with the use of digital automation [1]. The Industrial Internet of Things (IIoT) plans to connect to the Internet a large number of industrial objects. In this regard, it is mandatory for real-time infrastructure to be highly reliable for wireless transmissions. So far, the efforts undertaken in IoT were for best-effort solutions, but industrial applications demand a higher level of control in terms of reliability and delay [2]. For that reason, specific MAC protocols are needed to add strict guarantees. Deterministic approaches, especially, can be used to allocate a fixed bandwidth to every device or flow. In addition, these approaches can isolate flows, where each type of flow gets a specific transmission bandwidth. In IEEE 802. 15.4e TSCH mode, channel hopping mechanism is used to reduce external interference and fading. TSCH deploys a deterministic approach to avoid collisions by careful scheduling, which involves allocating a group of cells for interfering transmitters to avoid collisions while reducing contention. A number of centralized and distributed scheduling algorithms have been introduced as of date for TSCH [3]. Over-provisioning is a method used to cope with unreliable links in the schedule by reserving a few cells to allow a packet to be retransmitted. However, extra cells leads to an increase in delays and jitter [4]. Network capacity is also reduced if there is too much traffic and/or lack of reliability due to external interference. In order to handle the issues concerning scheduling, routing and internet integration, the IETF IPv6 through the TSCH mode of IEEE802.15.4e was established for an improved integration of the IPv6-enabled protocols such as RPL, 6LoWPAN and CoAP [5]. In this paper, we propose an Enhanced Minimal Scheduling Function (EMSF) in order to improve reliability and latency when pairs of nodes are dynamically determining their bandwidth requirements. The proposed algorithm is based on the minimal scheduling function (MSF) schemed for the 6TiSCH networks. Our proposal is designed to meet the following goals: 1) A dynamic scheduling: The proposed scheme allocates and deallocates cells without considering the thresholdbased mechanism. 2) A reduction of the transmitted data during the scheduling negotiation phase: The EMSF is designed to meet this target by introducing a prediction system model which anticipates the data to be transmitted for each pair of nodes in the next slotframe. 3) A reduced latency: This design is introduced by minimizing the overhead control packets in order to diminish the end-to-end data transmission delay and the queued data.
The remainder of this paper is organized as follows. In section II, we provide an outlook to the 6TiSCH WG over the 802.15.4e TSCH mode. We discuss some background information and related work in section III. The design of the system is described in section IV and V. We illustrate, in section VI, the results of simulations that show the performance of our approach, and we conclude the paper in section VII.  15.4e TSCH network communicate using a time-slotted mechanism over multiple frequencies, which follows a Time Division Multiple Access (TDMA) schedule. It partitions the wireless spectrum into time and frequency, which is scheduled over a set period of time. This scheduling is also called a superframe or a slotframe. A node transmits/receives data to/from its neighbours on a predefined timeslot and channel in the schedule. A cell, which is usually 10ms in length, is a basic unit of bandwidth scheduled. The transmitter in a cell sends a data packet to the receiver. Once successfully received, an acknowledgement is sent back by the receiver. Channel-hopping improves communication by making it more reliable through diversification of frequencies. This statistical mitigation reduces narrow-band interference and multi-path fading. Cells can contain multiple communication links as long as they are not conflict links nor links interfering amongst each other. Conflict links are those that have the same receiver and/or transmitter. The communication links bounce over a series of available channels in a quasirandom way between the super-frames. Both the sender and the receiver for each scheduled cell will use Eq.(1) to calculate communication frequency, i.e., f [6]: where F is the mapping function for channel frequency, ch offset is the channel offset, ASN is the total number of timeslots, and finally mod N ch is the modular division of N ch , which refers to the number of available physical channels. ASN is calculated as follows: where K is the slotframe cycle, S is the size of the slotframe, and T are the allocated timeslots.

B. Scheduling in 6TiSCH networks
Recently, 6TiSCH Wireless Group was working to define a pre-configured or learned minimal schedule of a node that joins a network with static scheduling configuration [7]. Various kinds of frame are transmitted and received through cells within a schedule determined by slotted ALOHA protocol. Note that static scheduling within 6TiSCH is used only for specific situations like during the bootstrapping stage or as a fallback during network failures. For other situations, a scheduling function is used in order to allocate or deallocate cells between neighboring nodes. 6TiSCH uses MSF as a default scheduling function presented in the IETF draft [8]. The allocation policy and the bandwidth estimation algorithm are used by MSF to determine when cells in neighbouring nodes should be added or deleted [9]. In addition, MSF uses a threshold-based mechanism to mitigate against sudden fluctuations and increases in bandwidth by adding or deleting operations. Both add and delete negotiations are similar, however. Despite that, given two nodes A and B in a network, node B contains all slotOffsets of node A candidate cells of the remove CellList requests. Since candidate cells are randomly selected, there is a high likelihood of negotiation errors at node A. This is due to the fact that node B contains fewer cells in CellList with available slotOffsets than NumCells. In addition, other pairs of nodes may use allocated cells that are also used by nodes A and B. This may cause network collisions, which are mitigated by the scheduling function. The minimal scheduling function uses 6top Housekeeping function to track cell usage and performance and to relocate cells that have collided [10].

III. RELATED WORKS
Constructing a schedule is application specific and several scheduling algorithms have been introduced to schedule TSCH networks. Different proposals could be used to set up the schedule. They can be classified as centralized and distributed. In centralized approaches, the DAG root builds and maintains the schedule for the entire network. Palattella et al. proposed Traffic Aware Scheduling Algorithm (TASA), a centralized scheduling technique that uses a leading-edge matching and colouring method of graph theory to map the distribution of time slots and channel offsets [11]. The motes in the network send the requirements of bandwidth and energy, TASA computes a schedule that satisfies those requests and returns them back to the motes. In distributed approaches, the nodes negotiate with their neighbors to build their own schedule. Accentura et al. proposed Decentralized Traffic Aware Scheduling (DeTAS), which builds optimal collisionfree multi-hop schedules [12]. DeTAS employs neighbourto-neighbour signaling in order to gather network and traffic information. It ensures the smallest queue utilization and the shortest possible end-to-end latency period between when the data was generated to when it was received. Orchestra is another non-graph scheduling technique in which nodes compute their own local schedules, hence the reason its referred to as autonomous scheduling of the TSCH in IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL) [13]. It has no central entity nor negotiation and allocates slots such that it can be installed or deleted automatically with the evolution of the RPL topology. Despite that, it does not offer any solution against bursty traffic. Domingo-Prieto et al. introduced a distributed scheduling algorithm as a solution against sudden or bursty traffic, which uses a control paradigm called Proportional Integral and Derivative (PID) [14]. Techniques based on graph theory have been introduced to other networks including peer-to-peer networks and cognitive radio networks. It is worth mentioning that the work of Domingo-Prieto et al. is the first one to use graph-theory based combinatorial properties to address scheduling in IEEE 802.15.4e TSCH networks. Soua et al. proposed the Wave scheduling algorithm [15]. It aims to reduce the slotframe size by dividing it with a unit called wave and achieving waves many times to build a schedule for all the nodes at proper intervals of time to the DAG root. Every node with a transmittable packet is allocated both a timeslot and a channel for every wave. The slot or channel pattern is determined by the first wave. The following waves are modeled after the first wave, however only the transmission-containing slots and the order in which they repeat themselves are copied from the first wave. Determining a schedule is application-specific and it's based on the metrics that need to be improved. The proposed 6TiSCH WG minimal scheduling function [7] defines how nodes add or remove cells based on a bandwidth estimation algorithm. This method is based on exchanging control packets to measure the required bandwidth. Hence, more resources are appealed to determine the appropriate measurements which leads to an increased probability of dropped packets and a high latency. Note that, unlike the existing scheduling approaches, our method will guarantee a minimum negotiation overhead which will reduce the latency, the packet queue size and the resource utilization. Our proposed model is based on three indispensable steps: 1) Computation of the average generated packets in the previous slotframes 2) Prediction of the amount of data (event/periodic).
3) 6p add/remove transaction according to the predicted model.

IV. PROPOSED SYSTEM
In this section, we will introduce some definitions and assumptions of the system model. When a 802.15.4e TSCH node detects a substantial unpredictable physical event, a massive flow of data packets is generated and queued by the node. These nodes check if they have sufficient bandwidth to send these packets to their parents. A limited number of transmissions and re-transmissions are allowed by each node, which, when exceeded, cause packet dropping. This appliance triggers a tremendous number of packet transactions and a spike in resources usage. To reduce negotiation errors, number of dropped packets and end-to-end latency times, we propose a novel scheduling function based on the minimal scheduling function presented in the IETF draft [8]. The proposed mechanism consists of the following two main operations: Computation of the mean of packets generated by each node and the prediction of the required cells in the next slotframe. First, we introduce some definitions: • Definition 1: We focus on event-driven WSN where nodes measure physical events and send it to the sink in an upstream data circulation transfer. • Definition 2: We define the network topology as graph G = (V, E) where V is the set of all nodes and E is the set of edges between the nodes displaying symmetric communications links. • Definition 3: In a data gathering frame of any node n we denote G(n), which is the number of data transmitting packets sent by node n and T(n), which is the sum of all the packets sent by n including G(n) and the number of packets received by the parent from its children.
Therefore, we define T(n) using the following equation: • Definition 4: We define Q P C (n) as the number of packets in the queue of n that has to be sent to parent and C P C (n) the number of cells already allocated between the parent p(n) and the child c(n). • Definition 5: After executing the scheduling algorithm and based on its output, nodes in G will either add, delete, or keep cells in the next slotframe S i+1 . In this paper we adopt the following assumptions: • Assumption 1: We assume that the gathered data network topology and the routing tree are provided. • Assumption 2: We consider also that the links of the routing tree are symmetric, since user data is gathered upstream, whereas the schedules are negotiated in a distributed fashion between nodes. • Assumption 3: Symmetric links are a requirement for the instant acknowledgment policy.

V. ENHANCED MINIMAL SCHEDULING ALGORITHM A. Prediction of the amount of data
In 802.15.4e TSCH networks, a node transmits two types of packets: Periodic data A w i (n) and Event-driven data A v i (n). Periodic data consist of enhanced beacons, which contain information about the actual ASN, the length of the timeslot and other information about the network. Event-driven data are sent upon the detection of a physical event. The total of a throughput a node generating is illustrated by the following formulas: Which is equivalent to:

B. Poisson-based packet generation model
As mentioned in the last section, we considered the 802.15.4e TSCH network as an event-driven network, where sensor nodes report data to the sink only when they obtain new data (an event occurs in a sensing area). We formulate the scheduling problem as a Poisson process model to describe the data generation. Process Poisson Definition [16]: A Poisson process N (t), t ≥ 0 with intensity λ > 0 is a counting process with the following properties. 1) Independent increment: For all t 0 = 0 < t 1 < t 2 < < t n , then N (t In the network, we consider the generated packets by different nodes as an independent event with no relation with the preceding event. Lemma 2: The Time T between each slotframe S is finite (slotframe durations stay the same through all the scheduling). Based on lemma (1) and (2), we can adopt a Poisson process model to describe data generation packets in the network. The distribution of the number of data packets, N (T ), generated by each node in the network from the beginning to the end of the slotframe is equal to the following formula: where λ is the average number of packets generated after a certain number of slotframes have passed since the two nodes are synchronized to the schedule. Mathematical, λ is defined by the following formula: where T is the actual instant, nbP acket i (n) is the number of packets generated by the node n in the instant T = i and β is the sum of previous number of slotframes which can be validated through simulations. In order to get an accurate value of λ, the protocol will execute it's scheduling algorithm with the minimal scheduling function up to β = 10 slotframes.
An illustration of the execution of the system model is described in Fig. 1. As an example, the nodes A and B are exchanging packets over the built scheduling by the minimal scheduling function. Starting from slotframe S = 10, using Eq.(7), node B determines the average number of generated packets in the previous slotframes since it joined the network as it is shown in Fig. 1(a). Then, the average number is used in Eq.(6) in order to determine the probability of getting a determined number of packets as depicted in Fig. 1(b). This operation will be repeated until a maximum probability value is reached. Based on the predicted output as observed in Fig.  1(c), the algorithm will execute either an add or a remove 6p operation explained in the following section.

C. Add/remove cells
Starting from a given slotframe cycle, each node in the network will execute the Algorithm 1. The purpose is to predict the number of packets that will be generated by each node in the next slotframe. To reduce resource computation by each node, the algorithm stops when a maximum value of λ is reached. By knowing the number of packets that will be generated in the next slotframe, a node can predict how many cells are required in order to exchange data with its preferred parent. Based on the output of the algorithm, a node can trigger a 6p transaction with its preferred parent either to add, or remove cells to the TSCH schedule of both nodes. if (p < C p c (n)) {Compare p with the actual reserved cells for node n} then 13: 6P DELETE command (p) {6P delete request of C p c (n) -p slots} 14: elseif (p > C p c (n)) then 15: 6P ADD command (p) {6P add request of C p c (n) + p slots} 16: end if 17: end for

VI. PERFORMANCE EVALUATION
We conducted our simulations on OpenWSN, which is an opensource network simulator for wireless sensor networks. The simulator supports a few major types of protocol based on IoT standards, such as 6LoWPAN, RPL, ROLL, and CoAP. All the protocols based on OpenWSN 6TiSCH use the latest IEEE 802.15.4e TSCH standard in order to improve their reliability and stability [17]. In order for OpenWSN to remain up to date and have the desired network metrics, it provides a pythonbased configuration tool that allows its network parameters to be modified. The behavior of the network (such as PDR in every channel), the node queuing priority and the timestamp of each sending and receiving packet is recorded and then simulated. Table I shows the parameters used in the OpenWSN simulation. A. 6p error ratio 6p negotiation error ratio is the average ratio between the number of 6p transaction errors and the total 6p transactions throughout a slotframe cycle. Fig. 2 displays the way that the 6p negotiation error ratio is affected by the network density. The number of nodes passes from 10 to 100. The negotiation Fig. 2. 6p error ratio error ratio increases with the increase in network density. In the MSF scenario, it goes from 2.1% to 19.8%, whereas in EMSF scenario it goes from 0.2% to 3.5%. This is due to the decrease in the number of control packets and to the substitution of the threshold-measurement mechanism that is needed for the prediction system to add or delete 6p operations. The number of 6p exchanged packets decreases, which leads to a lower negotiation-error ratio. The suggested mechanism, the EMSF, largely surpasses the MSF and keeps the negotiation-error ratio under 3.5% for all of the network densities. Fig. 3 represents the overhead traffic load in bytes that was employed by nodes in order to exchange 6p information in the network. We notice that the number of exchanged messages increases linearly with the number of deployed nodes. This is due to negotiation exchanges taken between pairs of nodes to determine the 6p operation that will be deployed. We notice that the EMSF maintains an almost constant amount of exchanged packets. This is due to the prediction algorithm that anticipates the number of required cells for each pair of nodes in the following slotframe. EMSF avoids sending overloads and keeps a constant average of control packets through the network lifetime.

C. Latency
The latencies are calculated as follows: Every packet is timestamped since it is generated in the application layer of a source node, until it reaches the application layer of the DAG root. As a result of this condition, retransmission on a MAC layer is not taken into consideration. However, if a packet is repeatedly transmitted, a peak in latency may occur. When a packet achieves 4 MAC retransmissions attempts and the queue is full, a packet will be considerably dropped. Each node sends a fixed traffic load of 2 packets per slotframe for the first 50 slotframes. Thereafter, each node sends a sporadic traffic load ranging from 2 to 7 packets per slotframe. 20 nodes were deployed in this simulation. An end-to-end latency comparison between MSF and EMSF is illustrated in Fig.4. The latency was almost constant for the first 50 slotframes because of stable transmitted data flow. Thereafter, latency varies in between cycles as a result of the failing stochastic transmissions based on the PDR between the nodes. EMSF keeps an end-to-end latency below 75 milliseconds in almost all the slotframe cycles. This is due to its scheduling mechanism that minimizes the overhead charges, which increases the PDR even when irregular data flow is generated.

D. Node queue size
The following Fig. 5 represents the average number of packets in the queues of the network nodes. From this figure, it can be seen that in the case of MSF, node queues are almost full and reach their maximum (5 packets) in some slotframes causing more dropped packets. On the other hand, EMSF shows better performance in this concern. Throughout 200 slotframes, EMSF shows an average queue size ranging from 0 to 4 packets. In a lot of cases, nodes over-allocate cells, especially those near to the DAG root. This is due to the prediction algorithm in the case where a high packet rate is generated in the previous slotframes. This will allocate more cells between pairs of nodes, which will be used when an unpredictable event occurs. For instance, given an average number of generated packets equal to 10 in the previous slotframes, a node generating 5 packets will allocate cells based on the average number of packets generated since the time it joined the network. This means that, even though a huge number of packets is generated, the node has already reserved more cells than its requirements. Therefore, packets tend to queue up less, but consume more energy and than in the case of MSF.

VII. CONCLUSION
In this paper, we formulated the scheduling function for IEEE 802.15.4e TSCH networks as a Poisson process model. We demonstrated that, based on the prediction algorithm, scheduling negotiation overhead is decreased noticeably. In addition, simulations approved that EMSF outperforms MSF in terms of the average packet queue length in the network and the end-to-end latency. In a future work, we will improve EMSF by combining it with an enhanced cell selection mechanism in order to reduce energy consumption throughout the network.


extfieldsofstudy:
Computer Science
Mathematics

text:
swTVM: Towards Optimized Tensor Code Generation for Deep Learning on Sunway Many-Core Processor

The flourish of deep learning frameworks and hardware platforms has been demanding an efficient compiler that can shield the diversity in both software and hardware in order to provide application portability. Among the existing deep learning compilers, TVM is well known for its efficiency in code generation and optimization across diverse hardware devices. In the meanwhile, the Sunway many-core processor renders itself as a competitive candidate for its attractive computational power in both scientific computing and deep learning workloads. This paper combines the trends in these two directions. Specifically, we propose swTVM that extends the original TVM to support ahead-of-time compilation for architecture requiring cross-compilation such as Sunway. In addition, we leverage the architecture features during the compilation such as core group for massive parallelism, DMA for high bandwidth memory transfer and local device memory for data locality, in order to generate efficient codes for deep learning workloads on Sunway. The experiment results show that the codes generated by swTVM achieves 1.79x on average compared to the state-of-the-art deep learning framework on Sunway, across six representative benchmarks. This work is the first attempt from the compiler perspective to bridge the gap of deep learning and Sunway processor particularly with productivity and efficiency in mind. We believe this work will encourage more people to embrace the power of deep learning and Sunway many-core processor.

I. INTRODUCTION
Currently, deep learning has achieved outstanding performance in many fields, including self-driving car [1], face detection [2] and machine translation [3]. The deep learning frameworks such as TensorFlow [4], PyTorch [5], MxNet [6], and Caffe [7], provide an efficient platform to support the research and development on intelligent applications. In the meanwhile, emerging deep learning algorithms exhibit increasing demands for massive computation power. To satisfy the computation demand, various accelerating hardwares such as GPU, FPGA [8] and ASIC [9] have been applied in the deep learning field. Current deep learning frameworks almost rely on the high performance libraries such as cuDNN [10] † Contributed equally. * Corresponding author. and MKL [11], which are provided by the hardware vendors to accelerate the deep learning workloads. With new deep learning algorithms and hardwares arising rapidly, the engineering cost for porting the algorithms to the hardwares has increased dramatically. It is necessary to find a way to deploy these emerging deep learning algorithms on the underlying hardwares automatically and efficiently. To address the above problem, the end-to-end compilers [12]- [16] for deep learning workloads have been proposed. For example, TVM [15], XLA [4], Tiramisu [16] and Tensor Comprehension [14] are the state-of-the-art deep learning compilers. Taking TVM for example, it digests deep learning models implemented using different frameworks as input, and generates efficient model codes targeting various hardware devices as output. Fundamentally, TVM adopts the design of two level optimization to automatically generate codes for deep learning models. On graph level, it applies multiple optimizations to the computation graph derived from the deep learning model, such as operator fusion and data layout transformation. On operator level, it converts the computations into the tensor operations targeting the various hardwares and hides the memory latency by optimizing the instruction pipeline. Moreover, TVM can optimize the code generation automatically according to the shape and data layout of the input to each layer for better performance.
Meanwhile, for its compelling computation power, Sunway many-core processor serves as the basic building block of Sunway TaihuLight supercomputer, which is the first supercomputer to achieve over 100 petaFlops in the world. The Sunway SW26010 processor consists of four core groups (CG). Each CG, including a Management Processing Element (MPE) and 64 Computing Processing Elements (CPEs), can achieve 765 GFlops peak performance in double-precision. The memory attached to each CG is 8GB with the bandwidth of 34.1GB/s. The MPE is a complete 64-bit RISC core, typically used for task control and management, whereas the CPE is also a 64-bit RISC core but with limited functionalities, typically used for computation. In addition, each CPE has a 64KB local device memory (LDM), that is managed explicitly by software. The executables on Sunway are generated through cross-compilation with MPE and CPE as different compilation targets. Due to the limitation of Sunway customized operating system, the dynamic linked libraries are not supported.
To embrace the advantage of automatic compilation and high performance for deep learning workload, it is intuitive to adapt TVM to Sunway processor. However, the unique compilation environment and architecture features prevent a naive adoption of TVM to Sunway. Firstly, TVM relies on dynamic link libraries to generate executables on different hardware devices, which is not supported on Sunway. In addition, its code organization fails to recognize the different compilation targets for MPE and CPEs, and thus incapable of managing the function calls between MPE and CPEs. Secondly, the memory capacity of each CG on Sunway is quite limited. During the deep learning computation, large memory occupancy is required to store the intermediate data as well as the weight parameters. How to allocate the memory space efficiently and leverage the unique architecture features such as DMA for high bandwidth data transfer is important to generate code with high performance. Thirdly, each CPE within a CG contains a 64KB LDM that can be used to buffer data with explicit software management. How to leverage the limited LDM on each CPE with improved data locality is critical for realizing the performance advantage of Sunway processor during code generation.
To address the above challenges, we propose swTVM, a deep learning compiler tailored for the unique compilation environment and architecture features on Sunway processor. In swTVM, we provide ahead-of-time (AOT) code generation that manages the function calls as well as compilation for MPE and CPE explicitly. In addition, we apply several optimizations to the tensor operations so that the architecture features such as DMA and LDM are better utilized during code generation. To the best of our knowledge, this is the first work to implement an end-to-end deep learning compiler on Sunway processor. Specifically, this paper makes the following contributions: • We implement the ahead-of-time (AOT) code generation, that produces different compilation targets for MPE and CPE as well as manages the function calls between MPE and CPE efficiently. In addition, we manage the intermediate memory space for each tensor operation globally, which avoids the overhead of frequent memory allocation during computation. • We apply several optimizations to the tensor operations regarding the unique architecture features on Sunway. Specifically, we propose a DMA control interface that manipulates the DMA data transfers for each tensor during computation. In addition, we design a LDM management mechanism that buffers the tensor data as much as possible to reduce the latency for accessing memory. Moreover, the DMA instructions are automatically inserted during code generation to improve the accessibility of the buffered data. • We propose swTVM that implements AOT code generation and architecture specific optimizations on top of TVM, which offers the high performance of Sunway pro-cessor to the deep learning community through automatic compilation. The evaluation results show that swTVM achieves 1.79× speedup on average for representative models compared to the state-of-the-art deep learning framework. The rest of this paper is organized as follows. In Section II, we present the background of the deep learning compiler and Sunway processor. Section III presents the design overview of swTVM. Section IV and Section V describe the details of code generation in AOT mode and optimizations for tensor operations on Sunway. Section VI presents the evaluation results of swTVM compared to swCaffe. Section VII presents the related work, and section VIII concludes this paper.

A. Sunway Processor
Each Sunway SW26010 processor has four CGs, where each CG contains 1 MPE and 64 CPEs. The executables on Sunway are generated through cross-compilation on x86 processor using customized compiler. Due to the limitation of the customized operating system on Sunway, it does not support dynamic linked libraries. Instead, the executables are generated with libraries statically linked. Moreover, the codes running on MPE and CPEs are compiled as different compilation targets (using compilation flags of -host) andslave, respectively).
As for memory hierarchy, each CPE has 16KB L1 instruction cache and 64KB local device memory (LDM). The LDM is commonly used as a programmable buffer with explicit software control. There are two ways to access main memory on Sunway. The first one is to use DMA, which prefers large and continuous data access. The other one is to use global load/store (Gload/Gstore) instruction, which prefers small and random data access compared to the DMA.
Two parallel programming models are supported on Sunway to exploit the massive parallelism of the CPEs, including Ope-nACC and Athread. OpenACC is more programmer friendly, with which programmers can utilize CPEs without knowing about the underlying architecture details. While with Athread, programmers can buffer the data in LDM, which provides the opportunity to reduce the accesses to main memory through explicit control. In this paper, we generate Athread codes on Sunway for better performance.
Although the LDM of CPE sounds similar to the shared memory on GPU, their design philosophies are quite different. GPU adopts SIMT parallelism that accesses the shared memory through concurrent threads within a warp. The GPU program achieves better performance if threads within a warp access a continuous memory region at the same time. However, on Sunway the CPEs access the memory and buffer the data in LDM independently. Therefore, without careful management, severe contention on memory bandwidth would occur and thus degrade the performance significantly. In addition, when buffering large continuous data block to LDM, the DMA data transfer can be utilized for higher memory bandwidth.

B. Automated Compilation for Deep Learning
There are increasing demands of deploying emerging deep learning models to various hardware devices, so that enormous engineering efforts are required to match the algorithms with the hardware efficiently. Currently, the performance of the deep learning models mainly depends on the computation library, such as cuDNN and MKL provided by hardware vendors. However, it is unsustainable to perform labor intensive performance tuning to match various hardware as new algorithms are arising rapidly. The deep learning compiler provides a way to build an efficient mapping between new algorithms and various hardware targets, and thus improves the portability of the deep learning models.
Despite different implementation approaches adopted by different deep learning compilers, their design philosophies (e.g., two level optimization) are somehow converging [17]. Therefore, we take TVM for illustration. TVM uses the idea of two-level optimization, including graph level and operator level. On graph level, it converts the deep learning models to the computation graph, and then applies optimizations such as operator fusion and data layout transformation. On operator level, it optimizes the code generation targeting specific hardware through loop optimization (e.g., loop tiling and loop unrolling). However, adapting existing deep learning compiler to Sunway processors introduces several challenges to be addressed, due to the unique compilation environment and architecture features of Sunway.

C. Challenges for DL compilation on Sunway
The first challenge is that Sunway processor relies on crosscompilation to generate executables and does not support dynamic linked libraries. It prohibits naive adaption of existing deep learning compiler such as TVM to Sunway. Therefore, code generation in AOT mode needs to be supported in the deep learning compiler so that it can compile the executables with static linked libraries. In addition, an efficient code organization is required with AOT code generation in order to support different compilation targets as well as function calls for MPE and CPEs. Moreover, the memory capacity of a CG is quite limited compared to the large volume of data generated during the tensor operation. To avoid the overhead of frequent memory allocation during computation, the memory needs to be managed globally in AOT code generation.
The second challenge is to optimize the generated code regarding the unique architecture features of Sunway. Summarizing from existing researches [18]- [21] and the benchmarking [22], the key to achieving high performance on Sunway is to 1) fully utilize the computing resources of CPEs for massive parallelism, and 2) leverage the LDM of each CPE to alleviate the bottleneck of memory access. Therefore, when the deep learning compiler optimizes the generated codes, the three rules need to be followed: 1) use the DMA as much as possible when accessing main memory. The DMA requires accessing large and continuous data block, which provides higher memory bandwidth; 2) leverage the LDM to buffer as much data as possible during the computation.  The LDM reduces the latency to access main memory; 3) minimize the frequency of memory access as much as possible.
The computation should exhibit better data locality and reaccessibility after each memory access. In sum, implementing an end-to-end deep learning compiler requires both adaptions to the compilation environment on Sunway and optimizations targeting the architecture features to improve the performance of generated codes.

III. DESIGN OVERVIEW
To address the challenges described in Section II-C, we propose swTVM for the Sunway many-core processor. In swTVM, we implement the AOT code generation as an extension to TVM, and manage the code organization for MPE and CPEs respectively. In addition, we manipulate the memory allocation of the tensor operation globally. The grey components in Figure 1(a) show the contribution of our work. We produce C source codes in AOT mode, which are then compiled by Sunway native compiler in order to generate the executable. The advantage of AOT code generation is that the memory allocation for each layer is determined based on the input and output of each layer before the actual computation, which avoids frequent memory allocation during the computation and thus eliminates the overhead of operations related to memory allocation.
The MPE codes generated in AOT mode are primarily responsible for calling each layer according to the topology of the deep learning models, whereas the CPE codes are responsible for the specific computation of operators defined by the layers. The codes generated for a Sunway CG consist of three parts: layer module, memory allocation module and parameter initialization module. To generate the code, the   Figure 1(c). The layer module invokes the layer implementations from the layer library, and the memory allocation module allocates the memory space for each layer within the computation queue. The parameter initialization module is responsible for initializing the parameters of the layer implementations within the layer library.
To leverage the architecture features on Sunway, we optimize the implementation of each operator, as shown in the bottom part of Figure 1(c). Specifically, we design a DMA control interface, which provides the DMA schedule primitives for the layer library. In addition, since the LDM on each CPE is only 64KB which cannot store the entire tensors, we design a LDM management mechanism to control the amount of tensor data to be buffered in LDM automatically. It can also adjust the buffer size and reorder the computation loops according to the configuration of each layer. Moreover, to improve the locality of the buffered data, we design an algorithm to insert DMA instructions into the appropriate locations of the generated code automatically. The code generation module then generates code with Sunway syntax and provides the layer implementation into the layer library, which is utilized by the layer module to fulfill the layers in the computation queue.
Note that, although swTVM is targeting the Sunway manycore processor, the approaches are also valuable when building end-to-end deep learning compilers for other emerging processors with cache-less design.

IV. AOT CODE GENERATION
To implement AOT code generation, we should consider the implementation of each layer and the approach to convert the deep learning model topology into the function calls of layers with the dependencies satisfied. swTVM transforms the model topology into the actual implementation on Sunway processor, as shown in Figure 2. After code generation, the implementation contains a series of operations such as memory allocation, parameter initialization, and function calls in the main function (e.g., Func main).
Since the MPE are cores with complete functionality, the generated codes can run on MPE directly. Whereas for CPEs, we need to generate separate files for compiling, as shown in Figure 2. We use a struct to accept multiple parameters in the CPE function ( Figure 2). In order to remove the dependency on the struct definition from the interface when calling the layer, we encapsulate CPE functions with another interface that renders the layer function calls as ordinary function calls (Figure 2(d)). The encapsulating interface is also useful when handling the memory allocation of the intermediate data for complex layers. The encapsulated function is organized in a separate file (Figure 2(d)) with MPE as its compilation target. The parameters stored in the struct file is only visible to the files containing the CPE function and encapsulated CPE function. We achieve the AOT code generation for each layer by organizing the code of each layer into the above three files in addition to a header file (Figure 2(c)) for the encapsulated CPE function.

A. Managing Memory Allocation
The memory allocation on both main memory and LDM for input/output data as well as temporal data of each layer needs to be managed explicitly. The memory allocated for input/output data includes intermediate data generated between layers, and weight parameters that cannot be released or overwrote during computation. Once completing one layer, each operator stores its result into main memory and then used by other operators. Since this data is stored in the main memory, the memory space is allocated and freed by MPE, as shown in Figure 2(a) (line 3-7).
Complex operators usually generate temporal data. The data is never re-used and thus can be freed once the computation completes. Because the temporal data is usually larger than the capacity of LDM (i.e., 64KB), it is also stored in the main memory, whose allocation and deallocation are controlled in the main function. When an operator is invoked, it uses a portion of the memory space that has already been allocated in the main function, which reduces the overhead for allocation and deallocation for each operator. The memory space for temporal data is allocated by MPE and used by CPEs. The implementation details are listed in Func main for MPE and Func layer slave (e.g., in layers.s.c file) for CPEs in Figure 2. The LDM utilization in Func Layer slave is described in Section V.

B. Managing Function Call
As shown in Figure 1(a), the implementation of swTVM is organized into three levels, which first transforms the topology of a deep learning model into computation graph, and then applies a serial of optimizations at graph level, and eventually implements the computation on specific hardware at operator level. In AOT code generation, the Func main in Figure 2 In addition, function calls for architecture specific codes can also be organized into three levels, including function call on MPE, function call on CPEs and function call from MPE to CPEs. These three levels correspond to the operators at graph level, operator level, and from graph level to operator level in swTVM. The graph level generates Func Main, which runs on MPE. And the Func layer is the implementation of the function call from graph level to operator level, which is invoked by Func main on MPE and then invokes the Func layer slave on CPEs. Func layer slave implements the computation performed at operator level.
With such design, swTVM can organize the AOT code generation and Sunway architecture optimizations through layered function calls, rather than relying on sophisticated lowlevel implementation details. In addition, through managing the dependencies of function calls, swTVM is able to generate codes for MPE and CPEs as different compilation targets.

C. Implementation Details
The Func main shown in Figure 2(a) consists of four stages, including memory allocation stage, parameter/input initialization stage, computation stage and output stage. During memory allocation stage, in addition to memory for the parameter and input/output of the deep learning model, temporal memory is also allocated for each layer, the size of which satisfies the maximum memory usage of each layer. The dependency across all layers is analyzed to decide the order of function calls. Each function in the computation stage corresponds to one or more layers in the model topology.
The implementation of each operator consists of Func layer on MPE, Func layer slave on CPEs and parameter structure Para. Func layer is further divided into three parts, such as the memory allocation for temporal space, parameter initialization, and computation. The memory allocation for temporal space is only required for the layer that combines multiple suboperators such as convolution and pooling. For such layers, the input of one sub-operator depends on the intermediate results from the previous sub-operator. Considering the overhead of frequent memory allocation, we allocate temporal memory space in the main function and share it across operators.
The format for calling the function on CPEs is to use the function name and parameter struct, as shown in Figure 2(c) (line 10). Para is the parameter struct that is only visible to corresponding layer.c and layer.slave.c files. Func layer slave consists of parameter parsing, LDM allocation, and computation. At the beginning of the function, the tensors are loaded from memory and then buffered in LDM. The LDM space is allocated through static arrays to buffer the tensor. The main memory is accessed through DMA instructions, which can be overlapped with the computation for efficiency, and the details are described in Section V.

D. Invoking Optimized Kernel Libraries
Since there are several optimized libraries available on Sunway processor for accelerating matrix multiplication and convolution computation, such as xMath, swGEMM and swDNN [23]. swTVM provides optional approach to easily integrate these libraries for better code generation, which is implemented in the following two stages. In schedule mapping stage, swTVM uses the intrinsic APIs to generate function calls to external libraries, and bypasses them to the code generation stage. Considering performance variation of different libraries across different tensor operations, swTVM invokes the libraries with optimal performance. For example, it invokes xMath and swGEMM for accelerating standard convolution and depthwise convolution operators respectively. In code generation stage, swTVM identifies the invoked libraries and automatically adds the relevant header files and parameters to generate the canonical C codes. Besides, it adds the corresponding flags to the compilation configurations (e.g., Makefile).

A. DMA Control Interface
An efficient DMA control interface plays an important role in swTVM to generate high-performance implementations of deep learning models on Sunway. In swTVM, the DMA control interface provides schedule primitives to control DMA in order to manage the data access efficiently. Figure 3 shows an example to control the tensor data access in matrix multiplication through the DMA control interface. Figure 3(a) shows the computation definition in swTVM, and Figure 3(b) shows the plain IR generated by swTVM, which is the same as original TVM. The split primitive splits the loop iterator into two parts (line 8-9 of Figure 3(a)). We call the outer part as parallel iterator and inner part as buffer iterator. And swTVM uses the parallel iterators to assign computation to CPEs for parallelization and buffer iterators for DMA data transfer.
swTVM can also buffer data along multiple dimensions. In Figure 3(c), tensor B is buffered along two dimensions (line 1). This allows fast access to the value along these two dimensions of tensor B when calculating the sub-region of tensor C. Additionally, swTVM can specify which tensor to be buffered and the region of the tensor to be buffered during code generation. To buffer partial of the tensor along one dimension, split, buffer read, and buffer write primitives are applied in sequence to split the dimension and buffer the corresponding data. After invoking the above primitives, Load Data region (line 6-11 in Figure 3(d)) generates the IR code of the read buffer for tensor B and A, whereas Store Data region (line 15-16 in Figure 3(d)) generates the IR code of write buffer for tensor C. The generated IR is then translated to DMA instructions during code generation.
Buffering data along multiple dimensions also occurs in convolution operator. The convolution operation is the computation among high-dimension tensors, where certain dimensions of the tensor may be quite small If only buffering data along only one dimension, the LDM space is not fully utilized. In such a case, buffering the tensor data along multiple dimensions improve the LDM utilization. When buffering, we satisfy the data access of the outer loop with high priority, which improves the locality of buffered data.

Load Data
Store Data C = A * B In complex layer such as convolution, the subscript to access the tensor data along one dimension is determined by multiple loop iterators. To handle such case, the DMA control interface accepts multiple loop iterators and allows the user to specify the expression on calculating the subscript based on these loop iterators, which determines the range of each dimension to be buffered. One such example is shown in the expression yy × stride + ry. The DMA control interface also supports expression inferring, which accepts the subscript expression and analyzes the correlation between the loop iterators and tensor dimensions automatically.

B. LDM Management Mechanism
To better control the data buffering in LDM, we design the LDM management mechanism, which determines the buffer size and the dimensions of tensor to be buffered. In addition, it reorders the computation loops to improve the locality of the buffered data.
1) Determining the Buffer Size: Due to the limited LDM space, the difficulty to determine the buffer size of each tensor is to identify the dependencies, which means the buffer size of one tensor can affect the buffer size of another. Figure 4 shows an example of buffer size dependency within the matrix multiplication (A × B = C). The dimensions of matrix A, B and C are (x,k), (k,y), and (x,y), respectively. When the buffer size of matrix C and matrix A is l 2 and l 1 respectively along the same dimension, the buffer size of matrix B is l 1 and l 2 along k and y dimension. Figure 5 shows the procedure of calculating the buffer size on the matrix multiplication and the possible size of each buffer. When determining the buffer dimension of each tensor using buffer read and buffer write in Figure 5(a), swTVM constructs a table that describes the buffer iterators of each tensor as shown in Figure 5(b). The sum of the buffer size from all buffer iterators of each tensor can be expressed in an equation, as shown in Figure 5(c). Then the buffer size of each tensor can be determined by choosing a possible value that satisfies the above equation. We limit the possible values to the power of two for better performance on Sunway, as shown in Figure 5(d). We use a greedy algorithm to search for the minimum possible value.
Constraint 1 -When determining the buffer size of each tensor, the following constraints should be satisfied.
• The buffer size of a buffer iterator cannot be larger than the original dimension. • The sum of the buffer size of all tensors cannot be larger than the LDM size. • When the buffer size in the lowest dimension is one, no buffer is allocated for the tensor, which means that the data is directly accessed from main memory. Strategy 1 -swTVM uses an approximate algorithm (Algorithm 1 in Appendix) to managing data buffer in LDM, which ensures an acceptable search time for an optimal solution. The algorithm consists of two parts, the initial part to allocate a predefined LDM memory space and expanding part to maximize the LDM utilization. In Algorithm 1, the iterators can be classified into three types: • sizeiter: determines the buffer size and is the index of the lowest dimension of the tensor that can be expanded; • numiter: determines the number of DMA instructions and is the index of the dimension (except the lowest dimension) of the tensor; • compiter: is the iterator that satisfies the conditions of both sizeiter and numiter. At the beginning of the algorithm, the sequence of the iterators is reordered. For compiters, it is reordered by the ascending order of the affected number of tensors. Whereas for sizeiters, it is reordered by the ascending order of the buffer size (line 9-10). After that, the buffer iterator for each loop iterator is initialized to a pre-defined size across each tensor (line 12-37). The buffer size is set to the minimum between the loop range and InitValue. The number InitValue is chosen based on empirical study that reading InitValue floats per memory access achieves good bandwidth, and InitValue is set to 64 on Sunway (line [17][18][19][20][21]. Then, the algorithm checks if the buffer size is larger than the size of LDM. If so, the amount of data to be transferred for current buffer iterators or even the previous buffered iterators needs to be reduced to fit in the limited size of LDM (line [22][23][24][25][26][27][28][29][30][31]. During the initialization, the algorithm invokes the UPDATE function if the range of the buffer iterator equals to the range of the loop iterator. When the dimension of the tensor to be buffered is no longer associated with any iterators, the higher dimension needs be adjusted to change the buffer size. And the CLASSIFY function is invoked to update numiters, sizeiters and compiters (line 23-25, 33-36, 46-52). After the initialization, if the LDM still has free space, the buffer size of each iterator is expanded to improve the LDM utilization. We use a greedy algorithm to load as much data into LDM as possible. The algorithm terminates when the LDM usage reaches the maximum size (line 39-53).
We take the matrix multiplication in Figure 3 to illustrate the process of the algorithm, where x, y and k is numiter, sizeiter, and compiter respectively. We set the buffer size of y to 64 and ensure our buffer size not exceeding the LDM capacity. Then, we set k to 64 that leads to the LDM usage of 16.5KB. Since there is no numiter satisfying the condition of UPDATE, the algorithm enters the expanding part. When y is set to 128, the LDM usage increases to 32.75KB. Continuing to expand k to 128, the buffer size reaches 65KB, which is larger than the LDM capacity (64KB). Therefore, x = 1, y = 128, and k = 64 are chosen as the buffer sizes.
2) Loop Reordering: After initializing the buffer size for each tensor, the loop order is adjusted to improve the locality of the buffered data.
Constraint 2 -To ensure the correctness after loop reordering, the following constraints need to be satisfied.
• The buffer iterator cannot be ahead of the parallel iterator, both of which are split from the same iterator; • The parallel iterator of the output tensor must be at the outermost loop to prevent write conflict; • The buffer cannot be ahead of other iterator associated with the same tensor; • The child iterator split from the parent iterator inherits its parent's order. as the loop iterators for current loop (line 2-11). The above process is repeated until all iterators are evaluated, which derives the final loop order (line [16][17][18][19][20][21][22]. The time complexity of Algorithm 2 is also within polynomial time.
We take the matrix multiplication in Figure 3 to illustrate the loop reordering. The iterators for which the order to be decided is x, yo and ko. The least number of DMA instructions for x, yo and ko is 256 + 128, 256 + 16 and 256 + 8 respectively. Therefore, ko is chosen first. And then, the least number of DMA instructions for x and yo are both 8. Therefore, the original loop order is unchanged. After that, the final loop order for x, yo and ko is determined.

C. DMA Auto-Insertion Algorithm
With the DMA control interface and LDM management mechanism available, we propose an algorithm to implement the auto-insertion of DMA instructions during the code generation. The DMA auto-insertion algorithm consists of three parts as following.
Determining the buffer size and the starting memory location. First, the buffer dimension is split into two parts, which makes the range of the inner loop within the buffer size. When the subscript of the dimension is correlated with only one loop iterator, the starting memory location of the buffer is calculated by setting the loop iterator of the inner loop to 0, whereas the buffer size is the range of the inner loop. All the buffer operations in Figure 3(c) belong to the above case. However, for complex operators such as stride convolution, the subscript of one dimension of the tensor is always correlated with several loop iterators. To obtain the starting memory location of the buffer, all loop iterators are set to zero and calculated in the subscript expression. The size of the buffer is the difference between the result of the subscript expression with all iterators set to their maximum value and the starting memory location.
Determining the locations of DMA instruction insertion. Figure 6 illustrates the process of determining the DMA insertion location for a tensor. At the beginning, we have the iterators which are associated with the tensor. Figure 6(a) shows the initial states of the iterators. The tensor has loop iterators such as v, j and i, and buffer iterators such as k and w. Then we iterate through the outer loops to inner loops. If the iterator of the current loop is not within the associated iterator set of the tensor, then the algorithm proceeds to the next loop. If the current iterator belongs to the set but does not belong to the buffer iterators, then the iterator is removed from the associated iterator set, which indicates the iterator is determined. In Figure 6(b), the iterator i is removed from the associated iterator set since it satisfies the above condition. When all iterators except the buffer iterators are removed from the associated iterator set, as shown in Figure 6(c), the locations to insert DMA instructions are determined. The above procedure is repeated for all tensors to determine the locations of DMA instruction insertion correspondingly.
Generating code with Sunway DMA syntax. Figure 3(e) shows the pseudo-code of the inserted DMA instructions. When generating the code, the DMA instructions whose memory address and LDM buffer address are continuous, are combined to reduce the number of DMA instructions.

D. Parallelism
To achieve better parallel efficiency with CPEs, the load balance and write conflict need to be considered when generating codes. The load balance can be achieved by using the athread parallel primitive, which splits computation task into sub-tasks along the highest dimension of the tensor. Take the vector multiplication (v = v1 × v2) with parallel implementation as an example. For the vector v with dimension size of 1,024, we divide its dimensions into CoreNum chunks. As CoreNum on Sunway is 64, the size of each chunk is 16. The begin and end indicates the range of sub-tasks for each CPE, which is determined by the id of CPE and the number of the tasks. The less optimal case happens when the size along the high dimension of the tensor is less than the number of CPEs. Such a case can be solved by using the fuse primitive to combine multiple dimensions until the size is large enough. And the write conflict can be avoided by splitting the tasks along the dimension of the tensor to be written.

A. Experiment Setup
In this section, we evaluate the performance of the codes generated by swTVM on a CG of Sunway processor. We compare swTVM with swCaffe [24], which is the deep learning framework customized for Sunway. We present the endto-end performance and the operator-level performance to demonstrate the efficiency of swTVM, and we provide the roofline model analysis to better understand the generated codes. Besides, we show the compilation overhead of swTVM.
For benchmarks, we select eight representative deep learning models that are the widely-used in inference tasks, as shown in Table I. Notably, swCaffe fails to execute ShuffleNet and Bert-base due to unsupported layers (e.g., permute, layernorm, and embedding). While swTVM supports them and generates high-performance codes for them, demonstrating its portability. Each model under each batch size is executed for 100 times and the average execution time is reported.
swTVM performs the compilation on the x86 platform. The compilation environment includes gcc/g++ 4.8.5 and Python 3.6.2. The codes generated by swTVM is a group of C/C++ files, which are then compiled by Sunway native compilers (sw5cc for C and sw5CC for C++) with -O3. swCaffe is configured with the recommended high-performance libraries, including swDNN and xMath. And all optimization macros (e.g., offloading im2col, relu, pooling, batchnorm operators to swDNN) are enabled.

B. End-to-End Performance
The end-to-end performance of swTVM across all benchmarks is shown in Figure 7. Notably, swTVM is configured with two configurations of graph-level optimizations: OPT=1 enables the basic operator fusion, and OPT=4 enables all built-in optimization passes of TVM. swTVM under both configurations outperforms swCaffe in nearly all benchmarks. Specifically, the average speedups of swTVM (OPT=1) compared the swCaffe baseline under the four batch sizes (i.e., 1, 2, 4, 8) are 1.71×, 1.61×, 1.56×, and 1.55×, respectively. And the average speedups of swTVM (OPT=4) are 1.79×, 1.66×, 1.62×, and 1.61×. This is because swTVM exploits the graph-level optimizations standing on the basis of TVM, while swCaffe ignores them. For example, the operator fusion can reduce the number of kernel launches on CPEs, eliminate the corresponding DMA transfer between LDM and main memory, and allow better sharing of the computation. With more graph-level optimizations enabled, the performance of swTVM (OPT=4) is better than that of swTVM (OPT=1).
The acceleration from memory-intensive operators (e.g., batch norm) dominates the performance improvement of swTVM. Among the benchmarks, YOLOv3 has the largest batch norm operators (with the largest input size), and thus it has higher speedup ration. With the increasing batch sizes, the speedup of swTVM decreases slightly, because of the inefficient batch norm implementation of swCaffe baseline. swCaffe implements batch norm through matrix multiplication which shows non-trivial overhead, therefore, the computation time remains nearly constant even doubling the batch size. Notably, as for MobileNet, the depthwise conv2d operators dominate over 95% of the computation time and are also highly-optimized by swTVM. Consequently, on MobileNet, swTVM achieves the maximum speedup of 2.79×, which is quite stable even with different batch sizes.

C. Operator-Level Performance
In order to evaluate the effectiveness of swTVM, we further perform operator-level performance comparison. We   Fig. 7: End-to-end performance of swTVM with two configuration of graph-level optimization, OPT=1 and OPT=4. The y-axis represents the speedup compared to swCaffe.
classify the operator into three categories, including convolution, dense, and memory-intensive operators. The experiment results is shown in Figure 8. Since YOLOv3 and DCGAN has no dense operator, the corresponding bars are left blank. On the three categories, swTVM achieves 1.36×, 1.29×, and 11.36× speedups on average compared to swCaffe, respectively. Among them, swTVM achieves the maximum speedup on memory-intensive operators, which mainly contain batch norm, relu, pooling, bias add operators. These operators benefit a lot from the operator fusion, which fuses multiple small operators together to avoid redundant DMA transfers between LDM and main memory. The batch norm operator in swCaffe is implemented as a batchnorm layer (applying the mean and the variance) and a scale layer (scaling and then shifting, i.e., ax + b). swTVM fuses mean/variance applying and scaling to the preceding convolution operator and also fuse the shifting to the next relu operator, leading to superior performance. As for convolution and dense operators, both swTVM and swCaffe can leverage the optimized kernel libraries such as swDNN, xMath, etc., so their performance could be similar. If these operators are configured with bias (e.g., all dense operators, convolution operators of VGG16), swTVM regards the bias computation as memory-intensive operators while swCaffe regards them as part of convolution/dense operators. As a result, the speedup of swTVM on these operators are slightly better, and the speedup on memory-intensive operators may decrease slightly.
Besides, the convolution operators from MobileNet optimized by swTVM show 2.74× speedup on average. These operators are depthwise convolutions, and each is transformed into im2col and tall-skinny matrix multiplication with parameters M, N, K, where M is 1, N represents the feature map size, K is the kernel size. In this scenario, swTVM invokes the optimal swGEMM library rather than xMath and achieves superior performance to swCaffe. Although the memoryintensive operators from DCGAN has 6.82× speedup, the overall speedup of DCGAN is still negligible, as shown in Figure 7. It is because the memory-intensive operators is not the performance bottleneck, which contribute to less than 2% of the end-to-end inference time. Similarly, the memoryintensive operators from VGG16 contribute to less than 5%.

D. Roofline Analysis
We further perform the roofline analysis to study the effectiveness of the codes generated by swTVM. Figure 9 presents the experiment results of the overall model inference across  all benchmarks, as well as the results of the convolution and dense operators. Only the lightweight models, MobileNet and ShuffleNet, lie on the left of the ridge point. They have low operational intensity since they are designed for lowpower edge devices. Most benchmarks lie on the right of the ridge point due to the high operational intensity and achieve better performance, because swTVM generates efficient codes for the convolution, dense, and memory-intensive operators. Specifically, the convolution operators optimized by swTVM reach 419.83 GFlops, more than half of the peak performance of a CG.

E. Compilation Overhead
The compilation overhead of swTVM can be attributed to two parts. The first part (codegen) is the AOT generation of optimized C/C++ codes and corresponding makefile, whereas the second part (make) is the compilation through the native C/C++ compiler of Sunway. Figure 10 presents the breakdown of the compilation overhead of swTVM and the compilation overhead of TVM on x86 CPU. It is obvious that their total compilation overhead are comparable. The codegen time of swTVM is much lower than TVM, whereas the make time is determined by the native compilers on Sunway.

A. Deep Learning Compiler
Currently, the deep learning community develops rapidly. There are always emerging deep learning models and hardware devices. However, the engineering efforts of porting various models to numerous hardware devices increase dramatically. Under this background, the end-to-end deep learning compilers are proposed. XLA [4] from Google focuses on the high-level computation graph, and it can fuse those subgraphs together to generate efficient code. DLVM [25] is similar to TensorFlow XLA, which focuses on the high-level, but it promotes using linear algebra instead of the computation graph to express the higher-level of the models. As they pay less attention to the hardware level, significant engineering effort is needed for each hardware and operation combination. TVM [15] proposes the end-to-end compiler for neural networks and now supports various hardware. Recent works such as Glow [12], Tensor Comprehensions [14] and nGraph [13] can all be classified into this category. Glow lays emphasis on its two-phase stronglytyped intermediate representation and nGraph pays more attention to how to simplify the connection between deep learning frameworks and hardware. Tensor Comprehensions provides a language similar to math to describe the neural network and supports optimizing the computational kernel according to the parameter of neural networks in JIT mechanism. There are also a few emerging tensor compilers optimizing the bottleneck operators [26]- [29]. However, they all lack the support of Sunway many-core processors.

B. Performance Optimization on Sunway
As a supercomputer consisting of massive Sunway manycores processors, Sunway TaihuLight achieved the peak performance of 125PFlops and ranked the first place in Top500 from 2016 to 2018. There are a lot of optimization works targeting the architecture features on Sunway, which are valuable for our work to generate high performance code.
For applications, molecular dynamics [30], earthquake simulation [31], and atmospheric dynamics [32] won the Gordon Bell Prize of ACM. For algorithms, there are plenty of algorithms optimized on Sunway such as BFS [18], SpMV [19], SpTRSV [20], [21], and Cholesky factorization [33]. BFS is an essential algorithm in calculating the shortest route and the maximum flow problem, and the optimization on Sunway achieves 23,755 giga-traversed edges per second. Sparse computation such as SpMV is one of the important computational kernels in scientific applications. The implementation of SpMV on Sunway achieves 15.5× speedup on average over 18 representative datasets. There are also two related works regarding the deep learning on Sunway. swDNN [23] is a neural network library customized for Sunway with tremendous engineering efforts. swCaffe [24] proposes a deep learning framework for distributed training on Sunway.
To the best of our knowledge, there is no existing work on the end-to-end deep learning compiler that exploits the architecture advantage of Sunway processor.

VIII. CONCLUSION
We propose a deep learning compiler, swTVM, for Sunway processor. swTVM adopts AOT code generation to address the unique compilation environment on Sunway, and leverages several architecture features during code generation so that the computing capability of Sunway can be better utilized. Specifically, a DMA control interface is proposed to manipulate the data access of the tensor better. A LDM management mechanism is designed to buffer data in LDM in order to reduce the memory access latency. Moreover, a DMA autoinsertion algorithm is proposed to identify the locations for inserting DMA instructions automatically with improved data re-use. In brief, swTVM bridges the gap of deep learning and Sunway processor with improved productivity and efficiency.