The Deep Learning Compiler: A Comprehensive Survey <s> 4.5.1 <s> We describe LLVM (low level virtual machine), a compiler framework designed to support transparent, lifelong program analysis and transformation for arbitrary programs, by providing high-level information to compiler transformations at compile-time, link-time, run-time, and in idle time between runs. LLVM defines a common, low-level code representation in static single assignment (SSA) form, with several novel features: a simple, language-independent type-system that exposes the primitives commonly used to implement high-level language features; an instruction for typed address arithmetic; and a simple mechanism that can be used to implement the exception handling features of high-level languages (and setjmp/longjmp in C) uniformly and efficiently. The LLVM compiler framework and code representation together provide a combination of key capabilities that are important for practical, lifelong analysis and transformation of programs. To our knowledge, no existing compilation approach provides all these capabilities. We describe the design of the LLVM representation and compiler framework, and evaluate the design in three ways: (a) the size and effectiveness of the representation, including the type information it provides; (b) compiler performance for several interprocedural problems; and (c) illustrative examples of the benefits LLVM provides for several challenging compiler problems. <s> BIB001 </s> The Deep Learning Compiler: A Comprehensive Survey <s> 4.5.1 <s> This paper presents the design of Glow, a machine learning compiler for heterogeneous hardware. It is a pragmatic approach to compilation that enables the generation of highly optimized code for multiple targets. Glow lowers the traditional neural network dataflow graph into a two-phase strongly-typed intermediate representation. The high-level intermediate representation allows the optimizer to perform domain-specific optimizations. The lower-level instruction-based address-only intermediate representation allows the compiler to perform memory-related optimizations, such as instruction scheduling, static memory allocation and copy elimination. At the lowest level, the optimizer performs machine-specific code generation to take advantage of specialized hardware features. Glow features a lowering phase which enables the compiler to support a high number of input operators as well as a large number of hardware targets by eliminating the need to implement all operators on all targets. The lowering phase is designed to reduce the input space and allow new hardware backends to focus on a small number of linear algebra primitives. <s> BIB002 </s> The Deep Learning Compiler: A Comprehensive Survey <s> 4.5.1 <s> Deep learning models with convolutional and recurrent networks are now ubiquitous and analyze massive amounts of audio, image, video, text and graph data, with applications in automatic translation, speech-to-text, scene understanding, ranking user preferences, ad placement, etc. Competing frameworks for building these networks such as TensorFlow, Chainer, CNTK, Torch/PyTorch, Caffe1/2, MXNet and Theano, explore different tradeoffs between usability and expressiveness, research or production orientation and supported hardware. They operate on a DAG of computational operators, wrapping high-performance libraries such as CUDNN (for NVIDIA GPUs) or NNPACK (for various CPUs), and automate memory allocation, synchronization, distribution. Custom operators are needed where the computation does not fit existing high-performance library calls, usually at a high engineering cost. This is frequently required when new operators are invented by researchers: such operators suffer a severe performance penalty, which limits the pace of innovation. Furthermore, even if there is an existing runtime call these frameworks can use, it often doesn't offer optimal performance for a user's particular network architecture and dataset, missing optimizations between operators as well as optimizations that can be done knowing the size and shape of data. Our contributions include (1) a language close to the mathematics of deep learning called Tensor Comprehensions offering both imperative and declarative styles, (2) a polyhedral Just-In-Time compiler to convert a mathematical description of a deep learning DAG into a CUDA kernel with delegated memory management and synchronization, also providing optimizations such as operator fusion and specialization for specific sizes, (3) a compilation cache populated by an autotuner. [Abstract cutoff] <s> BIB003
Hardware-specific Optimization. In the backend of DL compilers, hardware-specific optimizations, also known as target-dependent optimizations, are applied to obtain high-performance codes targeting specific hardware architecture. One way to apply the backend optimizations is to transform the low-level IR into LLVM IR in order to utilize the LLVM infrastructure to generate optimized CPU/GPU codes. The other way is to design customized optimizations with DL domain knowledge, which can leverage the target hardware more efficiently. Since hardware-specific optimizations are tailored for particular hardware architectures or implementations, we present five widely adopted approaches in existing DL compilers, including hardware intrinsic mapping, memory allocation and fetching, memory latency hiding, parallelization, and loop oriented optimization techniques. Hardware Intrinsic Mapping -Hardware intrinsic mapping can transform a certain set of low-level IR instructions to kernels that have already been highly optimized on the hardware. In TVM, the hardware intrinsic mapping is realized in the method of extensible tensorization, which can declare the behavior of hardware intrinsic and the lowering rule for intrinsic mapping. This method enables the compiler backend apply hardware implementation as well as highly optimized handcraft micro-kernels to a certain pattern of operations, which results in a significant performance gain. Whereas, Glow supports hardware intrinsic mapping such as quantization, which is commonly used to minimize the memory footprint and improve inference speed. Glow can estimate the possible numeric range for each stage of the neural network and supports profile-guided optimization to perform quantization automatically. Besides, Halide, which is widely used as the low-level IR in DL compilers such as TVM, maps specific IR patterns to SIMD opcodes on each architecture (e.g., SSE/AVX on x86 and NEON on ARM). This approach can avoid the inefficiency of LLVM IR mapping when encountering vector patterns. Memory allocation and Fetching -Memory allocation is another challenge in code generation at the backend, especially for GPUs and customized accelerators. For example, GPU contains primarily two memory spaces, shared memory space and local memory space, where shared memory has lower access latency with limited memory size, and local memory has higher access latency with large capacity. Such memory hierarchy requires efficient memory allocation and fetching techniques for improving data locality. To realize the optimization of memory allocation and fetching, TVM introduces the scheduling concept of memory scope. Memory scope schedule primitives can tag a compute stage as shared or thread-local. For compute stages tagged as shared, TVM generates code with shared memory allocation as well as cooperative data fetching, which inserts memory barrier at the proper code position to guarantee correctness. Besides, TC also provides similar features of shared and local (a.k.a. private) memory by extending PPCG  compiler. Different from TVM, the memory allocation and fetching is more constrained in TC (known as memory promotion), which only supports optimized memory allocation and fetching under predefined rules. In addition to GPUs, other DL accelerators also require efficient memory allocation and fetching in code generation for better performance. Particularly, TVM enable special buffering in accelerators through its memory scopes schedule primitives. Memory Latency Hiding -Memory latency hiding is also an important technique used in the backend by reordering the pipeline execution as much as possible. As most DL compilers support parallelization on CPU and GPU, memory latency hiding can be naturally achieved by hardware optimizations (e.g., warp context switching on GPU). But for TPU-like accelerators which implemented with decoupled access-execute (DAE) architecture, the backend needs to perform scheduling and fine-grained synchronization to obtain correct and efficient codes. To achieve better performance as well as reduce programming burden, TVM introduces virtual threading schedule primitive, which enables users to specify the data parallelism on virtualized multi-thread architecture. Then TVM lowers these virtually parallelized threads by inserting necessary memory barriers and interleaves the operations from these threads into a single instruction stream, which forms better execution pipeline of each thread to hide the memory access latency as much as possible. Loop Oriented Optimizations -Loop oriented optimizations are also applied in the backend to generate efficient codes for target hardware. Since Halide and LLVM (based on the polyhedral method) BIB001 have already incorporated such optimization techniques, some DL compilers leverage Halide and LLVM in their backends. The key techniques applied in loop oriented optimizations include: loop fusion, sliding windows, tiling, loop reordering, and loop unrolling. • Loop fusion: Loop fusion is a loop optimization technique that can fuse loops with the same boundaries together for better data reuse. For compilers like PlaidML, TVM, TC, and XLA, this optimization is performed by Halide schedule or polyhedral approach, while Glow does loop fusion by its operator stacking. • Sliding windows: Sliding windows is a loop optimization technique adopted by Halide. The central concept of sliding windows is to compute values when needed and store them until they are no longer required. When an output value of a nested loop is computed by values calculated by the previous compute stage (loops), the sliding window can cache the needed values on the fly for data reuse. As sliding windows will interleave the computation of two stages and make it serial, it is a tradeoff of parallelism and data reuse. • Tiling: Tiling is another loop optimization technique commonly used in high-performance computing. Tiling means that loops are split into several tiles, thus loops are separated into outer loops of iterating through tiles and inner loops of iterating inside a tile. This transformation is aimed to enable better data reuse inside a tile by fitting a tile into hardware caches, which are crucial in modern processors' memory hierarchy. As the size of a tile is quite hardware-specific, it is difficult to provide a rule to define the pattern and size for tiling. Thus, many DL compilers support deciding the pattern and size of tiling automatically by auto-tuning . • Loop reordering: Loop reordering (also known as loop permutation) means changing the order of iterations in a nested loop, which can optimize the memory access and thus increase the spatial locality. It is specific to data layout and hardware features, and Halide provides a schedule primitive called reorder, which can be used to optimize loop order through autotuning. However, it is not safe to perform loop reordering when there are dependencies along the iteration order. • Loop unrolling: Loop unrolling is also a commonly adopted optimization technique in compilers. Loop unrolling will unroll a specific loop to a fixed number of copies of loop bodies, which can benefit from less cost of loop controls (or fewer instruction numbers generated for this loop). Compilers reusing Halide's works support for schedule primitives for loop unrolling, but its loop unrolling is completely loop unrolling, which means it will replace the loop of size n by n copies of the loop body. The generalized loop unrolling is expressed by the combination of loop split and loop unrolling, which first split the loop into two nested loops and then unroll the inner loop completely. Parallelization -As modern processors generally support multi-threading and SIMD parallelism, it is important for the compiler backend to exploit parallelism in order to maximize hardware utilization for high performance. Halide and polyhedral models are the two major techniques adopted in existing DL compilers to exploit hardware parallelization and SIMD vectorization. • Halide: For thread-level parallelization, Halide uses a schedule primitive called parallel to specify the parallelized dimension of the loop, which can be tuned through auto-tuning. Halide also supports GPU parallelization by mapping loop dimensions tagged as parallel with annotation of block and thread. For vectorization, Halide replaces a loop of size n with a n-wide vector statement, which can be mapped to hardware-specific SIMD opcodes through hardware intrinsic mapping. • Polyhedral model: In a polyhedral model, one can perform transformations on polyhedron and thus obtain transformed loop mapping for better parallelization. As the polyhedral model is actually a loop transformation to detect potential parallelism, it can be applied to parallelize with CPU threads as well as GPU kernels. Furthermore, Stripe developed a variant of the polyhedral model called nested polyhedral model, which introduces parallel polyhedral block as its basic execution element of iteration. After this extension, a nested polyhedral model can detect hierarchy parallelization among levels of tiling and striding, and regardless of complicated control flow inside a parallel polyhedral block. In addition to the above two techniques, some DL compilers rely on handcraft libraries such as Glow BIB002 or optimized math libraries provided by hardware vendors (detailed discussion in Section 4.5.3), which can achieve much higher performance on the target hardware. In the meanwhile, Glow offloads the vectorization to LLVM compiler because the LLVM auto-vectorizer works well when provided the knowledge of tensor dimension and loop trip count. Compared to the approaches relying on optimized libraries and LLVM infrastructure, exploiting the parallelism entirely by compiler backend allows to apply more domain-specific knowledge of DL models, and thus achieves higher performance on diverse hardware targets, however at the expense of more engineering efforts. 4.5.2 Auto-tuning. Due to enormous search space for parameter tuning in hardware-specific optimizations, it is necessary to leverage auto-tuning to determine the optimal parameter settings. Halide/TVM allows the programmers to define the hardware-specific optimizations (scheduling) first, and then it uses auto-tuning to derive the optimal parameter settings. In this way, Halide/TVM programmers can update or re-design the scheduling by inspecting the performance of specific parameter settings repeatedly. In addition, auto-tuning can also be applied to polyhedral model for parameter tuning BIB003 . For example, TC utilizes the auto-tuning to explore the configurations (including polyhedral scheduling and the parameters) and update the compilation cache in order to minimize the overhead of polyhedral JIT compilation. Generally, the implementation of autotuning includes three parts: parameterization, cost model, searching technique and performance optimization. Parameterization -1) Data and target: The data parameter describes the specification of the data, such as input shapes. The target parameter describes hardware-specific characteristics and constrains to be considered during optimization scheduling and code generation. For example, for the GPU target, the hardware parameters such as shared memory and register size need to be specified. 2) Optimization options: The optimization options include the optimization scheduling and corresponding parameters, such as loop oriented optimizations and tile size. In TVM, both predefined and user-defined scheduling, as well as parameters, are taken into consideration. Whereas in TC, it prefers to parameterize the optimizations, which have a strong correlation with performance and can be changed later at low cost. For example, minibatch dimension is one of the parameters, which is usually mapped to grid dimensions in CUDA and can be optimized during auto-tuning. Cost model -The comparison of different cost models applied in auto-tuning are shown in Table 4 . 1) Black-box model: This model only considers the final execution time rather than the characteristics of the compilation task. It is easy to build a black-box module, but leads to higher overhead and less optimal solution without the guidance of task characteristics. 2) Pre-defined cost model: Ideally, an approach based on a pre-defined cost model expects a perfect model that is built on the characteristics of the compilation task and is able to evaluate the overall performance of the task. There are many factors affecting the accuracy of the model, such as memory access patterns and pipeline dependencies, which are correlated with the task and the hardware target. Compared to the ML-based model, the pre-defined model generates less computation overhead when applied, but requires large engineering efforts for re-building the model on each new DL model and hardware. 3) ML-based cost model: ML-based cost model is a statistical approach to predict performance using a machine learning method. Using the ML-based model enables the model to update as the new configuration explored, which helps to achieve higher prediction accuracy. TVM proposes a ML-based model and a neural network model to predict the running time of generated code on the given hardware target. The input of the cost models is a lowered loop program, and the two models use different independent variables when making regression prediction. Specifically, the ML-based model uses features extracted from the input, and the neural network model uses the AST of programs. TVM claims that the accuracy of the two models is similar, and chooses the ML-based model (tree boosting) as the default cost model. Searching technique -1) Initialization and searching space determination: The initial option can either be set randomly or be set according to the known configurations, such as configurations given by users or historical optimal configurations. In terms of searching space, it should be specified before auto-tuning. TVM allows developers to specify the searching space with their domain-specific knowledge and provides automatic search space extraction for each hardware target based on the computational description. While TC relies on the compilation cache and the predefined rules. 2) Genetic algorithm: The genetic search algorithm used by TC considers each tuning parameter as gene and each configuration as a candidate. The new candidate is generated by two methods: hybrid and mutation. For each new candidate, three parents are selected based on their fitness, which means the higher the performance, the more likely to be selected, and the genes of parents are randomly selected and then form the new candidate. After that, the genes are assigned random values with a low probability called mutation rate, which is used for controlling the tradeoff between exploration and exploitation. There are still other parameters of algorithms needed to be set, such as iteration bounds and other options related to schedule choice. 3) Simulated annealing algorithm: TVM uses this algorithm. The initial configuration can be generated randomly and then predict a similar configuration randomly at each step. The step is considered to be successful if the new configuration has a lower cost predicted by a given cost model. If the cost model is modified, the algorithm starts from the last step, the searching result of the previous cost model. Performance Optimization -1) Parallelization: One direction for improving auto-tuning performance is parallelization. TC proposes a generic multi-threaded, multi-GPU strategy under the consideration that the genetic algorithm needs to evaluate all candidates before every next generating step. First, the strategy enqueues candidate configuration and compile them by multiple CPU threads. The generated code are evaluated on GPUs in parallel, and each candidate owns its fitness used by the parent choosing step. After the finish of the whole evaluation, the new candidate is generated by the search algorithm, and the new compilation job is enqueued, waiting for compiling by CPU. Similarly, TVM supports cross-compilation and RPC, which allows users to compile on the local machine and run the programs with different auto-tuning configurations on multiple targets. 2) Configuration reuse: Another direction for improving auto-tuning performance is to reuse the previous auto-tuning configurations. TC stores the fastest known generated code version corresponded with given configuration by compilation cache and uses tuple as cache entry to present necessary information related to the version. During the compilation, the cache is queried before each kernel optimization enabling persistence and reuse, and auto-tuning is triggered if cache miss. Similarly, TVM produces a log file that stores the optimal configurations for all scheduling operators and queries the log file for best configurations during compilation. It is worth mentioning that TVM performs auto-tuning for each operator in Halide IR (e.g., conv2d) rather than treat all operators as a whole, and thus the optimal configurations are for operators separately rather than the low-level IR.