Loop tiling and fusion are two essential transformations in optimizing compilers to enhance the data locality of programs. Existing heuristics either perform loop tiling and fusion in a particular order, missing some of their profitable compositions, or execute ad-hoc implementations for domain-specific applications, calling for a generalized and systematic solution in optimizing compilers. In this article, we present a so-called basteln (an abbreviation for backward slicing of tiled loop nests) strategy in polyhedral compilation to better model the interplay between loop tiling and fusion. The basteln strategy first groups loop nests by preserving their parallelism/tilability and next performs rectangular/parallelogram tiling to the output groups that produce data consumed outside the considered program fragment. The memory footprints required by each tile are then computed, from which the upward exposed data are extracted to determine the tile shapes of the remaining fusion groups. Such a tiling mechanism can construct complex tile shapes imposed by the dependences between these groups, which are further merged by a post-tiling fusion algorithm for enhancing data locality without losing the parallelism/tilability of the output groups. The basteln strategy also takes into account the amount of redundant computations and the fusion of independent groups, exhibiting a general applicability. We integrate the basteln strategy into two optimizing compilers, with one a general-purpose optimizer and the other a domain-specific compiler for deploying deep learning models. The experiments are conducted on CPU, GPU, and a deep learning accelerator to demonstrate the effectiveness of the approach for a wide class of application domains, including deep learning, image processing, sparse matrix computation, and linear algebra. In particular, the basteln strategy achieves a mean speedup of 1.8× over cuBLAS/cuDNN and 1.1× over TVM on GPU when used to optimize deep learning models; it also outperforms PPCG and TVM by 11% and 20%, respectively, when generating code for the deep learning accelerator.

Due to the missing of a good orchestration of loop transformations, existing optimizing compilers for deploying neural networks on GPU either parallelize reductions ineffectively or miss the fusion opportunities with other operators. Neural network models thus exhibit sub-optimal performance on GPU. We present a practical approach called Panamera for the effective parallelization of reductions in neural networks on GPU. Panamera first leverages loop coalescing to flatten the loop dimensions of reductions, converting all reduction operators into canonical forms eligible for the polyhedral model. Next, Panamera uses polyhedral transformations to reduce the data movements caused by unfused reductions and perform multi-block hardware binding not considered by many compilers. Finally, Panamera embeds a highly optimized routine implemented using GPU atomic instructions, further improving the performance of neural network models while guaranteeing the correctness of parallel reductions. The experimental results demonstrate the effectiveness of our approach: for single operators our code obtains a mean speedup of 33.7×, 3.5×, 5.4× and 9.6× over cuDNN, CUB, TVM and Ansor, for sub-graphs our approach outperforms cuDNN, TVM and Ansor by 9.5×, 2.6× and 2.7×, and for end-to-end workloads, a tensor compiler integrated with our approach outperforms them by 122.5%, 19.3% and 15.2%.

Existing tensor compilers have proven their effectiveness in deploying deep neural networks on general-purpose hardware like CPU and GPU, but optimizing for neural processing units (NPUs) is still challenging due to the heterogeneous compute units and complicated memory hierarchy.

Inverse lithography technology (ILT), also known as pixel-based optical proximity correction (PB-OPC), has shown promising capability in pushing the current 193 nm lithography to its limit. By treating the mask optimization process as an inverse problem in lithography, ILT provides a more complete exploration of the solution space and better pattern fidelity than the traditional edge-based OPC. However, the existing methods of ILT are extremely time-consuming due to the slow convergence of the optimization process. To address this issue, in this paper we propose a support vector machine (SVM) based layout retargeting method for ILT, which is designed to generate a good initial input mask for the optimization process and promote the convergence speed. Supervised by optimized masks of training layouts generated by conventional ILT, SVM models are learned and used to predict the initial pixel values in the ‘undefined areas’ of the new layout. By this process, an initial input mask close to the final optimized mask of the new layout is generated, which reduces iterations needed in the following optimization process. Manufacturability is another critical issue in ILT; however, the mask generated by our layout retargeting method is quite irregular due to the prediction inaccuracy of the SVM models. To compensate for this drawback, a spatial filter is employed to regularize the retargeted mask for complexity reduction. We implemented our layout retargeting method with a regularized level-set based ILT (LSB-ILT) algorithm under partially coherent illumination conditions. Experimental results show that with an initial input mask generated by our layout retargeting method, the number of iterations needed in the optimization process and runtime of the whole process in ILT are reduced by 70.8% and 69.0%, respectively.

Inverse lithography technology (ILT) is one of the promising resolution enhancement techniques (RET), as the advanced integrated circuits (IC) technology nodes still use the 193nm light source. Among all the algorithms for ILT, the level-set-based ILT (LSB-ILT) is a feasible choice with good production result in practice. However, existing ILT algorithms optimize mask at nominal process condition without giving sufficient attention to the process variations, and thus the optimized masks show poor performance with focus and dose variations. In this paper, we put forward a new LSB-ILT algorithm for process robustness improvement with attenuated Phase Shift Mask (att-PSM) which is extensively used in the semiconductor foundries. In order to account for the process variations in the optimization, we adopt a new form of the cost function by adding the objective function of process variation band (PV band) to the nominal cost. The test patterns are from the M1 layer of a 28nm layout. Experimental results show that our new algorithm has a larger process window (PW) and reduces the process manufacturability index (PMI) by 41.37% compared with the LSB-ILT algorithm without PV band consideration.

Inverse lithography technology (ILT) is one of the promising resolution enhancement techniques, as the advanced IC technology nodes still use the 193 nm light source. In ILT, optical proximity correction (OPC) is treated as an inverse imaging problem to find the optimal solution using a set of mathematical approaches. Among all the algorithms for ILT, the level-set-based ILT (LSB-ILT) is a feasible choice with good production in practice. However, the manufacturability of the optimized mask is one of the critical issues in ILT; that is, the topology of its result is usually too complicated to manufacture. We put forward a new algorithm with high pattern fidelity called regularized LSB-ILT implemented in partially coherent illumination (PCI), which has the advantage of reducing mask complexity by suppressing the isolated irregular holes and protrusions in the edges generated in the optimization process. A new regularization term named the Laplacian term is also proposed in the regularized LSB-ILT optimization process to further reduce mask complexity in contrast with the total variation (TV) term. Experimental results show that the new algorithm with the Laplacian term can reduce the complexity of mask by over 40% compared with the ordinary LSB-ILT.