SOFTWARE: ACR: Advanced Code Generation for Digital Signal Processing Algorithms

本研究的目标是自动生成数字信号处理（DSP）变换算法的实现，这些算法适用于给定的现成计算平台，即，所生成的代码充分利用了体系结构特征和可用指令集，包括存储器层次结构、多处理器、向量指令、融合乘加指令和预取指令。我们将这种类型的代码称为“高级代码”，原因有两个：（1）代码使用的指令远远超出标准C或Fortran编程;（2）手动编写此类代码需要非常高的编程专业知识，包括汇编级编程和对平台架构的深入理解。我们的目标是雄心勃勃的：我们的方法基于以下几点：（1）我们将每个快速DSP变换算法表示为简洁的数学语言中的公式。(2)我们为每个变换导出了大量结构不同的快速算法或公式。 (3)这些不同的公式（即，算法）被有效地枚举和操纵。(4)我们自动将每个公式转换为高级代码。 (5)我们通过搜索替代公式和代码实现的空间来优化实现。步骤（4）是我们方法的关键要求--自动化步骤。换句话说，高级指令（包括向量指令、并行线程、融合乘加指令和预取指令）的适用性可以与我们的公式表示法中的数学构造相关。步骤（5）提供了代码对平台的调整和适应性，我们将研究从公式到高级代码的映射，并以一种适合于自动代码生成和优化的方式将其形式化。我们将开发一个编译器，翻译一个快速DSP算法的公式描述，可能会增加控制编码自由度的参数，到高级代码。最后，我们将构建一个“高级代码生成器”，它将我们的编译器与公式生成器和搜索模块连接起来，以自动探索结构上不同的快速算法空间和高级编码自由度空间。对于给定的DSP变换，我们的高级代码生成器会自动找到公式，即，算法，其结构允许最好的实现给定的可用高级指令和给定的计算平台.在对比其他方法，高级代码生成，包括使用优化C或Fortran编译器或手动编码的方法，我们的高级代码生成器自动化和集成的优化在数学层面的算法和优化在执行层面的机器特定的指令.这样，高级代码生成器就可以访问生成高质量代码所需的所有结构信息，并模仿了解并利用算法结构和给定体系结构来编写平台优化的高级代码的高技能程序员。 我们相信，我们的研究使得，为性能关键类的DSP算法，一个开拓性的一步，解决目前的基本问题之一，在软件开发的高性能科学计算：如何开发，合理的努力，最佳和便携式性能日益复杂和多样化的现成的计算平台。

The goal of this research is to automatically generate implementations of digital signal processing (DSP) transform algorithms that are adapted to a given off-the-shelf computing platform, i.e., the generated code takes full advantage of architectural features and available instructions sets, including the memory hierarchy, multiple processors, vector instructions, fused multiply-add instructions, and prefetching instructions. We refer to this type of code as "advanced code'' for two reasons: (1) the code uses instructions that aresignificantly beyond standard C or Fortran programming; and (2) manually writing such code requires a very high level of programming expertise including assembly level programming and a deep understanding of the platform's architecture. Our goal is ambitious: automatically generate code that competes with or outperforms expertly hand-tuned code for DSP algorithms.Our approach is based on the following: (1) We represent each fast DSPtransform algorithm as a formula in a concise mathematical language. (2) We derive for each transform a very large number of structurally different fast algorithms or formulas. (3) These different formulas (i.e., algorithms) are efficiently enumerated and manipulated. (4) We automatically translate each formula into advanced code. (5) We optimize the implementation by searching over the space of alternative formulas and code implementations.Step (4) is the key claim---the automation step---of our approach. In other words, the applicability of advanced instructions, including vector instructions, parallel threads, fused multiply-add instructions, and prefetching instructions, can be related to mathematical constructs in our formula notation. Step (5) provides thetuning and adaptability of the code to the platform.We will research the mapping from formulas to advanced code and formalize it in a way suitable for automatic code generation and optimization. We will develop a compiler that translates a formula description of a fast DSP algorithm, possibly augmented with parameters that control coding degrees of freedom, into advanced code. Finally, we will build an "Advanced Code Generator'' that interfaces our compiler with a formula generator and a search module toautomatically explore the space of structurally distinct fast algorithms and the space of advanced coding degrees of freedom. For a given DSP transform, our Advanced Code Generator automatically finds the formula, i.e., the algorithm, whose structure allows the best implementation given the available advanced instructions and given the computing platform.In contradistinction to other approaches to advanced code generation, including approaches using optimizing C or Fortran compilers or manual coding, our Advanced Code Generator automates and integrates the optimization at the mathematical level of algorithms and the optimization at the implementation level of machine-specific instructions. This way the Advanced Code Generator has access to all structural information necessary to produce high quality code andmimics a highly skilled programmer who understands and exploits the structure of algorithms and the given architecture to write platform-tuned advanced code. We believe that our research makes, for the performance-critical class of DSP algorithms, a pioneering step towards a solution for one of the present fundamental problems in software development for high performance scientific computing: How to develop, with reasonable effort, optimal and portable performance on increasingly complex and diverse off-the-shelf computing platforms.