The Deep Learning Compiler: A Comprehensive Survey <s> Block-level optimizations. Algebraic simplification -The algebraic simplification optimizations consist of optimizations in three parts in both DL compilers and general-purpose compilers: <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> BIB001 </s> The Deep Learning Compiler: A Comprehensive Survey <s> Block-level optimizations. Algebraic simplification -The algebraic simplification optimizations consist of optimizations in three parts in both DL compilers and general-purpose compilers: <s> In recent years, there is a surge on machine learning applications in industry. Many of them are based on popular AI frameworks like Tensorflow, Torch, Caffe, or MxNet, etc, and are enpowered by accelerator platforms such as GPUs. One important challenge of running Tensorflow computations on GPUs is the fine granularity problem, namely, FLOPS of individual ops are far from enough to fully exploit the computing power of underlying accelerators. The XLA framework provides a solid foundation to explore this problem further. In this paper, we propose FusionStitching, a novel, comprehensive Op fusion and code generation system to stitch computations into large GPU kernels. Experimental results on four public models and two of our large inhouse applications show another 55% (geometric mean) reduction of GPU kernel launches, compared to the XLA fusion baseline. This increases the E2E performance of both of our latency critical inhouse applications up to 20%. <s> BIB002 </s> The Deep Learning Compiler: A Comprehensive Survey <s> Block-level optimizations. Algebraic simplification -The algebraic simplification optimizations consist of optimizations in three parts in both DL compilers and general-purpose compilers: <s> Frameworks for writing, compiling, and optimizing deep learning (DL) models have recently enabled progress in areas like computer vision and natural language processing. Extending these frameworks to accommodate the rapidly diversifying landscape of DL models and hardware platforms presents challenging tradeoffs between expressivity, composability, and portability. We present Relay, a new compiler framework for DL. Relay's functional, statically typed intermediate representation (IR) unifies and generalizes existing DL IRs to express state-of-the-art models. The introduction of Relay's expressive IR requires careful design of domain-specific optimizations, addressed via Relay's extension mechanisms. Using these extension mechanisms, Relay supports a unified compiler that can target a variety of hardware platforms. Our evaluation demonstrates Relay's competitive performance for a broad class of models and devices (CPUs, GPUs, and emerging accelerators). Relay's design demonstrates how a unified IR can provide expressivity, composability, and portability without compromising performance. <s> BIB003 </s> The Deep Learning Compiler: A Comprehensive Survey <s> Block-level optimizations. Algebraic simplification -The algebraic simplification optimizations consist of optimizations in three parts in both DL compilers and general-purpose compilers: <s> Performance optimization is the art of continuous seeking a harmonious mapping between the application domain and hardware. Recent years have witnessed a surge of deep learning (DL) applications in industry. Conventional wisdom for optimizing such workloads mainly focus on compute intensive ops (GEMM, Convolution, etc). Yet we show in this work, that the performance of memory intensive computations is vital to E2E performance in practical DL models. We propose \emph{FusionStitching}, a optimization framework capable of fusing memory intensive \emph{elementwise}, \emph{reduction} and fine grained \emph{GEMM/Batched-GEMM} ops, with or without data dependences, into large computation units, then mapping and transforming them into efficient GPU kernels. We formulate the fusion plan optimization as an integer linear programming (ILP) problem, and propose a set of empirical heuristics to reduce the combinatorial search space. In order to map optimized fusion plans to hardware, we propose a technique to effectively compose various groups of computations into a single GPU kernel, by fully leveraging on chip resources like scratchpads or registers. Experimental results on six benchmarks and four industry scale practical models are encouraging. Overall, \emph{FusionStitching} can reach up to 5.7x speedup compared to Tensorflow baseline, and achieves 1.25x to 1.85x performance speedups compared to current state of the art, with 1.4x on average (geometric mean). <s> BIB004
(1) algebraic identities, for example, with which we can change the computation of x × 1 to x; (2) strength reduction, with which we can replace a more expensive operator by a cheaper one, such as replacing x/2 with x × 0.5; (3) constant folding, with which we can replace the constant expressions by their values, such as replacing the expression x × 2 × 3 with their final value x × 6. They consider a sequence of operation nodes, then take advantage of commutativity, associativity, and distributivity of different kinds of operators to simplify the computation. Despite the typical operators (+, −, ×, ÷, etc.) described above, the algebraic simplification optimizations can also be applied to DL specific operations, such as reshape, transpose, and pooling, thus the operators can be reordered and sometimes eliminated, which reduces the redundancy and improves the efficiency. Here we show several common cases: 1)Optimization of reshape/transpose nodes -This optimization finds and removes reshape/transpose operations according to more specific characters than algebraic simplification. Take the matrix multiplication (GEMM) for example, there are two matrices (e. g., A and B) , both matrices are transposed (to produce A T and B T , respectively), then A T and B T are multiplied together. However, a more efficient way to implement GEMM is to switch the order of the arguments A and B, multiply them together, and then transpose the output of the GEMM. Effectively, this approach cuts two transpose operations down to just one, where this optimization can do that rewriting; 2)Optimization of transpose nodes -This optimization combines multiple consecutive transpose nodes into a single node, eliminates identity transpose nodes, and optimizes transpose nodes into reshape nodes when they actually move no data; 3)Optimization of pool nodes -This optimization swaps the order of adjacent pooling node and ReLU node so that the ReLU operator can operate on the smaller tensor. Because the ReLU operation occupies a small fraction of whole computations, this optimization may bring slight performance improvement; 4)Optimization of ReduceMean nodes -This optimization performs substitutions of ReduceMean with AvgPool node (in Glow) if the input of the reduce operator is 4D with the last two dimensions to be reduced. Operator fusion -Operator fusion is indispensable building block of dl compilers, and exactly itâĂŹs an essential optimization in dl compilers. It enables better sharing of computation, removal of intermediate allocations, facilitates further optimization by combining loop nests BIB003 , as well as reduces launch and synchronization overhead BIB001 . In TVM, the operators are classified into four categories: 1) injective (one-to-one map), 2) reduction (complex-in-fusible) 3) complex-outfusible (can fuse element-wise map to output, e.g., conv2d), and 4) opaque (cannot be fused, e.g., sort). When the operators are defined, their corresponding categories are determined. To that end, TVM designs several rules to perform the fusion: 1) multiple injective operators can be fused into a new injective operator, 2) a reduction operator can be fused with input injective operators before the input, 3) complex-out-operators can be fused with injective operators after the output. According to the operator categories and fusion rules, fusion can be performed conveniently. In Tensor Comprehension, fusion is conducted in a different way based on the automatic polyhedron transformations. However, how to identify and fuse more and more complicated graph patterns, such as blocks with multiple broadcast and reduce nodes, remains to be a problem. Recent work BIB004 BIB002 tries to tackle this problem and proposes a framework to explore and optimize aggressive fusion plans. It supports not only element-wise and reduction nodes but also other computation/memory intensive nodes with complex dependencies. Operator sinking -This optimization sinks operations such as transposes below operations like a batch normalization, ReLU, sigmoid, channel shuffle. By doing this, many similar operations are moved around and closer to each other, which creates more opportunities for the algebraic simplification.