Automatic Performance Tuning of Numerical Kernels

数值内核的自动性能调优

• 批准号: 0090127
• 负责人: Katherine Yelick
• 金额: $ 49.77万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-07-01 至 2005-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0090127&HistoricalAwards=false
• 关键词: Automatic; Performance; Tuning; Numerical; Kernels

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.

计算工程和科学中的大规模模拟通常会花费大量时间在几种计算方法内核中，例如密集或稀疏的矩阵向量产品，在结构化或非结构化的网格上放松，或者在吸引或排斥颗粒的成对上的力量计算。在为这些应用程序生成高性能库方面，已经进行了大量工作，包括密集和稀疏的线性代数，多机方法和N体技术。在这些应用程序级别的库中建立的一个想法是，围绕这些数值核心组织了一组数字核，并借助这些kernels在每个方面都可以在每个核心上进行优化的平台来组织计算。这种方法的最著名示例是Blas（基本的线性代数例程），用于构建Lapack，Scalapack和其他库。 BLA由硬件供应商实现，并高度调整到每台机器的内存层次结构中。当进行机器特异性调整时，这些内核中的绝大多数都容易受到大加速度的影响。但是，手动调整需要数周或几个月的熟练工程师时间，并且必须重复每个微观架构或操作系统更改这项工作。这项研究将有助于自动化数值内核的体系结构调整过程，从而用半自动化的搜索过程替换当前的手工调节过程。该方法的原型存在用于密集的基质 - 型胶片（ATLAS和PHIPAC），FFTS（FFTW）和稀疏矩阵矢量乘数（Sparsity）。这些结果表明，与尝试的内核上的手工调整供应商代码相比，我们经常可以做到甚至更好。这些系统使用手写的“搜索定向代码生成器（SDCG）”来生成单个内核的许多不同实现，这些实现都在每个体系结构上运行，并且选择了最快的核心。通过将编译器技术与算法特定的转换规则梳理以自动化这些SDCG的生产，该方法将扩展到更广泛的数值内核，只要将技术用于常规编译器，前提是将适当的抽象数据类型或注释用于侧向核对或“不可能的“不可能”的依赖性依赖性的依赖性的依赖性的依赖性的依赖性的依赖性的规定，则该技术有用。这项工作还应刺激对新的高水平数值方法和体系结构的研究，这两者都受到缺乏高度调谐内核的限制。