Automatic Performance Tuning of Numerical Kernels

计算工程和科学中的大规模模拟通常将大量时间花在一些计算方法的核心上，例如密集或稀疏的矩阵-矢量乘积、结构化或非结构化网格上的松弛，或计算吸引或排斥粒子对之间的力。为这些应用程序生成高性能的库已经做了大量的工作，包括密集和稀疏线性代数、多重网格方法和n体技术。在这些应用程序级库中建立的一个想法是围绕一组数值内核来组织计算，并假设这些内核将在每个感兴趣的硬件平台上进行高度优化。这种方法最著名的例子是BLAS(基本线性代数例程)，它用于构建LAPACK、ScaLAPACK和其他库；BLAS由硬件供应商实现，并且高度调优到每台机器的内存层次结构。但是，这种方法受限于内核数量的增加、机器的数量、内存层次结构的深度和处理器的复杂性，以及在每台机器上调整每个内核的性能的难度。当执行特定于计算机的调优时，这些内核中的绝大多数都容易出现大幅加速。然而，手动调整需要几周或几个月的熟练工程师的时间，而且每次微体系结构或操作系统更改都必须重复这项工作。这项研究将致力于使依赖于体系结构的数值核的调优过程自动化，用半自动的搜索过程取代目前的手动调优过程。这种方法的原型有密集矩阵乘法(Atlas和PHiPAC)、快速傅立叶变换(FFTW)和稀疏矩阵向量乘法(稀疏性)。这些结果表明，我们经常可以在尝试的内核上做得和手动调优的供应商代码一样好，甚至更好。这些系统使用手写的“搜索定向代码生成器(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.