Automatic Performance Tuning of Numerical Kernels

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

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.