Automatic Performance Tuning of Numerical Kernels

计算工程和科学中的大规模模拟通常花费大量时间在一些计算方法核心上，例如密集或稀疏矩阵向量乘积，结构化或非结构化网格上的松弛，或者吸引或排斥粒子对之间的力的计算。在为这些应用程序生成高性能库方面已经做了大量的工作，包括密集和稀疏线性代数，多重网格方法和n-body techniques.在这些应用程序级库中建立的一个想法是围绕一组数值核来组织计算，假设这些核将在每个感兴趣的硬件平台上高度优化。这种方法最著名的例子是BLAS（基本线性代数例程），用于构建LAPACK、ScaLAPACK和其他库; BLAS是由硬件供应商实现的，并且高度调整到每台机器的存储器层次结构。然而，这种方法受到内核数量增长、机器数量庞大、存储器层次结构深度增长和处理器复杂性的限制，以及在每台机器上对每个内核进行性能调优的难度。当执行特定于机器的调优时，这些内核中的绝大多数都容易受到大的加速提升的影响。然而，手工调优需要熟练工程师几周或几个月的时间，并且必须为每个微架构或操作系统更改重复这项工作。这项研究将致力于自动化的数值内核的架构相关的调整过程中，取代目前的手工调整过程与半自动化的搜索过程。这种方法的原型存在于密集矩阵乘法（Atlas和PHiPAC）、FFT（FFTW）和稀疏矩阵向量乘法（Sparsity）中。这些结果表明，我们经常可以在内核上做得和手工调优的供应商代码一样好，甚至更好。这些系统使用一个手写的“搜索定向代码生成器（SDCG）”来产生单个内核的许多不同实现，这些实现都运行在每个架构上，并选择最快的一个。这种方法将被扩展到更广泛的数值内核，通过结合编译器技术与算法特定的转换规则，自动化这些SDCGs. Finally的生产，该技术预计将是有用的，在传统的编译器，提供适当的抽象数据类型或注释是用来侧步骤非常困难或“不可能”的依赖性分析需要证明所需的代码转换。这项工作也应该刺激研究新的高层次的数值方法和架构，这两者都是有限的缺乏高度调谐内核。

Large scale simulations in computational engineering and science often spend a great deal of their time in a few computational methods kernels, such as dense or sparse matrix-vector products, relaxation on a structured or unstructured mesh, or the computation of forces between pairs of attracting or repelling particles. There has been a great deal of work in generating high performance libraries for these applications, including dense and sparse linear algebra, multigrid methods, and n-body techniques.One idea established in these application-level libraries is to organize the computations around a set of numerical kernels, with the assumption that these kernels will be highly optimized on each of the hardware platforms of interest. The best known example of this approach is the BLAS (the Basic Linear Algebra routines), which are used in building LAPACK, ScaLAPACK, and other libraries; the BLAS are implemented by hardware vendors and are highly tuned to the memory hierarchy of each machine.However, this approach is limited by the growing number of kernels, the large number of machines, the increasing depth of memory hierarchies and complexity of processors, and by the difficulty of performance tuning each kernel on each machine. The great majority of these kernels are susceptible to large speedups when machine-specific tuning is performed. However, the hand tuning takes weeks or months of a skilled engineer's time, and this work must be repeated for each micro-architecture, or operating system change. This research will work to automate the process of architecture-dependent tuning of numerical kernels, replacing the current hand-tuning process with a semi-automated search procedure. Prototypes of this approach exist for dense matrix-multiplication (Atlas and PHiPAC), FFTs (FFTW), and sparse matrix-vector multiplication (Sparsity). These results show that we can frequently do as well as or even better than hand-tuned vendor code on the kernels attempted. These systems use a hand-written "search directed code generator (SDCG)" to produce many different implementations of a single kernel, which are all run on each architecture, with the fastest one being selected. This approach will be extended to a much wider range of numerical kernels by combing compiler technology with algorithm-specific transformation rules to automate the production of these SDCGs.Ultimately, the technology is expected to be useful in conventional compilers, provided that appropriate abstract data types or annotations are used to side-step very difficult or "impossible" dependency-analysis needed to justify the desired code transformations. This work should also stimulate research into new high level numerical methods and architectures, both of which are limited by the lack of highly tuned kernels.