Redundancy, retiming and data flow in compiling finite-difference applications for manycore architectures

有限差分法是计算科学和工程中最广泛使用的求解偏微分方程的方法，在地下图像重建、流体动力学、材料科学等领域都有重要的应用。有限差分求解器具有特有的循环和数据访问模式，这些模式受益于依赖于通用编译器中无法获得的应用程序知识的优化。Devito是在OPESCI项目中开发的一个软件，它为有限差分方法提供了一种高级语言，为这种特定于领域的编译器技术开辟了范围。这个项目的目标是探索这一前沿。我们要利用的关键思想是代数表达式的符号操作，以暴露冗余计算，并与何时对这些表达式求值，在何处存储它们以及何时预计算它们比重新计算它们更好的建模相一致。我们认为有一种统一的，甚至是最优的方式来做到这一点。我们研究理念的一个关键要素是软件工具的严格开发，这些工具可以在工业和科学重要性的各种现实问题上进行评估。这项工作将受到地震反演应用的推动（至少在最初），这将带来丰富的挑战。我们将瞄准最先进的并行硬件平台，包括多核、多线程和宽矢量架构，比如英特尔的Xeon Phi和Skylake处理器。

The finite difference method is the most widely-used approach to solving partial differential equations in computational science and engineering - with important applications from subsurface image reconstruction to fluid dynamics to materials science and beyond. Finite difference solvers have characteristic loop and data-access patterns that benefit from optimisations that rely on application knowledge not available in general-purpose compilers. Devito, a software developed in the OPESCI project, provides a high-level language for the finite difference method that opens up the scope for such domain-specific compiler techniques. The goal of this project is to explore this frontier. The key idea we aim to exploit is symbolic manipulation of algebraic expressions to expose redundant computations, and to do this in concert with modelling of when to evaluate such expressions, where to store them, and when pre-computing them is better than recomputing them. We think there is a way to do this in a unified, perhaps even optimal, way. A key element of our research philosophy is the rigorous development of software tools that can be evaluated on diverse real-world problems of industrial and scientific importance. The work will be driven (at least initially) by applications in seismic inversion, which provide a rich spectrum of challenges. We will target the most sophisticated parallel hardware platforms available, including manycore, multithreaded and wide-vector architectures - such as Intel's Xeon Phi and Skylake processors.